Bug 918607 - IonMonkey: Add a Range::setDouble which takes double arguments and use it to simplify and generalize several things.
authorDan Gohman <sunfish@google.com>
Tue, 15 Oct 2013 20:49:44 -0700
changeset 150874 42a20a0d42695e2787a6052ed62a66b371cd8a65
parent 150873 eba7271a9bee4b06a0c894b10c8ab48764cf68cd
child 150875 d0fc1cc4c62b1b219ef3498e76b89a93c1b8cdd1
push id35002
push usersunfish@google.com
push dateWed, 16 Oct 2013 03:54:41 +0000
treeherdermozilla-inbound@d0fc1cc4c62b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs918607
milestone27.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 918607 - IonMonkey: Add a Range::setDouble which takes double arguments and use it to simplify and generalize several things.
js/src/jit/RangeAnalysis.cpp
js/src/jit/RangeAnalysis.h
--- a/js/src/jit/RangeAnalysis.cpp
+++ b/js/src/jit/RangeAnalysis.cpp
@@ -24,17 +24,20 @@ using namespace js::jit;
 using mozilla::Abs;
 using mozilla::CountLeadingZeroes32;
 using mozilla::DoubleIsInt32;
 using mozilla::ExponentComponent;
 using mozilla::IsInfinite;
 using mozilla::IsFinite;
 using mozilla::IsNaN;
 using mozilla::IsNegative;
+using mozilla::NegativeInfinity;
+using mozilla::PositiveInfinity;
 using mozilla::Swap;
+using JS::GenericNaN;
 
 // This algorithm is based on the paper "Eliminating Range Checks Using
 // Static Single Assignment Form" by Gough and Klaren.
 //
 // We associate a range object with each SSA name, and the ranges are consulted
 // in order to determine whether overflow is possible for arithmetic
 // computations.
 //
@@ -137,32 +140,29 @@ RangeAnalysis::addBetaNodes()
 
         BranchDirection branch_dir;
         MTest *test = block->immediateDominatorBranch(&branch_dir);
 
         if (!test || !test->getOperand(0)->isCompare())
             continue;
 
         MCompare *compare = test->getOperand(0)->toCompare();
-
-        // TODO: support unsigned comparisons
-        if (compare->compareType() == MCompare::Compare_UInt32)
-            continue;
-
         MDefinition *left = compare->getOperand(0);
         MDefinition *right = compare->getOperand(1);
         double bound;
-        int16_t exponent = Range::IncludesInfinity;
+        double conservativeLower = NegativeInfinity();
+        double conservativeUpper = PositiveInfinity();
         MDefinition *val = nullptr;
 
         JSOp jsop = compare->jsop();
 
         if (branch_dir == FALSE_BRANCH) {
             jsop = analyze::NegateCompareOp(jsop);
-            exponent = Range::IncludesInfinityAndNaN;
+            conservativeLower = GenericNaN();
+            conservativeUpper = GenericNaN();
         }
 
         if (left->isConstant() && left->toConstant()->value().isNumber()) {
             bound = left->toConstant()->value().toNumber();
             val = right;
             jsop = analyze::ReverseCompareOp(jsop);
         } else if (right->isConstant() && right->toConstant()->value().isNumber()) {
             bound = right->toConstant()->value().toNumber();
@@ -192,49 +192,44 @@ RangeAnalysis::addBetaNodes()
         } else {
             continue;
         }
 
         // At this point, one of the operands if the compare is a constant, and
         // val is the other operand.
         JS_ASSERT(val);
 
