Open Bug 938176 Opened 11 years ago Updated 4 months ago

Range Analysis: Support beta nodes for unsigned comparisons

Categories

(Core :: JavaScript Engine: JIT, enhancement, P5)

enhancement

Tracking

()

People

(Reporter: sunfish, Unassigned)

References

(Blocks 1 open bug)

Details

(Whiteboard: [lang=c++])

Bug 936737 disabled beta nodes for unsigned comparisons. It would be nice to implement proper support for unsigned comparisons, and remove the TODO for them in RangeAnalysis::addBetaNodes.
Whiteboard: [mentor=sunfish][lang=c++]
Mentor: sunfish
Whiteboard: [mentor=sunfish][lang=c++] → [lang=c++]
Can I get more info? #936737 says I'm not authorized to see it. Why beta nodes was disabled for unsigned types comparisons? This bug looks interesting for me.
Bug 936737 is now opened, so you can see the failing testcase there.

In the code under the comment "For integers, if x < c, the upper bound of x is c-1.", the SafeSub function tests for signed overflow, and that's not obviously correct for unsigned ranges.

CodeGenerator::emitAssertRangeI uses signed comparisons to check ranges, and I believe it needs to be taught to do unsigned comparisons when checking a range for an MBeta for an unsigned comparison. This is a tricky area, since IonMonkey doesn't have a proper UInt32 type, so uint32 values use the int32 type with a special case for the >>> operator.

Those are the potential issues that I'm aware of at present. Fixing this bug will require finding out if there are any other problems. Feel free to ask questions and I'll answer as best I can.
(In reply to Dan Gohman [:sunfish] from comment #2)
> Bug 936737 is now opened, so you can see the failing testcase there.
> 
> In the code under the comment "For integers, if x < c, the upper bound of x
> is c-1.", the SafeSub function tests for signed overflow, and that's not
> obviously correct for unsigned ranges.
> 
> CodeGenerator::emitAssertRangeI uses signed comparisons to check ranges, and
> I believe it needs to be taught to do unsigned comparisons when checking a
> range for an MBeta for an unsigned comparison. This is a tricky area, since
> IonMonkey doesn't have a proper UInt32 type, so uint32 values use the int32
> type with a special case for the >>> operator.
> 
> Those are the potential issues that I'm aware of at present. Fixing this bug
> will require finding out if there are any other problems. Feel free to ask
> questions and I'll answer as best I can.

This looks interesting.

""""
Comparisons: if you want to compare a with b as two 32-bit unsigned words, then you have two standard idioms:

if ((a + Integer.MIN_VALUE) < (b + Integer.MIN_VALUE)) { ... }

if ((a & 0xFFFFFFFFL) < (b & 0xFFFFFFFFL)) { ... }
""""

This is what I found on stackoverflow: http://stackoverflow.com/a/5622596.
Does this seem to be of any relevance?

Thanks!
That stackoverflow page discusses Java, and while JS is similar, some of the details are different. JS' `+` doesn't silently wrap by itself, and JS doesn't have a "long" type, so the specific idioms given here don't apply. The standard way to do an unsigned comparison in JS is

if ((a >>> 0) < (b >>> 0)) { ... }

Within IonMonkey, this pattern is handled specially as an unsigned comparison. The bug here is to add support to IonMonkey's range analysis code for unsigned comparisons.
Assuming p5 since I don't think unsigned comparisons are used that much, except on asm.js/wasm code.
Priority: -- → P5
sunfish I would love to work on this bug.
I have been contributing for the past few months, and I want to understand jit in process.
Any Irc on which I can find you for discussing the solution.
I apologize, but I myself am busy with other projects and not able to properly mentor this bug at this time.
Mentor: sunfish
Severity: normal → S3
Blocks: sm-jits
Severity: S3 → N/A
Summary: Beta nodes for unsigned comparisons → Range Analysis: Support beta nodes for unsigned comparisons
You need to log in before you can comment on or make changes to this bug.