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