diff -r 000000000000 -r 6474c204b198 js/src/jit/RangeAnalysis.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/RangeAnalysis.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,591 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef jit_RangeAnalysis_h +#define jit_RangeAnalysis_h + +#include "mozilla/FloatingPoint.h" +#include "mozilla/MathAlgorithms.h" + +#include "jit/IonAnalysis.h" +#include "jit/MIR.h" + +// windows.h defines those, which messes with the definitions below. +#undef min +#undef max + +namespace js { +namespace jit { + +class MBasicBlock; +class MIRGraph; + +// An upper bound computed on the number of backedges a loop will take. +// This count only includes backedges taken while running Ion code: for OSR +// loops, this will exclude iterations that executed in the interpreter or in +// baseline compiled code. +struct LoopIterationBound : public TempObject +{ + // Loop for which this bound applies. + MBasicBlock *header; + + // Test from which this bound was derived. Code in the loop body which this + // test dominates (will include the backedge) will execute at most 'bound' + // times. Other code in the loop will execute at most '1 + Max(bound, 0)' + // times. + MTest *test; + + // Symbolic bound computed for the number of backedge executions. + LinearSum sum; + + LoopIterationBound(MBasicBlock *header, MTest *test, LinearSum sum) + : header(header), test(test), sum(sum) + { + } +}; + +// A symbolic upper or lower bound computed for a term. +struct SymbolicBound : public TempObject +{ + private: + SymbolicBound(LoopIterationBound *loop, LinearSum sum) + : loop(loop), sum(sum) + { + } + + public: + // Any loop iteration bound from which this was derived. + // + // If non-nullptr, then 'sum' is only valid within the loop body, at + // points dominated by the loop bound's test (see LoopIterationBound). + // + // If nullptr, then 'sum' is always valid. + LoopIterationBound *loop; + + static SymbolicBound *New(TempAllocator &alloc, LoopIterationBound *loop, LinearSum sum) { + return new(alloc) SymbolicBound(loop, sum); + } + + // Computed symbolic bound, see above. + LinearSum sum; + + void print(Sprinter &sp) const; + void dump() const; +}; + +class RangeAnalysis +{ + protected: + bool blockDominates(MBasicBlock *b, MBasicBlock *b2); + void replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom, + MBasicBlock *block); + + protected: + MIRGenerator *mir; + MIRGraph &graph_; + + TempAllocator &alloc() const; + + public: + MOZ_CONSTEXPR RangeAnalysis(MIRGenerator *mir, MIRGraph &graph) : + mir(mir), graph_(graph) {} + bool addBetaNodes(); + bool analyze(); + bool addRangeAssertions(); + bool removeBetaNodes(); + bool prepareForUCE(bool *shouldRemoveDeadCode); + bool truncate(); + + private: + bool analyzeLoop(MBasicBlock *header); + LoopIterationBound *analyzeLoopIterationCount(MBasicBlock *header, + MTest *test, BranchDirection direction); + void analyzeLoopPhi(MBasicBlock *header, LoopIterationBound *loopBound, MPhi *phi); + bool tryHoistBoundsCheck(MBasicBlock *header, MBoundsCheck *ins); + bool markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current); +}; + +class Range : public TempObject { + public: + // Int32 are signed. INT32_MAX is pow(2,31)-1 and INT32_MIN is -pow(2,31), + // so the greatest exponent we need is 31. + static const uint16_t MaxInt32Exponent = 31; + + // UInt32 are unsigned. UINT32_MAX is pow(2,32)-1, so it's the greatest + // value that has an exponent of 31. + static const uint16_t MaxUInt32Exponent = 31; + + // Maximal exponenent under which we have no precission loss on double + // operations. Double has 52 bits of mantissa, so 2^52+1 cannot be + // represented without loss. + static const uint16_t MaxTruncatableExponent = mozilla::FloatingPoint::ExponentShift; + + // Maximum exponent for finite values. + static const uint16_t MaxFiniteExponent = mozilla::FloatingPoint::ExponentBias; + + // An special exponent value representing all non-NaN values. This + // includes finite values and the infinities. + static const uint16_t IncludesInfinity = MaxFiniteExponent + 1; + + // An special exponent value representing all possible double-precision + // values. This includes finite values, the infinities, and NaNs. + static const uint16_t IncludesInfinityAndNaN = UINT16_MAX; + + // This range class uses int32_t ranges, but has several interfaces which + // use int64_t, which either holds an int32_t value, or one of the following + // special values which mean a value which is beyond the int32 range, + // potentially including infinity or NaN. These special values are + // guaranteed to compare greater, and less than, respectively, any int32_t + // value. + static const int64_t NoInt32UpperBound = int64_t(JSVAL_INT_MAX) + 1; + static const int64_t NoInt32LowerBound = int64_t(JSVAL_INT_MIN) - 1; + + private: + // Absolute ranges. + // + // We represent ranges where the endpoints can be in the set: + // {-infty} U [INT_MIN, INT_MAX] U {infty}. A bound of +/- + // infty means that the value may have overflowed in that + // direction. When computing the range of an integer + // instruction, the ranges of the operands can be clamped to + // [INT_MIN, INT_MAX], since if they had overflowed they would + // no longer be integers. This is important for optimizations + // and somewhat subtle. + // + // N.B.: All of the operations that compute new ranges based + // on existing ranges will ignore the hasInt32*Bound_ flags of the + // input ranges; that is, they implicitly clamp the ranges of + // the inputs to [INT_MIN, INT_MAX]. Therefore, while our range might + // be unbounded (and could overflow), when using this information to + // propagate through other ranges, we disregard this fact; if that code + // executes, then the overflow did not occur, so we may safely assume + // that the range is [INT_MIN, INT_MAX] instead. + // + // To facilitate this trick, we maintain the invariants that: + // 1) hasInt32LowerBound_ == false implies lower_ == JSVAL_INT_MIN + // 2) hasInt32UpperBound_ == false implies upper_ == JSVAL_INT_MAX + // + // As a second and less precise range analysis, we represent the maximal + // exponent taken by a value. The exponent is calculated by taking the + // absolute value and looking at the position of the highest bit. All + // exponent computation have to be over-estimations of the actual result. On + // the Int32 this over approximation is rectified. + + int32_t lower_; + bool hasInt32LowerBound_; + + int32_t upper_; + bool hasInt32UpperBound_; + + bool canHaveFractionalPart_; + uint16_t max_exponent_; + + // 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); + + // max_exponent_ must be one of three possible things. + JS_ASSERT(max_exponent_ <= MaxFiniteExponent || + max_exponent_ == IncludesInfinity || + max_exponent_ == IncludesInfinityAndNaN); + + // 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); + } + + // Set the lower_ and hasInt32LowerBound_ values. + void setLowerInit(int64_t x) { + if (x > JSVAL_INT_MAX) { + lower_ = JSVAL_INT_MAX; + hasInt32LowerBound_ = true; + } else if (x < JSVAL_INT_MIN) { + lower_ = JSVAL_INT_MIN; + hasInt32LowerBound_ = false; + } else { + lower_ = int32_t(x); + hasInt32LowerBound_ = true; + } + } + // Set the upper_ and hasInt32UpperBound_ values. + void setUpperInit(int64_t x) { + if (x > JSVAL_INT_MAX) { + upper_ = JSVAL_INT_MAX; + hasInt32UpperBound_ = false; + } else if (x < JSVAL_INT_MIN) { + upper_ = JSVAL_INT_MIN; + hasInt32UpperBound_ = true; + } else { + upper_ = int32_t(x); + hasInt32UpperBound_ = true; + } + } + + // Compute the least exponent value that would be compatible with the + // values of lower() and upper(). + // + // Note: + // exponent of JSVAL_INT_MIN == 31 + // exponent of JSVAL_INT_MAX == 30 + uint16_t exponentImpliedByInt32Bounds() const { + // The number of bits needed to encode |max| is the power of 2 plus one. + uint32_t max = Max(mozilla::Abs(lower()), mozilla::Abs(upper())); + uint16_t result = mozilla::FloorLog2(max); + JS_ASSERT(result == (max == 0 ? 0 : mozilla::ExponentComponent(double(max)))); + return result; + } + + // When converting a range which contains fractional values to a range + // containing only integers, the old max_exponent_ value may imply a better + // lower and/or upper bound than was previously available, because they no + // longer need to be conservative about fractional offsets and the ends of + // the range. + // + // Given an exponent value and pointers to the lower and upper bound values, + // this function refines the lower and upper bound values to the tighest + // bound for integer values implied by the exponent. + static void refineInt32BoundsByExponent(uint16_t e, int32_t *l, int32_t *h) { + if (e < MaxInt32Exponent) { + // pow(2, max_exponent_+1)-1 to compute a maximum absolute value. + int32_t limit = (uint32_t(1) << (e + 1)) - 1; + *h = Min(*h, limit); + *l = Max(*l, -limit); + } + } + + // If the value of any of the fields implies a stronger possible value for + // any other field, update that field to the stronger value. The range must + // be completely valid before and it is guaranteed to be kept valid. + void optimize() { + assertInvariants(); + + if (hasInt32Bounds()) { + // Examine lower() and upper(), and if they imply a better exponent + // bound than max_exponent_, set that value as the new + // max_exponent_. + uint16_t newExponent = exponentImpliedByInt32Bounds(); + if (newExponent < max_exponent_) { + max_exponent_ = newExponent; + assertInvariants(); + } + + // If we have a completely precise range, the value is an integer, + // since we can only represent integers. + if (canHaveFractionalPart_ && lower_ == upper_) { + canHaveFractionalPart_ = false; + assertInvariants(); + } + } + } + + // Set the range fields to the given raw values. + void rawInitialize(int32_t l, bool lb, int32_t h, bool hb, bool f, uint16_t e) { + lower_ = l; + hasInt32LowerBound_ = lb; + upper_ = h; + hasInt32UpperBound_ = hb; + canHaveFractionalPart_ = f; + max_exponent_ = e; + optimize(); + } + + // Construct a range from the given raw values. + Range(int32_t l, bool lb, int32_t h, bool hb, bool f, uint16_t e) + : symbolicLower_(nullptr), + symbolicUpper_(nullptr) + { + rawInitialize(l, lb, h, hb, f, e); + } + + public: + Range() + : symbolicLower_(nullptr), + symbolicUpper_(nullptr) + { + setUnknown(); + } + + Range(int64_t l, int64_t h, bool f = false, uint16_t e = MaxInt32Exponent) + : symbolicLower_(nullptr), + symbolicUpper_(nullptr) + { + set(l, h, f, e); + } + + Range(const Range &other) + : lower_(other.lower_), + hasInt32LowerBound_(other.hasInt32LowerBound_), + upper_(other.upper_), + hasInt32UpperBound_(other.hasInt32UpperBound_), + canHaveFractionalPart_(other.canHaveFractionalPart_), + max_exponent_(other.max_exponent_), + symbolicLower_(nullptr), + symbolicUpper_(nullptr) + { + assertInvariants(); + } + + // Construct a range from the given MDefinition. This differs from the + // MDefinition's range() method in that it describes the range of values + // *after* any bailout checks. + Range(const MDefinition *def); + + static Range *NewInt32Range(TempAllocator &alloc, int32_t l, int32_t h) { + return new(alloc) Range(l, h, false, MaxInt32Exponent); + } + + static Range *NewUInt32Range(TempAllocator &alloc, 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(alloc) Range(l, h, false, MaxUInt32Exponent); + } + + static Range *NewDoubleRange(TempAllocator &alloc, double l, double h) { + if (mozilla::IsNaN(l) && mozilla::IsNaN(h)) + return nullptr; + + Range *r = new(alloc) Range(); + r->setDouble(l, h); + return r; + } + + void print(Sprinter &sp) const; + void dump(FILE *fp) const; + void dump() 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 + // copying when chaining together unions when handling Phi + // nodes. + void unionWith(const Range *other); + static Range *intersect(TempAllocator &alloc, const Range *lhs, const Range *rhs, + bool *emptyRange); + static Range *add(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *sub(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *mul(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *and_(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *or_(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *xor_(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *not_(TempAllocator &alloc, const Range *op); + static Range *lsh(TempAllocator &alloc, const Range *lhs, int32_t c); + static Range *rsh(TempAllocator &alloc, const Range *lhs, int32_t c); + static Range *ursh(TempAllocator &alloc, const Range *lhs, int32_t c); + static Range *lsh(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *rsh(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *ursh(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *abs(TempAllocator &alloc, const Range *op); + static Range *min(TempAllocator &alloc, const Range *lhs, const Range *rhs); + static Range *max(TempAllocator &alloc, const Range *lhs, const Range *rhs); + + static bool negativeZeroMul(const Range *lhs, const Range *rhs); + + bool isUnknownInt32() const { + return isInt32() && lower() == INT32_MIN && upper() == INT32_MAX; + } + + bool isUnknown() const { + return !hasInt32LowerBound_ && + !hasInt32UpperBound_ && + canHaveFractionalPart_ && + max_exponent_ == IncludesInfinityAndNaN; + } + + bool hasInt32LowerBound() const { + return hasInt32LowerBound_; + } + bool hasInt32UpperBound() const { + return hasInt32UpperBound_; + } + + // Test whether the value is known to be within [INT32_MIN,INT32_MAX]. + // Note that this does not necessarily mean the value is an integer. + bool hasInt32Bounds() const { + return hasInt32LowerBound() && hasInt32UpperBound(); + } + + // Test whether the value is known to be representable as an int32. + bool isInt32() const { + return hasInt32Bounds() && !canHaveFractionalPart(); + } + + // Test whether the given value is known to be either 0 or 1. + bool isBoolean() const { + return lower() >= 0 && upper() <= 1 && !canHaveFractionalPart(); + } + + bool canHaveRoundingErrors() const { + return canHaveFractionalPart() || max_exponent_ >= MaxTruncatableExponent; + } + + // Test whether the range contains zero. + bool canBeZero() const { + return lower_ <= 0 && upper_ >= 0; + } + + // Test whether the range contains NaN values. + bool canBeNaN() const { + return max_exponent_ == IncludesInfinityAndNaN; + } + + // Test whether the range contains infinities or NaN values. + bool canBeInfiniteOrNaN() const { + return max_exponent_ >= IncludesInfinity; + } + + bool canHaveFractionalPart() const { + return canHaveFractionalPart_; + } + + uint16_t exponent() const { + JS_ASSERT(!canBeInfiniteOrNaN()); + return max_exponent_; + } + + uint16_t numBits() const { + return exponent() + 1; // 2^0 -> 1 + } + + // Return the lower bound. Asserts that the value has an int32 bound. + int32_t lower() const { + JS_ASSERT(hasInt32LowerBound()); + return lower_; + } + + // Return the upper bound. Asserts that the value has an int32 bound. + int32_t upper() const { + JS_ASSERT(hasInt32UpperBound()); + return upper_; + } + + // Test whether all values in this range can are finite and negative. + bool isFiniteNegative() const { + return upper_ < 0 && !canBeInfiniteOrNaN(); + } + + // Test whether all values in this range can are finite and non-negative. + bool isFiniteNonNegative() const { + return lower_ >= 0 && !canBeInfiniteOrNaN(); + } + + // Test whether a value in this range can possibly be a finite + // negative value. + bool canBeFiniteNegative() const { + return lower_ < 0; + } + + // Test whether a value in this range can possibly be a finite + // non-negative value. + bool canBeFiniteNonNegative() const { + return upper_ >= 0; + } + + // Set this range to have a lower bound not less than x. + void refineLower(int32_t x) { + assertInvariants(); + hasInt32LowerBound_ = true; + lower_ = Max(lower_, x); + optimize(); + } + + // Set this range to have an upper bound not greater than x. + void refineUpper(int32_t x) { + assertInvariants(); + hasInt32UpperBound_ = true; + upper_ = Min(upper_, x); + optimize(); + } + + void setInt32(int32_t l, int32_t h) { + hasInt32LowerBound_ = true; + hasInt32UpperBound_ = true; + lower_ = l; + upper_ = h; + canHaveFractionalPart_ = false; + max_exponent_ = exponentImpliedByInt32Bounds(); + assertInvariants(); + } + + void setDouble(double l, double h); + + void setUnknown() { + 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(); + } + + // Make the lower end of this range at least INT32_MIN, and make + // the upper end of this range at most INT32_MAX. + void clampToInt32(); + + // If this range exceeds int32_t range, at either or both ends, change + // it to int32_t range. Otherwise do nothing. + void wrapAroundToInt32(); + + // If this range exceeds [0, 32) range, at either or both ends, change + // it to the [0, 32) range. Otherwise do nothing. + void wrapAroundToShiftCount(); + + // If this range exceeds [0, 1] range, at either or both ends, change + // it to the [0, 1] range. Otherwise do nothing. + void wrapAroundToBoolean(); + + const SymbolicBound *symbolicLower() const { + return symbolicLower_; + } + const SymbolicBound *symbolicUpper() const { + return symbolicUpper_; + } + + void setSymbolicLower(SymbolicBound *bound) { + symbolicLower_ = bound; + } + void setSymbolicUpper(SymbolicBound *bound) { + symbolicUpper_ = bound; + } +}; + +} // namespace jit +} // namespace js + +#endif /* jit_RangeAnalysis_h */