941877 - OdinMonkey: Crash [@ js::jit::CodeGeneratorX86Shared::bailout] or Assertion failure: isDiv(), at jit/MIR.h

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: lldb stack

(function(stdlib, n, heap) {
    "use asm"
    var Float64ArrayView = new stdlib.Float64Array(heap)
    function f() {
        Float64ArrayView[0] = +(0xffffffff / 0xffffffff >> 0)
    }
})()

asserts js debug shell on m-c changeset c7cbfa315d46 without any CLI arguments at Assertion failure: isDiv(), at jit/MIR.h

My configure flags are:

CC="clang -Qunused-arguments" AR=ar CXX="clang++ -Qunused-arguments" sh ./configure --target=x86_64-apple-darwin12.5.0 --enable-optimize --enable-debug --enable-profiling --enable-gczeal --enable-debug-symbols --enable-methodjit --enable-type-inference --disable-tests --with-ccache --disable-threadsafe

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/2a5427c3a4ba
user:        Dan Gohman
date:        Wed Nov 20 21:53:51 2013 -0800
summary:     Bug 939893 - IonMonkey: Handle x/x in lowerUDiv. r=bhackett

Dan, is bug 939893 a likely regressor?

Comment 1

[Dan Gohman [:sunfish]]

Yes, bug 939893 is the regressor.

My patch for bug 940864 has the side effect of eliminating the code path which leads to the bug. If that gets accepted, I'll check that in, otherwise I'll find an alternate fix here.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: range-udivormod.patch

This patch is a subset of what I had originally posted to bug 940864. It doesn't make any range or inference changes. It just unifies MMod with AsmJSUMod and MDiv with AsmJSUDiv, which is sufficient to fix this bug.

It will also enable some new optimizations, but I'll file that as a separate bug.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: constify.patch

This is just a simple patch which adds const to various methods in MIR.h. One of these consts is needed by the other patch here.

Comment 4

[Nicolas B. Pierron [:nbp]]

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

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

