1015498 - Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(upper_)), at jit/RangeAnalysis.h or Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(lower_)), at jit/RangeAnalysis.h

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

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

Attachment: stacks

for (var j = 0; j < 999; j++) {
    (function() {
        Math.floor(1.5)
    })()
}

Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(upper_)), at jit/RangeAnalysis.h

for (var j = 0; j < 999; j++) {
    (function() {
        Math.floor(-1.5)
    })()
}

Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(lower_)), at jit/RangeAnalysis.h

These asserts happen on js debug shell on m-c changeset c695c2bd13ae with --ion-eager --ion-parallel-compile=off.

My configure flags are:

CC="clang -Qunused-arguments" CXX="clang++ -Qunused-arguments" AR=ar sh /Users/skywalker/trees/mozilla-central/js/src/configure --target=x86_64-apple-darwin12.5.0 --enable-optimize --enable-debug --enable-profiling --enable-gczeal --enable-debug-symbols --disable-tests --with-ccache --enable-threadsafe <other NSPR options>

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/80bbd2f2526b
user:        Julien Levesy
date:        Thu May 22 08:21:37 2014 -0700
summary:     Bug 1006597 - Implemented Range Analaysis to Math.floor. r=nbp

Nicolas, is bug 1006597 a likely regressor?

Comment 1

[Julien Levesy]

Managed to reproduce it on my setup. 
I looked with a debugger what happens here.
For your first case  (x = 1.5) 

What I found is this assert must fail in that case.
Here's a dump of the range object

(js::jit::Range) $1 = {
  lower_ = 1
  hasInt32LowerBound_ = true
  upper_ = 2
  hasInt32UpperBound_ = true
  canHaveFractionalPart_ = false
  max_exponent_ = 0
  symbolicLower_ = 0x0000000000000000
  symbolicUpper_ = 0x0000000000000000
}

So : max_exponent_ + canHaveFractionalPart_ => 0
and mozilla::FloorLog2(mozilla::Abs(upper_)) => mozilla::FloorLog2(2) => 31 - 30 => 1
0 >= 1 => Assertion fails.

Is it normal that max_exponent_ is set to 0 ?

To me, the point is this patch is surely a regressor, because it introduces the method Range::resetFractionalParts(). And the callstack shows that the assert fails in this method context.

Hope this can help.

Comment 2

[Nicolas B. Pierron [:nbp]]

