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#include <optional>
41
42using namespace llvm;
43
44ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
45 : Lower(Full ? APInt::getMaxValue(numBits: BitWidth) : APInt::getMinValue(numBits: BitWidth)),
46 Upper(Lower) {}
47
48ConstantRange::ConstantRange(APInt V)
49 : Lower(std::move(V)), Upper(Lower + 1) {}
50
51ConstantRange::ConstantRange(APInt L, APInt U)
52 : Lower(std::move(L)), Upper(std::move(U)) {
53 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
54 "ConstantRange with unequal bit widths");
55 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
56 "Lower == Upper, but they aren't min or max value!");
57}
58
59ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
60 bool IsSigned) {
61 if (Known.hasConflict())
62 return getEmpty(BitWidth: Known.getBitWidth());
63 if (Known.isUnknown())
64 return getFull(BitWidth: Known.getBitWidth());
65
66 // For unsigned ranges, or signed ranges with known sign bit, create a simple
67 // range between the smallest and largest possible value.
68 if (!IsSigned || Known.isNegative() || Known.isNonNegative())
69 return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);
70
71 // If we don't know the sign bit, pick the lower bound as a negative number
72 // and the upper bound as a non-negative one.
73 APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();
74 Lower.setSignBit();
75 Upper.clearSignBit();
76 return ConstantRange(Lower, Upper + 1);
77}
78
79KnownBits ConstantRange::toKnownBits() const {
80 // TODO: We could return conflicting known bits here, but consumers are
81 // likely not prepared for that.
82 if (isEmptySet())
83 return KnownBits(getBitWidth());
84
85 // We can only retain the top bits that are the same between min and max.
86 APInt Min = getUnsignedMin();
87 APInt Max = getUnsignedMax();
88 KnownBits Known = KnownBits::makeConstant(C: Min);
89 if (std::optional<unsigned> DifferentBit =
90 APIntOps::GetMostSignificantDifferentBit(A: Min, B: Max)) {
91 Known.Zero.clearLowBits(loBits: *DifferentBit + 1);
92 Known.One.clearLowBits(loBits: *DifferentBit + 1);
93 }
94 return Known;
95}
96
97ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
98 const ConstantRange &CR) {
99 if (CR.isEmptySet())
100 return CR;
101
102 uint32_t W = CR.getBitWidth();
103 switch (Pred) {
104 default:
105 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
106 case CmpInst::ICMP_EQ:
107 return CR;
108 case CmpInst::ICMP_NE:
109 if (CR.isSingleElement())
110 return ConstantRange(CR.getUpper(), CR.getLower());
111 return getFull(BitWidth: W);
112 case CmpInst::ICMP_ULT: {
113 APInt UMax(CR.getUnsignedMax());
114 if (UMax.isMinValue())
115 return getEmpty(BitWidth: W);
116 return ConstantRange(APInt::getMinValue(numBits: W), std::move(UMax));
117 }
118 case CmpInst::ICMP_SLT: {
119 APInt SMax(CR.getSignedMax());
120 if (SMax.isMinSignedValue())
121 return getEmpty(BitWidth: W);
122 return ConstantRange(APInt::getSignedMinValue(numBits: W), std::move(SMax));
123 }
124 case CmpInst::ICMP_ULE:
125 return getNonEmpty(Lower: APInt::getMinValue(numBits: W), Upper: CR.getUnsignedMax() + 1);
126 case CmpInst::ICMP_SLE:
127 return getNonEmpty(Lower: APInt::getSignedMinValue(numBits: W), Upper: CR.getSignedMax() + 1);
128 case CmpInst::ICMP_UGT: {
129 APInt UMin(CR.getUnsignedMin());
130 if (UMin.isMaxValue())
131 return getEmpty(BitWidth: W);
132 return ConstantRange(std::move(UMin) + 1, APInt::getZero(numBits: W));
133 }
134 case CmpInst::ICMP_SGT: {
135 APInt SMin(CR.getSignedMin());
136 if (SMin.isMaxSignedValue())
137 return getEmpty(BitWidth: W);
138 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(numBits: W));
139 }
140 case CmpInst::ICMP_UGE:
141 return getNonEmpty(Lower: CR.getUnsignedMin(), Upper: APInt::getZero(numBits: W));
142 case CmpInst::ICMP_SGE:
143 return getNonEmpty(Lower: CR.getSignedMin(), Upper: APInt::getSignedMinValue(numBits: W));
144 }
145}
146
147ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
148 const ConstantRange &CR) {
149 // Follows from De-Morgan's laws:
150 //
151 // ~(~A union ~B) == A intersect B.
152 //
153 return makeAllowedICmpRegion(Pred: CmpInst::getInversePredicate(pred: Pred), CR)
154 .inverse();
155}
156
157ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
158 const APInt &C) {
159 // Computes the exact range that is equal to both the constant ranges returned
160 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
161 // when RHS is a singleton such as an APInt and so the assert is valid.
162 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
163 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
164 //
165 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
166 return makeAllowedICmpRegion(Pred, CR: C);
167}
168
169bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate(
170 const ConstantRange &CR1, const ConstantRange &CR2) {
171 if (CR1.isEmptySet() || CR2.isEmptySet())
172 return true;
173
174 return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
175 (CR1.isAllNegative() && CR2.isAllNegative());
176}
177
178bool ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
179 const ConstantRange &CR1, const ConstantRange &CR2) {
180 if (CR1.isEmptySet() || CR2.isEmptySet())
181 return true;
182
183 return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
184 (CR1.isAllNegative() && CR2.isAllNonNegative());
185}
186
187CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness(
188 CmpInst::Predicate Pred, const ConstantRange &CR1,
189 const ConstantRange &CR2) {
190 assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) &&
191 "Only for relational integer predicates!");
192
193 CmpInst::Predicate FlippedSignednessPred =
194 CmpInst::getFlippedSignednessPredicate(pred: Pred);
195
196 if (areInsensitiveToSignednessOfICmpPredicate(CR1, CR2))
197 return FlippedSignednessPred;
198
199 if (areInsensitiveToSignednessOfInvertedICmpPredicate(CR1, CR2))
200 return CmpInst::getInversePredicate(pred: FlippedSignednessPred);
201
202 return CmpInst::Predicate::BAD_ICMP_PREDICATE;
203}
204
205void ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
206 APInt &RHS, APInt &Offset) const {
207 Offset = APInt(getBitWidth(), 0);
208 if (isFullSet() || isEmptySet()) {
209 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
210 RHS = APInt(getBitWidth(), 0);
211 } else if (auto *OnlyElt = getSingleElement()) {
212 Pred = CmpInst::ICMP_EQ;
213 RHS = *OnlyElt;
214 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
215 Pred = CmpInst::ICMP_NE;
216 RHS = *OnlyMissingElt;
217 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
218 Pred =
219 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
220 RHS = getUpper();
221 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
222 Pred =
223 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
224 RHS = getLower();
225 } else {
226 Pred = CmpInst::ICMP_ULT;
227 RHS = getUpper() - getLower();
228 Offset = -getLower();
229 }
230
231 assert(ConstantRange::makeExactICmpRegion(Pred, RHS) == add(Offset) &&
232 "Bad result!");
233}
234
235bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
236 APInt &RHS) const {
237 APInt Offset;
238 getEquivalentICmp(Pred, RHS, Offset);
239 return Offset.isZero();
240}
241
242bool ConstantRange::icmp(CmpInst::Predicate Pred,
243 const ConstantRange &Other) const {
244 if (isEmptySet() || Other.isEmptySet())
245 return true;
246
247 switch (Pred) {
248 case CmpInst::ICMP_EQ:
249 if (const APInt *L = getSingleElement())
250 if (const APInt *R = Other.getSingleElement())
251 return *L == *R;
252 return false;
253 case CmpInst::ICMP_NE:
254 return inverse().contains(CR: Other);
255 case CmpInst::ICMP_ULT:
256 return getUnsignedMax().ult(RHS: Other.getUnsignedMin());
257 case CmpInst::ICMP_ULE:
258 return getUnsignedMax().ule(RHS: Other.getUnsignedMin());
259 case CmpInst::ICMP_UGT:
260 return getUnsignedMin().ugt(RHS: Other.getUnsignedMax());
261 case CmpInst::ICMP_UGE:
262 return getUnsignedMin().uge(RHS: Other.getUnsignedMax());
263 case CmpInst::ICMP_SLT:
264 return getSignedMax().slt(RHS: Other.getSignedMin());
265 case CmpInst::ICMP_SLE:
266 return getSignedMax().sle(RHS: Other.getSignedMin());
267 case CmpInst::ICMP_SGT:
268 return getSignedMin().sgt(RHS: Other.getSignedMax());
269 case CmpInst::ICMP_SGE:
270 return getSignedMin().sge(RHS: Other.getSignedMax());
271 default:
272 llvm_unreachable("Invalid ICmp predicate");
273 }
274}
275
276/// Exact mul nuw region for single element RHS.
277static ConstantRange makeExactMulNUWRegion(const APInt &V) {
278 unsigned BitWidth = V.getBitWidth();
279 if (V == 0)
280 return ConstantRange::getFull(BitWidth: V.getBitWidth());
281
282 return ConstantRange::getNonEmpty(
283 Lower: APIntOps::RoundingUDiv(A: APInt::getMinValue(numBits: BitWidth), B: V,
284 RM: APInt::Rounding::UP),
285 Upper: APIntOps::RoundingUDiv(A: APInt::getMaxValue(numBits: BitWidth), B: V,
286 RM: APInt::Rounding::DOWN) + 1);
287}
288
289/// Exact mul nsw region for single element RHS.
290static ConstantRange makeExactMulNSWRegion(const APInt &V) {
291 // Handle 0 and -1 separately to avoid division by zero or overflow.
292 unsigned BitWidth = V.getBitWidth();
293 if (V == 0)
294 return ConstantRange::getFull(BitWidth);
295
296 APInt MinValue = APInt::getSignedMinValue(numBits: BitWidth);
297 APInt MaxValue = APInt::getSignedMaxValue(numBits: BitWidth);
298 // e.g. Returning [-127, 127], represented as [-127, -128).
299 if (V.isAllOnes())
300 return ConstantRange(-MaxValue, MinValue);
301
302 APInt Lower, Upper;
303 if (V.isNegative()) {
304 Lower = APIntOps::RoundingSDiv(A: MaxValue, B: V, RM: APInt::Rounding::UP);
305 Upper = APIntOps::RoundingSDiv(A: MinValue, B: V, RM: APInt::Rounding::DOWN);
306 } else {
307 Lower = APIntOps::RoundingSDiv(A: MinValue, B: V, RM: APInt::Rounding::UP);
308 Upper = APIntOps::RoundingSDiv(A: MaxValue, B: V, RM: APInt::Rounding::DOWN);
309 }
310 return ConstantRange::getNonEmpty(Lower, Upper: Upper + 1);
311}
312
313ConstantRange
314ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
315 const ConstantRange &Other,
316 unsigned NoWrapKind) {
317 using OBO = OverflowingBinaryOperator;
318
319 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
320
321 assert((NoWrapKind == OBO::NoSignedWrap ||
322 NoWrapKind == OBO::NoUnsignedWrap) &&
323 "NoWrapKind invalid!");
324
325 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
326 unsigned BitWidth = Other.getBitWidth();
327
328 switch (BinOp) {
329 default:
330 llvm_unreachable("Unsupported binary op");
331
332 case Instruction::Add: {
333 if (Unsigned)
334 return getNonEmpty(Lower: APInt::getZero(numBits: BitWidth), Upper: -Other.getUnsignedMax());
335
336 APInt SignedMinVal = APInt::getSignedMinValue(numBits: BitWidth);
337 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
338 return getNonEmpty(
339 Lower: SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
340 Upper: SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
341 }
342
343 case Instruction::Sub: {
344 if (Unsigned)
345 return getNonEmpty(Lower: Other.getUnsignedMax(), Upper: APInt::getMinValue(numBits: BitWidth));
346
347 APInt SignedMinVal = APInt::getSignedMinValue(numBits: BitWidth);
348 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
349 return getNonEmpty(
350 Lower: SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
351 Upper: SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
352 }
353
354 case Instruction::Mul:
355 if (Unsigned)
356 return makeExactMulNUWRegion(V: Other.getUnsignedMax());
357
358 // Avoid one makeExactMulNSWRegion() call for the common case of constants.
359 if (const APInt *C = Other.getSingleElement())
360 return makeExactMulNSWRegion(V: *C);
361
362 return makeExactMulNSWRegion(V: Other.getSignedMin())
363 .intersectWith(CR: makeExactMulNSWRegion(V: Other.getSignedMax()));
364
365 case Instruction::Shl: {
366 // For given range of shift amounts, if we ignore all illegal shift amounts
367 // (that always produce poison), what shift amount range is left?
368 ConstantRange ShAmt = Other.intersectWith(
369 CR: ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));
370 if (ShAmt.isEmptySet()) {
371 // If the entire range of shift amounts is already poison-producing,
372 // then we can freely add more poison-producing flags ontop of that.
373 return getFull(BitWidth);
374 }
375 // There are some legal shift amounts, we can compute conservatively-correct
376 // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
377 // to be at most bitwidth-1, which results in most conservative range.
378 APInt ShAmtUMax = ShAmt.getUnsignedMax();
379 if (Unsigned)
380 return getNonEmpty(Lower: APInt::getZero(numBits: BitWidth),
381 Upper: APInt::getMaxValue(numBits: BitWidth).lshr(ShiftAmt: ShAmtUMax) + 1);
382 return getNonEmpty(Lower: APInt::getSignedMinValue(numBits: BitWidth).ashr(ShiftAmt: ShAmtUMax),
383 Upper: APInt::getSignedMaxValue(numBits: BitWidth).ashr(ShiftAmt: ShAmtUMax) + 1);
384 }
385 }
386}
387
388ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
389 const APInt &Other,
390 unsigned NoWrapKind) {
391 // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
392 // "for all" and "for any" coincide in this case.
393 return makeGuaranteedNoWrapRegion(BinOp, Other: ConstantRange(Other), NoWrapKind);
394}
395
396ConstantRange ConstantRange::makeMaskNotEqualRange(const APInt &Mask,
397 const APInt &C) {
398 unsigned BitWidth = Mask.getBitWidth();
399
400 if ((Mask & C) != C)
401 return getFull(BitWidth);
402
403 if (Mask.isZero())
404 return getEmpty(BitWidth);
405
406 // If (Val & Mask) != C, constrained to the non-equality being
407 // satisfiable, then the value must be larger than the lowest set bit of
408 // Mask, offset by constant C.
409 return ConstantRange::getNonEmpty(
410 Lower: APInt::getOneBitSet(numBits: BitWidth, BitNo: Mask.countr_zero()) + C, Upper: C);
411}
412
413bool ConstantRange::isFullSet() const {
414 return Lower == Upper && Lower.isMaxValue();
415}
416
417bool ConstantRange::isEmptySet() const {
418 return Lower == Upper && Lower.isMinValue();
419}
420
421bool ConstantRange::isWrappedSet() const {
422 return Lower.ugt(RHS: Upper) && !Upper.isZero();
423}
424
425bool ConstantRange::isUpperWrapped() const {
426 return Lower.ugt(RHS: Upper);
427}
428
429bool ConstantRange::isSignWrappedSet() const {
430 return Lower.sgt(RHS: Upper) && !Upper.isMinSignedValue();
431}
432
433bool ConstantRange::isUpperSignWrapped() const {
434 return Lower.sgt(RHS: Upper);
435}
436
437bool
438ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
439 assert(getBitWidth() == Other.getBitWidth());
440 if (isFullSet())
441 return false;
442 if (Other.isFullSet())
443 return true;
444 return (Upper - Lower).ult(RHS: Other.Upper - Other.Lower);
445}
446
447bool
448ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
449 // If this a full set, we need special handling to avoid needing an extra bit
450 // to represent the size.
451 if (isFullSet())
452 return MaxSize == 0 || APInt::getMaxValue(numBits: getBitWidth()).ugt(RHS: MaxSize - 1);
453
454 return (Upper - Lower).ugt(RHS: MaxSize);
455}
456
457bool ConstantRange::isAllNegative() const {
458 // Empty set is all negative, full set is not.
459 if (isEmptySet())
460 return true;
461 if (isFullSet())
462 return false;
463
464 return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
465}
466
467bool ConstantRange::isAllNonNegative() const {
468 // Empty and full set are automatically treated correctly.
469 return !isSignWrappedSet() && Lower.isNonNegative();
470}
471
472bool ConstantRange::isAllPositive() const {
473 // Empty set is all positive, full set is not.
474 if (isEmptySet())
475 return true;
476 if (isFullSet())
477 return false;
478
479 return !isSignWrappedSet() && Lower.isStrictlyPositive();
480}
481
482APInt ConstantRange::getUnsignedMax() const {
483 if (isFullSet() || isUpperWrapped())
484 return APInt::getMaxValue(numBits: getBitWidth());
485 return getUpper() - 1;
486}
487
488APInt ConstantRange::getUnsignedMin() const {
489 if (isFullSet() || isWrappedSet())
490 return APInt::getMinValue(numBits: getBitWidth());
491 return getLower();
492}
493
494APInt ConstantRange::getSignedMax() const {
495 if (isFullSet() || isUpperSignWrapped())
496 return APInt::getSignedMaxValue(numBits: getBitWidth());
497 return getUpper() - 1;
498}
499
500APInt ConstantRange::getSignedMin() const {
501 if (isFullSet() || isSignWrappedSet())
502 return APInt::getSignedMinValue(numBits: getBitWidth());
503 return getLower();
504}
505
506bool ConstantRange::contains(const APInt &V) const {
507 if (Lower == Upper)
508 return isFullSet();
509
510 if (!isUpperWrapped())
511 return Lower.ule(RHS: V) && V.ult(RHS: Upper);
512 return Lower.ule(RHS: V) || V.ult(RHS: Upper);
513}
514
515bool ConstantRange::contains(const ConstantRange &Other) const {
516 if (isFullSet() || Other.isEmptySet()) return true;
517 if (isEmptySet() || Other.isFullSet()) return false;
518
519 if (!isUpperWrapped()) {
520 if (Other.isUpperWrapped())
521 return false;
522
523 return Lower.ule(RHS: Other.getLower()) && Other.getUpper().ule(RHS: Upper);
524 }
525
526 if (!Other.isUpperWrapped())
527 return Other.getUpper().ule(RHS: Upper) ||
528 Lower.ule(RHS: Other.getLower());
529
530 return Other.getUpper().ule(RHS: Upper) && Lower.ule(RHS: Other.getLower());
531}
532
533unsigned ConstantRange::getActiveBits() const {
534 if (isEmptySet())
535 return 0;
536
537 return getUnsignedMax().getActiveBits();
538}
539
540unsigned ConstantRange::getMinSignedBits() const {
541 if (isEmptySet())
542 return 0;
543
544 return std::max(a: getSignedMin().getSignificantBits(),
545 b: getSignedMax().getSignificantBits());
546}
547
548ConstantRange ConstantRange::subtract(const APInt &Val) const {
549 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
550 // If the set is empty or full, don't modify the endpoints.
551 if (Lower == Upper)
552 return *this;
553 return ConstantRange(Lower - Val, Upper - Val);
554}
555
556ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
557 return intersectWith(CR: CR.inverse());
558}
559
560static ConstantRange getPreferredRange(
561 const ConstantRange &CR1, const ConstantRange &CR2,
562 ConstantRange::PreferredRangeType Type) {
563 if (Type == ConstantRange::Unsigned) {
564 if (!CR1.isWrappedSet() && CR2.isWrappedSet())
565 return CR1;
566 if (CR1.isWrappedSet() && !CR2.isWrappedSet())
567 return CR2;
568 } else if (Type == ConstantRange::Signed) {
569 if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
570 return CR1;
571 if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
572 return CR2;
573 }
574
575 if (CR1.isSizeStrictlySmallerThan(Other: CR2))
576 return CR1;
577 return CR2;
578}
579
580ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
581 PreferredRangeType Type) const {
582 assert(getBitWidth() == CR.getBitWidth() &&
583 "ConstantRange types don't agree!");
584
585 // Handle common cases.
586 if ( isEmptySet() || CR.isFullSet()) return *this;
587 if (CR.isEmptySet() || isFullSet()) return CR;
588
589 if (!isUpperWrapped() && CR.isUpperWrapped())
590 return CR.intersectWith(CR: *this, Type);
591
592 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
593 if (Lower.ult(RHS: CR.Lower)) {
594 // L---U : this
595 // L---U : CR
596 if (Upper.ule(RHS: CR.Lower))
597 return getEmpty();
598
599 // L---U : this
600 // L---U : CR
601 if (Upper.ult(RHS: CR.Upper))
602 return ConstantRange(CR.Lower, Upper);
603
604 // L-------U : this
605 // L---U : CR
606 return CR;
607 }
608 // L---U : this
609 // L-------U : CR
610 if (Upper.ult(RHS: CR.Upper))
611 return *this;
612
613 // L-----U : this
614 // L-----U : CR
615 if (Lower.ult(RHS: CR.Upper))
616 return ConstantRange(Lower, CR.Upper);
617
618 // L---U : this
619 // L---U : CR
620 return getEmpty();
621 }
622
623 if (isUpperWrapped() && !CR.isUpperWrapped()) {
624 if (CR.Lower.ult(RHS: Upper)) {
625 // ------U L--- : this
626 // L--U : CR
627 if (CR.Upper.ult(RHS: Upper))
628 return CR;
629
630 // ------U L--- : this
631 // L------U : CR
632 if (CR.Upper.ule(RHS: Lower))
633 return ConstantRange(CR.Lower, Upper);
634
635 // ------U L--- : this
636 // L----------U : CR
637 return getPreferredRange(CR1: *this, CR2: CR, Type);
638 }
639 if (CR.Lower.ult(RHS: Lower)) {
640 // --U L---- : this
641 // L--U : CR
642 if (CR.Upper.ule(RHS: Lower))
643 return getEmpty();
644
645 // --U L---- : this
646 // L------U : CR
647 return ConstantRange(Lower, CR.Upper);
648 }
649
650 // --U L------ : this
651 // L--U : CR
652 return CR;
653 }
654
655 if (CR.Upper.ult(RHS: Upper)) {
656 // ------U L-- : this
657 // --U L------ : CR
658 if (CR.Lower.ult(RHS: Upper))
659 return getPreferredRange(CR1: *this, CR2: CR, Type);
660
661 // ----U L-- : this
662 // --U L---- : CR
663 if (CR.Lower.ult(RHS: Lower))
664 return ConstantRange(Lower, CR.Upper);
665
666 // ----U L---- : this
667 // --U L-- : CR
668 return CR;
669 }
670 if (CR.Upper.ule(RHS: Lower)) {
671 // --U L-- : this
672 // ----U L---- : CR
673 if (CR.Lower.ult(RHS: Lower))
674 return *this;
675
676 // --U L---- : this
677 // ----U L-- : CR
678 return ConstantRange(CR.Lower, Upper);
679 }
680
681 // --U L------ : this
682 // ------U L-- : CR
683 return getPreferredRange(CR1: *this, CR2: CR, Type);
684}
685
686ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
687 PreferredRangeType Type) const {
688 assert(getBitWidth() == CR.getBitWidth() &&
689 "ConstantRange types don't agree!");
690
691 if ( isFullSet() || CR.isEmptySet()) return *this;
692 if (CR.isFullSet() || isEmptySet()) return CR;
693
694 if (!isUpperWrapped() && CR.isUpperWrapped())
695 return CR.unionWith(CR: *this, Type);
696
697 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
698 // L---U and L---U : this
699 // L---U L---U : CR
700 // result in one of
701 // L---------U
702 // -----U L-----
703 if (CR.Upper.ult(RHS: Lower) || Upper.ult(RHS: CR.Lower))
704 return getPreferredRange(
705 CR1: ConstantRange(Lower, CR.Upper), CR2: ConstantRange(CR.Lower, Upper), Type);
706
707 APInt L = CR.Lower.ult(RHS: Lower) ? CR.Lower : Lower;
708 APInt U = (CR.Upper - 1).ugt(RHS: Upper - 1) ? CR.Upper : Upper;
709
710 if (L.isZero() && U.isZero())
711 return getFull();
712
713 return ConstantRange(std::move(L), std::move(U));
714 }
715
716 if (!CR.isUpperWrapped()) {
717 // ------U L----- and ------U L----- : this
718 // L--U L--U : CR
719 if (CR.Upper.ule(RHS: Upper) || CR.Lower.uge(RHS: Lower))
720 return *this;
721
722 // ------U L----- : this
723 // L---------U : CR
724 if (CR.Lower.ule(RHS: Upper) && Lower.ule(RHS: CR.Upper))
725 return getFull();
726
727 // ----U L---- : this
728 // L---U : CR
729 // results in one of
730 // ----------U L----
731 // ----U L----------
732 if (Upper.ult(RHS: CR.Lower) && CR.Upper.ult(RHS: Lower))
733 return getPreferredRange(
734 CR1: ConstantRange(Lower, CR.Upper), CR2: ConstantRange(CR.Lower, Upper), Type);
735
736 // ----U L----- : this
737 // L----U : CR
738 if (Upper.ult(RHS: CR.Lower) && Lower.ule(RHS: CR.Upper))
739 return ConstantRange(CR.Lower, Upper);
740
741 // ------U L---- : this
742 // L-----U : CR
743 assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
744 "ConstantRange::unionWith missed a case with one range wrapped");
745 return ConstantRange(Lower, CR.Upper);
746 }
747
748 // ------U L---- and ------U L---- : this
749 // -U L----------- and ------------U L : CR
750 if (CR.Lower.ule(RHS: Upper) || Lower.ule(RHS: CR.Upper))
751 return getFull();
752
753 APInt L = CR.Lower.ult(RHS: Lower) ? CR.Lower : Lower;
754 APInt U = CR.Upper.ugt(RHS: Upper) ? CR.Upper : Upper;
755
756 return ConstantRange(std::move(L), std::move(U));
757}
758
759std::optional<ConstantRange>
760ConstantRange::exactIntersectWith(const ConstantRange &CR) const {
761 // TODO: This can be implemented more efficiently.
762 ConstantRange Result = intersectWith(CR);
763 if (Result == inverse().unionWith(CR: CR.inverse()).inverse())
764 return Result;
765 return std::nullopt;
766}
767
768std::optional<ConstantRange>
769ConstantRange::exactUnionWith(const ConstantRange &CR) const {
770 // TODO: This can be implemented more efficiently.
771 ConstantRange Result = unionWith(CR);
772 if (Result == inverse().intersectWith(CR: CR.inverse()).inverse())
773 return Result;
774 return std::nullopt;
775}
776
777ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
778 uint32_t ResultBitWidth) const {
779 switch (CastOp) {
780 default:
781 llvm_unreachable("unsupported cast type");
782 case Instruction::Trunc:
783 return truncate(BitWidth: ResultBitWidth);
784 case Instruction::SExt:
785 return signExtend(BitWidth: ResultBitWidth);
786 case Instruction::ZExt:
787 return zeroExtend(BitWidth: ResultBitWidth);
788 case Instruction::BitCast:
789 return *this;
790 case Instruction::FPToUI:
791 case Instruction::FPToSI:
792 if (getBitWidth() == ResultBitWidth)
793 return *this;
794 else
795 return getFull(BitWidth: ResultBitWidth);
796 case Instruction::UIToFP: {
797 // TODO: use input range if available
798 auto BW = getBitWidth();
799 APInt Min = APInt::getMinValue(numBits: BW);
800 APInt Max = APInt::getMaxValue(numBits: BW);
801 if (ResultBitWidth > BW) {
802 Min = Min.zext(width: ResultBitWidth);
803 Max = Max.zext(width: ResultBitWidth);
804 }
805 return getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
806 }
807 case Instruction::SIToFP: {
808 // TODO: use input range if available
809 auto BW = getBitWidth();
810 APInt SMin = APInt::getSignedMinValue(numBits: BW);
811 APInt SMax = APInt::getSignedMaxValue(numBits: BW);
812 if (ResultBitWidth > BW) {
813 SMin = SMin.sext(width: ResultBitWidth);
814 SMax = SMax.sext(width: ResultBitWidth);
815 }
816 return getNonEmpty(Lower: std::move(SMin), Upper: std::move(SMax) + 1);
817 }
818 case Instruction::FPTrunc:
819 case Instruction::FPExt:
820 case Instruction::IntToPtr:
821 case Instruction::PtrToInt:
822 case Instruction::AddrSpaceCast:
823 // Conservatively return getFull set.
824 return getFull(BitWidth: ResultBitWidth);
825 };
826}
827
828ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
829 if (isEmptySet()) return getEmpty(BitWidth: DstTySize);
830
831 unsigned SrcTySize = getBitWidth();
832 assert(SrcTySize < DstTySize && "Not a value extension");
833 if (isFullSet() || isUpperWrapped()) {
834 // Change into [0, 1 << src bit width)
835 APInt LowerExt(DstTySize, 0);
836 if (!Upper) // special case: [X, 0) -- not really wrapping around
837 LowerExt = Lower.zext(width: DstTySize);
838 return ConstantRange(std::move(LowerExt),
839 APInt::getOneBitSet(numBits: DstTySize, BitNo: SrcTySize));
840 }
841
842 return ConstantRange(Lower.zext(width: DstTySize), Upper.zext(width: DstTySize));
843}
844
845ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
846 if (isEmptySet()) return getEmpty(BitWidth: DstTySize);
847
848 unsigned SrcTySize = getBitWidth();
849 assert(SrcTySize < DstTySize && "Not a value extension");
850
851 // special case: [X, INT_MIN) -- not really wrapping around
852 if (Upper.isMinSignedValue())
853 return ConstantRange(Lower.sext(width: DstTySize), Upper.zext(width: DstTySize));
854
855 if (isFullSet() || isSignWrappedSet()) {
856 return ConstantRange(APInt::getHighBitsSet(numBits: DstTySize,hiBitsSet: DstTySize-SrcTySize+1),
857 APInt::getLowBitsSet(numBits: DstTySize, loBitsSet: SrcTySize-1) + 1);
858 }
859
860 return ConstantRange(Lower.sext(width: DstTySize), Upper.sext(width: DstTySize));
861}
862
863ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
864 assert(getBitWidth() > DstTySize && "Not a value truncation");
865 if (isEmptySet())
866 return getEmpty(BitWidth: DstTySize);
867 if (isFullSet())
868 return getFull(BitWidth: DstTySize);
869
870 APInt LowerDiv(Lower), UpperDiv(Upper);
871 ConstantRange Union(DstTySize, /*isFullSet=*/false);
872
873 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
874 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
875 // then we do the union with [MaxValue, Upper)
876 if (isUpperWrapped()) {
877 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
878 // truncated range.
879 if (Upper.getActiveBits() > DstTySize || Upper.countr_one() == DstTySize)
880 return getFull(BitWidth: DstTySize);
881
882 Union = ConstantRange(APInt::getMaxValue(numBits: DstTySize),Upper.trunc(width: DstTySize));
883 UpperDiv.setAllBits();
884
885 // Union covers the MaxValue case, so return if the remaining range is just
886 // MaxValue(DstTy).
887 if (LowerDiv == UpperDiv)
888 return Union;
889 }
890
891 // Chop off the most significant bits that are past the destination bitwidth.
892 if (LowerDiv.getActiveBits() > DstTySize) {
893 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
894 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(numBits: getBitWidth(), loBit: DstTySize);
895 LowerDiv -= Adjust;
896 UpperDiv -= Adjust;
897 }
898
899 unsigned UpperDivWidth = UpperDiv.getActiveBits();
900 if (UpperDivWidth <= DstTySize)
901 return ConstantRange(LowerDiv.trunc(width: DstTySize),
902 UpperDiv.trunc(width: DstTySize)).unionWith(CR: Union);
903
904 // The truncated value wraps around. Check if we can do better than fullset.
905 if (UpperDivWidth == DstTySize + 1) {
906 // Clear the MSB so that UpperDiv wraps around.
907 UpperDiv.clearBit(BitPosition: DstTySize);
908 if (UpperDiv.ult(RHS: LowerDiv))
909 return ConstantRange(LowerDiv.trunc(width: DstTySize),
910 UpperDiv.trunc(width: DstTySize)).unionWith(CR: Union);
911 }
912
913 return getFull(BitWidth: DstTySize);
914}
915
916ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
917 unsigned SrcTySize = getBitWidth();
918 if (SrcTySize > DstTySize)
919 return truncate(DstTySize);
920 if (SrcTySize < DstTySize)
921 return zeroExtend(DstTySize);
922 return *this;
923}
924
925ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
926 unsigned SrcTySize = getBitWidth();
927 if (SrcTySize > DstTySize)
928 return truncate(DstTySize);
929 if (SrcTySize < DstTySize)
930 return signExtend(DstTySize);
931 return *this;
932}
933
934ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
935 const ConstantRange &Other) const {
936 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
937
938 switch (BinOp) {
939 case Instruction::Add:
940 return add(Other);
941 case Instruction::Sub:
942 return sub(Other);
943 case Instruction::Mul:
944 return multiply(Other);
945 case Instruction::UDiv:
946 return udiv(Other);
947 case Instruction::SDiv:
948 return sdiv(Other);
949 case Instruction::URem:
950 return urem(Other);
951 case Instruction::SRem:
952 return srem(Other);
953 case Instruction::Shl:
954 return shl(Other);
955 case Instruction::LShr:
956 return lshr(Other);
957 case Instruction::AShr:
958 return ashr(Other);
959 case Instruction::And:
960 return binaryAnd(Other);
961 case Instruction::Or:
962 return binaryOr(Other);
963 case Instruction::Xor:
964 return binaryXor(Other);
965 // Note: floating point operations applied to abstract ranges are just
966 // ideal integer operations with a lossy representation
967 case Instruction::FAdd:
968 return add(Other);
969 case Instruction::FSub:
970 return sub(Other);
971 case Instruction::FMul:
972 return multiply(Other);
973 default:
974 // Conservatively return getFull set.
975 return getFull();
976 }
977}
978
979ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,
980 const ConstantRange &Other,
981 unsigned NoWrapKind) const {
982 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
983
984 switch (BinOp) {
985 case Instruction::Add:
986 return addWithNoWrap(Other, NoWrapKind);
987 case Instruction::Sub:
988 return subWithNoWrap(Other, NoWrapKind);
989 case Instruction::Mul:
990 return multiplyWithNoWrap(Other, NoWrapKind);
991 default:
992 // Don't know about this Overflowing Binary Operation.
993 // Conservatively fallback to plain binop handling.
994 return binaryOp(BinOp, Other);
995 }
996}
997
998bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) {
999 switch (IntrinsicID) {
1000 case Intrinsic::uadd_sat:
1001 case Intrinsic::usub_sat:
1002 case Intrinsic::sadd_sat:
1003 case Intrinsic::ssub_sat:
1004 case Intrinsic::umin:
1005 case Intrinsic::umax:
1006 case Intrinsic::smin:
1007 case Intrinsic::smax:
1008 case Intrinsic::abs:
1009 case Intrinsic::ctlz:
1010 case Intrinsic::cttz:
1011 case Intrinsic::ctpop:
1012 return true;
1013 default:
1014 return false;
1015 }
1016}
1017
1018ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID,
1019 ArrayRef<ConstantRange> Ops) {
1020 switch (IntrinsicID) {
1021 case Intrinsic::uadd_sat:
1022 return Ops[0].uadd_sat(Other: Ops[1]);
1023 case Intrinsic::usub_sat:
1024 return Ops[0].usub_sat(Other: Ops[1]);
1025 case Intrinsic::sadd_sat:
1026 return Ops[0].sadd_sat(Other: Ops[1]);
1027 case Intrinsic::ssub_sat:
1028 return Ops[0].ssub_sat(Other: Ops[1]);
1029 case Intrinsic::umin:
1030 return Ops[0].umin(Other: Ops[1]);
1031 case Intrinsic::umax:
1032 return Ops[0].umax(Other: Ops[1]);
1033 case Intrinsic::smin:
1034 return Ops[0].smin(Other: Ops[1]);
1035 case Intrinsic::smax:
1036 return Ops[0].smax(Other: Ops[1]);
1037 case Intrinsic::abs: {
1038 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
1039 assert(IntMinIsPoison && "Must be known (immarg)");
1040 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
1041 return Ops[0].abs(IntMinIsPoison: IntMinIsPoison->getBoolValue());
1042 }
1043 case Intrinsic::ctlz: {
1044 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1045 assert(ZeroIsPoison && "Must be known (immarg)");
1046 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1047 return Ops[0].ctlz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
1048 }
1049 case Intrinsic::cttz: {
1050 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1051 assert(ZeroIsPoison && "Must be known (immarg)");
1052 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1053 return Ops[0].cttz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
1054 }
1055 case Intrinsic::ctpop:
1056 return Ops[0].ctpop();
1057 default:
1058 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
1059 llvm_unreachable("Unsupported intrinsic");
1060 }
1061}
1062
1063ConstantRange
1064ConstantRange::add(const ConstantRange &Other) const {
1065 if (isEmptySet() || Other.isEmptySet())
1066 return getEmpty();
1067 if (isFullSet() || Other.isFullSet())
1068 return getFull();
1069
1070 APInt NewLower = getLower() + Other.getLower();
1071 APInt NewUpper = getUpper() + Other.getUpper() - 1;
1072 if (NewLower == NewUpper)
1073 return getFull();
1074
1075 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1076 if (X.isSizeStrictlySmallerThan(Other: *this) ||
1077 X.isSizeStrictlySmallerThan(Other))
1078 // We've wrapped, therefore, full set.
1079 return getFull();
1080 return X;
1081}
1082
1083ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
1084 unsigned NoWrapKind,
1085 PreferredRangeType RangeType) const {
1086 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1087 // (X is from this, and Y is from Other)
1088 if (isEmptySet() || Other.isEmptySet())
1089 return getEmpty();
1090 if (isFullSet() && Other.isFullSet())
1091 return getFull();
1092
1093 using OBO = OverflowingBinaryOperator;
1094 ConstantRange Result = add(Other);
1095
1096 // If an overflow happens for every value pair in these two constant ranges,
1097 // we must return Empty set. In this case, we get that for free, because we
1098 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1099 // in an empty set.
1100
1101 if (NoWrapKind & OBO::NoSignedWrap)
1102 Result = Result.intersectWith(CR: sadd_sat(Other), Type: RangeType);
1103
1104 if (NoWrapKind & OBO::NoUnsignedWrap)
1105 Result = Result.intersectWith(CR: uadd_sat(Other), Type: RangeType);
1106
1107 return Result;
1108}
1109
1110ConstantRange
1111ConstantRange::sub(const ConstantRange &Other) const {
1112 if (isEmptySet() || Other.isEmptySet())
1113 return getEmpty();
1114 if (isFullSet() || Other.isFullSet())
1115 return getFull();
1116
1117 APInt NewLower = getLower() - Other.getUpper() + 1;
1118 APInt NewUpper = getUpper() - Other.getLower();
1119 if (NewLower == NewUpper)
1120 return getFull();
1121
1122 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1123 if (X.isSizeStrictlySmallerThan(Other: *this) ||
1124 X.isSizeStrictlySmallerThan(Other))
1125 // We've wrapped, therefore, full set.
1126 return getFull();
1127 return X;
1128}
1129
1130ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,
1131 unsigned NoWrapKind,
1132 PreferredRangeType RangeType) const {
1133 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1134 // (X is from this, and Y is from Other)
1135 if (isEmptySet() || Other.isEmptySet())
1136 return getEmpty();
1137 if (isFullSet() && Other.isFullSet())
1138 return getFull();
1139
1140 using OBO = OverflowingBinaryOperator;
1141 ConstantRange Result = sub(Other);
1142
1143 // If an overflow happens for every value pair in these two constant ranges,
1144 // we must return Empty set. In signed case, we get that for free, because we
1145 // get lucky that intersection of sub() with ssub_sat() results in an
1146 // empty set. But for unsigned we must perform the overflow check manually.
1147
1148 if (NoWrapKind & OBO::NoSignedWrap)
1149 Result = Result.intersectWith(CR: ssub_sat(Other), Type: RangeType);
1150
1151 if (NoWrapKind & OBO::NoUnsignedWrap) {
1152 if (getUnsignedMax().ult(RHS: Other.getUnsignedMin()))
1153 return getEmpty(); // Always overflows.
1154 Result = Result.intersectWith(CR: usub_sat(Other), Type: RangeType);
1155 }
1156
1157 return Result;
1158}
1159
1160ConstantRange
1161ConstantRange::multiply(const ConstantRange &Other) const {
1162 // TODO: If either operand is a single element and the multiply is known to
1163 // be non-wrapping, round the result min and max value to the appropriate
1164 // multiple of that element. If wrapping is possible, at least adjust the
1165 // range according to the greatest power-of-two factor of the single element.
1166
1167 if (isEmptySet() || Other.isEmptySet())
1168 return getEmpty();
1169
1170 if (const APInt *C = getSingleElement()) {
1171 if (C->isOne())
1172 return Other;
1173 if (C->isAllOnes())
1174 return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other);
1175 }
1176
1177 if (const APInt *C = Other.getSingleElement()) {
1178 if (C->isOne())
1179 return *this;
1180 if (C->isAllOnes())
1181 return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other: *this);
1182 }
1183
1184 // Multiplication is signedness-independent. However different ranges can be
1185 // obtained depending on how the input ranges are treated. These different
1186 // ranges are all conservatively correct, but one might be better than the
1187 // other. We calculate two ranges; one treating the inputs as unsigned
1188 // and the other signed, then return the smallest of these ranges.
1189
1190 // Unsigned range first.
1191 APInt this_min = getUnsignedMin().zext(width: getBitWidth() * 2);
1192 APInt this_max = getUnsignedMax().zext(width: getBitWidth() * 2);
1193 APInt Other_min = Other.getUnsignedMin().zext(width: getBitWidth() * 2);
1194 APInt Other_max = Other.getUnsignedMax().zext(width: getBitWidth() * 2);
1195
1196 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1197 this_max * Other_max + 1);
1198 ConstantRange UR = Result_zext.truncate(DstTySize: getBitWidth());
1199
1200 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1201 // from one positive number to another which is as good as we can generate.
1202 // In this case, skip the extra work of generating signed ranges which aren't
1203 // going to be better than this range.
1204 if (!UR.isUpperWrapped() &&
1205 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
1206 return UR;
1207
1208 // Now the signed range. Because we could be dealing with negative numbers
1209 // here, the lower bound is the smallest of the cartesian product of the
1210 // lower and upper ranges; for example:
1211 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1212 // Similarly for the upper bound, swapping min for max.
1213
1214 this_min = getSignedMin().sext(width: getBitWidth() * 2);
1215 this_max = getSignedMax().sext(width: getBitWidth() * 2);
1216 Other_min = Other.getSignedMin().sext(width: getBitWidth() * 2);
1217 Other_max = Other.getSignedMax().sext(width: getBitWidth() * 2);
1218
1219 auto L = {this_min * Other_min, this_min * Other_max,
1220 this_max * Other_min, this_max * Other_max};
1221 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1222 ConstantRange Result_sext(std::min(l: L, comp: Compare), std::max(l: L, comp: Compare) + 1);
1223 ConstantRange SR = Result_sext.truncate(DstTySize: getBitWidth());
1224
1225 return UR.isSizeStrictlySmallerThan(Other: SR) ? UR : SR;
1226}
1227
1228ConstantRange
1229ConstantRange::multiplyWithNoWrap(const ConstantRange &Other,
1230 unsigned NoWrapKind,
1231 PreferredRangeType RangeType) const {
1232 if (isEmptySet() || Other.isEmptySet())
1233 return getEmpty();
1234 if (isFullSet() && Other.isFullSet())
1235 return getFull();
1236
1237 ConstantRange Result = multiply(Other);
1238
1239 if (NoWrapKind & OverflowingBinaryOperator::NoSignedWrap)
1240 Result = Result.intersectWith(CR: smul_sat(Other), Type: RangeType);
1241
1242 if (NoWrapKind & OverflowingBinaryOperator::NoUnsignedWrap)
1243 Result = Result.intersectWith(CR: umul_sat(Other), Type: RangeType);
1244
1245 return Result;
1246}
1247
1248ConstantRange ConstantRange::smul_fast(const ConstantRange &Other) const {
1249 if (isEmptySet() || Other.isEmptySet())
1250 return getEmpty();
1251
1252 APInt Min = getSignedMin();
1253 APInt Max = getSignedMax();
1254 APInt OtherMin = Other.getSignedMin();
1255 APInt OtherMax = Other.getSignedMax();
1256
1257 bool O1, O2, O3, O4;
1258 auto Muls = {Min.smul_ov(RHS: OtherMin, Overflow&: O1), Min.smul_ov(RHS: OtherMax, Overflow&: O2),
1259 Max.smul_ov(RHS: OtherMin, Overflow&: O3), Max.smul_ov(RHS: OtherMax, Overflow&: O4)};
1260 if (O1 || O2 || O3 || O4)
1261 return getFull();
1262
1263 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1264 return getNonEmpty(Lower: std::min(l: Muls, comp: Compare), Upper: std::max(l: Muls, comp: Compare) + 1);
1265}
1266
1267ConstantRange
1268ConstantRange::smax(const ConstantRange &Other) const {
1269 // X smax Y is: range(smax(X_smin, Y_smin),
1270 // smax(X_smax, Y_smax))
1271 if (isEmptySet() || Other.isEmptySet())
1272 return getEmpty();
1273 APInt NewL = APIntOps::smax(A: getSignedMin(), B: Other.getSignedMin());
1274 APInt NewU = APIntOps::smax(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1275 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1276 if (isSignWrappedSet() || Other.isSignWrappedSet())
1277 return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1278 return Res;
1279}
1280
1281ConstantRange
1282ConstantRange::umax(const ConstantRange &Other) const {
1283 // X umax Y is: range(umax(X_umin, Y_umin),
1284 // umax(X_umax, Y_umax))
1285 if (isEmptySet() || Other.isEmptySet())
1286 return getEmpty();
1287 APInt NewL = APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin());
1288 APInt NewU = APIntOps::umax(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1289 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1290 if (isWrappedSet() || Other.isWrappedSet())
1291 return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1292 return Res;
1293}
1294
1295ConstantRange
1296ConstantRange::smin(const ConstantRange &Other) const {
1297 // X smin Y is: range(smin(X_smin, Y_smin),
1298 // smin(X_smax, Y_smax))
1299 if (isEmptySet() || Other.isEmptySet())
1300 return getEmpty();
1301 APInt NewL = APIntOps::smin(A: getSignedMin(), B: Other.getSignedMin());
1302 APInt NewU = APIntOps::smin(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1303 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1304 if (isSignWrappedSet() || Other.isSignWrappedSet())
1305 return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1306 return Res;
1307}
1308
1309ConstantRange
1310ConstantRange::umin(const ConstantRange &Other) const {
1311 // X umin Y is: range(umin(X_umin, Y_umin),
1312 // umin(X_umax, Y_umax))
1313 if (isEmptySet() || Other.isEmptySet())
1314 return getEmpty();
1315 APInt NewL = APIntOps::umin(A: getUnsignedMin(), B: Other.getUnsignedMin());
1316 APInt NewU = APIntOps::umin(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1317 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1318 if (isWrappedSet() || Other.isWrappedSet())
1319 return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1320 return Res;
1321}
1322
1323ConstantRange
1324ConstantRange::udiv(const ConstantRange &RHS) const {
1325 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1326 return getEmpty();
1327
1328 APInt Lower = getUnsignedMin().udiv(RHS: RHS.getUnsignedMax());
1329
1330 APInt RHS_umin = RHS.getUnsignedMin();
1331 if (RHS_umin.isZero()) {
1332 // We want the lowest value in RHS excluding zero. Usually that would be 1
1333 // except for a range in the form of [X, 1) in which case it would be X.
1334 if (RHS.getUpper() == 1)
1335 RHS_umin = RHS.getLower();
1336 else
1337 RHS_umin = 1;
1338 }
1339
1340 APInt Upper = getUnsignedMax().udiv(RHS: RHS_umin) + 1;
1341 return getNonEmpty(Lower: std::move(Lower), Upper: std::move(Upper));
1342}
1343
1344ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {
1345 // We split up the LHS and RHS into positive and negative components
1346 // and then also compute the positive and negative components of the result
1347 // separately by combining division results with the appropriate signs.
1348 APInt Zero = APInt::getZero(numBits: getBitWidth());
1349 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1350 // There are no positive 1-bit values. The 1 would get interpreted as -1.
1351 ConstantRange PosFilter =
1352 getBitWidth() == 1 ? getEmpty()
1353 : ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1354 ConstantRange NegFilter(SignedMin, Zero);
1355 ConstantRange PosL = intersectWith(CR: PosFilter);
1356 ConstantRange NegL = intersectWith(CR: NegFilter);
1357 ConstantRange PosR = RHS.intersectWith(CR: PosFilter);
1358 ConstantRange NegR = RHS.intersectWith(CR: NegFilter);
1359
1360 ConstantRange PosRes = getEmpty();
1361 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1362 // pos / pos = pos.
1363 PosRes = ConstantRange(PosL.Lower.sdiv(RHS: PosR.Upper - 1),
1364 (PosL.Upper - 1).sdiv(RHS: PosR.Lower) + 1);
1365
1366 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1367 // neg / neg = pos.
1368 //
1369 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1370 // IR level, so we'll want to exclude this case when calculating bounds.
1371 // (For APInts the operation is well-defined and yields SignedMin.) We
1372 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1373 APInt Lo = (NegL.Upper - 1).sdiv(RHS: NegR.Lower);
1374 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1375 // Remove -1 from the LHS. Skip if it's the only element, as this would
1376 // leave us with an empty set.
1377 if (!NegR.Lower.isAllOnes()) {
1378 APInt AdjNegRUpper;
1379 if (RHS.Lower.isAllOnes())
1380 // Negative part of [-1, X] without -1 is [SignedMin, X].
1381 AdjNegRUpper = RHS.Upper;
1382 else
1383 // [X, -1] without -1 is [X, -2].
1384 AdjNegRUpper = NegR.Upper - 1;
1385
1386 PosRes = PosRes.unionWith(
1387 CR: ConstantRange(Lo, NegL.Lower.sdiv(RHS: AdjNegRUpper - 1) + 1));
1388 }
1389
1390 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1391 // would leave us with an empty set.
1392 if (NegL.Upper != SignedMin + 1) {
1393 APInt AdjNegLLower;
1394 if (Upper == SignedMin + 1)
1395 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1396 AdjNegLLower = Lower;
1397 else
1398 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1399 AdjNegLLower = NegL.Lower + 1;
1400
1401 PosRes = PosRes.unionWith(
1402 CR: ConstantRange(std::move(Lo),
1403 AdjNegLLower.sdiv(RHS: NegR.Upper - 1) + 1));
1404 }
1405 } else {
1406 PosRes = PosRes.unionWith(
1407 CR: ConstantRange(std::move(Lo), NegL.Lower.sdiv(RHS: NegR.Upper - 1) + 1));
1408 }
1409 }
1410
1411 ConstantRange NegRes = getEmpty();
1412 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1413 // pos / neg = neg.
1414 NegRes = ConstantRange((PosL.Upper - 1).sdiv(RHS: NegR.Upper - 1),
1415 PosL.Lower.sdiv(RHS: NegR.Lower) + 1);
1416
1417 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1418 // neg / pos = neg.
1419 NegRes = NegRes.unionWith(
1420 CR: ConstantRange(NegL.Lower.sdiv(RHS: PosR.Lower),
1421 (NegL.Upper - 1).sdiv(RHS: PosR.Upper - 1) + 1));
1422
1423 // Prefer a non-wrapping signed range here.
1424 ConstantRange Res = NegRes.unionWith(CR: PosRes, Type: PreferredRangeType::Signed);
1425
1426 // Preserve the zero that we dropped when splitting the LHS by sign.
1427 if (contains(V: Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1428 Res = Res.unionWith(CR: ConstantRange(Zero));
1429 return Res;
1430}
1431
1432ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
1433 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1434 return getEmpty();
1435
1436 if (const APInt *RHSInt = RHS.getSingleElement()) {
1437 // UREM by null is UB.
1438 if (RHSInt->isZero())
1439 return getEmpty();
1440 // Use APInt's implementation of UREM for single element ranges.
1441 if (const APInt *LHSInt = getSingleElement())
1442 return {LHSInt->urem(RHS: *RHSInt)};
1443 }
1444
1445 // L % R for L < R is L.
1446 if (getUnsignedMax().ult(RHS: RHS.getUnsignedMin()))
1447 return *this;
1448
1449 // L % R is <= L and < R.
1450 APInt Upper = APIntOps::umin(A: getUnsignedMax(), B: RHS.getUnsignedMax() - 1) + 1;
1451 return getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()), Upper: std::move(Upper));
1452}
1453
1454ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1455 if (isEmptySet() || RHS.isEmptySet())
1456 return getEmpty();
1457
1458 if (const APInt *RHSInt = RHS.getSingleElement()) {
1459 // SREM by null is UB.
1460 if (RHSInt->isZero())
1461 return getEmpty();
1462 // Use APInt's implementation of SREM for single element ranges.
1463 if (const APInt *LHSInt = getSingleElement())
1464 return {LHSInt->srem(RHS: *RHSInt)};
1465 }
1466
1467 ConstantRange AbsRHS = RHS.abs();
1468 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1469 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1470
1471 // Modulus by zero is UB.
1472 if (MaxAbsRHS.isZero())
1473 return getEmpty();
1474
1475 if (MinAbsRHS.isZero())
1476 ++MinAbsRHS;
1477
1478 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1479
1480 if (MinLHS.isNonNegative()) {
1481 // L % R for L < R is L.
1482 if (MaxLHS.ult(RHS: MinAbsRHS))
1483 return *this;
1484
1485 // L % R is <= L and < R.
1486 APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1487 return ConstantRange(APInt::getZero(numBits: getBitWidth()), std::move(Upper));
1488 }
1489
1490 // Same basic logic as above, but the result is negative.
1491 if (MaxLHS.isNegative()) {
1492 if (MinLHS.ugt(RHS: -MinAbsRHS))
1493 return *this;
1494
1495 APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1496 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1497 }
1498
1499 // LHS range crosses zero.
1500 APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1501 APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1502 return ConstantRange(std::move(Lower), std::move(Upper));
1503}
1504
1505ConstantRange ConstantRange::binaryNot() const {
1506 return ConstantRange(APInt::getAllOnes(numBits: getBitWidth())).sub(Other: *this);
1507}
1508
1509ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const {
1510 if (isEmptySet() || Other.isEmptySet())
1511 return getEmpty();
1512
1513 ConstantRange KnownBitsRange =
1514 fromKnownBits(Known: toKnownBits() & Other.toKnownBits(), IsSigned: false);
1515 ConstantRange UMinUMaxRange =
1516 getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
1517 Upper: APIntOps::umin(A: Other.getUnsignedMax(), B: getUnsignedMax()) + 1);
1518 return KnownBitsRange.intersectWith(CR: UMinUMaxRange);
1519}
1520
1521ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const {
1522 if (isEmptySet() || Other.isEmptySet())
1523 return getEmpty();
1524
1525 ConstantRange KnownBitsRange =
1526 fromKnownBits(Known: toKnownBits() | Other.toKnownBits(), IsSigned: false);
1527 // Upper wrapped range.
1528 ConstantRange UMaxUMinRange =
1529 getNonEmpty(Lower: APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin()),
1530 Upper: APInt::getZero(numBits: getBitWidth()));
1531 return KnownBitsRange.intersectWith(CR: UMaxUMinRange);
1532}
1533
1534ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {
1535 if (isEmptySet() || Other.isEmptySet())
1536 return getEmpty();
1537
1538 // Use APInt's implementation of XOR for single element ranges.
1539 if (isSingleElement() && Other.isSingleElement())
1540 return {*getSingleElement() ^ *Other.getSingleElement()};
1541
1542 // Special-case binary complement, since we can give a precise answer.
1543 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1544 return binaryNot();
1545 if (isSingleElement() && getSingleElement()->isAllOnes())
1546 return Other.binaryNot();
1547
1548 KnownBits LHSKnown = toKnownBits();
1549 KnownBits RHSKnown = Other.toKnownBits();
1550 KnownBits Known = LHSKnown ^ RHSKnown;
1551 ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);
1552 // Typically the following code doesn't improve the result if BW = 1.
1553 if (getBitWidth() == 1)
1554 return CR;
1555
1556 // If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw
1557 // LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS
1558 // -nuw/nsw RHS.
1559 if ((~LHSKnown.Zero).isSubsetOf(RHS: RHSKnown.One))
1560 CR = CR.intersectWith(CR: Other.sub(Other: *this), Type: PreferredRangeType::Unsigned);
1561 else if ((~RHSKnown.Zero).isSubsetOf(RHS: LHSKnown.One))
1562 CR = CR.intersectWith(CR: this->sub(Other), Type: PreferredRangeType::Unsigned);
1563 return CR;
1564}
1565
1566ConstantRange
1567ConstantRange::shl(const ConstantRange &Other) const {
1568 if (isEmptySet() || Other.isEmptySet())
1569 return getEmpty();
1570
1571 APInt Min = getUnsignedMin();
1572 APInt Max = getUnsignedMax();
1573 if (const APInt *RHS = Other.getSingleElement()) {
1574 unsigned BW = getBitWidth();
1575 if (RHS->uge(RHS: BW))
1576 return getEmpty();
1577
1578 unsigned EqualLeadingBits = (Min ^ Max).countl_zero();
1579 if (RHS->ule(RHS: EqualLeadingBits))
1580 return getNonEmpty(Lower: Min << *RHS, Upper: (Max << *RHS) + 1);
1581
1582 return getNonEmpty(Lower: APInt::getZero(numBits: BW),
1583 Upper: APInt::getBitsSetFrom(numBits: BW, loBit: RHS->getZExtValue()) + 1);
1584 }
1585
1586 APInt OtherMax = Other.getUnsignedMax();
1587 if (isAllNegative() && OtherMax.ule(RHS: Min.countl_one())) {
1588 // For negative numbers, if the shift does not overflow in a signed sense,
1589 // a larger shift will make the number smaller.
1590 Max <<= Other.getUnsignedMin();
1591 Min <<= OtherMax;
1592 return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1593 }
1594
1595 // There's overflow!
1596 if (OtherMax.ugt(RHS: Max.countl_zero()))
1597 return getFull();
1598
1599 // FIXME: implement the other tricky cases
1600
1601 Min <<= Other.getUnsignedMin();
1602 Max <<= OtherMax;
1603
1604 return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1605}
1606
1607ConstantRange
1608ConstantRange::lshr(const ConstantRange &Other) const {
1609 if (isEmptySet() || Other.isEmptySet())
1610 return getEmpty();
1611
1612 APInt max = getUnsignedMax().lshr(ShiftAmt: Other.getUnsignedMin()) + 1;
1613 APInt min = getUnsignedMin().lshr(ShiftAmt: Other.getUnsignedMax());
1614 return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1615}
1616
1617ConstantRange
1618ConstantRange::ashr(const ConstantRange &Other) const {
1619 if (isEmptySet() || Other.isEmptySet())
1620 return getEmpty();
1621
1622 // May straddle zero, so handle both positive and negative cases.
1623 // 'PosMax' is the upper bound of the result of the ashr
1624 // operation, when Upper of the LHS of ashr is a non-negative.
1625 // number. Since ashr of a non-negative number will result in a
1626 // smaller number, the Upper value of LHS is shifted right with
1627 // the minimum value of 'Other' instead of the maximum value.
1628 APInt PosMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMin()) + 1;
1629
1630 // 'PosMin' is the lower bound of the result of the ashr
1631 // operation, when Lower of the LHS is a non-negative number.
1632 // Since ashr of a non-negative number will result in a smaller
1633 // number, the Lower value of LHS is shifted right with the
1634 // maximum value of 'Other'.
1635 APInt PosMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMax());
1636
1637 // 'NegMax' is the upper bound of the result of the ashr
1638 // operation, when Upper of the LHS of ashr is a negative number.
1639 // Since 'ashr' of a negative number will result in a bigger
1640 // number, the Upper value of LHS is shifted right with the
1641 // maximum value of 'Other'.
1642 APInt NegMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMax()) + 1;
1643
1644 // 'NegMin' is the lower bound of the result of the ashr
1645 // operation, when Lower of the LHS of ashr is a negative number.
1646 // Since 'ashr' of a negative number will result in a bigger
1647 // number, the Lower value of LHS is shifted right with the
1648 // minimum value of 'Other'.
1649 APInt NegMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMin());
1650
1651 APInt max, min;
1652 if (getSignedMin().isNonNegative()) {
1653 // Upper and Lower of LHS are non-negative.
1654 min = PosMin;
1655 max = PosMax;
1656 } else if (getSignedMax().isNegative()) {
1657 // Upper and Lower of LHS are negative.
1658 min = NegMin;
1659 max = NegMax;
1660 } else {
1661 // Upper is non-negative and Lower is negative.
1662 min = NegMin;
1663 max = PosMax;
1664 }
1665 return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1666}
1667
1668ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {
1669 if (isEmptySet() || Other.isEmptySet())
1670 return getEmpty();
1671
1672 APInt NewL = getUnsignedMin().uadd_sat(RHS: Other.getUnsignedMin());
1673 APInt NewU = getUnsignedMax().uadd_sat(RHS: Other.getUnsignedMax()) + 1;
1674 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1675}
1676
1677ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {
1678 if (isEmptySet() || Other.isEmptySet())
1679 return getEmpty();
1680
1681 APInt NewL = getSignedMin().sadd_sat(RHS: Other.getSignedMin());
1682 APInt NewU = getSignedMax().sadd_sat(RHS: Other.getSignedMax()) + 1;
1683 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1684}
1685
1686ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {
1687 if (isEmptySet() || Other.isEmptySet())
1688 return getEmpty();
1689
1690 APInt NewL = getUnsignedMin().usub_sat(RHS: Other.getUnsignedMax());
1691 APInt NewU = getUnsignedMax().usub_sat(RHS: Other.getUnsignedMin()) + 1;
1692 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1693}
1694
1695ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
1696 if (isEmptySet() || Other.isEmptySet())
1697 return getEmpty();
1698
1699 APInt NewL = getSignedMin().ssub_sat(RHS: Other.getSignedMax());
1700 APInt NewU = getSignedMax().ssub_sat(RHS: Other.getSignedMin()) + 1;
1701 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1702}
1703
1704ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {
1705 if (isEmptySet() || Other.isEmptySet())
1706 return getEmpty();
1707
1708 APInt NewL = getUnsignedMin().umul_sat(RHS: Other.getUnsignedMin());
1709 APInt NewU = getUnsignedMax().umul_sat(RHS: Other.getUnsignedMax()) + 1;
1710 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1711}
1712
1713ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {
1714 if (isEmptySet() || Other.isEmptySet())
1715 return getEmpty();
1716
1717 // Because we could be dealing with negative numbers here, the lower bound is
1718 // the smallest of the cartesian product of the lower and upper ranges;
1719 // for example:
1720 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1721 // Similarly for the upper bound, swapping min for max.
1722
1723 APInt Min = getSignedMin();
1724 APInt Max = getSignedMax();
1725 APInt OtherMin = Other.getSignedMin();
1726 APInt OtherMax = Other.getSignedMax();
1727
1728 auto L = {Min.smul_sat(RHS: OtherMin), Min.smul_sat(RHS: OtherMax),
1729 Max.smul_sat(RHS: OtherMin), Max.smul_sat(RHS: OtherMax)};
1730 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1731 return getNonEmpty(Lower: std::min(l: L, comp: Compare), Upper: std::max(l: L, comp: Compare) + 1);
1732}
1733
1734ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
1735 if (isEmptySet() || Other.isEmptySet())
1736 return getEmpty();
1737
1738 APInt NewL = getUnsignedMin().ushl_sat(RHS: Other.getUnsignedMin());
1739 APInt NewU = getUnsignedMax().ushl_sat(RHS: Other.getUnsignedMax()) + 1;
1740 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1741}
1742
1743ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {
1744 if (isEmptySet() || Other.isEmptySet())
1745 return getEmpty();
1746
1747 APInt Min = getSignedMin(), Max = getSignedMax();
1748 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1749 APInt NewL = Min.sshl_sat(RHS: Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1750 APInt NewU = Max.sshl_sat(RHS: Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1751 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1752}
1753
1754ConstantRange ConstantRange::inverse() const {
1755 if (isFullSet())
1756 return getEmpty();
1757 if (isEmptySet())
1758 return getFull();
1759 return ConstantRange(Upper, Lower);
1760}
1761
1762ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1763 if (isEmptySet())
1764 return getEmpty();
1765
1766 if (isSignWrappedSet()) {
1767 APInt Lo;
1768 // Check whether the range crosses zero.
1769 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1770 Lo = APInt::getZero(numBits: getBitWidth());
1771 else
1772 Lo = APIntOps::umin(A: Lower, B: -Upper + 1);
1773
1774 // If SignedMin is not poison, then it is included in the result range.
1775 if (IntMinIsPoison)
1776 return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()));
1777 else
1778 return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()) + 1);
1779 }
1780
1781 APInt SMin = getSignedMin(), SMax = getSignedMax();
1782
1783 // Skip SignedMin if it is poison.
1784 if (IntMinIsPoison && SMin.isMinSignedValue()) {
1785 // The range may become empty if it *only* contains SignedMin.
1786 if (SMax.isMinSignedValue())
1787 return getEmpty();
1788 ++SMin;
1789 }
1790
1791 // All non-negative.
1792 if (SMin.isNonNegative())
1793 return ConstantRange(SMin, SMax + 1);
1794
1795 // All negative.
1796 if (SMax.isNegative())
1797 return ConstantRange(-SMax, -SMin + 1);
1798
1799 // Range crosses zero.
1800 return ConstantRange::getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
1801 Upper: APIntOps::umax(A: -SMin, B: SMax) + 1);
1802}
1803
1804ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {
1805 if (isEmptySet())
1806 return getEmpty();
1807
1808 APInt Zero = APInt::getZero(numBits: getBitWidth());
1809 if (ZeroIsPoison && contains(V: Zero)) {
1810 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1811 // which a zero can appear:
1812 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1813 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1814 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1815
1816 if (getLower().isZero()) {
1817 if ((getUpper() - 1).isZero()) {
1818 // We have in input interval of kind [0, 1). In this case we cannot
1819 // really help but return empty-set.
1820 return getEmpty();
1821 }
1822
1823 // Compute the resulting range by excluding zero from Lower.
1824 return ConstantRange(
1825 APInt(getBitWidth(), (getUpper() - 1).countl_zero()),
1826 APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));
1827 } else if ((getUpper() - 1).isZero()) {
1828 // Compute the resulting range by excluding zero from Upper.
1829 return ConstantRange(Zero,
1830 APInt(getBitWidth(), getLower().countl_zero() + 1));
1831 } else {
1832 return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));
1833 }
1834 }
1835
1836 // Zero is either safe or not in the range. The output range is composed by
1837 // the result of countLeadingZero of the two extremes.
1838 return getNonEmpty(Lower: APInt(getBitWidth(), getUnsignedMax().countl_zero()),
1839 Upper: APInt(getBitWidth(), getUnsignedMin().countl_zero() + 1));
1840}
1841
1842static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower,
1843 const APInt &Upper) {
1844 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1845 "Unexpected wrapped set.");
1846 assert(Lower != Upper && "Unexpected empty set.");
1847 unsigned BitWidth = Lower.getBitWidth();
1848 if (Lower + 1 == Upper)
1849 return ConstantRange(APInt(BitWidth, Lower.countr_zero()));
1850 if (Lower.isZero())
1851 return ConstantRange(APInt::getZero(numBits: BitWidth),
1852 APInt(BitWidth, BitWidth + 1));
1853
1854 // Calculate longest common prefix.
1855 unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();
1856 // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().
1857 // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).
1858 return ConstantRange(
1859 APInt::getZero(numBits: BitWidth),
1860 APInt(BitWidth,
1861 std::max(a: BitWidth - LCPLength - 1, b: Lower.countr_zero()) + 1));
1862}
1863
1864ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {
1865 if (isEmptySet())
1866 return getEmpty();
1867
1868 unsigned BitWidth = getBitWidth();
1869 APInt Zero = APInt::getZero(numBits: BitWidth);
1870 if (ZeroIsPoison && contains(V: Zero)) {
1871 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1872 // which a zero can appear:
1873 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1874 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1875 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1876
1877 if (Lower.isZero()) {
1878 if (Upper == 1) {
1879 // We have in input interval of kind [0, 1). In this case we cannot
1880 // really help but return empty-set.
1881 return getEmpty();
1882 }
1883
1884 // Compute the resulting range by excluding zero from Lower.
1885 return getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
1886 } else if (Upper == 1) {
1887 // Compute the resulting range by excluding zero from Upper.
1888 return getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1889 } else {
1890 ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1891 ConstantRange CR2 =
1892 getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
1893 return CR1.unionWith(CR: CR2);
1894 }
1895 }
1896
1897 if (isFullSet())
1898 return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth + 1));
1899 if (!isWrappedSet())
1900 return getUnsignedCountTrailingZerosRange(Lower, Upper);
1901 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
1902 // [Lower, 0).
1903 // Handle [Lower, 0)
1904 ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1905 // Handle [0, Upper)
1906 ConstantRange CR2 = getUnsignedCountTrailingZerosRange(Lower: Zero, Upper);
1907 return CR1.unionWith(CR: CR2);
1908}
1909
1910static ConstantRange getUnsignedPopCountRange(const APInt &Lower,
1911 const APInt &Upper) {
1912 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1913 "Unexpected wrapped set.");
1914 assert(Lower != Upper && "Unexpected empty set.");
1915 unsigned BitWidth = Lower.getBitWidth();
1916 if (Lower + 1 == Upper)
1917 return ConstantRange(APInt(BitWidth, Lower.popcount()));
1918
1919 APInt Max = Upper - 1;
1920 // Calculate longest common prefix.
1921 unsigned LCPLength = (Lower ^ Max).countl_zero();
1922 unsigned LCPPopCount = Lower.getHiBits(numBits: LCPLength).popcount();
1923 // If Lower is {LCP, 000...}, the minimum is the popcount of LCP.
1924 // Otherwise, the minimum is the popcount of LCP + 1.
1925 unsigned MinBits =
1926 LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);
1927 // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -
1928 // length of LCP).
1929 // Otherwise, the minimum is the popcount of LCP + (BitWidth -
1930 // length of LCP - 1).
1931 unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -
1932 (Max.countr_one() < BitWidth - LCPLength ? 1 : 0);
1933 return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));
1934}
1935
1936ConstantRange ConstantRange::ctpop() const {
1937 if (isEmptySet())
1938 return getEmpty();
1939
1940 unsigned BitWidth = getBitWidth();
1941 APInt Zero = APInt::getZero(numBits: BitWidth);
1942 if (isFullSet())
1943 return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth + 1));
1944 if (!isWrappedSet())
1945 return getUnsignedPopCountRange(Lower, Upper);
1946 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
1947 // [Lower, 0).
1948 // Handle [Lower, 0) == [Lower, Max]
1949 ConstantRange CR1 = ConstantRange(APInt(BitWidth, Lower.countl_one()),
1950 APInt(BitWidth, BitWidth + 1));
1951 // Handle [0, Upper)
1952 ConstantRange CR2 = getUnsignedPopCountRange(Lower: Zero, Upper);
1953 return CR1.unionWith(CR: CR2);
1954}
1955
1956ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
1957 const ConstantRange &Other) const {
1958 if (isEmptySet() || Other.isEmptySet())
1959 return OverflowResult::MayOverflow;
1960
1961 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1962 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1963
1964 // a u+ b overflows high iff a u> ~b.
1965 if (Min.ugt(RHS: ~OtherMin))
1966 return OverflowResult::AlwaysOverflowsHigh;
1967 if (Max.ugt(RHS: ~OtherMax))
1968 return OverflowResult::MayOverflow;
1969 return OverflowResult::NeverOverflows;
1970}
1971
1972ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
1973 const ConstantRange &Other) const {
1974 if (isEmptySet() || Other.isEmptySet())
1975 return OverflowResult::MayOverflow;
1976
1977 APInt Min = getSignedMin(), Max = getSignedMax();
1978 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1979
1980 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1981 APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
1982
1983 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1984 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1985 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1986 Min.sgt(RHS: SignedMax - OtherMin))
1987 return OverflowResult::AlwaysOverflowsHigh;
1988 if (Max.isNegative() && OtherMax.isNegative() &&
1989 Max.slt(RHS: SignedMin - OtherMax))
1990 return OverflowResult::AlwaysOverflowsLow;
1991
1992 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1993 Max.sgt(RHS: SignedMax - OtherMax))
1994 return OverflowResult::MayOverflow;
1995 if (Min.isNegative() && OtherMin.isNegative() &&
1996 Min.slt(RHS: SignedMin - OtherMin))
1997 return OverflowResult::MayOverflow;
1998
1999 return OverflowResult::NeverOverflows;
2000}
2001
2002ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
2003 const ConstantRange &Other) const {
2004 if (isEmptySet() || Other.isEmptySet())
2005 return OverflowResult::MayOverflow;
2006
2007 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2008 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2009
2010 // a u- b overflows low iff a u< b.
2011 if (Max.ult(RHS: OtherMin))
2012 return OverflowResult::AlwaysOverflowsLow;
2013 if (Min.ult(RHS: OtherMax))
2014 return OverflowResult::MayOverflow;
2015 return OverflowResult::NeverOverflows;
2016}
2017
2018ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
2019 const ConstantRange &Other) const {
2020 if (isEmptySet() || Other.isEmptySet())
2021 return OverflowResult::MayOverflow;
2022
2023 APInt Min = getSignedMin(), Max = getSignedMax();
2024 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2025
2026 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
2027 APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
2028
2029 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
2030 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
2031 if (Min.isNonNegative() && OtherMax.isNegative() &&
2032 Min.sgt(RHS: SignedMax + OtherMax))
2033 return OverflowResult::AlwaysOverflowsHigh;
2034 if (Max.isNegative() && OtherMin.isNonNegative() &&
2035 Max.slt(RHS: SignedMin + OtherMin))
2036 return OverflowResult::AlwaysOverflowsLow;
2037
2038 if (Max.isNonNegative() && OtherMin.isNegative() &&
2039 Max.sgt(RHS: SignedMax + OtherMin))
2040 return OverflowResult::MayOverflow;
2041 if (Min.isNegative() && OtherMax.isNonNegative() &&
2042 Min.slt(RHS: SignedMin + OtherMax))
2043 return OverflowResult::MayOverflow;
2044
2045 return OverflowResult::NeverOverflows;
2046}
2047
2048ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
2049 const ConstantRange &Other) const {
2050 if (isEmptySet() || Other.isEmptySet())
2051 return OverflowResult::MayOverflow;
2052
2053 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2054 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2055 bool Overflow;
2056
2057 (void) Min.umul_ov(RHS: OtherMin, Overflow);
2058 if (Overflow)
2059 return OverflowResult::AlwaysOverflowsHigh;
2060
2061 (void) Max.umul_ov(RHS: OtherMax, Overflow);
2062 if (Overflow)
2063 return OverflowResult::MayOverflow;
2064
2065 return OverflowResult::NeverOverflows;
2066}
2067
2068void ConstantRange::print(raw_ostream &OS) const {
2069 if (isFullSet())
2070 OS << "full-set";
2071 else if (isEmptySet())
2072 OS << "empty-set";
2073 else
2074 OS << "[" << Lower << "," << Upper << ")";
2075}
2076
2077#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2078LLVM_DUMP_METHOD void ConstantRange::dump() const {
2079 print(dbgs());
2080}
2081#endif
2082
2083ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
2084 const unsigned NumRanges = Ranges.getNumOperands() / 2;
2085 assert(NumRanges >= 1 && "Must have at least one range!");
2086 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
2087
2088 auto *FirstLow = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 0));
2089 auto *FirstHigh = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 1));
2090
2091 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2092
2093 for (unsigned i = 1; i < NumRanges; ++i) {
2094 auto *Low = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 0));
2095 auto *High = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 1));
2096
2097 // Note: unionWith will potentially create a range that contains values not
2098 // contained in any of the original N ranges.
2099 CR = CR.unionWith(CR: ConstantRange(Low->getValue(), High->getValue()));
2100 }
2101
2102 return CR;
2103}
2104