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