1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Represent a range of possible values that may occur when the program is run
10 // for an integral value. This keeps track of a lower and upper bound for the
11 // constant, which MAY wrap around the end of the numeric range. To do this, it
12 // keeps track of a [lower, upper) bound, which specifies an interval just like
13 // STL iterators. When used with boolean values, the following are important
14 // ranges (other integral ranges use min/max values for special range values):
15 //
16 // [F, F) = {} = Empty set
17 // [T, F) = {T}
18 // [F, T) = {F}
19 // [T, T) = {F, T} = Full set
20 //
21 //===----------------------------------------------------------------------===//
22
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/Config/llvm-config.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Intrinsics.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Operator.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/ErrorHandling.h"
35 #include "llvm/Support/KnownBits.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include <algorithm>
38 #include <cassert>
39 #include <cstdint>
40
41 using namespace llvm;
42
ConstantRange(uint32_t BitWidth,bool Full)43 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
44 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
45 Upper(Lower) {}
46
ConstantRange(APInt V)47 ConstantRange::ConstantRange(APInt V)
48 : Lower(std::move(V)), Upper(Lower + 1) {}
49
ConstantRange(APInt L,APInt U)50 ConstantRange::ConstantRange(APInt L, APInt U)
51 : Lower(std::move(L)), Upper(std::move(U)) {
52 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
53 "ConstantRange with unequal bit widths");
54 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
55 "Lower == Upper, but they aren't min or max value!");
56 }
57
fromKnownBits(const KnownBits & Known,bool IsSigned)58 ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
59 bool IsSigned) {
60 assert(!Known.hasConflict() && "Expected valid KnownBits");
61
62 if (Known.isUnknown())
63 return getFull(Known.getBitWidth());
64
65 // For unsigned ranges, or signed ranges with known sign bit, create a simple
66 // range between the smallest and largest possible value.
67 if (!IsSigned || Known.isNegative() || Known.isNonNegative())
68 return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);
69
70 // If we don't know the sign bit, pick the lower bound as a negative number
71 // and the upper bound as a non-negative one.
72 APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();
73 Lower.setSignBit();
74 Upper.clearSignBit();
75 return ConstantRange(Lower, Upper + 1);
76 }
77
makeAllowedICmpRegion(CmpInst::Predicate Pred,const ConstantRange & CR)78 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
79 const ConstantRange &CR) {
80 if (CR.isEmptySet())
81 return CR;
82
83 uint32_t W = CR.getBitWidth();
84 switch (Pred) {
85 default:
86 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
87 case CmpInst::ICMP_EQ:
88 return CR;
89 case CmpInst::ICMP_NE:
90 if (CR.isSingleElement())
91 return ConstantRange(CR.getUpper(), CR.getLower());
92 return getFull(W);
93 case CmpInst::ICMP_ULT: {
94 APInt UMax(CR.getUnsignedMax());
95 if (UMax.isMinValue())
96 return getEmpty(W);
97 return ConstantRange(APInt::getMinValue(W), std::move(UMax));
98 }
99 case CmpInst::ICMP_SLT: {
100 APInt SMax(CR.getSignedMax());
101 if (SMax.isMinSignedValue())
102 return getEmpty(W);
103 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
104 }
105 case CmpInst::ICMP_ULE:
106 return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);
107 case CmpInst::ICMP_SLE:
108 return getNonEmpty(APInt::getSignedMinValue(W), CR.getSignedMax() + 1);
109 case CmpInst::ICMP_UGT: {
110 APInt UMin(CR.getUnsignedMin());
111 if (UMin.isMaxValue())
112 return getEmpty(W);
113 return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
114 }
115 case CmpInst::ICMP_SGT: {
116 APInt SMin(CR.getSignedMin());
117 if (SMin.isMaxSignedValue())
118 return getEmpty(W);
119 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
120 }
121 case CmpInst::ICMP_UGE:
122 return getNonEmpty(CR.getUnsignedMin(), APInt::getNullValue(W));
123 case CmpInst::ICMP_SGE:
124 return getNonEmpty(CR.getSignedMin(), APInt::getSignedMinValue(W));
125 }
126 }
127
makeSatisfyingICmpRegion(CmpInst::Predicate Pred,const ConstantRange & CR)128 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
129 const ConstantRange &CR) {
130 // Follows from De-Morgan's laws:
131 //
132 // ~(~A union ~B) == A intersect B.
133 //
134 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
135 .inverse();
136 }
137
makeExactICmpRegion(CmpInst::Predicate Pred,const APInt & C)138 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
139 const APInt &C) {
140 // Computes the exact range that is equal to both the constant ranges returned
141 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
142 // when RHS is a singleton such as an APInt and so the assert is valid.
143 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
144 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
145 //
146 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
147 return makeAllowedICmpRegion(Pred, C);
148 }
149
getEquivalentICmp(CmpInst::Predicate & Pred,APInt & RHS) const150 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
151 APInt &RHS) const {
152 bool Success = false;
153
154 if (isFullSet() || isEmptySet()) {
155 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
156 RHS = APInt(getBitWidth(), 0);
157 Success = true;
158 } else if (auto *OnlyElt = getSingleElement()) {
159 Pred = CmpInst::ICMP_EQ;
160 RHS = *OnlyElt;
161 Success = true;
162 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
163 Pred = CmpInst::ICMP_NE;
164 RHS = *OnlyMissingElt;
165 Success = true;
166 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
167 Pred =
168 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
169 RHS = getUpper();
170 Success = true;
171 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
172 Pred =
173 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
174 RHS = getLower();
175 Success = true;
176 }
177
178 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
179 "Bad result!");
180
181 return Success;
182 }
183
icmp(CmpInst::Predicate Pred,const ConstantRange & Other) const184 bool ConstantRange::icmp(CmpInst::Predicate Pred,
185 const ConstantRange &Other) const {
186 return makeSatisfyingICmpRegion(Pred, Other).contains(*this);
187 }
188
189 /// Exact mul nuw region for single element RHS.
makeExactMulNUWRegion(const APInt & V)190 static ConstantRange makeExactMulNUWRegion(const APInt &V) {
191 unsigned BitWidth = V.getBitWidth();
192 if (V == 0)
193 return ConstantRange::getFull(V.getBitWidth());
194
195 return ConstantRange::getNonEmpty(
196 APIntOps::RoundingUDiv(APInt::getMinValue(BitWidth), V,
197 APInt::Rounding::UP),
198 APIntOps::RoundingUDiv(APInt::getMaxValue(BitWidth), V,
199 APInt::Rounding::DOWN) + 1);
200 }
201
202 /// Exact mul nsw region for single element RHS.
makeExactMulNSWRegion(const APInt & V)203 static ConstantRange makeExactMulNSWRegion(const APInt &V) {
204 // Handle special case for 0, -1 and 1. See the last for reason why we
205 // specialize -1 and 1.
206 unsigned BitWidth = V.getBitWidth();
207 if (V == 0 || V.isOneValue())
208 return ConstantRange::getFull(BitWidth);
209
210 APInt MinValue = APInt::getSignedMinValue(BitWidth);
211 APInt MaxValue = APInt::getSignedMaxValue(BitWidth);
212 // e.g. Returning [-127, 127], represented as [-127, -128).
213 if (V.isAllOnesValue())
214 return ConstantRange(-MaxValue, MinValue);
215
216 APInt Lower, Upper;
217 if (V.isNegative()) {
218 Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
219 Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
220 } else {
221 Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
222 Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
223 }
224 // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
225 // Upper + 1 is guaranteed not to overflow, because |divisor| > 1. 0, -1,
226 // and 1 are already handled as special cases.
227 return ConstantRange(Lower, Upper + 1);
228 }
229
230 ConstantRange
makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,const ConstantRange & Other,unsigned NoWrapKind)231 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
232 const ConstantRange &Other,
233 unsigned NoWrapKind) {
234 using OBO = OverflowingBinaryOperator;
235
236 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
237
238 assert((NoWrapKind == OBO::NoSignedWrap ||
239 NoWrapKind == OBO::NoUnsignedWrap) &&
240 "NoWrapKind invalid!");
241
242 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
243 unsigned BitWidth = Other.getBitWidth();
244
245 switch (BinOp) {
246 default:
247 llvm_unreachable("Unsupported binary op");
248
249 case Instruction::Add: {
250 if (Unsigned)
251 return getNonEmpty(APInt::getNullValue(BitWidth),
252 -Other.getUnsignedMax());
253
254 APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
255 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
256 return getNonEmpty(
257 SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
258 SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
259 }
260
261 case Instruction::Sub: {
262 if (Unsigned)
263 return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
264
265 APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
266 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
267 return getNonEmpty(
268 SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
269 SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
270 }
271
272 case Instruction::Mul:
273 if (Unsigned)
274 return makeExactMulNUWRegion(Other.getUnsignedMax());
275
276 return makeExactMulNSWRegion(Other.getSignedMin())
277 .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
278
279 case Instruction::Shl: {
280 // For given range of shift amounts, if we ignore all illegal shift amounts
281 // (that always produce poison), what shift amount range is left?
282 ConstantRange ShAmt = Other.intersectWith(
283 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));
284 if (ShAmt.isEmptySet()) {
285 // If the entire range of shift amounts is already poison-producing,
286 // then we can freely add more poison-producing flags ontop of that.
287 return getFull(BitWidth);
288 }
289 // There are some legal shift amounts, we can compute conservatively-correct
290 // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
291 // to be at most bitwidth-1, which results in most conservative range.
292 APInt ShAmtUMax = ShAmt.getUnsignedMax();
293 if (Unsigned)
294 return getNonEmpty(APInt::getNullValue(BitWidth),
295 APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1);
296 return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(ShAmtUMax),
297 APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1);
298 }
299 }
300 }
301
makeExactNoWrapRegion(Instruction::BinaryOps BinOp,const APInt & Other,unsigned NoWrapKind)302 ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
303 const APInt &Other,
304 unsigned NoWrapKind) {
305 // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
306 // "for all" and "for any" coincide in this case.
307 return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
308 }
309
isFullSet() const310 bool ConstantRange::isFullSet() const {
311 return Lower == Upper && Lower.isMaxValue();
312 }
313
isEmptySet() const314 bool ConstantRange::isEmptySet() const {
315 return Lower == Upper && Lower.isMinValue();
316 }
317
isWrappedSet() const318 bool ConstantRange::isWrappedSet() const {
319 return Lower.ugt(Upper) && !Upper.isNullValue();
320 }
321
isUpperWrapped() const322 bool ConstantRange::isUpperWrapped() const {
323 return Lower.ugt(Upper);
324 }
325
isSignWrappedSet() const326 bool ConstantRange::isSignWrappedSet() const {
327 return Lower.sgt(Upper) && !Upper.isMinSignedValue();
328 }
329
isUpperSignWrapped() const330 bool ConstantRange::isUpperSignWrapped() const {
331 return Lower.sgt(Upper);
332 }
333
334 bool
isSizeStrictlySmallerThan(const ConstantRange & Other) const335 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
336 assert(getBitWidth() == Other.getBitWidth());
337 if (isFullSet())
338 return false;
339 if (Other.isFullSet())
340 return true;
341 return (Upper - Lower).ult(Other.Upper - Other.Lower);
342 }
343
344 bool
isSizeLargerThan(uint64_t MaxSize) const345 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
346 assert(MaxSize && "MaxSize can't be 0.");
347 // If this a full set, we need special handling to avoid needing an extra bit
348 // to represent the size.
349 if (isFullSet())
350 return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
351
352 return (Upper - Lower).ugt(MaxSize);
353 }
354
isAllNegative() const355 bool ConstantRange::isAllNegative() const {
356 // Empty set is all negative, full set is not.
357 if (isEmptySet())
358 return true;
359 if (isFullSet())
360 return false;
361
362 return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
363 }
364
isAllNonNegative() const365 bool ConstantRange::isAllNonNegative() const {
366 // Empty and full set are automatically treated correctly.
367 return !isSignWrappedSet() && Lower.isNonNegative();
368 }
369
getUnsignedMax() const370 APInt ConstantRange::getUnsignedMax() const {
371 if (isFullSet() || isUpperWrapped())
372 return APInt::getMaxValue(getBitWidth());
373 return getUpper() - 1;
374 }
375
getUnsignedMin() const376 APInt ConstantRange::getUnsignedMin() const {
377 if (isFullSet() || isWrappedSet())
378 return APInt::getMinValue(getBitWidth());
379 return getLower();
380 }
381
getSignedMax() const382 APInt ConstantRange::getSignedMax() const {
383 if (isFullSet() || isUpperSignWrapped())
384 return APInt::getSignedMaxValue(getBitWidth());
385 return getUpper() - 1;
386 }
387
getSignedMin() const388 APInt ConstantRange::getSignedMin() const {
389 if (isFullSet() || isSignWrappedSet())
390 return APInt::getSignedMinValue(getBitWidth());
391 return getLower();
392 }
393
contains(const APInt & V) const394 bool ConstantRange::contains(const APInt &V) const {
395 if (Lower == Upper)
396 return isFullSet();
397
398 if (!isUpperWrapped())
399 return Lower.ule(V) && V.ult(Upper);
400 return Lower.ule(V) || V.ult(Upper);
401 }
402
contains(const ConstantRange & Other) const403 bool ConstantRange::contains(const ConstantRange &Other) const {
404 if (isFullSet() || Other.isEmptySet()) return true;
405 if (isEmptySet() || Other.isFullSet()) return false;
406
407 if (!isUpperWrapped()) {
408 if (Other.isUpperWrapped())
409 return false;
410
411 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
412 }
413
414 if (!Other.isUpperWrapped())
415 return Other.getUpper().ule(Upper) ||
416 Lower.ule(Other.getLower());
417
418 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
419 }
420
getActiveBits() const421 unsigned ConstantRange::getActiveBits() const {
422 if (isEmptySet())
423 return 0;
424
425 return getUnsignedMax().getActiveBits();
426 }
427
getMinSignedBits() const428 unsigned ConstantRange::getMinSignedBits() const {
429 if (isEmptySet())
430 return 0;
431
432 return std::max(getSignedMin().getMinSignedBits(),
433 getSignedMax().getMinSignedBits());
434 }
435
subtract(const APInt & Val) const436 ConstantRange ConstantRange::subtract(const APInt &Val) const {
437 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
438 // If the set is empty or full, don't modify the endpoints.
439 if (Lower == Upper)
440 return *this;
441 return ConstantRange(Lower - Val, Upper - Val);
442 }
443
difference(const ConstantRange & CR) const444 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
445 return intersectWith(CR.inverse());
446 }
447
getPreferredRange(const ConstantRange & CR1,const ConstantRange & CR2,ConstantRange::PreferredRangeType Type)448 static ConstantRange getPreferredRange(
449 const ConstantRange &CR1, const ConstantRange &CR2,
450 ConstantRange::PreferredRangeType Type) {
451 if (Type == ConstantRange::Unsigned) {
452 if (!CR1.isWrappedSet() && CR2.isWrappedSet())
453 return CR1;
454 if (CR1.isWrappedSet() && !CR2.isWrappedSet())
455 return CR2;
456 } else if (Type == ConstantRange::Signed) {
457 if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
458 return CR1;
459 if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
460 return CR2;
461 }
462
463 if (CR1.isSizeStrictlySmallerThan(CR2))
464 return CR1;
465 return CR2;
466 }
467
intersectWith(const ConstantRange & CR,PreferredRangeType Type) const468 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
469 PreferredRangeType Type) const {
470 assert(getBitWidth() == CR.getBitWidth() &&
471 "ConstantRange types don't agree!");
472
473 // Handle common cases.
474 if ( isEmptySet() || CR.isFullSet()) return *this;
475 if (CR.isEmptySet() || isFullSet()) return CR;
476
477 if (!isUpperWrapped() && CR.isUpperWrapped())
478 return CR.intersectWith(*this, Type);
479
480 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
481 if (Lower.ult(CR.Lower)) {
482 // L---U : this
483 // L---U : CR
484 if (Upper.ule(CR.Lower))
485 return getEmpty();
486
487 // L---U : this
488 // L---U : CR
489 if (Upper.ult(CR.Upper))
490 return ConstantRange(CR.Lower, Upper);
491
492 // L-------U : this
493 // L---U : CR
494 return CR;
495 }
496 // L---U : this
497 // L-------U : CR
498 if (Upper.ult(CR.Upper))
499 return *this;
500
501 // L-----U : this
502 // L-----U : CR
503 if (Lower.ult(CR.Upper))
504 return ConstantRange(Lower, CR.Upper);
505
506 // L---U : this
507 // L---U : CR
508 return getEmpty();
509 }
510
511 if (isUpperWrapped() && !CR.isUpperWrapped()) {
512 if (CR.Lower.ult(Upper)) {
513 // ------U L--- : this
514 // L--U : CR
515 if (CR.Upper.ult(Upper))
516 return CR;
517
518 // ------U L--- : this
519 // L------U : CR
520 if (CR.Upper.ule(Lower))
521 return ConstantRange(CR.Lower, Upper);
522
523 // ------U L--- : this
524 // L----------U : CR
525 return getPreferredRange(*this, CR, Type);
526 }
527 if (CR.Lower.ult(Lower)) {
528 // --U L---- : this
529 // L--U : CR
530 if (CR.Upper.ule(Lower))
531 return getEmpty();
532
533 // --U L---- : this
534 // L------U : CR
535 return ConstantRange(Lower, CR.Upper);
536 }
537
538 // --U L------ : this
539 // L--U : CR
540 return CR;
541 }
542
543 if (CR.Upper.ult(Upper)) {
544 // ------U L-- : this
545 // --U L------ : CR
546 if (CR.Lower.ult(Upper))
547 return getPreferredRange(*this, CR, Type);
548
549 // ----U L-- : this
550 // --U L---- : CR
551 if (CR.Lower.ult(Lower))
552 return ConstantRange(Lower, CR.Upper);
553
554 // ----U L---- : this
555 // --U L-- : CR
556 return CR;
557 }
558 if (CR.Upper.ule(Lower)) {
559 // --U L-- : this
560 // ----U L---- : CR
561 if (CR.Lower.ult(Lower))
562 return *this;
563
564 // --U L---- : this
565 // ----U L-- : CR
566 return ConstantRange(CR.Lower, Upper);
567 }
568
569 // --U L------ : this
570 // ------U L-- : CR
571 return getPreferredRange(*this, CR, Type);
572 }
573
unionWith(const ConstantRange & CR,PreferredRangeType Type) const574 ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
575 PreferredRangeType Type) const {
576 assert(getBitWidth() == CR.getBitWidth() &&
577 "ConstantRange types don't agree!");
578
579 if ( isFullSet() || CR.isEmptySet()) return *this;
580 if (CR.isFullSet() || isEmptySet()) return CR;
581
582 if (!isUpperWrapped() && CR.isUpperWrapped())
583 return CR.unionWith(*this, Type);
584
585 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
586 // L---U and L---U : this
587 // L---U L---U : CR
588 // result in one of
589 // L---------U
590 // -----U L-----
591 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
592 return getPreferredRange(
593 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
594
595 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
596 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
597
598 if (L.isNullValue() && U.isNullValue())
599 return getFull();
600
601 return ConstantRange(std::move(L), std::move(U));
602 }
603
604 if (!CR.isUpperWrapped()) {
605 // ------U L----- and ------U L----- : this
606 // L--U L--U : CR
607 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
608 return *this;
609
610 // ------U L----- : this
611 // L---------U : CR
612 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
613 return getFull();
614
615 // ----U L---- : this
616 // L---U : CR
617 // results in one of
618 // ----------U L----
619 // ----U L----------
620 if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
621 return getPreferredRange(
622 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
623
624 // ----U L----- : this
625 // L----U : CR
626 if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
627 return ConstantRange(CR.Lower, Upper);
628
629 // ------U L---- : this
630 // L-----U : CR
631 assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
632 "ConstantRange::unionWith missed a case with one range wrapped");
633 return ConstantRange(Lower, CR.Upper);
634 }
635
636 // ------U L---- and ------U L---- : this
637 // -U L----------- and ------------U L : CR
638 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
639 return getFull();
640
641 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
642 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
643
644 return ConstantRange(std::move(L), std::move(U));
645 }
646
castOp(Instruction::CastOps CastOp,uint32_t ResultBitWidth) const647 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
648 uint32_t ResultBitWidth) const {
649 switch (CastOp) {
650 default:
651 llvm_unreachable("unsupported cast type");
652 case Instruction::Trunc:
653 return truncate(ResultBitWidth);
654 case Instruction::SExt:
655 return signExtend(ResultBitWidth);
656 case Instruction::ZExt:
657 return zeroExtend(ResultBitWidth);
658 case Instruction::BitCast:
659 return *this;
660 case Instruction::FPToUI:
661 case Instruction::FPToSI:
662 if (getBitWidth() == ResultBitWidth)
663 return *this;
664 else
665 return getFull(ResultBitWidth);
666 case Instruction::UIToFP: {
667 // TODO: use input range if available
668 auto BW = getBitWidth();
669 APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
670 APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
671 return ConstantRange(std::move(Min), std::move(Max));
672 }
673 case Instruction::SIToFP: {
674 // TODO: use input range if available
675 auto BW = getBitWidth();
676 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
677 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
678 return ConstantRange(std::move(SMin), std::move(SMax));
679 }
680 case Instruction::FPTrunc:
681 case Instruction::FPExt:
682 case Instruction::IntToPtr:
683 case Instruction::PtrToInt:
684 case Instruction::AddrSpaceCast:
685 // Conservatively return getFull set.
686 return getFull(ResultBitWidth);
687 };
688 }
689
zeroExtend(uint32_t DstTySize) const690 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
691 if (isEmptySet()) return getEmpty(DstTySize);
692
693 unsigned SrcTySize = getBitWidth();
694 assert(SrcTySize < DstTySize && "Not a value extension");
695 if (isFullSet() || isUpperWrapped()) {
696 // Change into [0, 1 << src bit width)
697 APInt LowerExt(DstTySize, 0);
698 if (!Upper) // special case: [X, 0) -- not really wrapping around
699 LowerExt = Lower.zext(DstTySize);
700 return ConstantRange(std::move(LowerExt),
701 APInt::getOneBitSet(DstTySize, SrcTySize));
702 }
703
704 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
705 }
706
signExtend(uint32_t DstTySize) const707 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
708 if (isEmptySet()) return getEmpty(DstTySize);
709
710 unsigned SrcTySize = getBitWidth();
711 assert(SrcTySize < DstTySize && "Not a value extension");
712
713 // special case: [X, INT_MIN) -- not really wrapping around
714 if (Upper.isMinSignedValue())
715 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
716
717 if (isFullSet() || isSignWrappedSet()) {
718 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
719 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
720 }
721
722 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
723 }
724
truncate(uint32_t DstTySize) const725 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
726 assert(getBitWidth() > DstTySize && "Not a value truncation");
727 if (isEmptySet())
728 return getEmpty(DstTySize);
729 if (isFullSet())
730 return getFull(DstTySize);
731
732 APInt LowerDiv(Lower), UpperDiv(Upper);
733 ConstantRange Union(DstTySize, /*isFullSet=*/false);
734
735 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
736 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
737 // then we do the union with [MaxValue, Upper)
738 if (isUpperWrapped()) {
739 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
740 // truncated range.
741 if (Upper.getActiveBits() > DstTySize ||
742 Upper.countTrailingOnes() == DstTySize)
743 return getFull(DstTySize);
744
745 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
746 UpperDiv.setAllBits();
747
748 // Union covers the MaxValue case, so return if the remaining range is just
749 // MaxValue(DstTy).
750 if (LowerDiv == UpperDiv)
751 return Union;
752 }
753
754 // Chop off the most significant bits that are past the destination bitwidth.
755 if (LowerDiv.getActiveBits() > DstTySize) {
756 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
757 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
758 LowerDiv -= Adjust;
759 UpperDiv -= Adjust;
760 }
761
762 unsigned UpperDivWidth = UpperDiv.getActiveBits();
763 if (UpperDivWidth <= DstTySize)
764 return ConstantRange(LowerDiv.trunc(DstTySize),
765 UpperDiv.trunc(DstTySize)).unionWith(Union);
766
767 // The truncated value wraps around. Check if we can do better than fullset.
768 if (UpperDivWidth == DstTySize + 1) {
769 // Clear the MSB so that UpperDiv wraps around.
770 UpperDiv.clearBit(DstTySize);
771 if (UpperDiv.ult(LowerDiv))
772 return ConstantRange(LowerDiv.trunc(DstTySize),
773 UpperDiv.trunc(DstTySize)).unionWith(Union);
774 }
775
776 return getFull(DstTySize);
777 }
778
zextOrTrunc(uint32_t DstTySize) const779 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
780 unsigned SrcTySize = getBitWidth();
781 if (SrcTySize > DstTySize)
782 return truncate(DstTySize);
783 if (SrcTySize < DstTySize)
784 return zeroExtend(DstTySize);
785 return *this;
786 }
787
sextOrTrunc(uint32_t DstTySize) const788 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
789 unsigned SrcTySize = getBitWidth();
790 if (SrcTySize > DstTySize)
791 return truncate(DstTySize);
792 if (SrcTySize < DstTySize)
793 return signExtend(DstTySize);
794 return *this;
795 }
796
binaryOp(Instruction::BinaryOps BinOp,const ConstantRange & Other) const797 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
798 const ConstantRange &Other) const {
799 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
800
801 switch (BinOp) {
802 case Instruction::Add:
803 return add(Other);
804 case Instruction::Sub:
805 return sub(Other);
806 case Instruction::Mul:
807 return multiply(Other);
808 case Instruction::UDiv:
809 return udiv(Other);
810 case Instruction::SDiv:
811 return sdiv(Other);
812 case Instruction::URem:
813 return urem(Other);
814 case Instruction::SRem:
815 return srem(Other);
816 case Instruction::Shl:
817 return shl(Other);
818 case Instruction::LShr:
819 return lshr(Other);
820 case Instruction::AShr:
821 return ashr(Other);
822 case Instruction::And:
823 return binaryAnd(Other);
824 case Instruction::Or:
825 return binaryOr(Other);
826 case Instruction::Xor:
827 return binaryXor(Other);
828 // Note: floating point operations applied to abstract ranges are just
829 // ideal integer operations with a lossy representation
830 case Instruction::FAdd:
831 return add(Other);
832 case Instruction::FSub:
833 return sub(Other);
834 case Instruction::FMul:
835 return multiply(Other);
836 default:
837 // Conservatively return getFull set.
838 return getFull();
839 }
840 }
841
overflowingBinaryOp(Instruction::BinaryOps BinOp,const ConstantRange & Other,unsigned NoWrapKind) const842 ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,
843 const ConstantRange &Other,
844 unsigned NoWrapKind) const {
845 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
846
847 switch (BinOp) {
848 case Instruction::Add:
849 return addWithNoWrap(Other, NoWrapKind);
850 case Instruction::Sub:
851 return subWithNoWrap(Other, NoWrapKind);
852 default:
853 // Don't know about this Overflowing Binary Operation.
854 // Conservatively fallback to plain binop handling.
855 return binaryOp(BinOp, Other);
856 }
857 }
858
isIntrinsicSupported(Intrinsic::ID IntrinsicID)859 bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) {
860 switch (IntrinsicID) {
861 case Intrinsic::uadd_sat:
862 case Intrinsic::usub_sat:
863 case Intrinsic::sadd_sat:
864 case Intrinsic::ssub_sat:
865 case Intrinsic::umin:
866 case Intrinsic::umax:
867 case Intrinsic::smin:
868 case Intrinsic::smax:
869 case Intrinsic::abs:
870 return true;
871 default:
872 return false;
873 }
874 }
875
intrinsic(Intrinsic::ID IntrinsicID,ArrayRef<ConstantRange> Ops)876 ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID,
877 ArrayRef<ConstantRange> Ops) {
878 switch (IntrinsicID) {
879 case Intrinsic::uadd_sat:
880 return Ops[0].uadd_sat(Ops[1]);
881 case Intrinsic::usub_sat:
882 return Ops[0].usub_sat(Ops[1]);
883 case Intrinsic::sadd_sat:
884 return Ops[0].sadd_sat(Ops[1]);
885 case Intrinsic::ssub_sat:
886 return Ops[0].ssub_sat(Ops[1]);
887 case Intrinsic::umin:
888 return Ops[0].umin(Ops[1]);
889 case Intrinsic::umax:
890 return Ops[0].umax(Ops[1]);
891 case Intrinsic::smin:
892 return Ops[0].smin(Ops[1]);
893 case Intrinsic::smax:
894 return Ops[0].smax(Ops[1]);
895 case Intrinsic::abs: {
896 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
897 assert(IntMinIsPoison && "Must be known (immarg)");
898 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
899 return Ops[0].abs(IntMinIsPoison->getBoolValue());
900 }
901 default:
902 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
903 llvm_unreachable("Unsupported intrinsic");
904 }
905 }
906
907 ConstantRange
add(const ConstantRange & Other) const908 ConstantRange::add(const ConstantRange &Other) const {
909 if (isEmptySet() || Other.isEmptySet())
910 return getEmpty();
911 if (isFullSet() || Other.isFullSet())
912 return getFull();
913
914 APInt NewLower = getLower() + Other.getLower();
915 APInt NewUpper = getUpper() + Other.getUpper() - 1;
916 if (NewLower == NewUpper)
917 return getFull();
918
919 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
920 if (X.isSizeStrictlySmallerThan(*this) ||
921 X.isSizeStrictlySmallerThan(Other))
922 // We've wrapped, therefore, full set.
923 return getFull();
924 return X;
925 }
926
addWithNoWrap(const ConstantRange & Other,unsigned NoWrapKind,PreferredRangeType RangeType) const927 ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
928 unsigned NoWrapKind,
929 PreferredRangeType RangeType) const {
930 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
931 // (X is from this, and Y is from Other)
932 if (isEmptySet() || Other.isEmptySet())
933 return getEmpty();
934 if (isFullSet() && Other.isFullSet())
935 return getFull();
936
937 using OBO = OverflowingBinaryOperator;
938 ConstantRange Result = add(Other);
939
940 // If an overflow happens for every value pair in these two constant ranges,
941 // we must return Empty set. In this case, we get that for free, because we
942 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
943 // in an empty set.
944
945 if (NoWrapKind & OBO::NoSignedWrap)
946 Result = Result.intersectWith(sadd_sat(Other), RangeType);
947
948 if (NoWrapKind & OBO::NoUnsignedWrap)
949 Result = Result.intersectWith(uadd_sat(Other), RangeType);
950
951 return Result;
952 }
953
954 ConstantRange
sub(const ConstantRange & Other) const955 ConstantRange::sub(const ConstantRange &Other) const {
956 if (isEmptySet() || Other.isEmptySet())
957 return getEmpty();
958 if (isFullSet() || Other.isFullSet())
959 return getFull();
960
961 APInt NewLower = getLower() - Other.getUpper() + 1;
962 APInt NewUpper = getUpper() - Other.getLower();
963 if (NewLower == NewUpper)
964 return getFull();
965
966 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
967 if (X.isSizeStrictlySmallerThan(*this) ||
968 X.isSizeStrictlySmallerThan(Other))
969 // We've wrapped, therefore, full set.
970 return getFull();
971 return X;
972 }
973
subWithNoWrap(const ConstantRange & Other,unsigned NoWrapKind,PreferredRangeType RangeType) const974 ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,
975 unsigned NoWrapKind,
976 PreferredRangeType RangeType) const {
977 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
978 // (X is from this, and Y is from Other)
979 if (isEmptySet() || Other.isEmptySet())
980 return getEmpty();
981 if (isFullSet() && Other.isFullSet())
982 return getFull();
983
984 using OBO = OverflowingBinaryOperator;
985 ConstantRange Result = sub(Other);
986
987 // If an overflow happens for every value pair in these two constant ranges,
988 // we must return Empty set. In signed case, we get that for free, because we
989 // get lucky that intersection of sub() with ssub_sat() results in an
990 // empty set. But for unsigned we must perform the overflow check manually.
991
992 if (NoWrapKind & OBO::NoSignedWrap)
993 Result = Result.intersectWith(ssub_sat(Other), RangeType);
994
995 if (NoWrapKind & OBO::NoUnsignedWrap) {
996 if (getUnsignedMax().ult(Other.getUnsignedMin()))
997 return getEmpty(); // Always overflows.
998 Result = Result.intersectWith(usub_sat(Other), RangeType);
999 }
1000
1001 return Result;
1002 }
1003
1004 ConstantRange
multiply(const ConstantRange & Other) const1005 ConstantRange::multiply(const ConstantRange &Other) const {
1006 // TODO: If either operand is a single element and the multiply is known to
1007 // be non-wrapping, round the result min and max value to the appropriate
1008 // multiple of that element. If wrapping is possible, at least adjust the
1009 // range according to the greatest power-of-two factor of the single element.
1010
1011 if (isEmptySet() || Other.isEmptySet())
1012 return getEmpty();
1013
1014 // Multiplication is signedness-independent. However different ranges can be
1015 // obtained depending on how the input ranges are treated. These different
1016 // ranges are all conservatively correct, but one might be better than the
1017 // other. We calculate two ranges; one treating the inputs as unsigned
1018 // and the other signed, then return the smallest of these ranges.
1019
1020 // Unsigned range first.
1021 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
1022 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
1023 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
1024 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
1025
1026 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1027 this_max * Other_max + 1);
1028 ConstantRange UR = Result_zext.truncate(getBitWidth());
1029
1030 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1031 // from one positive number to another which is as good as we can generate.
1032 // In this case, skip the extra work of generating signed ranges which aren't
1033 // going to be better than this range.
1034 if (!UR.isUpperWrapped() &&
1035 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
1036 return UR;
1037
1038 // Now the signed range. Because we could be dealing with negative numbers
1039 // here, the lower bound is the smallest of the cartesian product of the
1040 // lower and upper ranges; for example:
1041 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1042 // Similarly for the upper bound, swapping min for max.
1043
1044 this_min = getSignedMin().sext(getBitWidth() * 2);
1045 this_max = getSignedMax().sext(getBitWidth() * 2);
1046 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1047 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1048
1049 auto L = {this_min * Other_min, this_min * Other_max,
1050 this_max * Other_min, this_max * Other_max};
1051 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1052 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1053 ConstantRange SR = Result_sext.truncate(getBitWidth());
1054
1055 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
1056 }
1057
1058 ConstantRange
smax(const ConstantRange & Other) const1059 ConstantRange::smax(const ConstantRange &Other) const {
1060 // X smax Y is: range(smax(X_smin, Y_smin),
1061 // smax(X_smax, Y_smax))
1062 if (isEmptySet() || Other.isEmptySet())
1063 return getEmpty();
1064 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1065 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1066 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1067 if (isSignWrappedSet() || Other.isSignWrappedSet())
1068 return Res.intersectWith(unionWith(Other, Signed), Signed);
1069 return Res;
1070 }
1071
1072 ConstantRange
umax(const ConstantRange & Other) const1073 ConstantRange::umax(const ConstantRange &Other) const {
1074 // X umax Y is: range(umax(X_umin, Y_umin),
1075 // umax(X_umax, Y_umax))
1076 if (isEmptySet() || Other.isEmptySet())
1077 return getEmpty();
1078 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1079 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1080 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1081 if (isWrappedSet() || Other.isWrappedSet())
1082 return Res.intersectWith(unionWith(Other, Unsigned), Unsigned);
1083 return Res;
1084 }
1085
1086 ConstantRange
smin(const ConstantRange & Other) const1087 ConstantRange::smin(const ConstantRange &Other) const {
1088 // X smin Y is: range(smin(X_smin, Y_smin),
1089 // smin(X_smax, Y_smax))
1090 if (isEmptySet() || Other.isEmptySet())
1091 return getEmpty();
1092 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
1093 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
1094 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1095 if (isSignWrappedSet() || Other.isSignWrappedSet())
1096 return Res.intersectWith(unionWith(Other, Signed), Signed);
1097 return Res;
1098 }
1099
1100 ConstantRange
umin(const ConstantRange & Other) const1101 ConstantRange::umin(const ConstantRange &Other) const {
1102 // X umin Y is: range(umin(X_umin, Y_umin),
1103 // umin(X_umax, Y_umax))
1104 if (isEmptySet() || Other.isEmptySet())
1105 return getEmpty();
1106 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1107 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1108 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1109 if (isWrappedSet() || Other.isWrappedSet())
1110 return Res.intersectWith(unionWith(Other, Unsigned), Unsigned);
1111 return Res;
1112 }
1113
1114 ConstantRange
udiv(const ConstantRange & RHS) const1115 ConstantRange::udiv(const ConstantRange &RHS) const {
1116 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1117 return getEmpty();
1118
1119 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
1120
1121 APInt RHS_umin = RHS.getUnsignedMin();
1122 if (RHS_umin.isNullValue()) {
1123 // We want the lowest value in RHS excluding zero. Usually that would be 1
1124 // except for a range in the form of [X, 1) in which case it would be X.
1125 if (RHS.getUpper() == 1)
1126 RHS_umin = RHS.getLower();
1127 else
1128 RHS_umin = 1;
1129 }
1130
1131 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1132 return getNonEmpty(std::move(Lower), std::move(Upper));
1133 }
1134
sdiv(const ConstantRange & RHS) const1135 ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {
1136 // We split up the LHS and RHS into positive and negative components
1137 // and then also compute the positive and negative components of the result
1138 // separately by combining division results with the appropriate signs.
1139 APInt Zero = APInt::getNullValue(getBitWidth());
1140 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
1141 ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin);
1142 ConstantRange NegFilter(SignedMin, Zero);
1143 ConstantRange PosL = intersectWith(PosFilter);
1144 ConstantRange NegL = intersectWith(NegFilter);
1145 ConstantRange PosR = RHS.intersectWith(PosFilter);
1146 ConstantRange NegR = RHS.intersectWith(NegFilter);
1147
1148 ConstantRange PosRes = getEmpty();
1149 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1150 // pos / pos = pos.
1151 PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1152 (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1153
1154 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1155 // neg / neg = pos.
1156 //
1157 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1158 // IR level, so we'll want to exclude this case when calculating bounds.
1159 // (For APInts the operation is well-defined and yields SignedMin.) We
1160 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1161 APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1162 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) {
1163 // Remove -1 from the LHS. Skip if it's the only element, as this would
1164 // leave us with an empty set.
1165 if (!NegR.Lower.isAllOnesValue()) {
1166 APInt AdjNegRUpper;
1167 if (RHS.Lower.isAllOnesValue())
1168 // Negative part of [-1, X] without -1 is [SignedMin, X].
1169 AdjNegRUpper = RHS.Upper;
1170 else
1171 // [X, -1] without -1 is [X, -2].
1172 AdjNegRUpper = NegR.Upper - 1;
1173
1174 PosRes = PosRes.unionWith(
1175 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1176 }
1177
1178 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1179 // would leave us with an empty set.
1180 if (NegL.Upper != SignedMin + 1) {
1181 APInt AdjNegLLower;
1182 if (Upper == SignedMin + 1)
1183 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1184 AdjNegLLower = Lower;
1185 else
1186 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1187 AdjNegLLower = NegL.Lower + 1;
1188
1189 PosRes = PosRes.unionWith(
1190 ConstantRange(std::move(Lo),
1191 AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1192 }
1193 } else {
1194 PosRes = PosRes.unionWith(
1195 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1196 }
1197 }
1198
1199 ConstantRange NegRes = getEmpty();
1200 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1201 // pos / neg = neg.
1202 NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1203 PosL.Lower.sdiv(NegR.Lower) + 1);
1204
1205 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1206 // neg / pos = neg.
1207 NegRes = NegRes.unionWith(
1208 ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1209 (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1210
1211 // Prefer a non-wrapping signed range here.
1212 ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
1213
1214 // Preserve the zero that we dropped when splitting the LHS by sign.
1215 if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1216 Res = Res.unionWith(ConstantRange(Zero));
1217 return Res;
1218 }
1219
urem(const ConstantRange & RHS) const1220 ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
1221 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1222 return getEmpty();
1223
1224 // L % R for L < R is L.
1225 if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1226 return *this;
1227
1228 // L % R is <= L and < R.
1229 APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1230 return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
1231 }
1232
srem(const ConstantRange & RHS) const1233 ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1234 if (isEmptySet() || RHS.isEmptySet())
1235 return getEmpty();
1236
1237 ConstantRange AbsRHS = RHS.abs();
1238 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1239 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1240
1241 // Modulus by zero is UB.
1242 if (MaxAbsRHS.isNullValue())
1243 return getEmpty();
1244
1245 if (MinAbsRHS.isNullValue())
1246 ++MinAbsRHS;
1247
1248 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1249
1250 if (MinLHS.isNonNegative()) {
1251 // L % R for L < R is L.
1252 if (MaxLHS.ult(MinAbsRHS))
1253 return *this;
1254
1255 // L % R is <= L and < R.
1256 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1257 return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1258 }
1259
1260 // Same basic logic as above, but the result is negative.
1261 if (MaxLHS.isNegative()) {
1262 if (MinLHS.ugt(-MinAbsRHS))
1263 return *this;
1264
1265 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1266 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1267 }
1268
1269 // LHS range crosses zero.
1270 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1271 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1272 return ConstantRange(std::move(Lower), std::move(Upper));
1273 }
1274
binaryNot() const1275 ConstantRange ConstantRange::binaryNot() const {
1276 return ConstantRange(APInt::getAllOnesValue(getBitWidth())).sub(*this);
1277 }
1278
1279 ConstantRange
binaryAnd(const ConstantRange & Other) const1280 ConstantRange::binaryAnd(const ConstantRange &Other) const {
1281 if (isEmptySet() || Other.isEmptySet())
1282 return getEmpty();
1283
1284 // Use APInt's implementation of AND for single element ranges.
1285 if (isSingleElement() && Other.isSingleElement())
1286 return {*getSingleElement() & *Other.getSingleElement()};
1287
1288 // TODO: replace this with something less conservative
1289
1290 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
1291 return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1292 }
1293
1294 ConstantRange
binaryOr(const ConstantRange & Other) const1295 ConstantRange::binaryOr(const ConstantRange &Other) const {
1296 if (isEmptySet() || Other.isEmptySet())
1297 return getEmpty();
1298
1299 // Use APInt's implementation of OR for single element ranges.
1300 if (isSingleElement() && Other.isSingleElement())
1301 return {*getSingleElement() | *Other.getSingleElement()};
1302
1303 // TODO: replace this with something less conservative
1304
1305 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1306 return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1307 }
1308
binaryXor(const ConstantRange & Other) const1309 ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {
1310 if (isEmptySet() || Other.isEmptySet())
1311 return getEmpty();
1312
1313 // Use APInt's implementation of XOR for single element ranges.
1314 if (isSingleElement() && Other.isSingleElement())
1315 return {*getSingleElement() ^ *Other.getSingleElement()};
1316
1317 // Special-case binary complement, since we can give a precise answer.
1318 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnesValue())
1319 return binaryNot();
1320 if (isSingleElement() && getSingleElement()->isAllOnesValue())
1321 return Other.binaryNot();
1322
1323 // TODO: replace this with something less conservative
1324 return getFull();
1325 }
1326
1327 ConstantRange
shl(const ConstantRange & Other) const1328 ConstantRange::shl(const ConstantRange &Other) const {
1329 if (isEmptySet() || Other.isEmptySet())
1330 return getEmpty();
1331
1332 APInt max = getUnsignedMax();
1333 APInt Other_umax = Other.getUnsignedMax();
1334
1335 // If we are shifting by maximum amount of
1336 // zero return return the original range.
1337 if (Other_umax.isNullValue())
1338 return *this;
1339 // there's overflow!
1340 if (Other_umax.ugt(max.countLeadingZeros()))
1341 return getFull();
1342
1343 // FIXME: implement the other tricky cases
1344
1345 APInt min = getUnsignedMin();
1346 min <<= Other.getUnsignedMin();
1347 max <<= Other_umax;
1348
1349 return ConstantRange(std::move(min), std::move(max) + 1);
1350 }
1351
1352 ConstantRange
lshr(const ConstantRange & Other) const1353 ConstantRange::lshr(const ConstantRange &Other) const {
1354 if (isEmptySet() || Other.isEmptySet())
1355 return getEmpty();
1356
1357 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1358 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1359 return getNonEmpty(std::move(min), std::move(max));
1360 }
1361
1362 ConstantRange
ashr(const ConstantRange & Other) const1363 ConstantRange::ashr(const ConstantRange &Other) const {
1364 if (isEmptySet() || Other.isEmptySet())
1365 return getEmpty();
1366
1367 // May straddle zero, so handle both positive and negative cases.
1368 // 'PosMax' is the upper bound of the result of the ashr
1369 // operation, when Upper of the LHS of ashr is a non-negative.
1370 // number. Since ashr of a non-negative number will result in a
1371 // smaller number, the Upper value of LHS is shifted right with
1372 // the minimum value of 'Other' instead of the maximum value.
1373 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1374
1375 // 'PosMin' is the lower bound of the result of the ashr
1376 // operation, when Lower of the LHS is a non-negative number.
1377 // Since ashr of a non-negative number will result in a smaller
1378 // number, the Lower value of LHS is shifted right with the
1379 // maximum value of 'Other'.
1380 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1381
1382 // 'NegMax' is the upper bound of the result of the ashr
1383 // operation, when Upper of the LHS of ashr is a negative number.
1384 // Since 'ashr' of a negative number will result in a bigger
1385 // number, the Upper value of LHS is shifted right with the
1386 // maximum value of 'Other'.
1387 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1388
1389 // 'NegMin' is the lower bound of the result of the ashr
1390 // operation, when Lower of the LHS of ashr is a negative number.
1391 // Since 'ashr' of a negative number will result in a bigger
1392 // number, the Lower value of LHS is shifted right with the
1393 // minimum value of 'Other'.
1394 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1395
1396 APInt max, min;
1397 if (getSignedMin().isNonNegative()) {
1398 // Upper and Lower of LHS are non-negative.
1399 min = PosMin;
1400 max = PosMax;
1401 } else if (getSignedMax().isNegative()) {
1402 // Upper and Lower of LHS are negative.
1403 min = NegMin;
1404 max = NegMax;
1405 } else {
1406 // Upper is non-negative and Lower is negative.
1407 min = NegMin;
1408 max = PosMax;
1409 }
1410 return getNonEmpty(std::move(min), std::move(max));
1411 }
1412
uadd_sat(const ConstantRange & Other) const1413 ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {
1414 if (isEmptySet() || Other.isEmptySet())
1415 return getEmpty();
1416
1417 APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1418 APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1419 return getNonEmpty(std::move(NewL), std::move(NewU));
1420 }
1421
sadd_sat(const ConstantRange & Other) const1422 ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {
1423 if (isEmptySet() || Other.isEmptySet())
1424 return getEmpty();
1425
1426 APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1427 APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1428 return getNonEmpty(std::move(NewL), std::move(NewU));
1429 }
1430
usub_sat(const ConstantRange & Other) const1431 ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {
1432 if (isEmptySet() || Other.isEmptySet())
1433 return getEmpty();
1434
1435 APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1436 APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1437 return getNonEmpty(std::move(NewL), std::move(NewU));
1438 }
1439
ssub_sat(const ConstantRange & Other) const1440 ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
1441 if (isEmptySet() || Other.isEmptySet())
1442 return getEmpty();
1443
1444 APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1445 APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1446 return getNonEmpty(std::move(NewL), std::move(NewU));
1447 }
1448
umul_sat(const ConstantRange & Other) const1449 ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {
1450 if (isEmptySet() || Other.isEmptySet())
1451 return getEmpty();
1452
1453 APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
1454 APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
1455 return getNonEmpty(std::move(NewL), std::move(NewU));
1456 }
1457
smul_sat(const ConstantRange & Other) const1458 ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {
1459 if (isEmptySet() || Other.isEmptySet())
1460 return getEmpty();
1461
1462 // Because we could be dealing with negative numbers here, the lower bound is
1463 // the smallest of the cartesian product of the lower and upper ranges;
1464 // for example:
1465 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1466 // Similarly for the upper bound, swapping min for max.
1467
1468 APInt this_min = getSignedMin().sext(getBitWidth() * 2);
1469 APInt this_max = getSignedMax().sext(getBitWidth() * 2);
1470 APInt Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1471 APInt Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1472
1473 auto L = {this_min * Other_min, this_min * Other_max, this_max * Other_min,
1474 this_max * Other_max};
1475 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1476
1477 // Note that we wanted to perform signed saturating multiplication,
1478 // so since we performed plain multiplication in twice the bitwidth,
1479 // we need to perform signed saturating truncation.
1480 return getNonEmpty(std::min(L, Compare).truncSSat(getBitWidth()),
1481 std::max(L, Compare).truncSSat(getBitWidth()) + 1);
1482 }
1483
ushl_sat(const ConstantRange & Other) const1484 ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
1485 if (isEmptySet() || Other.isEmptySet())
1486 return getEmpty();
1487
1488 APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
1489 APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
1490 return getNonEmpty(std::move(NewL), std::move(NewU));
1491 }
1492
sshl_sat(const ConstantRange & Other) const1493 ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {
1494 if (isEmptySet() || Other.isEmptySet())
1495 return getEmpty();
1496
1497 APInt Min = getSignedMin(), Max = getSignedMax();
1498 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1499 APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1500 APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1501 return getNonEmpty(std::move(NewL), std::move(NewU));
1502 }
1503
inverse() const1504 ConstantRange ConstantRange::inverse() const {
1505 if (isFullSet())
1506 return getEmpty();
1507 if (isEmptySet())
1508 return getFull();
1509 return ConstantRange(Upper, Lower);
1510 }
1511
abs(bool IntMinIsPoison) const1512 ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1513 if (isEmptySet())
1514 return getEmpty();
1515
1516 if (isSignWrappedSet()) {
1517 APInt Lo;
1518 // Check whether the range crosses zero.
1519 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1520 Lo = APInt::getNullValue(getBitWidth());
1521 else
1522 Lo = APIntOps::umin(Lower, -Upper + 1);
1523
1524 // If SignedMin is not poison, then it is included in the result range.
1525 if (IntMinIsPoison)
1526 return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()));
1527 else
1528 return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1);
1529 }
1530
1531 APInt SMin = getSignedMin(), SMax = getSignedMax();
1532
1533 // Skip SignedMin if it is poison.
1534 if (IntMinIsPoison && SMin.isMinSignedValue()) {
1535 // The range may become empty if it *only* contains SignedMin.
1536 if (SMax.isMinSignedValue())
1537 return getEmpty();
1538 ++SMin;
1539 }
1540
1541 // All non-negative.
1542 if (SMin.isNonNegative())
1543 return *this;
1544
1545 // All negative.
1546 if (SMax.isNegative())
1547 return ConstantRange(-SMax, -SMin + 1);
1548
1549 // Range crosses zero.
1550 return ConstantRange(APInt::getNullValue(getBitWidth()),
1551 APIntOps::umax(-SMin, SMax) + 1);
1552 }
1553
unsignedAddMayOverflow(const ConstantRange & Other) const1554 ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
1555 const ConstantRange &Other) const {
1556 if (isEmptySet() || Other.isEmptySet())
1557 return OverflowResult::MayOverflow;
1558
1559 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1560 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1561
1562 // a u+ b overflows high iff a u> ~b.
1563 if (Min.ugt(~OtherMin))
1564 return OverflowResult::AlwaysOverflowsHigh;
1565 if (Max.ugt(~OtherMax))
1566 return OverflowResult::MayOverflow;
1567 return OverflowResult::NeverOverflows;
1568 }
1569
signedAddMayOverflow(const ConstantRange & Other) const1570 ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
1571 const ConstantRange &Other) const {
1572 if (isEmptySet() || Other.isEmptySet())
1573 return OverflowResult::MayOverflow;
1574
1575 APInt Min = getSignedMin(), Max = getSignedMax();
1576 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1577
1578 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
1579 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
1580
1581 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1582 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1583 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1584 Min.sgt(SignedMax - OtherMin))
1585 return OverflowResult::AlwaysOverflowsHigh;
1586 if (Max.isNegative() && OtherMax.isNegative() &&
1587 Max.slt(SignedMin - OtherMax))
1588 return OverflowResult::AlwaysOverflowsLow;
1589
1590 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1591 Max.sgt(SignedMax - OtherMax))
1592 return OverflowResult::MayOverflow;
1593 if (Min.isNegative() && OtherMin.isNegative() &&
1594 Min.slt(SignedMin - OtherMin))
1595 return OverflowResult::MayOverflow;
1596
1597 return OverflowResult::NeverOverflows;
1598 }
1599
unsignedSubMayOverflow(const ConstantRange & Other) const1600 ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
1601 const ConstantRange &Other) const {
1602 if (isEmptySet() || Other.isEmptySet())
1603 return OverflowResult::MayOverflow;
1604
1605 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1606 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1607
1608 // a u- b overflows low iff a u< b.
1609 if (Max.ult(OtherMin))
1610 return OverflowResult::AlwaysOverflowsLow;
1611 if (Min.ult(OtherMax))
1612 return OverflowResult::MayOverflow;
1613 return OverflowResult::NeverOverflows;
1614 }
1615
signedSubMayOverflow(const ConstantRange & Other) const1616 ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
1617 const ConstantRange &Other) const {
1618 if (isEmptySet() || Other.isEmptySet())
1619 return OverflowResult::MayOverflow;
1620
1621 APInt Min = getSignedMin(), Max = getSignedMax();
1622 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1623
1624 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
1625 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
1626
1627 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1628 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1629 if (Min.isNonNegative() && OtherMax.isNegative() &&
1630 Min.sgt(SignedMax + OtherMax))
1631 return OverflowResult::AlwaysOverflowsHigh;
1632 if (Max.isNegative() && OtherMin.isNonNegative() &&
1633 Max.slt(SignedMin + OtherMin))
1634 return OverflowResult::AlwaysOverflowsLow;
1635
1636 if (Max.isNonNegative() && OtherMin.isNegative() &&
1637 Max.sgt(SignedMax + OtherMin))
1638 return OverflowResult::MayOverflow;
1639 if (Min.isNegative() && OtherMax.isNonNegative() &&
1640 Min.slt(SignedMin + OtherMax))
1641 return OverflowResult::MayOverflow;
1642
1643 return OverflowResult::NeverOverflows;
1644 }
1645
unsignedMulMayOverflow(const ConstantRange & Other) const1646 ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
1647 const ConstantRange &Other) const {
1648 if (isEmptySet() || Other.isEmptySet())
1649 return OverflowResult::MayOverflow;
1650
1651 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1652 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1653 bool Overflow;
1654
1655 (void) Min.umul_ov(OtherMin, Overflow);
1656 if (Overflow)
1657 return OverflowResult::AlwaysOverflowsHigh;
1658
1659 (void) Max.umul_ov(OtherMax, Overflow);
1660 if (Overflow)
1661 return OverflowResult::MayOverflow;
1662
1663 return OverflowResult::NeverOverflows;
1664 }
1665
print(raw_ostream & OS) const1666 void ConstantRange::print(raw_ostream &OS) const {
1667 if (isFullSet())
1668 OS << "full-set";
1669 else if (isEmptySet())
1670 OS << "empty-set";
1671 else
1672 OS << "[" << Lower << "," << Upper << ")";
1673 }
1674
1675 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const1676 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1677 print(dbgs());
1678 }
1679 #endif
1680
getConstantRangeFromMetadata(const MDNode & Ranges)1681 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1682 const unsigned NumRanges = Ranges.getNumOperands() / 2;
1683 assert(NumRanges >= 1 && "Must have at least one range!");
1684 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1685
1686 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1687 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1688
1689 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1690
1691 for (unsigned i = 1; i < NumRanges; ++i) {
1692 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1693 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1694
1695 // Note: unionWith will potentially create a range that contains values not
1696 // contained in any of the original N ranges.
1697 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1698 }
1699
1700 return CR;
1701 }
1702