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