I need to be reassured that this doesn't degrade performance, esp. for Cload.

We can try to run Louis's benchmarking suite on this, although I'm not sure how much is running on trunk yet.

@chambart I thought Flambda would be immune to this but I think I might be wrong---it looks like [Un_anf] might be able to generate e.g. applications that contain side effects. (See the comment "When sequences of let-bindings...")

Make sure you test x86-32 bits with floating-point codes. Your change has potential to kill the way ocamlopt utilises the x87 FP stack.

@xavierleroy What about if we annotated Cload as to whether it is reading from a mutable field? Apparently in multicore the code up to Cmmgen already knows this property, so we could use that to obtain this annotation. Then we could prevent only the loads which read from mutable fields from being re-ordered.

Mutability information is always good to have. But many FP loads that are performance critical are from mutable storage (arrays, mutable unboxed record fields), so there is still much potential for performance breakage, esp on x86-x87.

The first version of this had dire performance even on normal x86-64. I've made a revised version which will be benchmarked shortly.

@chambart This issue appears to be more serious than I first thought: it looks like code that does not depend on unspecified evaluation order can be incorrectly re-ordered as a result of this bug when compiled with Flambda. (Thanks to Yaron Minsky for hard questioning that lead me to construct this test case.)

let i = ref 0

let f x y =
  Printf.printf "%d %d\n" x y;
  0
[@@inline never]

let foo _ = ()

let foobar baz =
  let incr_i _ =
    incr i;
    !i
  in
  let b = !i in
  let z = foo 42 in
  let a = (incr_i [@inlined never]) z in
  let x = f a b in
  x + 1

let () =
  ignore ((foobar 0) : int)

I think this is because we assume during Un_anf that the backend is always going to evaluate right-to-left. For example, the above code built with Flambda (at the default optimization level) produces the following Clambda for foobar:

(+
  (apply* camlBreak_eval_order__f_21 
    (apply* camlBreak_eval_order__incr_i_77  0a)
    (field 0 (field 0 "camlBreak_eval_order__Pmakeblock_124")))
  1)

(camlBreak_eval_order__Pmakeblock_124 is the reference called i.)

This bug does at least seem rather difficult to trigger because the "let-moveable" transformation in Un_anf is very conservative. Once we manage to fix this problem in a satisfactory manner we should consider applying this to the 4.04 branch also.

I'm still working on this problem, but as an aside, it looks like the list of side-effecting expressions in is_simple_expr may be missing some cases even ignoring Cload (Ccheckbound in particular is absent, and can raise an exception). (Actually never mind, I see this was noted above.)

This revised version is ready for review for 4.05. There are two parts:

1. Addition of mutability information to Cload. This is deliberately conservative at the moment.
2. A simple effect/coeffect analysis in Selectgen to restrict the movement of expressions to avoid the original evaluation order problem. (Note that deferral of expressions is still guarded by the original is_simple_expr.)

A substantial amount of effort has been invested in this patch to try to ensure that any performance degradation is kept to a minimum. The evolution of the code has largely been guided by benchmarking.

The multicore devs have a patch to propagate mutability information from earlier in the compiler which can link up with the new annotation on Cload and remove the need for the special case tracking the environment parameter.

We also have a 4.03 version of this patch (being used internally at Jane Street); performance numbers on x86-64 Linux can be seen here:
http://bench.flambda.ocamlpro.com/compare?test=2017-02-12-2300%2F4.03.1%2B%2Bpr966%2Bbench&reference=2017-02-12-2300%2F4.03.1%2Bdev%2Bbench

This patch is being re-tested on i386 32-bit at present and numbers should be available shortly. I expect it to show a degradation of a couple of percent on floating-point intensive work.

One of the benchmarks exhibits a small difference in allocation numbers but a large difference in compactions. It is believed that this is because of potential variable lifetime changes as a result of this patch. For example for some function alloc which allocates, the code:

foo(alloc(), load block[0])

was effectively translated as:

let alloc_result = alloc () in
foo(alloc_result, load block[0])

With this patch, we instead get:

let block_result = load block[0] in
let alloc_result = alloc () in
foo(alloc_result, block_result)

As such, if block is dead after the load, it might be collected during the call to alloc. Without the patch it would live for longer.

I've reviewed this, it looks fine.

We have two positive reviews so this is good to go. @mshinwell please remove the unrelated whitespace changes, then go ahead and merge.

I've addressed all of the code review comments save for the one about rewriting the testcases in Cmm, which I think is going to have to wait, and one I don't understand about overloading. I have asked @chambart about the latter. This should be ready for merging shortly.

The overloading comment was I believe supposed to say overriding; there should be no issue, since none of the "emit_parts*" functions are exposed in the .mli.

@lpw25 has read the post-code-review changes so I'm going to merge this now. I've asked @chambart to eyeball them in any case, but I fully expect that to be fine.