JM: TypeInference: Loop invariant code motion




JavaScript Engine
7 years ago
6 years ago


(Reporter: bhackett, Assigned: bhackett)


(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)



(3 attachments, 2 obsolete attachments)



7 years ago
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.

Comment 1

7 years ago
Created attachment 497521 [details] [diff] [review]
exploratory patch

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?
Blocks: 619423
No longer blocks: 608741
Created attachment 498941 [details]
Attachment #498941 - Attachment mime type: application/octet-stream → text/plain
Created attachment 498942 [details]
hotspot disassembly of

java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Test

Comment 4

6 years ago
Created attachment 524447 [details] [diff] [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

Comment 5

6 years ago
Created attachment 524548 [details] [diff] [review]

Patch landed on JM.
Attachment #524447 - Attachment is obsolete: true
We merged Type Inference.
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.