Possible optimisation: delaying allocations

[stedolan]

Here is an optimisation that I would like the compiler to do, which I was somewhat surprised that none of Closure / Flambda1 / Flambda2 currently perform. Currently, this function:

let go c =
  let s = Some c in
  if c < 0 then None else s

compiles to this cmm:

(function camlTest__go_81 (c/83: val)
 (let s/84 (alloc 1024 c/83) (if (< c/83 1) 1 s/84)))

which unconditionally allocates. It would be better to substitute away the let, moving the allocation under the if, so that it only allocates when c < 0.

Some more realistic examples:

• Local functions:

  let f x ys =
    let aux s = s + x in
    match ys with
    | [] -> 42
    | y :: ys -> ... aux ...

  Ideally, the closure aux would only be allocated in the _ :: _ branch.

• Inlined functions:

  let[@inline] log_change ch = if !logging_enabled then log := ch :: !log
  let do_stuff n m = log_change (Do_stuff (n, m)); n + m

  Ideally, the allocation Do_stuff (n, m) would only occur when logging_enabled is true.

[lthls]

Flambda 2 (more precisely, the translation from flambda 2 to Cmm) used to do it, but we removed it as it messed with quite a few tests in the testsuite (and possibly some tests in the Jane Street code base too, though I don't remember the details).

I think there were also some plans for a precise analysis of the best place to box/unbox numbers; it's possible that we could fit regular allocations in the same framework. But I don't know how much progress has been done on this.

[mshinwell]

We started looking at partial dead code elimination which I think should fix this (and also the cases where unnecessary boxing occurs at loop exit points). We had to pause work on PDCE but will get back to it after the first production release.

If I understand correctly the substitutions that used to happen in the Flambda to Cmm translation would only take effect if the value was linearly used. The reason we stopped doing this is because people are writing tests that rely on exact placement of allocation. The debate here really comes down to what kind of effects you consider allocation to have.

[stedolan]

If these tests are so sensitive to the exact placement of allocations, do they break with safepoints as well?

[mshinwell]

I wouldn't have thought so, from what I remember, but people will have to watch out for that in due course. I think I might backport the safepoints patch well in advance of moving to 4.13, in fact.

[Gbury]

From what I remember, moving allocations like this had the unexpected result of breaking tests that try and check that some section of code does not allocate. (Technically, allocations have observable side-effects because of the functions in Gc which return the number of allocations done).

In cases where the move does not cross function application, i think that with PDCE we should be able to move such allocations (but @chambart would probably know better).