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
1047ConstantRange ConstantRange::binaryOp(const BinaryOperator &BO,
1048 const ConstantRange &Other) const {
1049 if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: &BO))
1050 return overflowingBinaryOp(BinOp: BO.getOpcode(), Other, NoWrapKind: OBO->getNoWrapKind());
1051
1052 if (BO.getOpcode() == Instruction::Or)
1053 return binaryOr(Other, IsDisjoint: cast<PossiblyDisjointInst>(Val: BO).isDisjoint());
1054
1055 return binaryOp(BinOp: BO.getOpcode(), Other);
1056}
1057
1058bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) {
1059 switch (IntrinsicID) {
1060 case Intrinsic::uadd_sat:
1061 case Intrinsic::usub_sat:
1062 case Intrinsic::sadd_sat:
1063 case Intrinsic::ssub_sat:
1064 case Intrinsic::umin:
1065 case Intrinsic::umax:
1066 case Intrinsic::smin:
1067 case Intrinsic::smax:
1068 case Intrinsic::abs:
1069 case Intrinsic::ctlz:
1070 case Intrinsic::cttz:
1071 case Intrinsic::ctpop:
1072 return true;
1073 default:
1074 return false;
1075 }
1076}
1077
1078ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID,
1079 ArrayRef<ConstantRange> Ops) {
1080 switch (IntrinsicID) {
1081 case Intrinsic::uadd_sat:
1082 return Ops[0].uadd_sat(Other: Ops[1]);
1083 case Intrinsic::usub_sat:
1084 return Ops[0].usub_sat(Other: Ops[1]);
1085 case Intrinsic::sadd_sat:
1086 return Ops[0].sadd_sat(Other: Ops[1]);
1087 case Intrinsic::ssub_sat:
1088 return Ops[0].ssub_sat(Other: Ops[1]);
1089 case Intrinsic::umin:
1090 return Ops[0].umin(Other: Ops[1]);
1091 case Intrinsic::umax:
1092 return Ops[0].umax(Other: Ops[1]);
1093 case Intrinsic::smin:
1094 return Ops[0].smin(Other: Ops[1]);
1095 case Intrinsic::smax:
1096 return Ops[0].smax(Other: Ops[1]);
1097 case Intrinsic::abs: {
1098 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
1099 assert(IntMinIsPoison && "Must be known (immarg)");
1100 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
1101 return Ops[0].abs(IntMinIsPoison: IntMinIsPoison->getBoolValue());
1102 }
1103 case Intrinsic::ctlz: {
1104 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1105 assert(ZeroIsPoison && "Must be known (immarg)");
1106 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1107 return Ops[0].ctlz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
1108 }
1109 case Intrinsic::cttz: {
1110 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1111 assert(ZeroIsPoison && "Must be known (immarg)");
1112 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1113 return Ops[0].cttz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
1114 }
1115 case Intrinsic::ctpop:
1116 return Ops[0].ctpop();
1117 default:
1118 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
1119 llvm_unreachable("Unsupported intrinsic");
1120 }
1121}
1122
1123ConstantRange
1124ConstantRange::add(const ConstantRange &Other) const {
1125 if (isEmptySet() || Other.isEmptySet())
1126 return getEmpty();
1127 if (isFullSet() || Other.isFullSet())
1128 return getFull();
1129
1130 APInt NewLower = getLower() + Other.getLower();
1131 APInt NewUpper = getUpper() + Other.getUpper() - 1;
1132 if (NewLower == NewUpper)
1133 return getFull();
1134
1135 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1136 if (X.isSizeStrictlySmallerThan(Other: *this) ||
1137 X.isSizeStrictlySmallerThan(Other))
1138 // We've wrapped, therefore, full set.
1139 return getFull();
1140 return X;
1141}
1142
1143ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
1144 unsigned NoWrapKind,
1145 PreferredRangeType RangeType) const {
1146 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1147 // (X is from this, and Y is from Other)
1148 if (isEmptySet() || Other.isEmptySet())
1149 return getEmpty();
1150 if (isFullSet() && Other.isFullSet())
1151 return getFull();
1152
1153 using OBO = OverflowingBinaryOperator;
1154 ConstantRange Result = add(Other);
1155
1156 // If an overflow happens for every value pair in these two constant ranges,
1157 // we must return Empty set. In this case, we get that for free, because we
1158 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1159 // in an empty set.
1160
1161 if (NoWrapKind & OBO::NoSignedWrap)
1162 Result = Result.intersectWith(CR: sadd_sat(Other), Type: RangeType);
1163
1164 if (NoWrapKind & OBO::NoUnsignedWrap)
1165 Result = Result.intersectWith(CR: uadd_sat(Other), Type: RangeType);
1166
1167 return Result;
1168}
1169
1170ConstantRange
1171ConstantRange::sub(const ConstantRange &Other) const {
1172 if (isEmptySet() || Other.isEmptySet())
1173 return getEmpty();
1174 if (isFullSet() || Other.isFullSet())
1175 return getFull();
1176
1177 APInt NewLower = getLower() - Other.getUpper() + 1;
1178 APInt NewUpper = getUpper() - Other.getLower();
1179 if (NewLower == NewUpper)
1180 return getFull();
1181
1182 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1183 if (X.isSizeStrictlySmallerThan(Other: *this) ||
1184 X.isSizeStrictlySmallerThan(Other))
1185 // We've wrapped, therefore, full set.
1186 return getFull();
1187 return X;
1188}
1189
1190ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,
1191 unsigned NoWrapKind,
1192 PreferredRangeType RangeType) const {
1193 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1194 // (X is from this, and Y is from Other)
1195 if (isEmptySet() || Other.isEmptySet())
1196 return getEmpty();
1197 if (isFullSet() && Other.isFullSet())
1198 return getFull();
1199
1200 using OBO = OverflowingBinaryOperator;
1201 ConstantRange Result = sub(Other);
1202
1203 // If an overflow happens for every value pair in these two constant ranges,
1204 // we must return Empty set. In signed case, we get that for free, because we
1205 // get lucky that intersection of sub() with ssub_sat() results in an
1206 // empty set. But for unsigned we must perform the overflow check manually.
1207
1208 if (NoWrapKind & OBO::NoSignedWrap)
1209 Result = Result.intersectWith(CR: ssub_sat(Other), Type: RangeType);
1210
1211 if (NoWrapKind & OBO::NoUnsignedWrap) {
1212 if (getUnsignedMax().ult(RHS: Other.getUnsignedMin()))
1213 return getEmpty(); // Always overflows.
1214 Result = Result.intersectWith(CR: usub_sat(Other), Type: RangeType);
1215 }
1216
1217 return Result;
1218}
1219
1220ConstantRange ConstantRange::multiply(const ConstantRange &Other,
1221 unsigned NoWrapKind) const {
1222 // TODO: If either operand is a single element and the multiply is known to
1223 // be non-wrapping, round the result min and max value to the appropriate
1224 // multiple of that element. If wrapping is possible, at least adjust the
1225 // range according to the greatest power-of-two factor of the single element.
1226
1227 if (isEmptySet() || Other.isEmptySet())
1228 return getEmpty();
1229
1230 if (const APInt *C = getSingleElement()) {
1231 if (C->isOne())
1232 return Other;
1233 if (C->isAllOnes())
1234 return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other);
1235 }
1236
1237 if (const APInt *C = Other.getSingleElement()) {
1238 if (C->isOne())
1239 return *this;
1240 if (C->isAllOnes())
1241 return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other: *this);
1242 }
1243
1244 // Multiplication is signedness-independent. However different ranges can be
1245 // obtained depending on how the input ranges are treated. These different
1246 // ranges are all conservatively correct, but one might be better than the
1247 // other. We calculate two ranges; one treating the inputs as unsigned
1248 // and the other signed, then return the smallest of these ranges.
1249
1250 // Unsigned range first.
1251 unsigned BW = getBitWidth();
1252 ConstantRange UR = getEmpty();
1253 if (NoWrapKind & OverflowingBinaryOperator::NoUnsignedWrap) {
1254 bool MinOv;
1255 APInt MinMul = getUnsignedMin().umul_ov(RHS: Other.getUnsignedMin(), Overflow&: MinOv);
1256 if (MinOv)
1257 return getEmpty();
1258
1259 APInt MaxMul = getUnsignedMax().umul_sat(RHS: Other.getUnsignedMax());
1260 UR = ConstantRange::getNonEmpty(Lower: MinMul, Upper: MaxMul + 1);
1261 } else {
1262 APInt this_min = getUnsignedMin().zext(width: BW * 2);
1263 APInt this_max = getUnsignedMax().zext(width: BW * 2);
1264 APInt Other_min = Other.getUnsignedMin().zext(width: BW * 2);
1265 APInt Other_max = Other.getUnsignedMax().zext(width: BW * 2);
1266
1267 ConstantRange Result_zext =
1268 ConstantRange(this_min * Other_min, this_max * Other_max + 1);
1269 UR = Result_zext.truncate(DstTySize: BW);
1270 }
1271
1272 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1273 // from one positive number to another which is as good as we can generate.
1274 // In this case, skip the extra work of generating signed ranges which aren't
1275 // going to be better than this range.
1276 if (!(NoWrapKind & OverflowingBinaryOperator::NoSignedWrap) &&
1277 !UR.isUpperWrapped() &&
1278 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
1279 return UR;
1280
1281 // Now the signed range. Because we could be dealing with negative numbers
1282 // here, the lower bound is the smallest of the cartesian product of the
1283 // lower and upper ranges; for example:
1284 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1285 // Similarly for the upper bound, swapping min for max.
1286
1287 // FIXME: Avoid wide multiplications if nsw.
1288 APInt this_min = getSignedMin().sext(width: BW * 2);
1289 APInt this_max = getSignedMax().sext(width: BW * 2);
1290 APInt Other_min = Other.getSignedMin().sext(width: BW * 2);
1291 APInt Other_max = Other.getSignedMax().sext(width: BW * 2);
1292
1293 auto L = {this_min * Other_min, this_min * Other_max,
1294 this_max * Other_min, this_max * Other_max};
1295 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1296 ConstantRange Result_sext(std::min(l: L, comp: Compare), std::max(l: L, comp: Compare) + 1);
1297 if (NoWrapKind & OverflowingBinaryOperator::NoSignedWrap) {
1298 Result_sext = Result_sext.intersectWith(
1299 CR: ConstantRange(APInt::getSignedMinValue(numBits: BW).sext(width: BW * 2),
1300 APInt::getSignedMaxValue(numBits: BW).sext(width: BW * 2) + 1));
1301 }
1302 ConstantRange SR = Result_sext.truncate(DstTySize: BW);
1303 ConstantRange Result = UR.isSizeStrictlySmallerThan(Other: SR) ? UR : SR;
1304
1305 // mul nsw nuw X, Y s>= 0 if X s> 1 or Y s> 1
1306 if ((NoWrapKind == (OverflowingBinaryOperator::NoSignedWrap |
1307 OverflowingBinaryOperator::NoUnsignedWrap)) &&
1308 !Result.isAllNonNegative()) {
1309 if (getSignedMin().sgt(RHS: 1) || Other.getSignedMin().sgt(RHS: 1))
1310 Result = Result.intersectWith(
1311 CR: getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
1312 Upper: APInt::getSignedMinValue(numBits: getBitWidth())));
1313 }
1314
1315 return Result;
1316}
1317
1318ConstantRange ConstantRange::smul_fast(const ConstantRange &Other) const {
1319 if (isEmptySet() || Other.isEmptySet())
1320 return getEmpty();
1321
1322 APInt Min = getSignedMin();
1323 APInt Max = getSignedMax();
1324 APInt OtherMin = Other.getSignedMin();
1325 APInt OtherMax = Other.getSignedMax();
1326
1327 bool O1, O2, O3, O4;
1328 auto Muls = {Min.smul_ov(RHS: OtherMin, Overflow&: O1), Min.smul_ov(RHS: OtherMax, Overflow&: O2),
1329 Max.smul_ov(RHS: OtherMin, Overflow&: O3), Max.smul_ov(RHS: OtherMax, Overflow&: O4)};
1330 if (O1 || O2 || O3 || O4)
1331 return getFull();
1332
1333 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1334 return getNonEmpty(Lower: std::min(l: Muls, comp: Compare), Upper: std::max(l: Muls, comp: Compare) + 1);
1335}
1336
1337ConstantRange
1338ConstantRange::smax(const ConstantRange &Other) const {
1339 // X smax Y is: range(smax(X_smin, Y_smin),
1340 // smax(X_smax, Y_smax))
1341 if (isEmptySet() || Other.isEmptySet())
1342 return getEmpty();
1343 APInt NewL = APIntOps::smax(A: getSignedMin(), B: Other.getSignedMin());
1344 APInt NewU = APIntOps::smax(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1345 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1346 if (isSignWrappedSet() || Other.isSignWrappedSet())
1347 return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1348 return Res;
1349}
1350
1351ConstantRange
1352ConstantRange::umax(const ConstantRange &Other) const {
1353 // X umax Y is: range(umax(X_umin, Y_umin),
1354 // umax(X_umax, Y_umax))
1355 if (isEmptySet() || Other.isEmptySet())
1356 return getEmpty();
1357 APInt NewL = APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin());
1358 APInt NewU = APIntOps::umax(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1359 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1360 if (isWrappedSet() || Other.isWrappedSet())
1361 return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1362 return Res;
1363}
1364
1365ConstantRange
1366ConstantRange::smin(const ConstantRange &Other) const {
1367 // X smin Y is: range(smin(X_smin, Y_smin),
1368 // smin(X_smax, Y_smax))
1369 if (isEmptySet() || Other.isEmptySet())
1370 return getEmpty();
1371 APInt NewL = APIntOps::smin(A: getSignedMin(), B: Other.getSignedMin());
1372 APInt NewU = APIntOps::smin(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1373 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1374 if (isSignWrappedSet() || Other.isSignWrappedSet())
1375 return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1376 return Res;
1377}
1378
1379ConstantRange
1380ConstantRange::umin(const ConstantRange &Other) const {
1381 // X umin Y is: range(umin(X_umin, Y_umin),
1382 // umin(X_umax, Y_umax))
1383 if (isEmptySet() || Other.isEmptySet())
1384 return getEmpty();
1385 APInt NewL = APIntOps::umin(A: getUnsignedMin(), B: Other.getUnsignedMin());
1386 APInt NewU = APIntOps::umin(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1387 ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1388 if (isWrappedSet() || Other.isWrappedSet())
1389 return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1390 return Res;
1391}
1392
1393ConstantRange
1394ConstantRange::udiv(const ConstantRange &RHS) const {
1395 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1396 return getEmpty();
1397
1398 APInt Lower = getUnsignedMin().udiv(RHS: RHS.getUnsignedMax());
1399
1400 APInt RHS_umin = RHS.getUnsignedMin();
1401 if (RHS_umin.isZero()) {
1402 // We want the lowest value in RHS excluding zero. Usually that would be 1
1403 // except for a range in the form of [X, 1) in which case it would be X.
1404 if (RHS.getUpper() == 1)
1405 RHS_umin = RHS.getLower();
1406 else
1407 RHS_umin = 1;
1408 }
1409
1410 APInt Upper = getUnsignedMax().udiv(RHS: RHS_umin) + 1;
1411 return getNonEmpty(Lower: std::move(Lower), Upper: std::move(Upper));
1412}
1413
1414ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {
1415 APInt Zero = APInt::getZero(numBits: getBitWidth());
1416 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1417
1418 // We split up the LHS and RHS into positive and negative components
1419 // and then also compute the positive and negative components of the result
1420 // separately by combining division results with the appropriate signs.
1421 auto [PosL, NegL] = splitPosNeg();
1422 auto [PosR, NegR] = RHS.splitPosNeg();
1423
1424 ConstantRange PosRes = getEmpty();
1425 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1426 // pos / pos = pos.
1427 PosRes = ConstantRange(PosL.Lower.sdiv(RHS: PosR.Upper - 1),
1428 (PosL.Upper - 1).sdiv(RHS: PosR.Lower) + 1);
1429
1430 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1431 // neg / neg = pos.
1432 //
1433 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1434 // IR level, so we'll want to exclude this case when calculating bounds.
1435 // (For APInts the operation is well-defined and yields SignedMin.) We
1436 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1437 APInt Lo = (NegL.Upper - 1).sdiv(RHS: NegR.Lower);
1438 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1439 // Remove -1 from the LHS. Skip if it's the only element, as this would
1440 // leave us with an empty set.
1441 if (!NegR.Lower.isAllOnes()) {
1442 APInt AdjNegRUpper;
1443 if (RHS.Lower.isAllOnes())
1444 // Negative part of [-1, X] without -1 is [SignedMin, X].
1445 AdjNegRUpper = RHS.Upper;
1446 else
1447 // [X, -1] without -1 is [X, -2].
1448 AdjNegRUpper = NegR.Upper - 1;
1449
1450 PosRes = PosRes.unionWith(
1451 CR: ConstantRange(Lo, NegL.Lower.sdiv(RHS: AdjNegRUpper - 1) + 1));
1452 }
1453
1454 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1455 // would leave us with an empty set.
1456 if (NegL.Upper != SignedMin + 1) {
1457 APInt AdjNegLLower;
1458 if (Upper == SignedMin + 1)
1459 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1460 AdjNegLLower = Lower;
1461 else
1462 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1463 AdjNegLLower = NegL.Lower + 1;
1464
1465 PosRes = PosRes.unionWith(
1466 CR: ConstantRange(std::move(Lo),
1467 AdjNegLLower.sdiv(RHS: NegR.Upper - 1) + 1));
1468 }
1469 } else {
1470 PosRes = PosRes.unionWith(
1471 CR: ConstantRange(std::move(Lo), NegL.Lower.sdiv(RHS: NegR.Upper - 1) + 1));
1472 }
1473 }
1474
1475 ConstantRange NegRes = getEmpty();
1476 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1477 // pos / neg = neg.
1478 NegRes = ConstantRange((PosL.Upper - 1).sdiv(RHS: NegR.Upper - 1),
1479 PosL.Lower.sdiv(RHS: NegR.Lower) + 1);
1480
1481 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1482 // neg / pos = neg.
1483 NegRes = NegRes.unionWith(
1484 CR: ConstantRange(NegL.Lower.sdiv(RHS: PosR.Lower),
1485 (NegL.Upper - 1).sdiv(RHS: PosR.Upper - 1) + 1));
1486
1487 // Prefer a non-wrapping signed range here.
1488 ConstantRange Res = NegRes.unionWith(CR: PosRes, Type: PreferredRangeType::Signed);
1489
1490 // Preserve the zero that we dropped when splitting the LHS by sign.
1491 if (contains(V: Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1492 Res = Res.unionWith(CR: ConstantRange(Zero));
1493 return Res;
1494}
1495
1496ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
1497 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1498 return getEmpty();
1499
1500 if (const APInt *RHSInt = RHS.getSingleElement()) {
1501 // UREM by null is UB.
1502 if (RHSInt->isZero())
1503 return getEmpty();
1504 // Use APInt's implementation of UREM for single element ranges.
1505 if (const APInt *LHSInt = getSingleElement())
1506 return {LHSInt->urem(RHS: *RHSInt)};
1507 }
1508
1509 // L % R for L < R is L.
1510 if (getUnsignedMax().ult(RHS: RHS.getUnsignedMin()))
1511 return *this;
1512
1513 // L % R is <= L and < R.
1514 APInt Upper = APIntOps::umin(A: getUnsignedMax(), B: RHS.getUnsignedMax() - 1) + 1;
1515 return getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()), Upper: std::move(Upper));
1516}
1517
1518ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1519 if (isEmptySet() || RHS.isEmptySet())
1520 return getEmpty();
1521
1522 if (const APInt *RHSInt = RHS.getSingleElement()) {
1523 // SREM by null is UB.
1524 if (RHSInt->isZero())
1525 return getEmpty();
1526 // Use APInt's implementation of SREM for single element ranges.
1527 if (const APInt *LHSInt = getSingleElement())
1528 return {LHSInt->srem(RHS: *RHSInt)};
1529 }
1530
1531 ConstantRange AbsRHS = RHS.abs();
1532 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1533 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1534
1535 // Modulus by zero is UB.
1536 if (MaxAbsRHS.isZero())
1537 return getEmpty();
1538
1539 if (MinAbsRHS.isZero())
1540 ++MinAbsRHS;
1541
1542 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1543
1544 if (MinLHS.isNonNegative()) {
1545 // L % R for L < R is L.
1546 if (MaxLHS.ult(RHS: MinAbsRHS))
1547 return *this;
1548
1549 // L % R is <= L and < R.
1550 APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1551 return ConstantRange(APInt::getZero(numBits: getBitWidth()), std::move(Upper));
1552 }
1553
1554 // Same basic logic as above, but the result is negative.
1555 if (MaxLHS.isNegative()) {
1556 if (MinLHS.ugt(RHS: -MinAbsRHS))
1557 return *this;
1558
1559 APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1560 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1561 }
1562
1563 // LHS range crosses zero.
1564 APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1565 APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1566 return ConstantRange(std::move(Lower), std::move(Upper));
1567}
1568
1569ConstantRange ConstantRange::binaryNot() const {
1570 return ConstantRange(APInt::getAllOnes(numBits: getBitWidth())).sub(Other: *this);
1571}
1572
1573/// Estimate the 'bit-masked AND' operation's lower bound.
1574///
1575/// E.g., given two ranges as follows (single quotes are separators and
1576/// have no meaning here),
1577///
1578/// LHS = [10'00101'1, ; LLo
1579/// 10'10000'0] ; LHi
1580/// RHS = [10'11111'0, ; RLo
1581/// 10'11111'1] ; RHi
1582///
1583/// we know that the higher 2 bits of the result is always 10; and we also
1584/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than
1585/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.
1586///
1587/// The algorithm is as follows,
1588/// 1. we first calculate a mask to find the higher common bits by
1589/// Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
1590/// Mask = clear all non-leading-ones bits in Mask;
1591/// in the example, the Mask is set to 11'00000'0;
1592/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and
1593/// keeping the longest leading ones (i.e., 11'11111'0 in the example);
1594/// 3. return (LLo & new mask) as the lower bound;
1595/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
1596/// bound with the larger one.
1597static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
1598 const ConstantRange &RHS) {
1599 auto BitWidth = LHS.getBitWidth();
1600 // If either is full set or unsigned wrapped, then the range must contain '0'
1601 // which leads the lower bound to 0.
1602 if ((LHS.isFullSet() || RHS.isFullSet()) ||
1603 (LHS.isWrappedSet() || RHS.isWrappedSet()))
1604 return APInt::getZero(numBits: BitWidth);
1605
1606 auto LLo = LHS.getLower();
1607 auto LHi = LHS.getUpper() - 1;
1608 auto RLo = RHS.getLower();
1609 auto RHi = RHS.getUpper() - 1;
1610
1611 // Calculate the mask for the higher common bits.
1612 auto Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
1613 unsigned LeadingOnes = Mask.countLeadingOnes();
1614 Mask.clearLowBits(loBits: BitWidth - LeadingOnes);
1615
1616 auto estimateBound = [BitWidth, &Mask](APInt ALo, const APInt &BLo,
1617 const APInt &BHi) {
1618 unsigned LeadingOnes = ((BLo & BHi) | Mask).countLeadingOnes();
1619 unsigned StartBit = BitWidth - LeadingOnes;
1620 ALo.clearLowBits(loBits: StartBit);
1621 return ALo;
1622 };
1623
1624 auto LowerBoundByLHS = estimateBound(LLo, RLo, RHi);
1625 auto LowerBoundByRHS = estimateBound(RLo, LLo, LHi);
1626
1627 return APIntOps::umax(A: LowerBoundByLHS, B: LowerBoundByRHS);
1628}
1629
1630ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const {
1631 if (isEmptySet() || Other.isEmptySet())
1632 return getEmpty();
1633
1634 ConstantRange KnownBitsRange =
1635 fromKnownBits(Known: toKnownBits() & Other.toKnownBits(), IsSigned: false);
1636 auto LowerBound = estimateBitMaskedAndLowerBound(LHS: *this, RHS: Other);
1637 ConstantRange UMinUMaxRange = getNonEmpty(
1638 Lower: LowerBound, Upper: APIntOps::umin(A: Other.getUnsignedMax(), B: getUnsignedMax()) + 1);
1639 return KnownBitsRange.intersectWith(CR: UMinUMaxRange);
1640}
1641
1642ConstantRange ConstantRange::binaryOr(const ConstantRange &Other,
1643 bool IsDisjoint) const {
1644 if (isEmptySet() || Other.isEmptySet())
1645 return getEmpty();
1646
1647 ConstantRange KnownBitsRange =
1648 fromKnownBits(Known: toKnownBits() | Other.toKnownBits(), IsSigned: false);
1649
1650 // ~a & ~b >= x
1651 // <=> ~(~a & ~b) <= ~x
1652 // <=> a | b <= ~x
1653 // <=> a | b < ~x + 1 = -x
1654 // thus, UpperBound(a | b) == -LowerBound(~a & ~b)
1655 auto UpperBound =
1656 -estimateBitMaskedAndLowerBound(LHS: binaryNot(), RHS: Other.binaryNot());
1657 // Upper wrapped range.
1658 ConstantRange UMaxUMinRange = getNonEmpty(
1659 Lower: APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin()), Upper: UpperBound);
1660 ConstantRange Result = KnownBitsRange.intersectWith(CR: UMaxUMinRange);
1661
1662 if (IsDisjoint) {
1663 // Treat 'or disjoint' as both 'add nuw nsw' and binary or, picking the best
1664 // from both.
1665 using OBO = OverflowingBinaryOperator;
1666 Result = addWithNoWrap(Other, NoWrapKind: OBO::NoUnsignedWrap | OBO::NoSignedWrap)
1667 .intersectWith(CR: Result);
1668 }
1669 return Result;
1670}
1671
1672ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {
1673 if (isEmptySet() || Other.isEmptySet())
1674 return getEmpty();
1675
1676 // Use APInt's implementation of XOR for single element ranges.
1677 if (isSingleElement() && Other.isSingleElement())
1678 return {*getSingleElement() ^ *Other.getSingleElement()};
1679
1680 // Special-case binary complement, since we can give a precise answer.
1681 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1682 return binaryNot();
1683 if (isSingleElement() && getSingleElement()->isAllOnes())
1684 return Other.binaryNot();
1685
1686 KnownBits LHSKnown = toKnownBits();
1687 KnownBits RHSKnown = Other.toKnownBits();
1688 KnownBits Known = LHSKnown ^ RHSKnown;
1689 ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);
1690 // Typically the following code doesn't improve the result if BW = 1.
1691 if (getBitWidth() == 1)
1692 return CR;
1693
1694 // If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw
1695 // LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS
1696 // -nuw/nsw RHS.
1697 if ((~LHSKnown.Zero).isSubsetOf(RHS: RHSKnown.One))
1698 CR = CR.intersectWith(CR: Other.sub(Other: *this), Type: PreferredRangeType::Unsigned);
1699 else if ((~RHSKnown.Zero).isSubsetOf(RHS: LHSKnown.One))
1700 CR = CR.intersectWith(CR: this->sub(Other), Type: PreferredRangeType::Unsigned);
1701 return CR;
1702}
1703
1704ConstantRange
1705ConstantRange::shl(const ConstantRange &Other) const {
1706 if (isEmptySet() || Other.isEmptySet())
1707 return getEmpty();
1708
1709 APInt Min = getUnsignedMin();
1710 APInt Max = getUnsignedMax();
1711 if (const APInt *RHS = Other.getSingleElement()) {
1712 unsigned BW = getBitWidth();
1713 if (RHS->uge(RHS: BW))
1714 return getEmpty();
1715
1716 unsigned EqualLeadingBits = (Min ^ Max).countl_zero();
1717 if (RHS->ule(RHS: EqualLeadingBits))
1718 return getNonEmpty(Lower: Min << *RHS, Upper: (Max << *RHS) + 1);
1719
1720 return getNonEmpty(Lower: APInt::getZero(numBits: BW),
1721 Upper: APInt::getBitsSetFrom(numBits: BW, loBit: RHS->getZExtValue()) + 1);
1722 }
1723
1724 APInt OtherMax = Other.getUnsignedMax();
1725 if (isAllNegative() && OtherMax.ule(RHS: Min.countl_one())) {
1726 // For negative numbers, if the shift does not overflow in a signed sense,
1727 // a larger shift will make the number smaller.
1728 Max <<= Other.getUnsignedMin();
1729 Min <<= OtherMax;
1730 return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1731 }
1732
1733 // There's overflow!
1734 if (OtherMax.ugt(RHS: Max.countl_zero()))
1735 return getFull();
1736
1737 // FIXME: implement the other tricky cases
1738
1739 Min <<= Other.getUnsignedMin();
1740 Max <<= OtherMax;
1741
1742 return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1743}
1744
1745static ConstantRange computeShlNUW(const ConstantRange &LHS,
1746 const ConstantRange &RHS) {
1747 unsigned BitWidth = LHS.getBitWidth();
1748 bool Overflow;
1749 APInt LHSMin = LHS.getUnsignedMin();
1750 unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(Limit: BitWidth);
1751 APInt MinShl = LHSMin.ushl_ov(Amt: RHSMin, Overflow);
1752 if (Overflow)
1753 return ConstantRange::getEmpty(BitWidth);
1754 APInt LHSMax = LHS.getUnsignedMax();
1755 unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(Limit: BitWidth);
1756 APInt MaxShl = MinShl;
1757 unsigned MaxShAmt = LHSMax.countLeadingZeros();
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());
1762 if (RHSMin <= RHSMax)
1763 MaxShl = APIntOps::umax(A: MaxShl,
1764 B: APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - RHSMin));
1765 return ConstantRange::getNonEmpty(Lower: MinShl, Upper: MaxShl + 1);
1766}
1767
1768static ConstantRange computeShlNSWWithNNegLHS(const APInt &LHSMin,
1769 const APInt &LHSMax,
1770 unsigned RHSMin,
1771 unsigned RHSMax) {
1772 unsigned BitWidth = LHSMin.getBitWidth();
1773 bool Overflow;
1774 APInt MinShl = LHSMin.sshl_ov(Amt: RHSMin, Overflow);
1775 if (Overflow)
1776 return ConstantRange::getEmpty(BitWidth);
1777 APInt MaxShl = MinShl;
1778 unsigned MaxShAmt = LHSMax.countLeadingZeros() - 1;
1779 if (RHSMin <= MaxShAmt)
1780 MaxShl = LHSMax << std::min(a: RHSMax, b: MaxShAmt);
1781 RHSMin = std::max(a: RHSMin, b: MaxShAmt + 1);
1782 RHSMax = std::min(a: RHSMax, b: LHSMin.countLeadingZeros() - 1);
1783 if (RHSMin <= RHSMax)
1784 MaxShl = APIntOps::umax(A: MaxShl,
1785 B: APInt::getBitsSet(numBits: BitWidth, loBit: RHSMin, hiBit: BitWidth - 1));
1786 return ConstantRange::getNonEmpty(Lower: MinShl, Upper: MaxShl + 1);
1787}
1788
1789static ConstantRange computeShlNSWWithNegLHS(const APInt &LHSMin,
1790 const APInt &LHSMax,
1791 unsigned RHSMin, unsigned RHSMax) {
1792 unsigned BitWidth = LHSMin.getBitWidth();
1793 bool Overflow;
1794 APInt MaxShl = LHSMax.sshl_ov(Amt: RHSMin, Overflow);
1795 if (Overflow)
1796 return ConstantRange::getEmpty(BitWidth);
1797 APInt MinShl = MaxShl;
1798 unsigned MaxShAmt = LHSMin.countLeadingOnes() - 1;
1799 if (RHSMin <= MaxShAmt)
1800 MinShl = LHSMin.shl(shiftAmt: std::min(a: RHSMax, b: MaxShAmt));
1801 RHSMin = std::max(a: RHSMin, b: MaxShAmt + 1);
1802 RHSMax = std::min(a: RHSMax, b: LHSMax.countLeadingOnes() - 1);
1803 if (RHSMin <= RHSMax)
1804 MinShl = APInt::getSignMask(BitWidth);
1805 return ConstantRange::getNonEmpty(Lower: MinShl, Upper: MaxShl + 1);
1806}
1807
1808static ConstantRange computeShlNSW(const ConstantRange &LHS,
1809 const ConstantRange &RHS) {
1810 unsigned BitWidth = LHS.getBitWidth();
1811 unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(Limit: BitWidth);
1812 unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(Limit: BitWidth);
1813 APInt LHSMin = LHS.getSignedMin();
1814 APInt LHSMax = LHS.getSignedMax();
1815 if (LHSMin.isNonNegative())
1816 return computeShlNSWWithNNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);
1817 else if (LHSMax.isNegative())
1818 return computeShlNSWWithNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);
1819 return computeShlNSWWithNNegLHS(LHSMin: APInt::getZero(numBits: BitWidth), LHSMax, RHSMin,
1820 RHSMax)
1821 .unionWith(CR: computeShlNSWWithNegLHS(LHSMin, LHSMax: APInt::getAllOnes(numBits: BitWidth),
1822 RHSMin, RHSMax),
1823 Type: ConstantRange::Signed);
1824}
1825
1826ConstantRange ConstantRange::shlWithNoWrap(const ConstantRange &Other,
1827 unsigned NoWrapKind,
1828 PreferredRangeType RangeType) const {
1829 if (isEmptySet() || Other.isEmptySet())
1830 return getEmpty();
1831
1832 switch (NoWrapKind) {
1833 case 0:
1834 return shl(Other);
1835 case OverflowingBinaryOperator::NoSignedWrap:
1836 return computeShlNSW(LHS: *this, RHS: Other);
1837 case OverflowingBinaryOperator::NoUnsignedWrap:
1838 return computeShlNUW(LHS: *this, RHS: Other);
1839 case OverflowingBinaryOperator::NoSignedWrap |
1840 OverflowingBinaryOperator::NoUnsignedWrap:
1841 return computeShlNSW(LHS: *this, RHS: Other)
1842 .intersectWith(CR: computeShlNUW(LHS: *this, RHS: Other), Type: RangeType);
1843 default:
1844 llvm_unreachable("Invalid NoWrapKind");
1845 }
1846}
1847
1848ConstantRange
1849ConstantRange::lshr(const ConstantRange &Other) const {
1850 if (isEmptySet() || Other.isEmptySet())
1851 return getEmpty();
1852
1853 APInt max = getUnsignedMax().lshr(ShiftAmt: Other.getUnsignedMin()) + 1;
1854 APInt min = getUnsignedMin().lshr(ShiftAmt: Other.getUnsignedMax());
1855 return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1856}
1857
1858ConstantRange
1859ConstantRange::ashr(const ConstantRange &Other) const {
1860 if (isEmptySet() || Other.isEmptySet())
1861 return getEmpty();
1862
1863 // May straddle zero, so handle both positive and negative cases.
1864 // 'PosMax' is the upper bound of the result of the ashr
1865 // operation, when Upper of the LHS of ashr is a non-negative.
1866 // number. Since ashr of a non-negative number will result in a
1867 // smaller number, the Upper value of LHS is shifted right with
1868 // the minimum value of 'Other' instead of the maximum value.
1869 APInt PosMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMin()) + 1;
1870
1871 // 'PosMin' is the lower bound of the result of the ashr
1872 // operation, when Lower of the LHS is a non-negative number.
1873 // Since ashr of a non-negative number will result in a smaller
1874 // number, the Lower value of LHS is shifted right with the
1875 // maximum value of 'Other'.
1876 APInt PosMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMax());
1877
1878 // 'NegMax' is the upper bound of the result of the ashr
1879 // operation, when Upper of the LHS of ashr is a negative number.
1880 // Since 'ashr' of a negative number will result in a bigger
1881 // number, the Upper value of LHS is shifted right with the
1882 // maximum value of 'Other'.
1883 APInt NegMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMax()) + 1;
1884
1885 // 'NegMin' is the lower bound of the result of the ashr
1886 // operation, when Lower of the LHS of ashr is a negative number.
1887 // Since 'ashr' of a negative number will result in a bigger
1888 // number, the Lower value of LHS is shifted right with the
1889 // minimum value of 'Other'.
1890 APInt NegMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMin());
1891
1892 APInt max, min;
1893 if (getSignedMin().isNonNegative()) {
1894 // Upper and Lower of LHS are non-negative.
1895 min = std::move(PosMin);
1896 max = std::move(PosMax);
1897 } else if (getSignedMax().isNegative()) {
1898 // Upper and Lower of LHS are negative.
1899 min = std::move(NegMin);
1900 max = std::move(NegMax);
1901 } else {
1902 // Upper is non-negative and Lower is negative.
1903 min = std::move(NegMin);
1904 max = std::move(PosMax);
1905 }
1906 return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1907}
1908
1909ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {
1910 if (isEmptySet() || Other.isEmptySet())
1911 return getEmpty();
1912
1913 APInt NewL = getUnsignedMin().uadd_sat(RHS: Other.getUnsignedMin());
1914 APInt NewU = getUnsignedMax().uadd_sat(RHS: Other.getUnsignedMax()) + 1;
1915 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1916}
1917
1918ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {
1919 if (isEmptySet() || Other.isEmptySet())
1920 return getEmpty();
1921
1922 APInt NewL = getSignedMin().sadd_sat(RHS: Other.getSignedMin());
1923 APInt NewU = getSignedMax().sadd_sat(RHS: Other.getSignedMax()) + 1;
1924 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1925}
1926
1927ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {
1928 if (isEmptySet() || Other.isEmptySet())
1929 return getEmpty();
1930
1931 APInt NewL = getUnsignedMin().usub_sat(RHS: Other.getUnsignedMax());
1932 APInt NewU = getUnsignedMax().usub_sat(RHS: Other.getUnsignedMin()) + 1;
1933 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1934}
1935
1936ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
1937 if (isEmptySet() || Other.isEmptySet())
1938 return getEmpty();
1939
1940 APInt NewL = getSignedMin().ssub_sat(RHS: Other.getSignedMax());
1941 APInt NewU = getSignedMax().ssub_sat(RHS: Other.getSignedMin()) + 1;
1942 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1943}
1944
1945ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {
1946 if (isEmptySet() || Other.isEmptySet())
1947 return getEmpty();
1948
1949 APInt NewL = getUnsignedMin().umul_sat(RHS: Other.getUnsignedMin());
1950 APInt NewU = getUnsignedMax().umul_sat(RHS: Other.getUnsignedMax()) + 1;
1951 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1952}
1953
1954ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {
1955 if (isEmptySet() || Other.isEmptySet())
1956 return getEmpty();
1957
1958 // Because we could be dealing with negative numbers here, the lower bound is
1959 // the smallest of the cartesian product of the lower and upper ranges;
1960 // for example:
1961 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1962 // Similarly for the upper bound, swapping min for max.
1963
1964 APInt Min = getSignedMin();
1965 APInt Max = getSignedMax();
1966 APInt OtherMin = Other.getSignedMin();
1967 APInt OtherMax = Other.getSignedMax();
1968
1969 auto L = {Min.smul_sat(RHS: OtherMin), Min.smul_sat(RHS: OtherMax),
1970 Max.smul_sat(RHS: OtherMin), Max.smul_sat(RHS: OtherMax)};
1971 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1972 return getNonEmpty(Lower: std::min(l: L, comp: Compare), Upper: std::max(l: L, comp: Compare) + 1);
1973}
1974
1975ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
1976 if (isEmptySet() || Other.isEmptySet())
1977 return getEmpty();
1978
1979 APInt NewL = getUnsignedMin().ushl_sat(RHS: Other.getUnsignedMin());
1980 APInt NewU = getUnsignedMax().ushl_sat(RHS: Other.getUnsignedMax()) + 1;
1981 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1982}
1983
1984ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {
1985 if (isEmptySet() || Other.isEmptySet())
1986 return getEmpty();
1987
1988 APInt Min = getSignedMin(), Max = getSignedMax();
1989 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1990 APInt NewL = Min.sshl_sat(RHS: Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1991 APInt NewU = Max.sshl_sat(RHS: Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1992 return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1993}
1994
1995ConstantRange ConstantRange::inverse() const {
1996 if (isFullSet())
1997 return getEmpty();
1998 if (isEmptySet())
1999 return getFull();
2000 return ConstantRange(Upper, Lower);
2001}
2002
2003ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
2004 if (isEmptySet())
2005 return getEmpty();
2006
2007 if (isSignWrappedSet()) {
2008 APInt Lo;
2009 // Check whether the range crosses zero.
2010 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
2011 Lo = APInt::getZero(numBits: getBitWidth());
2012 else
2013 Lo = APIntOps::umin(A: Lower, B: -Upper + 1);
2014
2015 // If SignedMin is not poison, then it is included in the result range.
2016 if (IntMinIsPoison)
2017 return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()));
2018 else
2019 return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()) + 1);
2020 }
2021
2022 APInt SMin = getSignedMin(), SMax = getSignedMax();
2023
2024 // Skip SignedMin if it is poison.
2025 if (IntMinIsPoison && SMin.isMinSignedValue()) {
2026 // The range may become empty if it *only* contains SignedMin.
2027 if (SMax.isMinSignedValue())
2028 return getEmpty();
2029 ++SMin;
2030 }
2031
2032 // All non-negative.
2033 if (SMin.isNonNegative())
2034 return ConstantRange(SMin, SMax + 1);
2035
2036 // All negative.
2037 if (SMax.isNegative())
2038 return ConstantRange(-SMax, -SMin + 1);
2039
2040 // Range crosses zero.
2041 return ConstantRange::getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
2042 Upper: APIntOps::umax(A: -SMin, B: SMax) + 1);
2043}
2044
2045ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {
2046 if (isEmptySet())
2047 return getEmpty();
2048
2049 APInt Zero = APInt::getZero(numBits: getBitWidth());
2050 if (ZeroIsPoison && contains(V: Zero)) {
2051 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
2052 // which a zero can appear:
2053 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
2054 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
2055 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
2056
2057 if (getLower().isZero()) {
2058 if ((getUpper() - 1).isZero()) {
2059 // We have in input interval of kind [0, 1). In this case we cannot
2060 // really help but return empty-set.
2061 return getEmpty();
2062 }
2063
2064 // Compute the resulting range by excluding zero from Lower.
2065 return ConstantRange(
2066 APInt(getBitWidth(), (getUpper() - 1).countl_zero()),
2067 APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));
2068 } else if ((getUpper() - 1).isZero()) {
2069 // Compute the resulting range by excluding zero from Upper.
2070 return ConstantRange(Zero,
2071 APInt(getBitWidth(), getLower().countl_zero() + 1));
2072 } else {
2073 return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));
2074 }
2075 }
2076
2077 // Zero is either safe or not in the range. The output range is composed by
2078 // the result of countLeadingZero of the two extremes.
2079 return getNonEmpty(Lower: APInt(getBitWidth(), getUnsignedMax().countl_zero()),
2080 Upper: APInt(getBitWidth(), getUnsignedMin().countl_zero()) + 1);
2081}
2082
2083static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower,
2084 const APInt &Upper) {
2085 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
2086 "Unexpected wrapped set.");
2087 assert(Lower != Upper && "Unexpected empty set.");
2088 unsigned BitWidth = Lower.getBitWidth();
2089 if (Lower + 1 == Upper)
2090 return ConstantRange(APInt(BitWidth, Lower.countr_zero()));
2091 if (Lower.isZero())
2092 return ConstantRange(APInt::getZero(numBits: BitWidth),
2093 APInt(BitWidth, BitWidth + 1));
2094
2095 // Calculate longest common prefix.
2096 unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();
2097 // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().
2098 // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).
2099 return ConstantRange(
2100 APInt::getZero(numBits: BitWidth),
2101 APInt(BitWidth,
2102 std::max(a: BitWidth - LCPLength - 1, b: Lower.countr_zero()) + 1));
2103}
2104
2105ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {
2106 if (isEmptySet())
2107 return getEmpty();
2108
2109 unsigned BitWidth = getBitWidth();
2110 APInt Zero = APInt::getZero(numBits: BitWidth);
2111 if (ZeroIsPoison && contains(V: Zero)) {
2112 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
2113 // which a zero can appear:
2114 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
2115 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
2116 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
2117
2118 if (Lower.isZero()) {
2119 if (Upper == 1) {
2120 // We have in input interval of kind [0, 1). In this case we cannot
2121 // really help but return empty-set.
2122 return getEmpty();
2123 }
2124
2125 // Compute the resulting range by excluding zero from Lower.
2126 return getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
2127 } else if (Upper == 1) {
2128 // Compute the resulting range by excluding zero from Upper.
2129 return getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
2130 } else {
2131 ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
2132 ConstantRange CR2 =
2133 getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
2134 return CR1.unionWith(CR: CR2);
2135 }
2136 }
2137
2138 if (isFullSet())
2139 return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth) + 1);
2140 if (!isWrappedSet())
2141 return getUnsignedCountTrailingZerosRange(Lower, Upper);
2142 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
2143 // [Lower, 0).
2144 // Handle [Lower, 0)
2145 ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
2146 // Handle [0, Upper)
2147 ConstantRange CR2 = getUnsignedCountTrailingZerosRange(Lower: Zero, Upper);
2148 return CR1.unionWith(CR: CR2);
2149}
2150
2151static ConstantRange getUnsignedPopCountRange(const APInt &Lower,
2152 const APInt &Upper) {
2153 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
2154 "Unexpected wrapped set.");
2155 assert(Lower != Upper && "Unexpected empty set.");
2156 unsigned BitWidth = Lower.getBitWidth();
2157 if (Lower + 1 == Upper)
2158 return ConstantRange(APInt(BitWidth, Lower.popcount()));
2159
2160 APInt Max = Upper - 1;
2161 // Calculate longest common prefix.
2162 unsigned LCPLength = (Lower ^ Max).countl_zero();
2163 unsigned LCPPopCount = Lower.getHiBits(numBits: LCPLength).popcount();
2164 // If Lower is {LCP, 000...}, the minimum is the popcount of LCP.
2165 // Otherwise, the minimum is the popcount of LCP + 1.
2166 unsigned MinBits =
2167 LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);
2168 // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -
2169 // length of LCP).
2170 // Otherwise, the minimum is the popcount of LCP + (BitWidth -
2171 // length of LCP - 1).
2172 unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -
2173 (Max.countr_one() < BitWidth - LCPLength ? 1 : 0);
2174 return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));
2175}
2176
2177ConstantRange ConstantRange::ctpop() const {
2178 if (isEmptySet())
2179 return getEmpty();
2180
2181 unsigned BitWidth = getBitWidth();
2182 APInt Zero = APInt::getZero(numBits: BitWidth);
2183 if (isFullSet())
2184 return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth) + 1);
2185 if (!isWrappedSet())
2186 return getUnsignedPopCountRange(Lower, Upper);
2187 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
2188 // [Lower, 0).
2189 // Handle [Lower, 0) == [Lower, Max]
2190 ConstantRange CR1 = ConstantRange(APInt(BitWidth, Lower.countl_one()),
2191 APInt(BitWidth, BitWidth + 1));
2192 // Handle [0, Upper)
2193 ConstantRange CR2 = getUnsignedPopCountRange(Lower: Zero, Upper);
2194 return CR1.unionWith(CR: CR2);
2195}
2196
2197ConstantRange ConstantRange::sqrtFloor() const {
2198 if (isEmptySet())
2199 return getEmpty();
2200
2201 // sqrtFloor is monotonic, so the output range is composed by the result of
2202 // sqrtFloor of the two extremes.
2203 return getNonEmpty(Lower: getUnsignedMin().sqrtFloor(),
2204 Upper: getUnsignedMax().sqrtFloor() + 1);
2205}
2206
2207ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
2208 const ConstantRange &Other) const {
2209 if (isEmptySet() || Other.isEmptySet())
2210 return OverflowResult::MayOverflow;
2211
2212 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2213 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2214
2215 // a u+ b overflows high iff a u> ~b.
2216 if (Min.ugt(RHS: ~OtherMin))
2217 return OverflowResult::AlwaysOverflowsHigh;
2218 if (Max.ugt(RHS: ~OtherMax))
2219 return OverflowResult::MayOverflow;
2220 return OverflowResult::NeverOverflows;
2221}
2222
2223ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
2224 const ConstantRange &Other) const {
2225 if (isEmptySet() || Other.isEmptySet())
2226 return OverflowResult::MayOverflow;
2227
2228 APInt Min = getSignedMin(), Max = getSignedMax();
2229 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2230
2231 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
2232 APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
2233
2234 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
2235 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
2236 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
2237 Min.sgt(RHS: SignedMax - OtherMin))
2238 return OverflowResult::AlwaysOverflowsHigh;
2239 if (Max.isNegative() && OtherMax.isNegative() &&
2240 Max.slt(RHS: SignedMin - OtherMax))
2241 return OverflowResult::AlwaysOverflowsLow;
2242
2243 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
2244 Max.sgt(RHS: SignedMax - OtherMax))
2245 return OverflowResult::MayOverflow;
2246 if (Min.isNegative() && OtherMin.isNegative() &&
2247 Min.slt(RHS: SignedMin - OtherMin))
2248 return OverflowResult::MayOverflow;
2249
2250 return OverflowResult::NeverOverflows;
2251}
2252
2253ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
2254 const ConstantRange &Other) const {
2255 if (isEmptySet() || Other.isEmptySet())
2256 return OverflowResult::MayOverflow;
2257
2258 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2259 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2260
2261 // a u- b overflows low iff a u< b.
2262 if (Max.ult(RHS: OtherMin))
2263 return OverflowResult::AlwaysOverflowsLow;
2264 if (Min.ult(RHS: OtherMax))
2265 return OverflowResult::MayOverflow;
2266 return OverflowResult::NeverOverflows;
2267}
2268
2269ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
2270 const ConstantRange &Other) const {
2271 if (isEmptySet() || Other.isEmptySet())
2272 return OverflowResult::MayOverflow;
2273
2274 APInt Min = getSignedMin(), Max = getSignedMax();
2275 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2276
2277 APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
2278 APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
2279
2280 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
2281 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
2282 if (Min.isNonNegative() && OtherMax.isNegative() &&
2283 Min.sgt(RHS: SignedMax + OtherMax))
2284 return OverflowResult::AlwaysOverflowsHigh;
2285 if (Max.isNegative() && OtherMin.isNonNegative() &&
2286 Max.slt(RHS: SignedMin + OtherMin))
2287 return OverflowResult::AlwaysOverflowsLow;
2288
2289 if (Max.isNonNegative() && OtherMin.isNegative() &&
2290 Max.sgt(RHS: SignedMax + OtherMin))
2291 return OverflowResult::MayOverflow;
2292 if (Min.isNegative() && OtherMax.isNonNegative() &&
2293 Min.slt(RHS: SignedMin + OtherMax))
2294 return OverflowResult::MayOverflow;
2295
2296 return OverflowResult::NeverOverflows;
2297}
2298
2299ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
2300 const ConstantRange &Other) const {
2301 if (isEmptySet() || Other.isEmptySet())
2302 return OverflowResult::MayOverflow;
2303
2304 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2305 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2306 bool Overflow;
2307
2308 (void) Min.umul_ov(RHS: OtherMin, Overflow);
2309 if (Overflow)
2310 return OverflowResult::AlwaysOverflowsHigh;
2311
2312 (void) Max.umul_ov(RHS: OtherMax, Overflow);
2313 if (Overflow)
2314 return OverflowResult::MayOverflow;
2315
2316 return OverflowResult::NeverOverflows;
2317}
2318
2319void ConstantRange::print(raw_ostream &OS) const {
2320 if (isFullSet())
2321 OS << "full-set";
2322 else if (isEmptySet())
2323 OS << "empty-set";
2324 else
2325 OS << "[" << Lower << "," << Upper << ")";
2326}
2327
2328#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2329LLVM_DUMP_METHOD void ConstantRange::dump() const {
2330 print(dbgs());
2331}
2332#endif
2333
2334ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
2335 const unsigned NumRanges = Ranges.getNumOperands() / 2;
2336 assert(NumRanges >= 1 && "Must have at least one range!");
2337 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
2338
2339 auto *FirstLow = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 0));
2340 auto *FirstHigh = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 1));
2341
2342 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2343
2344 for (unsigned i = 1; i < NumRanges; ++i) {
2345 auto *Low = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 0));
2346 auto *High = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 1));
2347
2348 // Note: unionWith will potentially create a range that contains values not
2349 // contained in any of the original N ranges.
2350 CR = CR.unionWith(CR: ConstantRange(Low->getValue(), High->getValue()));
2351 }
2352
2353 return CR;
2354}
2355