894794 - IonMonkey: Incorrect result with %

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

(function() {
    for (var j = 0; j < 1; ++j) {
        var r = ((0x7fffffff - (0x80000000 | 0)) | 0) % 10000;
        assertEq(r, -1);
    }
})();

With --ion-eager: got 7295, expected -1

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/f1088655c731
user:        Jan de Mooij
date:        Tue Jul 09 10:23:58 2013 +0200
summary:     Bug 864400 - Optimize ModI for non-constant power-of-2 divisors. r=h4writer

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: first steps

What I've found so far:
- the constructor |Range(MDefinition*)| is calling truncate() if the operation is specialized for MIRType_Int32, while it shouldn't, as it results in different ranges. This results in the range of MSub being corrupted in |MBitOr::computeRange()|.
- |Range::or_| (as of today in inbound) doesn't compute correctly the range of 'a|0' operation if 'a' overflows the Int32 range. See attached patch.
- |RangeAnalysis::truncate| removes the bitwise 0 operation, while it actually has side effects, and I am not sure of the fix for that part. Nicolas, any idea?

Comment 2

[Nicolas B. Pierron [:nbp]]

Comment on attachment 777480 [details] [diff] [review]
first steps

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

::: js/src/ion/RangeAnalysis.cpp
@@ -386,5 @@
>      decimal_ = other->decimal_;
>      max_exponent_ = other->max_exponent_;
>  
> -    if (def->type() == MIRType_Int32)
> -        truncate();

we can restrict that to undefined ones.

@@ +468,5 @@
>      // the code below from calling js_bitscan_clz32 with a zero operand or from
>      // shifting an int32_t by 32.
>      if (lhs->lower_ == lhs->upper_) {
> +        if (lhs->lower_ == 0) {
> +            if (rhs->isInt32())

This one should always be an int32, see the patch attached on Bug 894786.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Fix truncated range of constants.

Currently we clamp the range after it is truncated, we should just reset it correctly to the clamped value of the constant.

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #3)
> Currently we clamp the range after it is truncated, we should just reset it
> correctly to the clamped value of the constant.

s/clamped/truncated/

… instead of the clamped value.

Comment 5

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2 - Collect Range info ahead instead of manipulating operand ranges.

As we remove the bit-ops at the end of the RangeAnalysis::truncate transformation, we cannot access any information of the range of any operands.  

The reason is simple:
  (x >>> 0) ==> [0 .. +inf[
  ((x >>> 0) | 0)  ==> [INT32_MIN .. INT32_MAX]
  ((x >>> 0) | 0) % -1 ==> lhs->range()->lower() > 0

If we remove the truncate operation, and access the lhs of MMod, we will obtain the range of Ursh instead of the range of the truncated value.

This patch move all uses of range() in the RangeAnalysis files and introduce a collectRangeInfo function for cases were we are interested in any operand range.

Note: It is still valid from a MIR to access its own range information as long as this is not feed into another CodeGen optimization.

Comment 6

[Jan de Mooij [:jandem]]

Comment on attachment 777517 [details] [diff] [review]
Part 1 - Fix truncated range of constants.

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

::: js/src/ion/RangeAnalysis.cpp
@@ +1563,3 @@
>      setResultType(MIRType_Int32);
>      if (range())
> +        range()->set(res, res, false, 32);

range()->set(res, res) will use MaxInt32Exponent (== 31) instead of 32. Can you explain when we need 31 or 32?

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 777520 [details] [diff] [review]
Part 2 - Collect Range info ahead instead of manipulating operand ranges.

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

Thanks for fixing this, r=me with comments addressed.

::: js/src/ion/RangeAnalysis.cpp
@@ +1866,5 @@
>      }
>  
> +    // Collect range information as soon as the truncate phased is finished to
> +    // ensure that we do not collect information from any operand out-side the
> +    // scope of the Range Anlaysis.

Typo: Analysis

Also, it would be good to add the "((x >>> 0) | 0) % -1 " explanation you gave in comment 5. Giving the range for each of these expressions makes it pretty clear what's going on.

@@ +1869,5 @@
> +    // ensure that we do not collect information from any operand out-side the
> +    // scope of the Range Anlaysis.
> +    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
> +        for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
> +            iter->collectRangeInfo();

Can we set MDefinition::range_ to NULL here, at least in debug builds? That should keep us from introducing similar bugs.

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #6)
> Comment on attachment 777517 [details] [diff] [review]
> Part 1 - Fix truncated range of constants.
> 
> Review of attachment 777517 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/ion/RangeAnalysis.cpp
> @@ +1563,3 @@
> >      setResultType(MIRType_Int32);
> >      if (range())
> > +        range()->set(res, res, false, 32);
> 
> range()->set(res, res) will use MaxInt32Exponent (== 31) instead of 32. Can
> you explain when we need 31 or 32?

When we set an Int, the exponent does not matter as it is computed again by rectifyExponent.  So here I could have put 75 and it would not have changed anything.

I should probably made a followup patch to remove all the exponent when none of the lower/upper values are out-side the range.

Comment 9

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #7)
> @@ +1869,5 @@
> > +    // ensure that we do not collect information from any operand out-side the
> > +    // scope of the Range Anlaysis.
> > +    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
> > +        for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
> > +            iter->collectRangeInfo();
> 
> Can we set MDefinition::range_ to NULL here, at least in debug builds? That
> should keep us from introducing similar bugs.

Sadly no, because the failure functions are still looking at the outcome of an instruction to determine if it is fallible.

I agree that we should prevent any way to do that in the future, but changing the failure to use a flag might be costly in size.

Comment 10

[Jan de Mooij [:jandem]]

Comment on attachment 777517 [details] [diff] [review]
Part 1 - Fix truncated range of constants.

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

::: js/src/ion/RangeAnalysis.cpp
@@ +1563,3 @@
>      setResultType(MIRType_Int32);
>      if (range())
> +        range()->set(res, res, false, 32);

If the 31 is ignored, we can remove the last two arguments and use range()->set(res, res).

Comment 11

[Nicolas B. Pierron [:nbp]]

Part 1 - http://hg.mozilla.org/integration/mozilla-inbound/rev/4e17c7ca2432
Part 2 - http://hg.mozilla.org/integration/mozilla-inbound/rev/6aa9971523fc

Comment 12

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

https://hg.mozilla.org/mozilla-central/rev/4e17c7ca2432
https://hg.mozilla.org/mozilla-central/rev/6aa9971523fc