-        // If we can't convert this bound to an int32_t, it won't be as easy to
-        // create interesting Ranges with.
-        if (!IsFinite(bound) || bound < INT32_MIN || bound > INT32_MAX)
-            continue;
-
         Range comp;
         switch (jsop) {
           case JSOP_LE:
-            comp.set(Range::NoInt32LowerBound, ceil(bound), true, exponent);
+            comp.setDouble(conservativeLower, bound);
             break;
           case JSOP_LT:
             // For integers, if x < c, the upper bound of x is c-1.
             if (val->type() == MIRType_Int32) {
                 int32_t intbound;
                 if (DoubleIsInt32(bound, &intbound) && SafeSub(intbound, 1, &intbound))
                     bound = intbound;
             }
-            comp.set(Range::NoInt32LowerBound, ceil(bound), true, exponent);
+            comp.setDouble(conservativeLower, bound);
             break;
           case JSOP_GE:
-            comp.set(floor(bound), Range::NoInt32UpperBound, true, exponent);
+            comp.setDouble(bound, conservativeUpper);
             break;
           case JSOP_GT:
             // For integers, if x > c, the lower bound of x is c+1.
             if (val->type() == MIRType_Int32) {
                 int32_t intbound;
                 if (DoubleIsInt32(bound, &intbound) && SafeAdd(intbound, 1, &intbound))
                     bound = intbound;
             }
-            comp.set(floor(bound), Range::NoInt32UpperBound, true, exponent);
+            comp.setDouble(bound, conservativeUpper);
             break;
           case JSOP_EQ:
-            comp.set(floor(bound), ceil(bound), true, exponent);
+            comp.setDouble(bound, bound);
             break;
           default:
             continue; // well, for neq we could have
                       // [-\inf, bound-1] U [bound+1, \inf] but we only use contiguous ranges.
         }
 
         if (IonSpewEnabled(IonSpew_Range)) {
             IonSpewHeader(IonSpew_Range);
@@ -372,16 +367,36 @@ Range::intersect(const Range *lhs, const
         return nullptr;
     }
 
     bool newHasInt32LowerBound = lhs->hasInt32LowerBound_ || rhs->hasInt32LowerBound_;
     bool newHasInt32UpperBound = lhs->hasInt32UpperBound_ || rhs->hasInt32UpperBound_;
     bool newFractional = lhs->canHaveFractionalPart_ && rhs->canHaveFractionalPart_;
     uint16_t newExponent = Min(lhs->max_exponent_, rhs->max_exponent_);
 
+    // If one of the ranges has a fractional part and the other doesn't, it's
+    // possible that we will have computed a newExponent that's more precise
+    // than our newLower and newUpper. This is unusual, so we handle it here
+    // instead of in optimize().
+    //
+    // For example, when the floating-point range has an actual maximum value
+    // of 1.5, it may have a range like [0,2] and the max_exponent may be zero.
+    // When intersecting such a range with an integer range, the fractional part
+    // of the range is dropped, but the max exponent of 0 remains valid.
+    if (lhs->canHaveFractionalPart_ != rhs->canHaveFractionalPart_ &&
+        newExponent < MaxInt32Exponent)
+    {
+        // pow(2, newExponent+1)-1 to compute the maximum value for newExponent.
+        int32_t limit = (uint32_t(1) << (newExponent + 1)) - 1;
+        if (limit != INT32_MIN) {
+            newUpper = Min(newUpper, limit);
+            newLower = Max(newLower, -limit);
+        }
+    }
+
     return new Range(newLower, newHasInt32LowerBound, newUpper, newHasInt32UpperBound,
                      newFractional, newExponent);
 }
 
 void
 Range::unionWith(const Range *other)
 {
     int32_t newLower = Min(lower_, other->lower_);
@@ -442,16 +457,67 @@ Range::Range(const MDefinition *def)
     // (INT32_MAX,UINT32_MAX], set the range to be conservatively correct for
     // use as either a uint32 or an int32.
     if (!hasInt32UpperBound() && def->isUrsh() && def->toUrsh()->bailoutsDisabled())
         lower_ = INT32_MIN;
 
     assertInvariants();
 }
 
+static uint16_t
+ExponentImpliedByDouble(double d)
+{
+    // Handle the special values.
+    if (IsNaN(d))
+        return Range::IncludesInfinityAndNaN;
+    if (IsInfinite(d))
+        return Range::IncludesInfinity;
+
+    // Otherwise take the exponent part and clamp it at zero, since the Range
+    // class doesn't track fractional ranges.
+    return uint16_t(Max(int_fast16_t(0), ExponentComponent(d)));
+}
+
+void
+Range::setDouble(double l, double h)
+{
+    // Infer lower_, upper_, hasInt32LowerBound_, and hasInt32UpperBound_.
+    if (l >= INT32_MIN && l <= INT32_MAX) {
+        lower_ = int32_t(floor(l));
+        hasInt32LowerBound_ = true;
+    } else {
+        lower_ = INT32_MIN;
+        hasInt32LowerBound_ = false;
+    }
+    if (h >= INT32_MIN && h <= INT32_MAX) {
+        upper_ = int32_t(ceil(h));
+        hasInt32UpperBound_ = true;
+    } else {
+        upper_ = INT32_MAX;
+        hasInt32UpperBound_ = false;
+    }
+
+    // Infer max_exponent_.
+    uint16_t lExp = ExponentImpliedByDouble(l);
+    uint16_t hExp = ExponentImpliedByDouble(h);
+    max_exponent_ = Max(lExp, hExp);
+
+    // Infer the canHaveFractionalPart_ field. We can have a fractional part
+    // if the range crosses through the neighborhood of zero. We won't have a
+    // fractional value if the value is always beyond the point at which
+    // double precision can't represent fractional values.
+    uint16_t minExp = Min(lExp, hExp);
+    bool includesNegative = IsNaN(l) || l < 0;
+    bool includesPositive = IsNaN(h) || h > 0;
+    bool crossesZero = includesNegative && includesPositive;
+    canHaveFractionalPart_ = crossesZero || minExp < MaxTruncatableExponent;
+
+    optimize();
+}
+
 static inline bool
 MissingAnyInt32Bounds(const Range *lhs, const Range *rhs)
 {
     return !lhs->hasInt32LowerBound() || !lhs->hasInt32UpperBound() ||
            !rhs->hasInt32LowerBound() || !rhs->hasInt32UpperBound();
 }
 
 Range *
