Last Comment Bug 618690 - JM: TypeInference: Hoist array bounds checks
: JM: TypeInference: Hoist array bounds checks
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal with 1 vote (vote)
: ---
Assigned To: Brian Hackett (:bhackett)
:
:
Mentors:
Depends on:
Blocks: 619423
  Show dependency treegraph
 
Reported: 2010-12-12 07:33 PST by Brian Hackett (:bhackett)
Modified: 2014-09-10 22:57 PDT (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP (181.19 KB, patch)
2011-04-05 13:35 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (201.39 KB, patch)
2011-04-05 18:19 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review

Description Brian Hackett (:bhackett) 2010-12-12 07:33:48 PST
For loops like:

for (i = 0; i < n; i++)
  arr[i]

We can hoist the initialized-length check to the loop's preamble code provided we can determine that arr is not modified in the loop, that i and n are integers and that the length of arr cannot shrink.

This should generalize but not too broadly, as array-accessing loops tend to be written in similar ways and doing a full symbolic range analysis is complicated and takes time.  It should, however, handle loop forms like that in v8-crypto's am3, which looks like:

while(--n >= 0)
  arr[i++];
Comment 1 Brian Hackett (:bhackett) 2011-04-05 13:35:51 PDT
Created attachment 524086 [details] [diff] [review]
WIP

Determines when bounds checks can be hoisted for a few access patterns: x[n], x[i] where i is loop invariant, and x[i] where i is <= something as determined from a linear relationship in the loop condition.  Also factors loop register stuff out of FrameState and into a new LoopState file (paving the way to make FrameState a per-frame thing).
Comment 2 Brian Hackett (:bhackett) 2011-04-05 18:19:53 PDT
Created attachment 524112 [details] [diff] [review]
patch

Patch landed on JM.  This is mostly about adding the machinery so we can hoist array bounds checks, will circle back and improve robustness once LICM and property accesses are improved and we have a good corpus of the bounds checks we want to be able to hoist.

http://hg.mozilla.org/projects/jaegermonkey/rev/7928f2dc3d4d

function foo(x, n) {
  for (var i = 0; i < n; i++)
    x[i] = i;
  var q = 0;
  for (var i = 0; i < 100000; i++) {
    for (var j = 0; j < n; j++)
      q = x[j];
  }
  return q;
}
foo([], 1000);

js -m -n (old): 145
js -m -n (new): 110
js -m: 577
js -j: 374
d8: 150
Comment 3 AWAY Tom Schuster [:evilpie] 2011-10-17 11:14:56 PDT
We merged Type Inference.

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