OdinMonkey: Incorrect result with >>> % >>

RESOLVED FIXED in mozilla28

Status

()

Core
JavaScript Engine: JIT
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: Jesse Ruderman, Assigned: sunfish)

Tracking

(Blocks: 2 bugs, {regression, testcase})

Trunk
mozilla28
x86_64
Mac OS X
regression, testcase
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 3 obsolete attachments)

(Reporter)

Description

5 years ago
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
(Assignee)

Comment 1

5 years ago
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.
Assignee: nobody → sunfish
Depends on: 891534
(Assignee)

Comment 2

5 years ago
Created attachment 8335523 [details] [diff] [review]
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.
Attachment #8335523 - Flags: review?(nicolas.b.pierron)
(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.
(Assignee)

Comment 4

5 years ago
(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.
(Assignee)

Comment 5

5 years ago
Created attachment 8336389 [details] [diff] [review]
range-udivormod.patch

This just refreshes the patch and fixes build errors on ARM.
Attachment #8335523 - Attachment is obsolete: true
Attachment #8335523 - Flags: review?(nicolas.b.pierron)
Attachment #8336389 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 6

5 years ago
Created attachment 8336391 [details] [diff] [review]
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.
Attachment #8336391 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 7

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

Actually, this patch is not ready yet.
Attachment #8336389 - Flags: review?(nicolas.b.pierron)
(Assignee)

Updated

5 years ago
Attachment #8336389 - Attachment is obsolete: true
(Assignee)

Updated

5 years ago
Attachment #8336391 - Attachment is obsolete: true
Attachment #8336391 - Flags: review?(nicolas.b.pierron)
(Assignee)

Comment 8

5 years ago
Created attachment 8336883 [details] [diff] [review]
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.
Attachment #8336883 - Flags: review?(nicolas.b.pierron)
Attachment #8336883 - Flags: review?(nicolas.b.pierron) → review+
https://hg.mozilla.org/mozilla-central/rev/0a188ddb392a
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
You need to log in before you can comment on or make changes to this bug.