JM: TypeInference: Loop invariant code motion

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
7 years ago
6 years ago

People

(Reporter: bhackett, Assigned: bhackett)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(3 attachments, 2 obsolete attachments)

(Assignee)

Description

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.
(Assignee)

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];
  }
  print(k);
}
for (var i = 100; i < 1000; i += 100)
  foo(i);

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

Comment 2

7 years ago
Created attachment 498941 [details]
Test.java

Updated

7 years ago
Attachment #498941 - Attachment mime type: application/octet-stream → text/plain

Comment 3

7 years ago
Created attachment 498942 [details]
hotspot disassembly of Test.foo

java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Test
(Assignee)

Comment 4

6 years ago
Created attachment 524447 [details] [diff] [review]
WIP

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
(Assignee)

Comment 5

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

Patch landed on JM.

http://hg.mozilla.org/projects/jaegermonkey/rev/6228c71f3994
Attachment #524447 - Attachment is obsolete: true
We merged Type Inference.
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.