1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- 2 * vim: set ts=8 sts=2 et sw=2 tw=80: 3 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef jit_RangeAnalysis_h 8 #define jit_RangeAnalysis_h 9 10 #include "mozilla/Assertions.h" 11 #include "mozilla/Attributes.h" 12 #include "mozilla/DebugOnly.h" 13 #include "mozilla/FloatingPoint.h" 14 #include "mozilla/MathAlgorithms.h" 15 16 #include <algorithm> 17 #include <stdint.h> 18 19 #include "jit/IonAnalysis.h" 20 #include "jit/IonTypes.h" 21 #include "jit/JitAllocPolicy.h" 22 #include "js/AllocPolicy.h" 23 #include "js/Value.h" 24 #include "js/Vector.h" 25 26 namespace js { 27 28 class GenericPrinter; 29 30 namespace jit { 31 32 class MBasicBlock; 33 class MBinaryBitwiseInstruction; 34 class MBoundsCheck; 35 class MDefinition; 36 class MIRGenerator; 37 class MIRGraph; 38 class MPhi; 39 class MTest; 40 41 enum class TruncateKind; 42 43 // An upper bound computed on the number of backedges a loop will take. 44 // This count only includes backedges taken while running Ion code: for OSR 45 // loops, this will exclude iterations that executed in the interpreter or in 46 // baseline compiled code. 47 struct LoopIterationBound : public TempObject { 48 // Loop for which this bound applies. 49 MBasicBlock* header; 50 51 // Test from which this bound was derived; after executing exactly 'bound' 52 // times this test will exit the loop. Code in the loop body which this 53 // test dominates (will include the backedge) will execute at most 'bound' 54 // times. Other code in the loop will execute at most '1 + Max(bound, 0)' 55 // times. 56 MTest* test; 57 58 // Symbolic bound computed for the number of backedge executions. The terms 59 // in this bound are all loop invariant. 60 LinearSum boundSum; 61 62 // Linear sum for the number of iterations already executed, at the start 63 // of the loop header. This will use loop invariant terms and header phis. 64 LinearSum currentSum; 65 LoopIterationBoundLoopIterationBound66 LoopIterationBound(MBasicBlock* header, MTest* test, 67 const LinearSum& boundSum, const LinearSum& currentSum) 68 : header(header), 69 test(test), 70 boundSum(boundSum), 71 currentSum(currentSum) {} 72 }; 73 74 typedef Vector<LoopIterationBound*, 0, SystemAllocPolicy> 75 LoopIterationBoundVector; 76 77 // A symbolic upper or lower bound computed for a term. 78 struct SymbolicBound : public TempObject { 79 private: SymbolicBoundSymbolicBound80 SymbolicBound(LoopIterationBound* loop, const LinearSum& sum) 81 : loop(loop), sum(sum) {} 82 83 public: 84 // Any loop iteration bound from which this was derived. 85 // 86 // If non-nullptr, then 'sum' is only valid within the loop body, at 87 // points dominated by the loop bound's test (see LoopIterationBound). 88 // 89 // If nullptr, then 'sum' is always valid. 90 LoopIterationBound* loop; 91 NewSymbolicBound92 static SymbolicBound* New(TempAllocator& alloc, LoopIterationBound* loop, 93 const LinearSum& sum) { 94 return new (alloc) SymbolicBound(loop, sum); 95 } 96 97 // Computed symbolic bound, see above. 98 LinearSum sum; 99 100 void dump(GenericPrinter& out) const; 101 void dump() const; 102 }; 103 104 class RangeAnalysis { 105 protected: 106 bool blockDominates(MBasicBlock* b, MBasicBlock* b2); 107 void replaceDominatedUsesWith(MDefinition* orig, MDefinition* dom, 108 MBasicBlock* block); 109 110 protected: 111 MIRGenerator* mir; 112 MIRGraph& graph_; 113 Vector<MBinaryBitwiseInstruction*, 16, SystemAllocPolicy> bitops; 114 115 TempAllocator& alloc() const; 116 117 public: RangeAnalysis(MIRGenerator * mir,MIRGraph & graph)118 RangeAnalysis(MIRGenerator* mir, MIRGraph& graph) : mir(mir), graph_(graph) {} 119 [[nodiscard]] bool addBetaNodes(); 120 [[nodiscard]] bool analyze(); 121 [[nodiscard]] bool addRangeAssertions(); 122 [[nodiscard]] bool removeBetaNodes(); 123 [[nodiscard]] bool prepareForUCE(bool* shouldRemoveDeadCode); 124 [[nodiscard]] bool tryRemovingGuards(); 125 [[nodiscard]] bool truncate(); 126 [[nodiscard]] bool removeUnnecessaryBitops(); 127 128 bool canTruncate(MDefinition* def, TruncateKind kind) const; 129 void adjustTruncatedInputs(MDefinition* def); 130 131 // Any iteration bounds discovered for loops in the graph. 132 LoopIterationBoundVector loopIterationBounds; 133 134 private: 135 [[nodiscard]] bool analyzeLoop(MBasicBlock* header); 136 LoopIterationBound* analyzeLoopIterationCount(MBasicBlock* header, 137 MTest* test, 138 BranchDirection direction); 139 void analyzeLoopPhi(LoopIterationBound* loopBound, MPhi* phi); 140 [[nodiscard]] bool tryHoistBoundsCheck(MBasicBlock* header, 141 MBoundsCheck* ins); 142 }; 143 144 class Range : public TempObject { 145 public: 146 // Int32 are signed. INT32_MAX is pow(2,31)-1 and INT32_MIN is -pow(2,31), 147 // so the greatest exponent we need is 31. 148 static const uint16_t MaxInt32Exponent = 31; 149 150 // UInt32 are unsigned. UINT32_MAX is pow(2,32)-1, so it's the greatest 151 // value that has an exponent of 31. 152 static const uint16_t MaxUInt32Exponent = 31; 153 154 // Maximal exponenent under which we have no precission loss on double 155 // operations. Double has 52 bits of mantissa, so 2^52+1 cannot be 156 // represented without loss. 157 static const uint16_t MaxTruncatableExponent = 158 mozilla::FloatingPoint<double>::kExponentShift; 159 160 // Maximum exponent for finite values. 161 static const uint16_t MaxFiniteExponent = 162 mozilla::FloatingPoint<double>::kExponentBias; 163 164 // An special exponent value representing all non-NaN values. This 165 // includes finite values and the infinities. 166 static const uint16_t IncludesInfinity = MaxFiniteExponent + 1; 167 168 // An special exponent value representing all possible double-precision 169 // values. This includes finite values, the infinities, and NaNs. 170 static const uint16_t IncludesInfinityAndNaN = UINT16_MAX; 171 172 // This range class uses int32_t ranges, but has several interfaces which 173 // use int64_t, which either holds an int32_t value, or one of the following 174 // special values which mean a value which is beyond the int32 range, 175 // potentially including infinity or NaN. These special values are 176 // guaranteed to compare greater, and less than, respectively, any int32_t 177 // value. 178 static const int64_t NoInt32UpperBound = int64_t(JSVAL_INT_MAX) + 1; 179 static const int64_t NoInt32LowerBound = int64_t(JSVAL_INT_MIN) - 1; 180 181 enum FractionalPartFlag { 182 ExcludesFractionalParts = false, 183 IncludesFractionalParts = true 184 }; 185 enum NegativeZeroFlag { 186 ExcludesNegativeZero = false, 187 IncludesNegativeZero = true 188 }; 189 190 private: 191 // Absolute ranges. 192 // 193 // We represent ranges where the endpoints can be in the set: 194 // {-infty} U [INT_MIN, INT_MAX] U {infty}. A bound of +/- 195 // infty means that the value may have overflowed in that 196 // direction. When computing the range of an integer 197 // instruction, the ranges of the operands can be clamped to 198 // [INT_MIN, INT_MAX], since if they had overflowed they would 199 // no longer be integers. This is important for optimizations 200 // and somewhat subtle. 201 // 202 // N.B.: All of the operations that compute new ranges based 203 // on existing ranges will ignore the hasInt32*Bound_ flags of the 204 // input ranges; that is, they implicitly clamp the ranges of 205 // the inputs to [INT_MIN, INT_MAX]. Therefore, while our range might 206 // be unbounded (and could overflow), when using this information to 207 // propagate through other ranges, we disregard this fact; if that code 208 // executes, then the overflow did not occur, so we may safely assume 209 // that the range is [INT_MIN, INT_MAX] instead. 210 // 211 // To facilitate this trick, we maintain the invariants that: 212 // 1) hasInt32LowerBound_ == false implies lower_ == JSVAL_INT_MIN 213 // 2) hasInt32UpperBound_ == false implies upper_ == JSVAL_INT_MAX 214 // 215 // As a second and less precise range analysis, we represent the maximal 216 // exponent taken by a value. The exponent is calculated by taking the 217 // absolute value and looking at the position of the highest bit. All 218 // exponent computation have to be over-estimations of the actual result. On 219 // the Int32 this over approximation is rectified. 220 221 MOZ_INIT_OUTSIDE_CTOR int32_t lower_; 222 MOZ_INIT_OUTSIDE_CTOR int32_t upper_; 223 224 MOZ_INIT_OUTSIDE_CTOR bool hasInt32LowerBound_; 225 MOZ_INIT_OUTSIDE_CTOR bool hasInt32UpperBound_; 226 227 MOZ_INIT_OUTSIDE_CTOR FractionalPartFlag canHaveFractionalPart_ : 1; 228 MOZ_INIT_OUTSIDE_CTOR NegativeZeroFlag canBeNegativeZero_ : 1; 229 MOZ_INIT_OUTSIDE_CTOR uint16_t max_exponent_; 230 231 // Any symbolic lower or upper bound computed for this term. 232 const SymbolicBound* symbolicLower_; 233 const SymbolicBound* symbolicUpper_; 234 235 // This function simply makes several MOZ_ASSERTs to verify the internal 236 // consistency of this range. assertInvariants()237 void assertInvariants() const { 238 // Basic sanity :). 239 MOZ_ASSERT(lower_ <= upper_); 240 241 // When hasInt32LowerBound_ or hasInt32UpperBound_ are false, we set 242 // lower_ and upper_ to these specific values as it simplifies the 243 // implementation in some places. 244 MOZ_ASSERT_IF(!hasInt32LowerBound_, lower_ == JSVAL_INT_MIN); 245 MOZ_ASSERT_IF(!hasInt32UpperBound_, upper_ == JSVAL_INT_MAX); 246 247 // max_exponent_ must be one of three possible things. 248 MOZ_ASSERT(max_exponent_ <= MaxFiniteExponent || 249 max_exponent_ == IncludesInfinity || 250 max_exponent_ == IncludesInfinityAndNaN); 251 252 // Forbid the max_exponent_ field from implying better bounds for 253 // lower_/upper_ fields. We have to add 1 to the max_exponent_ when 254 // canHaveFractionalPart_ is true in order to accomodate 255 // fractional offsets. For example, 2147483647.9 is greater than 256 // INT32_MAX, so a range containing that value will have 257 // hasInt32UpperBound_ set to false, however that value also has 258 // exponent 30, which is strictly less than MaxInt32Exponent. For 259 // another example, 1.9 has an exponent of 0 but requires upper_ to be 260 // at least 2, which has exponent 1. 261 mozilla::DebugOnly<uint32_t> adjustedExponent = 262 max_exponent_ + (canHaveFractionalPart_ ? 1 : 0); 263 MOZ_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_, 264 adjustedExponent >= MaxInt32Exponent); 265 MOZ_ASSERT(adjustedExponent >= mozilla::FloorLog2(mozilla::Abs(upper_))); 266 MOZ_ASSERT(adjustedExponent >= mozilla::FloorLog2(mozilla::Abs(lower_))); 267 268 // The following are essentially static assertions, but FloorLog2 isn't 269 // trivially suitable for constexpr :(. 270 MOZ_ASSERT(mozilla::FloorLog2(JSVAL_INT_MIN) == MaxInt32Exponent); 271 MOZ_ASSERT(mozilla::FloorLog2(JSVAL_INT_MAX) == 30); 272 MOZ_ASSERT(mozilla::FloorLog2(UINT32_MAX) == MaxUInt32Exponent); 273 MOZ_ASSERT(mozilla::FloorLog2(0) == 0); 274 } 275 276 // Set the lower_ and hasInt32LowerBound_ values. setLowerInit(int64_t x)277 void setLowerInit(int64_t x) { 278 if (x > JSVAL_INT_MAX) { 279 lower_ = JSVAL_INT_MAX; 280 hasInt32LowerBound_ = true; 281 } else if (x < JSVAL_INT_MIN) { 282 lower_ = JSVAL_INT_MIN; 283 hasInt32LowerBound_ = false; 284 } else { 285 lower_ = int32_t(x); 286 hasInt32LowerBound_ = true; 287 } 288 } 289 // Set the upper_ and hasInt32UpperBound_ values. setUpperInit(int64_t x)290 void setUpperInit(int64_t x) { 291 if (x > JSVAL_INT_MAX) { 292 upper_ = JSVAL_INT_MAX; 293 hasInt32UpperBound_ = false; 294 } else if (x < JSVAL_INT_MIN) { 295 upper_ = JSVAL_INT_MIN; 296 hasInt32UpperBound_ = true; 297 } else { 298 upper_ = int32_t(x); 299 hasInt32UpperBound_ = true; 300 } 301 } 302 303 // Compute the least exponent value that would be compatible with the 304 // values of lower() and upper(). 305 // 306 // Note: 307 // exponent of JSVAL_INT_MIN == 31 308 // exponent of JSVAL_INT_MAX == 30 exponentImpliedByInt32Bounds()309 uint16_t exponentImpliedByInt32Bounds() const { 310 // The number of bits needed to encode |max| is the power of 2 plus one. 311 uint32_t max = std::max(mozilla::Abs(lower()), mozilla::Abs(upper())); 312 uint16_t result = mozilla::FloorLog2(max); 313 MOZ_ASSERT(result == 314 (max == 0 ? 0 : mozilla::ExponentComponent(double(max)))); 315 return result; 316 } 317 318 // When converting a range which contains fractional values to a range 319 // containing only integers, the old max_exponent_ value may imply a better 320 // lower and/or upper bound than was previously available, because they no 321 // longer need to be conservative about fractional offsets and the ends of 322 // the range. 323 // 324 // Given an exponent value and pointers to the lower and upper bound values, 325 // this function refines the lower and upper bound values to the tighest 326 // bound for integer values implied by the exponent. refineInt32BoundsByExponent(uint16_t e,int32_t * l,bool * lb,int32_t * h,bool * hb)327 static void refineInt32BoundsByExponent(uint16_t e, int32_t* l, bool* lb, 328 int32_t* h, bool* hb) { 329 if (e < MaxInt32Exponent) { 330 // pow(2, max_exponent_+1)-1 to compute a maximum absolute value. 331 int32_t limit = (uint32_t(1) << (e + 1)) - 1; 332 *h = std::min(*h, limit); 333 *l = std::max(*l, -limit); 334 *hb = true; 335 *lb = true; 336 } 337 } 338 339 // If the value of any of the fields implies a stronger possible value for 340 // any other field, update that field to the stronger value. The range must 341 // be completely valid before and it is guaranteed to be kept valid. optimize()342 void optimize() { 343 assertInvariants(); 344 345 if (hasInt32Bounds()) { 346 // Examine lower() and upper(), and if they imply a better exponent 347 // bound than max_exponent_, set that value as the new 348 // max_exponent_. 349 uint16_t newExponent = exponentImpliedByInt32Bounds(); 350 if (newExponent < max_exponent_) { 351 max_exponent_ = newExponent; 352 assertInvariants(); 353 } 354 355 // If we have a completely precise range, the value is an integer, 356 // since we can only represent integers. 357 if (canHaveFractionalPart_ && lower_ == upper_) { 358 canHaveFractionalPart_ = ExcludesFractionalParts; 359 assertInvariants(); 360 } 361 } 362 363 // If the range doesn't include zero, it doesn't include negative zero. 364 if (canBeNegativeZero_ && !canBeZero()) { 365 canBeNegativeZero_ = ExcludesNegativeZero; 366 assertInvariants(); 367 } 368 } 369 370 // Set the range fields to the given raw values. rawInitialize(int32_t l,bool lb,int32_t h,bool hb,FractionalPartFlag canHaveFractionalPart,NegativeZeroFlag canBeNegativeZero,uint16_t e)371 void rawInitialize(int32_t l, bool lb, int32_t h, bool hb, 372 FractionalPartFlag canHaveFractionalPart, 373 NegativeZeroFlag canBeNegativeZero, uint16_t e) { 374 lower_ = l; 375 upper_ = h; 376 hasInt32LowerBound_ = lb; 377 hasInt32UpperBound_ = hb; 378 canHaveFractionalPart_ = canHaveFractionalPart; 379 canBeNegativeZero_ = canBeNegativeZero; 380 max_exponent_ = e; 381 optimize(); 382 } 383 384 // Construct a range from the given raw values. Range(int32_t l,bool lb,int32_t h,bool hb,FractionalPartFlag canHaveFractionalPart,NegativeZeroFlag canBeNegativeZero,uint16_t e)385 Range(int32_t l, bool lb, int32_t h, bool hb, 386 FractionalPartFlag canHaveFractionalPart, 387 NegativeZeroFlag canBeNegativeZero, uint16_t e) 388 : symbolicLower_(nullptr), symbolicUpper_(nullptr) { 389 rawInitialize(l, lb, h, hb, canHaveFractionalPart, canBeNegativeZero, e); 390 } 391 392 public: Range()393 Range() : symbolicLower_(nullptr), symbolicUpper_(nullptr) { setUnknown(); } 394 Range(int64_t l,int64_t h,FractionalPartFlag canHaveFractionalPart,NegativeZeroFlag canBeNegativeZero,uint16_t e)395 Range(int64_t l, int64_t h, FractionalPartFlag canHaveFractionalPart, 396 NegativeZeroFlag canBeNegativeZero, uint16_t e) 397 : symbolicLower_(nullptr), symbolicUpper_(nullptr) { 398 set(l, h, canHaveFractionalPart, canBeNegativeZero, e); 399 } 400 Range(const Range & other)401 Range(const Range& other) 402 : lower_(other.lower_), 403 upper_(other.upper_), 404 hasInt32LowerBound_(other.hasInt32LowerBound_), 405 hasInt32UpperBound_(other.hasInt32UpperBound_), 406 canHaveFractionalPart_(other.canHaveFractionalPart_), 407 canBeNegativeZero_(other.canBeNegativeZero_), 408 max_exponent_(other.max_exponent_), 409 symbolicLower_(nullptr), 410 symbolicUpper_(nullptr) { 411 assertInvariants(); 412 } 413 414 // Construct a range from the given MDefinition. This differs from the 415 // MDefinition's range() method in that it describes the range of values 416 // *after* any bailout checks. 417 explicit Range(const MDefinition* def); 418 NewInt32Range(TempAllocator & alloc,int32_t l,int32_t h)419 static Range* NewInt32Range(TempAllocator& alloc, int32_t l, int32_t h) { 420 return new (alloc) Range(l, h, ExcludesFractionalParts, 421 ExcludesNegativeZero, MaxInt32Exponent); 422 } 423 424 // Construct an int32 range containing just i. This is just a convenience 425 // wrapper around NewInt32Range. NewInt32SingletonRange(TempAllocator & alloc,int32_t i)426 static Range* NewInt32SingletonRange(TempAllocator& alloc, int32_t i) { 427 return NewInt32Range(alloc, i, i); 428 } 429 NewUInt32Range(TempAllocator & alloc,uint32_t l,uint32_t h)430 static Range* NewUInt32Range(TempAllocator& alloc, uint32_t l, uint32_t h) { 431 // For now, just pass them to the constructor as int64_t values. 432 // They'll become unbounded if they're not in the int32_t range. 433 return new (alloc) Range(l, h, ExcludesFractionalParts, 434 ExcludesNegativeZero, MaxUInt32Exponent); 435 } 436 437 // Construct a range containing values >= l and <= h. Note that this 438 // function treats negative zero as equal to zero, as >= and <= do. If the 439 // range includes zero, it is assumed to include negative zero too. NewDoubleRange(TempAllocator & alloc,double l,double h)440 static Range* NewDoubleRange(TempAllocator& alloc, double l, double h) { 441 if (mozilla::IsNaN(l) && mozilla::IsNaN(h)) { 442 return nullptr; 443 } 444 445 Range* r = new (alloc) Range(); 446 r->setDouble(l, h); 447 return r; 448 } 449 450 // Construct the strictest possible range containing d, or null if d is NaN. 451 // This function treats negative zero as distinct from zero, since this 452 // makes the strictest possible range containin zero a range which 453 // contains one value rather than two. NewDoubleSingletonRange(TempAllocator & alloc,double d)454 static Range* NewDoubleSingletonRange(TempAllocator& alloc, double d) { 455 if (mozilla::IsNaN(d)) { 456 return nullptr; 457 } 458 459 Range* r = new (alloc) Range(); 460 r->setDoubleSingleton(d); 461 return r; 462 } 463 464 void dump(GenericPrinter& out) const; 465 void dump() const; 466 [[nodiscard]] bool update(const Range* other); 467 468 // Unlike the other operations, unionWith is an in-place 469 // modification. This is to avoid a bunch of useless extra 470 // copying when chaining together unions when handling Phi 471 // nodes. 472 void unionWith(const Range* other); 473 static Range* intersect(TempAllocator& alloc, const Range* lhs, 474 const Range* rhs, bool* emptyRange); 475 static Range* add(TempAllocator& alloc, const Range* lhs, const Range* rhs); 476 static Range* sub(TempAllocator& alloc, const Range* lhs, const Range* rhs); 477 static Range* mul(TempAllocator& alloc, const Range* lhs, const Range* rhs); 478 static Range* and_(TempAllocator& alloc, const Range* lhs, const Range* rhs); 479 static Range* or_(TempAllocator& alloc, const Range* lhs, const Range* rhs); 480 static Range* xor_(TempAllocator& alloc, const Range* lhs, const Range* rhs); 481 static Range* not_(TempAllocator& alloc, const Range* op); 482 static Range* lsh(TempAllocator& alloc, const Range* lhs, int32_t c); 483 static Range* rsh(TempAllocator& alloc, const Range* lhs, int32_t c); 484 static Range* ursh(TempAllocator& alloc, const Range* lhs, int32_t c); 485 static Range* lsh(TempAllocator& alloc, const Range* lhs, const Range* rhs); 486 static Range* rsh(TempAllocator& alloc, const Range* lhs, const Range* rhs); 487 static Range* ursh(TempAllocator& alloc, const Range* lhs, const Range* rhs); 488 static Range* abs(TempAllocator& alloc, const Range* op); 489 static Range* min(TempAllocator& alloc, const Range* lhs, const Range* rhs); 490 static Range* max(TempAllocator& alloc, const Range* lhs, const Range* rhs); 491 static Range* floor(TempAllocator& alloc, const Range* op); 492 static Range* ceil(TempAllocator& alloc, const Range* op); 493 static Range* sign(TempAllocator& alloc, const Range* op); 494 static Range* NaNToZero(TempAllocator& alloc, const Range* op); 495 static Range* toIntegerInt32(TempAllocator& alloc, const Range* op); 496 497 [[nodiscard]] static bool negativeZeroMul(const Range* lhs, const Range* rhs); 498 isUnknownInt32()499 bool isUnknownInt32() const { 500 return isInt32() && lower() == INT32_MIN && upper() == INT32_MAX; 501 } 502 isUnknown()503 bool isUnknown() const { 504 return !hasInt32LowerBound_ && !hasInt32UpperBound_ && 505 canHaveFractionalPart_ && canBeNegativeZero_ && 506 max_exponent_ == IncludesInfinityAndNaN; 507 } 508 hasInt32LowerBound()509 bool hasInt32LowerBound() const { return hasInt32LowerBound_; } hasInt32UpperBound()510 bool hasInt32UpperBound() const { return hasInt32UpperBound_; } 511 512 // Test whether the value is known to be within [INT32_MIN,INT32_MAX]. 513 // Note that this does not necessarily mean the value is an integer. hasInt32Bounds()514 bool hasInt32Bounds() const { 515 return hasInt32LowerBound() && hasInt32UpperBound(); 516 } 517 518 // Test whether the value is known to be representable as an int32. isInt32()519 bool isInt32() const { 520 return hasInt32Bounds() && !canHaveFractionalPart_ && !canBeNegativeZero_; 521 } 522 523 // Test whether the given value is known to be either 0 or 1. isBoolean()524 bool isBoolean() const { 525 return lower() >= 0 && upper() <= 1 && !canHaveFractionalPart_ && 526 !canBeNegativeZero_; 527 } 528 canHaveRoundingErrors()529 bool canHaveRoundingErrors() const { 530 return canHaveFractionalPart_ || canBeNegativeZero_ || 531 max_exponent_ >= MaxTruncatableExponent; 532 } 533 534 // Test if an integer x belongs to the range. contains(int32_t x)535 bool contains(int32_t x) const { return x >= lower_ && x <= upper_; } 536 537 // Test whether the range contains zero (of either sign). canBeZero()538 bool canBeZero() const { return contains(0); } 539 540 // Test whether the range contains NaN values. canBeNaN()541 bool canBeNaN() const { return max_exponent_ == IncludesInfinityAndNaN; } 542 543 // Test whether the range contains infinities or NaN values. canBeInfiniteOrNaN()544 bool canBeInfiniteOrNaN() const { return max_exponent_ >= IncludesInfinity; } 545 canHaveFractionalPart()546 FractionalPartFlag canHaveFractionalPart() const { 547 return canHaveFractionalPart_; 548 } 549 canBeNegativeZero()550 NegativeZeroFlag canBeNegativeZero() const { return canBeNegativeZero_; } 551 exponent()552 uint16_t exponent() const { 553 MOZ_ASSERT(!canBeInfiniteOrNaN()); 554 return max_exponent_; 555 } 556 numBits()557 uint16_t numBits() const { 558 return exponent() + 1; // 2^0 -> 1 559 } 560 561 // Return the lower bound. Asserts that the value has an int32 bound. lower()562 int32_t lower() const { 563 MOZ_ASSERT(hasInt32LowerBound()); 564 return lower_; 565 } 566 567 // Return the upper bound. Asserts that the value has an int32 bound. upper()568 int32_t upper() const { 569 MOZ_ASSERT(hasInt32UpperBound()); 570 return upper_; 571 } 572 573 // Test whether all values in this range can are finite and negative. isFiniteNegative()574 bool isFiniteNegative() const { return upper_ < 0 && !canBeInfiniteOrNaN(); } 575 576 // Test whether all values in this range can are finite and non-negative. isFiniteNonNegative()577 bool isFiniteNonNegative() const { 578 return lower_ >= 0 && !canBeInfiniteOrNaN(); 579 } 580 581 // Test whether a value in this range can possibly be a finite 582 // negative value. Note that "negative zero" is not considered negative. canBeFiniteNegative()583 bool canBeFiniteNegative() const { return lower_ < 0; } 584 585 // Test whether a value in this range can possibly be a finite 586 // non-negative value. canBeFiniteNonNegative()587 bool canBeFiniteNonNegative() const { return upper_ >= 0; } 588 589 // Test whether a value in this range can have the sign bit set (not 590 // counting NaN, where the sign bit is meaningless). canHaveSignBitSet()591 bool canHaveSignBitSet() const { 592 return !hasInt32LowerBound() || canBeFiniteNegative() || 593 canBeNegativeZero(); 594 } 595 596 // Set this range to have a lower bound not less than x. refineLower(int32_t x)597 void refineLower(int32_t x) { 598 assertInvariants(); 599 hasInt32LowerBound_ = true; 600 lower_ = std::max(lower_, x); 601 optimize(); 602 } 603 604 // Set this range to have an upper bound not greater than x. refineUpper(int32_t x)605 void refineUpper(int32_t x) { 606 assertInvariants(); 607 hasInt32UpperBound_ = true; 608 upper_ = std::min(upper_, x); 609 optimize(); 610 } 611 612 // Set this range to exclude negative zero. refineToExcludeNegativeZero()613 void refineToExcludeNegativeZero() { 614 assertInvariants(); 615 canBeNegativeZero_ = ExcludesNegativeZero; 616 optimize(); 617 } 618 setInt32(int32_t l,int32_t h)619 void setInt32(int32_t l, int32_t h) { 620 hasInt32LowerBound_ = true; 621 hasInt32UpperBound_ = true; 622 lower_ = l; 623 upper_ = h; 624 canHaveFractionalPart_ = ExcludesFractionalParts; 625 canBeNegativeZero_ = ExcludesNegativeZero; 626 max_exponent_ = exponentImpliedByInt32Bounds(); 627 assertInvariants(); 628 } 629 630 // Set this range to include values >= l and <= h. Note that this 631 // function treats negative zero as equal to zero, as >= and <= do. If the 632 // range includes zero, it is assumed to include negative zero too. 633 void setDouble(double l, double h); 634 635 // Set this range to the narrowest possible range containing d. 636 // This function treats negative zero as distinct from zero, since this 637 // makes the narrowest possible range containin zero a range which 638 // contains one value rather than two. 639 void setDoubleSingleton(double d); 640 setUnknown()641 void setUnknown() { 642 set(NoInt32LowerBound, NoInt32UpperBound, IncludesFractionalParts, 643 IncludesNegativeZero, IncludesInfinityAndNaN); 644 MOZ_ASSERT(isUnknown()); 645 } 646 set(int64_t l,int64_t h,FractionalPartFlag canHaveFractionalPart,NegativeZeroFlag canBeNegativeZero,uint16_t e)647 void set(int64_t l, int64_t h, FractionalPartFlag canHaveFractionalPart, 648 NegativeZeroFlag canBeNegativeZero, uint16_t e) { 649 max_exponent_ = e; 650 canHaveFractionalPart_ = canHaveFractionalPart; 651 canBeNegativeZero_ = canBeNegativeZero; 652 setLowerInit(l); 653 setUpperInit(h); 654 optimize(); 655 } 656 657 // Make the lower end of this range at least INT32_MIN, and make 658 // the upper end of this range at most INT32_MAX. 659 void clampToInt32(); 660 661 // If this range exceeds int32_t range, at either or both ends, change 662 // it to int32_t range. Otherwise do nothing. 663 void wrapAroundToInt32(); 664 665 // If this range exceeds [0, 32) range, at either or both ends, change 666 // it to the [0, 32) range. Otherwise do nothing. 667 void wrapAroundToShiftCount(); 668 669 // If this range exceeds [0, 1] range, at either or both ends, change 670 // it to the [0, 1] range. Otherwise do nothing. 671 void wrapAroundToBoolean(); 672 symbolicLower()673 const SymbolicBound* symbolicLower() const { return symbolicLower_; } symbolicUpper()674 const SymbolicBound* symbolicUpper() const { return symbolicUpper_; } 675 setSymbolicLower(SymbolicBound * bound)676 void setSymbolicLower(SymbolicBound* bound) { symbolicLower_ = bound; } setSymbolicUpper(SymbolicBound * bound)677 void setSymbolicUpper(SymbolicBound* bound) { symbolicUpper_ = bound; } 678 }; 679 680 } // namespace jit 681 } // namespace js 682 683 #endif /* jit_RangeAnalysis_h */ 684