Closed Bug 894794 Opened 6 years ago Closed 6 years ago

IonMonkey: Incorrect result with %

Categories

(Core :: JavaScript Engine, defect)

x86_64
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla25

People

(Reporter: jruderman, Assigned: nbp)

References

(Blocks 1 open bug)

Details

(Keywords: regression, testcase)

Attachments

(3 files)

(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
Attached patch first stepsSplinter Review
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?
Flags: needinfo?(nicolas.b.pierron)
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.
Assignee: general → nicolas.b.pierron
Status: NEW → ASSIGNED
Flags: needinfo?(nicolas.b.pierron)
Currently we clamp the range after it is truncated, we should just reset it correctly to the clamped value of the constant.
Attachment #777517 - Flags: review?(jdemooij)
(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.
Attachment #777517 - Attachment description: Fix truncated range of constants. → Part 1 - Fix truncated range of constants.
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.
Attachment #777520 - Flags: review?(jdemooij)
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 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.
Attachment #777520 - Flags: review?(jdemooij) → review+
Attachment #777520 - Attachment description: Collect Range info ahead instead of manipulating operand ranges. → Part 2 - Collect Range info ahead instead of manipulating operand ranges.
(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.
(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 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).
Attachment #777517 - Flags: review?(jdemooij) → review+
https://hg.mozilla.org/mozilla-central/rev/4e17c7ca2432
https://hg.mozilla.org/mozilla-central/rev/6aa9971523fc
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla25
You need to log in before you can comment on or make changes to this bug.