652520 - JM+TI: integer analysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

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 [Laid off!]]

Attachment: 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 [Laid off!]]

Attachment: 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]

Still working on this, or is it a WONTFIX since IM is on the way?

Comment 4

[Brian Hackett [Laid off!]]

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