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