Closed Bug 1258632 Opened 8 years ago Closed 8 years ago

GVN doesn't take MDiv/MMod::unsigned_ into account

Categories

(Core :: JavaScript Engine: JIT, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla48
Tracking Status
firefox45 - ---
firefox46 + fixed
firefox47 + fixed
firefox48 + fixed
firefox-esr45 --- fixed

People

(Reporter: pipcet, Assigned: pipcet)

Details

Attachments

(2 files, 1 obsolete file)

Attached file idiv.js
The attached script produces different results in the JS shell when run with and without the "--no-asmjs" option. The correct result is 0x40001, and that's what's produced with the --no-asmjs option, as well as by an older version of the shell, and also by node.js. The asmjs version yields 0xff40001.

At its core, the script reads (r1 is the return value):

	    r6 = (r2>>>0)%(r7>>>0)|0;
	    if ((r2|0)!=(r6|0)) return 0;
	    r1 = (r2|0)%(r7|0)|0;
	    r7 = (imul(r7|0,i3|0))|0;

(All of these lines, as well as a surrounding loop, appear to be necessary to trigger the bug). I think what is happening is that the unsigned modulo performed in the first line and the signed modulo in the third line get combined improperly; the assembler output reads

   0x00007ffff7fe3020:	48 83 ec 08	sub    $0x8,%rsp
   0x00007ffff7fe3024:	48 8b c7	mov    %rdi,%rax
   0x00007ffff7fe3027:	85 f6	test   %esi,%esi
   0x00007ffff7fe3029:	0f 84 2c 00 00 00	je     0x7ffff7fe305b
   0x00007ffff7fe302f:	33 d2	xor    %edx,%edx
=> 0x00007ffff7fe3031:	f7 f6	div    %esi
   0x00007ffff7fe3033:	8b ca	mov    %edx,%ecx
   0x00007ffff7fe3035:	3b f9	cmp    %ecx,%edi
   0x00007ffff7fe3037:	0f 84 07 00 00 00	je     0x7ffff7fe3044
   0x00007ffff7fe303d:	33 c0	xor    %eax,%eax
   0x00007ffff7fe303f:	e9 02 00 00 00	jmpq   0x7ffff7fe3046
   0x00007ffff7fe3044:	8b c1	mov    %ecx,%eax
   0x00007ffff7fe3046:	66 90	xchg   %ax,%ax
   0x00007ffff7fe3048:	48 83 c4 08	add    $0x8,%rsp
   0x00007ffff7fe304c:	c3	retq   

The division marked by the arrow is an unsigned division, which is correct for the calculation of r6 but incorrect for that of r1; however, no second division is performed, and the incorrect value is returned in %eax.

The culprit appears to be in the GVN code, as "--ion-gvn=off" makes the script return the right result.
Proposed patch. Appears to work in first tests.
Thank you for the bug report, it is indeed a differential testing bug between asm.js and non asm.js, and a very nice catch by the way!

I found a more minimal test case:

function AsmModule(stdlib, foreign, heap) {
    "use asm";
    var g = 0;
    function f (r2, r7) {
        r2 = r2|0;
        r7 = r7|0;
        var r6 = 0;
        r6 = (r2>>>0)%(r7>>>0)|0;
        g = r6; // make sure r6 isn't destroyed by GVN
        return (r2|0)%(r7|0)|0;
    }
    return { f: f, };
}

Thank you for the patch as well, it looks good, I'll make comments there directly.
Assignee: nobody → pipcet
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Summary: asm.js misoptimization: signed vs unsigned modulo operator → GVN doesn't take MDiv/MMod::unsigned_ into account
Comment on attachment 8733280 [details] [diff] [review]
0001-Bug-1258632-avoid-mis-compiled-asm.js-code.patch

Review of attachment 8733280 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good!

Can you please:
- include the test in jit-tests/tests/asm.js/testExpression.js, with the compact form:

assertEq(asmLink(asmCompile(USE_ASM + "var g=0; function f(x, y) { x = x|0; y = y|0; var r6 = 0; r6 = (x>>>0)%(y>>>0)|0; g = r6; return (x|0)%(y|0)|0; } return f;"))(0xff40001, 0xfff80000), 0x40001);

- change the patch format so that it follows our conventions as described there: https://developer.mozilla.org/en-US/docs/Mercurial/Using_Mercurial#Commit_Message_Conventions
- add r=bbouvier at the end of your patch
- submit it again, with the review flag set to "?" and in the text field ":bbouvier"

Thanks!

::: js/src/jit/MIR.h
@@ +6896,5 @@
>      }
>  
> +    bool congruentTo(const MDefinition* ins) const override {
> +        return binaryCongruentTo(ins) &&
> +            unsigned_ == ins->toDiv()->isUnsigned();

Instead of calling binaryCongruentTo, can you call the parent's class congruentTo here? Even if it has the same effect, that would allow us changing the parent's method without having to worry about changing the child's method too.

Style nit: can you align the "u" of "unsigned_" with the first letter after the space following the return, please?

return something() &&
       unsigned_ == ...

@@ +6979,5 @@
>      TruncateKind operandTruncateKind(size_t index) const override;
>  
> +    bool congruentTo(const MDefinition* ins) const override {
> +        return binaryCongruentTo(ins) &&
> +            unsigned_ == ins->toMod()->isUnsigned();

ditto
Attachment #8733280 - Flags: feedback+
(In reply to Benjamin Bouvier [:bbouvier] from comment #2)
> Thank you for the bug report, it is indeed a differential testing bug
> between asm.js and non asm.js, and a very nice catch by the way!

Thanks for responding so quickly!

> I found a more minimal test case:

I've shortened this a bit further for the test case, and hopefully fixed the other problems you noted.
Attached patch mdiv-mmod.patchSplinter Review
Attachment #8733280 - Attachment is obsolete: true
Attachment #8733439 - Flags: review?(bbouvier)
Comment on attachment 8733439 [details] [diff] [review]
mdiv-mmod.patch

Review of attachment 8733439 [details] [diff] [review]:
-----------------------------------------------------------------

Nice, thank you! I will post this patch to try on your behalf, so that we can check the tests pass in all variants on our infra. Then we can add a note to this bug "checkin-needed" and then it is going to be in the next nightly.
Attachment #8733439 - Flags: review?(bbouvier) → review+
Duh, i've based this try build on a broken WIP patch (so failures are unrelated). New try build based on inbound without any other patch:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=380f221e8e6c
There was a test failure due to bug https://bugzilla.mozilla.org/show_bug.cgi?id=1256004, so I retriggered that test job and it succeeded now. I think we're good to go, right?
Yes, it does look green enough for me. (comment 8 for try build)
Keywords: checkin-needed
[Tracking Requested - why for this release]: correctness issue in asm.js (and soon webassembly), which has been present for a long time (at least it's in the current release).
https://hg.mozilla.org/mozilla-central/rev/a3bb04ba5a1d
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
Comment on attachment 8733439 [details] [diff] [review]
mdiv-mmod.patch

Approval Request Comment
[Feature/regressing bug #]: can't tell for sure, it's been there since asm.js, it seems.
[User impact if declined]: correctness issues on asm.js / webassembly programs
[Describe test coverage new/current, TreeHerder]: all green on try, has stick on inbound for a few days
[Risks and why]: very very low, if not none
[String/UUID change made/needed]: n/a
Attachment #8733439 - Flags: approval-mozilla-beta?
Attachment #8733439 - Flags: approval-mozilla-aurora?
Comment on attachment 8733439 [details] [diff] [review]
mdiv-mmod.patch

Seems low risk, has tests and will improve asm.js, taking it.
Should be in 46 beta 7
Attachment #8733439 - Flags: approval-mozilla-beta?
Attachment #8733439 - Flags: approval-mozilla-beta+
Attachment #8733439 - Flags: approval-mozilla-aurora?
Attachment #8733439 - Flags: approval-mozilla-aurora+
Comment on attachment 8733439 [details] [diff] [review]
mdiv-mmod.patch

See previous approval comment. It's a really small patch so I think it would be worth it.
Attachment #8733439 - Flags: approval-mozilla-esr45?
Tracking belatedly, so we will notice if this reopens.
Comment on attachment 8733439 [details] [diff] [review]
mdiv-mmod.patch

Improve the quality of esr, taking it.
Should be in 45.1.0
Attachment #8733439 - Flags: approval-mozilla-esr45? → approval-mozilla-esr45+
You need to log in before you can comment on or make changes to this bug.