894786 - FPE crash in OdinMonkey-generated code with (shiftExpr % -1)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

(function() {
  "use asm";
  function f(z)
  {
    z = z|0;
    return (((0xc0000000 >>> z) >> 0) % -1)|0;
  }
  return f;
})()(0);

This started crashing when bug 864400 landed, but might be a pre-existing range analysis bug.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Make sure all bitwise operations are truncating their inputs.

This patch fix the case when this test case is ran with --ion-eager --no-asmjs, and include the following changes:
 - Rename Range::truncate to Range::clamp
 - Restrict the Range::Range(const MDefinition *) to clamp only if the input is unknown (most of the MIRType_Int32 are signed ints)
 - Add Range::truncate to handle overflow case needed on all inputs which might come from MUrsh, as the unsigned nature of the result is not coming from anywhere.
 - Add assertions to ensure that bitwise functions are only called with int32 ranges.

Another patch will be needed to make this pass with asm.js, as the cast from unsigned to signed done by (>> 0) is not known by type the range analysis and thus caused the modulo to handle an unsigned left operand where it is called with a signed left operand.

Comment 2

[Luke Wagner [:luke]]

I'm not sure what you're asking me here...

Comment 3

[Nicolas B. Pierron [:nbp]]

(In reply to Luke Wagner [:luke] from comment #2)
> I'm not sure what you're asking me here...

Here is why.

(In reply to Nicolas B. Pierron [:nbp] from comment #1)
> Another patch will be needed to make this pass with asm.js, as the cast from
> unsigned to signed done by (>> 0) is not known by type the range analysis
> and thus caused the modulo to handle an unsigned left operand where it is
> called with a signed left operand.

I wonder, would it be possible to still produce them in the MIR when instructions are changing sign, otherwise we are leaving no clue for the Range analysis to deduce that the input might be signed.  Which lead to this error where we just did have any information.

Or just annotate MUrsh with a isTruncated flag to annotate that its result is not in the Range [0 .. whatever] but should be wrapped around if it is too high.  Do you know where I should be looking for?

Comment 4

[Luke Wagner [:luke]]

I still mostly cannot parse what you are saying.

I'm guessing the problem is that
  ((0xc0000000 >>> z) >> 0) % -1)
gets generated as
  MMod(MUrsh(0xc0000000, z), -1)
where the resultType of MURsh is MIRType_Int32 (note: no MRsh(,0)).  Range analysis thus assumes that the result of MUrsh must be positive and that the lhs of % cannot be INT32_MIN and thus it doesn't branch.  Is that right?

It seems like the fix is that, if resultType == MIRType_Int32, range analysis should NOT say that the range of MUrsh is [0, 0xc000000], rather it should implicitly wrap the result range to the destination type (MIRType_Int32) which means that the range becomes [INT32_MIN, INT32_MAX].

Comment 5

[Nicolas B. Pierron [:nbp]]

(In reply to Luke Wagner [:luke] from comment #4)
> I'm guessing the problem is that
>   ((0xc0000000 >>> z) >> 0) % -1)
> gets generated as
>   MMod(MUrsh(0xc0000000, z), -1)
> where the resultType of MURsh is MIRType_Int32 (note: no MRsh(,0)).  Range
> analysis thus assumes that the result of MUrsh must be positive and that the
> lhs of % cannot be INT32_MIN and thus it doesn't branch.  Is that right?

Exactly.

> It seems like the fix is that, if resultType == MIRType_Int32, range
> analysis should NOT say that the range of MUrsh is [0, 0xc000000], rather it
> should implicitly wrap the result range to the destination type
> (MIRType_Int32) which means that the range becomes [INT32_MIN, INT32_MAX].

Indeed, this would work as we did before, but then we lose the information that the return value will be a positive number, if it overflow the int32 range.

Also note that to be correct, we should encode not [INT32_MIN .. INT32_MAX] but [INT32_MIN .. RANGE_MAX[ otherwise we get a wrong exponent approximation:

a = x >>> 0; // [INT32_MIN .. INT32_MAX] (nb bits = 31)
b = -1 >>> 13; // b == 2^21 - 1 (nb bits = 21)
if (a > 0) {
  // beta node: [0 .. INT32_MAX] (nb bits = 31)
  return (a * b) | 0; // int truncation (nb bits = 31 + 21 - 1 < 52)
}

Comment 6

[Luke Wagner [:luke]]

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> Indeed, this would work as we did before, but then we lose the information
> that the return value will be a positive number, if it overflow the int32
> range.

But, if the resultType() == MIRType_Int32, then it isn't true that it will be a positive number.  If you want to represent large positive numbers, you'd need a MIRType_Uint32 (which would be generally useful, I'd think).

Comment 7

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> a = x >>> 0; // [INT32_MIN .. INT32_MAX] (nb bits = 31)
> b = -1 >>> 13; // b == 2^21 - 1 (nb bits = 21)
> if (a > 0) {
>   // beta node: [0 .. INT32_MAX] (nb bits = 31)
>   return (a * b) | 0; // int truncation (nb bits = 31 + 21 - 1 < 52)
> }

I was trying to make a test case for it, but I realized that we do not correctly compute the range on beta node … I will investigate more.

Comment 8

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2: Work around the lack of unsigned representation.

Following the discussion with luke, as we lack UInt32 mir type, when an UInt32 becomes bigger than INT32_MAX, we change the range to account for the overflow in case of truncated values.

To keep the range as a correct approximation, we need to keep the upper infinity flag such as a value bigger than INT32_MAX does not fall out-side the scope of the range.

Apply this truncation of unsigned int to the result of MUrsh and also to loads from an UInt32 typed array.

Comment 9

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2: Work around the lack of unsigned representation.

Same thing, with the missing function definition.

Comment 10

[Jeff Walden [:Waldo]]

Comment on attachment 777462 [details] [diff] [review]
Make sure all bitwise operations are truncating their inputs.

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

::: js/src/ion/RangeAnalysis.cpp
@@ +390,2 @@
>      else if (def->type() == MIRType_Boolean)
>          truncateToBoolean();

I think this method would read better if written this way -- without any redundant range-copy at all.  (This also lets you get rid of emptyRange entirely, avoiding a static initializer.)

    const Range *other = def->range();
    if (def->type() == MIRType_Boolean) {
        truncateToBoolean();
    } else {
        const Range *other = def->range();
        if (!other) {
            makeRangeInfinite();
            symbolicLower_ = symbolicUpper_ = NULL;
        } else if (def->type() == MIRType_Int32) {
            *this = *other;
            symbolicLower_ = symbolicUpper_ = NULL;
        } else {
            lower_ = other->lower_;
            lower_infinite_ = other->lower_infinite_;
            upper_ = other->upper_;
            upper_infinite_ = other->upper_infinite_;
            decimal_ = other->decimal_;
            max_exponent_ = other->max_exponent_;
        }
    }

I'm pretty sure this is equivalent, although you should double-check me on that.

@@ -734,5 @@
>  
>      setRange(range);
> -
> -    if (block()->isLoopHeader()) {
> -    }

This was important!  Why are you removing this?

@@ +869,4 @@
>  
>      MDefinition *rhs = getOperand(1);
>      if (!rhs->isConstant()) {
> +        right.truncate();

Technically this (and the same in M{Ur,R}sh::computeRange) is wrong.  This is cutting it down to the int32_t range, but really that operand is converted to the uint32_t range.  But because of the bitwise-identical nature, it doesn't *actually* make a difference in the final analysis.  Correct?

@@ +1018,5 @@
>  void
>  MToInt32::computeRange()
>  {
> +    Range *output = new Range(getOperand(0));
> +    output->clamp();

Why clamp, here?  Suppose the actual range of values for the input were [INT32_MIN - 5, INT32_MIN + 2], which would be represented as [INT32_MIN and lower_infinite_, INT32_MIN + 2 and !upper_infinite_].  The output is that value modulo the int32_t range, if I understand correctly.  Won't clamp convert this to the output range [INT32_MIN, INT32_MIN + 2], even tho INT32_MIN - 1 should convert to INT32_MAX?

@@ +1560,5 @@
>      // Truncate the double to int, since all uses truncates it.
>      value_.setInt32(ToInt32(value_.toDouble()));
>      setResultType(MIRType_Int32);
>      if (range())
> +        range()->clamp();

Hmm.  Why wouldn't this range be exactly the single element |ToInt32(value_.toDouble())|?

@@ +1577,5 @@
>  
>      specialization_ = MIRType_Int32;
>      setResultType(MIRType_Int32);
>      if (range())
> +        range()->clamp();

So, yeah, this should have been truncate, because

   (a + b) | 0

if a + b overflows int32_t space, wraps around to INT32_MIN and such.  I want a test which hits this.  :-P  Same holds for MSub.

@@ +1660,5 @@
>  MToDouble::truncate()
>  {
>      JS_ASSERT(type() == MIRType_Double);
>  
>      // We use the return type to flag that this MToDouble sould be replaced by a

should

::: js/src/ion/RangeAnalysis.h
@@ +338,5 @@
>          JS_ASSERT_IF(upper_infinite_, upper_ == JSVAL_INT_MAX);
>      }
>  
> +    // Clamp the result to the Int32 range by removing the infinities.
> +    void clamp();

// Make the lower end of this range at least INT32_MIN, and make
// the upper end of this range at most INT32_MAX.

I'd name this clampToInt32() for clarity.  The meaning of "clamp" alone is not necessarily clear to someone reading the code, without prior knowledge of it.

@@ +346,1 @@
>      void truncate();

// If this range exceeds int32_t range, at either or both ends, change
// it to int32_t range.  Otherwise do nothing.
void setToInt32RangeIfOverflows();

Comment 11

[Nicolas B. Pierron [:nbp]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #10)
> @@ -734,5 @@
> >  
> >      setRange(range);
> > -
> > -    if (block()->isLoopHeader()) {
> > -    }
> 
> This was important!  Why are you removing this?

Hum … you are right, this might have some unknown side-effect, I guess we should keep it around.

> @@ +869,4 @@
> >  
> >      MDefinition *rhs = getOperand(1);
> >      if (!rhs->isConstant()) {
> > +        right.truncate();
> 
> Technically this (and the same in M{Ur,R}sh::computeRange) is wrong.  This
> is cutting it down to the int32_t range, but really that operand is
> converted to the uint32_t range.  But because of the bitwise-identical
> nature, it doesn't *actually* make a difference in the final analysis. 
> Correct?

To be correct, they are supposed to be clamped to the range [0 .. 31].

> @@ +1018,5 @@
> >  void
> >  MToInt32::computeRange()
> >  {
> > +    Range *output = new Range(getOperand(0));
> > +    output->clamp();
> 
> Why clamp, here?  Suppose the actual range of values for the input were
> [INT32_MIN - 5, INT32_MIN + 2], which would be represented as [INT32_MIN and
> lower_infinite_, INT32_MIN + 2 and !upper_infinite_].  The output is that
> value modulo the int32_t range, if I understand correctly.  Won't clamp
> convert this to the output range [INT32_MIN, INT32_MIN + 2], even tho
> INT32_MIN - 1 should convert to INT32_MAX?

ion::MToInt32 bails if the input is not an Int32 and it does not cause any overflow if the value is bigger or lower.
So clamp seems to be the correct meaning for it.

> @@ +1560,5 @@
> >      // Truncate the double to int, since all uses truncates it.
> >      value_.setInt32(ToInt32(value_.toDouble()));
> >      setResultType(MIRType_Int32);
> >      if (range())
> > +        range()->clamp();
> 
> Hmm.  Why wouldn't this range be exactly the single element
> |ToInt32(value_.toDouble())|?

Because I already do that as part of attachment 777517 [details] [diff] [review].

Comment 12

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1: Make sure all bitwise operations are truncating their inputs.

Delta:
- Apply nits.
- Rename truncate to wrapToInt32.
- Add wrapToShiftCounter for shift right operands.
- Add default value for Range::set.

Comment 13

[Jeff Walden [:Waldo]]

Comment on attachment 778215 [details] [diff] [review]
Part 1: Make sure all bitwise operations are truncating their inputs.

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

r=me if you write some tests that exercise some of the extra bugs that this fixes in truncated addition/subtraction/multiplication/etc.  Make sure the tests fail without the patch and pass with, of course.

::: js/src/ion/RangeAnalysis.cpp
@@ +368,5 @@
>     max_exponent_ = max_exponent;
>  }
>  
> +const int64_t RANGE_INF_MAX = (int64_t) JSVAL_INT_MAX + 1;
> +const int64_t RANGE_INF_MIN = (int64_t) JSVAL_INT_MIN - 1;

int64_t(JSVAL_INT_MAX) and so on (C++ casts).

@@ +1538,5 @@
> +Range::wrapToShiftCounter()
> +{
> +    if (lower() >= 0 || upper() < 32)
> +        return;
> +    set(0, 31);

I think this would read slightly better if it doesn't require mentally inverting logic:

  if (lower() < 0 || upper() >= 32)
    set(0, 31);

Also, is that condition even right?  I think you wanted && there, not ||.

::: js/src/ion/RangeAnalysis.h
@@ +343,5 @@
> +    void clampToInt32();
> +
> +    // If this range exceeds int32_t range, at either or both ends, change
> +    // it to int32_t range.  Otherwise do nothing.
> +    void wrapToInt32();

"wrap" is a heavily overloaded term.  For what you want, "wrap around" (or wrap-around, or wraparound, I dunno offhand what's most canonical) is the unambiguous phrase.  "wrap", in a method name written like this, doesn't connote wraparound at all.

So, how to name all these wrap-methods.  wrapAroundToInt32, wrapAroundToShiftCount, wrapAroundToBoolean?

@@ +346,5 @@
> +    // it to int32_t range.  Otherwise do nothing.
> +    void wrapToInt32();
> +
> +    // If this range exceeds [0..32] range, at either or both ends, change
> +    // it to the [0..32] range.  Otherwise do nothing.

[0..32) to exclude 32.

Mathematical notation would more often be [0, 32) with a comma, but it doesn't really matter.  I'd use the math notation if I were writing this.

@@ +347,5 @@
> +    void wrapToInt32();
> +
> +    // If this range exceeds [0..32] range, at either or both ends, change
> +    // it to the [0..32] range.  Otherwise do nothing.
> +    void wrapToShiftCounter();

ShiftCount, definitely.  There's no counter-ness to this at all.

Comment 14

[Nicolas B. Pierron [:nbp]]

Part 1 - http://hg.mozilla.org/integration/mozilla-inbound/rev/322a966b388e
Part 2 - http://hg.mozilla.org/integration/mozilla-inbound/rev/68e224769eb1

Comment 16

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

https://hg.mozilla.org/mozilla-central/rev/322a966b388e
https://hg.mozilla.org/mozilla-central/rev/68e224769eb1

Comment 17

[Hannes Verschore [:h4writer]]

68e224769eb1 Bug 894786 - Part 2: Work around the lack of unsigned representation. r=jandem
6aa9971523fc Bug 894794 - Collect Range info ahead instead of manipulating operand ranges. 
4e17c7ca2432 Bug 894794 - Fix truncated range of constants. r=jandem
322a966b388e Bug 894786 - Ensure all bitwise operations are truncating their inputs. r=Waldo

I assume one of these gave a regression on kraken-desaturate of 14.3%