Line data Source code
1 : //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // Represent a range of possible values that may occur when the program is run
11 : // for an integral value. This keeps track of a lower and upper bound for the
12 : // constant, which MAY wrap around the end of the numeric range. To do this, it
13 : // keeps track of a [lower, upper) bound, which specifies an interval just like
14 : // STL iterators. When used with boolean values, the following are important
15 : // ranges (other integral ranges use min/max values for special range values):
16 : //
17 : // [F, F) = {} = Empty set
18 : // [T, F) = {T}
19 : // [F, T) = {F}
20 : // [T, T) = {F, T} = Full set
21 : //
22 : //===----------------------------------------------------------------------===//
23 :
24 : #include "llvm/ADT/APInt.h"
25 : #include "llvm/Config/llvm-config.h"
26 : #include "llvm/IR/ConstantRange.h"
27 : #include "llvm/IR/Constants.h"
28 : #include "llvm/IR/InstrTypes.h"
29 : #include "llvm/IR/Instruction.h"
30 : #include "llvm/IR/Metadata.h"
31 : #include "llvm/IR/Operator.h"
32 : #include "llvm/Support/Compiler.h"
33 : #include "llvm/Support/Debug.h"
34 : #include "llvm/Support/ErrorHandling.h"
35 : #include "llvm/Support/raw_ostream.h"
36 : #include <algorithm>
37 : #include <cassert>
38 : #include <cstdint>
39 :
40 : using namespace llvm;
41 :
42 13645870 : ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
43 : : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44 24966974 : Upper(Lower) {}
45 :
46 7549946 : ConstantRange::ConstantRange(APInt V)
47 7549946 : : Lower(std::move(V)), Upper(Lower + 1) {}
48 :
49 14821681 : ConstantRange::ConstantRange(APInt L, APInt U)
50 : : Lower(std::move(L)), Upper(std::move(U)) {
51 : assert(Lower.getBitWidth() == Upper.getBitWidth() &&
52 : "ConstantRange with unequal bit widths");
53 : assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
54 : "Lower == Upper, but they aren't min or max value!");
55 14821681 : }
56 :
57 1634317 : ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
58 : const ConstantRange &CR) {
59 1634317 : if (CR.isEmptySet())
60 0 : return CR;
61 :
62 : uint32_t W = CR.getBitWidth();
63 1634317 : switch (Pred) {
64 0 : default:
65 0 : llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
66 655535 : case CmpInst::ICMP_EQ:
67 655535 : return CR;
68 : case CmpInst::ICMP_NE:
69 161691 : if (CR.isSingleElement())
70 318072 : return ConstantRange(CR.getUpper(), CR.getLower());
71 2655 : return ConstantRange(W);
72 218760 : case CmpInst::ICMP_ULT: {
73 218760 : APInt UMax(CR.getUnsignedMax());
74 218760 : if (UMax.isMinValue())
75 1200 : return ConstantRange(W, /* empty */ false);
76 435120 : return ConstantRange(APInt::getMinValue(W), std::move(UMax));
77 : }
78 86563 : case CmpInst::ICMP_SLT: {
79 86563 : APInt SMax(CR.getSignedMax());
80 86563 : if (SMax.isMinSignedValue())
81 1026 : return ConstantRange(W, /* empty */ false);
82 171074 : return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
83 : }
84 38485 : case CmpInst::ICMP_ULE: {
85 38485 : APInt UMax(CR.getUnsignedMax());
86 38485 : if (UMax.isMaxValue())
87 2509 : return ConstantRange(W);
88 71952 : return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
89 : }
90 34563 : case CmpInst::ICMP_SLE: {
91 34563 : APInt SMax(CR.getSignedMax());
92 34563 : if (SMax.isMaxSignedValue())
93 582 : return ConstantRange(W);
94 67962 : return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
95 : }
96 175218 : case CmpInst::ICMP_UGT: {
97 175218 : APInt UMin(CR.getUnsignedMin());
98 175218 : if (UMin.isMaxValue())
99 2472 : return ConstantRange(W, /* empty */ false);
100 518238 : return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
101 : }
102 182685 : case CmpInst::ICMP_SGT: {
103 182685 : APInt SMin(CR.getSignedMin());
104 182685 : if (SMin.isMaxSignedValue())
105 1301 : return ConstantRange(W, /* empty */ false);
106 544152 : return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
107 : }
108 32158 : case CmpInst::ICMP_UGE: {
109 32158 : APInt UMin(CR.getUnsignedMin());
110 32158 : if (UMin.isMinValue())
111 4395 : return ConstantRange(W);
112 55526 : return ConstantRange(std::move(UMin), APInt::getNullValue(W));
113 : }
114 48659 : case CmpInst::ICMP_SGE: {
115 48659 : APInt SMin(CR.getSignedMin());
116 48659 : if (SMin.isMinSignedValue())
117 2920 : return ConstantRange(W);
118 91478 : return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
119 : }
120 : }
121 : }
122 :
123 258493 : ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
124 : const ConstantRange &CR) {
125 : // Follows from De-Morgan's laws:
126 : //
127 : // ~(~A union ~B) == A intersect B.
128 : //
129 516986 : return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
130 258493 : .inverse();
131 : }
132 :
133 968850 : ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
134 : const APInt &C) {
135 : // Computes the exact range that is equal to both the constant ranges returned
136 : // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
137 : // when RHS is a singleton such as an APInt and so the assert is valid.
138 : // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
139 : // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
140 : //
141 : assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
142 968850 : return makeAllowedICmpRegion(Pred, C);
143 : }
144 :
145 142786 : bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
146 : APInt &RHS) const {
147 : bool Success = false;
148 :
149 142786 : if (isFullSet() || isEmptySet()) {
150 3 : Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
151 2 : RHS = APInt(getBitWidth(), 0);
152 : Success = true;
153 142784 : } else if (auto *OnlyElt = getSingleElement()) {
154 864 : Pred = CmpInst::ICMP_EQ;
155 864 : RHS = *OnlyElt;
156 : Success = true;
157 141920 : } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
158 26583 : Pred = CmpInst::ICMP_NE;
159 26583 : RHS = *OnlyMissingElt;
160 : Success = true;
161 203668 : } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
162 73415 : Pred =
163 73415 : getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
164 73415 : RHS = getUpper();
165 : Success = true;
166 54917 : } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
167 41917 : Pred =
168 41917 : getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
169 41917 : RHS = getLower();
170 : Success = true;
171 : }
172 :
173 : assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
174 : "Bad result!");
175 :
176 142786 : return Success;
177 : }
178 :
179 : ConstantRange
180 5670333 : ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
181 : const ConstantRange &Other,
182 : unsigned NoWrapKind) {
183 : using OBO = OverflowingBinaryOperator;
184 :
185 : // Computes the intersection of CR0 and CR1. It is different from
186 : // intersectWith in that the ConstantRange returned will only contain elements
187 : // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
188 : // not, of both X and Y).
189 : auto SubsetIntersect =
190 : [](const ConstantRange &CR0, const ConstantRange &CR1) {
191 : return CR0.inverse().unionWith(CR1.inverse()).inverse();
192 : };
193 :
194 : assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
195 :
196 : assert((NoWrapKind == OBO::NoSignedWrap ||
197 : NoWrapKind == OBO::NoUnsignedWrap ||
198 : NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199 : "NoWrapKind invalid!");
200 :
201 : unsigned BitWidth = Other.getBitWidth();
202 11340666 : ConstantRange Result(BitWidth);
203 :
204 5670333 : switch (BinOp) {
205 0 : default:
206 : // Conservative answer: empty set
207 0 : return ConstantRange(BitWidth, false);
208 :
209 3450761 : case Instruction::Add:
210 3450761 : if (auto *C = Other.getSingleElement())
211 3449531 : if (C->isNullValue())
212 : // Full set: nothing signed / unsigned wraps when added to 0.
213 1865440 : return ConstantRange(BitWidth);
214 1585321 : if (NoWrapKind & OBO::NoUnsignedWrap)
215 : Result =
216 1849400 : SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
217 2774100 : -Other.getUnsignedMax()));
218 1585321 : if (NoWrapKind & OBO::NoSignedWrap) {
219 660632 : const APInt &SignedMin = Other.getSignedMin();
220 660632 : const APInt &SignedMax = Other.getSignedMax();
221 660632 : if (SignedMax.isStrictlyPositive())
222 811556 : Result = SubsetIntersect(
223 : Result,
224 811556 : ConstantRange(APInt::getSignedMinValue(BitWidth),
225 1217334 : APInt::getSignedMinValue(BitWidth) - SignedMax));
226 702622 : if (SignedMin.isNegative())
227 510670 : Result = SubsetIntersect(
228 : Result,
229 766005 : ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
230 766005 : APInt::getSignedMinValue(BitWidth)));
231 : }
232 : return Result;
233 :
234 108 : case Instruction::Sub:
235 108 : if (auto *C = Other.getSingleElement())
236 31 : if (C->isNullValue())
237 : // Full set: nothing signed / unsigned wraps when subtracting 0.
238 6 : return ConstantRange(BitWidth);
239 102 : if (NoWrapKind & OBO::NoUnsignedWrap)
240 : Result =
241 172 : SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
242 258 : APInt::getMinValue(BitWidth)));
243 102 : if (NoWrapKind & OBO::NoSignedWrap) {
244 27 : const APInt &SignedMin = Other.getSignedMin();
245 27 : const APInt &SignedMax = Other.getSignedMax();
246 27 : if (SignedMax.isStrictlyPositive())
247 34 : Result = SubsetIntersect(
248 : Result,
249 51 : ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
250 51 : APInt::getSignedMinValue(BitWidth)));
251 27 : if (SignedMin.isNegative())
252 30 : Result = SubsetIntersect(
253 : Result,
254 30 : ConstantRange(APInt::getSignedMinValue(BitWidth),
255 45 : APInt::getSignedMinValue(BitWidth) + SignedMin));
256 : }
257 : return Result;
258 2219464 : case Instruction::Mul: {
259 2219464 : if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) {
260 : return SubsetIntersect(
261 512 : makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap),
262 768 : makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap));
263 : }
264 :
265 : // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
266 2219208 : const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
267 : const auto makeSingleValueRegion = [Unsigned,
268 : BitWidth](APInt V) -> ConstantRange {
269 : // Handle special case for 0, -1 and 1. See the last for reason why we
270 : // specialize -1 and 1.
271 : if (V == 0 || V.isOneValue())
272 : return ConstantRange(BitWidth, true);
273 :
274 : APInt MinValue, MaxValue;
275 : if (Unsigned) {
276 : MinValue = APInt::getMinValue(BitWidth);
277 : MaxValue = APInt::getMaxValue(BitWidth);
278 : } else {
279 : MinValue = APInt::getSignedMinValue(BitWidth);
280 : MaxValue = APInt::getSignedMaxValue(BitWidth);
281 : }
282 : // e.g. Returning [-127, 127], represented as [-127, -128).
283 : if (!Unsigned && V.isAllOnesValue())
284 : return ConstantRange(-MaxValue, MinValue);
285 :
286 : APInt Lower, Upper;
287 : if (!Unsigned && V.isNegative()) {
288 : Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
289 : Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
290 : } else if (Unsigned) {
291 : Lower = APIntOps::RoundingUDiv(MinValue, V, APInt::Rounding::UP);
292 : Upper = APIntOps::RoundingUDiv(MaxValue, V, APInt::Rounding::DOWN);
293 : } else {
294 : Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
295 : Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
296 : }
297 : if (Unsigned) {
298 : Lower = Lower.zextOrSelf(BitWidth);
299 : Upper = Upper.zextOrSelf(BitWidth);
300 : } else {
301 : Lower = Lower.sextOrSelf(BitWidth);
302 : Upper = Upper.sextOrSelf(BitWidth);
303 : }
304 : // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
305 : // Upper + 1 is guanranteed not to overflow, because |divisor| > 1. 0, -1,
306 : // and 1 are already handled as special cases.
307 : return ConstantRange(Lower, Upper + 1);
308 2219208 : };
309 :
310 2219208 : if (Unsigned)
311 2356064 : return makeSingleValueRegion(Other.getUnsignedMax());
312 :
313 2082352 : return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
314 3157019 : makeSingleValueRegion(Other.getSignedMax()));
315 : }
316 : }
317 : }
318 :
319 43174294 : bool ConstantRange::isFullSet() const {
320 97113190 : return Lower == Upper && Lower.isMaxValue();
321 : }
322 :
323 27164783 : bool ConstantRange::isEmptySet() const {
324 59601845 : return Lower == Upper && Lower.isMinValue();
325 : }
326 :
327 16775318 : bool ConstantRange::isWrappedSet() const {
328 33550636 : return Lower.ugt(Upper);
329 : }
330 :
331 5218 : bool ConstantRange::isSignWrappedSet() const {
332 8296 : return contains(APInt::getSignedMaxValue(getBitWidth())) &&
333 8319 : contains(APInt::getSignedMinValue(getBitWidth()));
334 : }
335 :
336 6 : APInt ConstantRange::getSetSize() const {
337 6 : if (isFullSet())
338 1 : return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
339 :
340 : // This is also correct for wrapped sets.
341 15 : return (Upper - Lower).zext(getBitWidth()+1);
342 : }
343 :
344 : bool
345 321271 : ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
346 : assert(getBitWidth() == Other.getBitWidth());
347 321271 : if (isFullSet())
348 : return false;
349 212559 : if (Other.isFullSet())
350 : return true;
351 643047 : return (Upper - Lower).ult(Other.Upper - Other.Lower);
352 : }
353 :
354 : bool
355 332691 : ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
356 : assert(MaxSize && "MaxSize can't be 0.");
357 : // If this a full set, we need special handling to avoid needing an extra bit
358 : // to represent the size.
359 332691 : if (isFullSet())
360 18 : return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
361 :
362 665485 : return (Upper - Lower).ugt(MaxSize);
363 : }
364 :
365 3757943 : APInt ConstantRange::getUnsignedMax() const {
366 3757943 : if (isFullSet() || isWrappedSet())
367 : return APInt::getMaxValue(getBitWidth());
368 2686522 : return getUpper() - 1;
369 : }
370 :
371 765881 : APInt ConstantRange::getUnsignedMin() const {
372 858710 : if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
373 156181 : return APInt::getMinValue(getBitWidth());
374 : return getLower();
375 : }
376 :
377 2435958 : APInt ConstantRange::getSignedMax() const {
378 2435958 : if (isFullSet() || Lower.sgt(Upper))
379 165157 : return APInt::getSignedMaxValue(getBitWidth());
380 2270801 : return getUpper() - 1;
381 : }
382 :
383 4859332 : APInt ConstantRange::getSignedMin() const {
384 4859332 : if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
385 409812 : return APInt::getSignedMinValue(getBitWidth());
386 : return getLower();
387 : }
388 :
389 632668 : bool ConstantRange::contains(const APInt &V) const {
390 1265336 : if (Lower == Upper)
391 2991 : return isFullSet();
392 :
393 629677 : if (!isWrappedSet())
394 504649 : return Lower.ule(V) && V.ult(Upper);
395 125028 : return Lower.ule(V) || V.ult(Upper);
396 : }
397 :
398 6295919 : bool ConstantRange::contains(const ConstantRange &Other) const {
399 6295919 : if (isFullSet() || Other.isEmptySet()) return true;
400 3994351 : if (isEmptySet() || Other.isFullSet()) return false;
401 :
402 2905201 : if (!isWrappedSet()) {
403 1583221 : if (Other.isWrappedSet())
404 : return false;
405 :
406 2437848 : return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
407 : }
408 :
409 1321980 : if (!Other.isWrappedSet())
410 1256584 : return Other.getUpper().ule(Upper) ||
411 409209 : Lower.ule(Other.getLower());
412 :
413 1387376 : return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
414 : }
415 :
416 34863 : ConstantRange ConstantRange::subtract(const APInt &Val) const {
417 : assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
418 : // If the set is empty or full, don't modify the endpoints.
419 69726 : if (Lower == Upper)
420 355 : return *this;
421 69016 : return ConstantRange(Lower - Val, Upper - Val);
422 : }
423 :
424 27279 : ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
425 27279 : return intersectWith(CR.inverse());
426 : }
427 :
428 999186 : ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
429 : assert(getBitWidth() == CR.getBitWidth() &&
430 : "ConstantRange types don't agree!");
431 :
432 : // Handle common cases.
433 999186 : if ( isEmptySet() || CR.isFullSet()) return *this;
434 673130 : if (CR.isEmptySet() || isFullSet()) return CR;
435 :
436 402576 : if (!isWrappedSet() && CR.isWrappedSet())
437 35622 : return CR.intersectWith(*this);
438 :
439 366954 : if (!isWrappedSet() && !CR.isWrappedSet()) {
440 419744 : if (Lower.ult(CR.Lower)) {
441 20842 : if (Upper.ule(CR.Lower))
442 24 : return ConstantRange(getBitWidth(), false);
443 :
444 20794 : if (Upper.ult(CR.Upper))
445 2264 : return ConstantRange(CR.Lower, Upper);
446 :
447 9265 : return CR;
448 : }
449 398902 : if (Upper.ult(CR.Upper))
450 2376 : return *this;
451 :
452 197075 : if (Lower.ult(CR.Upper))
453 394000 : return ConstantRange(Lower, CR.Upper);
454 :
455 75 : return ConstantRange(getBitWidth(), false);
456 : }
457 :
458 157082 : if (isWrappedSet() && !CR.isWrappedSet()) {
459 191806 : if (CR.Lower.ult(Upper)) {
460 112150 : if (CR.Upper.ult(Upper))
461 19225 : return CR;
462 :
463 73700 : if (CR.Upper.ule(Lower))
464 39712 : return ConstantRange(CR.Lower, Upper);
465 :
466 16994 : if (isSizeStrictlySmallerThan(CR))
467 8436 : return *this;
468 8558 : return CR;
469 : }
470 79656 : if (CR.Lower.ult(Lower)) {
471 70424 : if (CR.Upper.ule(Lower))
472 101 : return ConstantRange(getBitWidth(), false);
473 :
474 70222 : return ConstantRange(Lower, CR.Upper);
475 : }
476 4616 : return CR;
477 : }
478 :
479 122358 : if (CR.Upper.ult(Upper)) {
480 46734 : if (CR.Lower.ult(Upper)) {
481 10811 : if (isSizeStrictlySmallerThan(CR))
482 67 : return *this;
483 10744 : return CR;
484 : }
485 :
486 25112 : if (CR.Lower.ult(Lower))
487 6914 : return ConstantRange(Lower, CR.Upper);
488 :
489 9099 : return CR;
490 : }
491 75624 : if (CR.Upper.ule(Lower)) {
492 47552 : if (CR.Lower.ult(Lower))
493 530 : return *this;
494 :
495 46492 : return ConstantRange(CR.Lower, Upper);
496 : }
497 14036 : if (isSizeStrictlySmallerThan(CR))
498 264 : return *this;
499 13772 : return CR;
500 : }
501 :
502 3023792 : ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
503 : assert(getBitWidth() == CR.getBitWidth() &&
504 : "ConstantRange types don't agree!");
505 :
506 3023792 : if ( isFullSet() || CR.isEmptySet()) return *this;
507 2717943 : if (CR.isFullSet() || isEmptySet()) return CR;
508 :
509 1094447 : if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
510 :
511 1030726 : if (!isWrappedSet() && !CR.isWrappedSet()) {
512 1856732 : if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
513 : // If the two ranges are disjoint, find the smaller gap and bridge it.
514 3525 : APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
515 1175 : if (d1.ult(d2))
516 940 : return ConstantRange(Lower, CR.Upper);
517 1410 : return ConstantRange(CR.Lower, Upper);
518 : }
519 :
520 927191 : APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
521 1885324 : APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
522 :
523 988250 : if (L.isNullValue() && U.isNullValue())
524 0 : return ConstantRange(getBitWidth());
525 :
526 1854382 : return ConstantRange(std::move(L), std::move(U));
527 : }
528 :
529 102360 : if (!CR.isWrappedSet()) {
530 : // ------U L----- and ------U L----- : this
531 : // L--U L--U : CR
532 133392 : if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
533 2151 : return *this;
534 :
535 : // ------U L----- : this
536 : // L---------U : CR
537 64545 : if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
538 43158 : return ConstantRange(getBitWidth());
539 :
540 : // ----U L---- : this
541 : // L---U : CR
542 : // <d1> <d2>
543 21387 : if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
544 42152 : APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
545 21076 : if (d1.ult(d2))
546 728 : return ConstantRange(Lower, CR.Upper);
547 41424 : return ConstantRange(CR.Lower, Upper);
548 : }
549 :
550 : // ----U L----- : this
551 : // L----U : CR
552 311 : if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
553 292 : return ConstantRange(CR.Lower, Upper);
554 :
555 : // ------U L---- : this
556 : // L-----U : CR
557 : assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
558 : "ConstantRange::unionWith missed a case with one range wrapped");
559 330 : return ConstantRange(Lower, CR.Upper);
560 : }
561 :
562 : // ------U L---- and ------U L---- : this
563 : // -U L----------- and ------------U L : CR
564 71328 : if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
565 100 : return ConstantRange(getBitWidth());
566 :
567 35564 : APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
568 35564 : APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
569 :
570 71128 : return ConstantRange(std::move(L), std::move(U));
571 : }
572 :
573 3777 : ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
574 : uint32_t ResultBitWidth) const {
575 3777 : switch (CastOp) {
576 0 : default:
577 0 : llvm_unreachable("unsupported cast type");
578 684 : case Instruction::Trunc:
579 684 : return truncate(ResultBitWidth);
580 268 : case Instruction::SExt:
581 268 : return signExtend(ResultBitWidth);
582 2708 : case Instruction::ZExt:
583 2708 : return zeroExtend(ResultBitWidth);
584 19 : case Instruction::BitCast:
585 19 : return *this;
586 : case Instruction::FPToUI:
587 : case Instruction::FPToSI:
588 50 : if (getBitWidth() == ResultBitWidth)
589 50 : return *this;
590 : else
591 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
592 : case Instruction::UIToFP: {
593 : // TODO: use input range if available
594 : auto BW = getBitWidth();
595 82 : APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
596 82 : APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
597 82 : return ConstantRange(std::move(Min), std::move(Max));
598 : }
599 : case Instruction::SIToFP: {
600 : // TODO: use input range if available
601 : auto BW = getBitWidth();
602 7 : APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
603 14 : APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
604 14 : return ConstantRange(std::move(SMin), std::move(SMax));
605 : }
606 : case Instruction::FPTrunc:
607 : case Instruction::FPExt:
608 : case Instruction::IntToPtr:
609 : case Instruction::PtrToInt:
610 : case Instruction::AddrSpaceCast:
611 : // Conservatively return full set.
612 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
613 : };
614 : }
615 :
616 45529 : ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
617 45529 : if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
618 :
619 : unsigned SrcTySize = getBitWidth();
620 : assert(SrcTySize < DstTySize && "Not a value extension");
621 45528 : if (isFullSet() || isWrappedSet()) {
622 : // Change into [0, 1 << src bit width)
623 : APInt LowerExt(DstTySize, 0);
624 71376 : if (!Upper) // special case: [X, 0) -- not really wrapping around
625 64 : LowerExt = Lower.zext(DstTySize);
626 : return ConstantRange(std::move(LowerExt),
627 71376 : APInt::getOneBitSet(DstTySize, SrcTySize));
628 : }
629 :
630 19680 : return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
631 : }
632 :
633 22260 : ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
634 22260 : if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
635 :
636 : unsigned SrcTySize = getBitWidth();
637 : assert(SrcTySize < DstTySize && "Not a value extension");
638 :
639 : // special case: [X, INT_MIN) -- not really wrapping around
640 22259 : if (Upper.isMinSignedValue())
641 224 : return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
642 :
643 22147 : if (isFullSet() || isSignWrappedSet()) {
644 40340 : return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
645 60510 : APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
646 : }
647 :
648 3954 : return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
649 : }
650 :
651 256556 : ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
652 : assert(getBitWidth() > DstTySize && "Not a value truncation");
653 256556 : if (isEmptySet())
654 1 : return ConstantRange(DstTySize, /*isFullSet=*/false);
655 256555 : if (isFullSet())
656 5603 : return ConstantRange(DstTySize, /*isFullSet=*/true);
657 :
658 501904 : APInt LowerDiv(Lower), UpperDiv(Upper);
659 501904 : ConstantRange Union(DstTySize, /*isFullSet=*/false);
660 :
661 : // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
662 : // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
663 : // then we do the union with [MaxValue, Upper)
664 250952 : if (isWrappedSet()) {
665 : // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
666 : // truncated range.
667 172540 : if (Upper.getActiveBits() > DstTySize ||
668 : Upper.countTrailingOnes() == DstTySize)
669 43514 : return ConstantRange(DstTySize, /*isFullSet=*/true);
670 :
671 127394 : Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
672 63697 : UpperDiv.setAllBits();
673 :
674 : // Union covers the MaxValue case, so return if the remaining range is just
675 : // MaxValue(DstTy).
676 63697 : if (LowerDiv == UpperDiv)
677 : return Union;
678 : }
679 :
680 : // Chop off the most significant bits that are past the destination bitwidth.
681 205189 : if (LowerDiv.getActiveBits() > DstTySize) {
682 : // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
683 62311 : APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
684 62311 : LowerDiv -= Adjust;
685 62311 : UpperDiv -= Adjust;
686 : }
687 :
688 : unsigned UpperDivWidth = UpperDiv.getActiveBits();
689 205189 : if (UpperDivWidth <= DstTySize)
690 182038 : return ConstantRange(LowerDiv.trunc(DstTySize),
691 273057 : UpperDiv.trunc(DstTySize)).unionWith(Union);
692 :
693 : // The truncated value wraps around. Check if we can do better than fullset.
694 114170 : if (UpperDivWidth == DstTySize + 1) {
695 : // Clear the MSB so that UpperDiv wraps around.
696 : UpperDiv.clearBit(DstTySize);
697 6803 : if (UpperDiv.ult(LowerDiv))
698 34 : return ConstantRange(LowerDiv.trunc(DstTySize),
699 51 : UpperDiv.trunc(DstTySize)).unionWith(Union);
700 : }
701 :
702 114153 : return ConstantRange(DstTySize, /*isFullSet=*/true);
703 : }
704 :
705 2527 : ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
706 : unsigned SrcTySize = getBitWidth();
707 2527 : if (SrcTySize > DstTySize)
708 38 : return truncate(DstTySize);
709 2489 : if (SrcTySize < DstTySize)
710 472 : return zeroExtend(DstTySize);
711 2017 : return *this;
712 : }
713 :
714 426 : ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
715 : unsigned SrcTySize = getBitWidth();
716 426 : if (SrcTySize > DstTySize)
717 2 : return truncate(DstTySize);
718 424 : if (SrcTySize < DstTySize)
719 70 : return signExtend(DstTySize);
720 354 : return *this;
721 : }
722 :
723 21976 : ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
724 : const ConstantRange &Other) const {
725 : assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
726 :
727 21976 : switch (BinOp) {
728 16227 : case Instruction::Add:
729 16227 : return add(Other);
730 2 : case Instruction::Sub:
731 2 : return sub(Other);
732 395 : case Instruction::Mul:
733 395 : return multiply(Other);
734 113 : case Instruction::UDiv:
735 113 : return udiv(Other);
736 716 : case Instruction::Shl:
737 716 : return shl(Other);
738 1930 : case Instruction::LShr:
739 1930 : return lshr(Other);
740 1000 : case Instruction::AShr:
741 1000 : return ashr(Other);
742 1292 : case Instruction::And:
743 1292 : return binaryAnd(Other);
744 272 : case Instruction::Or:
745 272 : return binaryOr(Other);
746 : // Note: floating point operations applied to abstract ranges are just
747 : // ideal integer operations with a lossy representation
748 17 : case Instruction::FAdd:
749 17 : return add(Other);
750 4 : case Instruction::FSub:
751 4 : return sub(Other);
752 8 : case Instruction::FMul:
753 8 : return multiply(Other);
754 : default:
755 : // Conservatively return full set.
756 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
757 : }
758 : }
759 :
760 : ConstantRange
761 789020 : ConstantRange::add(const ConstantRange &Other) const {
762 789020 : if (isEmptySet() || Other.isEmptySet())
763 8 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
764 789012 : if (isFullSet() || Other.isFullSet())
765 700962 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
766 :
767 88050 : APInt NewLower = getLower() + Other.getLower();
768 88050 : APInt NewUpper = getUpper() + Other.getUpper() - 1;
769 88050 : if (NewLower == NewUpper)
770 51 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
771 :
772 263997 : ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
773 166654 : if (X.isSizeStrictlySmallerThan(*this) ||
774 78655 : X.isSizeStrictlySmallerThan(Other))
775 : // We've wrapped, therefore, full set.
776 9344 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
777 : return X;
778 : }
779 :
780 28 : ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
781 : // Calculate the subset of this range such that "X + Other" is
782 : // guaranteed not to wrap (overflow) for all X in this subset.
783 : // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
784 : // passing a single element range.
785 : auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
786 56 : ConstantRange(Other),
787 56 : OverflowingBinaryOperator::NoSignedWrap);
788 28 : auto NSWConstrainedRange = intersectWith(NSWRange);
789 :
790 28 : return NSWConstrainedRange.add(ConstantRange(Other));
791 : }
792 :
793 : ConstantRange
794 99 : ConstantRange::sub(const ConstantRange &Other) const {
795 99 : if (isEmptySet() || Other.isEmptySet())
796 6 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
797 93 : if (isFullSet() || Other.isFullSet())
798 18 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
799 :
800 75 : APInt NewLower = getLower() - Other.getUpper() + 1;
801 75 : APInt NewUpper = getUpper() - Other.getLower();
802 75 : if (NewLower == NewUpper)
803 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
804 :
805 225 : ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
806 150 : if (X.isSizeStrictlySmallerThan(*this) ||
807 75 : X.isSizeStrictlySmallerThan(Other))
808 : // We've wrapped, therefore, full set.
809 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
810 : return X;
811 : }
812 :
813 : ConstantRange
814 132890 : ConstantRange::multiply(const ConstantRange &Other) const {
815 : // TODO: If either operand is a single element and the multiply is known to
816 : // be non-wrapping, round the result min and max value to the appropriate
817 : // multiple of that element. If wrapping is possible, at least adjust the
818 : // range according to the greatest power-of-two factor of the single element.
819 :
820 132890 : if (isEmptySet() || Other.isEmptySet())
821 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
822 :
823 : // Multiplication is signedness-independent. However different ranges can be
824 : // obtained depending on how the input ranges are treated. These different
825 : // ranges are all conservatively correct, but one might be better than the
826 : // other. We calculate two ranges; one treating the inputs as unsigned
827 : // and the other signed, then return the smallest of these ranges.
828 :
829 : // Unsigned range first.
830 132885 : APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
831 132885 : APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
832 132885 : APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
833 132885 : APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
834 :
835 265770 : ConstantRange Result_zext = ConstantRange(this_min * Other_min,
836 531540 : this_max * Other_max + 1);
837 265770 : ConstantRange UR = Result_zext.truncate(getBitWidth());
838 :
839 : // If the unsigned range doesn't wrap, and isn't negative then it's a range
840 : // from one positive number to another which is as good as we can generate.
841 : // In this case, skip the extra work of generating signed ranges which aren't
842 : // going to be better than this range.
843 265759 : if (!UR.isWrappedSet() &&
844 112673 : (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
845 : return UR;
846 :
847 : // Now the signed range. Because we could be dealing with negative numbers
848 : // here, the lower bound is the smallest of the cartesian product of the
849 : // lower and upper ranges; for example:
850 : // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
851 : // Similarly for the upper bound, swapping min for max.
852 :
853 225252 : this_min = getSignedMin().sext(getBitWidth() * 2);
854 225252 : this_max = getSignedMax().sext(getBitWidth() * 2);
855 225252 : Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
856 225252 : Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
857 :
858 112626 : auto L = {this_min * Other_min, this_min * Other_max,
859 675756 : this_max * Other_min, this_max * Other_max};
860 : auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
861 450504 : ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
862 225252 : ConstantRange SR = Result_sext.truncate(getBitWidth());
863 :
864 225176 : return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
865 : }
866 :
867 : ConstantRange
868 5481 : ConstantRange::smax(const ConstantRange &Other) const {
869 : // X smax Y is: range(smax(X_smin, Y_smin),
870 : // smax(X_smax, Y_smax))
871 5481 : if (isEmptySet() || Other.isEmptySet())
872 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
873 10952 : APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
874 10952 : APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
875 5476 : if (NewU == NewL)
876 621 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
877 9710 : return ConstantRange(std::move(NewL), std::move(NewU));
878 : }
879 :
880 : ConstantRange
881 1986 : ConstantRange::umax(const ConstantRange &Other) const {
882 : // X umax Y is: range(umax(X_umin, Y_umin),
883 : // umax(X_umax, Y_umax))
884 1986 : if (isEmptySet() || Other.isEmptySet())
885 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
886 3962 : APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
887 3962 : APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
888 1981 : if (NewU == NewL)
889 739 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
890 2484 : return ConstantRange(std::move(NewL), std::move(NewU));
891 : }
892 :
893 : ConstantRange
894 17 : ConstantRange::smin(const ConstantRange &Other) const {
895 : // X smin Y is: range(smin(X_smin, Y_smin),
896 : // smin(X_smax, Y_smax))
897 17 : if (isEmptySet() || Other.isEmptySet())
898 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
899 24 : APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
900 24 : APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
901 12 : if (NewU == NewL)
902 3 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
903 18 : return ConstantRange(std::move(NewL), std::move(NewU));
904 : }
905 :
906 : ConstantRange
907 103 : ConstantRange::umin(const ConstantRange &Other) const {
908 : // X umin Y is: range(umin(X_umin, Y_umin),
909 : // umin(X_umax, Y_umax))
910 103 : if (isEmptySet() || Other.isEmptySet())
911 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
912 196 : APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
913 196 : APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
914 98 : if (NewU == NewL)
915 3 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
916 190 : return ConstantRange(std::move(NewL), std::move(NewU));
917 : }
918 :
919 : ConstantRange
920 19182 : ConstantRange::udiv(const ConstantRange &RHS) const {
921 57536 : if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
922 7 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
923 19175 : if (RHS.isFullSet())
924 4467 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
925 :
926 29416 : APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
927 :
928 14708 : APInt RHS_umin = RHS.getUnsignedMin();
929 14708 : if (RHS_umin.isNullValue()) {
930 : // We want the lowest value in RHS excluding zero. Usually that would be 1
931 : // except for a range in the form of [X, 1) in which case it would be X.
932 1157 : if (RHS.getUpper() == 1)
933 333 : RHS_umin = RHS.getLower();
934 : else
935 824 : RHS_umin = 1;
936 : }
937 :
938 30431 : APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
939 :
940 : // If the LHS is Full and the RHS is a wrapped interval containing 1 then
941 : // this could occur.
942 14708 : if (Lower == Upper)
943 584 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
944 :
945 28248 : return ConstantRange(std::move(Lower), std::move(Upper));
946 : }
947 :
948 : ConstantRange
949 1292 : ConstantRange::binaryAnd(const ConstantRange &Other) const {
950 1292 : if (isEmptySet() || Other.isEmptySet())
951 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
952 :
953 : // TODO: replace this with something less conservative
954 :
955 2584 : APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
956 1292 : if (umin.isAllOnesValue())
957 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
958 2584 : return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
959 : }
960 :
961 : ConstantRange
962 272 : ConstantRange::binaryOr(const ConstantRange &Other) const {
963 272 : if (isEmptySet() || Other.isEmptySet())
964 0 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
965 :
966 : // TODO: replace this with something less conservative
967 :
968 544 : APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
969 272 : if (umax.isNullValue())
970 3 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
971 538 : return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
972 : }
973 :
974 : ConstantRange
975 731 : ConstantRange::shl(const ConstantRange &Other) const {
976 731 : if (isEmptySet() || Other.isEmptySet())
977 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
978 :
979 726 : APInt max = getUnsignedMax();
980 726 : APInt Other_umax = Other.getUnsignedMax();
981 :
982 : // there's overflow!
983 1452 : if (Other_umax.uge(max.countLeadingZeros()))
984 411 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
985 :
986 : // FIXME: implement the other tricky cases
987 :
988 315 : APInt min = getUnsignedMin();
989 315 : min <<= Other.getUnsignedMin();
990 315 : max <<= Other_umax;
991 :
992 630 : return ConstantRange(std::move(min), std::move(max) + 1);
993 : }
994 :
995 : ConstantRange
996 1945 : ConstantRange::lshr(const ConstantRange &Other) const {
997 1945 : if (isEmptySet() || Other.isEmptySet())
998 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
999 :
1000 3936 : APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1001 3936 : APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1002 1940 : if (min == max)
1003 3 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1004 :
1005 3874 : return ConstantRange(std::move(min), std::move(max));
1006 : }
1007 :
1008 : ConstantRange
1009 1017 : ConstantRange::ashr(const ConstantRange &Other) const {
1010 1017 : if (isEmptySet() || Other.isEmptySet())
1011 5 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1012 :
1013 : // May straddle zero, so handle both positive and negative cases.
1014 : // 'PosMax' is the upper bound of the result of the ashr
1015 : // operation, when Upper of the LHS of ashr is a non-negative.
1016 : // number. Since ashr of a non-negative number will result in a
1017 : // smaller number, the Upper value of LHS is shifted right with
1018 : // the minimum value of 'Other' instead of the maximum value.
1019 2024 : APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1020 :
1021 : // 'PosMin' is the lower bound of the result of the ashr
1022 : // operation, when Lower of the LHS is a non-negative number.
1023 : // Since ashr of a non-negative number will result in a smaller
1024 : // number, the Lower value of LHS is shifted right with the
1025 : // maximum value of 'Other'.
1026 2024 : APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1027 :
1028 : // 'NegMax' is the upper bound of the result of the ashr
1029 : // operation, when Upper of the LHS of ashr is a negative number.
1030 : // Since 'ashr' of a negative number will result in a bigger
1031 : // number, the Upper value of LHS is shifted right with the
1032 : // maximum value of 'Other'.
1033 2024 : APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1034 :
1035 : // 'NegMin' is the lower bound of the result of the ashr
1036 : // operation, when Lower of the LHS of ashr is a negative number.
1037 : // Since 'ashr' of a negative number will result in a bigger
1038 : // number, the Lower value of LHS is shifted right with the
1039 : // minimum value of 'Other'.
1040 2024 : APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1041 :
1042 : APInt max, min;
1043 2024 : if (getSignedMin().isNonNegative()) {
1044 : // Upper and Lower of LHS are non-negative.
1045 33 : min = PosMin;
1046 33 : max = PosMax;
1047 1958 : } else if (getSignedMax().isNegative()) {
1048 : // Upper and Lower of LHS are negative.
1049 1 : min = NegMin;
1050 1 : max = NegMax;
1051 : } else {
1052 : // Upper is non-negative and Lower is negative.
1053 978 : min = NegMin;
1054 978 : max = PosMax;
1055 : }
1056 1012 : if (min == max)
1057 3 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1058 :
1059 2018 : return ConstantRange(std::move(min), std::move(max));
1060 : }
1061 :
1062 8713306 : ConstantRange ConstantRange::inverse() const {
1063 8713306 : if (isFullSet())
1064 2030922 : return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1065 6682384 : if (isEmptySet())
1066 219011 : return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1067 25853492 : return ConstantRange(Upper, Lower);
1068 : }
1069 :
1070 4800 : void ConstantRange::print(raw_ostream &OS) const {
1071 4800 : if (isFullSet())
1072 2288 : OS << "full-set";
1073 2512 : else if (isEmptySet())
1074 2 : OS << "empty-set";
1075 : else
1076 2510 : OS << "[" << Lower << "," << Upper << ")";
1077 4800 : }
1078 :
1079 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1080 : LLVM_DUMP_METHOD void ConstantRange::dump() const {
1081 : print(dbgs());
1082 : }
1083 : #endif
1084 :
1085 70933 : ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1086 70933 : const unsigned NumRanges = Ranges.getNumOperands() / 2;
1087 : assert(NumRanges >= 1 && "Must have at least one range!");
1088 : assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1089 :
1090 : auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1091 : auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1092 :
1093 141866 : ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1094 :
1095 70941 : for (unsigned i = 1; i < NumRanges; ++i) {
1096 8 : auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1097 8 : auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1098 :
1099 : // Note: unionWith will potentially create a range that contains values not
1100 : // contained in any of the original N ranges.
1101 8 : CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1102 : }
1103 :
1104 70933 : return CR;
1105 : }
|
