Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stack overflow in compiler with flambda #8921

Closed
RealyUniqueName opened this issue Sep 6, 2019 · 15 comments

Comments

@RealyUniqueName
Copy link

commented Sep 6, 2019

Sorry, I couldn't reduce this to a self contained sample.
Here is the project: https://github.com/RealyUniqueName/haxe/tree/flambda_bug
Setup steps:

$ git clone --depth=1 --recursive --single-branch --branch flambda_bug git@github.com:RealyUniqueName/haxe.git
$ cd haxe
$ opam pin add haxe . --no-action
$ opam install haxe --deps-only

Then trying to build it with ocaml switch with flambda (tried 4.06...4.08.1) I get this error:

$ make
<...>
(ocamlfind ocamlopt -bin-annot -safe-string -thread -g -w -3 -w -40  -I libs/extlib-leftovers -I libs/extc -I libs/neko -I libs/javalib -I libs/swflib -I libs/ttflib -I libs/ilib -I libs/objsize -I libs/pcre -I libs/ziplib -I _build/src/core -I _build/src/core/ds -I _build/src/core/json -I _build/src/core/display -I _build/src/syntax -I _build/src/context -I _build/src/context/display -I _build/src/codegen -I _build/src/codegen/gencommon -I _build/src/generators -I _build/src/generators/jvm -I _build/src/optimization -I _build/src/filters -I _build/src/macro -I _build/src/macro/eval -I _build/src/macro/eval/bytes -I _build/src/typing -I _build/src/compiler -package unix -package str -package threads -package dynlink -package sedlex.ppx -package xml-light -package extlib -package ptmap -package sha -c _build/src/typing/typeload.ml 2>tmp.tmp && sed -e 's/_build\/src\//src\//' tmp.tmp) || (sed -e 's/_build\/src\//src\//' tmp.tmp && exit 1)
Fatal error: exception Stack overflow
Raised by primitive operation at file "hashtbl.ml", line 196, characters 9-23
Called from file "asmcomp/compilenv.ml", line 304, characters 8-47
Called from file "asmcomp/import_approx.ml", line 193, characters 10-54
Called from file "asmcomp/import_approx.ml", line 219, characters 16-35
Called from file "asmcomp/import_approx.ml", line 222, characters 31-59
Called from file "middle_end/simple_value_approx.ml", line 716, characters 32-57
Called from file "array.ml", line 132, characters 21-43
Called from file "middle_end/simple_value_approx.ml", line 704, characters 6-68
Called from file "middle_end/simple_value_approx.ml", line 738, characters 16-66
Called from file "array.ml", line 132, characters 21-43
<...>
Called from file "array.ml", line 132, characters 21-43
Called from file "middle_end/simple_value_approx.ml", line 704, characters 6-68
Called from file "middle_end/simple_value_approx.ml", line 738, characters 16-66
Makefile:322: recipe for target '_build/src/typing/typeload.cmx' failed

Now if I go to https://github.com/RealyUniqueName/haxe/blob/60f11d1/src/typing/typeload.ml#L547-L552 and replace t_dynamic lines with assert false, then typeload.ml is compiled successfully.

if Diagnostics.is_diagnostics_run p then begin
	delay ctx PForce (fun () -> DisplayToplevel.handle_unresolved_identifier ctx name p true);
	t_dynamic (* replace with `assert false` *)
