Line data Source code
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 : namespace js {
17 : namespace jit {
18 :
19 : class MBasicBlock;
20 : class MIRGraph;
21 :
22 : // An upper bound computed on the number of backedges a loop will take.
23 : // This count only includes backedges taken while running Ion code: for OSR
24 : // loops, this will exclude iterations that executed in the interpreter or in
25 : // baseline compiled code.
26 : struct LoopIterationBound : public TempObject
27 : {
28 : // Loop for which this bound applies.
29 : MBasicBlock* header;
30 :
31 : // Test from which this bound was derived; after executing exactly 'bound'
32 : // times this test will exit the loop. Code in the loop body which this
33 : // test dominates (will include the backedge) will execute at most 'bound'
34 : // times. Other code in the loop will execute at most '1 + Max(bound, 0)'
35 : // times.
36 : MTest* test;
37 :
38 : // Symbolic bound computed for the number of backedge executions. The terms
39 : // in this bound are all loop invariant.
40 : LinearSum boundSum;
41 :
42 : // Linear sum for the number of iterations already executed, at the start
43 : // of the loop header. This will use loop invariant terms and header phis.
44 : LinearSum currentSum;
45 :
46 3 : LoopIterationBound(MBasicBlock* header, MTest* test,
47 : const LinearSum& boundSum, const LinearSum& currentSum)
48 3 : : header(header), test(test),
49 3 : boundSum(boundSum), currentSum(currentSum)
50 : {
51 3 : }
52 : };
53 :
54 : typedef Vector<LoopIterationBound*, 0, SystemAllocPolicy> LoopIterationBoundVector;
55 :
56 : // A symbolic upper or lower bound computed for a term.
57 : struct SymbolicBound : public TempObject
58 : {
59 : private:
60 6 : SymbolicBound(LoopIterationBound* loop, const LinearSum& sum)
61 6 : : loop(loop), sum(sum)
62 : {
63 6 : }
64 :
65 : public:
66 : // Any loop iteration bound from which this was derived.
67 : //
68 : // If non-nullptr, then 'sum' is only valid within the loop body, at
69 : // points dominated by the loop bound's test (see LoopIterationBound).
70 : //
71 : // If nullptr, then 'sum' is always valid.
72 : LoopIterationBound* loop;
73 :
74 : static SymbolicBound*
75 6 : New(TempAllocator& alloc, LoopIterationBound* loop, const LinearSum& sum) {
76 6 : return new(alloc) SymbolicBound(loop, sum);
77 : }
78 :
79 : // Computed symbolic bound, see above.
80 : LinearSum sum;
81 :
82 : void dump(GenericPrinter& out) const;
83 : void dump() const;
84 : };
85 :
86 8 : class RangeAnalysis
87 : {
88 : protected:
89 : bool blockDominates(MBasicBlock* b, MBasicBlock* b2);
90 : void replaceDominatedUsesWith(MDefinition* orig, MDefinition* dom,
91 : MBasicBlock* block);
92 :
93 : protected:
94 : MIRGenerator* mir;
95 : MIRGraph& graph_;
96 : Vector<MBinaryBitwiseInstruction*, 16, SystemAllocPolicy> bitops;
97 :
98 : TempAllocator& alloc() const;
99 :
100 : public:
101 8 : RangeAnalysis(MIRGenerator* mir, MIRGraph& graph) :
102 8 : mir(mir), graph_(graph) {}
103 : MOZ_MUST_USE bool addBetaNodes();
104 : MOZ_MUST_USE bool analyze();
105 : MOZ_MUST_USE bool addRangeAssertions();
106 : MOZ_MUST_USE bool removeBetaNodes();
107 : MOZ_MUST_USE bool prepareForUCE(bool* shouldRemoveDeadCode);
108 : MOZ_MUST_USE bool tryRemovingGuards();
109 : MOZ_MUST_USE bool truncate();
110 : MOZ_MUST_USE bool removeUnnecessaryBitops();
111 :
112 : // Any iteration bounds discovered for loops in the graph.
113 : LoopIterationBoundVector loopIterationBounds;
114 :
115 : private:
116 : MOZ_MUST_USE bool analyzeLoop(MBasicBlock* header);
117 : LoopIterationBound* analyzeLoopIterationCount(MBasicBlock* header,
118 : MTest* test, BranchDirection direction);
119 : void analyzeLoopPhi(MBasicBlock* header, LoopIterationBound* loopBound, MPhi* phi);
120 : MOZ_MUST_USE 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.
214 835 : void assertInvariants() const {
215 : // Basic sanity :).
216 835 : 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 835 : MOZ_ASSERT_IF(!hasInt32LowerBound_, lower_ == JSVAL_INT_MIN);
222 835 : MOZ_ASSERT_IF(!hasInt32UpperBound_, upper_ == JSVAL_INT_MAX);
223 :
224 : // max_exponent_ must be one of three possible things.
225 835 : 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 2505 : mozilla::DebugOnly<uint32_t> adjustedExponent = max_exponent_ +
239 2505 : (canHaveFractionalPart_ ? 1 : 0);
240 835 : MOZ_ASSERT_IF(!hasInt32LowerBound_ || !hasInt32UpperBound_,
241 : adjustedExponent >= MaxInt32Exponent);
242 835 : MOZ_ASSERT(adjustedExponent >= mozilla::FloorLog2(mozilla::Abs(upper_)));
243 835 : 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 835 : MOZ_ASSERT(mozilla::FloorLog2(JSVAL_INT_MIN) == MaxInt32Exponent);
248 835 : MOZ_ASSERT(mozilla::FloorLog2(JSVAL_INT_MAX) == 30);
249 835 : MOZ_ASSERT(mozilla::FloorLog2(UINT32_MAX) == MaxUInt32Exponent);
250 835 : MOZ_ASSERT(mozilla::FloorLog2(0) == 0);
251 835 : }
252 :
253 : // Set the lower_ and hasInt32LowerBound_ values.
254 195 : void setLowerInit(int64_t x) {
255 195 : if (x > JSVAL_INT_MAX) {
256 0 : lower_ = JSVAL_INT_MAX;
257 0 : hasInt32LowerBound_ = true;
258 195 : } else if (x < JSVAL_INT_MIN) {
259 117 : lower_ = JSVAL_INT_MIN;
260 117 : hasInt32LowerBound_ = false;
261 : } else {
262 78 : lower_ = int32_t(x);
263 78 : hasInt32LowerBound_ = true;
264 : }
265 195 : }
266 : // Set the upper_ and hasInt32UpperBound_ values.
267 195 : void setUpperInit(int64_t x) {
268 195 : if (x > JSVAL_INT_MAX) {
269 119 : upper_ = JSVAL_INT_MAX;
270 119 : hasInt32UpperBound_ = false;
271 76 : } else if (x < JSVAL_INT_MIN) {
272 0 : upper_ = JSVAL_INT_MIN;
273 0 : hasInt32UpperBound_ = true;
274 : } else {
275 76 : upper_ = int32_t(x);
276 76 : hasInt32UpperBound_ = true;
277 : }
278 195 : }
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
286 254 : uint16_t exponentImpliedByInt32Bounds() const {
287 : // The number of bits needed to encode |max| is the power of 2 plus one.
288 254 : uint32_t max = Max(mozilla::Abs(lower()), mozilla::Abs(upper()));
289 254 : uint16_t result = mozilla::FloorLog2(max);
290 254 : MOZ_ASSERT(result == (max == 0 ? 0 : mozilla::ExponentComponent(double(max))));
291 254 : 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.
303 5 : static void refineInt32BoundsByExponent(uint16_t e,
304 : int32_t* l, bool* lb,
305 : int32_t* h, bool* hb)
306 : {
307 5 : if (e < MaxInt32Exponent) {
308 : // pow(2, max_exponent_+1)-1 to compute a maximum absolute value.
309 5 : int32_t limit = (uint32_t(1) << (e + 1)) - 1;
310 5 : *h = Min(*h, limit);
311 5 : *l = Max(*l, -limit);
312 5 : *hb = true;
313 5 : *lb = true;
314 : }
315 5 : }
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.
320 335 : void optimize() {
321 335 : assertInvariants();
322 :
323 335 : 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 211 : uint16_t newExponent = exponentImpliedByInt32Bounds();
328 211 : if (newExponent < max_exponent_) {
329 75 : max_exponent_ = newExponent;
330 75 : assertInvariants();
331 : }
332 :
333 : // If we have a completely precise range, the value is an integer,
334 : // since we can only represent integers.
335 211 : if (canHaveFractionalPart_ && lower_ == upper_) {
336 78 : canHaveFractionalPart_ = ExcludesFractionalParts;
337 78 : assertInvariants();
338 : }
339 : }
340 :
341 : // If the range doesn't include zero, it doesn't include negative zero.
342 335 : if (canBeNegativeZero_ && !canBeZero()) {
343 0 : canBeNegativeZero_ = ExcludesNegativeZero;
344 0 : assertInvariants();
345 : }
346 335 : }
347 :
348 : // Set the range fields to the given raw values.
349 57 : void rawInitialize(int32_t l, bool lb, int32_t h, bool hb,
350 : FractionalPartFlag canHaveFractionalPart,
351 : NegativeZeroFlag canBeNegativeZero,
352 : uint16_t e)
353 : {
354 57 : lower_ = l;
355 57 : upper_ = h;
356 57 : hasInt32LowerBound_ = lb;
357 57 : hasInt32UpperBound_ = hb;
358 57 : canHaveFractionalPart_ = canHaveFractionalPart;
359 57 : canBeNegativeZero_ = canBeNegativeZero;
360 57 : max_exponent_ = e;
361 57 : optimize();
362 57 : }
363 :
364 : // Construct a range from the given raw values.
365 55 : Range(int32_t l, bool lb, int32_t h, bool hb,
366 : FractionalPartFlag canHaveFractionalPart,
367 : NegativeZeroFlag canBeNegativeZero,
368 : uint16_t e)
369 55 : : symbolicLower_(nullptr),
370 55 : symbolicUpper_(nullptr)
371 : {
372 55 : rawInitialize(l, lb, h, hb, canHaveFractionalPart, canBeNegativeZero, e);
373 55 : }
374 :
375 : public:
376 111 : Range()
377 111 : : symbolicLower_(nullptr),
378 111 : symbolicUpper_(nullptr)
379 : {
380 111 : setUnknown();
381 111 : }
382 :
383 78 : Range(int64_t l, int64_t h,
384 : FractionalPartFlag canHaveFractionalPart,
385 : NegativeZeroFlag canBeNegativeZero,
386 : uint16_t e)
387 78 : : symbolicLower_(nullptr),
388 78 : symbolicUpper_(nullptr)
389 : {
390 78 : set(l, h, canHaveFractionalPart, canBeNegativeZero, e);
391 78 : }
392 :
393 42 : Range(const Range& other)
394 84 : : lower_(other.lower_),
395 42 : upper_(other.upper_),
396 42 : hasInt32LowerBound_(other.hasInt32LowerBound_),
397 42 : hasInt32UpperBound_(other.hasInt32UpperBound_),
398 42 : canHaveFractionalPart_(other.canHaveFractionalPart_),
399 42 : canBeNegativeZero_(other.canBeNegativeZero_),
400 42 : max_exponent_(other.max_exponent_),
401 : symbolicLower_(nullptr),
402 336 : symbolicUpper_(nullptr)
403 : {
404 42 : assertInvariants();
405 42 : }
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 :
412 56 : static Range* NewInt32Range(TempAllocator& alloc, int32_t l, int32_t h) {
413 56 : 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.
418 : static Range* NewInt32SingletonRange(TempAllocator& alloc, int32_t i) {
419 : return NewInt32Range(alloc, i, i);
420 : }
421 :
422 14 : 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 14 : 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.
431 0 : static Range* NewDoubleRange(TempAllocator& alloc, double l, double h) {
432 0 : if (mozilla::IsNaN(l) && mozilla::IsNaN(h))
433 0 : return nullptr;
434 :
435 0 : Range* r = new(alloc) Range();
436 0 : r->setDouble(l, h);
437 0 : 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.
444 49 : static Range* NewDoubleSingletonRange(TempAllocator& alloc, double d) {
445 49 : if (mozilla::IsNaN(d))
446 0 : return nullptr;
447 :
448 49 : Range* r = new(alloc) Range();
449 49 : r->setDoubleSingleton(d);
450 49 : return r;
451 : }
452 :
453 : void dump(GenericPrinter& out) const;
454 : void dump() const;
455 : MOZ_MUST_USE 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 : static Range* NaNToZero(TempAllocator& alloc, const Range* op);
484 :
485 : static MOZ_MUST_USE bool negativeZeroMul(const Range* lhs, const Range* rhs);
486 :
487 0 : bool isUnknownInt32() const {
488 0 : return isInt32() && lower() == INT32_MIN && upper() == INT32_MAX;
489 : }
490 :
491 117 : bool isUnknown() const {
492 234 : return !hasInt32LowerBound_ &&
493 234 : !hasInt32UpperBound_ &&
494 234 : canHaveFractionalPart_ &&
495 351 : canBeNegativeZero_ &&
496 234 : max_exponent_ == IncludesInfinityAndNaN;
497 : }
498 :
499 1115 : bool hasInt32LowerBound() const {
500 1115 : return hasInt32LowerBound_;
501 : }
502 1195 : bool hasInt32UpperBound() const {
503 1195 : return hasInt32UpperBound_;
504 : }
505 :
506 : // Test whether the value is known to be within [INT32_MIN,INT32_MAX].
507 : // Note that this does not necessarily mean the value is an integer.
508 831 : bool hasInt32Bounds() const {
509 831 : return hasInt32LowerBound() && hasInt32UpperBound();
510 : }
511 :
512 : // Test whether the value is known to be representable as an int32.
513 313 : bool isInt32() const {
514 622 : return hasInt32Bounds() &&
515 622 : !canHaveFractionalPart_ &&
516 622 : !canBeNegativeZero_;
517 : }
518 :
519 : // Test whether the given value is known to be either 0 or 1.
520 0 : bool isBoolean() const {
521 0 : return lower() >= 0 && upper() <= 1 &&
522 0 : !canHaveFractionalPart_ &&
523 0 : !canBeNegativeZero_;
524 : }
525 :
526 141 : bool canHaveRoundingErrors() const {
527 140 : return canHaveFractionalPart_ ||
528 281 : canBeNegativeZero_ ||
529 281 : max_exponent_ >= MaxTruncatableExponent;
530 : }
531 :
532 : // Test if an integer x belongs to the range.
533 125 : bool contains(int32_t x) const {
534 125 : return x >= lower_ && x <= upper_;
535 : }
536 :
537 : // Test whether the range contains zero (of either sign).
538 125 : bool canBeZero() const {
539 125 : return contains(0);
540 : }
541 :
542 : // Test whether the range contains NaN values.
543 104 : bool canBeNaN() const {
544 104 : return max_exponent_ == IncludesInfinityAndNaN;
545 : }
546 :
547 : // Test whether the range contains infinities or NaN values.
548 8 : bool canBeInfiniteOrNaN() const {
549 8 : return max_exponent_ >= IncludesInfinity;
550 : }
551 :
552 328 : FractionalPartFlag canHaveFractionalPart() const {
553 328 : return canHaveFractionalPart_;
554 : }
555 :
556 9 : NegativeZeroFlag canBeNegativeZero() const {
557 9 : return canBeNegativeZero_;
558 : }
559 :
560 0 : uint16_t exponent() const {
561 0 : MOZ_ASSERT(!canBeInfiniteOrNaN());
562 0 : return max_exponent_;
563 : }
564 :
565 0 : uint16_t numBits() const {
566 0 : return exponent() + 1; // 2^0 -> 1
567 : }
568 :
569 : // Return the lower bound. Asserts that the value has an int32 bound.
570 260 : int32_t lower() const {
571 260 : MOZ_ASSERT(hasInt32LowerBound());
572 260 : return lower_;
573 : }
574 :
575 : // Return the upper bound. Asserts that the value has an int32 bound.
576 256 : int32_t upper() const {
577 256 : MOZ_ASSERT(hasInt32UpperBound());
578 256 : return upper_;
579 : }
580 :
581 : // Test whether all values in this range can are finite and negative.
582 0 : bool isFiniteNegative() const {
583 0 : return upper_ < 0 && !canBeInfiniteOrNaN();
584 : }
585 :
586 : // Test whether all values in this range can are finite and non-negative.
587 0 : bool isFiniteNonNegative() const {
588 0 : return lower_ >= 0 && !canBeInfiniteOrNaN();
589 : }
590 :
591 : // Test whether a value in this range can possibly be a finite
592 : // negative value. Note that "negative zero" is not considered negative.
593 0 : bool canBeFiniteNegative() const {
594 0 : return lower_ < 0;
595 : }
596 :
597 : // Test whether a value in this range can possibly be a finite
598 : // non-negative value.
599 0 : bool canBeFiniteNonNegative() const {
600 0 : return upper_ >= 0;
601 : }
602 :
603 : // Test whether a value in this range can have the sign bit set (not
604 : // counting NaN, where the sign bit is meaningless).
605 0 : bool canHaveSignBitSet() const {
606 0 : return !hasInt32LowerBound() || canBeFiniteNegative() || canBeNegativeZero();
607 : }
608 :
609 : // Set this range to have a lower bound not less than x.
610 0 : void refineLower(int32_t x) {
611 0 : assertInvariants();
612 0 : hasInt32LowerBound_ = true;
613 0 : lower_ = Max(lower_, x);
614 0 : optimize();
615 0 : }
616 :
617 : // Set this range to have an upper bound not greater than x.
618 0 : void refineUpper(int32_t x) {
619 0 : assertInvariants();
620 0 : hasInt32UpperBound_ = true;
621 0 : upper_ = Min(upper_, x);
622 0 : optimize();
623 0 : }
624 :
625 : // Set this range to exclude negative zero.
626 1 : void refineToExcludeNegativeZero() {
627 1 : assertInvariants();
628 1 : canBeNegativeZero_ = ExcludesNegativeZero;
629 1 : optimize();
630 1 : }
631 :
632 43 : void setInt32(int32_t l, int32_t h) {
633 43 : hasInt32LowerBound_ = true;
634 43 : hasInt32UpperBound_ = true;
635 43 : lower_ = l;
636 43 : upper_ = h;
637 43 : canHaveFractionalPart_ = ExcludesFractionalParts;
638 43 : canBeNegativeZero_ = ExcludesNegativeZero;
639 43 : max_exponent_ = exponentImpliedByInt32Bounds();
640 43 : assertInvariants();
641 43 : }
642 :
643 : // Set this range to include values >= l and <= h. Note that this
644 : // function treats negative zero as equal to zero, as >= and <= do. If the
645 : // range includes zero, it is assumed to include negative zero too.
646 : void setDouble(double l, double h);
647 :
648 : // Set this range to the narrowest possible range containing d.
649 : // This function treats negative zero as distinct from zero, since this
650 : // makes the narrowest possible range containin zero a range which
651 : // contains one value rather than two.
652 : void setDoubleSingleton(double d);
653 :
654 117 : void setUnknown() {
655 : set(NoInt32LowerBound, NoInt32UpperBound,
656 : IncludesFractionalParts,
657 : IncludesNegativeZero,
658 117 : IncludesInfinityAndNaN);
659 117 : MOZ_ASSERT(isUnknown());
660 117 : }
661 :
662 195 : void set(int64_t l, int64_t h,
663 : FractionalPartFlag canHaveFractionalPart,
664 : NegativeZeroFlag canBeNegativeZero,
665 : uint16_t e)
666 : {
667 195 : max_exponent_ = e;
668 195 : canHaveFractionalPart_ = canHaveFractionalPart;
669 195 : canBeNegativeZero_ = canBeNegativeZero;
670 195 : setLowerInit(l);
671 195 : setUpperInit(h);
672 195 : optimize();
673 195 : }
674 :
675 : // Make the lower end of this range at least INT32_MIN, and make
676 : // the upper end of this range at most INT32_MAX.
677 : void clampToInt32();
678 :
679 : // If this range exceeds int32_t range, at either or both ends, change
680 : // it to int32_t range. Otherwise do nothing.
681 : void wrapAroundToInt32();
682 :
683 : // If this range exceeds [0, 32) range, at either or both ends, change
684 : // it to the [0, 32) range. Otherwise do nothing.
685 : void wrapAroundToShiftCount();
686 :
687 : // If this range exceeds [0, 1] range, at either or both ends, change
688 : // it to the [0, 1] range. Otherwise do nothing.
689 : void wrapAroundToBoolean();
690 :
691 2 : const SymbolicBound* symbolicLower() const {
692 2 : return symbolicLower_;
693 : }
694 2 : const SymbolicBound* symbolicUpper() const {
695 2 : return symbolicUpper_;
696 : }
697 :
698 3 : void setSymbolicLower(SymbolicBound* bound) {
699 3 : symbolicLower_ = bound;
700 3 : }
701 3 : void setSymbolicUpper(SymbolicBound* bound) {
702 3 : symbolicUpper_ = bound;
703 3 : }
704 : };
705 :
706 : } // namespace jit
707 : } // namespace js
708 :
709 : #endif /* jit_RangeAnalysis_h */
|