(In reply to Julien Levesy from comment #1)
> Managed to reproduce it on my setup. 
> I looked with a debugger what happens here.
> For your first case  (x = 1.5) 
> 
> Is it normal that max_exponent_ is set to 0 ?

Yes, max_exponent_ refers to the power of 2 of the absolute value, almost as in the double representation.  the exact relation is   abs(x) < 2^(max_exponent_ + 1)

I was expecting the optimize function to fix this case for us, to shrink the upper bound based on the exponent, but I guess we are failing inside the assertInvariant of the optimize function :/

I guess we should use refineInt32BoundsByExponent instead.

(as long as this is not a fuzzblocker)
Julien, do you want to continue on this issue?

Comment 3

[Julien Levesy]

Yes we're failing in optimize call. Actually first line calls AssertInvariants.
Sure, I'll handle that as soon as possible.

BTW, I haven't seen it when I ran Ion test suite, did I miss something? Or maybe should a write a test that highlight this issue ?

Comment 4

[Julien Levesy]

Attachment: Replace optimize call by refineInt32BoundsByExponent in Range::resetFractionalPart

Here's the fix.
It avoids the issue in both cases.
jit tests are green, too.

Comment 5

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8428849 [details] [diff] [review]
Replace optimize call by refineInt32BoundsByExponent in Range::resetFractionalPart

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

Add the two test cases, and run the test suite with --ion-check-range-analysis, to make sure that we have no more errors.

::: js/src/jit/RangeAnalysis.h
@@ +590,5 @@
>      }
>  
>      void resetFractionalPart() {
>          canHaveFractionalPart_ = false;
> +        refineInt32BoundsByExponent(max_exponent_, &lower_, &hasInt32LowerBound_, &upper_, &hasInt32UpperBound_);

Don't we need to lower the lower bound by -1 at some point, because of the semantic of Math.floor?

Comment 6

[Julien Levesy]

Attachment: Replace optimize call by refineInt32BoundsByExponent in Range::resetFractionalPart

Here it is.
I am forced to make setLowerInit / setUpperInit public calls. I don't think this is good.
But actually I don't have any simple way to manipulate Lower bound of a range from outside,
exept Range::setInt32, setDouble and set method,  which all manipulates upper and lower bound.
RefineLower will also be useless here.

Ran test with --ion-check-range-analysis flag.
Here's failed tests list:
-FAIL - asm.js/testBullet.js
-FAIL - gc/bug888463.js
-FAIL - ion/testFloat32-correctness.js
-FAIL - sunspider/check-crypto-aes.js
-FAIL - sunspider/check-string-tagcloud.js

Comment 7

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8429047 [details] [diff] [review]
Replace optimize call by refineInt32BoundsByExponent in Range::resetFractionalPart

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

I cannot give a r+ with failing tests. We need to fix these test before.

The other option would be to have a Range::floor functions, as we already do for some Math functions [1].

[1] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/RangeAnalysis.h#402-417

Comment 8

[Julien Levesy]

Attachment: Attachment to Bug 1015498 - Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(upper_)), at jit/RangeAnalysis.h or Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(lower

Implement MFloor::computeRange using new Range::floor to avoid assertion failures.

Here's a new patch.
All tests are green.
But actually, don't we put the new instance in an invalid state, if F.I max_exponent_ is set to 0 ?

Comment 9

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8429601 [details] [diff] [review]
Attachment to Bug 1015498 - Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(upper_)), at jit/RangeAnalysis.h or Assertion failure: max_exponent_ + canHaveFractionalPart_ >= mozilla::FloorLog2(mozilla::Abs(lower

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

::: js/src/jit/RangeAnalysis.cpp
@@ +555,5 @@
>  Range::setDouble(double l, double h)
>  {
>      // Infer lower_, upper_, hasInt32LowerBound_, and hasInt32UpperBound_.
>      if (l >= INT32_MIN && l <= INT32_MAX) {
> +        lower_ = int32_t(std::floor(l));

Leave this outside of this patch for now, and I guess we can make a follow-up patch for using Decimal::floor instead of std.

@@ +958,5 @@
> +Range::floor(TempAllocator &alloc, const Range *op)
> +{
> +
> +    Range *copy  = new(alloc) Range(*op);
> +    copy->setLowerInit(copy->lower_ - 1);

We only want to substract 1, if "op" has a fractional part.
Also, we might have to increase the exponent too, such as -1.5 is floored to -2, which should raise the max_exponent_ from 0 to 1, if the max_exponent_ is not yet higher than that.

Comment 10

[Julien Levesy]

Attachment: Bug1015498part2.patch

Here's the floor patch fix

Comment 11

[Julien Levesy]

Attachment: Replaced floor call by Decimal::floor to avoid naming clash with Range::floor method

Comment 12

[Julien Levesy]

Attachment: Bug1015498part1.patch

Here's a new patch. It does not compile, because of the floor methods naming clash.
 I assumed there is no point in decrementing lower bound if it's not Int32 defined (aka infinite or overflowed).
 Also, to re evaluate max_exponent, I check before if the upper bound is defined and I use exponentImpliedByInt32Bounds(),
 to handle all cases where we have to increment max exponent (F.I x = -127.5). If upper bound is not defined, we don't have to re evaluate max_exponent_ as we know it will be greater than lower bound implied exponent in that case.
 I'm quite sure, I'm wrong ... ^^. But I wanted your opinion.

I ran jit-test suite, everything is fine

Comment 13

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8430776 [details] [diff] [review]
Bug1015498part2.patch

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

I think Waldo is the right person to ask, for these kind of patches.

Comment 14

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8430780 [details] [diff] [review]
Bug1015498part1.patch

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

This looks correct this time :)

Can you add more test cases especially checking all ranges.
Use if with less-than operators to shrink the ranges to what you want to test.

function myFloor(x) {
  return x - Math.abs(x % 1);
}

  if (10 < x && x < 100)
    assertEq(Math.floor(x), myFloor(x));

  if (-100 < x && x < -10)
    assertEq(Math.floor(x), myFloor(x));

  if (-(4294967296 - 1) < x && x < 10)
    assertEq(Math.floor(x), myFloor(x));

Note that the result of assertEq is not that interesting, even if it might catch errors in myFloor or in the codegen implementations, what is interesting is that we are giving ranges, and checking how we compile it with the --ion-check-range-analysis option.

::: js/src/jit-test/tests/ion/bug1015498.js
@@ +1,1 @@
> +for (var j = 0; j < 999; j++) {

nit: instead of running until 999, lower the the ion.usecount.trigger (grep in the test suite)

::: js/src/jit/RangeAnalysis.cpp
@@ +959,5 @@
> +{
> +    Range *copy = new(alloc) Range(*op);
> +    // Decrement lower bound of copy range
> +    // if op have a factional part and lower
> +    // bound is Int32 defined

style-nit: we wrap comment on 80 columns.

Comment 15

[Julien Levesy]

Here's my test.

> setJitCompilerOption("baseline.usecount.trigger", 10);
> setJitCompilerOption("ion.usecount.trigger", 20);
>
> function floorRangeTest(x) {
>     (function() {
>         if(10 < x && x < 100)
>             Math.floor(x);
> 
>         if(-100 < x && x < -10)
>             Math.floor(x);
>     })()
> }
> 
> for (var j = 0; j < 20; j++) {
>     floorRangeTest(50.4);
> }

When I break in Range::floor here's the op Range dump :

> (lldb) p *op
> (const js::jit::Range) $0 = {
>   lower_ = -2147483648
>   hasInt32LowerBound_ = false
>   upper_ = 2147483647
>   hasInt32UpperBound_ = false
>   canHaveFractionalPart_ = true
>   max_exponent_ = 65535
>   symbolicLower_ = 0x0000000000000000
>   symbolicUpper_ = 0x0000000000000000
> } 

op's Range is undefined :-(.
It's a bit weird, because we're expecting range equal to ]10, 100[ in that case, isn't it ? 
What did I miss ? Thanks.

Comment 16

[Nicolas B. Pierron [:nbp]]

(In reply to Julien Levesy from comment #15)
> Here's my test.
> 
> > setJitCompilerOption("baseline.usecount.trigger", 10);
> > setJitCompilerOption("ion.usecount.trigger", 20);
> > 
> > function floorRangeTest(x) {
> >     (function() {

Can you remove the inner function?

> >         if(10 < x && x < 100)
> >             Math.floor(x);
> > 
> >         if(-100 < x && x < -10)
> >             Math.floor(x);
> >     })()
> > }
> > 
> > for (var j = 0; j < 20; j++) {
> >     floorRangeTest(50.4);
> > }
> 
> When I break in Range::floor here's the op Range dump :
> 
> > (lldb) p *op
> > (const js::jit::Range) $0 = {
> >   lower_ = -2147483648
> >   hasInt32LowerBound_ = false
> >   upper_ = 2147483647
> >   hasInt32UpperBound_ = false
> >   canHaveFractionalPart_ = true
> >   max_exponent_ = 65535
> >   symbolicLower_ = 0x0000000000000000
> >   symbolicUpper_ = 0x0000000000000000
> > } 
> 
> op's Range is undefined :-(.
> It's a bit weird, because we're expecting range equal to ]10, 100[ in that
> case, isn't it ? 
> What did I miss ? Thanks.

Use iongraph, you will have a clear view of the Range Analysis across the program.

Comment 17

[Julien Levesy]

Ok here's an update.

if(10 < x) {
   if(x < 100) {
      assertEq(Math.floor(x), myFloor(x)); 
   }
}

Actually, when executing this code, my dump object is correct, for op : 

(const js::jit::Range) $0 = {
  lower_ = 10
  hasInt32LowerBound_ = true
  upper_ = 100
  hasInt32UpperBound_ = true
  canHaveFractionalPart_ = true
  max_exponent_ = 6
  symbolicLower_ = 0x0000000000000000
  symbolicUpper_ = 0x0000000000000000
}

Ion graph told us that when we express a test with multiple conditions (ie : A && B) Ion does a phi between A && !A and does not evaluate A && B, so range information is lost. ( Thanks bbouvier for helping me understanding that ;-) )
I'll propose test cases asap.

Comment 18

[Julien Levesy]

Attachment: Bug1015498part1v2.patch

Comment 19

[Julien Levesy]

Seems I miss something with git-bz, my comment was lost.
So...
Here's a new patch. It adds range based tests cases. I spotted an overflow issue when lower==JSVAL_INT_MIN
and fixed it.
BTW, my last message was unprecise, actually it does evaluate A && B, but evaluated A is a phi between A && !A, and it looses Range information.
bbouvier told me this is a know issue, (bug 913935)

Comment 20

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8432352 [details] [diff] [review]
Bug1015498part1v2.patch

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

This is converging ;)
Range Analysis is a big pieces of corner cases, still one more to handle.

::: js/src/jit-test/tests/ion/bug1015498.js
@@ +59,5 @@
> +}
> +
> +for (var j = 0; j < 30; j++) {
> +    floorRangeTest(50.4);
> +    floorRangeTest(-50.4);

Generate the input instead of using a constant to prevent constant propagation in inlined versions of floorRangeTest.
You might also want to iterate on a list of chosen values, such as the range analysis assertion fails if we do have a value which is not in the expected range of MFloor.

::: js/src/jit/RangeAnalysis.cpp
@@ +963,5 @@
> +    if (op->canHaveFractionalPart() &&
> +        op->hasInt32LowerBound())
> +    {
> +        if(copy->lower_ == JSVAL_INT_MIN)
> +        {

style-nit: move the brace on the same line as the if, when the condition fit on one line.

@@ +965,5 @@
> +    {
> +        if(copy->lower_ == JSVAL_INT_MIN)
> +        {
> +            copy->hasInt32LowerBound_ = false;
> +            copy->max_exponent_ = MaxInt32Exponent;

The max_exponent_ might be higher than 32, if the upper bound is not in the int32 range.

@@ +969,5 @@
> +            copy->max_exponent_ = MaxInt32Exponent;
> +        }
> +        else
> +        {
> +            copy->setLowerInit(copy->lower_ - 1);

Note that you can also use setLowerInit, under the condition that you convert the lower bound to an int64_t before subtracting 1.

Comment 21

[Julien Levesy]

Attachment: Bug1015498part1v3.patch

Comment 22

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8436960 [details] [diff] [review]
Bug1015498part1v3.patch

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

This sounds good to me :)

::: js/src/jit/RangeAnalysis.cpp
@@ +962,5 @@
> +    // bound is Int32 defined. Also we avoid to decrement when op have a
> +    // fractional part but lower_ >= JSVAL_INT_MAX.
> +    if (op->canHaveFractionalPart() &&
> +        op->hasInt32LowerBound())
> +        copy->setLowerInit(int64_t(copy->lower_) - 1);

style-nit: No need to put the condition on 2 lines.

@@ +972,5 @@
> +    // we increment it.
> +    if(copy->hasInt32Bounds())
> +        copy->max_exponent_ = copy->exponentImpliedByInt32Bounds();
> +    else if(copy->max_exponent_ < MaxFiniteExponent)
> +        ++(copy->max_exponent_);

nit: no need for the parentheses, post increment is fine too ;)

@@ +975,5 @@
> +    else if(copy->max_exponent_ < MaxFiniteExponent)
> +        ++(copy->max_exponent_);
> +
> +    copy->canHaveFractionalPart_ = false;
> +    refineInt32BoundsByExponent(copy->max_exponent_,

As we have exponentImpliedByInt32Bounds, I do not think this function call is needed anymore.

Comment 23

[Julien Levesy]

Attachment: Bug1015498part1v4.patch

Comment 24

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8437865 [details] [diff] [review]
Bug1015498part1v4.patch

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

Awesome :)

Comment 25

[Nicolas B. Pierron [:nbp]]

(part 1) https://tbpl.mozilla.org/?tree=Try&rev=aed895e39105

Comment 26

[Nicolas B. Pierron [:nbp]]

I made the following modification to make the patch run as it is today:
https://hg.mozilla.org/try/rev/dca712023017#l2.13

Try seems to build correctly on all platforms about this change: (re-running B2G Desktop OSX)
https://tbpl.mozilla.org/?tree=Try&rev=88ac0e8838b3

And it seems to work fine too.
https://tbpl.mozilla.org/?tree=Try&rev=405aa00577a8

Comment 27

[Jeff Walden [:Waldo]]

Comment on attachment 8430776 [details] [diff] [review]
Bug1015498part2.patch

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

Sorry for delay here, I've been significantly distracted by a pressing security issue for awhile recently.  :-(

::: js/src/jit/RangeAnalysis.cpp
@@ +557,5 @@
>  Range::setDouble(double l, double h)
>  {
>      // Infer lower_, upper_, hasInt32LowerBound_, and hasInt32UpperBound_.
>      if (l >= INT32_MIN && l <= INT32_MAX) {
> +        lower_ = int32_t(Decimal::fromDouble(l).floor().toDouble());

Why wouldn't we use ::floor here?  This converts the double to a string, then parses the string as a decimal, then does a bunch more stuff.  Computing the floor of a double, in contrast, should be a much simpler matter of extracting the exponent and doing some masking (plus a little futzing for negatives and denormals), or maybe even just handing off to a floating point instruction.

Comment 28

[Nicolas B. Pierron [:nbp]]

nbp_> Waldo: is std::floor better than ::floor ?
Waldo> nbp_: they're likely identical, but std::floor is only exposed I think if <cmath> is included, which it's probably only bootlegged
Waldo> nbp_: and we tend to normally use just the C functions, at least right now
Waldo> so consistency is ::floor

Ok, so I will land the modified patch sent to the try server.

Comment 29

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/25526818c33a

Comment 30

[Julien Levesy]

Great !
What a pleasure to see this patch finally landed :D 
I was pretty sure Decimal::fromDouble was not optimal, but I didn't think about scope resolution operator to disambiguate. Sorry about that !

Comment 31

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/25526818c33a