/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/IR/ConstantRange.cpp
Line | Count | Source (jump to first uncovered line) |
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/IR/ConstantRange.h" |
26 | | #include "llvm/IR/Constants.h" |
27 | | #include "llvm/IR/InstrTypes.h" |
28 | | #include "llvm/IR/Instruction.h" |
29 | | #include "llvm/IR/Metadata.h" |
30 | | #include "llvm/IR/Operator.h" |
31 | | #include "llvm/Support/Compiler.h" |
32 | | #include "llvm/Support/Debug.h" |
33 | | #include "llvm/Support/ErrorHandling.h" |
34 | | #include "llvm/Support/raw_ostream.h" |
35 | | #include <algorithm> |
36 | | #include <cassert> |
37 | | #include <cstdint> |
38 | | |
39 | | using namespace llvm; |
40 | | |
41 | | ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) |
42 | | : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)), |
43 | 536M | Upper(Lower) {} |
44 | | |
45 | | ConstantRange::ConstantRange(APInt V) |
46 | 143M | : Lower(std::move(V)), Upper(Lower + 1) {} |
47 | | |
48 | | ConstantRange::ConstantRange(APInt L, APInt U) |
49 | 269M | : Lower(std::move(L)), Upper(std::move(U)) { |
50 | 269M | assert(Lower.getBitWidth() == Upper.getBitWidth() && |
51 | 269M | "ConstantRange with unequal bit widths"); |
52 | 269M | assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && |
53 | 269M | "Lower == Upper, but they aren't min or max value!"); |
54 | 269M | } |
55 | | |
56 | | ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, |
57 | 57.5M | const ConstantRange &CR) { |
58 | 57.5M | if (CR.isEmptySet()) |
59 | 0 | return CR; |
60 | 57.5M | |
61 | 57.5M | uint32_t W = CR.getBitWidth(); |
62 | 57.5M | switch (Pred) { |
63 | 0 | default: |
64 | 0 | llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()"); |
65 | 24.8M | case CmpInst::ICMP_EQ: |
66 | 24.8M | return CR; |
67 | 2.06M | case CmpInst::ICMP_NE: |
68 | 2.06M | if (CR.isSingleElement()) |
69 | 1.69M | return ConstantRange(CR.getUpper(), CR.getLower()); |
70 | 365k | return ConstantRange(W); |
71 | 4.79M | case CmpInst::ICMP_ULT: { |
72 | 4.79M | APInt UMax(CR.getUnsignedMax()); |
73 | 4.79M | if (UMax.isMinValue()) |
74 | 562 | return ConstantRange(W, /* empty */ false); |
75 | 4.79M | return ConstantRange(APInt::getMinValue(W), std::move(UMax)); |
76 | 4.79M | } |
77 | 6.36M | case CmpInst::ICMP_SLT: { |
78 | 6.36M | APInt SMax(CR.getSignedMax()); |
79 | 6.36M | if (SMax.isMinSignedValue()) |
80 | 0 | return ConstantRange(W, /* empty */ false); |
81 | 6.36M | return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax)); |
82 | 6.36M | } |
83 | 499k | case CmpInst::ICMP_ULE: { |
84 | 499k | APInt UMax(CR.getUnsignedMax()); |
85 | 499k | if (UMax.isMaxValue()) |
86 | 19.0k | return ConstantRange(W); |
87 | 480k | return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1); |
88 | 480k | } |
89 | 2.07M | case CmpInst::ICMP_SLE: { |
90 | 2.07M | APInt SMax(CR.getSignedMax()); |
91 | 2.07M | if (SMax.isMaxSignedValue()) |
92 | 112k | return ConstantRange(W); |
93 | 1.95M | return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1); |
94 | 1.95M | } |
95 | 3.50M | case CmpInst::ICMP_UGT: { |
96 | 3.50M | APInt UMin(CR.getUnsignedMin()); |
97 | 3.50M | if (UMin.isMaxValue()) |
98 | 1.00k | return ConstantRange(W, /* empty */ false); |
99 | 3.50M | return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W)); |
100 | 3.50M | } |
101 | 10.8M | case CmpInst::ICMP_SGT: { |
102 | 10.8M | APInt SMin(CR.getSignedMin()); |
103 | 10.8M | if (SMin.isMaxSignedValue()) |
104 | 410 | return ConstantRange(W, /* empty */ false); |
105 | 10.8M | return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W)); |
106 | 10.8M | } |
107 | 828k | case CmpInst::ICMP_UGE: { |
108 | 828k | APInt UMin(CR.getUnsignedMin()); |
109 | 828k | if (UMin.isMinValue()) |
110 | 100k | return ConstantRange(W); |
111 | 728k | return ConstantRange(std::move(UMin), APInt::getNullValue(W)); |
112 | 728k | } |
113 | 1.75M | case CmpInst::ICMP_SGE: { |
114 | 1.75M | APInt SMin(CR.getSignedMin()); |
115 | 1.75M | if (SMin.isMinSignedValue()) |
116 | 207k | return ConstantRange(W); |
117 | 1.54M | return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W)); |
118 | 1.54M | } |
119 | 57.5M | } |
120 | 57.5M | } |
121 | | |
122 | | ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, |
123 | 8.68M | const ConstantRange &CR) { |
124 | 8.68M | // Follows from De-Morgan's laws: |
125 | 8.68M | // |
126 | 8.68M | // ~(~A union ~B) == A intersect B. |
127 | 8.68M | // |
128 | 8.68M | return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) |
129 | 8.68M | .inverse(); |
130 | 8.68M | } |
131 | | |
132 | | ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred, |
133 | 29.9M | const APInt &C) { |
134 | 29.9M | // Computes the exact range that is equal to both the constant ranges returned |
135 | 29.9M | // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true |
136 | 29.9M | // when RHS is a singleton such as an APInt and so the assert is valid. |
137 | 29.9M | // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion |
138 | 29.9M | // returns [0,4) but makeSatisfyICmpRegion returns [0,2). |
139 | 29.9M | // |
140 | 29.9M | assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C)); |
141 | 29.9M | return makeAllowedICmpRegion(Pred, C); |
142 | 29.9M | } |
143 | | |
144 | | bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, |
145 | 7.09M | APInt &RHS) const { |
146 | 7.09M | bool Success = false; |
147 | 7.09M | |
148 | 7.09M | if (isFullSet() || 7.09M isEmptySet()7.09M ) { |
149 | 2 | Pred = isEmptySet() ? CmpInst::ICMP_ULT1 : CmpInst::ICMP_UGE1 ; |
150 | 2 | RHS = APInt(getBitWidth(), 0); |
151 | 2 | Success = true; |
152 | 7.09M | } else if (auto *7.09M OnlyElt7.09M = getSingleElement()) { |
153 | 41.7k | Pred = CmpInst::ICMP_EQ; |
154 | 41.7k | RHS = *OnlyElt; |
155 | 41.7k | Success = true; |
156 | 7.09M | } else if (auto *7.05M OnlyMissingElt7.05M = getSingleMissingElement()) { |
157 | 1.30M | Pred = CmpInst::ICMP_NE; |
158 | 1.30M | RHS = *OnlyMissingElt; |
159 | 1.30M | Success = true; |
160 | 7.05M | } else if (5.74M getLower().isMinSignedValue() || 5.74M getLower().isMinValue()4.20M ) { |
161 | 2.72M | Pred = |
162 | 2.72M | getLower().isMinSignedValue() ? CmpInst::ICMP_SLT1.53M : CmpInst::ICMP_ULT1.18M ; |
163 | 2.72M | RHS = getUpper(); |
164 | 2.72M | Success = true; |
165 | 5.74M | } else if (3.01M getUpper().isMinSignedValue() || 3.01M getUpper().isMinValue()481k ) { |
166 | 3.01M | Pred = |
167 | 3.01M | getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE2.53M : CmpInst::ICMP_UGE481k ; |
168 | 7.09M | RHS = getLower(); |
169 | 7.09M | Success = true; |
170 | 7.09M | } |
171 | 7.09M | |
172 | 7.09M | assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) && |
173 | 7.09M | "Bad result!"); |
174 | 7.09M | |
175 | 7.09M | return Success; |
176 | 7.09M | } |
177 | | |
178 | | ConstantRange |
179 | | ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, |
180 | | const ConstantRange &Other, |
181 | 85.8M | unsigned NoWrapKind) { |
182 | 85.8M | using OBO = OverflowingBinaryOperator; |
183 | 85.8M | |
184 | 85.8M | // Computes the intersection of CR0 and CR1. It is different from |
185 | 85.8M | // intersectWith in that the ConstantRange returned will only contain elements |
186 | 85.8M | // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or |
187 | 85.8M | // not, of both X and Y). |
188 | 85.8M | auto SubsetIntersect = |
189 | 49.4M | [](const ConstantRange &CR0, const ConstantRange &CR1) { |
190 | 49.4M | return CR0.inverse().unionWith(CR1.inverse()).inverse(); |
191 | 49.4M | }; |
192 | 85.8M | |
193 | 85.8M | assert(BinOp >= Instruction::BinaryOpsBegin && |
194 | 85.8M | BinOp < Instruction::BinaryOpsEnd && "Binary operators only!"); |
195 | 85.8M | |
196 | 85.8M | assert((NoWrapKind == OBO::NoSignedWrap || |
197 | 85.8M | NoWrapKind == OBO::NoUnsignedWrap || |
198 | 85.8M | NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && |
199 | 85.8M | "NoWrapKind invalid!"); |
200 | 85.8M | |
201 | 85.8M | unsigned BitWidth = Other.getBitWidth(); |
202 | 85.8M | if (BinOp != Instruction::Add) |
203 | 85.8M | // Conservative answer: empty set |
204 | 0 | return ConstantRange(BitWidth, false); |
205 | 85.8M | |
206 | 85.8M | if (auto *85.8M C85.8M = Other.getSingleElement()) |
207 | 85.7M | if (85.7M C->isNullValue()85.7M ) |
208 | 85.7M | // Full set: nothing signed / unsigned wraps when added to 0. |
209 | 36.4M | return ConstantRange(BitWidth); |
210 | 49.3M | |
211 | 49.3M | ConstantRange Result(BitWidth); |
212 | 49.3M | |
213 | 49.3M | if (NoWrapKind & OBO::NoUnsignedWrap) |
214 | 25.7M | Result = |
215 | 25.7M | SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth), |
216 | 25.7M | -Other.getUnsignedMax())); |
217 | 49.3M | |
218 | 49.3M | if (NoWrapKind & OBO::NoSignedWrap49.3M ) { |
219 | 23.6M | const APInt &SignedMin = Other.getSignedMin(); |
220 | 23.6M | const APInt &SignedMax = Other.getSignedMax(); |
221 | 23.6M | |
222 | 23.6M | if (SignedMax.isStrictlyPositive()) |
223 | 14.9M | Result = SubsetIntersect( |
224 | 14.9M | Result, |
225 | 14.9M | ConstantRange(APInt::getSignedMinValue(BitWidth), |
226 | 14.9M | APInt::getSignedMinValue(BitWidth) - SignedMax)); |
227 | 23.6M | |
228 | 23.6M | if (SignedMin.isNegative()) |
229 | 8.67M | Result = SubsetIntersect( |
230 | 8.67M | Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin, |
231 | 8.67M | APInt::getSignedMinValue(BitWidth))); |
232 | 23.6M | } |
233 | 85.8M | |
234 | 85.8M | return Result; |
235 | 85.8M | } |
236 | | |
237 | 891M | bool ConstantRange::isFullSet() const { |
238 | 231M | return Lower == Upper && Lower.isMaxValue(); |
239 | 891M | } |
240 | | |
241 | 558M | bool ConstantRange::isEmptySet() const { |
242 | 95.5M | return Lower == Upper && Lower.isMinValue(); |
243 | 558M | } |
244 | | |
245 | 271M | bool ConstantRange::isWrappedSet() const { |
246 | 271M | return Lower.ugt(Upper); |
247 | 271M | } |
248 | | |
249 | 184k | bool ConstantRange::isSignWrappedSet() const { |
250 | 184k | return contains(APInt::getSignedMaxValue(getBitWidth())) && |
251 | 88.5k | contains(APInt::getSignedMinValue(getBitWidth())); |
252 | 184k | } |
253 | | |
254 | 6 | APInt ConstantRange::getSetSize() const { |
255 | 6 | if (isFullSet()) |
256 | 1 | return APInt::getOneBitSet(getBitWidth()+1, getBitWidth()); |
257 | 5 | |
258 | 5 | // This is also correct for wrapped sets. |
259 | 5 | return (Upper - Lower).zext(getBitWidth()+1); |
260 | 5 | } |
261 | | |
262 | | bool |
263 | 11.1M | ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const { |
264 | 11.1M | assert(getBitWidth() == Other.getBitWidth()); |
265 | 11.1M | if (isFullSet()) |
266 | 2.25M | return false; |
267 | 8.87M | if (8.87M Other.isFullSet()8.87M ) |
268 | 52 | return true; |
269 | 8.87M | return (Upper - Lower).ult(Other.Upper - Other.Lower); |
270 | 8.87M | } |
271 | | |
272 | | bool |
273 | 15.9M | ConstantRange::isSizeLargerThan(uint64_t MaxSize) const { |
274 | 15.9M | assert(MaxSize && "MaxSize can't be 0."); |
275 | 15.9M | // If this a full set, we need special handling to avoid needing an extra bit |
276 | 15.9M | // to represent the size. |
277 | 15.9M | if (isFullSet()) |
278 | 30 | return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1); |
279 | 15.9M | |
280 | 15.9M | return (Upper - Lower).ugt(MaxSize); |
281 | 15.9M | } |
282 | | |
283 | 63.3M | APInt ConstantRange::getUnsignedMax() const { |
284 | 63.3M | if (isFullSet() || 63.3M isWrappedSet()61.0M ) |
285 | 14.6M | return APInt::getMaxValue(getBitWidth()); |
286 | 48.7M | return getUpper() - 1; |
287 | 48.7M | } |
288 | | |
289 | 14.1M | APInt ConstantRange::getUnsignedMin() const { |
290 | 14.1M | if (isFullSet() || 14.1M (isWrappedSet() && 11.9M !getUpper().isNullValue()3.08M )) |
291 | 3.29M | return APInt::getMinValue(getBitWidth()); |
292 | 10.8M | return getLower(); |
293 | 10.8M | } |
294 | | |
295 | 53.6M | APInt ConstantRange::getSignedMax() const { |
296 | 53.6M | if (isFullSet() || 53.6M Lower.sgt(Upper)50.8M ) |
297 | 3.25M | return APInt::getSignedMaxValue(getBitWidth()); |
298 | 50.4M | return getUpper() - 1; |
299 | 50.4M | } |
300 | | |
301 | 89.2M | APInt ConstantRange::getSignedMin() const { |
302 | 89.2M | if (isFullSet() || 89.2M (Lower.sgt(Upper) && 81.0M !getUpper().isMinSignedValue()1.77M )) |
303 | 9.01M | return APInt::getSignedMinValue(getBitWidth()); |
304 | 80.2M | return getLower(); |
305 | 80.2M | } |
306 | | |
307 | 16.6M | bool ConstantRange::contains(const APInt &V) const { |
308 | 16.6M | if (Lower == Upper) |
309 | 51.8k | return isFullSet(); |
310 | 16.5M | |
311 | 16.5M | if (16.5M !isWrappedSet()16.5M ) |
312 | 12.6M | return Lower.ule(V) && 12.6M V.ult(Upper)11.5M ; |
313 | 3.85M | return Lower.ule(V) || 3.85M V.ult(Upper)2.42M ; |
314 | 16.6M | } |
315 | | |
316 | 102M | bool ConstantRange::contains(const ConstantRange &Other) const { |
317 | 102M | if (isFullSet() || 102M Other.isEmptySet()65.8M ) return true36.4M ; |
318 | 65.8M | if (65.8M isEmptySet() || 65.8M Other.isFullSet()65.4M ) return false19.3M ; |
319 | 46.4M | |
320 | 46.4M | if (46.4M !isWrappedSet()46.4M ) { |
321 | 23.8M | if (Other.isWrappedSet()) |
322 | 7.95M | return false; |
323 | 15.8M | |
324 | 15.8M | return Lower.ule(Other.getLower()) && 15.8M Other.getUpper().ule(Upper)14.6M ; |
325 | 23.8M | } |
326 | 22.6M | |
327 | 22.6M | if (22.6M !Other.isWrappedSet()22.6M ) |
328 | 12.5M | return Other.getUpper().ule(Upper) || |
329 | 7.74M | Lower.ule(Other.getLower()); |
330 | 10.1M | |
331 | 10.1M | return Other.getUpper().ule(Upper) && 10.1M Lower.ule(Other.getLower())6.75M ; |
332 | 102M | } |
333 | | |
334 | 947k | ConstantRange ConstantRange::subtract(const APInt &Val) const { |
335 | 947k | assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); |
336 | 947k | // If the set is empty or full, don't modify the endpoints. |
337 | 947k | if (Lower == Upper) |
338 | 30.1k | return *this; |
339 | 917k | return ConstantRange(Lower - Val, Upper - Val); |
340 | 917k | } |
341 | | |
342 | 932k | ConstantRange ConstantRange::difference(const ConstantRange &CR) const { |
343 | 932k | return intersectWith(CR.inverse()); |
344 | 932k | } |
345 | | |
346 | 30.1M | ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { |
347 | 30.1M | assert(getBitWidth() == CR.getBitWidth() && |
348 | 30.1M | "ConstantRange types don't agree!"); |
349 | 30.1M | |
350 | 30.1M | // Handle common cases. |
351 | 30.1M | if ( isEmptySet() || 30.1M CR.isFullSet()30.1M ) return *this8.54M ; |
352 | 21.6M | if (21.6M CR.isEmptySet() || 21.6M isFullSet()21.6M ) return CR8.37M ; |
353 | 13.2M | |
354 | 13.2M | if (13.2M !isWrappedSet() && 13.2M CR.isWrappedSet()7.18M ) |
355 | 1.28M | return CR.intersectWith(*this); |
356 | 11.9M | |
357 | 11.9M | if (11.9M !isWrappedSet() && 11.9M !CR.isWrappedSet()5.89M ) { |
358 | 5.89M | if (Lower.ult(CR.Lower)5.89M ) { |
359 | 368k | if (Upper.ule(CR.Lower)) |
360 | 207 | return ConstantRange(getBitWidth(), false); |
361 | 368k | |
362 | 368k | if (368k Upper.ult(CR.Upper)368k ) |
363 | 28.7k | return ConstantRange(CR.Lower, Upper); |
364 | 339k | |
365 | 339k | return CR; |
366 | 339k | } |
367 | 5.52M | if (5.52M Upper.ult(CR.Upper)5.52M ) |
368 | 28.7k | return *this; |
369 | 5.49M | |
370 | 5.49M | if (5.49M Lower.ult(CR.Upper)5.49M ) |
371 | 5.49M | return ConstantRange(Lower, CR.Upper); |
372 | 106 | |
373 | 106 | return ConstantRange(getBitWidth(), false); |
374 | 106 | } |
375 | 6.08M | |
376 | 6.08M | if (6.08M isWrappedSet() && 6.08M !CR.isWrappedSet()6.08M ) { |
377 | 3.65M | if (CR.Lower.ult(Upper)3.65M ) { |
378 | 1.99M | if (CR.Upper.ult(Upper)) |
379 | 691k | return CR; |
380 | 1.29M | |
381 | 1.29M | if (1.29M CR.Upper.ule(Lower)1.29M ) |
382 | 452k | return ConstantRange(CR.Lower, Upper); |
383 | 846k | |
384 | 846k | if (846k isSizeStrictlySmallerThan(CR)846k ) |
385 | 550k | return *this; |
386 | 296k | return CR; |
387 | 296k | } |
388 | 1.65M | if (1.65M CR.Lower.ult(Lower)1.65M ) { |
389 | 1.44M | if (CR.Upper.ule(Lower)) |
390 | 6.20k | return ConstantRange(getBitWidth(), false); |
391 | 1.43M | |
392 | 1.43M | return ConstantRange(Lower, CR.Upper); |
393 | 1.43M | } |
394 | 214k | return CR; |
395 | 214k | } |
396 | 2.43M | |
397 | 2.43M | if (2.43M CR.Upper.ult(Upper)2.43M ) { |
398 | 1.35M | if (CR.Lower.ult(Upper)1.35M ) { |
399 | 616k | if (isSizeStrictlySmallerThan(CR)) |
400 | 6.60k | return *this; |
401 | 610k | return CR; |
402 | 610k | } |
403 | 742k | |
404 | 742k | if (742k CR.Lower.ult(Lower)742k ) |
405 | 33.5k | return ConstantRange(Lower, CR.Upper); |
406 | 708k | |
407 | 708k | return CR; |
408 | 708k | } |
409 | 1.07M | if (1.07M CR.Upper.ule(Lower)1.07M ) { |
410 | 813k | if (CR.Lower.ult(Lower)) |
411 | 19.5k | return *this; |
412 | 793k | |
413 | 793k | return ConstantRange(CR.Lower, Upper); |
414 | 793k | } |
415 | 265k | if (265k isSizeStrictlySmallerThan(CR)265k ) |
416 | 9.96k | return *this; |
417 | 255k | return CR; |
418 | 255k | } |
419 | | |
420 | 63.1M | ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { |
421 | 63.1M | assert(getBitWidth() == CR.getBitWidth() && |
422 | 63.1M | "ConstantRange types don't agree!"); |
423 | 63.1M | |
424 | 63.1M | if ( isFullSet() || 63.1M CR.isEmptySet()59.6M ) return *this3.79M ; |
425 | 59.3M | if (59.3M CR.isFullSet() || 59.3M isEmptySet()59.2M ) return CR49.4M ; |
426 | 9.87M | |
427 | 9.87M | if (9.87M !isWrappedSet() && 9.87M CR.isWrappedSet()5.59M ) return CR.unionWith(*this)2.23M ; |
428 | 7.64M | |
429 | 7.64M | if (7.64M !isWrappedSet() && 7.64M !CR.isWrappedSet()3.35M ) { |
430 | 3.35M | if (CR.Upper.ult(Lower) || 3.35M Upper.ult(CR.Lower)3.34M ) { |
431 | 75.0k | // If the two ranges are disjoint, find the smaller gap and bridge it. |
432 | 75.0k | APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; |
433 | 75.0k | if (d1.ult(d2)) |
434 | 24.1k | return ConstantRange(Lower, CR.Upper); |
435 | 50.8k | return ConstantRange(CR.Lower, Upper); |
436 | 50.8k | } |
437 | 3.28M | |
438 | 3.28M | APInt L = CR.Lower.ult(Lower) ? 3.28M CR.Lower43.7k : Lower3.23M ; |
439 | 3.28M | APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper162k : Upper3.11M ; |
440 | 3.28M | |
441 | 3.28M | if (L.isNullValue() && 3.28M U.isNullValue()1.65M ) |
442 | 0 | return ConstantRange(getBitWidth()); |
443 | 3.28M | |
444 | 3.28M | return ConstantRange(std::move(L), std::move(U)); |
445 | 3.28M | } |
446 | 4.28M | |
447 | 4.28M | if (4.28M !CR.isWrappedSet()4.28M ) { |
448 | 2.36M | // ------U L----- and ------U L----- : this |
449 | 2.36M | // L--U L--U : CR |
450 | 2.36M | if (CR.Upper.ule(Upper) || 2.36M CR.Lower.uge(Lower)2.21M ) |
451 | 202k | return *this; |
452 | 2.16M | |
453 | 2.16M | // ------U L----- : this |
454 | 2.16M | // L---------U : CR |
455 | 2.16M | if (2.16M CR.Lower.ule(Upper) && 2.16M Lower.ule(CR.Upper)958k ) |
456 | 915k | return ConstantRange(getBitWidth()); |
457 | 1.25M | |
458 | 1.25M | // ----U L---- : this |
459 | 1.25M | // L---U : CR |
460 | 1.25M | // <d1> <d2> |
461 | 1.25M | if (1.25M Upper.ule(CR.Lower) && 1.25M CR.Upper.ule(Lower)1.24M ) { |
462 | 1.24M | APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; |
463 | 1.24M | if (d1.ult(d2)) |
464 | 40.4k | return ConstantRange(Lower, CR.Upper); |
465 | 1.20M | return ConstantRange(CR.Lower, Upper); |
466 | 1.20M | } |
467 | 5.51k | |
468 | 5.51k | // ----U L----- : this |
469 | 5.51k | // L----U : CR |
470 | 5.51k | if (5.51k Upper.ult(CR.Lower) && 5.51k Lower.ult(CR.Upper)104 ) |
471 | 104 | return ConstantRange(CR.Lower, Upper); |
472 | 5.41k | |
473 | 5.41k | // ------U L---- : this |
474 | 5.41k | // L-----U : CR |
475 | 0 | assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && |
476 | 5.41k | "ConstantRange::unionWith missed a case with one range wrapped"); |
477 | 5.41k | return ConstantRange(Lower, CR.Upper); |
478 | 5.41k | } |
479 | 1.91M | |
480 | 1.91M | // ------U L---- and ------U L---- : this |
481 | 1.91M | // -U L----------- and ------------U L : CR |
482 | 1.91M | if (1.91M CR.Lower.ule(Upper) || 1.91M Lower.ule(CR.Upper)1.89M ) |
483 | 19.8k | return ConstantRange(getBitWidth()); |
484 | 1.89M | |
485 | 1.89M | APInt L = CR.Lower.ult(Lower) ? 1.89M CR.Lower1.51k : Lower1.89M ; |
486 | 1.89M | APInt U = CR.Upper.ugt(Upper) ? CR.Upper47.9k : Upper1.84M ; |
487 | 63.1M | |
488 | 63.1M | return ConstantRange(std::move(L), std::move(U)); |
489 | 63.1M | } |
490 | | |
491 | | ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, |
492 | 133k | uint32_t ResultBitWidth) const { |
493 | 133k | switch (CastOp) { |
494 | 0 | default: |
495 | 0 | llvm_unreachable("unsupported cast type"); |
496 | 61.8k | case Instruction::Trunc: |
497 | 61.8k | return truncate(ResultBitWidth); |
498 | 18.0k | case Instruction::SExt: |
499 | 18.0k | return signExtend(ResultBitWidth); |
500 | 32.3k | case Instruction::ZExt: |
501 | 32.3k | return zeroExtend(ResultBitWidth); |
502 | 3.54k | case Instruction::BitCast: |
503 | 3.54k | return *this; |
504 | 10.0k | case Instruction::FPToUI: |
505 | 10.0k | case Instruction::FPToSI: |
506 | 10.0k | if (getBitWidth() == ResultBitWidth) |
507 | 10.0k | return *this; |
508 | 10.0k | else |
509 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
510 | 5.88k | case Instruction::UIToFP: { |
511 | 5.88k | // TODO: use input range if available |
512 | 5.88k | auto BW = getBitWidth(); |
513 | 5.88k | APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth); |
514 | 5.88k | APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth); |
515 | 5.88k | return ConstantRange(std::move(Min), std::move(Max)); |
516 | 0 | } |
517 | 1.95k | case Instruction::SIToFP: { |
518 | 1.95k | // TODO: use input range if available |
519 | 1.95k | auto BW = getBitWidth(); |
520 | 1.95k | APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth); |
521 | 1.95k | APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth); |
522 | 1.95k | return ConstantRange(std::move(SMin), std::move(SMax)); |
523 | 0 | } |
524 | 0 | case Instruction::FPTrunc: |
525 | 0 | case Instruction::FPExt: |
526 | 0 | case Instruction::IntToPtr: |
527 | 0 | case Instruction::PtrToInt: |
528 | 0 | case Instruction::AddrSpaceCast: |
529 | 0 | // Conservatively return full set. |
530 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
531 | 0 | }; |
532 | 0 | } |
533 | | |
534 | 1.17M | ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { |
535 | 1.17M | if (isEmptySet()1.17M ) return ConstantRange(DstTySize, /*isFullSet=*/false)1 ; |
536 | 1.17M | |
537 | 1.17M | unsigned SrcTySize = getBitWidth(); |
538 | 1.17M | assert(SrcTySize < DstTySize && "Not a value extension"); |
539 | 1.17M | if (isFullSet() || 1.17M isWrappedSet()350k ) { |
540 | 992k | // Change into [0, 1 << src bit width) |
541 | 992k | APInt LowerExt(DstTySize, 0); |
542 | 992k | if (!Upper) // special case: [X, 0) -- not really wrapping around |
543 | 865 | LowerExt = Lower.zext(DstTySize); |
544 | 992k | return ConstantRange(std::move(LowerExt), |
545 | 992k | APInt::getOneBitSet(DstTySize, SrcTySize)); |
546 | 992k | } |
547 | 186k | |
548 | 186k | return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); |
549 | 186k | } |
550 | | |
551 | 1.07M | ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { |
552 | 1.07M | if (isEmptySet()1.07M ) return ConstantRange(DstTySize, /*isFullSet=*/false)1 ; |
553 | 1.07M | |
554 | 1.07M | unsigned SrcTySize = getBitWidth(); |
555 | 1.07M | assert(SrcTySize < DstTySize && "Not a value extension"); |
556 | 1.07M | |
557 | 1.07M | // special case: [X, INT_MIN) -- not really wrapping around |
558 | 1.07M | if (Upper.isMinSignedValue()) |
559 | 2.41k | return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); |
560 | 1.07M | |
561 | 1.07M | if (1.07M isFullSet() || 1.07M isSignWrappedSet()184k ) { |
562 | 977k | return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), |
563 | 977k | APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); |
564 | 977k | } |
565 | 95.7k | |
566 | 95.7k | return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); |
567 | 95.7k | } |
568 | | |
569 | 5.05M | ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { |
570 | 5.05M | assert(getBitWidth() > DstTySize && "Not a value truncation"); |
571 | 5.05M | if (isEmptySet()) |
572 | 1 | return ConstantRange(DstTySize, /*isFullSet=*/false); |
573 | 5.05M | if (5.05M isFullSet()5.05M ) |
574 | 166k | return ConstantRange(DstTySize, /*isFullSet=*/true); |
575 | 4.88M | |
576 | 4.88M | APInt LowerDiv(Lower), UpperDiv(Upper); |
577 | 4.88M | ConstantRange Union(DstTySize, /*isFullSet=*/false); |
578 | 4.88M | |
579 | 4.88M | // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] |
580 | 4.88M | // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and |
581 | 4.88M | // then we do the union with [MaxValue, Upper) |
582 | 4.88M | if (isWrappedSet()4.88M ) { |
583 | 2.23M | // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole |
584 | 2.23M | // truncated range. |
585 | 2.23M | if (Upper.getActiveBits() > DstTySize || |
586 | 2.07M | Upper.countTrailingOnes() == DstTySize) |
587 | 176k | return ConstantRange(DstTySize, /*isFullSet=*/true); |
588 | 2.05M | |
589 | 2.05M | Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); |
590 | 2.05M | UpperDiv.setAllBits(); |
591 | 2.05M | |
592 | 2.05M | // Union covers the MaxValue case, so return if the remaining range is just |
593 | 2.05M | // MaxValue(DstTy). |
594 | 2.05M | if (LowerDiv == UpperDiv) |
595 | 12.4k | return Union; |
596 | 4.69M | } |
597 | 4.69M | |
598 | 4.69M | // Chop off the most significant bits that are past the destination bitwidth. |
599 | 4.69M | if (4.69M LowerDiv.getActiveBits() > DstTySize4.69M ) { |
600 | 2.07M | // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv. |
601 | 2.07M | APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize); |
602 | 2.07M | LowerDiv -= Adjust; |
603 | 2.07M | UpperDiv -= Adjust; |
604 | 2.07M | } |
605 | 4.69M | |
606 | 4.69M | unsigned UpperDivWidth = UpperDiv.getActiveBits(); |
607 | 4.69M | if (UpperDivWidth <= DstTySize) |
608 | 2.33M | return ConstantRange(LowerDiv.trunc(DstTySize), |
609 | 2.33M | UpperDiv.trunc(DstTySize)).unionWith(Union); |
610 | 2.36M | |
611 | 2.36M | // The truncated value wraps around. Check if we can do better than fullset. |
612 | 2.36M | if (2.36M UpperDivWidth == DstTySize + 12.36M ) { |
613 | 107k | // Clear the MSB so that UpperDiv wraps around. |
614 | 107k | UpperDiv.clearBit(DstTySize); |
615 | 107k | if (UpperDiv.ult(LowerDiv)) |
616 | 153 | return ConstantRange(LowerDiv.trunc(DstTySize), |
617 | 153 | UpperDiv.trunc(DstTySize)).unionWith(Union); |
618 | 2.36M | } |
619 | 2.36M | |
620 | 2.36M | return ConstantRange(DstTySize, /*isFullSet=*/true); |
621 | 2.36M | } |
622 | | |
623 | 84.5k | ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { |
624 | 84.5k | unsigned SrcTySize = getBitWidth(); |
625 | 84.5k | if (SrcTySize > DstTySize) |
626 | 9.23k | return truncate(DstTySize); |
627 | 75.2k | if (75.2k SrcTySize < DstTySize75.2k ) |
628 | 11.0k | return zeroExtend(DstTySize); |
629 | 64.2k | return *this; |
630 | 64.2k | } |
631 | | |
632 | 20.7k | ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { |
633 | 20.7k | unsigned SrcTySize = getBitWidth(); |
634 | 20.7k | if (SrcTySize > DstTySize) |
635 | 15 | return truncate(DstTySize); |
636 | 20.7k | if (20.7k SrcTySize < DstTySize20.7k ) |
637 | 823 | return signExtend(DstTySize); |
638 | 19.8k | return *this; |
639 | 19.8k | } |
640 | | |
641 | | ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, |
642 | 636k | const ConstantRange &Other) const { |
643 | 636k | assert(BinOp >= Instruction::BinaryOpsBegin && |
644 | 636k | BinOp < Instruction::BinaryOpsEnd && "Binary operators only!"); |
645 | 636k | |
646 | 636k | switch (BinOp) { |
647 | 477k | case Instruction::Add: |
648 | 477k | return add(Other); |
649 | 17 | case Instruction::Sub: |
650 | 17 | return sub(Other); |
651 | 6.54k | case Instruction::Mul: |
652 | 6.54k | return multiply(Other); |
653 | 5.75k | case Instruction::UDiv: |
654 | 5.75k | return udiv(Other); |
655 | 37.3k | case Instruction::Shl: |
656 | 37.3k | return shl(Other); |
657 | 42.8k | case Instruction::LShr: |
658 | 42.8k | return lshr(Other); |
659 | 41.4k | case Instruction::And: |
660 | 41.4k | return binaryAnd(Other); |
661 | 10.1k | case Instruction::Or: |
662 | 10.1k | return binaryOr(Other); |
663 | 636k | // Note: floating point operations applied to abstract ranges are just |
664 | 636k | // ideal integer operations with a lossy representation |
665 | 2.49k | case Instruction::FAdd: |
666 | 2.49k | return add(Other); |
667 | 1.05k | case Instruction::FSub: |
668 | 1.05k | return sub(Other); |
669 | 11.2k | case Instruction::FMul: |
670 | 11.2k | return multiply(Other); |
671 | 0 | default: |
672 | 0 | // Conservatively return full set. |
673 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
674 | 0 | } |
675 | 0 | } |
676 | | |
677 | | ConstantRange |
678 | 6.70M | ConstantRange::add(const ConstantRange &Other) const { |
679 | 6.70M | if (isEmptySet() || 6.70M Other.isEmptySet()6.70M ) |
680 | 881 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
681 | 6.70M | if (6.70M isFullSet() || 6.70M Other.isFullSet()5.75M ) |
682 | 3.04M | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
683 | 3.66M | |
684 | 3.66M | APInt NewLower = getLower() + Other.getLower(); |
685 | 3.66M | APInt NewUpper = getUpper() + Other.getUpper() - 1; |
686 | 3.66M | if (NewLower == NewUpper) |
687 | 401 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
688 | 3.66M | |
689 | 3.66M | ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); |
690 | 3.66M | if (X.isSizeStrictlySmallerThan(*this) || |
691 | 3.43M | X.isSizeStrictlySmallerThan(Other)) |
692 | 3.66M | // We've wrapped, therefore, full set. |
693 | 229k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
694 | 3.43M | return X; |
695 | 3.43M | } |
696 | | |
697 | 227 | ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const { |
698 | 227 | // Calculate the subset of this range such that "X + Other" is |
699 | 227 | // guaranteed not to wrap (overflow) for all X in this subset. |
700 | 227 | // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are |
701 | 227 | // passing a single element range. |
702 | 227 | auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add, |
703 | 227 | ConstantRange(Other), |
704 | 227 | OverflowingBinaryOperator::NoSignedWrap); |
705 | 227 | auto NSWConstrainedRange = intersectWith(NSWRange); |
706 | 227 | |
707 | 227 | return NSWConstrainedRange.add(ConstantRange(Other)); |
708 | 227 | } |
709 | | |
710 | | ConstantRange |
711 | 1.09k | ConstantRange::sub(const ConstantRange &Other) const { |
712 | 1.09k | if (isEmptySet() || 1.09k Other.isEmptySet()940 ) |
713 | 190 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
714 | 900 | if (900 isFullSet() || 900 Other.isFullSet()111 ) |
715 | 859 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
716 | 41 | |
717 | 41 | APInt NewLower = getLower() - Other.getUpper() + 1; |
718 | 41 | APInt NewUpper = getUpper() - Other.getLower(); |
719 | 41 | if (NewLower == NewUpper) |
720 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
721 | 41 | |
722 | 41 | ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); |
723 | 41 | if (X.isSizeStrictlySmallerThan(*this) || |
724 | 41 | X.isSizeStrictlySmallerThan(Other)) |
725 | 41 | // We've wrapped, therefore, full set. |
726 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
727 | 41 | return X; |
728 | 41 | } |
729 | | |
730 | | ConstantRange |
731 | 2.44M | ConstantRange::multiply(const ConstantRange &Other) const { |
732 | 2.44M | // TODO: If either operand is a single element and the multiply is known to |
733 | 2.44M | // be non-wrapping, round the result min and max value to the appropriate |
734 | 2.44M | // multiple of that element. If wrapping is possible, at least adjust the |
735 | 2.44M | // range according to the greatest power-of-two factor of the single element. |
736 | 2.44M | |
737 | 2.44M | if (isEmptySet() || 2.44M Other.isEmptySet()2.44M ) |
738 | 521 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
739 | 2.44M | |
740 | 2.44M | // Multiplication is signedness-independent. However different ranges can be |
741 | 2.44M | // obtained depending on how the input ranges are treated. These different |
742 | 2.44M | // ranges are all conservatively correct, but one might be better than the |
743 | 2.44M | // other. We calculate two ranges; one treating the inputs as unsigned |
744 | 2.44M | // and the other signed, then return the smallest of these ranges. |
745 | 2.44M | |
746 | 2.44M | // Unsigned range first. |
747 | 2.44M | APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); |
748 | 2.44M | APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); |
749 | 2.44M | APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); |
750 | 2.44M | APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); |
751 | 2.44M | |
752 | 2.44M | ConstantRange Result_zext = ConstantRange(this_min * Other_min, |
753 | 2.44M | this_max * Other_max + 1); |
754 | 2.44M | ConstantRange UR = Result_zext.truncate(getBitWidth()); |
755 | 2.44M | |
756 | 2.44M | // If the unsigned range doesn't wrap, and isn't negative then it's a range |
757 | 2.44M | // from one positive number to another which is as good as we can generate. |
758 | 2.44M | // In this case, skip the extra work of generating signed ranges which aren't |
759 | 2.44M | // going to be better than this range. |
760 | 2.44M | if (!UR.isWrappedSet() && |
761 | 2.44M | (UR.getUpper().isNonNegative() || 2.44M UR.getUpper().isMinSignedValue()2.30M )) |
762 | 145k | return UR; |
763 | 2.30M | |
764 | 2.30M | // Now the signed range. Because we could be dealing with negative numbers |
765 | 2.30M | // here, the lower bound is the smallest of the cartesian product of the |
766 | 2.30M | // lower and upper ranges; for example: |
767 | 2.30M | // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. |
768 | 2.30M | // Similarly for the upper bound, swapping min for max. |
769 | 2.30M | |
770 | 2.30M | this_min = getSignedMin().sext(getBitWidth() * 2); |
771 | 2.30M | this_max = getSignedMax().sext(getBitWidth() * 2); |
772 | 2.30M | Other_min = Other.getSignedMin().sext(getBitWidth() * 2); |
773 | 2.30M | Other_max = Other.getSignedMax().sext(getBitWidth() * 2); |
774 | 2.30M | |
775 | 2.30M | auto L = {this_min * Other_min, this_min * Other_max, |
776 | 2.30M | this_max * Other_min, this_max * Other_max}; |
777 | 13.8M | auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; |
778 | 2.30M | ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1); |
779 | 2.30M | ConstantRange SR = Result_sext.truncate(getBitWidth()); |
780 | 2.30M | |
781 | 2.30M | return UR.isSizeStrictlySmallerThan(SR) ? UR52 : SR2.30M ; |
782 | 2.44M | } |
783 | | |
784 | | ConstantRange |
785 | 225k | ConstantRange::smax(const ConstantRange &Other) const { |
786 | 225k | // X smax Y is: range(smax(X_smin, Y_smin), |
787 | 225k | // smax(X_smax, Y_smax)) |
788 | 225k | if (isEmptySet() || 225k Other.isEmptySet()225k ) |
789 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
790 | 225k | APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); |
791 | 225k | APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; |
792 | 225k | if (NewU == NewL) |
793 | 20.9k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
794 | 204k | return ConstantRange(std::move(NewL), std::move(NewU)); |
795 | 204k | } |
796 | | |
797 | | ConstantRange |
798 | 210k | ConstantRange::umax(const ConstantRange &Other) const { |
799 | 210k | // X umax Y is: range(umax(X_umin, Y_umin), |
800 | 210k | // umax(X_umax, Y_umax)) |
801 | 210k | if (isEmptySet() || 210k Other.isEmptySet()210k ) |
802 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
803 | 210k | APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); |
804 | 210k | APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; |
805 | 210k | if (NewU == NewL) |
806 | 138k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
807 | 71.8k | return ConstantRange(std::move(NewL), std::move(NewU)); |
808 | 71.8k | } |
809 | | |
810 | | ConstantRange |
811 | 157 | ConstantRange::smin(const ConstantRange &Other) const { |
812 | 157 | // X smin Y is: range(smin(X_smin, Y_smin), |
813 | 157 | // smin(X_smax, Y_smax)) |
814 | 157 | if (isEmptySet() || 157 Other.isEmptySet()153 ) |
815 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
816 | 152 | APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); |
817 | 152 | APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1; |
818 | 152 | if (NewU == NewL) |
819 | 97 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
820 | 55 | return ConstantRange(std::move(NewL), std::move(NewU)); |
821 | 55 | } |
822 | | |
823 | | ConstantRange |
824 | 173 | ConstantRange::umin(const ConstantRange &Other) const { |
825 | 173 | // X umin Y is: range(umin(X_umin, Y_umin), |
826 | 173 | // umin(X_umax, Y_umax)) |
827 | 173 | if (isEmptySet() || 173 Other.isEmptySet()169 ) |
828 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
829 | 168 | APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); |
830 | 168 | APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1; |
831 | 168 | if (NewU == NewL) |
832 | 47 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
833 | 121 | return ConstantRange(std::move(NewL), std::move(NewU)); |
834 | 121 | } |
835 | | |
836 | | ConstantRange |
837 | 220k | ConstantRange::udiv(const ConstantRange &RHS) const { |
838 | 220k | if (isEmptySet() || 220k RHS.isEmptySet()220k || RHS.getUnsignedMax().isNullValue()220k ) |
839 | 7 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
840 | 220k | if (220k RHS.isFullSet()220k ) |
841 | 2.05k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
842 | 218k | |
843 | 218k | APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); |
844 | 218k | |
845 | 218k | APInt RHS_umin = RHS.getUnsignedMin(); |
846 | 218k | if (RHS_umin.isNullValue()218k ) { |
847 | 3.15k | // We want the lowest value in RHS excluding zero. Usually that would be 1 |
848 | 3.15k | // except for a range in the form of [X, 1) in which case it would be X. |
849 | 3.15k | if (RHS.getUpper() == 1) |
850 | 0 | RHS_umin = RHS.getLower(); |
851 | 3.15k | else |
852 | 3.15k | RHS_umin = 1; |
853 | 3.15k | } |
854 | 218k | |
855 | 218k | APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; |
856 | 218k | |
857 | 218k | // If the LHS is Full and the RHS is a wrapped interval containing 1 then |
858 | 218k | // this could occur. |
859 | 218k | if (Lower == Upper) |
860 | 1.13k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
861 | 217k | |
862 | 217k | return ConstantRange(std::move(Lower), std::move(Upper)); |
863 | 217k | } |
864 | | |
865 | | ConstantRange |
866 | 41.4k | ConstantRange::binaryAnd(const ConstantRange &Other) const { |
867 | 41.4k | if (isEmptySet() || 41.4k Other.isEmptySet()41.4k ) |
868 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
869 | 41.4k | |
870 | 41.4k | // TODO: replace this with something less conservative |
871 | 41.4k | |
872 | 41.4k | APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); |
873 | 41.4k | if (umin.isAllOnesValue()) |
874 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
875 | 41.4k | return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1); |
876 | 41.4k | } |
877 | | |
878 | | ConstantRange |
879 | 10.1k | ConstantRange::binaryOr(const ConstantRange &Other) const { |
880 | 10.1k | if (isEmptySet() || 10.1k Other.isEmptySet()10.1k ) |
881 | 0 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
882 | 10.1k | |
883 | 10.1k | // TODO: replace this with something less conservative |
884 | 10.1k | |
885 | 10.1k | APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); |
886 | 10.1k | if (umax.isNullValue()) |
887 | 9 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
888 | 10.1k | return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth())); |
889 | 10.1k | } |
890 | | |
891 | | ConstantRange |
892 | 37.3k | ConstantRange::shl(const ConstantRange &Other) const { |
893 | 37.3k | if (isEmptySet() || 37.3k Other.isEmptySet()37.3k ) |
894 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
895 | 37.3k | |
896 | 37.3k | APInt max = getUnsignedMax(); |
897 | 37.3k | APInt Other_umax = Other.getUnsignedMax(); |
898 | 37.3k | |
899 | 37.3k | // there's overflow! |
900 | 37.3k | if (Other_umax.uge(max.countLeadingZeros())) |
901 | 23.4k | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
902 | 13.8k | |
903 | 13.8k | // FIXME: implement the other tricky cases |
904 | 13.8k | |
905 | 13.8k | APInt min = getUnsignedMin(); |
906 | 13.8k | min <<= Other.getUnsignedMin(); |
907 | 13.8k | max <<= Other_umax; |
908 | 13.8k | |
909 | 13.8k | return ConstantRange(std::move(min), std::move(max) + 1); |
910 | 13.8k | } |
911 | | |
912 | | ConstantRange |
913 | 42.8k | ConstantRange::lshr(const ConstantRange &Other) const { |
914 | 42.8k | if (isEmptySet() || 42.8k Other.isEmptySet()42.8k ) |
915 | 5 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
916 | 42.8k | |
917 | 42.8k | APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1; |
918 | 42.8k | APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); |
919 | 42.8k | if (min == max) |
920 | 3 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
921 | 42.8k | |
922 | 42.8k | return ConstantRange(std::move(min), std::move(max)); |
923 | 42.8k | } |
924 | | |
925 | 177M | ConstantRange ConstantRange::inverse() const { |
926 | 177M | if (isFullSet()) |
927 | 49.7M | return ConstantRange(getBitWidth(), /*isFullSet=*/false); |
928 | 127M | if (127M isEmptySet()127M ) |
929 | 323 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); |
930 | 127M | return ConstantRange(Upper, Lower); |
931 | 127M | } |
932 | | |
933 | 3.96k | void ConstantRange::print(raw_ostream &OS) const { |
934 | 3.96k | if (isFullSet()) |
935 | 1.91k | OS << "full-set"; |
936 | 2.05k | else if (2.05k isEmptySet()2.05k ) |
937 | 2 | OS << "empty-set"; |
938 | 2.05k | else |
939 | 2.05k | OS << "[" << Lower << "," << Upper << ")"; |
940 | 3.96k | } |
941 | | |
942 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
943 | | LLVM_DUMP_METHOD void ConstantRange::dump() const { |
944 | | print(dbgs()); |
945 | | } |
946 | | #endif |
947 | | |
948 | 798k | ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) { |
949 | 798k | const unsigned NumRanges = Ranges.getNumOperands() / 2; |
950 | 798k | assert(NumRanges >= 1 && "Must have at least one range!"); |
951 | 798k | assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs"); |
952 | 798k | |
953 | 798k | auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0)); |
954 | 798k | auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1)); |
955 | 798k | |
956 | 798k | ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue()); |
957 | 798k | |
958 | 798k | for (unsigned i = 1; i < NumRanges798k ; ++i8 ) { |
959 | 8 | auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0)); |
960 | 8 | auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1)); |
961 | 8 | |
962 | 8 | // Note: unionWith will potentially create a range that contains values not |
963 | 8 | // contained in any of the original N ranges. |
964 | 8 | CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue())); |
965 | 8 | } |
966 | 798k | |
967 | 798k | return CR; |
968 | 798k | } |