Simplify doesn't seem to like symbol grouping from Lambda_to_flambda

[Keryan-dev]

Working on PR #540 and #541, which need to group symbols of closures and code to have a correct order of declarations. I stumbled on failures in Simplify and Un_cps.

The following examples are run with #541 which group every symbols in a single let-binding.

let f n =
  let rec loop i =
    loop (i + n)
  in
  loop 0

It gives us after CPS conversion (in a concise form):

let-symbol f_0_0_code = (ref to loop_1_1_code in closure)
and loop_1_1_code = (no dependencies)
and f_0 = (closure for f_0_0_code)

To which Simplify react with:

>> Fatal error: Patricia_tree.disjoint_union: key f_0_0_code is in intersection

Tweaking the example we can obtain a different error:

let g m n = m - n
let f n =
  let rec loop i =
    if i >= n then g n 42 else
    loop (i + 1)
  in
  loop 0

let-symbol g_0_0_code = (no dependencies)
and f_1_1_code = (ref to loop_2_2_code in closure)
and loop_2_2_code = (ref to symbol g_0)
and g_0 = (closure for g_0_0_code)
and f_1 = (closure for f_1_1_code)

>> Fatal error: Code ID camlTest__loop_2_5_code not bound
Context is: translating function camlTest__f_1_3_code to Cmm with return cont k69, exn cont k70 and body:

In this case, Simplify produces:

let-symbol loop_2_2_code = (ref to symbol g_0)
and f_1_1_code = (ref to loop_2_2_code in closure)
and g_0_0_code = (no dependencies)
and g_0 = (closure for g_0_4_code) (* ! *)
and g_0_4_code = (no dependencies)
and f_1 = (closure for f_1_3_code) (* ! *)
and f_1_3_code = (ref to loop_2_5_code in closure) (* ! *)

So we have g_0_0_code, f_1_1_code and loop_2_2_code unused and loop_2_5_code undefined.

Going further with #540, which sorts the declarations to group symbols only where its needed.

The examples above are no longer an issue but we can still find code that triggers odd behaviors:

let rec f w =
  let fa, af = f w in
    (fun x -> fa x),
    (fun x -> af x)

let-symbol anon_1_1_code = (no dependencies)
           anon_2_2_code = (no dependencies)
let-symbol f_0 = (closure for f_0_0_code)
and f_0_0_code = (ref to anon_1_1_code in closure
                  ref to anon_2_2_code in closure
                  ref to symbol f_0)

>> Fatal error: Code ID anon_1_1_code not bound

After simplify:

let-symbol anon_1_1_code = (deleted)
           anon_2_2_code = (no dependencies) (* ! *)
           anon_1_4_code = (no dependencies)
           anon_2_5_code = (no dependencies)
let-symbol f_0_0_code = (ref to anon_1_1_code in closure
                         ref to anon_2_2_code in closure
                         ref to symbol f_0)
and f_0 = (closure of f_0_3_code) (* ! *)
and f_0_3_code = (ref to anon_1_4_code in closure
                  ref to anon_2_5_code in closure
                  ref to symbol f_0)

So we have f_0_0_code and anon_2_2_code unused but not deleted, which causes the error. Unlike the previous example the code would be correct by deleting them.

For completeness, the same example with #541 raises:

>> Fatal error: Patricia_tree.disjoint_union: key f_0_3_code is in intersection