::: js/src/jit/MIR.h
@@ +4071,3 @@
>      {
>          MDiv *div = new(alloc) MDiv(left, right, type);
> +        div->unsigned_ = unsignd;

In which patch is unsigned_ declared?

::: js/src/jit/RangeAnalysis.cpp
@@ +1233,5 @@
> +    // but then we can ignore fractional parts and signedness issues.
> +    if (unsigned_) {
> +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;
> +        setRange(Range::NewUInt32Range(0, Max(lhsBound, rhsBound)));

If rhs is zero, we need to represent NaN.
Otherwise I guess we should rename the flag unsignedAndTruncated ?

@@ +1289,4 @@
>          setRange(new Range(0, lhs.upper(), true, lhs.exponent()));
> +    } else if (unsigned_) {
> +        // Unsigned division will return a uint32 value.
> +        setRange(Range::NewUInt32Range(0, UINT32_MAX));

Same here, we need to accound for rhs.lower() *> 0*, which is not provided by the unsigned_ flag.

Comment 5

[Nicolas B. Pierron [:nbp]]

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

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

Naming this flag unsignedAndTruncated makes more sense in terms of specialization, and also it implies that we would fail/bail if the result is not truncated.
Naming it only unsigned leave the hypothesis that the value might reach NaN or +Infinity, which does not seems to be the case here.

Comment 6

[Dan Gohman [:sunfish]]

Attachment: range-udivormod.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #4)
> Comment on attachment 8336881 [details] [diff] [review]
> range-udivormod.patch
> 
> Review of attachment 8336881 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MIR.h
> @@ +4071,3 @@
> >      {
> >          MDiv *div = new(alloc) MDiv(left, right, type);
> > +        div->unsigned_ = unsignd;
> 
> In which patch is unsigned_ declared?

It's already there, introduced in bug 891534.

> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1233,5 @@
> > +    // but then we can ignore fractional parts and signedness issues.
> > +    if (unsigned_) {
> > +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> > +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;
> > +        setRange(Range::NewUInt32Range(0, Max(lhsBound, rhsBound)));
> 
> If rhs is zero, we need to represent NaN.
> Otherwise I guess we should rename the flag unsignedAndTruncated ?

The case of rhs being zero is already handled, immediately above where this code is added.

> @@ +1289,4 @@
> >          setRange(new Range(0, lhs.upper(), true, lhs.exponent()));
> > +    } else if (unsigned_) {
> > +        // Unsigned division will return a uint32 value.
> > +        setRange(Range::NewUInt32Range(0, UINT32_MAX));
> 
> Same here, we need to accound for rhs.lower() *> 0*, which is not provided
> by the unsigned_ flag.

Good catch. My new patch adds a check for this case.

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> Comment on attachment 8336881 [details] [diff] [review]
> range-udivormod.patch
> 
> Review of attachment 8336881 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Naming this flag unsignedAndTruncated makes more sense in terms of
> specialization, and also it implies that we would fail/bail if the result is
> not truncated.
> Naming it only unsigned leave the hypothesis that the value might reach NaN
> or +Infinity, which does not seems to be the case here.

The existing canBeDivideByZero_ flag describes when the zero check can be omitted, and the isTruncated() from base class MBinaryArithInstruction describes when the operator is truncated. I think it makes sense to leave the unsigned_ flag as it is and keep these concepts separate.

Comment 7

[Dan Gohman [:sunfish]]

Constify patch checked in here:
https://hg.mozilla.org/integration/mozilla-inbound/rev/792f3433ded5

Comment 8

[Nicolas B. Pierron [:nbp]]

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

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

The rest sounds good, address the Modulo case question/issues and ask again for review :)

::: js/src/jit/RangeAnalysis.cpp
@@ +1232,5 @@
> +    // For unsigned ranges, we have to convert both operands to unsigned,
> +    // but then we can ignore fractional parts and signedness issues.
> +    if (unsigned_) {
> +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;

If we cannot assert that both inputs are non-negative, then we should consider the modification of the sign bit, or just consider that we cover the full Uint32 range.

[-255, 255]'s max is uint32_t(-1), which is higher than uint32_t(-255) and uint32_t(255).

@@ +1233,5 @@
> +    // but then we can ignore fractional parts and signedness issues.
> +    if (unsigned_) {
> +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;
> +        setRange(Range::NewUInt32Range(0, Max(lhsBound, rhsBound)));

This should be a Min and not a Max for a Modulo.

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +2129,5 @@
> +
> +    if (!ins->mir()->isTruncated()) {
> +        masm.ma_cmp(dest, Imm32(0));
> +        if (!bailoutIf(Assembler::LessThan, ins->snapshot()))
> +            return false;

I presume this is needed because we are not considering the result of an unsigned Div as being an unsigned, right?
Thus we bail because we cannot safely represent a value above INT32_MAX, right?

Follow-up: Can we use the Range to determine if we need to bail after all?

@@ +2142,5 @@
>  {
>      Register lhs = ToRegister(ins->lhs());
>      Register rhs = ToRegister(ins->rhs());
>      Register output = ToRegister(ins->output());
>      Label notzero;

This label is no longer used.

Comment 9

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: opt stack

(function(stdlib, n, heap) {
    "use asm"
    var Int16ArrayView = new stdlib.Int16Array(heap);
    function f(i0, d1) {
        i0 = i0 | 0
        d1 = +d1
        var d2 = 1.
        var i3 = 0
        Int16ArrayView[0] = i0
        d2 = (.0 / .0)
        switch ((i0 + i0) | 0) {
            case 0:
                d2 = .0
                break
        };
        (((i3 - (0 < 0)) >>> ((.0 < -0) + (.0 > .0))) / 0) >> (0 + (((0 + 0) ^ (9 > 0)) | 0))
    }
})()

Here's another testcase that crashes js opt shell at rev 53d55d2d0a25 at js::jit::CodeGeneratorX86Shared::bailout (looks near-NULL) and asserts similarly.

Please add this testcase to the next patch, if possible.

Comment 10

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/792f3433ded5

Comment 11

[Dan Gohman [:sunfish]]

Attachment: range-udivormod.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #8)
> Comment on attachment 8337768 [details] [diff] [review]
> range-udivormod.patch
> 
> Review of attachment 8337768 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> The rest sounds good, address the Modulo case question/issues and ask again
> for review :)
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1232,5 @@
> > +    // For unsigned ranges, we have to convert both operands to unsigned,
> > +    // but then we can ignore fractional parts and signedness issues.
> > +    if (unsigned_) {
> > +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> > +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;
> 
> If we cannot assert that both inputs are non-negative, then we should
> consider the modification of the sign bit, or just consider that we cover
> the full Uint32 range.
> 
> [-255, 255]'s max is uint32_t(-1), which is higher than uint32_t(-255) and
> uint32_t(255).

Fixed.

> @@ +1233,5 @@
> > +    // but then we can ignore fractional parts and signedness issues.
> > +    if (unsigned_) {
> > +        uint32_t lhsBound = Max<uint32_t>(lhs.lower(), lhs.upper());
> > +        uint32_t rhsBound = Max<uint32_t>(rhs.lower(), rhs.upper()) - 1;
> > +        setRange(Range::NewUInt32Range(0, Max(lhsBound, rhsBound)));
> 
> This should be a Min and not a Max for a Modulo.

Fixed.

> ::: js/src/jit/arm/CodeGenerator-arm.cpp
> @@ +2129,5 @@
> > +
> > +    if (!ins->mir()->isTruncated()) {
> > +        masm.ma_cmp(dest, Imm32(0));
> > +        if (!bailoutIf(Assembler::LessThan, ins->snapshot()))
> > +            return false;
> 
> I presume this is needed because we are not considering the result of an
> unsigned Div as being an unsigned, right?
> Thus we bail because we cannot safely represent a value above INT32_MAX,
> right?

Right. MIR does't have a proper UInt32 type, so nodes which want to return an unsigned value use Int32 and have bailouts for the case where the result is not an Int32 (unless truncated, or marked as bailouts-disabled).

> Follow-up: Can we use the Range to determine if we need to bail after all?

Yes, that should work. I filed bug 943410 for this.

> @@ +2142,5 @@
> >  {
> >      Register lhs = ToRegister(ins->lhs());
> >      Register rhs = ToRegister(ins->rhs());
> >      Register output = ToRegister(ins->output());
> >      Label notzero;
> 
> This label is no longer used.

Fixed.

I also added Gary's testcases, as well as a few hand-written tests.

Comment 12

[Nicolas B. Pierron [:nbp]]

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

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

r=me with the suggested modification.

::: js/src/jit/RangeAnalysis.cpp
@@ +1241,5 @@
> +        // the maximum unsigned value when interpreted as unsigned.
> +        if (lhs.lower() <= -1 && lhs.upper() >= -1)
> +            lhsBound = UINT32_MAX;
> +        if (rhs.lower() <= -1 && rhs.upper() >= -1)
> +            rhsBound = UINT32_MAX;

The same problem appears with -2 and all other negative numbers, use lhs.canBeFiniteNegative() instead.
Using canBeFiniteNegative is a conservative approximation which might lead to a larger range than expected.

Comment 13

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #12)
> Comment on attachment 8338539 [details] [diff] [review]
> range-udivormod.patch
> 
> Review of attachment 8338539 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> r=me with the suggested modification.
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1241,5 @@
> > +        // the maximum unsigned value when interpreted as unsigned.
> > +        if (lhs.lower() <= -1 && lhs.upper() >= -1)
> > +            lhsBound = UINT32_MAX;
> > +        if (rhs.lower() <= -1 && rhs.upper() >= -1)
> > +            rhsBound = UINT32_MAX;
> 
> The same problem appears with -2 and all other negative numbers, use
> lhs.canBeFiniteNegative() instead.
> Using canBeFiniteNegative is a conservative approximation which might lead
> to a larger range than expected.

If the range doesn't include -1, then the range doesn't cross the zero boundary, and the Max<uint32_t>(lower(), upper()) we did just above this is already correct. I'll add a comment about that.

Comment 14

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #13)
> (In reply to Nicolas B. Pierron [:nbp] from comment #12)
> > > +        if (rhs.lower() <= -1 && rhs.upper() >= -1)
> > > +            rhsBound = UINT32_MAX;
> > 
> > The same problem appears with -2 and all other negative numbers, use
> > lhs.canBeFiniteNegative() instead.
> > Using canBeFiniteNegative is a conservative approximation which might lead
> > to a larger range than expected.
> 
> If the range doesn't include -1, then the range doesn't cross the zero
> boundary, and the Max<uint32_t>(lower(), upper()) we did just above this is
> already correct. I'll add a comment about that.

Indeed, r=me with the comment then.

Comment 15

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/1fb0d84b5210

Comment 16

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/1fb0d84b5210

Comment 17

[Ioana (away)]

https://hg.mozilla.org/mozilla-central/diff/1fb0d84b5210/js/src/jit-test/tests/asm.js/bug941877.js