@@ -896,78 +962,19 @@ MBeta::computeRange()
     } else {
         setRange(range);
     }
 }
 
 void
 MConstant::computeRange()
 {
-    if (type() == MIRType_Int32) {
-        setRange(Range::NewSingleValueRange(value().toInt32()));
-        return;
-    }
-
-    if (type() != MIRType_Double)
-        return;
-
-    double d = value().toDouble();
-
-    // NaN is not handled by range analysis.
-    if (IsNaN(d))
-        return;
-
-    // Beyond-int32 values are used to set both lower and upper to the range boundaries.
-    if (IsInfinite(d)) {
-        if (IsNegative(d))
-            setRange(Range::NewDoubleRange(Range::NoInt32LowerBound,
-                                           Range::NoInt32LowerBound,
-                                           Range::IncludesInfinity));
-        else
-            setRange(Range::NewDoubleRange(Range::NoInt32UpperBound,
-                                           Range::NoInt32UpperBound,
-                                           Range::IncludesInfinity));
-        return;
-    }
-
-    // Extract the exponent, to approximate it with the range analysis.
-    int exp = ExponentComponent(d);
-    if (exp < 0) {
-        // This double only has a fractional part.
-        if (IsNegative(d))
-            setRange(Range::NewDoubleRange(-1, 0));
-        else
-            setRange(Range::NewDoubleRange(0, 1));
-    } else if (exp < Range::MaxTruncatableExponent) {
-        // Extract the integral part.
-        int64_t integral = ToInt64(d);
-        // Extract the fractional part.
-        double rest = d - (double) integral;
-        // Estimate the smallest integral boundaries.
-        //   Safe double comparisons, because there is no precision loss.
-        int64_t l = integral - ((rest < 0) ? 1 : 0);
-        int64_t h = integral + ((rest > 0) ? 1 : 0);
-        // If we adjusted into a new exponent range, adjust exp accordingly.
-        if ((rest < 0 && (l == INT64_MIN || IsPowerOfTwo(Abs(l)))) ||
-            (rest > 0 && (h == INT64_MIN || IsPowerOfTwo(Abs(h)))))
-        {
-            ++exp;
-        }
-        setRange(new Range(l, h, (rest != 0), exp));
-    } else {
-        // This double has a precision loss. This also mean that it cannot
-        // encode any values with fractional parts.
-        if (IsNegative(d))
-            setRange(Range::NewDoubleRange(Range::NoInt32LowerBound,
-                                           Range::NoInt32LowerBound,
-                                           exp));
-        else
-            setRange(Range::NewDoubleRange(Range::NoInt32UpperBound,
-                                           Range::NoInt32UpperBound,
-                                           exp));
+    if (value().isNumber()) {
+        double d = value().toNumber();
+        setRange(Range::NewDoubleRange(d, d));
     }
 }
 
 void
 MCharCodeAt::computeRange()
 {
     // ECMA 262 says that the integer will be non-negative and at most 65535.
     setRange(Range::NewInt32Range(0, 65535));
--- a/js/src/jit/RangeAnalysis.h
+++ b/js/src/jit/RangeAnalysis.h
@@ -171,25 +171,44 @@ class Range : public TempObject {
 
     // Any symbolic lower or upper bound computed for this term.
     const SymbolicBound *symbolicLower_;
     const SymbolicBound *symbolicUpper_;
 
     // This function simply makes several JS_ASSERTs to verify the internal
     // consistency of this range.
     void assertInvariants() const {
+        // Basic sanity :).
         JS_ASSERT(lower_ <= upper_);
+
+        // When hasInt32LowerBound_ or hasInt32UpperBound_ are false, we set
+        // lower_ and upper_ to these specific values as it simplifies the
+        // implementation in some places.
         JS_ASSERT_IF(!hasInt32LowerBound_, lower_ == JSVAL_INT_MIN);
         JS_ASSERT_IF(!hasInt32UpperBound_, upper_ == JSVAL_INT_MAX);
-        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_, max_exponent_ >= MaxInt32Exponent);
+
+        // max_exponent_ must be one of three possible things.
         JS_ASSERT(max_exponent_ <= MaxFiniteExponent ||
                   max_exponent_ == IncludesInfinity ||
                   max_exponent_ == IncludesInfinityAndNaN);
-        JS_ASSERT(max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(upper_)));
-        JS_ASSERT(max_exponent_ >= mozilla::FloorLog2(mozilla::Abs(lower_)));
+
+        // Forbid the max_exponent_ field from implying better bounds for
+        // lower_/upper_ fields. We have to add 1 to the max_exponent_ when
+        // canHaveFractionalPart_ is true in order to accomodate fractional
+        // offsets. For example, 2147483647.9 is greater than INT32_MAX, so a
+        // range containing that value will have hasInt32UpperBound_ set to
+        // false, however that value also has exponent 30, which is strictly
+        // less than MaxInt32Exponent. For another example, 1.9 has an exponent
+        // of 0 but requires upper_ to be at least 2, which has exponent 1.
+        JS_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
+                     max_exponent_ + canHaveFractionalPart_ >= MaxInt32Exponent);
+        JS_ASSERT(max_exponent_ + canHaveFractionalPart_ >=
+                  mozilla::FloorLog2(mozilla::Abs(upper_)));
+        JS_ASSERT(max_exponent_ + canHaveFractionalPart_ >=
+                  mozilla::FloorLog2(mozilla::Abs(lower_)));
 
         // The following are essentially static assertions, but FloorLog2 isn't
         // trivially suitable for constexpr :(.
         JS_ASSERT(mozilla::FloorLog2(JSVAL_INT_MIN) == MaxInt32Exponent);
         JS_ASSERT(mozilla::FloorLog2(JSVAL_INT_MAX) == 30);
         JS_ASSERT(mozilla::FloorLog2(UINT32_MAX) == MaxUInt32Exponent);
         JS_ASSERT(mozilla::FloorLog2(0) == 0);
     }
