Last Comment Bug 652520 - JM+TI: integer analysis
: JM+TI: integer analysis
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 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:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

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 User image 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 User image Brian Hackett (:bhackett) 2011-04-26 10:59:49 PDT
Created attachment 528356 [details] [diff] [review]

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++) { }

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

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 User image 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 User image 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.

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