The Tor Browser: comparison js/src/jit/RangeAnalysis.h

--1:000000000000
+:c13f0898f460
+/* -*- 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 / file comparison

comparison: js/src/jit/RangeAnalysis.h

js/src/jit/RangeAnalysis.h