@@ -317,22 +336,23 @@ class Range : public TempObject {
     }
 
     static Range *NewUInt32Range(uint32_t l, uint32_t h) {
         // For now, just pass them to the constructor as int64_t values.
         // They'll become unbounded if they're not in the int32_t range.
         return new Range(l, h, false, MaxUInt32Exponent);
     }
 
-    static Range *NewDoubleRange(int64_t l, int64_t h, uint16_t e = IncludesInfinityAndNaN) {
-        return new Range(l, h, true, e);
-    }
+    static Range *NewDoubleRange(double l, double h) {
+        if (mozilla::IsNaN(l) && mozilla::IsNaN(h))
+            return nullptr;
 
-    static Range *NewSingleValueRange(int64_t v) {
-        return new Range(v, v, false, IncludesInfinityAndNaN);
+        Range *r = new Range();
+        r->setDouble(l, h);
+        return r;
     }
 
     void print(Sprinter &sp) const;
     void dump(FILE *fp) const;
     bool update(const Range *other);
 
     // Unlike the other operations, unionWith is an in-place
     // modification. This is to avoid a bunch of useless extra
@@ -480,22 +500,21 @@ class Range : public TempObject {
         hasInt32UpperBound_ = true;
         lower_ = l;
         upper_ = h;
         canHaveFractionalPart_ = false;
         max_exponent_ = exponentImpliedByInt32Bounds();
         assertInvariants();
     }
 
+    void setDouble(double l, double h);
+
     void setUnknown() {
-        setDouble(NoInt32LowerBound, NoInt32UpperBound);
-    }
-
-    void setDouble(int64_t l, int64_t h, uint16_t e = IncludesInfinityAndNaN) {
-        set(l, h, true, e);
+        set(NoInt32LowerBound, NoInt32UpperBound, true, IncludesInfinityAndNaN);
+        JS_ASSERT(isUnknown());
     }
 
     void set(int64_t l, int64_t h, bool f, uint16_t e) {
         max_exponent_ = e;
         canHaveFractionalPart_ = f;
         setLowerInit(l);
         setUpperInit(h);
         optimize();