The Tor Browser: js/src/jit/RangeAnalysis.h@6474c204b198 (annotated)

js/src/jit/RangeAnalysis.h@6474c204b198 (annotated)

js/src/jit/RangeAnalysis.h

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- 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<double>::ExponentShift;
     // Maximum exponent for finite values.
     static const uint16_t MaxFiniteExponent = mozilla::FloatingPoint<double>::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 */

The Tor Browser / annotate

js/src/jit/RangeAnalysis.h@6474c204b198 (annotated)

js/src/jit/RangeAnalysis.h