Last Comment Bug 652520 - JM+TI: integer analysis
: JM+TI: integer analysis
Status: RESOLVED FIXED
:
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)
:
:
Mentors:
Depends on:
Blocks: 619423 650496
  Show dependency treegraph
 
Reported: 2011-04-25 06:16 PDT by Brian Hackett (:bhackett)
Modified: 2012-01-30 11:11 PST (History)
9 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP (34.59 KB, patch)
2011-04-26 10:59 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
WIP 2 (80.24 KB, patch)
2011-04-27 13:25 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review

Description Brian Hackett (:bhackett) 2011-04-25 06:16:03 PDT
Spun off from bug 650496, as this should get its own tracking.  We want to eliminate integer overflow checks where possible within loops, this can make a significant difference in crypto code.  This covers both eliminating overflow checks on operations which we can prove don't overflow via interval analysis, and on operations which could overflow (and have overflowed, even) but where overflows are not observable because the result definitely flows through a bitwise operation.
Comment 1 Brian Hackett (:bhackett) 2011-04-26 10:59:49 PDT
Created attachment 528356 [details] [diff] [review]
WIP

Within loops, eliminate overflow checks on add/sub which we can determine will not overflow based on the loop test.  A lot of overlap and reused code with array bounds check hoisting.  Not sure why I wrote these off for so long, but the jump-on-overflows *do* cost a lot once other sources of slowdown (spill code, type tests, etc.) have been removed.

function bar(x) {
  for (var i = 0; i < x; i++) { }
}
bar(1000000000);

-m -n (before): 1077
-m -n (after):  719
d8: 725
-j: 1950
-m: 3232
Comment 2 Brian Hackett (:bhackett) 2011-04-27 13:25:47 PDT
Created attachment 528698 [details] [diff] [review]
WIP 2

Updated with more analysis stuff:

- Pulls in ranges from bitops with an interval analysis.  This interval analysis behaves in pretty much the same way as the one in Nanojit, but operates on the SSA form so can see outside of loops (but not into callers).  This info is used to identify adds/subs/muls that can't overflow.

- Introduce the idea of a constrained loop, which contains only int/double arithmetic and array accesses.  If we can determine the result of an add or mul within this loop must flow to a bitop in the same iteration of the loop, then overflows in the add or negative zeroes produced by the mul are ignored.

Increases v8-crypto score from 9600 to 12200, not robust enough for pbkdf2 yet.
Comment 3 Paul Wright 2012-01-30 10:10:24 PST
Still working on this, or is it a WONTFIX since IM is on the way?
Comment 4 Brian Hackett (:bhackett) 2012-01-30 11:11:02 PST
Hmm, this got committed without any update to the bug.  These analyses are going to get ported to IM before too long I think.

https://hg.mozilla.org/mozilla-central/rev/c03780e2597b

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