Last Comment Bug 618692 - JM: TypeInference: Loop invariant code motion
: JM: TypeInference: Loop invariant code motion
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
-- normal with 2 votes (vote)
: ---
Assigned To: Brian Hackett (:bhackett)
: Jason Orendorff [:jorendorff]
Depends on:
Blocks: 619423
  Show dependency treegraph
Reported: 2010-12-12 07:45 PST by Brian Hackett (:bhackett)
Modified: 2011-10-17 11:14 PDT (History)
12 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

exploratory patch (24.45 KB, patch)
2010-12-14 09:52 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review (592 bytes, text/plain)
2010-12-20 19:31 PST, Ed Lee :Mardak
no flags Details
hotspot disassembly of (7.82 KB, text/plain)
2010-12-20 19:32 PST, Ed Lee :Mardak
no flags Details
WIP (85.68 KB, patch)
2011-04-07 11:54 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (95.79 KB, patch)
2011-04-07 17:20 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review

Description User image Brian Hackett (:bhackett) 2010-12-12 07:45:48 PST
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 User image Brian Hackett (:bhackett) 2010-12-14 09:52:53 PST
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?
Comment 2 User image Ed Lee :Mardak 2010-12-20 19:31:49 PST
Created attachment 498941 [details]
Comment 3 User image Ed Lee :Mardak 2010-12-20 19:32:37 PST
Created attachment 498942 [details]
hotspot disassembly of

java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Test
Comment 4 User image Brian Hackett (:bhackett) 2011-04-07 11:54:19 PDT
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.
Comment 5 User image Brian Hackett (:bhackett) 2011-04-07 17:20:47 PDT
Created attachment 524548 [details] [diff] [review]

Patch landed on JM.
Comment 6 User image Tom Schuster [:evilpie] 2011-10-17 11:14:55 PDT
We merged Type Inference.

Note You need to log in before you can comment on or make changes to this bug.