1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Represent a range of possible values that may occur when the program is run
11 // for an integral value. This keeps track of a lower and upper bound for the
12 // constant, which MAY wrap around the end of the numeric range. To do this, it
13 // keeps track of a [lower, upper) bound, which specifies an interval just like
14 // STL iterators. When used with boolean values, the following are important
15 // ranges (other integral ranges use min/max values for special range values):
16 //
17 // [F, F) = {} = Empty set
18 // [T, F) = {T}
19 // [F, T) = {F}
20 // [T, T) = {F, T} = Full set
21 //
22 //===----------------------------------------------------------------------===//
23
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/InstrTypes.h"
26 #include "llvm/IR/Operator.h"
27 #include "llvm/IR/ConstantRange.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 using namespace llvm;
31
32 /// Initialize a full (the default) or empty set for the specified type.
33 ///
ConstantRange(uint32_t BitWidth,bool Full)34 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
35 if (Full)
36 Lower = Upper = APInt::getMaxValue(BitWidth);
37 else
38 Lower = Upper = APInt::getMinValue(BitWidth);
39 }
40
41 /// Initialize a range to hold the single specified value.
42 ///
ConstantRange(APIntMoveTy V)43 ConstantRange::ConstantRange(APIntMoveTy V)
44 : Lower(std::move(V)), Upper(Lower + 1) {}
45
ConstantRange(APIntMoveTy L,APIntMoveTy U)46 ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U)
47 : Lower(std::move(L)), Upper(std::move(U)) {
48 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
49 "ConstantRange with unequal bit widths");
50 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
51 "Lower == Upper, but they aren't min or max value!");
52 }
53
makeAllowedICmpRegion(CmpInst::Predicate Pred,const ConstantRange & CR)54 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
55 const ConstantRange &CR) {
56 if (CR.isEmptySet())
57 return CR;
58
59 uint32_t W = CR.getBitWidth();
60 switch (Pred) {
61 default:
62 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
63 case CmpInst::ICMP_EQ:
64 return CR;
65 case CmpInst::ICMP_NE:
66 if (CR.isSingleElement())
67 return ConstantRange(CR.getUpper(), CR.getLower());
68 return ConstantRange(W);
69 case CmpInst::ICMP_ULT: {
70 APInt UMax(CR.getUnsignedMax());
71 if (UMax.isMinValue())
72 return ConstantRange(W, /* empty */ false);
73 return ConstantRange(APInt::getMinValue(W), UMax);
74 }
75 case CmpInst::ICMP_SLT: {
76 APInt SMax(CR.getSignedMax());
77 if (SMax.isMinSignedValue())
78 return ConstantRange(W, /* empty */ false);
79 return ConstantRange(APInt::getSignedMinValue(W), SMax);
80 }
81 case CmpInst::ICMP_ULE: {
82 APInt UMax(CR.getUnsignedMax());
83 if (UMax.isMaxValue())
84 return ConstantRange(W);
85 return ConstantRange(APInt::getMinValue(W), UMax + 1);
86 }
87 case CmpInst::ICMP_SLE: {
88 APInt SMax(CR.getSignedMax());
89 if (SMax.isMaxSignedValue())
90 return ConstantRange(W);
91 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
92 }
93 case CmpInst::ICMP_UGT: {
94 APInt UMin(CR.getUnsignedMin());
95 if (UMin.isMaxValue())
96 return ConstantRange(W, /* empty */ false);
97 return ConstantRange(UMin + 1, APInt::getNullValue(W));
98 }
99 case CmpInst::ICMP_SGT: {
100 APInt SMin(CR.getSignedMin());
101 if (SMin.isMaxSignedValue())
102 return ConstantRange(W, /* empty */ false);
103 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
104 }
105 case CmpInst::ICMP_UGE: {
106 APInt UMin(CR.getUnsignedMin());
107 if (UMin.isMinValue())
108 return ConstantRange(W);
109 return ConstantRange(UMin, APInt::getNullValue(W));
110 }
111 case CmpInst::ICMP_SGE: {
112 APInt SMin(CR.getSignedMin());
113 if (SMin.isMinSignedValue())
114 return ConstantRange(W);
115 return ConstantRange(SMin, APInt::getSignedMinValue(W));
116 }
117 }
118 }
119
makeSatisfyingICmpRegion(CmpInst::Predicate Pred,const ConstantRange & CR)120 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
121 const ConstantRange &CR) {
122 // Follows from De-Morgan's laws:
123 //
124 // ~(~A union ~B) == A intersect B.
125 //
126 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
127 .inverse();
128 }
129
makeExactICmpRegion(CmpInst::Predicate Pred,const APInt & C)130 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
131 const APInt &C) {
132 // Computes the exact range that is equal to both the constant ranges returned
133 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
134 // when RHS is a singleton such as an APInt and so the assert is valid.
135 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
136 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
137 //
138 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
139 return makeAllowedICmpRegion(Pred, C);
140 }
141
getEquivalentICmp(CmpInst::Predicate & Pred,APInt & RHS) const142 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
143 APInt &RHS) const {
144 bool Success = false;
145
146 if (isFullSet() || isEmptySet()) {
147 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
148 RHS = APInt(getBitWidth(), 0);
149 Success = true;
150 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
151 Pred =
152 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
153 RHS = getUpper();
154 Success = true;
155 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
156 Pred =
157 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
158 RHS = getLower();
159 Success = true;
160 }
161
162 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
163 "Bad result!");
164
165 return Success;
166 }
167
168 ConstantRange
makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,const ConstantRange & Other,unsigned NoWrapKind)169 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
170 const ConstantRange &Other,
171 unsigned NoWrapKind) {
172 typedef OverflowingBinaryOperator OBO;
173
174 // Computes the intersection of CR0 and CR1. It is different from
175 // intersectWith in that the ConstantRange returned will only contain elements
176 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
177 // not, of both X and Y).
178 auto SubsetIntersect =
179 [](const ConstantRange &CR0, const ConstantRange &CR1) {
180 return CR0.inverse().unionWith(CR1.inverse()).inverse();
181 };
182
183 assert(BinOp >= Instruction::BinaryOpsBegin &&
184 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
185
186 assert((NoWrapKind == OBO::NoSignedWrap ||
187 NoWrapKind == OBO::NoUnsignedWrap ||
188 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
189 "NoWrapKind invalid!");
190
191 unsigned BitWidth = Other.getBitWidth();
192 if (BinOp != Instruction::Add)
193 // Conservative answer: empty set
194 return ConstantRange(BitWidth, false);
195
196 if (auto *C = Other.getSingleElement())
197 if (C->isMinValue())
198 // Full set: nothing signed / unsigned wraps when added to 0.
199 return ConstantRange(BitWidth);
200
201 ConstantRange Result(BitWidth);
202
203 if (NoWrapKind & OBO::NoUnsignedWrap)
204 Result =
205 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
206 -Other.getUnsignedMax()));
207
208 if (NoWrapKind & OBO::NoSignedWrap) {
209 APInt SignedMin = Other.getSignedMin();
210 APInt SignedMax = Other.getSignedMax();
211
212 if (SignedMax.isStrictlyPositive())
213 Result = SubsetIntersect(
214 Result,
215 ConstantRange(APInt::getSignedMinValue(BitWidth),
216 APInt::getSignedMinValue(BitWidth) - SignedMax));
217
218 if (SignedMin.isNegative())
219 Result = SubsetIntersect(
220 Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
221 APInt::getSignedMinValue(BitWidth)));
222 }
223
224 return Result;
225 }
226
227 /// isFullSet - Return true if this set contains all of the elements possible
228 /// for this data-type
isFullSet() const229 bool ConstantRange::isFullSet() const {
230 return Lower == Upper && Lower.isMaxValue();
231 }
232
233 /// isEmptySet - Return true if this set contains no members.
234 ///
isEmptySet() const235 bool ConstantRange::isEmptySet() const {
236 return Lower == Upper && Lower.isMinValue();
237 }
238
239 /// isWrappedSet - Return true if this set wraps around the top of the range,
240 /// for example: [100, 8)
241 ///
isWrappedSet() const242 bool ConstantRange::isWrappedSet() const {
243 return Lower.ugt(Upper);
244 }
245
246 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
247 /// its bitwidth, for example: i8 [120, 140).
248 ///
isSignWrappedSet() const249 bool ConstantRange::isSignWrappedSet() const {
250 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
251 contains(APInt::getSignedMinValue(getBitWidth()));
252 }
253
254 /// getSetSize - Return the number of elements in this set.
255 ///
getSetSize() const256 APInt ConstantRange::getSetSize() const {
257 if (isFullSet()) {
258 APInt Size(getBitWidth()+1, 0);
259 Size.setBit(getBitWidth());
260 return Size;
261 }
262
263 // This is also correct for wrapped sets.
264 return (Upper - Lower).zext(getBitWidth()+1);
265 }
266
267 /// getUnsignedMax - Return the largest unsigned value contained in the
268 /// ConstantRange.
269 ///
getUnsignedMax() const270 APInt ConstantRange::getUnsignedMax() const {
271 if (isFullSet() || isWrappedSet())
272 return APInt::getMaxValue(getBitWidth());
273 return getUpper() - 1;
274 }
275
276 /// getUnsignedMin - Return the smallest unsigned value contained in the
277 /// ConstantRange.
278 ///
getUnsignedMin() const279 APInt ConstantRange::getUnsignedMin() const {
280 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
281 return APInt::getMinValue(getBitWidth());
282 return getLower();
283 }
284
285 /// getSignedMax - Return the largest signed value contained in the
286 /// ConstantRange.
287 ///
getSignedMax() const288 APInt ConstantRange::getSignedMax() const {
289 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
290 if (!isWrappedSet()) {
291 if (getLower().sle(getUpper() - 1))
292 return getUpper() - 1;
293 return SignedMax;
294 }
295 if (getLower().isNegative() == getUpper().isNegative())
296 return SignedMax;
297 return getUpper() - 1;
298 }
299
300 /// getSignedMin - Return the smallest signed value contained in the
301 /// ConstantRange.
302 ///
getSignedMin() const303 APInt ConstantRange::getSignedMin() const {
304 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
305 if (!isWrappedSet()) {
306 if (getLower().sle(getUpper() - 1))
307 return getLower();
308 return SignedMin;
309 }
310 if ((getUpper() - 1).slt(getLower())) {
311 if (getUpper() != SignedMin)
312 return SignedMin;
313 }
314 return getLower();
315 }
316
317 /// contains - Return true if the specified value is in the set.
318 ///
contains(const APInt & V) const319 bool ConstantRange::contains(const APInt &V) const {
320 if (Lower == Upper)
321 return isFullSet();
322
323 if (!isWrappedSet())
324 return Lower.ule(V) && V.ult(Upper);
325 return Lower.ule(V) || V.ult(Upper);
326 }
327
328 /// contains - Return true if the argument is a subset of this range.
329 /// Two equal sets contain each other. The empty set contained by all other
330 /// sets.
331 ///
contains(const ConstantRange & Other) const332 bool ConstantRange::contains(const ConstantRange &Other) const {
333 if (isFullSet() || Other.isEmptySet()) return true;
334 if (isEmptySet() || Other.isFullSet()) return false;
335
336 if (!isWrappedSet()) {
337 if (Other.isWrappedSet())
338 return false;
339
340 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
341 }
342
343 if (!Other.isWrappedSet())
344 return Other.getUpper().ule(Upper) ||
345 Lower.ule(Other.getLower());
346
347 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
348 }
349
350 /// subtract - Subtract the specified constant from the endpoints of this
351 /// constant range.
subtract(const APInt & Val) const352 ConstantRange ConstantRange::subtract(const APInt &Val) const {
353 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
354 // If the set is empty or full, don't modify the endpoints.
355 if (Lower == Upper)
356 return *this;
357 return ConstantRange(Lower - Val, Upper - Val);
358 }
359
360 /// \brief Subtract the specified range from this range (aka relative complement
361 /// of the sets).
difference(const ConstantRange & CR) const362 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
363 return intersectWith(CR.inverse());
364 }
365
366 /// intersectWith - Return the range that results from the intersection of this
367 /// range with another range. The resultant range is guaranteed to include all
368 /// elements contained in both input ranges, and to have the smallest possible
369 /// set size that does so. Because there may be two intersections with the
370 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
intersectWith(const ConstantRange & CR) const371 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
372 assert(getBitWidth() == CR.getBitWidth() &&
373 "ConstantRange types don't agree!");
374
375 // Handle common cases.
376 if ( isEmptySet() || CR.isFullSet()) return *this;
377 if (CR.isEmptySet() || isFullSet()) return CR;
378
379 if (!isWrappedSet() && CR.isWrappedSet())
380 return CR.intersectWith(*this);
381
382 if (!isWrappedSet() && !CR.isWrappedSet()) {
383 if (Lower.ult(CR.Lower)) {
384 if (Upper.ule(CR.Lower))
385 return ConstantRange(getBitWidth(), false);
386
387 if (Upper.ult(CR.Upper))
388 return ConstantRange(CR.Lower, Upper);
389
390 return CR;
391 }
392 if (Upper.ult(CR.Upper))
393 return *this;
394
395 if (Lower.ult(CR.Upper))
396 return ConstantRange(Lower, CR.Upper);
397
398 return ConstantRange(getBitWidth(), false);
399 }
400
401 if (isWrappedSet() && !CR.isWrappedSet()) {
402 if (CR.Lower.ult(Upper)) {
403 if (CR.Upper.ult(Upper))
404 return CR;
405
406 if (CR.Upper.ule(Lower))
407 return ConstantRange(CR.Lower, Upper);
408
409 if (getSetSize().ult(CR.getSetSize()))
410 return *this;
411 return CR;
412 }
413 if (CR.Lower.ult(Lower)) {
414 if (CR.Upper.ule(Lower))
415 return ConstantRange(getBitWidth(), false);
416
417 return ConstantRange(Lower, CR.Upper);
418 }
419 return CR;
420 }
421
422 if (CR.Upper.ult(Upper)) {
423 if (CR.Lower.ult(Upper)) {
424 if (getSetSize().ult(CR.getSetSize()))
425 return *this;
426 return CR;
427 }
428
429 if (CR.Lower.ult(Lower))
430 return ConstantRange(Lower, CR.Upper);
431
432 return CR;
433 }
434 if (CR.Upper.ule(Lower)) {
435 if (CR.Lower.ult(Lower))
436 return *this;
437
438 return ConstantRange(CR.Lower, Upper);
439 }
440 if (getSetSize().ult(CR.getSetSize()))
441 return *this;
442 return CR;
443 }
444
445
446 /// unionWith - Return the range that results from the union of this range with
447 /// another range. The resultant range is guaranteed to include the elements of
448 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
449 /// [3, 15), which includes 9, 10, and 11, which were not included in either
450 /// set before.
451 ///
unionWith(const ConstantRange & CR) const452 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
453 assert(getBitWidth() == CR.getBitWidth() &&
454 "ConstantRange types don't agree!");
455
456 if ( isFullSet() || CR.isEmptySet()) return *this;
457 if (CR.isFullSet() || isEmptySet()) return CR;
458
459 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
460
461 if (!isWrappedSet() && !CR.isWrappedSet()) {
462 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
463 // If the two ranges are disjoint, find the smaller gap and bridge it.
464 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
465 if (d1.ult(d2))
466 return ConstantRange(Lower, CR.Upper);
467 return ConstantRange(CR.Lower, Upper);
468 }
469
470 APInt L = Lower, U = Upper;
471 if (CR.Lower.ult(L))
472 L = CR.Lower;
473 if ((CR.Upper - 1).ugt(U - 1))
474 U = CR.Upper;
475
476 if (L == 0 && U == 0)
477 return ConstantRange(getBitWidth());
478
479 return ConstantRange(L, U);
480 }
481
482 if (!CR.isWrappedSet()) {
483 // ------U L----- and ------U L----- : this
484 // L--U L--U : CR
485 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
486 return *this;
487
488 // ------U L----- : this
489 // L---------U : CR
490 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
491 return ConstantRange(getBitWidth());
492
493 // ----U L---- : this
494 // L---U : CR
495 // <d1> <d2>
496 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
497 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
498 if (d1.ult(d2))
499 return ConstantRange(Lower, CR.Upper);
500 return ConstantRange(CR.Lower, Upper);
501 }
502
503 // ----U L----- : this
504 // L----U : CR
505 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
506 return ConstantRange(CR.Lower, Upper);
507
508 // ------U L---- : this
509 // L-----U : CR
510 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
511 "ConstantRange::unionWith missed a case with one range wrapped");
512 return ConstantRange(Lower, CR.Upper);
513 }
514
515 // ------U L---- and ------U L---- : this
516 // -U L----------- and ------------U L : CR
517 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
518 return ConstantRange(getBitWidth());
519
520 APInt L = Lower, U = Upper;
521 if (CR.Upper.ugt(U))
522 U = CR.Upper;
523 if (CR.Lower.ult(L))
524 L = CR.Lower;
525
526 return ConstantRange(L, U);
527 }
528
529 /// zeroExtend - Return a new range in the specified integer type, which must
530 /// be strictly larger than the current type. The returned range will
531 /// correspond to the possible range of values as if the source range had been
532 /// zero extended.
zeroExtend(uint32_t DstTySize) const533 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
534 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
535
536 unsigned SrcTySize = getBitWidth();
537 assert(SrcTySize < DstTySize && "Not a value extension");
538 if (isFullSet() || isWrappedSet()) {
539 // Change into [0, 1 << src bit width)
540 APInt LowerExt(DstTySize, 0);
541 if (!Upper) // special case: [X, 0) -- not really wrapping around
542 LowerExt = Lower.zext(DstTySize);
543 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
544 }
545
546 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
547 }
548
549 /// signExtend - Return a new range in the specified integer type, which must
550 /// be strictly larger than the current type. The returned range will
551 /// correspond to the possible range of values as if the source range had been
552 /// sign extended.
signExtend(uint32_t DstTySize) const553 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
554 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
555
556 unsigned SrcTySize = getBitWidth();
557 assert(SrcTySize < DstTySize && "Not a value extension");
558
559 // special case: [X, INT_MIN) -- not really wrapping around
560 if (Upper.isMinSignedValue())
561 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
562
563 if (isFullSet() || isSignWrappedSet()) {
564 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
565 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
566 }
567
568 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
569 }
570
571 /// truncate - Return a new range in the specified integer type, which must be
572 /// strictly smaller than the current type. The returned range will
573 /// correspond to the possible range of values as if the source range had been
574 /// truncated to the specified type.
truncate(uint32_t DstTySize) const575 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
576 assert(getBitWidth() > DstTySize && "Not a value truncation");
577 if (isEmptySet())
578 return ConstantRange(DstTySize, /*isFullSet=*/false);
579 if (isFullSet())
580 return ConstantRange(DstTySize, /*isFullSet=*/true);
581
582 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
583 APInt MaxBitValue(getBitWidth(), 0);
584 MaxBitValue.setBit(DstTySize);
585
586 APInt LowerDiv(Lower), UpperDiv(Upper);
587 ConstantRange Union(DstTySize, /*isFullSet=*/false);
588
589 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
590 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
591 // then we do the union with [MaxValue, Upper)
592 if (isWrappedSet()) {
593 // If Upper is greater than Max Value, it covers the whole truncated range.
594 if (Upper.uge(MaxValue))
595 return ConstantRange(DstTySize, /*isFullSet=*/true);
596
597 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
598 UpperDiv = APInt::getMaxValue(getBitWidth());
599
600 // Union covers the MaxValue case, so return if the remaining range is just
601 // MaxValue.
602 if (LowerDiv == UpperDiv)
603 return Union;
604 }
605
606 // Chop off the most significant bits that are past the destination bitwidth.
607 if (LowerDiv.uge(MaxValue)) {
608 APInt Div(getBitWidth(), 0);
609 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
610 UpperDiv = UpperDiv - MaxBitValue * Div;
611 }
612
613 if (UpperDiv.ule(MaxValue))
614 return ConstantRange(LowerDiv.trunc(DstTySize),
615 UpperDiv.trunc(DstTySize)).unionWith(Union);
616
617 // The truncated value wraps around. Check if we can do better than fullset.
618 APInt UpperModulo = UpperDiv - MaxBitValue;
619 if (UpperModulo.ult(LowerDiv))
620 return ConstantRange(LowerDiv.trunc(DstTySize),
621 UpperModulo.trunc(DstTySize)).unionWith(Union);
622
623 return ConstantRange(DstTySize, /*isFullSet=*/true);
624 }
625
626 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
627 /// value is zero extended, truncated, or left alone to make it that width.
zextOrTrunc(uint32_t DstTySize) const628 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
629 unsigned SrcTySize = getBitWidth();
630 if (SrcTySize > DstTySize)
631 return truncate(DstTySize);
632 if (SrcTySize < DstTySize)
633 return zeroExtend(DstTySize);
634 return *this;
635 }
636
637 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
638 /// value is sign extended, truncated, or left alone to make it that width.
sextOrTrunc(uint32_t DstTySize) const639 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
640 unsigned SrcTySize = getBitWidth();
641 if (SrcTySize > DstTySize)
642 return truncate(DstTySize);
643 if (SrcTySize < DstTySize)
644 return signExtend(DstTySize);
645 return *this;
646 }
647
648 ConstantRange
add(const ConstantRange & Other) const649 ConstantRange::add(const ConstantRange &Other) const {
650 if (isEmptySet() || Other.isEmptySet())
651 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
652 if (isFullSet() || Other.isFullSet())
653 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
654
655 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
656 APInt NewLower = getLower() + Other.getLower();
657 APInt NewUpper = getUpper() + Other.getUpper() - 1;
658 if (NewLower == NewUpper)
659 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
660
661 ConstantRange X = ConstantRange(NewLower, NewUpper);
662 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
663 // We've wrapped, therefore, full set.
664 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
665
666 return X;
667 }
668
669 ConstantRange
sub(const ConstantRange & Other) const670 ConstantRange::sub(const ConstantRange &Other) const {
671 if (isEmptySet() || Other.isEmptySet())
672 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
673 if (isFullSet() || Other.isFullSet())
674 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
675
676 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
677 APInt NewLower = getLower() - Other.getUpper() + 1;
678 APInt NewUpper = getUpper() - Other.getLower();
679 if (NewLower == NewUpper)
680 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
681
682 ConstantRange X = ConstantRange(NewLower, NewUpper);
683 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
684 // We've wrapped, therefore, full set.
685 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
686
687 return X;
688 }
689
690 ConstantRange
multiply(const ConstantRange & Other) const691 ConstantRange::multiply(const ConstantRange &Other) const {
692 // TODO: If either operand is a single element and the multiply is known to
693 // be non-wrapping, round the result min and max value to the appropriate
694 // multiple of that element. If wrapping is possible, at least adjust the
695 // range according to the greatest power-of-two factor of the single element.
696
697 if (isEmptySet() || Other.isEmptySet())
698 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
699
700 // Multiplication is signedness-independent. However different ranges can be
701 // obtained depending on how the input ranges are treated. These different
702 // ranges are all conservatively correct, but one might be better than the
703 // other. We calculate two ranges; one treating the inputs as unsigned
704 // and the other signed, then return the smallest of these ranges.
705
706 // Unsigned range first.
707 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
708 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
709 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
710 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
711
712 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
713 this_max * Other_max + 1);
714 ConstantRange UR = Result_zext.truncate(getBitWidth());
715
716 // If the unsigned range doesn't wrap, and isn't negative then it's a range
717 // from one positive number to another which is as good as we can generate.
718 // In this case, skip the extra work of generating signed ranges which aren't
719 // going to be better than this range.
720 if (!UR.isWrappedSet() && UR.getLower().isNonNegative())
721 return UR;
722
723 // Now the signed range. Because we could be dealing with negative numbers
724 // here, the lower bound is the smallest of the cartesian product of the
725 // lower and upper ranges; for example:
726 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
727 // Similarly for the upper bound, swapping min for max.
728
729 this_min = getSignedMin().sext(getBitWidth() * 2);
730 this_max = getSignedMax().sext(getBitWidth() * 2);
731 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
732 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
733
734 auto L = {this_min * Other_min, this_min * Other_max,
735 this_max * Other_min, this_max * Other_max};
736 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
737 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
738 ConstantRange SR = Result_sext.truncate(getBitWidth());
739
740 return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
741 }
742
743 ConstantRange
smax(const ConstantRange & Other) const744 ConstantRange::smax(const ConstantRange &Other) const {
745 // X smax Y is: range(smax(X_smin, Y_smin),
746 // smax(X_smax, Y_smax))
747 if (isEmptySet() || Other.isEmptySet())
748 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
749 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
750 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
751 if (NewU == NewL)
752 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
753 return ConstantRange(NewL, NewU);
754 }
755
756 ConstantRange
umax(const ConstantRange & Other) const757 ConstantRange::umax(const ConstantRange &Other) const {
758 // X umax Y is: range(umax(X_umin, Y_umin),
759 // umax(X_umax, Y_umax))
760 if (isEmptySet() || Other.isEmptySet())
761 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
762 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
763 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
764 if (NewU == NewL)
765 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
766 return ConstantRange(NewL, NewU);
767 }
768
769 ConstantRange
smin(const ConstantRange & Other) const770 ConstantRange::smin(const ConstantRange &Other) const {
771 // X smin Y is: range(smin(X_smin, Y_smin),
772 // smin(X_smax, Y_smax))
773 if (isEmptySet() || Other.isEmptySet())
774 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
775 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
776 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
777 if (NewU == NewL)
778 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
779 return ConstantRange(NewL, NewU);
780 }
781
782 ConstantRange
umin(const ConstantRange & Other) const783 ConstantRange::umin(const ConstantRange &Other) const {
784 // X umin Y is: range(umin(X_umin, Y_umin),
785 // umin(X_umax, Y_umax))
786 if (isEmptySet() || Other.isEmptySet())
787 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
788 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
789 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
790 if (NewU == NewL)
791 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
792 return ConstantRange(NewL, NewU);
793 }
794
795 ConstantRange
udiv(const ConstantRange & RHS) const796 ConstantRange::udiv(const ConstantRange &RHS) const {
797 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
798 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
799 if (RHS.isFullSet())
800 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
801
802 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
803
804 APInt RHS_umin = RHS.getUnsignedMin();
805 if (RHS_umin == 0) {
806 // We want the lowest value in RHS excluding zero. Usually that would be 1
807 // except for a range in the form of [X, 1) in which case it would be X.
808 if (RHS.getUpper() == 1)
809 RHS_umin = RHS.getLower();
810 else
811 RHS_umin = APInt(getBitWidth(), 1);
812 }
813
814 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
815
816 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
817 // this could occur.
818 if (Lower == Upper)
819 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
820
821 return ConstantRange(Lower, Upper);
822 }
823
824 ConstantRange
binaryAnd(const ConstantRange & Other) const825 ConstantRange::binaryAnd(const ConstantRange &Other) const {
826 if (isEmptySet() || Other.isEmptySet())
827 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
828
829 // TODO: replace this with something less conservative
830
831 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
832 if (umin.isAllOnesValue())
833 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
834 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
835 }
836
837 ConstantRange
binaryOr(const ConstantRange & Other) const838 ConstantRange::binaryOr(const ConstantRange &Other) const {
839 if (isEmptySet() || Other.isEmptySet())
840 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
841
842 // TODO: replace this with something less conservative
843
844 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
845 if (umax.isMinValue())
846 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
847 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
848 }
849
850 ConstantRange
shl(const ConstantRange & Other) const851 ConstantRange::shl(const ConstantRange &Other) const {
852 if (isEmptySet() || Other.isEmptySet())
853 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
854
855 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
856 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
857
858 // there's no overflow!
859 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
860 if (Zeros.ugt(Other.getUnsignedMax()))
861 return ConstantRange(min, max + 1);
862
863 // FIXME: implement the other tricky cases
864 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
865 }
866
867 ConstantRange
lshr(const ConstantRange & Other) const868 ConstantRange::lshr(const ConstantRange &Other) const {
869 if (isEmptySet() || Other.isEmptySet())
870 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
871
872 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
873 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
874 if (min == max + 1)
875 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
876
877 return ConstantRange(min, max + 1);
878 }
879
inverse() const880 ConstantRange ConstantRange::inverse() const {
881 if (isFullSet())
882 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
883 if (isEmptySet())
884 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
885 return ConstantRange(Upper, Lower);
886 }
887
888 /// print - Print out the bounds to a stream...
889 ///
print(raw_ostream & OS) const890 void ConstantRange::print(raw_ostream &OS) const {
891 if (isFullSet())
892 OS << "full-set";
893 else if (isEmptySet())
894 OS << "empty-set";
895 else
896 OS << "[" << Lower << "," << Upper << ")";
897 }
898
899 /// dump - Allow printing from a debugger easily...
900 ///
dump() const901 LLVM_DUMP_METHOD void ConstantRange::dump() const {
902 print(dbgs());
903 }
904