940864 - OdinMonkey: Incorrect result with >>> % >>

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Jesse Ruderman]

function a()
{
    "use asm";
    function f()
    {
        return (((((-1) >>> (0+0)) | 0) % 10000) >> (0+0)) | 0;
    }
    return f;
}
assertEq(a()(), -1);


With asmjs enabled:  Assertion failed: got 7295, expected -1
With --no-asmjs:     Pass


The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/29a1d64653e8
user:        Dan Gohman
date:        Tue Oct 15 20:49:43 2013 -0700
summary:     Bug 925586 - IonMonkey: Make range analysis use type information consistently. r=nbp

Comment 1

[Dan Gohman [:sunfish]]

Bug 891534 introduced range analysis code to convert MDiv and MMod to unsigned. However, the asm.js front-end omits the inner |0 under the expectation that when it creates an MMod (rather than an AsmJSUMod) it will always get a signed mod. Since it doesn't see a |0, range analysis sees the >>>0 as the left operand of the mod, so it converts the mod to unsigned.

One way to solve this would be to move the unsigned mod detection code out of range analysis and into an MMod::infer, to be called at IonBuilder time. This way it wouldn't ever see code with |0 stripped out. However, this would require teaching other parts of range analysis to know that values can have magical unsigned behavior even without >>>.

Another way to solve this would be to introduce AsmJSSMod/AsmJSSDiv, signed counterparts to AsmJSUMod/AsmJSUDiv.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: range-udivormod.patch

Bug 891534 added an unsigned flag to MDiv and MMod to let non-asm.js code get some of the same benefit as asm.js code was getting with MAsmJSUDiv and MAsmJSUMod. This patch takes the next logical step, and makes the regular MMod and MDiv support everything that asm.js needs, moves asm.js over to using them, and removes MAsmJSUDiv and MAsmJSUMod.

The main bug fix is moving the code that converts signed MDiv/MMod to unsigned out of RangeAnalysis and into code called from IonBuilder. This prevents it from seeing the code with |0 omitted. It also eliminates some redundancy, since it's doing effectively the same type inference that the asm.js front-end is already doing, so it doesn't need to be re-done on the non-asm.js path.

The rest of the patch is changes that were needed to support that fix. This means that unsigned MDiv and MMod may exist earlier than before, so RangeAnalysis needs to cope with them, and it means that there may be unsigned MDiv/MMod which may still be fallible, so codegen needs to have more complex zero checks.

Comment 3

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #1)
> Another way to solve this would be to introduce AsmJSSMod/AsmJSSDiv, signed
> counterparts to AsmJSUMod/AsmJSUDiv.

Wouldn't it be easier to solve all these issues by adding a flag on MUrsh to make MustBeUInt32 fail if AsmJS has at least one path which wrap the result to an int32?  Note that this flag would be similar to having a MIRType_Int32 instead of MIRType_UInt32 as a result type of MUrsh.

Moving the logic to IonBuilder implies that we want everybody to explicit the sign of each operands with to enable unsigned division & modulo.  Using the flag to disable such optimization implies that we keep this optimization while fixing the lack of information provided by AsmJS.

Ideally the flag should be part of the operand of the MInstruction that we are analyzing.  In the worse case we can think of isLhsSigned & isRhsSigned, but we would need to be careful with the Range constructor build out of a MDefinition as we would need to wrapAroundToInt32 if we have an unsigned operand.

Comment 4

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #3)
> (In reply to Dan Gohman [:sunfish] from comment #1)
> > Another way to solve this would be to introduce AsmJSSMod/AsmJSSDiv, signed
> > counterparts to AsmJSUMod/AsmJSUDiv.
> 
> Wouldn't it be easier to solve all these issues by adding a flag on MUrsh to
> make MustBeUInt32 fail if AsmJS has at least one path which wrap the result
> to an int32?  Note that this flag would be similar to having a MIRType_Int32
> instead of MIRType_UInt32 as a result type of MUrsh.

I don't like having a flag on a node describing what users of the node are doing. If a node has multiple users, and some of them wrap the result to int32, they shouldn't cause other users which don't, to see the node differently.

> Moving the logic to IonBuilder implies that we want everybody to explicit
> the sign of each operands with to enable unsigned division & modulo.  Using
> the flag to disable such optimization implies that we keep this optimization
> while fixing the lack of information provided by AsmJS.

I tend to think of signed and unsigned divison/remainder/modulus as being different kinds of opcodes. To me, it's perfectly natural for MIR producers to decide which opcode they want up front. This is what asm.js is already doing, and my proposed patch makes IonBuilder consistent with that.

Also, this way of handling unsigned is consistent with MCompare's way of handling unsigned.

> Ideally the flag should be part of the operand of the MInstruction that we
> are analyzing.  In the worse case we can think of isLhsSigned & isRhsSigned,
> but we would need to be careful with the Range constructor build out of a
> MDefinition as we would need to wrapAroundToInt32 if we have an unsigned
> operand.

Having separate flags for each operand sounds more confusing. I don't think we need the complexity that would result from having to consider cases where one operand is signed and the other is unsigned.

Comment 5

[Dan Gohman [:sunfish]]

Attachment: range-udivormod.patch

This just refreshes the patch and fixes build errors on ARM.

Comment 6

[Dan Gohman [:sunfish]]

Attachment: range-optimize-div-mod.patch

This patch implements the optimization to have range analysis form unsigned mod/div when possible. This seems to catch more cases than the old optimization removed by the other patch.

Comment 7

[Dan Gohman [:sunfish]]

Comment on attachment 8336389 [details] [diff] [review]
range-udivormod.patch

Actually, this patch is not ready yet.

Comment 8

[Dan Gohman [:sunfish]]

Attachment: simple-ursh-fix.patch

My previous patches were a bit too ambitious here. Here's a patch which just fixes the bug, in a simple way.

Comment 9

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0a188ddb392a

Comment 10

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/0a188ddb392a