author | Dan Gohman <sunfish@google.com> |
Tue, 15 Oct 2013 20:49:44 -0700 | |
changeset 150874 | 42a20a0d42695e2787a6052ed62a66b371cd8a65 |
parent 150873 | eba7271a9bee4b06a0c894b10c8ab48764cf68cd |
child 150875 | d0fc1cc4c62b1b219ef3498e76b89a93c1b8cdd1 |
push id | 25469 |
push user | cbook@mozilla.com |
push date | Wed, 16 Oct 2013 10:46:01 +0000 |
treeherder | autoland@afae5911a1e0 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
bugs | 918607 |
milestone | 27.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
|
js/src/jit/RangeAnalysis.cpp | file | annotate | diff | comparison | revisions | |
js/src/jit/RangeAnalysis.h | file | annotate | diff | comparison | revisions |
--- 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();