Closed Bug 618692 Opened 9 years ago Closed 8 years ago

JM: TypeInference: Loop invariant code motion


(Core :: JavaScript Engine, defect)

Not set





(Reporter: bhackett, Assigned: bhackett)


(Blocks 1 open bug)



(3 files, 2 obsolete files)

JM should support loop invariant code motion in the following cases:

- Arithmetic on variables not modified by the loop.
- Slot pointers for arrays we can determine don't grow.
- Elements of arrays we can determine aren't modified.
- Properties of objects we can determine aren't modified.

These will be computed in the loop's preamble and then either carried in registers or spilled to temporary stack space, as for frame entries.  These all behave like stack temporaries, except slot pointers (which aren't a Value), so the FrameState should not need too much modification.
Attached patch exploratory patch (obsolete) — Splinter Review
This adds the FrameState infrastructure needed to manage loop invariant temporaries, including letting them be carried around loops.  For GETELEM it carries slots pointers with no bounds or other correctness checks, just want to measure how much this affects times.

function foo(n) {
  var a = Array(n);
  for (var i = 0; i < n; i++)
    a[i] = 1;
  var k = 0;
  for (var i = 0; i < 100000; i++) {
    for (var j = 0; j < n; j++)
      k += a[j];
for (var i = 100; i < 1000; i += 100)

Times for this and equivalent C/Java programs:

gcc -O3            333 (with noinline, -m32)
java               200 (yikes!)
d8 (crankshaft)    983
js -m (old infer)  823
js -m (new infer)  662
js -m              3173
js -j              2120
jsc                2620

So 33% faster than crankshaft, 5x as fast as current JM, 2x slower than comparable C.  I'd like to figure out what's going on with the C code, because the code GCC is generating is not too crazy and not too far off from our code (slow script check excepted; dropping this improves the time to 635).  Any way to get Java to spew the magic it's doing?
Attached file
Attachment #498941 - Attachment mime type: application/octet-stream → text/plain
java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Test
Attached patch WIP (obsolete) — Splinter Review
WIP.  As for bounds check hoisting, the initial patch will be getting the LICM machinery into place and followup work will improve the robustness.  This one only does LICM for slot pointers on arrays whose bounds checks have been hoisted.

The idea behind LICM is that we want to track 'soft' loop invariants, i.e. those we can determine are not directly modified by the JIT code in the loop.  Whenever we call into C++ or make a scripted call (things which we won't want to do in loops with invariant code, though we will eventually be able to inline calls in loops with invariant code), all the invariant values are restored immediately afterwards, picking up any side effects.

For 'hard' invariants on values we know won't be modified anywhere else (only using non-escaping locals/args) this restoration isn't really required, but is still done as we store the temporaries in the space used for the next stack frame.
Assignee: general → bhackett1024
Attachment #497521 - Attachment is obsolete: true
Attached patch patchSplinter Review
Patch landed on JM.
Attachment #524447 - Attachment is obsolete: true
We merged Type Inference.
Closed: 8 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.