File: | lib/IR/ConstantRange.cpp |
Warning: | line 323, column 34 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | Upper(Lower) {} | |||
44 | ||||
45 | ConstantRange::ConstantRange(APInt V) | |||
46 | : Lower(std::move(V)), Upper(Lower + 1) {} | |||
47 | ||||
48 | ConstantRange::ConstantRange(APInt L, APInt U) | |||
49 | : Lower(std::move(L)), Upper(std::move(U)) { | |||
50 | assert(Lower.getBitWidth() == Upper.getBitWidth() &&(static_cast <bool> (Lower.getBitWidth() == Upper.getBitWidth () && "ConstantRange with unequal bit widths") ? void (0) : __assert_fail ("Lower.getBitWidth() == Upper.getBitWidth() && \"ConstantRange with unequal bit widths\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 51, __extension__ __PRETTY_FUNCTION__)) | |||
51 | "ConstantRange with unequal bit widths")(static_cast <bool> (Lower.getBitWidth() == Upper.getBitWidth () && "ConstantRange with unequal bit widths") ? void (0) : __assert_fail ("Lower.getBitWidth() == Upper.getBitWidth() && \"ConstantRange with unequal bit widths\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 51, __extension__ __PRETTY_FUNCTION__)); | |||
52 | assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&(static_cast <bool> ((Lower != Upper || (Lower.isMaxValue () || Lower.isMinValue())) && "Lower == Upper, but they aren't min or max value!" ) ? void (0) : __assert_fail ("(Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && \"Lower == Upper, but they aren't min or max value!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 53, __extension__ __PRETTY_FUNCTION__)) | |||
53 | "Lower == Upper, but they aren't min or max value!")(static_cast <bool> ((Lower != Upper || (Lower.isMaxValue () || Lower.isMinValue())) && "Lower == Upper, but they aren't min or max value!" ) ? void (0) : __assert_fail ("(Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && \"Lower == Upper, but they aren't min or max value!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 53, __extension__ __PRETTY_FUNCTION__)); | |||
54 | } | |||
55 | ||||
56 | ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, | |||
57 | const ConstantRange &CR) { | |||
58 | if (CR.isEmptySet()) | |||
59 | return CR; | |||
60 | ||||
61 | uint32_t W = CR.getBitWidth(); | |||
62 | switch (Pred) { | |||
63 | default: | |||
64 | llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()")::llvm::llvm_unreachable_internal("Invalid ICmp predicate to makeAllowedICmpRegion()" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 64); | |||
65 | case CmpInst::ICMP_EQ: | |||
66 | return CR; | |||
67 | case CmpInst::ICMP_NE: | |||
68 | if (CR.isSingleElement()) | |||
69 | return ConstantRange(CR.getUpper(), CR.getLower()); | |||
70 | return ConstantRange(W); | |||
71 | case CmpInst::ICMP_ULT: { | |||
72 | APInt UMax(CR.getUnsignedMax()); | |||
73 | if (UMax.isMinValue()) | |||
74 | return ConstantRange(W, /* empty */ false); | |||
75 | return ConstantRange(APInt::getMinValue(W), std::move(UMax)); | |||
76 | } | |||
77 | case CmpInst::ICMP_SLT: { | |||
78 | APInt SMax(CR.getSignedMax()); | |||
79 | if (SMax.isMinSignedValue()) | |||
80 | return ConstantRange(W, /* empty */ false); | |||
81 | return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax)); | |||
82 | } | |||
83 | case CmpInst::ICMP_ULE: { | |||
84 | APInt UMax(CR.getUnsignedMax()); | |||
85 | if (UMax.isMaxValue()) | |||
86 | return ConstantRange(W); | |||
87 | return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1); | |||
88 | } | |||
89 | case CmpInst::ICMP_SLE: { | |||
90 | APInt SMax(CR.getSignedMax()); | |||
91 | if (SMax.isMaxSignedValue()) | |||
92 | return ConstantRange(W); | |||
93 | return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1); | |||
94 | } | |||
95 | case CmpInst::ICMP_UGT: { | |||
96 | APInt UMin(CR.getUnsignedMin()); | |||
97 | if (UMin.isMaxValue()) | |||
98 | return ConstantRange(W, /* empty */ false); | |||
99 | return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W)); | |||
100 | } | |||
101 | case CmpInst::ICMP_SGT: { | |||
102 | APInt SMin(CR.getSignedMin()); | |||
103 | if (SMin.isMaxSignedValue()) | |||
104 | return ConstantRange(W, /* empty */ false); | |||
105 | return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W)); | |||
106 | } | |||
107 | case CmpInst::ICMP_UGE: { | |||
108 | APInt UMin(CR.getUnsignedMin()); | |||
109 | if (UMin.isMinValue()) | |||
110 | return ConstantRange(W); | |||
111 | return ConstantRange(std::move(UMin), APInt::getNullValue(W)); | |||
112 | } | |||
113 | case CmpInst::ICMP_SGE: { | |||
114 | APInt SMin(CR.getSignedMin()); | |||
115 | if (SMin.isMinSignedValue()) | |||
116 | return ConstantRange(W); | |||
117 | return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W)); | |||
118 | } | |||
119 | } | |||
120 | } | |||
121 | ||||
122 | ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, | |||
123 | const ConstantRange &CR) { | |||
124 | // Follows from De-Morgan's laws: | |||
125 | // | |||
126 | // ~(~A union ~B) == A intersect B. | |||
127 | // | |||
128 | return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) | |||
129 | .inverse(); | |||
130 | } | |||
131 | ||||
132 | ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred, | |||
133 | const APInt &C) { | |||
134 | // Computes the exact range that is equal to both the constant ranges returned | |||
135 | // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true | |||
136 | // when RHS is a singleton such as an APInt and so the assert is valid. | |||
137 | // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion | |||
138 | // returns [0,4) but makeSatisfyICmpRegion returns [0,2). | |||
139 | // | |||
140 | assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C))(static_cast <bool> (makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion (Pred, C)) ? void (0) : __assert_fail ("makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C)" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 140, __extension__ __PRETTY_FUNCTION__)); | |||
141 | return makeAllowedICmpRegion(Pred, C); | |||
142 | } | |||
143 | ||||
144 | bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, | |||
145 | APInt &RHS) const { | |||
146 | bool Success = false; | |||
147 | ||||
148 | if (isFullSet() || isEmptySet()) { | |||
149 | Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE; | |||
150 | RHS = APInt(getBitWidth(), 0); | |||
151 | Success = true; | |||
152 | } else if (auto *OnlyElt = getSingleElement()) { | |||
153 | Pred = CmpInst::ICMP_EQ; | |||
154 | RHS = *OnlyElt; | |||
155 | Success = true; | |||
156 | } else if (auto *OnlyMissingElt = getSingleMissingElement()) { | |||
157 | Pred = CmpInst::ICMP_NE; | |||
158 | RHS = *OnlyMissingElt; | |||
159 | Success = true; | |||
160 | } else if (getLower().isMinSignedValue() || getLower().isMinValue()) { | |||
161 | Pred = | |||
162 | getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; | |||
163 | RHS = getUpper(); | |||
164 | Success = true; | |||
165 | } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) { | |||
166 | Pred = | |||
167 | getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE; | |||
168 | RHS = getLower(); | |||
169 | Success = true; | |||
170 | } | |||
171 | ||||
172 | assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&(static_cast <bool> ((!Success || ConstantRange::makeExactICmpRegion (Pred, RHS) == *this) && "Bad result!") ? void (0) : __assert_fail ("(!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) && \"Bad result!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 173, __extension__ __PRETTY_FUNCTION__)) | |||
173 | "Bad result!")(static_cast <bool> ((!Success || ConstantRange::makeExactICmpRegion (Pred, RHS) == *this) && "Bad result!") ? void (0) : __assert_fail ("(!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) && \"Bad result!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 173, __extension__ __PRETTY_FUNCTION__)); | |||
174 | ||||
175 | return Success; | |||
176 | } | |||
177 | ||||
178 | ConstantRange | |||
179 | ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, | |||
180 | const ConstantRange &Other, | |||
181 | unsigned NoWrapKind) { | |||
182 | using OBO = OverflowingBinaryOperator; | |||
183 | ||||
184 | // Computes the intersection of CR0 and CR1. It is different from | |||
185 | // intersectWith in that the ConstantRange returned will only contain elements | |||
186 | // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or | |||
187 | // not, of both X and Y). | |||
188 | auto SubsetIntersect = | |||
189 | [](const ConstantRange &CR0, const ConstantRange &CR1) { | |||
190 | return CR0.inverse().unionWith(CR1.inverse()).inverse(); | |||
191 | }; | |||
192 | ||||
193 | assert(BinOp >= Instruction::BinaryOpsBegin &&(static_cast <bool> (BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && "Binary operators only!" ) ? void (0) : __assert_fail ("BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && \"Binary operators only!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 194, __extension__ __PRETTY_FUNCTION__)) | |||
194 | BinOp < Instruction::BinaryOpsEnd && "Binary operators only!")(static_cast <bool> (BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && "Binary operators only!" ) ? void (0) : __assert_fail ("BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && \"Binary operators only!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 194, __extension__ __PRETTY_FUNCTION__)); | |||
195 | ||||
196 | assert((NoWrapKind == OBO::NoSignedWrap ||(static_cast <bool> ((NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && "NoWrapKind invalid!") ? void (0) : __assert_fail ("(NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && \"NoWrapKind invalid!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 199, __extension__ __PRETTY_FUNCTION__)) | |||
197 | NoWrapKind == OBO::NoUnsignedWrap ||(static_cast <bool> ((NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && "NoWrapKind invalid!") ? void (0) : __assert_fail ("(NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && \"NoWrapKind invalid!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 199, __extension__ __PRETTY_FUNCTION__)) | |||
198 | NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&(static_cast <bool> ((NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && "NoWrapKind invalid!") ? void (0) : __assert_fail ("(NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && \"NoWrapKind invalid!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 199, __extension__ __PRETTY_FUNCTION__)) | |||
199 | "NoWrapKind invalid!")(static_cast <bool> ((NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && "NoWrapKind invalid!") ? void (0) : __assert_fail ("(NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap || NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && \"NoWrapKind invalid!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 199, __extension__ __PRETTY_FUNCTION__)); | |||
200 | ||||
201 | unsigned BitWidth = Other.getBitWidth(); | |||
202 | ConstantRange Result(BitWidth); | |||
203 | ||||
204 | switch (BinOp) { | |||
205 | default: | |||
206 | // Conservative answer: empty set | |||
207 | return ConstantRange(BitWidth, false); | |||
208 | ||||
209 | case Instruction::Add: | |||
210 | if (auto *C = Other.getSingleElement()) | |||
211 | if (C->isNullValue()) | |||
212 | // Full set: nothing signed / unsigned wraps when added to 0. | |||
213 | return ConstantRange(BitWidth); | |||
214 | if (NoWrapKind & OBO::NoUnsignedWrap) | |||
215 | Result = | |||
216 | SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth), | |||
217 | -Other.getUnsignedMax())); | |||
218 | if (NoWrapKind & OBO::NoSignedWrap) { | |||
219 | const APInt &SignedMin = Other.getSignedMin(); | |||
220 | const APInt &SignedMax = Other.getSignedMax(); | |||
221 | if (SignedMax.isStrictlyPositive()) | |||
222 | Result = SubsetIntersect( | |||
223 | Result, | |||
224 | ConstantRange(APInt::getSignedMinValue(BitWidth), | |||
225 | APInt::getSignedMinValue(BitWidth) - SignedMax)); | |||
226 | if (SignedMin.isNegative()) | |||
227 | Result = SubsetIntersect( | |||
228 | Result, | |||
229 | ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin, | |||
230 | APInt::getSignedMinValue(BitWidth))); | |||
231 | } | |||
232 | return Result; | |||
233 | ||||
234 | case Instruction::Sub: | |||
235 | if (auto *C = Other.getSingleElement()) | |||
236 | if (C->isNullValue()) | |||
237 | // Full set: nothing signed / unsigned wraps when subtracting 0. | |||
238 | return ConstantRange(BitWidth); | |||
239 | if (NoWrapKind & OBO::NoUnsignedWrap) | |||
240 | Result = | |||
241 | SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(), | |||
242 | APInt::getMinValue(BitWidth))); | |||
243 | if (NoWrapKind & OBO::NoSignedWrap) { | |||
244 | const APInt &SignedMin = Other.getSignedMin(); | |||
245 | const APInt &SignedMax = Other.getSignedMax(); | |||
246 | if (SignedMax.isStrictlyPositive()) | |||
247 | Result = SubsetIntersect( | |||
248 | Result, | |||
249 | ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax, | |||
250 | APInt::getSignedMinValue(BitWidth))); | |||
251 | if (SignedMin.isNegative()) | |||
252 | Result = SubsetIntersect( | |||
253 | Result, | |||
254 | ConstantRange(APInt::getSignedMinValue(BitWidth), | |||
255 | APInt::getSignedMinValue(BitWidth) + SignedMin)); | |||
256 | } | |||
257 | return Result; | |||
258 | } | |||
259 | } | |||
260 | ||||
261 | bool ConstantRange::isFullSet() const { | |||
262 | return Lower == Upper && Lower.isMaxValue(); | |||
263 | } | |||
264 | ||||
265 | bool ConstantRange::isEmptySet() const { | |||
266 | return Lower == Upper && Lower.isMinValue(); | |||
267 | } | |||
268 | ||||
269 | bool ConstantRange::isWrappedSet() const { | |||
270 | return Lower.ugt(Upper); | |||
271 | } | |||
272 | ||||
273 | bool ConstantRange::isSignWrappedSet() const { | |||
274 | return contains(APInt::getSignedMaxValue(getBitWidth())) && | |||
275 | contains(APInt::getSignedMinValue(getBitWidth())); | |||
276 | } | |||
277 | ||||
278 | APInt ConstantRange::getSetSize() const { | |||
279 | if (isFullSet()) | |||
280 | return APInt::getOneBitSet(getBitWidth()+1, getBitWidth()); | |||
281 | ||||
282 | // This is also correct for wrapped sets. | |||
283 | return (Upper - Lower).zext(getBitWidth()+1); | |||
284 | } | |||
285 | ||||
286 | bool | |||
287 | ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const { | |||
288 | assert(getBitWidth() == Other.getBitWidth())(static_cast <bool> (getBitWidth() == Other.getBitWidth ()) ? void (0) : __assert_fail ("getBitWidth() == Other.getBitWidth()" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 288, __extension__ __PRETTY_FUNCTION__)); | |||
289 | if (isFullSet()) | |||
290 | return false; | |||
291 | if (Other.isFullSet()) | |||
292 | return true; | |||
293 | return (Upper - Lower).ult(Other.Upper - Other.Lower); | |||
294 | } | |||
295 | ||||
296 | bool | |||
297 | ConstantRange::isSizeLargerThan(uint64_t MaxSize) const { | |||
298 | assert(MaxSize && "MaxSize can't be 0.")(static_cast <bool> (MaxSize && "MaxSize can't be 0." ) ? void (0) : __assert_fail ("MaxSize && \"MaxSize can't be 0.\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 298, __extension__ __PRETTY_FUNCTION__)); | |||
299 | // If this a full set, we need special handling to avoid needing an extra bit | |||
300 | // to represent the size. | |||
301 | if (isFullSet()) | |||
302 | return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1); | |||
303 | ||||
304 | return (Upper - Lower).ugt(MaxSize); | |||
305 | } | |||
306 | ||||
307 | APInt ConstantRange::getUnsignedMax() const { | |||
308 | if (isFullSet() || isWrappedSet()) | |||
309 | return APInt::getMaxValue(getBitWidth()); | |||
310 | return getUpper() - 1; | |||
311 | } | |||
312 | ||||
313 | APInt ConstantRange::getUnsignedMin() const { | |||
314 | if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue())) | |||
315 | return APInt::getMinValue(getBitWidth()); | |||
316 | return getLower(); | |||
317 | } | |||
318 | ||||
319 | APInt ConstantRange::getSignedMax() const { | |||
320 | if (isFullSet() || Lower.sgt(Upper)) | |||
321 | return APInt::getSignedMaxValue(getBitWidth()); | |||
322 | return getUpper() - 1; | |||
323 | } | |||
324 | ||||
325 | APInt ConstantRange::getSignedMin() const { | |||
326 | if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue())) | |||
327 | return APInt::getSignedMinValue(getBitWidth()); | |||
328 | return getLower(); | |||
329 | } | |||
330 | ||||
331 | bool ConstantRange::contains(const APInt &V) const { | |||
332 | if (Lower == Upper) | |||
333 | return isFullSet(); | |||
334 | ||||
335 | if (!isWrappedSet()) | |||
336 | return Lower.ule(V) && V.ult(Upper); | |||
337 | return Lower.ule(V) || V.ult(Upper); | |||
338 | } | |||
339 | ||||
340 | bool ConstantRange::contains(const ConstantRange &Other) const { | |||
341 | if (isFullSet() || Other.isEmptySet()) return true; | |||
342 | if (isEmptySet() || Other.isFullSet()) return false; | |||
343 | ||||
344 | if (!isWrappedSet()) { | |||
345 | if (Other.isWrappedSet()) | |||
346 | return false; | |||
347 | ||||
348 | return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); | |||
349 | } | |||
350 | ||||
351 | if (!Other.isWrappedSet()) | |||
352 | return Other.getUpper().ule(Upper) || | |||
353 | Lower.ule(Other.getLower()); | |||
354 | ||||
355 | return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); | |||
356 | } | |||
357 | ||||
358 | ConstantRange ConstantRange::subtract(const APInt &Val) const { | |||
359 | assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width")(static_cast <bool> (Val.getBitWidth() == getBitWidth() && "Wrong bit width") ? void (0) : __assert_fail ("Val.getBitWidth() == getBitWidth() && \"Wrong bit width\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 359, __extension__ __PRETTY_FUNCTION__)); | |||
360 | // If the set is empty or full, don't modify the endpoints. | |||
361 | if (Lower == Upper) | |||
362 | return *this; | |||
363 | return ConstantRange(Lower - Val, Upper - Val); | |||
364 | } | |||
365 | ||||
366 | ConstantRange ConstantRange::difference(const ConstantRange &CR) const { | |||
367 | return intersectWith(CR.inverse()); | |||
368 | } | |||
369 | ||||
370 | ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { | |||
371 | assert(getBitWidth() == CR.getBitWidth() &&(static_cast <bool> (getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!") ? void (0) : __assert_fail ("getBitWidth() == CR.getBitWidth() && \"ConstantRange types don't agree!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 372, __extension__ __PRETTY_FUNCTION__)) | |||
372 | "ConstantRange types don't agree!")(static_cast <bool> (getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!") ? void (0) : __assert_fail ("getBitWidth() == CR.getBitWidth() && \"ConstantRange types don't agree!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 372, __extension__ __PRETTY_FUNCTION__)); | |||
373 | ||||
374 | // Handle common cases. | |||
375 | if ( isEmptySet() || CR.isFullSet()) return *this; | |||
376 | if (CR.isEmptySet() || isFullSet()) return CR; | |||
377 | ||||
378 | if (!isWrappedSet() && CR.isWrappedSet()) | |||
379 | return CR.intersectWith(*this); | |||
380 | ||||
381 | if (!isWrappedSet() && !CR.isWrappedSet()) { | |||
382 | if (Lower.ult(CR.Lower)) { | |||
383 | if (Upper.ule(CR.Lower)) | |||
384 | return ConstantRange(getBitWidth(), false); | |||
385 | ||||
386 | if (Upper.ult(CR.Upper)) | |||
387 | return ConstantRange(CR.Lower, Upper); | |||
388 | ||||
389 | return CR; | |||
390 | } | |||
391 | if (Upper.ult(CR.Upper)) | |||
392 | return *this; | |||
393 | ||||
394 | if (Lower.ult(CR.Upper)) | |||
395 | return ConstantRange(Lower, CR.Upper); | |||
396 | ||||
397 | return ConstantRange(getBitWidth(), false); | |||
398 | } | |||
399 | ||||
400 | if (isWrappedSet() && !CR.isWrappedSet()) { | |||
401 | if (CR.Lower.ult(Upper)) { | |||
402 | if (CR.Upper.ult(Upper)) | |||
403 | return CR; | |||
404 | ||||
405 | if (CR.Upper.ule(Lower)) | |||
406 | return ConstantRange(CR.Lower, Upper); | |||
407 | ||||
408 | if (isSizeStrictlySmallerThan(CR)) | |||
409 | return *this; | |||
410 | return CR; | |||
411 | } | |||
412 | if (CR.Lower.ult(Lower)) { | |||
413 | if (CR.Upper.ule(Lower)) | |||
414 | return ConstantRange(getBitWidth(), false); | |||
415 | ||||
416 | return ConstantRange(Lower, CR.Upper); | |||
417 | } | |||
418 | return CR; | |||
419 | } | |||
420 | ||||
421 | if (CR.Upper.ult(Upper)) { | |||
422 | if (CR.Lower.ult(Upper)) { | |||
423 | if (isSizeStrictlySmallerThan(CR)) | |||
424 | return *this; | |||
425 | return CR; | |||
426 | } | |||
427 | ||||
428 | if (CR.Lower.ult(Lower)) | |||
429 | return ConstantRange(Lower, CR.Upper); | |||
430 | ||||
431 | return CR; | |||
432 | } | |||
433 | if (CR.Upper.ule(Lower)) { | |||
434 | if (CR.Lower.ult(Lower)) | |||
435 | return *this; | |||
436 | ||||
437 | return ConstantRange(CR.Lower, Upper); | |||
438 | } | |||
439 | if (isSizeStrictlySmallerThan(CR)) | |||
440 | return *this; | |||
441 | return CR; | |||
442 | } | |||
443 | ||||
444 | ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { | |||
445 | assert(getBitWidth() == CR.getBitWidth() &&(static_cast <bool> (getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!") ? void (0) : __assert_fail ("getBitWidth() == CR.getBitWidth() && \"ConstantRange types don't agree!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 446, __extension__ __PRETTY_FUNCTION__)) | |||
446 | "ConstantRange types don't agree!")(static_cast <bool> (getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!") ? void (0) : __assert_fail ("getBitWidth() == CR.getBitWidth() && \"ConstantRange types don't agree!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 446, __extension__ __PRETTY_FUNCTION__)); | |||
447 | ||||
448 | if ( isFullSet() || CR.isEmptySet()) return *this; | |||
449 | if (CR.isFullSet() || isEmptySet()) return CR; | |||
450 | ||||
451 | if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); | |||
452 | ||||
453 | if (!isWrappedSet() && !CR.isWrappedSet()) { | |||
454 | if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { | |||
455 | // If the two ranges are disjoint, find the smaller gap and bridge it. | |||
456 | APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; | |||
457 | if (d1.ult(d2)) | |||
458 | return ConstantRange(Lower, CR.Upper); | |||
459 | return ConstantRange(CR.Lower, Upper); | |||
460 | } | |||
461 | ||||
462 | APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; | |||
463 | APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper; | |||
464 | ||||
465 | if (L.isNullValue() && U.isNullValue()) | |||
466 | return ConstantRange(getBitWidth()); | |||
467 | ||||
468 | return ConstantRange(std::move(L), std::move(U)); | |||
469 | } | |||
470 | ||||
471 | if (!CR.isWrappedSet()) { | |||
472 | // ------U L----- and ------U L----- : this | |||
473 | // L--U L--U : CR | |||
474 | if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) | |||
475 | return *this; | |||
476 | ||||
477 | // ------U L----- : this | |||
478 | // L---------U : CR | |||
479 | if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) | |||
480 | return ConstantRange(getBitWidth()); | |||
481 | ||||
482 | // ----U L---- : this | |||
483 | // L---U : CR | |||
484 | // <d1> <d2> | |||
485 | if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { | |||
486 | APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; | |||
487 | if (d1.ult(d2)) | |||
488 | return ConstantRange(Lower, CR.Upper); | |||
489 | return ConstantRange(CR.Lower, Upper); | |||
490 | } | |||
491 | ||||
492 | // ----U L----- : this | |||
493 | // L----U : CR | |||
494 | if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) | |||
495 | return ConstantRange(CR.Lower, Upper); | |||
496 | ||||
497 | // ------U L---- : this | |||
498 | // L-----U : CR | |||
499 | assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&(static_cast <bool> (CR.Lower.ult(Upper) && CR. Upper.ult(Lower) && "ConstantRange::unionWith missed a case with one range wrapped" ) ? void (0) : __assert_fail ("CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && \"ConstantRange::unionWith missed a case with one range wrapped\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 500, __extension__ __PRETTY_FUNCTION__)) | |||
500 | "ConstantRange::unionWith missed a case with one range wrapped")(static_cast <bool> (CR.Lower.ult(Upper) && CR. Upper.ult(Lower) && "ConstantRange::unionWith missed a case with one range wrapped" ) ? void (0) : __assert_fail ("CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && \"ConstantRange::unionWith missed a case with one range wrapped\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 500, __extension__ __PRETTY_FUNCTION__)); | |||
501 | return ConstantRange(Lower, CR.Upper); | |||
502 | } | |||
503 | ||||
504 | // ------U L---- and ------U L---- : this | |||
505 | // -U L----------- and ------------U L : CR | |||
506 | if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) | |||
507 | return ConstantRange(getBitWidth()); | |||
508 | ||||
509 | APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; | |||
510 | APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper; | |||
511 | ||||
512 | return ConstantRange(std::move(L), std::move(U)); | |||
513 | } | |||
514 | ||||
515 | ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, | |||
516 | uint32_t ResultBitWidth) const { | |||
517 | switch (CastOp) { | |||
518 | default: | |||
519 | llvm_unreachable("unsupported cast type")::llvm::llvm_unreachable_internal("unsupported cast type", "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 519); | |||
520 | case Instruction::Trunc: | |||
521 | return truncate(ResultBitWidth); | |||
522 | case Instruction::SExt: | |||
523 | return signExtend(ResultBitWidth); | |||
524 | case Instruction::ZExt: | |||
525 | return zeroExtend(ResultBitWidth); | |||
526 | case Instruction::BitCast: | |||
527 | return *this; | |||
528 | case Instruction::FPToUI: | |||
529 | case Instruction::FPToSI: | |||
530 | if (getBitWidth() == ResultBitWidth) | |||
531 | return *this; | |||
532 | else | |||
533 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
534 | case Instruction::UIToFP: { | |||
535 | // TODO: use input range if available | |||
536 | auto BW = getBitWidth(); | |||
537 | APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth); | |||
538 | APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth); | |||
539 | return ConstantRange(std::move(Min), std::move(Max)); | |||
540 | } | |||
541 | case Instruction::SIToFP: { | |||
542 | // TODO: use input range if available | |||
543 | auto BW = getBitWidth(); | |||
544 | APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth); | |||
545 | APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth); | |||
546 | return ConstantRange(std::move(SMin), std::move(SMax)); | |||
547 | } | |||
548 | case Instruction::FPTrunc: | |||
549 | case Instruction::FPExt: | |||
550 | case Instruction::IntToPtr: | |||
551 | case Instruction::PtrToInt: | |||
552 | case Instruction::AddrSpaceCast: | |||
553 | // Conservatively return full set. | |||
554 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
555 | }; | |||
556 | } | |||
557 | ||||
558 | ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { | |||
559 | if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); | |||
560 | ||||
561 | unsigned SrcTySize = getBitWidth(); | |||
562 | assert(SrcTySize < DstTySize && "Not a value extension")(static_cast <bool> (SrcTySize < DstTySize && "Not a value extension") ? void (0) : __assert_fail ("SrcTySize < DstTySize && \"Not a value extension\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 562, __extension__ __PRETTY_FUNCTION__)); | |||
563 | if (isFullSet() || isWrappedSet()) { | |||
564 | // Change into [0, 1 << src bit width) | |||
565 | APInt LowerExt(DstTySize, 0); | |||
566 | if (!Upper) // special case: [X, 0) -- not really wrapping around | |||
567 | LowerExt = Lower.zext(DstTySize); | |||
568 | return ConstantRange(std::move(LowerExt), | |||
569 | APInt::getOneBitSet(DstTySize, SrcTySize)); | |||
570 | } | |||
571 | ||||
572 | return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); | |||
573 | } | |||
574 | ||||
575 | ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { | |||
576 | if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); | |||
577 | ||||
578 | unsigned SrcTySize = getBitWidth(); | |||
579 | assert(SrcTySize < DstTySize && "Not a value extension")(static_cast <bool> (SrcTySize < DstTySize && "Not a value extension") ? void (0) : __assert_fail ("SrcTySize < DstTySize && \"Not a value extension\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 579, __extension__ __PRETTY_FUNCTION__)); | |||
580 | ||||
581 | // special case: [X, INT_MIN) -- not really wrapping around | |||
582 | if (Upper.isMinSignedValue()) | |||
583 | return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); | |||
584 | ||||
585 | if (isFullSet() || isSignWrappedSet()) { | |||
586 | return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), | |||
587 | APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); | |||
588 | } | |||
589 | ||||
590 | return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); | |||
591 | } | |||
592 | ||||
593 | ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { | |||
594 | assert(getBitWidth() > DstTySize && "Not a value truncation")(static_cast <bool> (getBitWidth() > DstTySize && "Not a value truncation") ? void (0) : __assert_fail ("getBitWidth() > DstTySize && \"Not a value truncation\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 594, __extension__ __PRETTY_FUNCTION__)); | |||
595 | if (isEmptySet()) | |||
596 | return ConstantRange(DstTySize, /*isFullSet=*/false); | |||
597 | if (isFullSet()) | |||
598 | return ConstantRange(DstTySize, /*isFullSet=*/true); | |||
599 | ||||
600 | APInt LowerDiv(Lower), UpperDiv(Upper); | |||
601 | ConstantRange Union(DstTySize, /*isFullSet=*/false); | |||
602 | ||||
603 | // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] | |||
604 | // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and | |||
605 | // then we do the union with [MaxValue, Upper) | |||
606 | if (isWrappedSet()) { | |||
607 | // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole | |||
608 | // truncated range. | |||
609 | if (Upper.getActiveBits() > DstTySize || | |||
610 | Upper.countTrailingOnes() == DstTySize) | |||
611 | return ConstantRange(DstTySize, /*isFullSet=*/true); | |||
612 | ||||
613 | Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); | |||
614 | UpperDiv.setAllBits(); | |||
615 | ||||
616 | // Union covers the MaxValue case, so return if the remaining range is just | |||
617 | // MaxValue(DstTy). | |||
618 | if (LowerDiv == UpperDiv) | |||
619 | return Union; | |||
620 | } | |||
621 | ||||
622 | // Chop off the most significant bits that are past the destination bitwidth. | |||
623 | if (LowerDiv.getActiveBits() > DstTySize) { | |||
624 | // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv. | |||
625 | APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize); | |||
626 | LowerDiv -= Adjust; | |||
627 | UpperDiv -= Adjust; | |||
628 | } | |||
629 | ||||
630 | unsigned UpperDivWidth = UpperDiv.getActiveBits(); | |||
631 | if (UpperDivWidth <= DstTySize) | |||
632 | return ConstantRange(LowerDiv.trunc(DstTySize), | |||
633 | UpperDiv.trunc(DstTySize)).unionWith(Union); | |||
634 | ||||
635 | // The truncated value wraps around. Check if we can do better than fullset. | |||
636 | if (UpperDivWidth == DstTySize + 1) { | |||
637 | // Clear the MSB so that UpperDiv wraps around. | |||
638 | UpperDiv.clearBit(DstTySize); | |||
639 | if (UpperDiv.ult(LowerDiv)) | |||
640 | return ConstantRange(LowerDiv.trunc(DstTySize), | |||
641 | UpperDiv.trunc(DstTySize)).unionWith(Union); | |||
642 | } | |||
643 | ||||
644 | return ConstantRange(DstTySize, /*isFullSet=*/true); | |||
645 | } | |||
646 | ||||
647 | ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { | |||
648 | unsigned SrcTySize = getBitWidth(); | |||
649 | if (SrcTySize > DstTySize) | |||
650 | return truncate(DstTySize); | |||
651 | if (SrcTySize < DstTySize) | |||
652 | return zeroExtend(DstTySize); | |||
653 | return *this; | |||
654 | } | |||
655 | ||||
656 | ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { | |||
657 | unsigned SrcTySize = getBitWidth(); | |||
658 | if (SrcTySize > DstTySize) | |||
659 | return truncate(DstTySize); | |||
660 | if (SrcTySize < DstTySize) | |||
661 | return signExtend(DstTySize); | |||
662 | return *this; | |||
663 | } | |||
664 | ||||
665 | ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, | |||
666 | const ConstantRange &Other) const { | |||
667 | assert(BinOp >= Instruction::BinaryOpsBegin &&(static_cast <bool> (BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && "Binary operators only!" ) ? void (0) : __assert_fail ("BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && \"Binary operators only!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 668, __extension__ __PRETTY_FUNCTION__)) | |||
668 | BinOp < Instruction::BinaryOpsEnd && "Binary operators only!")(static_cast <bool> (BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && "Binary operators only!" ) ? void (0) : __assert_fail ("BinOp >= Instruction::BinaryOpsBegin && BinOp < Instruction::BinaryOpsEnd && \"Binary operators only!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 668, __extension__ __PRETTY_FUNCTION__)); | |||
669 | ||||
670 | switch (BinOp) { | |||
671 | case Instruction::Add: | |||
672 | return add(Other); | |||
673 | case Instruction::Sub: | |||
674 | return sub(Other); | |||
675 | case Instruction::Mul: | |||
676 | return multiply(Other); | |||
677 | case Instruction::UDiv: | |||
678 | return udiv(Other); | |||
679 | case Instruction::Shl: | |||
680 | return shl(Other); | |||
681 | case Instruction::LShr: | |||
682 | return lshr(Other); | |||
683 | case Instruction::AShr: | |||
684 | return ashr(Other); | |||
685 | case Instruction::And: | |||
686 | return binaryAnd(Other); | |||
687 | case Instruction::Or: | |||
688 | return binaryOr(Other); | |||
689 | // Note: floating point operations applied to abstract ranges are just | |||
690 | // ideal integer operations with a lossy representation | |||
691 | case Instruction::FAdd: | |||
692 | return add(Other); | |||
693 | case Instruction::FSub: | |||
694 | return sub(Other); | |||
695 | case Instruction::FMul: | |||
696 | return multiply(Other); | |||
697 | default: | |||
698 | // Conservatively return full set. | |||
699 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
700 | } | |||
701 | } | |||
702 | ||||
703 | ConstantRange | |||
704 | ConstantRange::add(const ConstantRange &Other) const { | |||
705 | if (isEmptySet() || Other.isEmptySet()) | |||
706 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
707 | if (isFullSet() || Other.isFullSet()) | |||
708 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
709 | ||||
710 | APInt NewLower = getLower() + Other.getLower(); | |||
711 | APInt NewUpper = getUpper() + Other.getUpper() - 1; | |||
712 | if (NewLower == NewUpper) | |||
713 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
714 | ||||
715 | ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); | |||
716 | if (X.isSizeStrictlySmallerThan(*this) || | |||
717 | X.isSizeStrictlySmallerThan(Other)) | |||
718 | // We've wrapped, therefore, full set. | |||
719 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
720 | return X; | |||
721 | } | |||
722 | ||||
723 | ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const { | |||
724 | // Calculate the subset of this range such that "X + Other" is | |||
725 | // guaranteed not to wrap (overflow) for all X in this subset. | |||
726 | // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are | |||
727 | // passing a single element range. | |||
728 | auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add, | |||
729 | ConstantRange(Other), | |||
730 | OverflowingBinaryOperator::NoSignedWrap); | |||
731 | auto NSWConstrainedRange = intersectWith(NSWRange); | |||
732 | ||||
733 | return NSWConstrainedRange.add(ConstantRange(Other)); | |||
734 | } | |||
735 | ||||
736 | ConstantRange | |||
737 | ConstantRange::sub(const ConstantRange &Other) const { | |||
738 | if (isEmptySet() || Other.isEmptySet()) | |||
739 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
740 | if (isFullSet() || Other.isFullSet()) | |||
741 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
742 | ||||
743 | APInt NewLower = getLower() - Other.getUpper() + 1; | |||
744 | APInt NewUpper = getUpper() - Other.getLower(); | |||
745 | if (NewLower == NewUpper) | |||
746 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
747 | ||||
748 | ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); | |||
749 | if (X.isSizeStrictlySmallerThan(*this) || | |||
750 | X.isSizeStrictlySmallerThan(Other)) | |||
751 | // We've wrapped, therefore, full set. | |||
752 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
753 | return X; | |||
754 | } | |||
755 | ||||
756 | ConstantRange | |||
757 | ConstantRange::multiply(const ConstantRange &Other) const { | |||
758 | // TODO: If either operand is a single element and the multiply is known to | |||
759 | // be non-wrapping, round the result min and max value to the appropriate | |||
760 | // multiple of that element. If wrapping is possible, at least adjust the | |||
761 | // range according to the greatest power-of-two factor of the single element. | |||
762 | ||||
763 | if (isEmptySet() || Other.isEmptySet()) | |||
764 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
765 | ||||
766 | // Multiplication is signedness-independent. However different ranges can be | |||
767 | // obtained depending on how the input ranges are treated. These different | |||
768 | // ranges are all conservatively correct, but one might be better than the | |||
769 | // other. We calculate two ranges; one treating the inputs as unsigned | |||
770 | // and the other signed, then return the smallest of these ranges. | |||
771 | ||||
772 | // Unsigned range first. | |||
773 | APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); | |||
774 | APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); | |||
775 | APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); | |||
776 | APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); | |||
777 | ||||
778 | ConstantRange Result_zext = ConstantRange(this_min * Other_min, | |||
779 | this_max * Other_max + 1); | |||
780 | ConstantRange UR = Result_zext.truncate(getBitWidth()); | |||
781 | ||||
782 | // If the unsigned range doesn't wrap, and isn't negative then it's a range | |||
783 | // from one positive number to another which is as good as we can generate. | |||
784 | // In this case, skip the extra work of generating signed ranges which aren't | |||
785 | // going to be better than this range. | |||
786 | if (!UR.isWrappedSet() && | |||
787 | (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue())) | |||
788 | return UR; | |||
789 | ||||
790 | // Now the signed range. Because we could be dealing with negative numbers | |||
791 | // here, the lower bound is the smallest of the cartesian product of the | |||
792 | // lower and upper ranges; for example: | |||
793 | // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. | |||
794 | // Similarly for the upper bound, swapping min for max. | |||
795 | ||||
796 | this_min = getSignedMin().sext(getBitWidth() * 2); | |||
797 | this_max = getSignedMax().sext(getBitWidth() * 2); | |||
798 | Other_min = Other.getSignedMin().sext(getBitWidth() * 2); | |||
799 | Other_max = Other.getSignedMax().sext(getBitWidth() * 2); | |||
800 | ||||
801 | auto L = {this_min * Other_min, this_min * Other_max, | |||
802 | this_max * Other_min, this_max * Other_max}; | |||
803 | auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; | |||
804 | ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1); | |||
805 | ConstantRange SR = Result_sext.truncate(getBitWidth()); | |||
806 | ||||
807 | return UR.isSizeStrictlySmallerThan(SR) ? UR : SR; | |||
808 | } | |||
809 | ||||
810 | ConstantRange | |||
811 | ConstantRange::smax(const ConstantRange &Other) const { | |||
812 | // X smax Y is: range(smax(X_smin, Y_smin), | |||
813 | // smax(X_smax, Y_smax)) | |||
814 | if (isEmptySet() || Other.isEmptySet()) | |||
815 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
816 | APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); | |||
817 | APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; | |||
818 | if (NewU == NewL) | |||
819 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
820 | return ConstantRange(std::move(NewL), std::move(NewU)); | |||
821 | } | |||
822 | ||||
823 | ConstantRange | |||
824 | ConstantRange::umax(const ConstantRange &Other) const { | |||
825 | // X umax Y is: range(umax(X_umin, Y_umin), | |||
826 | // umax(X_umax, Y_umax)) | |||
827 | if (isEmptySet() || Other.isEmptySet()) | |||
828 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
829 | APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); | |||
830 | APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; | |||
831 | if (NewU == NewL) | |||
832 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
833 | return ConstantRange(std::move(NewL), std::move(NewU)); | |||
834 | } | |||
835 | ||||
836 | ConstantRange | |||
837 | ConstantRange::smin(const ConstantRange &Other) const { | |||
838 | // X smin Y is: range(smin(X_smin, Y_smin), | |||
839 | // smin(X_smax, Y_smax)) | |||
840 | if (isEmptySet() || Other.isEmptySet()) | |||
841 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
842 | APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); | |||
843 | APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1; | |||
844 | if (NewU == NewL) | |||
845 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
846 | return ConstantRange(std::move(NewL), std::move(NewU)); | |||
847 | } | |||
848 | ||||
849 | ConstantRange | |||
850 | ConstantRange::umin(const ConstantRange &Other) const { | |||
851 | // X umin Y is: range(umin(X_umin, Y_umin), | |||
852 | // umin(X_umax, Y_umax)) | |||
853 | if (isEmptySet() || Other.isEmptySet()) | |||
854 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
855 | APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); | |||
856 | APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1; | |||
857 | if (NewU == NewL) | |||
858 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
859 | return ConstantRange(std::move(NewL), std::move(NewU)); | |||
860 | } | |||
861 | ||||
862 | ConstantRange | |||
863 | ConstantRange::udiv(const ConstantRange &RHS) const { | |||
864 | if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) | |||
865 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
866 | if (RHS.isFullSet()) | |||
867 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
868 | ||||
869 | APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); | |||
870 | ||||
871 | APInt RHS_umin = RHS.getUnsignedMin(); | |||
872 | if (RHS_umin.isNullValue()) { | |||
873 | // We want the lowest value in RHS excluding zero. Usually that would be 1 | |||
874 | // except for a range in the form of [X, 1) in which case it would be X. | |||
875 | if (RHS.getUpper() == 1) | |||
876 | RHS_umin = RHS.getLower(); | |||
877 | else | |||
878 | RHS_umin = 1; | |||
879 | } | |||
880 | ||||
881 | APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; | |||
882 | ||||
883 | // If the LHS is Full and the RHS is a wrapped interval containing 1 then | |||
884 | // this could occur. | |||
885 | if (Lower == Upper) | |||
886 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
887 | ||||
888 | return ConstantRange(std::move(Lower), std::move(Upper)); | |||
889 | } | |||
890 | ||||
891 | ConstantRange | |||
892 | ConstantRange::binaryAnd(const ConstantRange &Other) const { | |||
893 | if (isEmptySet() || Other.isEmptySet()) | |||
894 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
895 | ||||
896 | // TODO: replace this with something less conservative | |||
897 | ||||
898 | APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); | |||
899 | if (umin.isAllOnesValue()) | |||
900 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
901 | return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1); | |||
902 | } | |||
903 | ||||
904 | ConstantRange | |||
905 | ConstantRange::binaryOr(const ConstantRange &Other) const { | |||
906 | if (isEmptySet() || Other.isEmptySet()) | |||
907 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
908 | ||||
909 | // TODO: replace this with something less conservative | |||
910 | ||||
911 | APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); | |||
912 | if (umax.isNullValue()) | |||
913 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
914 | return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth())); | |||
915 | } | |||
916 | ||||
917 | ConstantRange | |||
918 | ConstantRange::shl(const ConstantRange &Other) const { | |||
919 | if (isEmptySet() || Other.isEmptySet()) | |||
920 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
921 | ||||
922 | APInt max = getUnsignedMax(); | |||
923 | APInt Other_umax = Other.getUnsignedMax(); | |||
924 | ||||
925 | // there's overflow! | |||
926 | if (Other_umax.uge(max.countLeadingZeros())) | |||
927 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
928 | ||||
929 | // FIXME: implement the other tricky cases | |||
930 | ||||
931 | APInt min = getUnsignedMin(); | |||
932 | min <<= Other.getUnsignedMin(); | |||
933 | max <<= Other_umax; | |||
934 | ||||
935 | return ConstantRange(std::move(min), std::move(max) + 1); | |||
936 | } | |||
937 | ||||
938 | ConstantRange | |||
939 | ConstantRange::lshr(const ConstantRange &Other) const { | |||
940 | if (isEmptySet() || Other.isEmptySet()) | |||
941 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
942 | ||||
943 | APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1; | |||
944 | APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); | |||
945 | if (min == max) | |||
946 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
947 | ||||
948 | return ConstantRange(std::move(min), std::move(max)); | |||
949 | } | |||
950 | ||||
951 | ConstantRange | |||
952 | ConstantRange::ashr(const ConstantRange &Other) const { | |||
953 | if (isEmptySet() || Other.isEmptySet()) | |||
954 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
955 | ||||
956 | // May straddle zero, so handle both positive and negative cases. | |||
957 | // 'PosMax' is the upper bound of the result of the ashr | |||
958 | // operation, when Upper of the LHS of ashr is a non-negative. | |||
959 | // number. Since ashr of a non-negative number will result in a | |||
960 | // smaller number, the Upper value of LHS is shifted right with | |||
961 | // the minimum value of 'Other' instead of the maximum value. | |||
962 | APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1; | |||
963 | ||||
964 | // 'PosMin' is the lower bound of the result of the ashr | |||
965 | // operation, when Lower of the LHS is a non-negative number. | |||
966 | // Since ashr of a non-negative number will result in a smaller | |||
967 | // number, the Lower value of LHS is shifted right with the | |||
968 | // maximum value of 'Other'. | |||
969 | APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax()); | |||
970 | ||||
971 | // 'NegMax' is the upper bound of the result of the ashr | |||
972 | // operation, when Upper of the LHS of ashr is a negative number. | |||
973 | // Since 'ashr' of a negative number will result in a bigger | |||
974 | // number, the Upper value of LHS is shifted right with the | |||
975 | // maximum value of 'Other'. | |||
976 | APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1; | |||
977 | ||||
978 | // 'NegMin' is the lower bound of the result of the ashr | |||
979 | // operation, when Lower of the LHS of ashr is a negative number. | |||
980 | // Since 'ashr' of a negative number will result in a bigger | |||
981 | // number, the Lower value of LHS is shifted right with the | |||
982 | // minimum value of 'Other'. | |||
983 | APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin()); | |||
984 | ||||
985 | APInt max, min; | |||
986 | if (getSignedMin().isNonNegative()) { | |||
987 | // Upper and Lower of LHS are non-negative. | |||
988 | min = PosMin; | |||
989 | max = PosMax; | |||
990 | } else if (getSignedMax().isNegative()) { | |||
991 | // Upper and Lower of LHS are negative. | |||
992 | min = NegMin; | |||
993 | max = NegMax; | |||
994 | } else { | |||
995 | // Upper is non-negative and Lower is negative. | |||
996 | min = NegMin; | |||
997 | max = PosMax; | |||
998 | } | |||
999 | if (min == max) | |||
1000 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
1001 | ||||
1002 | return ConstantRange(std::move(min), std::move(max)); | |||
1003 | } | |||
1004 | ||||
1005 | ConstantRange ConstantRange::inverse() const { | |||
1006 | if (isFullSet()) | |||
1007 | return ConstantRange(getBitWidth(), /*isFullSet=*/false); | |||
1008 | if (isEmptySet()) | |||
1009 | return ConstantRange(getBitWidth(), /*isFullSet=*/true); | |||
1010 | return ConstantRange(Upper, Lower); | |||
1011 | } | |||
1012 | ||||
1013 | void ConstantRange::print(raw_ostream &OS) const { | |||
1014 | if (isFullSet()) | |||
1015 | OS << "full-set"; | |||
1016 | else if (isEmptySet()) | |||
1017 | OS << "empty-set"; | |||
1018 | else | |||
1019 | OS << "[" << Lower << "," << Upper << ")"; | |||
1020 | } | |||
1021 | ||||
1022 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
1023 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ConstantRange::dump() const { | |||
1024 | print(dbgs()); | |||
1025 | } | |||
1026 | #endif | |||
1027 | ||||
1028 | ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) { | |||
1029 | const unsigned NumRanges = Ranges.getNumOperands() / 2; | |||
1030 | assert(NumRanges >= 1 && "Must have at least one range!")(static_cast <bool> (NumRanges >= 1 && "Must have at least one range!" ) ? void (0) : __assert_fail ("NumRanges >= 1 && \"Must have at least one range!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 1030, __extension__ __PRETTY_FUNCTION__)); | |||
1031 | assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs")(static_cast <bool> (Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs") ? void (0) : __assert_fail ("Ranges.getNumOperands() % 2 == 0 && \"Must be a sequence of pairs\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/IR/ConstantRange.cpp" , 1031, __extension__ __PRETTY_FUNCTION__)); | |||
1032 | ||||
1033 | auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0)); | |||
1034 | auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1)); | |||
1035 | ||||
1036 | ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue()); | |||
1037 | ||||
1038 | for (unsigned i = 1; i < NumRanges; ++i) { | |||
| ||||
1039 | auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0)); | |||
1040 | auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1)); | |||
1041 | ||||
1042 | // Note: unionWith will potentially create a range that contains values not | |||
1043 | // contained in any of the original N ranges. | |||
1044 | CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue())); | |||
1045 | } | |||
1046 | ||||
1047 | return CR; | |||
1048 | } |
1 | //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===// | |||
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 | /// \file | |||
11 | /// \brief This file implements a class to represent arbitrary precision | |||
12 | /// integral constant values and operations on them. | |||
13 | /// | |||
14 | //===----------------------------------------------------------------------===// | |||
15 | ||||
16 | #ifndef LLVM_ADT_APINT_H | |||
17 | #define LLVM_ADT_APINT_H | |||
18 | ||||
19 | #include "llvm/Support/Compiler.h" | |||
20 | #include "llvm/Support/MathExtras.h" | |||
21 | #include <cassert> | |||
22 | #include <climits> | |||
23 | #include <cstring> | |||
24 | #include <string> | |||
25 | ||||
26 | namespace llvm { | |||
27 | class FoldingSetNodeID; | |||
28 | class StringRef; | |||
29 | class hash_code; | |||
30 | class raw_ostream; | |||
31 | ||||
32 | template <typename T> class SmallVectorImpl; | |||
33 | template <typename T> class ArrayRef; | |||
34 | ||||
35 | class APInt; | |||
36 | ||||
37 | inline APInt operator-(APInt); | |||
38 | ||||
39 | //===----------------------------------------------------------------------===// | |||
40 | // APInt Class | |||
41 | //===----------------------------------------------------------------------===// | |||
42 | ||||
43 | /// \brief Class for arbitrary precision integers. | |||
44 | /// | |||
45 | /// APInt is a functional replacement for common case unsigned integer type like | |||
46 | /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width | |||
47 | /// integer sizes and large integer value types such as 3-bits, 15-bits, or more | |||
48 | /// than 64-bits of precision. APInt provides a variety of arithmetic operators | |||
49 | /// and methods to manipulate integer values of any bit-width. It supports both | |||
50 | /// the typical integer arithmetic and comparison operations as well as bitwise | |||
51 | /// manipulation. | |||
52 | /// | |||
53 | /// The class has several invariants worth noting: | |||
54 | /// * All bit, byte, and word positions are zero-based. | |||
55 | /// * Once the bit width is set, it doesn't change except by the Truncate, | |||
56 | /// SignExtend, or ZeroExtend operations. | |||
57 | /// * All binary operators must be on APInt instances of the same bit width. | |||
58 | /// Attempting to use these operators on instances with different bit | |||
59 | /// widths will yield an assertion. | |||
60 | /// * The value is stored canonically as an unsigned value. For operations | |||
61 | /// where it makes a difference, there are both signed and unsigned variants | |||
62 | /// of the operation. For example, sdiv and udiv. However, because the bit | |||
63 | /// widths must be the same, operations such as Mul and Add produce the same | |||
64 | /// results regardless of whether the values are interpreted as signed or | |||
65 | /// not. | |||
66 | /// * In general, the class tries to follow the style of computation that LLVM | |||
67 | /// uses in its IR. This simplifies its use for LLVM. | |||
68 | /// | |||
69 | class LLVM_NODISCARD[[clang::warn_unused_result]] APInt { | |||
70 | public: | |||
71 | typedef uint64_t WordType; | |||
72 | ||||
73 | /// This enum is used to hold the constants we needed for APInt. | |||
74 | enum : unsigned { | |||
75 | /// Byte size of a word. | |||
76 | APINT_WORD_SIZE = sizeof(WordType), | |||
77 | /// Bits in a word. | |||
78 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8 | |||
79 | }; | |||
80 | ||||
81 | static const WordType WORD_MAX = ~WordType(0); | |||
82 | ||||
83 | private: | |||
84 | /// This union is used to store the integer value. When the | |||
85 | /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. | |||
86 | union { | |||
87 | uint64_t VAL; ///< Used to store the <= 64 bits integer value. | |||
88 | uint64_t *pVal; ///< Used to store the >64 bits integer value. | |||
89 | } U; | |||
90 | ||||
91 | unsigned BitWidth; ///< The number of bits in this APInt. | |||
92 | ||||
93 | friend struct DenseMapAPIntKeyInfo; | |||
94 | ||||
95 | friend class APSInt; | |||
96 | ||||
97 | /// \brief Fast internal constructor | |||
98 | /// | |||
99 | /// This constructor is used only internally for speed of construction of | |||
100 | /// temporaries. It is unsafe for general use so it is not public. | |||
101 | APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { | |||
102 | U.pVal = val; | |||
103 | } | |||
104 | ||||
105 | /// \brief Determine if this APInt just has one word to store value. | |||
106 | /// | |||
107 | /// \returns true if the number of bits <= 64, false otherwise. | |||
108 | bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } | |||
109 | ||||
110 | /// \brief Determine which word a bit is in. | |||
111 | /// | |||
112 | /// \returns the word position for the specified bit position. | |||
113 | static unsigned whichWord(unsigned bitPosition) { | |||
114 | return bitPosition / APINT_BITS_PER_WORD; | |||
115 | } | |||
116 | ||||
117 | /// \brief Determine which bit in a word a bit is in. | |||
118 | /// | |||
119 | /// \returns the bit position in a word for the specified bit position | |||
120 | /// in the APInt. | |||
121 | static unsigned whichBit(unsigned bitPosition) { | |||
122 | return bitPosition % APINT_BITS_PER_WORD; | |||
123 | } | |||
124 | ||||
125 | /// \brief Get a single bit mask. | |||
126 | /// | |||
127 | /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set | |||
128 | /// This method generates and returns a uint64_t (word) mask for a single | |||
129 | /// bit at a specific bit position. This is used to mask the bit in the | |||
130 | /// corresponding word. | |||
131 | static uint64_t maskBit(unsigned bitPosition) { | |||
132 | return 1ULL << whichBit(bitPosition); | |||
133 | } | |||
134 | ||||
135 | /// \brief Clear unused high order bits | |||
136 | /// | |||
137 | /// This method is used internally to clear the top "N" bits in the high order | |||
138 | /// word that are not used by the APInt. This is needed after the most | |||
139 | /// significant word is assigned a value to ensure that those bits are | |||
140 | /// zero'd out. | |||
141 | APInt &clearUnusedBits() { | |||
142 | // Compute how many bits are used in the final word | |||
143 | unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1; | |||
144 | ||||
145 | // Mask out the high bits. | |||
146 | uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - WordBits); | |||
147 | if (isSingleWord()) | |||
148 | U.VAL &= mask; | |||
149 | else | |||
150 | U.pVal[getNumWords() - 1] &= mask; | |||
151 | return *this; | |||
152 | } | |||
153 | ||||
154 | /// \brief Get the word corresponding to a bit position | |||
155 | /// \returns the corresponding word for the specified bit position. | |||
156 | uint64_t getWord(unsigned bitPosition) const { | |||
157 | return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; | |||
158 | } | |||
159 | ||||
160 | /// Utility method to change the bit width of this APInt to new bit width, | |||
161 | /// allocating and/or deallocating as necessary. There is no guarantee on the | |||
162 | /// value of any bits upon return. Caller should populate the bits after. | |||
163 | void reallocate(unsigned NewBitWidth); | |||
164 | ||||
165 | /// \brief Convert a char array into an APInt | |||
166 | /// | |||
167 | /// \param radix 2, 8, 10, 16, or 36 | |||
168 | /// Converts a string into a number. The string must be non-empty | |||
169 | /// and well-formed as a number of the given base. The bit-width | |||
170 | /// must be sufficient to hold the result. | |||
171 | /// | |||
172 | /// This is used by the constructors that take string arguments. | |||
173 | /// | |||
174 | /// StringRef::getAsInteger is superficially similar but (1) does | |||
175 | /// not assume that the string is well-formed and (2) grows the | |||
176 | /// result to hold the input. | |||
177 | void fromString(unsigned numBits, StringRef str, uint8_t radix); | |||
178 | ||||
179 | /// \brief An internal division function for dividing APInts. | |||
180 | /// | |||
181 | /// This is used by the toString method to divide by the radix. It simply | |||
182 | /// provides a more convenient form of divide for internal use since KnuthDiv | |||
183 | /// has specific constraints on its inputs. If those constraints are not met | |||
184 | /// then it provides a simpler form of divide. | |||
185 | static void divide(const WordType *LHS, unsigned lhsWords, | |||
186 | const WordType *RHS, unsigned rhsWords, WordType *Quotient, | |||
187 | WordType *Remainder); | |||
188 | ||||
189 | /// out-of-line slow case for inline constructor | |||
190 | void initSlowCase(uint64_t val, bool isSigned); | |||
191 | ||||
192 | /// shared code between two array constructors | |||
193 | void initFromArray(ArrayRef<uint64_t> array); | |||
194 | ||||
195 | /// out-of-line slow case for inline copy constructor | |||
196 | void initSlowCase(const APInt &that); | |||
197 | ||||
198 | /// out-of-line slow case for shl | |||
199 | void shlSlowCase(unsigned ShiftAmt); | |||
200 | ||||
201 | /// out-of-line slow case for lshr. | |||
202 | void lshrSlowCase(unsigned ShiftAmt); | |||
203 | ||||
204 | /// out-of-line slow case for ashr. | |||
205 | void ashrSlowCase(unsigned ShiftAmt); | |||
206 | ||||
207 | /// out-of-line slow case for operator= | |||
208 | void AssignSlowCase(const APInt &RHS); | |||
209 | ||||
210 | /// out-of-line slow case for operator== | |||
211 | bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
212 | ||||
213 | /// out-of-line slow case for countLeadingZeros | |||
214 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
215 | ||||
216 | /// out-of-line slow case for countLeadingOnes. | |||
217 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
218 | ||||
219 | /// out-of-line slow case for countTrailingZeros. | |||
220 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
221 | ||||
222 | /// out-of-line slow case for countTrailingOnes | |||
223 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
224 | ||||
225 | /// out-of-line slow case for countPopulation | |||
226 | unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
227 | ||||
228 | /// out-of-line slow case for intersects. | |||
229 | bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
230 | ||||
231 | /// out-of-line slow case for isSubsetOf. | |||
232 | bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
233 | ||||
234 | /// out-of-line slow case for setBits. | |||
235 | void setBitsSlowCase(unsigned loBit, unsigned hiBit); | |||
236 | ||||
237 | /// out-of-line slow case for flipAllBits. | |||
238 | void flipAllBitsSlowCase(); | |||
239 | ||||
240 | /// out-of-line slow case for operator&=. | |||
241 | void AndAssignSlowCase(const APInt& RHS); | |||
242 | ||||
243 | /// out-of-line slow case for operator|=. | |||
244 | void OrAssignSlowCase(const APInt& RHS); | |||
245 | ||||
246 | /// out-of-line slow case for operator^=. | |||
247 | void XorAssignSlowCase(const APInt& RHS); | |||
248 | ||||
249 | /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
250 | /// to, or greater than RHS. | |||
251 | int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
252 | ||||
253 | /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
254 | /// to, or greater than RHS. | |||
255 | int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
256 | ||||
257 | public: | |||
258 | /// \name Constructors | |||
259 | /// @{ | |||
260 | ||||
261 | /// \brief Create a new APInt of numBits width, initialized as val. | |||
262 | /// | |||
263 | /// If isSigned is true then val is treated as if it were a signed value | |||
264 | /// (i.e. as an int64_t) and the appropriate sign extension to the bit width | |||
265 | /// will be done. Otherwise, no sign extension occurs (high order bits beyond | |||
266 | /// the range of val are zero filled). | |||
267 | /// | |||
268 | /// \param numBits the bit width of the constructed APInt | |||
269 | /// \param val the initial value of the APInt | |||
270 | /// \param isSigned how to treat signedness of val | |||
271 | APInt(unsigned numBits, uint64_t val, bool isSigned = false) | |||
272 | : BitWidth(numBits) { | |||
273 | assert(BitWidth && "bitwidth too small")(static_cast <bool> (BitWidth && "bitwidth too small" ) ? void (0) : __assert_fail ("BitWidth && \"bitwidth too small\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 273, __extension__ __PRETTY_FUNCTION__)); | |||
274 | if (isSingleWord()) { | |||
275 | U.VAL = val; | |||
276 | clearUnusedBits(); | |||
277 | } else { | |||
278 | initSlowCase(val, isSigned); | |||
279 | } | |||
280 | } | |||
281 | ||||
282 | /// \brief Construct an APInt of numBits width, initialized as bigVal[]. | |||
283 | /// | |||
284 | /// Note that bigVal.size() can be smaller or larger than the corresponding | |||
285 | /// bit width but any extraneous bits will be dropped. | |||
286 | /// | |||
287 | /// \param numBits the bit width of the constructed APInt | |||
288 | /// \param bigVal a sequence of words to form the initial value of the APInt | |||
289 | APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); | |||
290 | ||||
291 | /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but | |||
292 | /// deprecated because this constructor is prone to ambiguity with the | |||
293 | /// APInt(unsigned, uint64_t, bool) constructor. | |||
294 | /// | |||
295 | /// If this overload is ever deleted, care should be taken to prevent calls | |||
296 | /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) | |||
297 | /// constructor. | |||
298 | APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); | |||
299 | ||||
300 | /// \brief Construct an APInt from a string representation. | |||
301 | /// | |||
302 | /// This constructor interprets the string \p str in the given radix. The | |||
303 | /// interpretation stops when the first character that is not suitable for the | |||
304 | /// radix is encountered, or the end of the string. Acceptable radix values | |||
305 | /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the | |||
306 | /// string to require more bits than numBits. | |||
307 | /// | |||
308 | /// \param numBits the bit width of the constructed APInt | |||
309 | /// \param str the string to be interpreted | |||
310 | /// \param radix the radix to use for the conversion | |||
311 | APInt(unsigned numBits, StringRef str, uint8_t radix); | |||
312 | ||||
313 | /// Simply makes *this a copy of that. | |||
314 | /// @brief Copy Constructor. | |||
315 | APInt(const APInt &that) : BitWidth(that.BitWidth) { | |||
316 | if (isSingleWord()) | |||
317 | U.VAL = that.U.VAL; | |||
318 | else | |||
319 | initSlowCase(that); | |||
320 | } | |||
321 | ||||
322 | /// \brief Move Constructor. | |||
323 | APInt(APInt &&that) : BitWidth(that.BitWidth) { | |||
| ||||
324 | memcpy(&U, &that.U, sizeof(U)); | |||
325 | that.BitWidth = 0; | |||
326 | } | |||
327 | ||||
328 | /// \brief Destructor. | |||
329 | ~APInt() { | |||
330 | if (needsCleanup()) | |||
331 | delete[] U.pVal; | |||
332 | } | |||
333 | ||||
334 | /// \brief Default constructor that creates an uninteresting APInt | |||
335 | /// representing a 1-bit zero value. | |||
336 | /// | |||
337 | /// This is useful for object deserialization (pair this with the static | |||
338 | /// method Read). | |||
339 | explicit APInt() : BitWidth(1) { U.VAL = 0; } | |||
340 | ||||
341 | /// \brief Returns whether this instance allocated memory. | |||
342 | bool needsCleanup() const { return !isSingleWord(); } | |||
343 | ||||
344 | /// Used to insert APInt objects, or objects that contain APInt objects, into | |||
345 | /// FoldingSets. | |||
346 | void Profile(FoldingSetNodeID &id) const; | |||
347 | ||||
348 | /// @} | |||
349 | /// \name Value Tests | |||
350 | /// @{ | |||
351 | ||||
352 | /// \brief Determine sign of this APInt. | |||
353 | /// | |||
354 | /// This tests the high bit of this APInt to determine if it is set. | |||
355 | /// | |||
356 | /// \returns true if this APInt is negative, false otherwise | |||
357 | bool isNegative() const { return (*this)[BitWidth - 1]; } | |||
358 | ||||
359 | /// \brief Determine if this APInt Value is non-negative (>= 0) | |||
360 | /// | |||
361 | /// This tests the high bit of the APInt to determine if it is unset. | |||
362 | bool isNonNegative() const { return !isNegative(); } | |||
363 | ||||
364 | /// \brief Determine if sign bit of this APInt is set. | |||
365 | /// | |||
366 | /// This tests the high bit of this APInt to determine if it is set. | |||
367 | /// | |||
368 | /// \returns true if this APInt has its sign bit set, false otherwise. | |||
369 | bool isSignBitSet() const { return (*this)[BitWidth-1]; } | |||
370 | ||||
371 | /// \brief Determine if sign bit of this APInt is clear. | |||
372 | /// | |||
373 | /// This tests the high bit of this APInt to determine if it is clear. | |||
374 | /// | |||
375 | /// \returns true if this APInt has its sign bit clear, false otherwise. | |||
376 | bool isSignBitClear() const { return !isSignBitSet(); } | |||
377 | ||||
378 | /// \brief Determine if this APInt Value is positive. | |||
379 | /// | |||
380 | /// This tests if the value of this APInt is positive (> 0). Note | |||
381 | /// that 0 is not a positive value. | |||
382 | /// | |||
383 | /// \returns true if this APInt is positive. | |||
384 | bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); } | |||
385 | ||||
386 | /// \brief Determine if all bits are set | |||
387 | /// | |||
388 | /// This checks to see if the value has all bits of the APInt are set or not. | |||
389 | bool isAllOnesValue() const { | |||
390 | if (isSingleWord()) | |||
391 | return U.VAL == WORD_MAX >> (APINT_BITS_PER_WORD - BitWidth); | |||
392 | return countTrailingOnesSlowCase() == BitWidth; | |||
393 | } | |||
394 | ||||
395 | /// \brief Determine if all bits are clear | |||
396 | /// | |||
397 | /// This checks to see if the value has all bits of the APInt are clear or | |||
398 | /// not. | |||
399 | bool isNullValue() const { return !*this; } | |||
400 | ||||
401 | /// \brief Determine if this is a value of 1. | |||
402 | /// | |||
403 | /// This checks to see if the value of this APInt is one. | |||
404 | bool isOneValue() const { | |||
405 | if (isSingleWord()) | |||
406 | return U.VAL == 1; | |||
407 | return countLeadingZerosSlowCase() == BitWidth - 1; | |||
408 | } | |||
409 | ||||
410 | /// \brief Determine if this is the largest unsigned value. | |||
411 | /// | |||
412 | /// This checks to see if the value of this APInt is the maximum unsigned | |||
413 | /// value for the APInt's bit width. | |||
414 | bool isMaxValue() const { return isAllOnesValue(); } | |||
415 | ||||
416 | /// \brief Determine if this is the largest signed value. | |||
417 | /// | |||
418 | /// This checks to see if the value of this APInt is the maximum signed | |||
419 | /// value for the APInt's bit width. | |||
420 | bool isMaxSignedValue() const { | |||
421 | if (isSingleWord()) | |||
422 | return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); | |||
423 | return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; | |||
424 | } | |||
425 | ||||
426 | /// \brief Determine if this is the smallest unsigned value. | |||
427 | /// | |||
428 | /// This checks to see if the value of this APInt is the minimum unsigned | |||
429 | /// value for the APInt's bit width. | |||
430 | bool isMinValue() const { return isNullValue(); } | |||
431 | ||||
432 | /// \brief Determine if this is the smallest signed value. | |||
433 | /// | |||
434 | /// This checks to see if the value of this APInt is the minimum signed | |||
435 | /// value for the APInt's bit width. | |||
436 | bool isMinSignedValue() const { | |||
437 | if (isSingleWord()) | |||
438 | return U.VAL == (WordType(1) << (BitWidth - 1)); | |||
439 | return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; | |||
440 | } | |||
441 | ||||
442 | /// \brief Check if this APInt has an N-bits unsigned integer value. | |||
443 | bool isIntN(unsigned N) const { | |||
444 | assert(N && "N == 0 ???")(static_cast <bool> (N && "N == 0 ???") ? void ( 0) : __assert_fail ("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 444, __extension__ __PRETTY_FUNCTION__)); | |||
445 | return getActiveBits() <= N; | |||
446 | } | |||
447 | ||||
448 | /// \brief Check if this APInt has an N-bits signed integer value. | |||
449 | bool isSignedIntN(unsigned N) const { | |||
450 | assert(N && "N == 0 ???")(static_cast <bool> (N && "N == 0 ???") ? void ( 0) : __assert_fail ("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 450, __extension__ __PRETTY_FUNCTION__)); | |||
451 | return getMinSignedBits() <= N; | |||
452 | } | |||
453 | ||||
454 | /// \brief Check if this APInt's value is a power of two greater than zero. | |||
455 | /// | |||
456 | /// \returns true if the argument APInt value is a power of two > 0. | |||
457 | bool isPowerOf2() const { | |||
458 | if (isSingleWord()) | |||
459 | return isPowerOf2_64(U.VAL); | |||
460 | return countPopulationSlowCase() == 1; | |||
461 | } | |||
462 | ||||
463 | /// \brief Check if the APInt's value is returned by getSignMask. | |||
464 | /// | |||
465 | /// \returns true if this is the value returned by getSignMask. | |||
466 | bool isSignMask() const { return isMinSignedValue(); } | |||
467 | ||||
468 | /// \brief Convert APInt to a boolean value. | |||
469 | /// | |||
470 | /// This converts the APInt to a boolean value as a test against zero. | |||
471 | bool getBoolValue() const { return !!*this; } | |||
472 | ||||
473 | /// If this value is smaller than the specified limit, return it, otherwise | |||
474 | /// return the limit value. This causes the value to saturate to the limit. | |||
475 | uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const { | |||
476 | return ugt(Limit) ? Limit : getZExtValue(); | |||
477 | } | |||
478 | ||||
479 | /// \brief Check if the APInt consists of a repeated bit pattern. | |||
480 | /// | |||
481 | /// e.g. 0x01010101 satisfies isSplat(8). | |||
482 | /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit | |||
483 | /// width without remainder. | |||
484 | bool isSplat(unsigned SplatSizeInBits) const; | |||
485 | ||||
486 | /// \returns true if this APInt value is a sequence of \param numBits ones | |||
487 | /// starting at the least significant bit with the remainder zero. | |||
488 | bool isMask(unsigned numBits) const { | |||
489 | assert(numBits != 0 && "numBits must be non-zero")(static_cast <bool> (numBits != 0 && "numBits must be non-zero" ) ? void (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 489, __extension__ __PRETTY_FUNCTION__)); | |||
490 | assert(numBits <= BitWidth && "numBits out of range")(static_cast <bool> (numBits <= BitWidth && "numBits out of range" ) ? void (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 490, __extension__ __PRETTY_FUNCTION__)); | |||
491 | if (isSingleWord()) | |||
492 | return U.VAL == (WORD_MAX >> (APINT_BITS_PER_WORD - numBits)); | |||
493 | unsigned Ones = countTrailingOnesSlowCase(); | |||
494 | return (numBits == Ones) && | |||
495 | ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
496 | } | |||
497 | ||||
498 | /// \returns true if this APInt is a non-empty sequence of ones starting at | |||
499 | /// the least significant bit with the remainder zero. | |||
500 | /// Ex. isMask(0x0000FFFFU) == true. | |||
501 | bool isMask() const { | |||
502 | if (isSingleWord()) | |||
503 | return isMask_64(U.VAL); | |||
504 | unsigned Ones = countTrailingOnesSlowCase(); | |||
505 | return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
506 | } | |||
507 | ||||
508 | /// \brief Return true if this APInt value contains a sequence of ones with | |||
509 | /// the remainder zero. | |||
510 | bool isShiftedMask() const { | |||
511 | if (isSingleWord()) | |||
512 | return isShiftedMask_64(U.VAL); | |||
513 | unsigned Ones = countPopulationSlowCase(); | |||
514 | unsigned LeadZ = countLeadingZerosSlowCase(); | |||
515 | return (Ones + LeadZ + countTrailingZeros()) == BitWidth; | |||
516 | } | |||
517 | ||||
518 | /// @} | |||
519 | /// \name Value Generators | |||
520 | /// @{ | |||
521 | ||||
522 | /// \brief Gets maximum unsigned value of APInt for specific bit width. | |||
523 | static APInt getMaxValue(unsigned numBits) { | |||
524 | return getAllOnesValue(numBits); | |||
525 | } | |||
526 | ||||
527 | /// \brief Gets maximum signed value of APInt for a specific bit width. | |||
528 | static APInt getSignedMaxValue(unsigned numBits) { | |||
529 | APInt API = getAllOnesValue(numBits); | |||
530 | API.clearBit(numBits - 1); | |||
531 | return API; | |||
532 | } | |||
533 | ||||
534 | /// \brief Gets minimum unsigned value of APInt for a specific bit width. | |||
535 | static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } | |||
536 | ||||
537 | /// \brief Gets minimum signed value of APInt for a specific bit width. | |||
538 | static APInt getSignedMinValue(unsigned numBits) { | |||
539 | APInt API(numBits, 0); | |||
540 | API.setBit(numBits - 1); | |||
541 | return API; | |||
542 | } | |||
543 | ||||
544 | /// \brief Get the SignMask for a specific bit width. | |||
545 | /// | |||
546 | /// This is just a wrapper function of getSignedMinValue(), and it helps code | |||
547 | /// readability when we want to get a SignMask. | |||
548 | static APInt getSignMask(unsigned BitWidth) { | |||
549 | return getSignedMinValue(BitWidth); | |||
550 | } | |||
551 | ||||
552 | /// \brief Get the all-ones value. | |||
553 | /// | |||
554 | /// \returns the all-ones value for an APInt of the specified bit-width. | |||
555 | static APInt getAllOnesValue(unsigned numBits) { | |||
556 | return APInt(numBits, WORD_MAX, true); | |||
557 | } | |||
558 | ||||
559 | /// \brief Get the '0' value. | |||
560 | /// | |||
561 | /// \returns the '0' value for an APInt of the specified bit-width. | |||
562 | static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); } | |||
563 | ||||
564 | /// \brief Compute an APInt containing numBits highbits from this APInt. | |||
565 | /// | |||
566 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
567 | /// the low bits and right shift to the least significant bit. | |||
568 | /// | |||
569 | /// \returns the high "numBits" bits of this APInt. | |||
570 | APInt getHiBits(unsigned numBits) const; | |||
571 | ||||
572 | /// \brief Compute an APInt containing numBits lowbits from this APInt. | |||
573 | /// | |||
574 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
575 | /// the high bits. | |||
576 | /// | |||
577 | /// \returns the low "numBits" bits of this APInt. | |||
578 | APInt getLoBits(unsigned numBits) const; | |||
579 | ||||
580 | /// \brief Return an APInt with exactly one bit set in the result. | |||
581 | static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { | |||
582 | APInt Res(numBits, 0); | |||
583 | Res.setBit(BitNo); | |||
584 | return Res; | |||
585 | } | |||
586 | ||||
587 | /// \brief Get a value with a block of bits set. | |||
588 | /// | |||
589 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
590 | /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other | |||
591 | /// bits will be zero. For example, with parameters(32, 0, 16) you would get | |||
592 | /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For | |||
593 | /// example, with parameters (32, 28, 4), you would get 0xF000000F. | |||
594 | /// | |||
595 | /// \param numBits the intended bit width of the result | |||
596 | /// \param loBit the index of the lowest bit set. | |||
597 | /// \param hiBit the index of the highest bit set. | |||
598 | /// | |||
599 | /// \returns An APInt value with the requested bits set. | |||
600 | static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { | |||
601 | APInt Res(numBits, 0); | |||
602 | Res.setBits(loBit, hiBit); | |||
603 | return Res; | |||
604 | } | |||
605 | ||||
606 | /// \brief Get a value with upper bits starting at loBit set. | |||
607 | /// | |||
608 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
609 | /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other | |||
610 | /// bits will be zero. For example, with parameters(32, 12) you would get | |||
611 | /// 0xFFFFF000. | |||
612 | /// | |||
613 | /// \param numBits the intended bit width of the result | |||
614 | /// \param loBit the index of the lowest bit to set. | |||
615 | /// | |||
616 | /// \returns An APInt value with the requested bits set. | |||
617 | static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { | |||
618 | APInt Res(numBits, 0); | |||
619 | Res.setBitsFrom(loBit); | |||
620 | return Res; | |||
621 | } | |||
622 | ||||
623 | /// \brief Get a value with high bits set | |||
624 | /// | |||
625 | /// Constructs an APInt value that has the top hiBitsSet bits set. | |||
626 | /// | |||
627 | /// \param numBits the bitwidth of the result | |||
628 | /// \param hiBitsSet the number of high-order bits set in the result. | |||
629 | static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { | |||
630 | APInt Res(numBits, 0); | |||
631 | Res.setHighBits(hiBitsSet); | |||
632 | return Res; | |||
633 | } | |||
634 | ||||
635 | /// \brief Get a value with low bits set | |||
636 | /// | |||
637 | /// Constructs an APInt value that has the bottom loBitsSet bits set. | |||
638 | /// | |||
639 | /// \param numBits the bitwidth of the result | |||
640 | /// \param loBitsSet the number of low-order bits set in the result. | |||
641 | static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { | |||
642 | APInt Res(numBits, 0); | |||
643 | Res.setLowBits(loBitsSet); | |||
644 | return Res; | |||
645 | } | |||
646 | ||||
647 | /// \brief Return a value containing V broadcasted over NewLen bits. | |||
648 | static APInt getSplat(unsigned NewLen, const APInt &V); | |||
649 | ||||
650 | /// \brief Determine if two APInts have the same value, after zero-extending | |||
651 | /// one of them (if needed!) to ensure that the bit-widths match. | |||
652 | static bool isSameValue(const APInt &I1, const APInt &I2) { | |||
653 | if (I1.getBitWidth() == I2.getBitWidth()) | |||
654 | return I1 == I2; | |||
655 | ||||
656 | if (I1.getBitWidth() > I2.getBitWidth()) | |||
657 | return I1 == I2.zext(I1.getBitWidth()); | |||
658 | ||||
659 | return I1.zext(I2.getBitWidth()) == I2; | |||
660 | } | |||
661 | ||||
662 | /// \brief Overload to compute a hash_code for an APInt value. | |||
663 | friend hash_code hash_value(const APInt &Arg); | |||
664 | ||||
665 | /// This function returns a pointer to the internal storage of the APInt. | |||
666 | /// This is useful for writing out the APInt in binary form without any | |||
667 | /// conversions. | |||
668 | const uint64_t *getRawData() const { | |||
669 | if (isSingleWord()) | |||
670 | return &U.VAL; | |||
671 | return &U.pVal[0]; | |||
672 | } | |||
673 | ||||
674 | /// @} | |||
675 | /// \name Unary Operators | |||
676 | /// @{ | |||
677 | ||||
678 | /// \brief Postfix increment operator. | |||
679 | /// | |||
680 | /// Increments *this by 1. | |||
681 | /// | |||
682 | /// \returns a new APInt value representing the original value of *this. | |||
683 | const APInt operator++(int) { | |||
684 | APInt API(*this); | |||
685 | ++(*this); | |||
686 | return API; | |||
687 | } | |||
688 | ||||
689 | /// \brief Prefix increment operator. | |||
690 | /// | |||
691 | /// \returns *this incremented by one | |||
692 | APInt &operator++(); | |||
693 | ||||
694 | /// \brief Postfix decrement operator. | |||
695 | /// | |||
696 | /// Decrements *this by 1. | |||
697 | /// | |||
698 | /// \returns a new APInt value representing the original value of *this. | |||
699 | const APInt operator--(int) { | |||
700 | APInt API(*this); | |||
701 | --(*this); | |||
702 | return API; | |||
703 | } | |||
704 | ||||
705 | /// \brief Prefix decrement operator. | |||
706 | /// | |||
707 | /// \returns *this decremented by one. | |||
708 | APInt &operator--(); | |||
709 | ||||
710 | /// \brief Logical negation operator. | |||
711 | /// | |||
712 | /// Performs logical negation operation on this APInt. | |||
713 | /// | |||
714 | /// \returns true if *this is zero, false otherwise. | |||
715 | bool operator!() const { | |||
716 | if (isSingleWord()) | |||
717 | return U.VAL == 0; | |||
718 | return countLeadingZerosSlowCase() == BitWidth; | |||
719 | } | |||
720 | ||||
721 | /// @} | |||
722 | /// \name Assignment Operators | |||
723 | /// @{ | |||
724 | ||||
725 | /// \brief Copy assignment operator. | |||
726 | /// | |||
727 | /// \returns *this after assignment of RHS. | |||
728 | APInt &operator=(const APInt &RHS) { | |||
729 | // If the bitwidths are the same, we can avoid mucking with memory | |||
730 | if (isSingleWord() && RHS.isSingleWord()) { | |||
731 | U.VAL = RHS.U.VAL; | |||
732 | BitWidth = RHS.BitWidth; | |||
733 | return clearUnusedBits(); | |||
734 | } | |||
735 | ||||
736 | AssignSlowCase(RHS); | |||
737 | return *this; | |||
738 | } | |||
739 | ||||
740 | /// @brief Move assignment operator. | |||
741 | APInt &operator=(APInt &&that) { | |||
742 | assert(this != &that && "Self-move not supported")(static_cast <bool> (this != &that && "Self-move not supported" ) ? void (0) : __assert_fail ("this != &that && \"Self-move not supported\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 742, __extension__ __PRETTY_FUNCTION__)); | |||
743 | if (!isSingleWord()) | |||
744 | delete[] U.pVal; | |||
745 | ||||
746 | // Use memcpy so that type based alias analysis sees both VAL and pVal | |||
747 | // as modified. | |||
748 | memcpy(&U, &that.U, sizeof(U)); | |||
749 | ||||
750 | BitWidth = that.BitWidth; | |||
751 | that.BitWidth = 0; | |||
752 | ||||
753 | return *this; | |||
754 | } | |||
755 | ||||
756 | /// \brief Assignment operator. | |||
757 | /// | |||
758 | /// The RHS value is assigned to *this. If the significant bits in RHS exceed | |||
759 | /// the bit width, the excess bits are truncated. If the bit width is larger | |||
760 | /// than 64, the value is zero filled in the unspecified high order bits. | |||
761 | /// | |||
762 | /// \returns *this after assignment of RHS value. | |||
763 | APInt &operator=(uint64_t RHS) { | |||
764 | if (isSingleWord()) { | |||
765 | U.VAL = RHS; | |||
766 | clearUnusedBits(); | |||
767 | } else { | |||
768 | U.pVal[0] = RHS; | |||
769 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
770 | } | |||
771 | return *this; | |||
772 | } | |||
773 | ||||
774 | /// \brief Bitwise AND assignment operator. | |||
775 | /// | |||
776 | /// Performs a bitwise AND operation on this APInt and RHS. The result is | |||
777 | /// assigned to *this. | |||
778 | /// | |||
779 | /// \returns *this after ANDing with RHS. | |||
780 | APInt &operator&=(const APInt &RHS) { | |||
781 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth && "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 781, __extension__ __PRETTY_FUNCTION__)); | |||
782 | if (isSingleWord()) | |||
783 | U.VAL &= RHS.U.VAL; | |||
784 | else | |||
785 | AndAssignSlowCase(RHS); | |||
786 | return *this; | |||
787 | } | |||
788 | ||||
789 | /// \brief Bitwise AND assignment operator. | |||
790 | /// | |||
791 | /// Performs a bitwise AND operation on this APInt and RHS. RHS is | |||
792 | /// logically zero-extended or truncated to match the bit-width of | |||
793 | /// the LHS. | |||
794 | APInt &operator&=(uint64_t RHS) { | |||
795 | if (isSingleWord()) { | |||
796 | U.VAL &= RHS; | |||
797 | return *this; | |||
798 | } | |||
799 | U.pVal[0] &= RHS; | |||
800 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
801 | return *this; | |||
802 | } | |||
803 | ||||
804 | /// \brief Bitwise OR assignment operator. | |||
805 | /// | |||
806 | /// Performs a bitwise OR operation on this APInt and RHS. The result is | |||
807 | /// assigned *this; | |||
808 | /// | |||
809 | /// \returns *this after ORing with RHS. | |||
810 | APInt &operator|=(const APInt &RHS) { | |||
811 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth && "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 811, __extension__ __PRETTY_FUNCTION__)); | |||
812 | if (isSingleWord()) | |||
813 | U.VAL |= RHS.U.VAL; | |||
814 | else | |||
815 | OrAssignSlowCase(RHS); | |||
816 | return *this; | |||
817 | } | |||
818 | ||||
819 | /// \brief Bitwise OR assignment operator. | |||
820 | /// | |||
821 | /// Performs a bitwise OR operation on this APInt and RHS. RHS is | |||
822 | /// logically zero-extended or truncated to match the bit-width of | |||
823 | /// the LHS. | |||
824 | APInt &operator|=(uint64_t RHS) { | |||
825 | if (isSingleWord()) { | |||
826 | U.VAL |= RHS; | |||
827 | clearUnusedBits(); | |||
828 | } else { | |||
829 | U.pVal[0] |= RHS; | |||
830 | } | |||
831 | return *this; | |||
832 | } | |||
833 | ||||
834 | /// \brief Bitwise XOR assignment operator. | |||
835 | /// | |||
836 | /// Performs a bitwise XOR operation on this APInt and RHS. The result is | |||
837 | /// assigned to *this. | |||
838 | /// | |||
839 | /// \returns *this after XORing with RHS. | |||
840 | APInt &operator^=(const APInt &RHS) { | |||
841 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth && "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 841, __extension__ __PRETTY_FUNCTION__)); | |||
842 | if (isSingleWord()) | |||
843 | U.VAL ^= RHS.U.VAL; | |||
844 | else | |||
845 | XorAssignSlowCase(RHS); | |||
846 | return *this; | |||
847 | } | |||
848 | ||||
849 | /// \brief Bitwise XOR assignment operator. | |||
850 | /// | |||
851 | /// Performs a bitwise XOR operation on this APInt and RHS. RHS is | |||
852 | /// logically zero-extended or truncated to match the bit-width of | |||
853 | /// the LHS. | |||
854 | APInt &operator^=(uint64_t RHS) { | |||
855 | if (isSingleWord()) { | |||
856 | U.VAL ^= RHS; | |||
857 | clearUnusedBits(); | |||
858 | } else { | |||
859 | U.pVal[0] ^= RHS; | |||
860 | } | |||
861 | return *this; | |||
862 | } | |||
863 | ||||
864 | /// \brief Multiplication assignment operator. | |||
865 | /// | |||
866 | /// Multiplies this APInt by RHS and assigns the result to *this. | |||
867 | /// | |||
868 | /// \returns *this | |||
869 | APInt &operator*=(const APInt &RHS); | |||
870 | APInt &operator*=(uint64_t RHS); | |||
871 | ||||
872 | /// \brief Addition assignment operator. | |||
873 | /// | |||
874 | /// Adds RHS to *this and assigns the result to *this. | |||
875 | /// | |||
876 | /// \returns *this | |||
877 | APInt &operator+=(const APInt &RHS); | |||
878 | APInt &operator+=(uint64_t RHS); | |||
879 | ||||
880 | /// \brief Subtraction assignment operator. | |||
881 | /// | |||
882 | /// Subtracts RHS from *this and assigns the result to *this. | |||
883 | /// | |||
884 | /// \returns *this | |||
885 | APInt &operator-=(const APInt &RHS); | |||
886 | APInt &operator-=(uint64_t RHS); | |||
887 | ||||
888 | /// \brief Left-shift assignment function. | |||
889 | /// | |||
890 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
891 | /// | |||
892 | /// \returns *this after shifting left by ShiftAmt | |||
893 | APInt &operator<<=(unsigned ShiftAmt) { | |||
894 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth && "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 894, __extension__ __PRETTY_FUNCTION__)); | |||
895 | if (isSingleWord()) { | |||
896 | if (ShiftAmt == BitWidth) | |||
897 | U.VAL = 0; | |||
898 | else | |||
899 | U.VAL <<= ShiftAmt; | |||
900 | return clearUnusedBits(); | |||
901 | } | |||
902 | shlSlowCase(ShiftAmt); | |||
903 | return *this; | |||
904 | } | |||
905 | ||||
906 | /// \brief Left-shift assignment function. | |||
907 | /// | |||
908 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
909 | /// | |||
910 | /// \returns *this after shifting left by ShiftAmt | |||
911 | APInt &operator<<=(const APInt &ShiftAmt); | |||
912 | ||||
913 | /// @} | |||
914 | /// \name Binary Operators | |||
915 | /// @{ | |||
916 | ||||
917 | /// \brief Multiplication operator. | |||
918 | /// | |||
919 | /// Multiplies this APInt by RHS and returns the result. | |||
920 | APInt operator*(const APInt &RHS) const; | |||
921 | ||||
922 | /// \brief Left logical shift operator. | |||
923 | /// | |||
924 | /// Shifts this APInt left by \p Bits and returns the result. | |||
925 | APInt operator<<(unsigned Bits) const { return shl(Bits); } | |||
926 | ||||
927 | /// \brief Left logical shift operator. | |||
928 | /// | |||
929 | /// Shifts this APInt left by \p Bits and returns the result. | |||
930 | APInt operator<<(const APInt &Bits) const { return shl(Bits); } | |||
931 | ||||
932 | /// \brief Arithmetic right-shift function. | |||
933 | /// | |||
934 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
935 | APInt ashr(unsigned ShiftAmt) const { | |||
936 | APInt R(*this); | |||
937 | R.ashrInPlace(ShiftAmt); | |||
938 | return R; | |||
939 | } | |||
940 | ||||
941 | /// Arithmetic right-shift this APInt by ShiftAmt in place. | |||
942 | void ashrInPlace(unsigned ShiftAmt) { | |||
943 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth && "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 943, __extension__ __PRETTY_FUNCTION__)); | |||
944 | if (isSingleWord()) { | |||
945 | int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); | |||
946 | if (ShiftAmt == BitWidth) | |||
947 | U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit. | |||
948 | else | |||
949 | U.VAL = SExtVAL >> ShiftAmt; | |||
950 | clearUnusedBits(); | |||
951 | return; | |||
952 | } | |||
953 | ashrSlowCase(ShiftAmt); | |||
954 | } | |||
955 | ||||
956 | /// \brief Logical right-shift function. | |||
957 | /// | |||
958 | /// Logical right-shift this APInt by shiftAmt. | |||
959 | APInt lshr(unsigned shiftAmt) const { | |||
960 | APInt R(*this); | |||
961 | R.lshrInPlace(shiftAmt); | |||
962 | return R; | |||
963 | } | |||
964 | ||||
965 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
966 | void lshrInPlace(unsigned ShiftAmt) { | |||
967 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth && "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 967, __extension__ __PRETTY_FUNCTION__)); | |||
968 | if (isSingleWord()) { | |||
969 | if (ShiftAmt == BitWidth) | |||
970 | U.VAL = 0; | |||
971 | else | |||
972 | U.VAL >>= ShiftAmt; | |||
973 | return; | |||
974 | } | |||
975 | lshrSlowCase(ShiftAmt); | |||
976 | } | |||
977 | ||||
978 | /// \brief Left-shift function. | |||
979 | /// | |||
980 | /// Left-shift this APInt by shiftAmt. | |||
981 | APInt shl(unsigned shiftAmt) const { | |||
982 | APInt R(*this); | |||
983 | R <<= shiftAmt; | |||
984 | return R; | |||
985 | } | |||
986 | ||||
987 | /// \brief Rotate left by rotateAmt. | |||
988 | APInt rotl(unsigned rotateAmt) const; | |||
989 | ||||
990 | /// \brief Rotate right by rotateAmt. | |||
991 | APInt rotr(unsigned rotateAmt) const; | |||
992 | ||||
993 | /// \brief Arithmetic right-shift function. | |||
994 | /// | |||
995 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
996 | APInt ashr(const APInt &ShiftAmt) const { | |||
997 | APInt R(*this); | |||
998 | R.ashrInPlace(ShiftAmt); | |||
999 | return R; | |||
1000 | } | |||
1001 | ||||
1002 | /// Arithmetic right-shift this APInt by shiftAmt in place. | |||
1003 | void ashrInPlace(const APInt &shiftAmt); | |||
1004 | ||||
1005 | /// \brief Logical right-shift function. | |||
1006 | /// | |||
1007 | /// Logical right-shift this APInt by shiftAmt. | |||
1008 | APInt lshr(const APInt &ShiftAmt) const { | |||
1009 | APInt R(*this); | |||
1010 | R.lshrInPlace(ShiftAmt); | |||
1011 | return R; | |||
1012 | } | |||
1013 | ||||
1014 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
1015 | void lshrInPlace(const APInt &ShiftAmt); | |||
1016 | ||||
1017 | /// \brief Left-shift function. | |||
1018 | /// | |||
1019 | /// Left-shift this APInt by shiftAmt. | |||
1020 | APInt shl(const APInt &ShiftAmt) const { | |||
1021 | APInt R(*this); | |||
1022 | R <<= ShiftAmt; | |||
1023 | return R; | |||
1024 | } | |||
1025 | ||||
1026 | /// \brief Rotate left by rotateAmt. | |||
1027 | APInt rotl(const APInt &rotateAmt) const; | |||
1028 | ||||
1029 | /// \brief Rotate right by rotateAmt. | |||
1030 | APInt rotr(const APInt &rotateAmt) const; | |||
1031 | ||||
1032 | /// \brief Unsigned division operation. | |||
1033 | /// | |||
1034 | /// Perform an unsigned divide operation on this APInt by RHS. Both this and | |||
1035 | /// RHS are treated as unsigned quantities for purposes of this division. | |||
1036 | /// | |||
1037 | /// \returns a new APInt value containing the division result | |||
1038 | APInt udiv(const APInt &RHS) const; | |||
1039 | APInt udiv(uint64_t RHS) const; | |||
1040 | ||||
1041 | /// \brief Signed division function for APInt. | |||
1042 | /// | |||
1043 | /// Signed divide this APInt by APInt RHS. | |||
1044 | APInt sdiv(const APInt &RHS) const; | |||
1045 | APInt sdiv(int64_t RHS) const; | |||
1046 | ||||
1047 | /// \brief Unsigned remainder operation. | |||
1048 | /// | |||
1049 | /// Perform an unsigned remainder operation on this APInt with RHS being the | |||
1050 | /// divisor. Both this and RHS are treated as unsigned quantities for purposes | |||
1051 | /// of this operation. Note that this is a true remainder operation and not a | |||
1052 | /// modulo operation because the sign follows the sign of the dividend which | |||
1053 | /// is *this. | |||
1054 | /// | |||
1055 | /// \returns a new APInt value containing the remainder result | |||
1056 | APInt urem(const APInt &RHS) const; | |||
1057 | uint64_t urem(uint64_t RHS) const; | |||
1058 | ||||
1059 | /// \brief Function for signed remainder operation. | |||
1060 | /// | |||
1061 | /// Signed remainder operation on APInt. | |||
1062 | APInt srem(const APInt &RHS) const; | |||
1063 | int64_t srem(int64_t RHS) const; | |||
1064 | ||||
1065 | /// \brief Dual division/remainder interface. | |||
1066 | /// | |||
1067 | /// Sometimes it is convenient to divide two APInt values and obtain both the | |||
1068 | /// quotient and remainder. This function does both operations in the same | |||
1069 | /// computation making it a little more efficient. The pair of input arguments | |||
1070 | /// may overlap with the pair of output arguments. It is safe to call | |||
1071 | /// udivrem(X, Y, X, Y), for example. | |||
1072 | static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
1073 | APInt &Remainder); | |||
1074 | static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, | |||
1075 | uint64_t &Remainder); | |||
1076 | ||||
1077 | static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
1078 | APInt &Remainder); | |||
1079 | static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, | |||
1080 | int64_t &Remainder); | |||
1081 | ||||
1082 | // Operations that return overflow indicators. | |||
1083 | APInt sadd_ov(const APInt &RHS, bool &Overflow) const; | |||
1084 | APInt uadd_ov(const APInt &RHS, bool &Overflow) const; | |||
1085 | APInt ssub_ov(const APInt &RHS, bool &Overflow) const; | |||
1086 | APInt usub_ov(const APInt &RHS, bool &Overflow) const; | |||
1087 | APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; | |||
1088 | APInt smul_ov(const APInt &RHS, bool &Overflow) const; | |||
1089 | APInt umul_ov(const APInt &RHS, bool &Overflow) const; | |||
1090 | APInt sshl_ov(const APInt &Amt, bool &Overflow) const; | |||
1091 | APInt ushl_ov(const APInt &Amt, bool &Overflow) const; | |||
1092 | ||||
1093 | /// \brief Array-indexing support. | |||
1094 | /// | |||
1095 | /// \returns the bit value at bitPosition | |||
1096 | bool operator[](unsigned bitPosition) const { | |||
1097 | assert(bitPosition < getBitWidth() && "Bit position out of bounds!")(static_cast <bool> (bitPosition < getBitWidth() && "Bit position out of bounds!") ? void (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1097, __extension__ __PRETTY_FUNCTION__)); | |||
1098 | return (maskBit(bitPosition) & getWord(bitPosition)) != 0; | |||
1099 | } | |||
1100 | ||||
1101 | /// @} | |||
1102 | /// \name Comparison Operators | |||
1103 | /// @{ | |||
1104 | ||||
1105 | /// \brief Equality operator. | |||
1106 | /// | |||
1107 | /// Compares this APInt with RHS for the validity of the equality | |||
1108 | /// relationship. | |||
1109 | bool operator==(const APInt &RHS) const { | |||
1110 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")(static_cast <bool> (BitWidth == RHS.BitWidth && "Comparison requires equal bit widths") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1110, __extension__ __PRETTY_FUNCTION__)); | |||
1111 | if (isSingleWord()) | |||
1112 | return U.VAL == RHS.U.VAL; | |||
1113 | return EqualSlowCase(RHS); | |||
1114 | } | |||
1115 | ||||
1116 | /// \brief Equality operator. | |||
1117 | /// | |||
1118 | /// Compares this APInt with a uint64_t for the validity of the equality | |||
1119 | /// relationship. | |||
1120 | /// | |||
1121 | /// \returns true if *this == Val | |||
1122 | bool operator==(uint64_t Val) const { | |||
1123 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; | |||
1124 | } | |||
1125 | ||||
1126 | /// \brief Equality comparison. | |||
1127 | /// | |||
1128 | /// Compares this APInt with RHS for the validity of the equality | |||
1129 | /// relationship. | |||
1130 | /// | |||
1131 | /// \returns true if *this == Val | |||
1132 | bool eq(const APInt &RHS) const { return (*this) == RHS; } | |||
1133 | ||||
1134 | /// \brief Inequality operator. | |||
1135 | /// | |||
1136 | /// Compares this APInt with RHS for the validity of the inequality | |||
1137 | /// relationship. | |||
1138 | /// | |||
1139 | /// \returns true if *this != Val | |||
1140 | bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } | |||
1141 | ||||
1142 | /// \brief Inequality operator. | |||
1143 | /// | |||
1144 | /// Compares this APInt with a uint64_t for the validity of the inequality | |||
1145 | /// relationship. | |||
1146 | /// | |||
1147 | /// \returns true if *this != Val | |||
1148 | bool operator!=(uint64_t Val) const { return !((*this) == Val); } | |||
1149 | ||||
1150 | /// \brief Inequality comparison | |||
1151 | /// | |||
1152 | /// Compares this APInt with RHS for the validity of the inequality | |||
1153 | /// relationship. | |||
1154 | /// | |||
1155 | /// \returns true if *this != Val | |||
1156 | bool ne(const APInt &RHS) const { return !((*this) == RHS); } | |||
1157 | ||||
1158 | /// \brief Unsigned less than comparison | |||
1159 | /// | |||
1160 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1161 | /// the validity of the less-than relationship. | |||
1162 | /// | |||
1163 | /// \returns true if *this < RHS when both are considered unsigned. | |||
1164 | bool ult(const APInt &RHS) const { return compare(RHS) < 0; } | |||
1165 | ||||
1166 | /// \brief Unsigned less than comparison | |||
1167 | /// | |||
1168 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1169 | /// the validity of the less-than relationship. | |||
1170 | /// | |||
1171 | /// \returns true if *this < RHS when considered unsigned. | |||
1172 | bool ult(uint64_t RHS) const { | |||
1173 | // Only need to check active bits if not a single word. | |||
1174 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; | |||
1175 | } | |||
1176 | ||||
1177 | /// \brief Signed less than comparison | |||
1178 | /// | |||
1179 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1180 | /// validity of the less-than relationship. | |||
1181 | /// | |||
1182 | /// \returns true if *this < RHS when both are considered signed. | |||
1183 | bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } | |||
1184 | ||||
1185 | /// \brief Signed less than comparison | |||
1186 | /// | |||
1187 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1188 | /// the validity of the less-than relationship. | |||
1189 | /// | |||
1190 | /// \returns true if *this < RHS when considered signed. | |||
1191 | bool slt(int64_t RHS) const { | |||
1192 | return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative() | |||
1193 | : getSExtValue() < RHS; | |||
1194 | } | |||
1195 | ||||
1196 | /// \brief Unsigned less or equal comparison | |||
1197 | /// | |||
1198 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1199 | /// validity of the less-or-equal relationship. | |||
1200 | /// | |||
1201 | /// \returns true if *this <= RHS when both are considered unsigned. | |||
1202 | bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } | |||
1203 | ||||
1204 | /// \brief Unsigned less or equal comparison | |||
1205 | /// | |||
1206 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1207 | /// the validity of the less-or-equal relationship. | |||
1208 | /// | |||
1209 | /// \returns true if *this <= RHS when considered unsigned. | |||
1210 | bool ule(uint64_t RHS) const { return !ugt(RHS); } | |||
1211 | ||||
1212 | /// \brief Signed less or equal comparison | |||
1213 | /// | |||
1214 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1215 | /// validity of the less-or-equal relationship. | |||
1216 | /// | |||
1217 | /// \returns true if *this <= RHS when both are considered signed. | |||
1218 | bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } | |||
1219 | ||||
1220 | /// \brief Signed less or equal comparison | |||
1221 | /// | |||
1222 | /// Regards both *this as a signed quantity and compares it with RHS for the | |||
1223 | /// validity of the less-or-equal relationship. | |||
1224 | /// | |||
1225 | /// \returns true if *this <= RHS when considered signed. | |||
1226 | bool sle(uint64_t RHS) const { return !sgt(RHS); } | |||
1227 | ||||
1228 | /// \brief Unsigned greather than comparison | |||
1229 | /// | |||
1230 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1231 | /// the validity of the greater-than relationship. | |||
1232 | /// | |||
1233 | /// \returns true if *this > RHS when both are considered unsigned. | |||
1234 | bool ugt(const APInt &RHS) const { return !ule(RHS); } | |||
1235 | ||||
1236 | /// \brief Unsigned greater than comparison | |||
1237 | /// | |||
1238 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1239 | /// the validity of the greater-than relationship. | |||
1240 | /// | |||
1241 | /// \returns true if *this > RHS when considered unsigned. | |||
1242 | bool ugt(uint64_t RHS) const { | |||
1243 | // Only need to check active bits if not a single word. | |||
1244 | return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; | |||
1245 | } | |||
1246 | ||||
1247 | /// \brief Signed greather than comparison | |||
1248 | /// | |||
1249 | /// Regards both *this and RHS as signed quantities and compares them for the | |||
1250 | /// validity of the greater-than relationship. | |||
1251 | /// | |||
1252 | /// \returns true if *this > RHS when both are considered signed. | |||
1253 | bool sgt(const APInt &RHS) const { return !sle(RHS); } | |||
1254 | ||||
1255 | /// \brief Signed greater than comparison | |||
1256 | /// | |||
1257 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1258 | /// the validity of the greater-than relationship. | |||
1259 | /// | |||
1260 | /// \returns true if *this > RHS when considered signed. | |||
1261 | bool sgt(int64_t RHS) const { | |||
1262 | return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative() | |||
1263 | : getSExtValue() > RHS; | |||
1264 | } | |||
1265 | ||||
1266 | /// \brief Unsigned greater or equal comparison | |||
1267 | /// | |||
1268 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1269 | /// validity of the greater-or-equal relationship. | |||
1270 | /// | |||
1271 | /// \returns true if *this >= RHS when both are considered unsigned. | |||
1272 | bool uge(const APInt &RHS) const { return !ult(RHS); } | |||
1273 | ||||
1274 | /// \brief Unsigned greater or equal comparison | |||
1275 | /// | |||
1276 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1277 | /// the validity of the greater-or-equal relationship. | |||
1278 | /// | |||
1279 | /// \returns true if *this >= RHS when considered unsigned. | |||
1280 | bool uge(uint64_t RHS) const { return !ult(RHS); } | |||
1281 | ||||
1282 | /// \brief Signed greater or equal comparison | |||
1283 | /// | |||
1284 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1285 | /// validity of the greater-or-equal relationship. | |||
1286 | /// | |||
1287 | /// \returns true if *this >= RHS when both are considered signed. | |||
1288 | bool sge(const APInt &RHS) const { return !slt(RHS); } | |||
1289 | ||||
1290 | /// \brief Signed greater or equal comparison | |||
1291 | /// | |||
1292 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1293 | /// the validity of the greater-or-equal relationship. | |||
1294 | /// | |||
1295 | /// \returns true if *this >= RHS when considered signed. | |||
1296 | bool sge(int64_t RHS) const { return !slt(RHS); } | |||
1297 | ||||
1298 | /// This operation tests if there are any pairs of corresponding bits | |||
1299 | /// between this APInt and RHS that are both set. | |||
1300 | bool intersects(const APInt &RHS) const { | |||
1301 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth && "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1301, __extension__ __PRETTY_FUNCTION__)); | |||
1302 | if (isSingleWord()) | |||
1303 | return (U.VAL & RHS.U.VAL) != 0; | |||
1304 | return intersectsSlowCase(RHS); | |||
1305 | } | |||
1306 | ||||
1307 | /// This operation checks that all bits set in this APInt are also set in RHS. | |||
1308 | bool isSubsetOf(const APInt &RHS) const { | |||
1309 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth && "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1309, __extension__ __PRETTY_FUNCTION__)); | |||
1310 | if (isSingleWord()) | |||
1311 | return (U.VAL & ~RHS.U.VAL) == 0; | |||
1312 | return isSubsetOfSlowCase(RHS); | |||
1313 | } | |||
1314 | ||||
1315 | /// @} | |||
1316 | /// \name Resizing Operators | |||
1317 | /// @{ | |||
1318 | ||||
1319 | /// \brief Truncate to new width. | |||
1320 | /// | |||
1321 | /// Truncate the APInt to a specified width. It is an error to specify a width | |||
1322 | /// that is greater than or equal to the current width. | |||
1323 | APInt trunc(unsigned width) const; | |||
1324 | ||||
1325 | /// \brief Sign extend to a new width. | |||
1326 | /// | |||
1327 | /// This operation sign extends the APInt to a new width. If the high order | |||
1328 | /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. | |||
1329 | /// It is an error to specify a width that is less than or equal to the | |||
1330 | /// current width. | |||
1331 | APInt sext(unsigned width) const; | |||
1332 | ||||
1333 | /// \brief Zero extend to a new width. | |||
1334 | /// | |||
1335 | /// This operation zero extends the APInt to a new width. The high order bits | |||
1336 | /// are filled with 0 bits. It is an error to specify a width that is less | |||
1337 | /// than or equal to the current width. | |||
1338 | APInt zext(unsigned width) const; | |||
1339 | ||||
1340 | /// \brief Sign extend or truncate to width | |||
1341 | /// | |||
1342 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
1343 | /// extended, truncated, or left alone to make it that width. | |||
1344 | APInt sextOrTrunc(unsigned width) const; | |||
1345 | ||||
1346 | /// \brief Zero extend or truncate to width | |||
1347 | /// | |||
1348 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
1349 | /// extended, truncated, or left alone to make it that width. | |||
1350 | APInt zextOrTrunc(unsigned width) const; | |||
1351 | ||||
1352 | /// \brief Sign extend or truncate to width | |||
1353 | /// | |||
1354 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
1355 | /// extended, or left alone to make it that width. | |||
1356 | APInt sextOrSelf(unsigned width) const; | |||
1357 | ||||
1358 | /// \brief Zero extend or truncate to width | |||
1359 | /// | |||
1360 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
1361 | /// extended, or left alone to make it that width. | |||
1362 | APInt zextOrSelf(unsigned width) const; | |||
1363 | ||||
1364 | /// @} | |||
1365 | /// \name Bit Manipulation Operators | |||
1366 | /// @{ | |||
1367 | ||||
1368 | /// \brief Set every bit to 1. | |||
1369 | void setAllBits() { | |||
1370 | if (isSingleWord()) | |||
1371 | U.VAL = WORD_MAX; | |||
1372 | else | |||
1373 | // Set all the bits in all the words. | |||
1374 | memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); | |||
1375 | // Clear the unused ones | |||
1376 | clearUnusedBits(); | |||
1377 | } | |||
1378 | ||||
1379 | /// \brief Set a given bit to 1. | |||
1380 | /// | |||
1381 | /// Set the given bit to 1 whose position is given as "bitPosition". | |||
1382 | void setBit(unsigned BitPosition) { | |||
1383 | assert(BitPosition <= BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition <= BitWidth && "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition <= BitWidth && \"BitPosition out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1383, __extension__ __PRETTY_FUNCTION__)); | |||
1384 | WordType Mask = maskBit(BitPosition); | |||
1385 | if (isSingleWord()) | |||
1386 | U.VAL |= Mask; | |||
1387 | else | |||
1388 | U.pVal[whichWord(BitPosition)] |= Mask; | |||
1389 | } | |||
1390 | ||||
1391 | /// Set the sign bit to 1. | |||
1392 | void setSignBit() { | |||
1393 | setBit(BitWidth - 1); | |||
1394 | } | |||
1395 | ||||
1396 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. | |||
1397 | void setBits(unsigned loBit, unsigned hiBit) { | |||
1398 | assert(hiBit <= BitWidth && "hiBit out of range")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range" ) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1398, __extension__ __PRETTY_FUNCTION__)); | |||
1399 | assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range" ) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1399, __extension__ __PRETTY_FUNCTION__)); | |||
1400 | assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast <bool> (loBit <= hiBit && "loBit greater than hiBit" ) ? void (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1400, __extension__ __PRETTY_FUNCTION__)); | |||
1401 | if (loBit == hiBit) | |||
1402 | return; | |||
1403 | if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { | |||
1404 | uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); | |||
1405 | mask <<= loBit; | |||
1406 | if (isSingleWord()) | |||
1407 | U.VAL |= mask; | |||
1408 | else | |||
1409 | U.pVal[0] |= mask; | |||
1410 | } else { | |||
1411 | setBitsSlowCase(loBit, hiBit); | |||
1412 | } | |||
1413 | } | |||
1414 | ||||
1415 | /// Set the top bits starting from loBit. | |||
1416 | void setBitsFrom(unsigned loBit) { | |||
1417 | return setBits(loBit, BitWidth); | |||
1418 | } | |||
1419 | ||||
1420 | /// Set the bottom loBits bits. | |||
1421 | void setLowBits(unsigned loBits) { | |||
1422 | return setBits(0, loBits); | |||
1423 | } | |||
1424 | ||||
1425 | /// Set the top hiBits bits. | |||
1426 | void setHighBits(unsigned hiBits) { | |||
1427 | return setBits(BitWidth - hiBits, BitWidth); | |||
1428 | } | |||
1429 | ||||
1430 | /// \brief Set every bit to 0. | |||
1431 | void clearAllBits() { | |||
1432 | if (isSingleWord()) | |||
1433 | U.VAL = 0; | |||
1434 | else | |||
1435 | memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); | |||
1436 | } | |||
1437 | ||||
1438 | /// \brief Set a given bit to 0. | |||
1439 | /// | |||
1440 | /// Set the given bit to 0 whose position is given as "bitPosition". | |||
1441 | void clearBit(unsigned BitPosition) { | |||
1442 | assert(BitPosition <= BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition <= BitWidth && "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition <= BitWidth && \"BitPosition out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1442, __extension__ __PRETTY_FUNCTION__)); | |||
1443 | WordType Mask = ~maskBit(BitPosition); | |||
1444 | if (isSingleWord()) | |||
1445 | U.VAL &= Mask; | |||
1446 | else | |||
1447 | U.pVal[whichWord(BitPosition)] &= Mask; | |||
1448 | } | |||
1449 | ||||
1450 | /// Set the sign bit to 0. | |||
1451 | void clearSignBit() { | |||
1452 | clearBit(BitWidth - 1); | |||
1453 | } | |||
1454 | ||||
1455 | /// \brief Toggle every bit to its opposite value. | |||
1456 | void flipAllBits() { | |||
1457 | if (isSingleWord()) { | |||
1458 | U.VAL ^= WORD_MAX; | |||
1459 | clearUnusedBits(); | |||
1460 | } else { | |||
1461 | flipAllBitsSlowCase(); | |||
1462 | } | |||
1463 | } | |||
1464 | ||||
1465 | /// \brief Toggles a given bit to its opposite value. | |||
1466 | /// | |||
1467 | /// Toggle a given bit to its opposite value whose position is given | |||
1468 | /// as "bitPosition". | |||
1469 | void flipBit(unsigned bitPosition); | |||
1470 | ||||
1471 | /// Negate this APInt in place. | |||
1472 | void negate() { | |||
1473 | flipAllBits(); | |||
1474 | ++(*this); | |||
1475 | } | |||
1476 | ||||
1477 | /// Insert the bits from a smaller APInt starting at bitPosition. | |||
1478 | void insertBits(const APInt &SubBits, unsigned bitPosition); | |||
1479 | ||||
1480 | /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). | |||
1481 | APInt extractBits(unsigned numBits, unsigned bitPosition) const; | |||
1482 | ||||
1483 | /// @} | |||
1484 | /// \name Value Characterization Functions | |||
1485 | /// @{ | |||
1486 | ||||
1487 | /// \brief Return the number of bits in the APInt. | |||
1488 | unsigned getBitWidth() const { return BitWidth; } | |||
1489 | ||||
1490 | /// \brief Get the number of words. | |||
1491 | /// | |||
1492 | /// Here one word's bitwidth equals to that of uint64_t. | |||
1493 | /// | |||
1494 | /// \returns the number of words to hold the integer value of this APInt. | |||
1495 | unsigned getNumWords() const { return getNumWords(BitWidth); } | |||
1496 | ||||
1497 | /// \brief Get the number of words. | |||
1498 | /// | |||
1499 | /// *NOTE* Here one word's bitwidth equals to that of uint64_t. | |||
1500 | /// | |||
1501 | /// \returns the number of words to hold the integer value with a given bit | |||
1502 | /// width. | |||
1503 | static unsigned getNumWords(unsigned BitWidth) { | |||
1504 | return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; | |||
1505 | } | |||
1506 | ||||
1507 | /// \brief Compute the number of active bits in the value | |||
1508 | /// | |||
1509 | /// This function returns the number of active bits which is defined as the | |||
1510 | /// bit width minus the number of leading zeros. This is used in several | |||
1511 | /// computations to see how "wide" the value is. | |||
1512 | unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); } | |||
1513 | ||||
1514 | /// \brief Compute the number of active words in the value of this APInt. | |||
1515 | /// | |||
1516 | /// This is used in conjunction with getActiveData to extract the raw value of | |||
1517 | /// the APInt. | |||
1518 | unsigned getActiveWords() const { | |||
1519 | unsigned numActiveBits = getActiveBits(); | |||
1520 | return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; | |||
1521 | } | |||
1522 | ||||
1523 | /// \brief Get the minimum bit size for this signed APInt | |||
1524 | /// | |||
1525 | /// Computes the minimum bit width for this APInt while considering it to be a | |||
1526 | /// signed (and probably negative) value. If the value is not negative, this | |||
1527 | /// function returns the same value as getActiveBits()+1. Otherwise, it | |||
1528 | /// returns the smallest bit width that will retain the negative value. For | |||
1529 | /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so | |||
1530 | /// for -1, this function will always return 1. | |||
1531 | unsigned getMinSignedBits() const { | |||
1532 | if (isNegative()) | |||
1533 | return BitWidth - countLeadingOnes() + 1; | |||
1534 | return getActiveBits() + 1; | |||
1535 | } | |||
1536 | ||||
1537 | /// \brief Get zero extended value | |||
1538 | /// | |||
1539 | /// This method attempts to return the value of this APInt as a zero extended | |||
1540 | /// uint64_t. The bitwidth must be <= 64 or the value must fit within a | |||
1541 | /// uint64_t. Otherwise an assertion will result. | |||
1542 | uint64_t getZExtValue() const { | |||
1543 | if (isSingleWord()) | |||
1544 | return U.VAL; | |||
1545 | assert(getActiveBits() <= 64 && "Too many bits for uint64_t")(static_cast <bool> (getActiveBits() <= 64 && "Too many bits for uint64_t") ? void (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1545, __extension__ __PRETTY_FUNCTION__)); | |||
1546 | return U.pVal[0]; | |||
1547 | } | |||
1548 | ||||
1549 | /// \brief Get sign extended value | |||
1550 | /// | |||
1551 | /// This method attempts to return the value of this APInt as a sign extended | |||
1552 | /// int64_t. The bit width must be <= 64 or the value must fit within an | |||
1553 | /// int64_t. Otherwise an assertion will result. | |||
1554 | int64_t getSExtValue() const { | |||
1555 | if (isSingleWord()) | |||
1556 | return SignExtend64(U.VAL, BitWidth); | |||
1557 | assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")(static_cast <bool> (getMinSignedBits() <= 64 && "Too many bits for int64_t") ? void (0) : __assert_fail ("getMinSignedBits() <= 64 && \"Too many bits for int64_t\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/APInt.h" , 1557, __extension__ __PRETTY_FUNCTION__)); | |||
1558 | return int64_t(U.pVal[0]); | |||
1559 | } | |||
1560 | ||||
1561 | /// \brief Get bits required for string value. | |||
1562 | /// | |||
1563 | /// This method determines how many bits are required to hold the APInt | |||
1564 | /// equivalent of the string given by \p str. | |||
1565 | static unsigned getBitsNeeded(StringRef str, uint8_t radix); | |||
1566 | ||||
1567 | /// \brief The APInt version of the countLeadingZeros functions in | |||
1568 | /// MathExtras.h. | |||
1569 | /// | |||
1570 | /// It counts the number of zeros from the most significant bit to the first | |||
1571 | /// one bit. | |||
1572 | /// | |||
1573 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
1574 | /// zeros from the most significant bit to the first one bits. | |||
1575 | unsigned countLeadingZeros() const { | |||
1576 | if (isSingleWord()) { | |||
1577 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; | |||
1578 | return llvm::countLeadingZeros(U.VAL) - unusedBits; | |||
1579 | } | |||
1580 | return countLeadingZerosSlowCase(); | |||
1581 | } | |||
1582 | ||||
1583 | /// \brief Count the number of leading one bits. | |||
1584 | /// | |||
1585 | /// This function is an APInt version of the countLeadingOnes | |||
1586 | /// functions in MathExtras.h. It counts the number of ones from the most | |||
1587 | /// significant bit to the first zero bit. | |||
1588 | /// | |||
1589 | /// \returns 0 if the high order bit is not set, otherwise returns the number | |||
1590 | /// of 1 bits from the most significant to the least | |||
1591 | unsigned countLeadingOnes() const { | |||
1592 | if (isSingleWord()) | |||
1593 | return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); | |||
1594 | return countLeadingOnesSlowCase(); | |||
1595 | } | |||
1596 | ||||
1597 | /// Computes the number of leading bits of this APInt that are equal to its | |||
1598 | /// sign bit. | |||
1599 | unsigned getNumSignBits() const { | |||
1600 | return isNegative() ? countLeadingOnes() : countLeadingZeros(); | |||
1601 | } | |||
1602 | ||||
1603 | /// \brief Count the number of trailing zero bits. | |||
1604 | /// | |||
1605 | /// This function is an APInt version of the countTrailingZeros | |||
1606 | /// functions in MathExtras.h. It counts the number of zeros from the least | |||
1607 | /// significant bit to the first set bit. | |||
1608 | /// | |||
1609 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
1610 | /// zeros from the least significant bit to the first one bit. | |||
1611 | unsigned countTrailingZeros() const { | |||
1612 | if (isSingleWord()) | |||
1613 | return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth); | |||
1614 | return countTrailingZerosSlowCase(); | |||
1615 | } | |||
1616 | ||||
1617 | /// \brief Count the number of trailing one bits. | |||
1618 | /// | |||
1619 | /// This function is an APInt version of the countTrailingOnes | |||
1620 | /// functions in MathExtras.h. It counts the number of ones from the least | |||
1621 | /// significant bit to the first zero bit. | |||
1622 | /// | |||
1623 | /// \returns BitWidth if the value is all ones, otherwise returns the number | |||
1624 | /// of ones from the least significant bit to the first zero bit. | |||
1625 | unsigned countTrailingOnes() const { | |||
1626 | if (isSingleWord()) | |||
1627 | return llvm::countTrailingOnes(U.VAL); | |||
1628 | return countTrailingOnesSlowCase(); | |||
1629 | } | |||
1630 | ||||
1631 | /// \brief Count the number of bits set. | |||
1632 | /// | |||
1633 | /// This function is an APInt version of the countPopulation functions | |||
1634 | /// in MathExtras.h. It counts the number of 1 bits in the APInt value. | |||
1635 | /// | |||
1636 | /// \returns 0 if the value is zero, otherwise returns the number of set bits. | |||
1637 | unsigned countPopulation() const { | |||
1638 | if (isSingleWord()) | |||
1639 | return llvm::countPopulation(U.VAL); | |||
1640 | return countPopulationSlowCase(); | |||
1641 | } | |||
1642 | ||||
1643 | /// @} | |||
1644 | /// \name Conversion Functions | |||
1645 | /// @{ | |||
1646 | void print(raw_ostream &OS, bool isSigned) const; | |||
1647 | ||||
1648 | /// Converts an APInt to a string and append it to Str. Str is commonly a | |||
1649 | /// SmallString. | |||
1650 | void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, | |||
1651 | bool formatAsCLiteral = false) const; | |||
1652 | ||||
1653 | /// Considers the APInt to be unsigned and converts it into a string in the | |||
1654 | /// radix given. The radix can be 2, 8, 10 16, or 36. | |||
1655 | void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
1656 | toString(Str, Radix, false, false); | |||
1657 | } | |||
1658 | ||||
1659 | /// Considers the APInt to be signed and converts it into a string in the | |||
1660 | /// radix given. The radix can be 2, 8, 10, 16, or 36. | |||
1661 | void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
1662 | toString(Str, Radix, true, false); | |||
1663 | } | |||
1664 | ||||
1665 | /// \brief Return the APInt as a std::string. | |||
1666 | /// | |||
1667 | /// Note that this is an inefficient method. It is better to pass in a | |||
1668 | /// SmallVector/SmallString to the methods above to avoid thrashing the heap | |||
1669 | /// for the string. | |||
1670 | std::string toString(unsigned Radix, bool Signed) const; | |||
1671 | ||||
1672 | /// \returns a byte-swapped representation of this APInt Value. | |||
1673 | APInt byteSwap() const; | |||
1674 | ||||
1675 | /// \returns the value with the bit representation reversed of this APInt | |||
1676 | /// Value. | |||
1677 | APInt reverseBits() const; | |||
1678 | ||||
1679 | /// \brief Converts this APInt to a double value. | |||
1680 | double roundToDouble(bool isSigned) const; | |||
1681 | ||||
1682 | /// \brief Converts this unsigned APInt to a double value. | |||
1683 | double roundToDouble() const { return roundToDouble(false); } | |||
1684 | ||||
1685 | /// \brief Converts this signed APInt to a double value. | |||
1686 | double signedRoundToDouble() const { return roundToDouble(true); } | |||
1687 | ||||
1688 | /// \brief Converts APInt bits to a double | |||
1689 | /// | |||
1690 | /// The conversion does not do a translation from integer to double, it just | |||
1691 | /// re-interprets the bits as a double. Note that it is valid to do this on | |||
1692 | /// any bit width. Exactly 64 bits will be translated. | |||
1693 | double bitsToDouble() const { | |||
1694 | return BitsToDouble(getWord(0)); | |||
1695 | } | |||
1696 | ||||
1697 | /// \brief Converts APInt bits to a double | |||
1698 | /// | |||
1699 | /// The conversion does not do a translation from integer to float, it just | |||
1700 | /// re-interprets the bits as a float. Note that it is valid to do this on | |||
1701 | /// any bit width. Exactly 32 bits will be translated. | |||
1702 | float bitsToFloat() const { | |||
1703 | return BitsToFloat(getWord(0)); | |||
1704 | } | |||
1705 | ||||
1706 | /// \brief Converts a double to APInt bits. | |||
1707 | /// | |||
1708 | /// The conversion does not do a translation from double to integer, it just | |||
1709 | /// re-interprets the bits of the double. | |||
1710 | static APInt doubleToBits(double V) { | |||
1711 | return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V)); | |||
1712 | } | |||
1713 | ||||
1714 | /// \brief Converts a float to APInt bits. | |||
1715 | /// | |||
1716 | /// The conversion does not do a translation from float to integer, it just | |||
1717 | /// re-interprets the bits of the float. | |||
1718 | static APInt floatToBits(float V) { | |||
1719 | return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V)); | |||
1720 | } | |||
1721 | ||||
1722 | /// @} | |||
1723 | /// \name Mathematics Operations | |||
1724 | /// @{ | |||
1725 | ||||
1726 | /// \returns the floor log base 2 of this APInt. | |||
1727 | unsigned logBase2() const { return getActiveBits() - 1; } | |||
1728 | ||||
1729 | /// \returns the ceil log base 2 of this APInt. | |||
1730 | unsigned ceilLogBase2() const { | |||
1731 | APInt temp(*this); | |||
1732 | --temp; | |||
1733 | return temp.getActiveBits(); | |||
1734 | } | |||
1735 | ||||
1736 | /// \returns the nearest log base 2 of this APInt. Ties round up. | |||
1737 | /// | |||
1738 | /// NOTE: When we have a BitWidth of 1, we define: | |||
1739 | /// | |||
1740 | /// log2(0) = UINT32_MAX | |||
1741 | /// log2(1) = 0 | |||
1742 | /// | |||
1743 | /// to get around any mathematical concerns resulting from | |||
1744 | /// referencing 2 in a space where 2 does no exist. | |||
1745 | unsigned nearestLogBase2() const { | |||
1746 | // Special case when we have a bitwidth of 1. If VAL is 1, then we | |||
1747 | // get 0. If VAL is 0, we get WORD_MAX which gets truncated to | |||
1748 | // UINT32_MAX. | |||
1749 | if (BitWidth == 1) | |||
1750 | return U.VAL - 1; | |||
1751 | ||||
1752 | // Handle the zero case. | |||
1753 | if (isNullValue()) | |||
1754 | return UINT32_MAX(4294967295U); | |||
1755 | ||||
1756 | // The non-zero case is handled by computing: | |||
1757 | // | |||
1758 | // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. | |||
1759 | // | |||
1760 | // where x[i] is referring to the value of the ith bit of x. | |||
1761 | unsigned lg = logBase2(); | |||
1762 | return lg + unsigned((*this)[lg - 1]); | |||
1763 | } | |||
1764 | ||||
1765 | /// \returns the log base 2 of this APInt if its an exact power of two, -1 | |||
1766 | /// otherwise | |||
1767 | int32_t exactLogBase2() const { | |||
1768 | if (!isPowerOf2()) | |||
1769 | return -1; | |||
1770 | return logBase2(); | |||
1771 | } | |||
1772 | ||||
1773 | /// \brief Compute the square root | |||
1774 | APInt sqrt() const; | |||
1775 | ||||
1776 | /// \brief Get the absolute value; | |||
1777 | /// | |||
1778 | /// If *this is < 0 then return -(*this), otherwise *this; | |||
1779 | APInt abs() const { | |||
1780 | if (isNegative()) | |||
1781 | return -(*this); | |||
1782 | return *this; | |||
1783 | } | |||
1784 | ||||
1785 | /// \returns the multiplicative inverse for a given modulo. | |||
1786 | APInt multiplicativeInverse(const APInt &modulo) const; | |||
1787 | ||||
1788 | /// @} | |||
1789 | /// \name Support for division by constant | |||
1790 | /// @{ | |||
1791 | ||||
1792 | /// Calculate the magic number for signed division by a constant. | |||
1793 | struct ms; | |||
1794 | ms magic() const; | |||
1795 | ||||
1796 | /// Calculate the magic number for unsigned division by a constant. | |||
1797 | struct mu; | |||
1798 | mu magicu(unsigned LeadingZeros = 0) const; | |||
1799 | ||||
1800 | /// @} | |||
1801 | /// \name Building-block Operations for APInt and APFloat | |||
1802 | /// @{ | |||
1803 | ||||
1804 | // These building block operations operate on a representation of arbitrary | |||
1805 | // precision, two's-complement, bignum integer values. They should be | |||
1806 | // sufficient to implement APInt and APFloat bignum requirements. Inputs are | |||
1807 | // generally a pointer to the base of an array of integer parts, representing | |||
1808 | // an unsigned bignum, and a count of how many parts there are. | |||
1809 | ||||
1810 | /// Sets the least significant part of a bignum to the input value, and zeroes | |||
1811 | /// out higher parts. | |||
1812 | static void tcSet(WordType *, WordType, unsigned); | |||
1813 | ||||
1814 | /// Assign one bignum to another. | |||
1815 | static void tcAssign(WordType *, const WordType *, unsigned); | |||
1816 | ||||
1817 | /// Returns true if a bignum is zero, false otherwise. | |||
1818 | static bool tcIsZero(const WordType *, unsigned); | |||
1819 | ||||
1820 | /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. | |||
1821 | static int tcExtractBit(const WordType *, unsigned bit); | |||
1822 | ||||
1823 | /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to | |||
1824 | /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least | |||
1825 | /// significant bit of DST. All high bits above srcBITS in DST are | |||
1826 | /// zero-filled. | |||
1827 | static void tcExtract(WordType *, unsigned dstCount, | |||
1828 | const WordType *, unsigned srcBits, | |||
1829 | unsigned srcLSB); | |||
1830 | ||||
1831 | /// Set the given bit of a bignum. Zero-based. | |||
1832 | static void tcSetBit(WordType *, unsigned bit); | |||
1833 | ||||
1834 | /// Clear the given bit of a bignum. Zero-based. | |||
1835 | static void tcClearBit(WordType *, unsigned bit); | |||
1836 | ||||
1837 | /// Returns the bit number of the least or most significant set bit of a | |||
1838 | /// number. If the input number has no bits set -1U is returned. | |||
1839 | static unsigned tcLSB(const WordType *, unsigned n); | |||
1840 | static unsigned tcMSB(const WordType *parts, unsigned n); | |||
1841 | ||||
1842 | /// Negate a bignum in-place. | |||
1843 | static void tcNegate(WordType *, unsigned); | |||
1844 | ||||
1845 | /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
1846 | static WordType tcAdd(WordType *, const WordType *, | |||
1847 | WordType carry, unsigned); | |||
1848 | /// DST += RHS. Returns the carry flag. | |||
1849 | static WordType tcAddPart(WordType *, WordType, unsigned); | |||
1850 | ||||
1851 | /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
1852 | static WordType tcSubtract(WordType *, const WordType *, | |||
1853 | WordType carry, unsigned); | |||
1854 | /// DST -= RHS. Returns the carry flag. | |||
1855 | static WordType tcSubtractPart(WordType *, WordType, unsigned); | |||
1856 | ||||
1857 | /// DST += SRC * MULTIPLIER + PART if add is true | |||
1858 | /// DST = SRC * MULTIPLIER + PART if add is false | |||
1859 | /// | |||
1860 | /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must | |||
1861 | /// start at the same point, i.e. DST == SRC. | |||
1862 | /// | |||
1863 | /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned. | |||
1864 | /// Otherwise DST is filled with the least significant DSTPARTS parts of the | |||
1865 | /// result, and if all of the omitted higher parts were zero return zero, | |||
1866 | /// otherwise overflow occurred and return one. | |||
1867 | static int tcMultiplyPart(WordType *dst, const WordType *src, | |||
1868 | WordType multiplier, WordType carry, | |||
1869 | unsigned srcParts, unsigned dstParts, | |||
1870 | bool add); | |||
1871 | ||||
1872 | /// DST = LHS * RHS, where DST has the same width as the operands and is | |||
1873 | /// filled with the least significant parts of the result. Returns one if | |||
1874 | /// overflow occurred, otherwise zero. DST must be disjoint from both | |||
1875 | /// operands. | |||
1876 | static int tcMultiply(WordType *, const WordType *, const WordType *, | |||
1877 | unsigned); | |||
1878 | ||||
1879 | /// DST = LHS * RHS, where DST has width the sum of the widths of the | |||
1880 | /// operands. No overflow occurs. DST must be disjoint from both operands. | |||
1881 | static void tcFullMultiply(WordType *, const WordType *, | |||
1882 | const WordType *, unsigned, unsigned); | |||
1883 | ||||
1884 | /// If RHS is zero LHS and REMAINDER are left unchanged, return one. | |||
1885 | /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set | |||
1886 | /// REMAINDER to the remainder, return zero. i.e. | |||
1887 | /// | |||
1888 | /// OLD_LHS = RHS * LHS + REMAINDER | |||
1889 | /// | |||
1890 | /// SCRATCH is a bignum of the same size as the operands and result for use by | |||
1891 | /// the routine; its contents need not be initialized and are destroyed. LHS, | |||
1892 | /// REMAINDER and SCRATCH must be distinct. | |||
1893 | static int tcDivide(WordType *lhs, const WordType *rhs, | |||
1894 | WordType *remainder, WordType *scratch, | |||
1895 | unsigned parts); | |||
1896 | ||||
1897 | /// Shift a bignum left Count bits. Shifted in bits are zero. There are no | |||
1898 | /// restrictions on Count. | |||
1899 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); | |||
1900 | ||||
1901 | /// Shift a bignum right Count bits. Shifted in bits are zero. There are no | |||
1902 | /// restrictions on Count. | |||
1903 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); | |||
1904 | ||||
1905 | /// The obvious AND, OR and XOR and complement operations. | |||
1906 | static void tcAnd(WordType *, const WordType *, unsigned); | |||
1907 | static void tcOr(WordType *, const WordType *, unsigned); | |||
1908 | static void tcXor(WordType *, const WordType *, unsigned); | |||
1909 | static void tcComplement(WordType *, unsigned); | |||
1910 | ||||
1911 | /// Comparison (unsigned) of two bignums. | |||
1912 | static int tcCompare(const WordType *, const WordType *, unsigned); | |||
1913 | ||||
1914 | /// Increment a bignum in-place. Return the carry flag. | |||
1915 | static WordType tcIncrement(WordType *dst, unsigned parts) { | |||
1916 | return tcAddPart(dst, 1, parts); | |||
1917 | } | |||
1918 | ||||
1919 | /// Decrement a bignum in-place. Return the borrow flag. | |||
1920 | static WordType tcDecrement(WordType *dst, unsigned parts) { | |||
1921 | return tcSubtractPart(dst, 1, parts); | |||
1922 | } | |||
1923 | ||||
1924 | /// Set the least significant BITS and clear the rest. | |||
1925 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); | |||
1926 | ||||
1927 | /// \brief debug method | |||
1928 | void dump() const; | |||
1929 | ||||
1930 | /// @} | |||
1931 | }; | |||
1932 | ||||
1933 | /// Magic data for optimising signed division by a constant. | |||
1934 | struct APInt::ms { | |||
1935 | APInt m; ///< magic number | |||
1936 | unsigned s; ///< shift amount | |||
1937 | }; | |||
1938 | ||||
1939 | /// Magic data for optimising unsigned division by a constant. | |||
1940 | struct APInt::mu { | |||
1941 | APInt m; ///< magic number | |||
1942 | bool a; ///< add indicator | |||
1943 | unsigned s; ///< shift amount | |||
1944 | }; | |||
1945 | ||||
1946 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } | |||
1947 | ||||
1948 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } | |||
1949 | ||||
1950 | /// \brief Unary bitwise complement operator. | |||
1951 | /// | |||
1952 | /// \returns an APInt that is the bitwise complement of \p v. | |||
1953 | inline APInt operator~(APInt v) { | |||
1954 | v.flipAllBits(); | |||
1955 | return v; | |||
1956 | } | |||
1957 | ||||
1958 | inline APInt operator&(APInt a, const APInt &b) { | |||
1959 | a &= b; | |||
1960 | return a; | |||
1961 | } | |||
1962 | ||||
1963 | inline APInt operator&(const APInt &a, APInt &&b) { | |||
1964 | b &= a; | |||
1965 | return std::move(b); | |||
1966 | } | |||
1967 | ||||
1968 | inline APInt operator&(APInt a, uint64_t RHS) { | |||
1969 | a &= RHS; | |||
1970 | return a; | |||
1971 | } | |||
1972 | ||||
1973 | inline APInt operator&(uint64_t LHS, APInt b) { | |||
1974 | b &= LHS; | |||
1975 | return b; | |||
1976 | } | |||
1977 | ||||
1978 | inline APInt operator|(APInt a, const APInt &b) { | |||
1979 | a |= b; | |||
1980 | return a; | |||
1981 | } | |||
1982 | ||||
1983 | inline APInt operator|(const APInt &a, APInt &&b) { | |||
1984 | b |= a; | |||
1985 | return std::move(b); | |||
1986 | } | |||
1987 | ||||
1988 | inline APInt operator|(APInt a, uint64_t RHS) { | |||
1989 | a |= RHS; | |||
1990 | return a; | |||
1991 | } | |||
1992 | ||||
1993 | inline APInt operator|(uint64_t LHS, APInt b) { | |||
1994 | b |= LHS; | |||
1995 | return b; | |||
1996 | } | |||
1997 | ||||
1998 | inline APInt operator^(APInt a, const APInt &b) { | |||
1999 | a ^= b; | |||
2000 | return a; | |||
2001 | } | |||
2002 | ||||
2003 | inline APInt operator^(const APInt &a, APInt &&b) { | |||
2004 | b ^= a; | |||
2005 | return std::move(b); | |||
2006 | } | |||
2007 | ||||
2008 | inline APInt operator^(APInt a, uint64_t RHS) { | |||
2009 | a ^= RHS; | |||
2010 | return a; | |||
2011 | } | |||
2012 | ||||
2013 | inline APInt operator^(uint64_t LHS, APInt b) { | |||
2014 | b ^= LHS; | |||
2015 | return b; | |||
2016 | } | |||
2017 | ||||
2018 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { | |||
2019 | I.print(OS, true); | |||
2020 | return OS; | |||
2021 | } | |||
2022 | ||||
2023 | inline APInt operator-(APInt v) { | |||
2024 | v.negate(); | |||
2025 | return v; | |||
2026 | } | |||
2027 | ||||
2028 | inline APInt operator+(APInt a, const APInt &b) { | |||
2029 | a += b; | |||
2030 | return a; | |||
2031 | } | |||
2032 | ||||
2033 | inline APInt operator+(const APInt &a, APInt &&b) { | |||
2034 | b += a; | |||
2035 | return std::move(b); | |||
2036 | } | |||
2037 | ||||
2038 | inline APInt operator+(APInt a, uint64_t RHS) { | |||
2039 | a += RHS; | |||
2040 | return a; | |||
2041 | } | |||
2042 | ||||
2043 | inline APInt operator+(uint64_t LHS, APInt b) { | |||
2044 | b += LHS; | |||
2045 | return b; | |||
2046 | } | |||
2047 | ||||
2048 | inline APInt operator-(APInt a, const APInt &b) { | |||
2049 | a -= b; | |||
2050 | return a; | |||
2051 | } | |||
2052 | ||||
2053 | inline APInt operator-(const APInt &a, APInt &&b) { | |||
2054 | b.negate(); | |||
2055 | b += a; | |||
2056 | return std::move(b); | |||
2057 | } | |||
2058 | ||||
2059 | inline APInt operator-(APInt a, uint64_t RHS) { | |||
2060 | a -= RHS; | |||
2061 | return a; | |||
2062 | } | |||
2063 | ||||
2064 | inline APInt operator-(uint64_t LHS, APInt b) { | |||
2065 | b.negate(); | |||
2066 | b += LHS; | |||
2067 | return b; | |||
2068 | } | |||
2069 | ||||
2070 | inline APInt operator*(APInt a, uint64_t RHS) { | |||
2071 | a *= RHS; | |||
2072 | return a; | |||
2073 | } | |||
2074 | ||||
2075 | inline APInt operator*(uint64_t LHS, APInt b) { | |||
2076 | b *= LHS; | |||
2077 | return b; | |||
2078 | } | |||
2079 | ||||
2080 | ||||
2081 | namespace APIntOps { | |||
2082 | ||||
2083 | /// \brief Determine the smaller of two APInts considered to be signed. | |||
2084 | inline const APInt &smin(const APInt &A, const APInt &B) { | |||
2085 | return A.slt(B) ? A : B; | |||
2086 | } | |||
2087 | ||||
2088 | /// \brief Determine the larger of two APInts considered to be signed. | |||
2089 | inline const APInt &smax(const APInt &A, const APInt &B) { | |||
2090 | return A.sgt(B) ? A : B; | |||
2091 | } | |||
2092 | ||||
2093 | /// \brief Determine the smaller of two APInts considered to be signed. | |||
2094 | inline const APInt &umin(const APInt &A, const APInt &B) { | |||
2095 | return A.ult(B) ? A : B; | |||
2096 | } | |||
2097 | ||||
2098 | /// \brief Determine the larger of two APInts considered to be unsigned. | |||
2099 | inline const APInt &umax(const APInt &A, const APInt &B) { | |||
2100 | return A.ugt(B) ? A : B; | |||
2101 | } | |||
2102 | ||||
2103 | /// \brief Compute GCD of two unsigned APInt values. | |||
2104 | /// | |||
2105 | /// This function returns the greatest common divisor of the two APInt values | |||
2106 | /// using Stein's algorithm. | |||
2107 | /// | |||
2108 | /// \returns the greatest common divisor of A and B. | |||
2109 | APInt GreatestCommonDivisor(APInt A, APInt B); | |||
2110 | ||||
2111 | /// \brief Converts the given APInt to a double value. | |||
2112 | /// | |||
2113 | /// Treats the APInt as an unsigned value for conversion purposes. | |||
2114 | inline double RoundAPIntToDouble(const APInt &APIVal) { | |||
2115 | return APIVal.roundToDouble(); | |||
2116 | } | |||
2117 | ||||
2118 | /// \brief Converts the given APInt to a double value. | |||
2119 | /// | |||
2120 | /// Treats the APInt as a signed value for conversion purposes. | |||
2121 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { | |||
2122 | return APIVal.signedRoundToDouble(); | |||
2123 | } | |||
2124 | ||||
2125 | /// \brief Converts the given APInt to a float vlalue. | |||
2126 | inline float RoundAPIntToFloat(const APInt &APIVal) { | |||
2127 | return float(RoundAPIntToDouble(APIVal)); | |||
2128 | } | |||
2129 | ||||
2130 | /// \brief Converts the given APInt to a float value. | |||
2131 | /// | |||
2132 | /// Treast the APInt as a signed value for conversion purposes. | |||
2133 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { | |||
2134 | return float(APIVal.signedRoundToDouble()); | |||
2135 | } | |||
2136 | ||||
2137 | /// \brief Converts the given double value into a APInt. | |||
2138 | /// | |||
2139 | /// This function convert a double value to an APInt value. | |||
2140 | APInt RoundDoubleToAPInt(double Double, unsigned width); | |||
2141 | ||||
2142 | /// \brief Converts a float value into a APInt. | |||
2143 | /// | |||
2144 | /// Converts a float value into an APInt value. | |||
2145 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { | |||
2146 | return RoundDoubleToAPInt(double(Float), width); | |||
2147 | } | |||
2148 | ||||
2149 | } // End of APIntOps namespace | |||
2150 | ||||
2151 | // See friend declaration above. This additional declaration is required in | |||
2152 | // order to compile LLVM with IBM xlC compiler. | |||
2153 | hash_code hash_value(const APInt &Arg); | |||
2154 | } // End of llvm namespace | |||
2155 | ||||
2156 | #endif |