end else if ctx.com.display.dms_display && not (DisplayPosition.display_position#enclosed_in pn) then
	t_dynamic  (* replace with `assert false` *)
else

But then the next file with t_dynamic fails with the same stack overflow.

t_dynamic is a recursive value of a variant type:

let rec t_dynamic = TDynamic t_dynamic

https://github.com/RealyUniqueName/haxe/blob/60f11d1/src/core/type.ml#L447

TDynamic is a tag of this variant:

type t =
	| TMono of t option ref
	| TEnum of tenum * tparams
	| TInst of tclass * tparams
	| TType of tdef * tparams
	| TFun of tsignature
	| TAnon of tanon
	| TDynamic of t
	| TLazy of tlazy ref
	| TAbstract of tabstract * tparams

https://github.com/RealyUniqueName/haxe/blob/60f11d1/src/core/type.ml#L54-L63

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

It's clear from the stack trace that we're creating a recursive approximation for this value via a symbol. My understanding is that this is not supposed to happen, so I think the fault lies with the code producing this approximation rather than with the Simple_value_approx.meet code which is looping.

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

I've managed to reproduce with a smaller example :

(* a.ml *)
type t = S of t

let rec t = S t
(* b.ml *)
let f () =
  if Sys.opaque_identity true then A.t
  else A.t

I'll investigate a bit further, but if someone else wants to have a look it should help.

(Edited to an even smaller example)

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

So, it turns out that the Simple_value_approx.meet code tries to find approximations for symbols through its really_import_approx argument, so in the case of recursive values it will indeed recursively scan the value indefinitely.
An easy fix for this particular case is to add a case in meet for identical symbols, but of course it's still possible to craft more complicated recursive definitions that will send it into an infinite loop anyway.
I'll discuss with @chambart about a proper fix, in the meantime there's a number of ways you can step around the problem, one of them being to replace the definition of t_dynamic by:

let t_dynamic =
  let rec t_dynamic_ = TDynamic t_dynamic_ in
  Sys.opaque_identity t_dynamic_
@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

As I said above: I don't think it is the meet code that is incorrect. I think that in current flambda the approximation for a symbol is not supposed to reference itself. The approximation for t in your example should be roughly Block [Unknown].

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

How would you handle mutually recursive definitions ?

let rec x = S y
and y = S x

Currently, the approximation for x is Block [Symbol y] (and reciprocally for y), so you would need some way to find out that the definitions are actually cyclic.
I guess you could patch approximations for Let_rec_symbol so that any symbol that is being defined is replaced by Unknown in the approximation, is that more or less what you had in mind ?

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

is that more or less what you had in mind ?

I was basically thinking that we could just remove the line:

let approx = A.augment_with_symbol approx symbol in

in define_let_rec_symbol_approx. I think that should prevent recursion coming from Let_rec_symbol.

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

I am now a little worried that we may have a similar problem with Let_rec because the augment_with_var seems to be built into Env.add for the variable case. So we should check that whilst we are at it.

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

I don't think define_let_rec_symbol_approx creates the self-referencing approximations that are the problem. The reason I need two files for my smaller example is that I need to have an approximation built by Build_export_info then read by Import_info to get the bug.
I was trying to see if I could fix the bug by preventing Build_export_info from creating recursive approximations.

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

The reason I need two files for my smaller example is that I need to have an approximation built by Build_export_info then read by Import_info to get the bug.

I hadn't noticed that it was two files. That's somewhat reassuring: Let_rec_symbol must already be protected from this in some way, and presumably so is Let_rec.

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

I have a patch that replaces recursive symbols by Value_unknown in Build_export_info; if you agree that this is a good way to fix the bug, I can submit it as a pull request so that we can work on the implementation details.

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

It looks like you could probably mark symbols as recursive in the Build_export_info.Env.t and then in
approx_of_constant_defining_value_block_field and descr_of_named you would check if the symbol was recursive and produce Value_unknown instead of Value_symbol in those cases.

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

(Looks like you wrote the code about 1 minute quicker than I could describe it).

@lpw25

This comment has been minimized.

Copy link
Contributor

commented Sep 6, 2019

Yeah, make a PR with what you've got and we'll discuss it there.

@RealyUniqueName

This comment has been minimized.

Copy link
Author

commented Sep 6, 2019

in the meantime there's a number of ways you can step around the problem, one of them being to replace the definition of t_dynamic by:

let t_dynamic =
  let rec t_dynamic_ = TDynamic t_dynamic_ in
  Sys.opaque_identity t_dynamic_

That works. Thank you.

@lthls

This comment has been minimized.

Copy link
Contributor

commented Sep 9, 2019

The PR is ready there: #8924

@chambart chambart closed this in f814450 Sep 11, 2019
gasche added a commit that referenced this issue Sep 11, 2019
Fixes #8921

(cherry picked from commit f814450)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.