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
makeNoWrapRegion(Instruction::BinaryOps BinOp,const APInt & C,unsigned NoWrapKind)130 ConstantRange ConstantRange::makeNoWrapRegion(Instruction::BinaryOps BinOp,
131 const APInt &C,
132 unsigned NoWrapKind) {
133 typedef OverflowingBinaryOperator OBO;
134
135 // Computes the intersection of CR0 and CR1. It is different from
136 // intersectWith in that the ConstantRange returned will only contain elements
137 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
138 // not, of both X and Y).
139 auto SubsetIntersect =
140 [](const ConstantRange &CR0, const ConstantRange &CR1) {
141 return CR0.inverse().unionWith(CR1.inverse()).inverse();
142 };
143
144 assert(BinOp >= Instruction::BinaryOpsBegin &&
145 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
146
147 assert((NoWrapKind == OBO::NoSignedWrap ||
148 NoWrapKind == OBO::NoUnsignedWrap ||
149 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
150 "NoWrapKind invalid!");
151
152 unsigned BitWidth = C.getBitWidth();
153 if (BinOp != Instruction::Add)
154 // Conservative answer: empty set
155 return ConstantRange(BitWidth, false);
156
157 if (C.isMinValue())
158 // Full set: nothing signed / unsigned wraps when added to 0.
159 return ConstantRange(BitWidth);
160
161 ConstantRange Result(BitWidth);
162
163 if (NoWrapKind & OBO::NoUnsignedWrap)
164 Result = SubsetIntersect(Result,
165 ConstantRange(APInt::getNullValue(BitWidth), -C));
166
167 if (NoWrapKind & OBO::NoSignedWrap) {
168 if (C.isStrictlyPositive())
169 Result = SubsetIntersect(
170 Result, ConstantRange(APInt::getSignedMinValue(BitWidth),
171 APInt::getSignedMinValue(BitWidth) - C));
172 else
173 Result = SubsetIntersect(
174 Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - C,
175 APInt::getSignedMinValue(BitWidth)));
176 }
177
178 return Result;
179 }
180
181 /// isFullSet - Return true if this set contains all of the elements possible
182 /// for this data-type
isFullSet() const183 bool ConstantRange::isFullSet() const {
184 return Lower == Upper && Lower.isMaxValue();
185 }
186
187 /// isEmptySet - Return true if this set contains no members.
188 ///
isEmptySet() const189 bool ConstantRange::isEmptySet() const {
190 return Lower == Upper && Lower.isMinValue();
191 }
192
193 /// isWrappedSet - Return true if this set wraps around the top of the range,
194 /// for example: [100, 8)
195 ///
isWrappedSet() const196 bool ConstantRange::isWrappedSet() const {
197 return Lower.ugt(Upper);
198 }
199
200 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
201 /// its bitwidth, for example: i8 [120, 140).
202 ///
isSignWrappedSet() const203 bool ConstantRange::isSignWrappedSet() const {
204 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
205 contains(APInt::getSignedMinValue(getBitWidth()));
206 }
207
208 /// getSetSize - Return the number of elements in this set.
209 ///
getSetSize() const210 APInt ConstantRange::getSetSize() const {
211 if (isFullSet()) {
212 APInt Size(getBitWidth()+1, 0);
213 Size.setBit(getBitWidth());
214 return Size;
215 }
216
217 // This is also correct for wrapped sets.
218 return (Upper - Lower).zext(getBitWidth()+1);
219 }
220
221 /// getUnsignedMax - Return the largest unsigned value contained in the
222 /// ConstantRange.
223 ///
getUnsignedMax() const224 APInt ConstantRange::getUnsignedMax() const {
225 if (isFullSet() || isWrappedSet())
226 return APInt::getMaxValue(getBitWidth());
227 return getUpper() - 1;
228 }
229
230 /// getUnsignedMin - Return the smallest unsigned value contained in the
231 /// ConstantRange.
232 ///
getUnsignedMin() const233 APInt ConstantRange::getUnsignedMin() const {
234 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
235 return APInt::getMinValue(getBitWidth());
236 return getLower();
237 }
238
239 /// getSignedMax - Return the largest signed value contained in the
240 /// ConstantRange.
241 ///
getSignedMax() const242 APInt ConstantRange::getSignedMax() const {
243 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
244 if (!isWrappedSet()) {
245 if (getLower().sle(getUpper() - 1))
246 return getUpper() - 1;
247 return SignedMax;
248 }
249 if (getLower().isNegative() == getUpper().isNegative())
250 return SignedMax;
251 return getUpper() - 1;
252 }
253
254 /// getSignedMin - Return the smallest signed value contained in the
255 /// ConstantRange.
256 ///
getSignedMin() const257 APInt ConstantRange::getSignedMin() const {
258 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
259 if (!isWrappedSet()) {
260 if (getLower().sle(getUpper() - 1))
261 return getLower();
262 return SignedMin;
263 }
264 if ((getUpper() - 1).slt(getLower())) {
265 if (getUpper() != SignedMin)
266 return SignedMin;
267 }
268 return getLower();
269 }
270
271 /// contains - Return true if the specified value is in the set.
272 ///
contains(const APInt & V) const273 bool ConstantRange::contains(const APInt &V) const {
274 if (Lower == Upper)
275 return isFullSet();
276
277 if (!isWrappedSet())
278 return Lower.ule(V) && V.ult(Upper);
279 return Lower.ule(V) || V.ult(Upper);
280 }
281
282 /// contains - Return true if the argument is a subset of this range.
283 /// Two equal sets contain each other. The empty set contained by all other
284 /// sets.
285 ///
contains(const ConstantRange & Other) const286 bool ConstantRange::contains(const ConstantRange &Other) const {
287 if (isFullSet() || Other.isEmptySet()) return true;
288 if (isEmptySet() || Other.isFullSet()) return false;
289
290 if (!isWrappedSet()) {
291 if (Other.isWrappedSet())
292 return false;
293
294 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
295 }
296
297 if (!Other.isWrappedSet())
298 return Other.getUpper().ule(Upper) ||
299 Lower.ule(Other.getLower());
300
301 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
302 }
303
304 /// subtract - Subtract the specified constant from the endpoints of this
305 /// constant range.
subtract(const APInt & Val) const306 ConstantRange ConstantRange::subtract(const APInt &Val) const {
307 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
308 // If the set is empty or full, don't modify the endpoints.
309 if (Lower == Upper)
310 return *this;
311 return ConstantRange(Lower - Val, Upper - Val);
312 }
313
314 /// \brief Subtract the specified range from this range (aka relative complement
315 /// of the sets).
difference(const ConstantRange & CR) const316 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
317 return intersectWith(CR.inverse());
318 }
319
320 /// intersectWith - Return the range that results from the intersection of this
321 /// range with another range. The resultant range is guaranteed to include all
322 /// elements contained in both input ranges, and to have the smallest possible
323 /// set size that does so. Because there may be two intersections with the
324 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
intersectWith(const ConstantRange & CR) const325 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
326 assert(getBitWidth() == CR.getBitWidth() &&
327 "ConstantRange types don't agree!");
328
329 // Handle common cases.
330 if ( isEmptySet() || CR.isFullSet()) return *this;
331 if (CR.isEmptySet() || isFullSet()) return CR;
332
333 if (!isWrappedSet() && CR.isWrappedSet())
334 return CR.intersectWith(*this);
335
336 if (!isWrappedSet() && !CR.isWrappedSet()) {
337 if (Lower.ult(CR.Lower)) {
338 if (Upper.ule(CR.Lower))
339 return ConstantRange(getBitWidth(), false);
340
341 if (Upper.ult(CR.Upper))
342 return ConstantRange(CR.Lower, Upper);
343
344 return CR;
345 }
346 if (Upper.ult(CR.Upper))
347 return *this;
348
349 if (Lower.ult(CR.Upper))
350 return ConstantRange(Lower, CR.Upper);
351
352 return ConstantRange(getBitWidth(), false);
353 }
354
355 if (isWrappedSet() && !CR.isWrappedSet()) {
356 if (CR.Lower.ult(Upper)) {
357 if (CR.Upper.ult(Upper))
358 return CR;
359
360 if (CR.Upper.ule(Lower))
361 return ConstantRange(CR.Lower, Upper);
362
363 if (getSetSize().ult(CR.getSetSize()))
364 return *this;
365 return CR;
366 }
367 if (CR.Lower.ult(Lower)) {
368 if (CR.Upper.ule(Lower))
369 return ConstantRange(getBitWidth(), false);
370
371 return ConstantRange(Lower, CR.Upper);
372 }
373 return CR;
374 }
375
376 if (CR.Upper.ult(Upper)) {
377 if (CR.Lower.ult(Upper)) {
378 if (getSetSize().ult(CR.getSetSize()))
379 return *this;
380 return CR;
381 }
382
383 if (CR.Lower.ult(Lower))
384 return ConstantRange(Lower, CR.Upper);
385
386 return CR;
387 }
388 if (CR.Upper.ule(Lower)) {
389 if (CR.Lower.ult(Lower))
390 return *this;
391
392 return ConstantRange(CR.Lower, Upper);
393 }
394 if (getSetSize().ult(CR.getSetSize()))
395 return *this;
396 return CR;
397 }
398
399
400 /// unionWith - Return the range that results from the union of this range with
401 /// another range. The resultant range is guaranteed to include the elements of
402 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
403 /// [3, 15), which includes 9, 10, and 11, which were not included in either
404 /// set before.
405 ///
unionWith(const ConstantRange & CR) const406 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
407 assert(getBitWidth() == CR.getBitWidth() &&
408 "ConstantRange types don't agree!");
409
410 if ( isFullSet() || CR.isEmptySet()) return *this;
411 if (CR.isFullSet() || isEmptySet()) return CR;
412
413 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
414
415 if (!isWrappedSet() && !CR.isWrappedSet()) {
416 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
417 // If the two ranges are disjoint, find the smaller gap and bridge it.
418 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
419 if (d1.ult(d2))
420 return ConstantRange(Lower, CR.Upper);
421 return ConstantRange(CR.Lower, Upper);
422 }
423
424 APInt L = Lower, U = Upper;
425 if (CR.Lower.ult(L))
426 L = CR.Lower;
427 if ((CR.Upper - 1).ugt(U - 1))
428 U = CR.Upper;
429
430 if (L == 0 && U == 0)
431 return ConstantRange(getBitWidth());
432
433 return ConstantRange(L, U);
434 }
435
436 if (!CR.isWrappedSet()) {
437 // ------U L----- and ------U L----- : this
438 // L--U L--U : CR
439 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
440 return *this;
441
442 // ------U L----- : this
443 // L---------U : CR
444 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
445 return ConstantRange(getBitWidth());
446
447 // ----U L---- : this
448 // L---U : CR
449 // <d1> <d2>
450 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
451 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
452 if (d1.ult(d2))
453 return ConstantRange(Lower, CR.Upper);
454 return ConstantRange(CR.Lower, Upper);
455 }
456
457 // ----U L----- : this
458 // L----U : CR
459 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
460 return ConstantRange(CR.Lower, Upper);
461
462 // ------U L---- : this
463 // L-----U : CR
464 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
465 "ConstantRange::unionWith missed a case with one range wrapped");
466 return ConstantRange(Lower, CR.Upper);
467 }
468
469 // ------U L---- and ------U L---- : this
470 // -U L----------- and ------------U L : CR
471 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
472 return ConstantRange(getBitWidth());
473
474 APInt L = Lower, U = Upper;
475 if (CR.Upper.ugt(U))
476 U = CR.Upper;
477 if (CR.Lower.ult(L))
478 L = CR.Lower;
479
480 return ConstantRange(L, U);
481 }
482
483 /// zeroExtend - Return a new range in the specified integer type, which must
484 /// be strictly larger than the current type. The returned range will
485 /// correspond to the possible range of values as if the source range had been
486 /// zero extended.
zeroExtend(uint32_t DstTySize) const487 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
488 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
489
490 unsigned SrcTySize = getBitWidth();
491 assert(SrcTySize < DstTySize && "Not a value extension");
492 if (isFullSet() || isWrappedSet()) {
493 // Change into [0, 1 << src bit width)
494 APInt LowerExt(DstTySize, 0);
495 if (!Upper) // special case: [X, 0) -- not really wrapping around
496 LowerExt = Lower.zext(DstTySize);
497 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
498 }
499
500 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
501 }
502
503 /// signExtend - Return a new range in the specified integer type, which must
504 /// be strictly larger than the current type. The returned range will
505 /// correspond to the possible range of values as if the source range had been
506 /// sign extended.
signExtend(uint32_t DstTySize) const507 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
508 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
509
510 unsigned SrcTySize = getBitWidth();
511 assert(SrcTySize < DstTySize && "Not a value extension");
512
513 // special case: [X, INT_MIN) -- not really wrapping around
514 if (Upper.isMinSignedValue())
515 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
516
517 if (isFullSet() || isSignWrappedSet()) {
518 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
519 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
520 }
521
522 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
523 }
524
525 /// truncate - Return a new range in the specified integer type, which must be
526 /// strictly smaller than the current type. The returned range will
527 /// correspond to the possible range of values as if the source range had been
528 /// truncated to the specified type.
truncate(uint32_t DstTySize) const529 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
530 assert(getBitWidth() > DstTySize && "Not a value truncation");
531 if (isEmptySet())
532 return ConstantRange(DstTySize, /*isFullSet=*/false);
533 if (isFullSet())
534 return ConstantRange(DstTySize, /*isFullSet=*/true);
535
536 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
537 APInt MaxBitValue(getBitWidth(), 0);
538 MaxBitValue.setBit(DstTySize);
539
540 APInt LowerDiv(Lower), UpperDiv(Upper);
541 ConstantRange Union(DstTySize, /*isFullSet=*/false);
542
543 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
544 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
545 // then we do the union with [MaxValue, Upper)
546 if (isWrappedSet()) {
547 // if Upper is greater than Max Value, it covers the whole truncated range.
548 if (Upper.uge(MaxValue))
549 return ConstantRange(DstTySize, /*isFullSet=*/true);
550
551 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
552 UpperDiv = APInt::getMaxValue(getBitWidth());
553
554 // Union covers the MaxValue case, so return if the remaining range is just
555 // MaxValue.
556 if (LowerDiv == UpperDiv)
557 return Union;
558 }
559
560 // Chop off the most significant bits that are past the destination bitwidth.
561 if (LowerDiv.uge(MaxValue)) {
562 APInt Div(getBitWidth(), 0);
563 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
564 UpperDiv = UpperDiv - MaxBitValue * Div;
565 }
566
567 if (UpperDiv.ule(MaxValue))
568 return ConstantRange(LowerDiv.trunc(DstTySize),
569 UpperDiv.trunc(DstTySize)).unionWith(Union);
570
571 // The truncated value wrapps around. Check if we can do better than fullset.
572 APInt UpperModulo = UpperDiv - MaxBitValue;
573 if (UpperModulo.ult(LowerDiv))
574 return ConstantRange(LowerDiv.trunc(DstTySize),
575 UpperModulo.trunc(DstTySize)).unionWith(Union);
576
577 return ConstantRange(DstTySize, /*isFullSet=*/true);
578 }
579
580 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
581 /// value is zero extended, truncated, or left alone to make it that width.
zextOrTrunc(uint32_t DstTySize) const582 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
583 unsigned SrcTySize = getBitWidth();
584 if (SrcTySize > DstTySize)
585 return truncate(DstTySize);
586 if (SrcTySize < DstTySize)
587 return zeroExtend(DstTySize);
588 return *this;
589 }
590
591 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
592 /// value is sign extended, truncated, or left alone to make it that width.
sextOrTrunc(uint32_t DstTySize) const593 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
594 unsigned SrcTySize = getBitWidth();
595 if (SrcTySize > DstTySize)
596 return truncate(DstTySize);
597 if (SrcTySize < DstTySize)
598 return signExtend(DstTySize);
599 return *this;
600 }
601
602 ConstantRange
add(const ConstantRange & Other) const603 ConstantRange::add(const ConstantRange &Other) const {
604 if (isEmptySet() || Other.isEmptySet())
605 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
606 if (isFullSet() || Other.isFullSet())
607 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
608
609 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
610 APInt NewLower = getLower() + Other.getLower();
611 APInt NewUpper = getUpper() + Other.getUpper() - 1;
612 if (NewLower == NewUpper)
613 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
614
615 ConstantRange X = ConstantRange(NewLower, NewUpper);
616 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
617 // We've wrapped, therefore, full set.
618 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
619
620 return X;
621 }
622
623 ConstantRange
sub(const ConstantRange & Other) const624 ConstantRange::sub(const ConstantRange &Other) const {
625 if (isEmptySet() || Other.isEmptySet())
626 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
627 if (isFullSet() || Other.isFullSet())
628 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
629
630 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
631 APInt NewLower = getLower() - Other.getUpper() + 1;
632 APInt NewUpper = getUpper() - Other.getLower();
633 if (NewLower == NewUpper)
634 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
635
636 ConstantRange X = ConstantRange(NewLower, NewUpper);
637 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
638 // We've wrapped, therefore, full set.
639 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
640
641 return X;
642 }
643
644 ConstantRange
multiply(const ConstantRange & Other) const645 ConstantRange::multiply(const ConstantRange &Other) const {
646 // TODO: If either operand is a single element and the multiply is known to
647 // be non-wrapping, round the result min and max value to the appropriate
648 // multiple of that element. If wrapping is possible, at least adjust the
649 // range according to the greatest power-of-two factor of the single element.
650
651 if (isEmptySet() || Other.isEmptySet())
652 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
653
654 // Multiplication is signedness-independent. However different ranges can be
655 // obtained depending on how the input ranges are treated. These different
656 // ranges are all conservatively correct, but one might be better than the
657 // other. We calculate two ranges; one treating the inputs as unsigned
658 // and the other signed, then return the smallest of these ranges.
659
660 // Unsigned range first.
661 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
662 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
663 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
664 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
665
666 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
667 this_max * Other_max + 1);
668 ConstantRange UR = Result_zext.truncate(getBitWidth());
669
670 // Now the signed range. Because we could be dealing with negative numbers
671 // here, the lower bound is the smallest of the cartesian product of the
672 // lower and upper ranges; for example:
673 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
674 // Similarly for the upper bound, swapping min for max.
675
676 this_min = getSignedMin().sext(getBitWidth() * 2);
677 this_max = getSignedMax().sext(getBitWidth() * 2);
678 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
679 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
680
681 auto L = {this_min * Other_min, this_min * Other_max,
682 this_max * Other_min, this_max * Other_max};
683 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
684 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
685 ConstantRange SR = Result_sext.truncate(getBitWidth());
686
687 return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
688 }
689
690 ConstantRange
smax(const ConstantRange & Other) const691 ConstantRange::smax(const ConstantRange &Other) const {
692 // X smax Y is: range(smax(X_smin, Y_smin),
693 // smax(X_smax, Y_smax))
694 if (isEmptySet() || Other.isEmptySet())
695 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
696 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
697 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
698 if (NewU == NewL)
699 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
700 return ConstantRange(NewL, NewU);
701 }
702
703 ConstantRange
umax(const ConstantRange & Other) const704 ConstantRange::umax(const ConstantRange &Other) const {
705 // X umax Y is: range(umax(X_umin, Y_umin),
706 // umax(X_umax, Y_umax))
707 if (isEmptySet() || Other.isEmptySet())
708 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
709 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
710 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
711 if (NewU == NewL)
712 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
713 return ConstantRange(NewL, NewU);
714 }
715
716 ConstantRange
udiv(const ConstantRange & RHS) const717 ConstantRange::udiv(const ConstantRange &RHS) const {
718 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
719 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
720 if (RHS.isFullSet())
721 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
722
723 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
724
725 APInt RHS_umin = RHS.getUnsignedMin();
726 if (RHS_umin == 0) {
727 // We want the lowest value in RHS excluding zero. Usually that would be 1
728 // except for a range in the form of [X, 1) in which case it would be X.
729 if (RHS.getUpper() == 1)
730 RHS_umin = RHS.getLower();
731 else
732 RHS_umin = APInt(getBitWidth(), 1);
733 }
734
735 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
736
737 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
738 // this could occur.
739 if (Lower == Upper)
740 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
741
742 return ConstantRange(Lower, Upper);
743 }
744
745 ConstantRange
binaryAnd(const ConstantRange & Other) const746 ConstantRange::binaryAnd(const ConstantRange &Other) const {
747 if (isEmptySet() || Other.isEmptySet())
748 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
749
750 // TODO: replace this with something less conservative
751
752 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
753 if (umin.isAllOnesValue())
754 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
755 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
756 }
757
758 ConstantRange
binaryOr(const ConstantRange & Other) const759 ConstantRange::binaryOr(const ConstantRange &Other) const {
760 if (isEmptySet() || Other.isEmptySet())
761 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
762
763 // TODO: replace this with something less conservative
764
765 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
766 if (umax.isMinValue())
767 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
768 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
769 }
770
771 ConstantRange
shl(const ConstantRange & Other) const772 ConstantRange::shl(const ConstantRange &Other) const {
773 if (isEmptySet() || Other.isEmptySet())
774 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
775
776 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
777 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
778
779 // there's no overflow!
780 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
781 if (Zeros.ugt(Other.getUnsignedMax()))
782 return ConstantRange(min, max + 1);
783
784 // FIXME: implement the other tricky cases
785 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
786 }
787
788 ConstantRange
lshr(const ConstantRange & Other) const789 ConstantRange::lshr(const ConstantRange &Other) const {
790 if (isEmptySet() || Other.isEmptySet())
791 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
792
793 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
794 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
795 if (min == max + 1)
796 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
797
798 return ConstantRange(min, max + 1);
799 }
800
inverse() const801 ConstantRange ConstantRange::inverse() const {
802 if (isFullSet())
803 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
804 if (isEmptySet())
805 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
806 return ConstantRange(Upper, Lower);
807 }
808
809 /// print - Print out the bounds to a stream...
810 ///
print(raw_ostream & OS) const811 void ConstantRange::print(raw_ostream &OS) const {
812 if (isFullSet())
813 OS << "full-set";
814 else if (isEmptySet())
815 OS << "empty-set";
816 else
817 OS << "[" << Lower << "," << Upper << ")";
818 }
819
820 /// dump - Allow printing from a debugger easily...
821 ///
dump() const822 void ConstantRange::dump() const {
823 print(dbgs());
824 }
825