File: | llvm/include/llvm/ADT/APInt.h |
Warning: | line 927, column 15 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// | ||||
2 | // | ||||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||
4 | // See https://llvm.org/LICENSE.txt for license information. | ||||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||
6 | // | ||||
7 | //===----------------------------------------------------------------------===// | ||||
8 | // | ||||
9 | // This file defines the primary stateless implementation of the | ||||
10 | // Alias Analysis interface that implements identities (two different | ||||
11 | // globals cannot alias, etc), but does no stateful analysis. | ||||
12 | // | ||||
13 | //===----------------------------------------------------------------------===// | ||||
14 | |||||
15 | #include "llvm/Analysis/BasicAliasAnalysis.h" | ||||
16 | #include "llvm/ADT/APInt.h" | ||||
17 | #include "llvm/ADT/ScopeExit.h" | ||||
18 | #include "llvm/ADT/SmallPtrSet.h" | ||||
19 | #include "llvm/ADT/SmallVector.h" | ||||
20 | #include "llvm/ADT/Statistic.h" | ||||
21 | #include "llvm/Analysis/AliasAnalysis.h" | ||||
22 | #include "llvm/Analysis/AssumptionCache.h" | ||||
23 | #include "llvm/Analysis/CFG.h" | ||||
24 | #include "llvm/Analysis/CaptureTracking.h" | ||||
25 | #include "llvm/Analysis/InstructionSimplify.h" | ||||
26 | #include "llvm/Analysis/LoopInfo.h" | ||||
27 | #include "llvm/Analysis/MemoryBuiltins.h" | ||||
28 | #include "llvm/Analysis/MemoryLocation.h" | ||||
29 | #include "llvm/Analysis/PhiValues.h" | ||||
30 | #include "llvm/Analysis/TargetLibraryInfo.h" | ||||
31 | #include "llvm/Analysis/ValueTracking.h" | ||||
32 | #include "llvm/IR/Argument.h" | ||||
33 | #include "llvm/IR/Attributes.h" | ||||
34 | #include "llvm/IR/Constant.h" | ||||
35 | #include "llvm/IR/Constants.h" | ||||
36 | #include "llvm/IR/DataLayout.h" | ||||
37 | #include "llvm/IR/DerivedTypes.h" | ||||
38 | #include "llvm/IR/Dominators.h" | ||||
39 | #include "llvm/IR/Function.h" | ||||
40 | #include "llvm/IR/GetElementPtrTypeIterator.h" | ||||
41 | #include "llvm/IR/GlobalAlias.h" | ||||
42 | #include "llvm/IR/GlobalVariable.h" | ||||
43 | #include "llvm/IR/InstrTypes.h" | ||||
44 | #include "llvm/IR/Instruction.h" | ||||
45 | #include "llvm/IR/Instructions.h" | ||||
46 | #include "llvm/IR/IntrinsicInst.h" | ||||
47 | #include "llvm/IR/Intrinsics.h" | ||||
48 | #include "llvm/IR/Metadata.h" | ||||
49 | #include "llvm/IR/Operator.h" | ||||
50 | #include "llvm/IR/Type.h" | ||||
51 | #include "llvm/IR/User.h" | ||||
52 | #include "llvm/IR/Value.h" | ||||
53 | #include "llvm/InitializePasses.h" | ||||
54 | #include "llvm/Pass.h" | ||||
55 | #include "llvm/Support/Casting.h" | ||||
56 | #include "llvm/Support/CommandLine.h" | ||||
57 | #include "llvm/Support/Compiler.h" | ||||
58 | #include "llvm/Support/KnownBits.h" | ||||
59 | #include <cassert> | ||||
60 | #include <cstdint> | ||||
61 | #include <cstdlib> | ||||
62 | #include <utility> | ||||
63 | |||||
64 | #define DEBUG_TYPE"basicaa" "basicaa" | ||||
65 | |||||
66 | using namespace llvm; | ||||
67 | |||||
68 | /// Enable analysis of recursive PHI nodes. | ||||
69 | static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, | ||||
70 | cl::init(true)); | ||||
71 | |||||
72 | /// By default, even on 32-bit architectures we use 64-bit integers for | ||||
73 | /// calculations. This will allow us to more-aggressively decompose indexing | ||||
74 | /// expressions calculated using i64 values (e.g., long long in C) which is | ||||
75 | /// common enough to worry about. | ||||
76 | static cl::opt<bool> ForceAtLeast64Bits("basic-aa-force-at-least-64b", | ||||
77 | cl::Hidden, cl::init(true)); | ||||
78 | static cl::opt<bool> DoubleCalcBits("basic-aa-double-calc-bits", | ||||
79 | cl::Hidden, cl::init(false)); | ||||
80 | |||||
81 | /// SearchLimitReached / SearchTimes shows how often the limit of | ||||
82 | /// to decompose GEPs is reached. It will affect the precision | ||||
83 | /// of basic alias analysis. | ||||
84 | STATISTIC(SearchLimitReached, "Number of times the limit to "static llvm::Statistic SearchLimitReached = {"basicaa", "SearchLimitReached" , "Number of times the limit to " "decompose GEPs is reached" } | ||||
85 | "decompose GEPs is reached")static llvm::Statistic SearchLimitReached = {"basicaa", "SearchLimitReached" , "Number of times the limit to " "decompose GEPs is reached" }; | ||||
86 | STATISTIC(SearchTimes, "Number of times a GEP is decomposed")static llvm::Statistic SearchTimes = {"basicaa", "SearchTimes" , "Number of times a GEP is decomposed"}; | ||||
87 | |||||
88 | /// Cutoff after which to stop analysing a set of phi nodes potentially involved | ||||
89 | /// in a cycle. Because we are analysing 'through' phi nodes, we need to be | ||||
90 | /// careful with value equivalence. We use reachability to make sure a value | ||||
91 | /// cannot be involved in a cycle. | ||||
92 | const unsigned MaxNumPhiBBsValueReachabilityCheck = 20; | ||||
93 | |||||
94 | // The max limit of the search depth in DecomposeGEPExpression() and | ||||
95 | // getUnderlyingObject(), both functions need to use the same search | ||||
96 | // depth otherwise the algorithm in aliasGEP will assert. | ||||
97 | static const unsigned MaxLookupSearchDepth = 6; | ||||
98 | |||||
99 | bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA, | ||||
100 | FunctionAnalysisManager::Invalidator &Inv) { | ||||
101 | // We don't care if this analysis itself is preserved, it has no state. But | ||||
102 | // we need to check that the analyses it depends on have been. Note that we | ||||
103 | // may be created without handles to some analyses and in that case don't | ||||
104 | // depend on them. | ||||
105 | if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) || | ||||
106 | (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) || | ||||
107 | (LI && Inv.invalidate<LoopAnalysis>(Fn, PA)) || | ||||
108 | (PV && Inv.invalidate<PhiValuesAnalysis>(Fn, PA))) | ||||
109 | return true; | ||||
110 | |||||
111 | // Otherwise this analysis result remains valid. | ||||
112 | return false; | ||||
113 | } | ||||
114 | |||||
115 | //===----------------------------------------------------------------------===// | ||||
116 | // Useful predicates | ||||
117 | //===----------------------------------------------------------------------===// | ||||
118 | |||||
119 | /// Returns true if the pointer is one which would have been considered an | ||||
120 | /// escape by isNonEscapingLocalObject. | ||||
121 | static bool isEscapeSource(const Value *V) { | ||||
122 | if (isa<CallBase>(V)) | ||||
123 | return true; | ||||
124 | |||||
125 | if (isa<Argument>(V)) | ||||
126 | return true; | ||||
127 | |||||
128 | // The load case works because isNonEscapingLocalObject considers all | ||||
129 | // stores to be escapes (it passes true for the StoreCaptures argument | ||||
130 | // to PointerMayBeCaptured). | ||||
131 | if (isa<LoadInst>(V)) | ||||
132 | return true; | ||||
133 | |||||
134 | return false; | ||||
135 | } | ||||
136 | |||||
137 | /// Returns the size of the object specified by V or UnknownSize if unknown. | ||||
138 | static uint64_t getObjectSize(const Value *V, const DataLayout &DL, | ||||
139 | const TargetLibraryInfo &TLI, | ||||
140 | bool NullIsValidLoc, | ||||
141 | bool RoundToAlign = false) { | ||||
142 | uint64_t Size; | ||||
143 | ObjectSizeOpts Opts; | ||||
144 | Opts.RoundToAlign = RoundToAlign; | ||||
145 | Opts.NullIsUnknownSize = NullIsValidLoc; | ||||
146 | if (getObjectSize(V, Size, DL, &TLI, Opts)) | ||||
147 | return Size; | ||||
148 | return MemoryLocation::UnknownSize; | ||||
149 | } | ||||
150 | |||||
151 | /// Returns true if we can prove that the object specified by V is smaller than | ||||
152 | /// Size. | ||||
153 | static bool isObjectSmallerThan(const Value *V, uint64_t Size, | ||||
154 | const DataLayout &DL, | ||||
155 | const TargetLibraryInfo &TLI, | ||||
156 | bool NullIsValidLoc) { | ||||
157 | // Note that the meanings of the "object" are slightly different in the | ||||
158 | // following contexts: | ||||
159 | // c1: llvm::getObjectSize() | ||||
160 | // c2: llvm.objectsize() intrinsic | ||||
161 | // c3: isObjectSmallerThan() | ||||
162 | // c1 and c2 share the same meaning; however, the meaning of "object" in c3 | ||||
163 | // refers to the "entire object". | ||||
164 | // | ||||
165 | // Consider this example: | ||||
166 | // char *p = (char*)malloc(100) | ||||
167 | // char *q = p+80; | ||||
168 | // | ||||
169 | // In the context of c1 and c2, the "object" pointed by q refers to the | ||||
170 | // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. | ||||
171 | // | ||||
172 | // However, in the context of c3, the "object" refers to the chunk of memory | ||||
173 | // being allocated. So, the "object" has 100 bytes, and q points to the middle | ||||
174 | // the "object". In case q is passed to isObjectSmallerThan() as the 1st | ||||
175 | // parameter, before the llvm::getObjectSize() is called to get the size of | ||||
176 | // entire object, we should: | ||||
177 | // - either rewind the pointer q to the base-address of the object in | ||||
178 | // question (in this case rewind to p), or | ||||
179 | // - just give up. It is up to caller to make sure the pointer is pointing | ||||
180 | // to the base address the object. | ||||
181 | // | ||||
182 | // We go for 2nd option for simplicity. | ||||
183 | if (!isIdentifiedObject(V)) | ||||
184 | return false; | ||||
185 | |||||
186 | // This function needs to use the aligned object size because we allow | ||||
187 | // reads a bit past the end given sufficient alignment. | ||||
188 | uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc, | ||||
189 | /*RoundToAlign*/ true); | ||||
190 | |||||
191 | return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size; | ||||
192 | } | ||||
193 | |||||
194 | /// Return the minimal extent from \p V to the end of the underlying object, | ||||
195 | /// assuming the result is used in an aliasing query. E.g., we do use the query | ||||
196 | /// location size and the fact that null pointers cannot alias here. | ||||
197 | static uint64_t getMinimalExtentFrom(const Value &V, | ||||
198 | const LocationSize &LocSize, | ||||
199 | const DataLayout &DL, | ||||
200 | bool NullIsValidLoc) { | ||||
201 | // If we have dereferenceability information we know a lower bound for the | ||||
202 | // extent as accesses for a lower offset would be valid. We need to exclude | ||||
203 | // the "or null" part if null is a valid pointer. | ||||
204 | bool CanBeNull; | ||||
205 | uint64_t DerefBytes = V.getPointerDereferenceableBytes(DL, CanBeNull); | ||||
206 | DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes; | ||||
207 | // If queried with a precise location size, we assume that location size to be | ||||
208 | // accessed, thus valid. | ||||
209 | if (LocSize.isPrecise()) | ||||
210 | DerefBytes = std::max(DerefBytes, LocSize.getValue()); | ||||
211 | return DerefBytes; | ||||
212 | } | ||||
213 | |||||
214 | /// Returns true if we can prove that the object specified by V has size Size. | ||||
215 | static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, | ||||
216 | const TargetLibraryInfo &TLI, bool NullIsValidLoc) { | ||||
217 | uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc); | ||||
218 | return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size; | ||||
219 | } | ||||
220 | |||||
221 | //===----------------------------------------------------------------------===// | ||||
222 | // GetElementPtr Instruction Decomposition and Analysis | ||||
223 | //===----------------------------------------------------------------------===// | ||||
224 | |||||
225 | /// Analyzes the specified value as a linear expression: "A*V + B", where A and | ||||
226 | /// B are constant integers. | ||||
227 | /// | ||||
228 | /// Returns the scale and offset values as APInts and return V as a Value*, and | ||||
229 | /// return whether we looked through any sign or zero extends. The incoming | ||||
230 | /// Value is known to have IntegerType, and it may already be sign or zero | ||||
231 | /// extended. | ||||
232 | /// | ||||
233 | /// Note that this looks through extends, so the high bits may not be | ||||
234 | /// represented in the result. | ||||
235 | /*static*/ const Value *BasicAAResult::GetLinearExpression( | ||||
236 | const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, | ||||
237 | unsigned &SExtBits, const DataLayout &DL, unsigned Depth, | ||||
238 | AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) { | ||||
239 | assert(V->getType()->isIntegerTy() && "Not an integer value")((V->getType()->isIntegerTy() && "Not an integer value" ) ? static_cast<void> (0) : __assert_fail ("V->getType()->isIntegerTy() && \"Not an integer value\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 239, __PRETTY_FUNCTION__)); | ||||
240 | |||||
241 | // Limit our recursion depth. | ||||
242 | if (Depth
| ||||
243 | Scale = 1; | ||||
244 | Offset = 0; | ||||
245 | return V; | ||||
246 | } | ||||
247 | |||||
248 | if (const ConstantInt *Const
| ||||
249 | // If it's a constant, just convert it to an offset and remove the variable. | ||||
250 | // If we've been called recursively, the Offset bit width will be greater | ||||
251 | // than the constant's (the Offset's always as wide as the outermost call), | ||||
252 | // so we'll zext here and process any extension in the isa<SExtInst> & | ||||
253 | // isa<ZExtInst> cases below. | ||||
254 | Offset += Const->getValue().zextOrSelf(Offset.getBitWidth()); | ||||
255 | assert(Scale == 0 && "Constant values don't have a scale")((Scale == 0 && "Constant values don't have a scale") ? static_cast<void> (0) : __assert_fail ("Scale == 0 && \"Constant values don't have a scale\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 255, __PRETTY_FUNCTION__)); | ||||
256 | return V; | ||||
257 | } | ||||
258 | |||||
259 | if (const BinaryOperator *BOp
| ||||
260 | if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { | ||||
261 | // If we've been called recursively, then Offset and Scale will be wider | ||||
262 | // than the BOp operands. We'll always zext it here as we'll process sign | ||||
263 | // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases). | ||||
264 | APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth()); | ||||
265 | |||||
266 | switch (BOp->getOpcode()) { | ||||
267 | default: | ||||
268 | // We don't understand this instruction, so we can't decompose it any | ||||
269 | // further. | ||||
270 | Scale = 1; | ||||
271 | Offset = 0; | ||||
272 | return V; | ||||
273 | case Instruction::Or: | ||||
274 | // X|C == X+C if all the bits in C are unset in X. Otherwise we can't | ||||
275 | // analyze it. | ||||
276 | if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC, | ||||
277 | BOp, DT)) { | ||||
278 | Scale = 1; | ||||
279 | Offset = 0; | ||||
280 | return V; | ||||
281 | } | ||||
282 | LLVM_FALLTHROUGH[[gnu::fallthrough]]; | ||||
283 | case Instruction::Add: | ||||
284 | V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, | ||||
285 | SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); | ||||
286 | Offset += RHS; | ||||
287 | break; | ||||
288 | case Instruction::Sub: | ||||
289 | V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, | ||||
290 | SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); | ||||
291 | Offset -= RHS; | ||||
292 | break; | ||||
293 | case Instruction::Mul: | ||||
294 | V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, | ||||
295 | SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); | ||||
296 | Offset *= RHS; | ||||
297 | Scale *= RHS; | ||||
298 | break; | ||||
299 | case Instruction::Shl: | ||||
300 | V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, | ||||
301 | SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); | ||||
302 | |||||
303 | // We're trying to linearize an expression of the kind: | ||||
304 | // shl i8 -128, 36 | ||||
305 | // where the shift count exceeds the bitwidth of the type. | ||||
306 | // We can't decompose this further (the expression would return | ||||
307 | // a poison value). | ||||
308 | if (Offset.getBitWidth() < RHS.getLimitedValue() || | ||||
309 | Scale.getBitWidth() < RHS.getLimitedValue()) { | ||||
310 | Scale = 1; | ||||
311 | Offset = 0; | ||||
312 | return V; | ||||
313 | } | ||||
314 | |||||
315 | Offset <<= RHS.getLimitedValue(); | ||||
316 | Scale <<= RHS.getLimitedValue(); | ||||
317 | // the semantics of nsw and nuw for left shifts don't match those of | ||||
318 | // multiplications, so we won't propagate them. | ||||
319 | NSW = NUW = false; | ||||
320 | return V; | ||||
321 | } | ||||
322 | |||||
323 | if (isa<OverflowingBinaryOperator>(BOp)) { | ||||
324 | NUW &= BOp->hasNoUnsignedWrap(); | ||||
325 | NSW &= BOp->hasNoSignedWrap(); | ||||
326 | } | ||||
327 | return V; | ||||
328 | } | ||||
329 | } | ||||
330 | |||||
331 | // Since GEP indices are sign extended anyway, we don't care about the high | ||||
332 | // bits of a sign or zero extended value - just scales and offsets. The | ||||
333 | // extensions have to be consistent though. | ||||
334 | if (isa<SExtInst>(V) || isa<ZExtInst>(V)) { | ||||
335 | Value *CastOp = cast<CastInst>(V)->getOperand(0); | ||||
336 | unsigned NewWidth = V->getType()->getPrimitiveSizeInBits(); | ||||
337 | unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); | ||||
338 | unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits; | ||||
339 | const Value *Result = | ||||
340 | GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL, | ||||
341 | Depth + 1, AC, DT, NSW, NUW); | ||||
342 | |||||
343 | // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this | ||||
344 | // by just incrementing the number of bits we've extended by. | ||||
345 | unsigned ExtendedBy = NewWidth - SmallWidth; | ||||
346 | |||||
347 | if (isa<SExtInst>(V) && ZExtBits == 0) { | ||||
348 | // sext(sext(%x, a), b) == sext(%x, a + b) | ||||
349 | |||||
350 | if (NSW) { | ||||
351 | // We haven't sign-wrapped, so it's valid to decompose sext(%x + c) | ||||
352 | // into sext(%x) + sext(c). We'll sext the Offset ourselves: | ||||
353 | unsigned OldWidth = Offset.getBitWidth(); | ||||
354 | Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth); | ||||
355 | } else { | ||||
356 | // We may have signed-wrapped, so don't decompose sext(%x + c) into | ||||
357 | // sext(%x) + sext(c) | ||||
358 | Scale = 1; | ||||
359 | Offset = 0; | ||||
360 | Result = CastOp; | ||||
361 | ZExtBits = OldZExtBits; | ||||
362 | SExtBits = OldSExtBits; | ||||
363 | } | ||||
364 | SExtBits += ExtendedBy; | ||||
365 | } else { | ||||
366 | // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b) | ||||
367 | |||||
368 | if (!NUW) { | ||||
369 | // We may have unsigned-wrapped, so don't decompose zext(%x + c) into | ||||
370 | // zext(%x) + zext(c) | ||||
371 | Scale = 1; | ||||
372 | Offset = 0; | ||||
373 | Result = CastOp; | ||||
374 | ZExtBits = OldZExtBits; | ||||
375 | SExtBits = OldSExtBits; | ||||
376 | } | ||||
377 | ZExtBits += ExtendedBy; | ||||
378 | } | ||||
379 | |||||
380 | return Result; | ||||
381 | } | ||||
382 | |||||
383 | Scale = 1; | ||||
384 | Offset = 0; | ||||
385 | return V; | ||||
386 | } | ||||
387 | |||||
388 | /// To ensure a pointer offset fits in an integer of size PointerSize | ||||
389 | /// (in bits) when that size is smaller than the maximum pointer size. This is | ||||
390 | /// an issue, for example, in particular for 32b pointers with negative indices | ||||
391 | /// that rely on two's complement wrap-arounds for precise alias information | ||||
392 | /// where the maximum pointer size is 64b. | ||||
393 | static APInt adjustToPointerSize(const APInt &Offset, unsigned PointerSize) { | ||||
394 | assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!")((PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!" ) ? static_cast<void> (0) : __assert_fail ("PointerSize <= Offset.getBitWidth() && \"Invalid PointerSize!\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 394, __PRETTY_FUNCTION__)); | ||||
395 | unsigned ShiftBits = Offset.getBitWidth() - PointerSize; | ||||
396 | return (Offset << ShiftBits).ashr(ShiftBits); | ||||
397 | } | ||||
398 | |||||
399 | static unsigned getMaxPointerSize(const DataLayout &DL) { | ||||
400 | unsigned MaxPointerSize = DL.getMaxPointerSizeInBits(); | ||||
401 | if (MaxPointerSize < 64 && ForceAtLeast64Bits) MaxPointerSize = 64; | ||||
402 | if (DoubleCalcBits) MaxPointerSize *= 2; | ||||
403 | |||||
404 | return MaxPointerSize; | ||||
405 | } | ||||
406 | |||||
407 | /// If V is a symbolic pointer expression, decompose it into a base pointer | ||||
408 | /// with a constant offset and a number of scaled symbolic offsets. | ||||
409 | /// | ||||
410 | /// The scaled symbolic offsets (represented by pairs of a Value* and a scale | ||||
411 | /// in the VarIndices vector) are Value*'s that are known to be scaled by the | ||||
412 | /// specified amount, but which may have other unrepresented high bits. As | ||||
413 | /// such, the gep cannot necessarily be reconstructed from its decomposed form. | ||||
414 | /// | ||||
415 | /// This function is capable of analyzing everything that getUnderlyingObject | ||||
416 | /// can look through. To be able to do that getUnderlyingObject and | ||||
417 | /// DecomposeGEPExpression must use the same search depth | ||||
418 | /// (MaxLookupSearchDepth). | ||||
419 | BasicAAResult::DecomposedGEP | ||||
420 | BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, | ||||
421 | AssumptionCache *AC, DominatorTree *DT) { | ||||
422 | // Limit recursion depth to limit compile time in crazy cases. | ||||
423 | unsigned MaxLookup = MaxLookupSearchDepth; | ||||
424 | SearchTimes++; | ||||
425 | |||||
426 | unsigned MaxPointerSize = getMaxPointerSize(DL); | ||||
427 | DecomposedGEP Decomposed; | ||||
428 | Decomposed.Offset = APInt(MaxPointerSize, 0); | ||||
429 | Decomposed.HasCompileTimeConstantScale = true; | ||||
430 | do { | ||||
431 | // See if this is a bitcast or GEP. | ||||
432 | const Operator *Op = dyn_cast<Operator>(V); | ||||
433 | if (!Op) { | ||||
434 | // The only non-operator case we can handle are GlobalAliases. | ||||
435 | if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { | ||||
436 | if (!GA->isInterposable()) { | ||||
437 | V = GA->getAliasee(); | ||||
438 | continue; | ||||
439 | } | ||||
440 | } | ||||
441 | Decomposed.Base = V; | ||||
442 | return Decomposed; | ||||
443 | } | ||||
444 | |||||
445 | if (Op->getOpcode() == Instruction::BitCast || | ||||
446 | Op->getOpcode() == Instruction::AddrSpaceCast) { | ||||
447 | V = Op->getOperand(0); | ||||
448 | continue; | ||||
449 | } | ||||
450 | |||||
451 | const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); | ||||
452 | if (!GEPOp) { | ||||
453 | if (const auto *PHI = dyn_cast<PHINode>(V)) { | ||||
454 | // Look through single-arg phi nodes created by LCSSA. | ||||
455 | if (PHI->getNumIncomingValues() == 1) { | ||||
456 | V = PHI->getIncomingValue(0); | ||||
457 | continue; | ||||
458 | } | ||||
459 | } else if (const auto *Call = dyn_cast<CallBase>(V)) { | ||||
460 | // CaptureTracking can know about special capturing properties of some | ||||
461 | // intrinsics like launder.invariant.group, that can't be expressed with | ||||
462 | // the attributes, but have properties like returning aliasing pointer. | ||||
463 | // Because some analysis may assume that nocaptured pointer is not | ||||
464 | // returned from some special intrinsic (because function would have to | ||||
465 | // be marked with returns attribute), it is crucial to use this function | ||||
466 | // because it should be in sync with CaptureTracking. Not using it may | ||||
467 | // cause weird miscompilations where 2 aliasing pointers are assumed to | ||||
468 | // noalias. | ||||
469 | if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) { | ||||
470 | V = RP; | ||||
471 | continue; | ||||
472 | } | ||||
473 | } | ||||
474 | |||||
475 | Decomposed.Base = V; | ||||
476 | return Decomposed; | ||||
477 | } | ||||
478 | |||||
479 | // Don't attempt to analyze GEPs over unsized objects. | ||||
480 | if (!GEPOp->getSourceElementType()->isSized()) { | ||||
481 | Decomposed.Base = V; | ||||
482 | return Decomposed; | ||||
483 | } | ||||
484 | |||||
485 | // Don't attempt to analyze GEPs if index scale is not a compile-time | ||||
486 | // constant. | ||||
487 | if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) { | ||||
488 | Decomposed.Base = V; | ||||
489 | Decomposed.HasCompileTimeConstantScale = false; | ||||
490 | return Decomposed; | ||||
491 | } | ||||
492 | |||||
493 | unsigned AS = GEPOp->getPointerAddressSpace(); | ||||
494 | // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. | ||||
495 | gep_type_iterator GTI = gep_type_begin(GEPOp); | ||||
496 | unsigned PointerSize = DL.getPointerSizeInBits(AS); | ||||
497 | // Assume all GEP operands are constants until proven otherwise. | ||||
498 | bool GepHasConstantOffset = true; | ||||
499 | for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); | ||||
500 | I != E; ++I, ++GTI) { | ||||
501 | const Value *Index = *I; | ||||
502 | // Compute the (potentially symbolic) offset in bytes for this index. | ||||
503 | if (StructType *STy = GTI.getStructTypeOrNull()) { | ||||
504 | // For a struct, add the member offset. | ||||
505 | unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); | ||||
506 | if (FieldNo == 0) | ||||
507 | continue; | ||||
508 | |||||
509 | Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo); | ||||
510 | continue; | ||||
511 | } | ||||
512 | |||||
513 | // For an array/pointer, add the element offset, explicitly scaled. | ||||
514 | if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { | ||||
515 | if (CIdx->isZero()) | ||||
516 | continue; | ||||
517 | Decomposed.Offset += | ||||
518 | DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() * | ||||
519 | CIdx->getValue().sextOrTrunc(MaxPointerSize); | ||||
520 | continue; | ||||
521 | } | ||||
522 | |||||
523 | GepHasConstantOffset = false; | ||||
524 | |||||
525 | APInt Scale(MaxPointerSize, | ||||
526 | DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize()); | ||||
527 | unsigned ZExtBits = 0, SExtBits = 0; | ||||
528 | |||||
529 | // If the integer type is smaller than the pointer size, it is implicitly | ||||
530 | // sign extended to pointer size. | ||||
531 | unsigned Width = Index->getType()->getIntegerBitWidth(); | ||||
532 | if (PointerSize > Width) | ||||
533 | SExtBits += PointerSize - Width; | ||||
534 | |||||
535 | // Use GetLinearExpression to decompose the index into a C1*V+C2 form. | ||||
536 | APInt IndexScale(Width, 0), IndexOffset(Width, 0); | ||||
537 | bool NSW = true, NUW = true; | ||||
538 | const Value *OrigIndex = Index; | ||||
539 | Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits, | ||||
540 | SExtBits, DL, 0, AC, DT, NSW, NUW); | ||||
541 | |||||
542 | // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. | ||||
543 | // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. | ||||
544 | |||||
545 | // It can be the case that, even through C1*V+C2 does not overflow for | ||||
546 | // relevant values of V, (C2*Scale) can overflow. In that case, we cannot | ||||
547 | // decompose the expression in this way. | ||||
548 | // | ||||
549 | // FIXME: C1*Scale and the other operations in the decomposed | ||||
550 | // (C1*Scale)*V+C2*Scale can also overflow. We should check for this | ||||
551 | // possibility. | ||||
552 | bool Overflow; | ||||
553 | APInt ScaledOffset = IndexOffset.sextOrTrunc(MaxPointerSize) | ||||
554 | .smul_ov(Scale, Overflow); | ||||
555 | if (Overflow) { | ||||
556 | Index = OrigIndex; | ||||
557 | IndexScale = 1; | ||||
558 | IndexOffset = 0; | ||||
559 | |||||
560 | ZExtBits = SExtBits = 0; | ||||
561 | if (PointerSize > Width) | ||||
562 | SExtBits += PointerSize - Width; | ||||
563 | } else { | ||||
564 | Decomposed.Offset += ScaledOffset; | ||||
565 | Scale *= IndexScale.sextOrTrunc(MaxPointerSize); | ||||
566 | } | ||||
567 | |||||
568 | // If we already had an occurrence of this index variable, merge this | ||||
569 | // scale into it. For example, we want to handle: | ||||
570 | // A[x][x] -> x*16 + x*4 -> x*20 | ||||
571 | // This also ensures that 'x' only appears in the index list once. | ||||
572 | for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) { | ||||
573 | if (Decomposed.VarIndices[i].V == Index && | ||||
574 | Decomposed.VarIndices[i].ZExtBits == ZExtBits && | ||||
575 | Decomposed.VarIndices[i].SExtBits == SExtBits) { | ||||
576 | Scale += Decomposed.VarIndices[i].Scale; | ||||
577 | Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i); | ||||
578 | break; | ||||
579 | } | ||||
580 | } | ||||
581 | |||||
582 | // Make sure that we have a scale that makes sense for this target's | ||||
583 | // pointer size. | ||||
584 | Scale = adjustToPointerSize(Scale, PointerSize); | ||||
585 | |||||
586 | if (!!Scale) { | ||||
587 | VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale}; | ||||
588 | Decomposed.VarIndices.push_back(Entry); | ||||
589 | } | ||||
590 | } | ||||
591 | |||||
592 | // Take care of wrap-arounds | ||||
593 | if (GepHasConstantOffset) | ||||
594 | Decomposed.Offset = adjustToPointerSize(Decomposed.Offset, PointerSize); | ||||
595 | |||||
596 | // Analyze the base pointer next. | ||||
597 | V = GEPOp->getOperand(0); | ||||
598 | } while (--MaxLookup); | ||||
599 | |||||
600 | // If the chain of expressions is too deep, just return early. | ||||
601 | Decomposed.Base = V; | ||||
602 | SearchLimitReached++; | ||||
603 | return Decomposed; | ||||
604 | } | ||||
605 | |||||
606 | /// Returns whether the given pointer value points to memory that is local to | ||||
607 | /// the function, with global constants being considered local to all | ||||
608 | /// functions. | ||||
609 | bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, | ||||
610 | AAQueryInfo &AAQI, bool OrLocal) { | ||||
611 | assert(Visited.empty() && "Visited must be cleared after use!")((Visited.empty() && "Visited must be cleared after use!" ) ? static_cast<void> (0) : __assert_fail ("Visited.empty() && \"Visited must be cleared after use!\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 611, __PRETTY_FUNCTION__)); | ||||
612 | |||||
613 | unsigned MaxLookup = 8; | ||||
614 | SmallVector<const Value *, 16> Worklist; | ||||
615 | Worklist.push_back(Loc.Ptr); | ||||
616 | do { | ||||
617 | const Value *V = getUnderlyingObject(Worklist.pop_back_val()); | ||||
618 | if (!Visited.insert(V).second) { | ||||
619 | Visited.clear(); | ||||
620 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||||
621 | } | ||||
622 | |||||
623 | // An alloca instruction defines local memory. | ||||
624 | if (OrLocal && isa<AllocaInst>(V)) | ||||
625 | continue; | ||||
626 | |||||
627 | // A global constant counts as local memory for our purposes. | ||||
628 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { | ||||
629 | // Note: this doesn't require GV to be "ODR" because it isn't legal for a | ||||
630 | // global to be marked constant in some modules and non-constant in | ||||
631 | // others. GV may even be a declaration, not a definition. | ||||
632 | if (!GV->isConstant()) { | ||||
633 | Visited.clear(); | ||||
634 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||||
635 | } | ||||
636 | continue; | ||||
637 | } | ||||
638 | |||||
639 | // If both select values point to local memory, then so does the select. | ||||
640 | if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { | ||||
641 | Worklist.push_back(SI->getTrueValue()); | ||||
642 | Worklist.push_back(SI->getFalseValue()); | ||||
643 | continue; | ||||
644 | } | ||||
645 | |||||
646 | // If all values incoming to a phi node point to local memory, then so does | ||||
647 | // the phi. | ||||
648 | if (const PHINode *PN = dyn_cast<PHINode>(V)) { | ||||
649 | // Don't bother inspecting phi nodes with many operands. | ||||
650 | if (PN->getNumIncomingValues() > MaxLookup) { | ||||
651 | Visited.clear(); | ||||
652 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||||
653 | } | ||||
654 | for (Value *IncValue : PN->incoming_values()) | ||||
655 | Worklist.push_back(IncValue); | ||||
656 | continue; | ||||
657 | } | ||||
658 | |||||
659 | // Otherwise be conservative. | ||||
660 | Visited.clear(); | ||||
661 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||||
662 | } while (!Worklist.empty() && --MaxLookup); | ||||
663 | |||||
664 | Visited.clear(); | ||||
665 | return Worklist.empty(); | ||||
666 | } | ||||
667 | |||||
668 | /// Returns the behavior when calling the given call site. | ||||
669 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) { | ||||
670 | if (Call->doesNotAccessMemory()) | ||||
671 | // Can't do better than this. | ||||
672 | return FMRB_DoesNotAccessMemory; | ||||
673 | |||||
674 | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; | ||||
675 | |||||
676 | // If the callsite knows it only reads memory, don't return worse | ||||
677 | // than that. | ||||
678 | if (Call->onlyReadsMemory()) | ||||
679 | Min = FMRB_OnlyReadsMemory; | ||||
680 | else if (Call->doesNotReadMemory()) | ||||
681 | Min = FMRB_OnlyWritesMemory; | ||||
682 | |||||
683 | if (Call->onlyAccessesArgMemory()) | ||||
684 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); | ||||
685 | else if (Call->onlyAccessesInaccessibleMemory()) | ||||
686 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem); | ||||
687 | else if (Call->onlyAccessesInaccessibleMemOrArgMem()) | ||||
688 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem); | ||||
689 | |||||
690 | // If the call has operand bundles then aliasing attributes from the function | ||||
691 | // it calls do not directly apply to the call. This can be made more precise | ||||
692 | // in the future. | ||||
693 | if (!Call->hasOperandBundles()) | ||||
694 | if (const Function *F = Call->getCalledFunction()) | ||||
695 | Min = | ||||
696 | FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F)); | ||||
697 | |||||
698 | return Min; | ||||
699 | } | ||||
700 | |||||
701 | /// Returns the behavior when calling the given function. For use when the call | ||||
702 | /// site is not known. | ||||
703 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) { | ||||
704 | // If the function declares it doesn't access memory, we can't do better. | ||||
705 | if (F->doesNotAccessMemory()) | ||||
706 | return FMRB_DoesNotAccessMemory; | ||||
707 | |||||
708 | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; | ||||
709 | |||||
710 | // If the function declares it only reads memory, go with that. | ||||
711 | if (F->onlyReadsMemory()) | ||||
712 | Min = FMRB_OnlyReadsMemory; | ||||
713 | else if (F->doesNotReadMemory()) | ||||
714 | Min = FMRB_OnlyWritesMemory; | ||||
715 | |||||
716 | if (F->onlyAccessesArgMemory()) | ||||
717 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); | ||||
718 | else if (F->onlyAccessesInaccessibleMemory()) | ||||
719 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem); | ||||
720 | else if (F->onlyAccessesInaccessibleMemOrArgMem()) | ||||
721 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem); | ||||
722 | |||||
723 | return Min; | ||||
724 | } | ||||
725 | |||||
726 | /// Returns true if this is a writeonly (i.e Mod only) parameter. | ||||
727 | static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx, | ||||
728 | const TargetLibraryInfo &TLI) { | ||||
729 | if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly)) | ||||
730 | return true; | ||||
731 | |||||
732 | // We can bound the aliasing properties of memset_pattern16 just as we can | ||||
733 | // for memcpy/memset. This is particularly important because the | ||||
734 | // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 | ||||
735 | // whenever possible. | ||||
736 | // FIXME Consider handling this in InferFunctionAttr.cpp together with other | ||||
737 | // attributes. | ||||
738 | LibFunc F; | ||||
739 | if (Call->getCalledFunction() && | ||||
740 | TLI.getLibFunc(*Call->getCalledFunction(), F) && | ||||
741 | F == LibFunc_memset_pattern16 && TLI.has(F)) | ||||
742 | if (ArgIdx == 0) | ||||
743 | return true; | ||||
744 | |||||
745 | // TODO: memset_pattern4, memset_pattern8 | ||||
746 | // TODO: _chk variants | ||||
747 | // TODO: strcmp, strcpy | ||||
748 | |||||
749 | return false; | ||||
750 | } | ||||
751 | |||||
752 | ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call, | ||||
753 | unsigned ArgIdx) { | ||||
754 | // Checking for known builtin intrinsics and target library functions. | ||||
755 | if (isWriteOnlyParam(Call, ArgIdx, TLI)) | ||||
756 | return ModRefInfo::Mod; | ||||
757 | |||||
758 | if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly)) | ||||
759 | return ModRefInfo::Ref; | ||||
760 | |||||
761 | if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone)) | ||||
762 | return ModRefInfo::NoModRef; | ||||
763 | |||||
764 | return AAResultBase::getArgModRefInfo(Call, ArgIdx); | ||||
765 | } | ||||
766 | |||||
767 | static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { | ||||
768 | const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call); | ||||
769 | return II && II->getIntrinsicID() == IID; | ||||
770 | } | ||||
771 | |||||
772 | #ifndef NDEBUG | ||||
773 | static const Function *getParent(const Value *V) { | ||||
774 | if (const Instruction *inst = dyn_cast<Instruction>(V)) { | ||||
775 | if (!inst->getParent()) | ||||
776 | return nullptr; | ||||
777 | return inst->getParent()->getParent(); | ||||
778 | } | ||||
779 | |||||
780 | if (const Argument *arg = dyn_cast<Argument>(V)) | ||||
781 | return arg->getParent(); | ||||
782 | |||||
783 | return nullptr; | ||||
784 | } | ||||
785 | |||||
786 | static bool notDifferentParent(const Value *O1, const Value *O2) { | ||||
787 | |||||
788 | const Function *F1 = getParent(O1); | ||||
789 | const Function *F2 = getParent(O2); | ||||
790 | |||||
791 | return !F1 || !F2 || F1 == F2; | ||||
792 | } | ||||
793 | #endif | ||||
794 | |||||
795 | AliasResult BasicAAResult::alias(const MemoryLocation &LocA, | ||||
796 | const MemoryLocation &LocB, | ||||
797 | AAQueryInfo &AAQI) { | ||||
798 | assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&((notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries." ) ? static_cast<void> (0) : __assert_fail ("notDifferentParent(LocA.Ptr, LocB.Ptr) && \"BasicAliasAnalysis doesn't support interprocedural queries.\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 799, __PRETTY_FUNCTION__)) | ||||
799 | "BasicAliasAnalysis doesn't support interprocedural queries.")((notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries." ) ? static_cast<void> (0) : __assert_fail ("notDifferentParent(LocA.Ptr, LocB.Ptr) && \"BasicAliasAnalysis doesn't support interprocedural queries.\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 799, __PRETTY_FUNCTION__)); | ||||
800 | |||||
801 | // If we have a directly cached entry for these locations, we have recursed | ||||
802 | // through this once, so just return the cached results. Notably, when this | ||||
803 | // happens, we don't clear the cache. | ||||
804 | AAQueryInfo::LocPair Locs(LocA, LocB); | ||||
805 | if (Locs.first.Ptr > Locs.second.Ptr) | ||||
806 | std::swap(Locs.first, Locs.second); | ||||
807 | auto CacheIt = AAQI.AliasCache.find(Locs); | ||||
808 | if (CacheIt != AAQI.AliasCache.end()) | ||||
809 | return CacheIt->second; | ||||
810 | |||||
811 | AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, | ||||
812 | LocB.Size, LocB.AATags, AAQI); | ||||
813 | |||||
814 | assert(VisitedPhiBBs.empty())((VisitedPhiBBs.empty()) ? static_cast<void> (0) : __assert_fail ("VisitedPhiBBs.empty()", "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 814, __PRETTY_FUNCTION__)); | ||||
815 | return Alias; | ||||
816 | } | ||||
817 | |||||
818 | /// Checks to see if the specified callsite can clobber the specified memory | ||||
819 | /// object. | ||||
820 | /// | ||||
821 | /// Since we only look at local properties of this function, we really can't | ||||
822 | /// say much about this query. We do, however, use simple "address taken" | ||||
823 | /// analysis on local objects. | ||||
824 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, | ||||
825 | const MemoryLocation &Loc, | ||||
826 | AAQueryInfo &AAQI) { | ||||
827 | assert(notDifferentParent(Call, Loc.Ptr) &&((notDifferentParent(Call, Loc.Ptr) && "AliasAnalysis query involving multiple functions!" ) ? static_cast<void> (0) : __assert_fail ("notDifferentParent(Call, Loc.Ptr) && \"AliasAnalysis query involving multiple functions!\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 828, __PRETTY_FUNCTION__)) | ||||
828 | "AliasAnalysis query involving multiple functions!")((notDifferentParent(Call, Loc.Ptr) && "AliasAnalysis query involving multiple functions!" ) ? static_cast<void> (0) : __assert_fail ("notDifferentParent(Call, Loc.Ptr) && \"AliasAnalysis query involving multiple functions!\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 828, __PRETTY_FUNCTION__)); | ||||
829 | |||||
830 | const Value *Object = getUnderlyingObject(Loc.Ptr); | ||||
831 | |||||
832 | // Calls marked 'tail' cannot read or write allocas from the current frame | ||||
833 | // because the current frame might be destroyed by the time they run. However, | ||||
834 | // a tail call may use an alloca with byval. Calling with byval copies the | ||||
835 | // contents of the alloca into argument registers or stack slots, so there is | ||||
836 | // no lifetime issue. | ||||
837 | if (isa<AllocaInst>(Object)) | ||||
838 | if (const CallInst *CI = dyn_cast<CallInst>(Call)) | ||||
839 | if (CI->isTailCall() && | ||||
840 | !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal)) | ||||
841 | return ModRefInfo::NoModRef; | ||||
842 | |||||
843 | // Stack restore is able to modify unescaped dynamic allocas. Assume it may | ||||
844 | // modify them even though the alloca is not escaped. | ||||
845 | if (auto *AI = dyn_cast<AllocaInst>(Object)) | ||||
846 | if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) | ||||
847 | return ModRefInfo::Mod; | ||||
848 | |||||
849 | // If the pointer is to a locally allocated object that does not escape, | ||||
850 | // then the call can not mod/ref the pointer unless the call takes the pointer | ||||
851 | // as an argument, and itself doesn't capture it. | ||||
852 | if (!isa<Constant>(Object) && Call != Object && | ||||
853 | isNonEscapingLocalObject(Object, &AAQI.IsCapturedCache)) { | ||||
854 | |||||
855 | // Optimistically assume that call doesn't touch Object and check this | ||||
856 | // assumption in the following loop. | ||||
857 | ModRefInfo Result = ModRefInfo::NoModRef; | ||||
858 | bool IsMustAlias = true; | ||||
859 | |||||
860 | unsigned OperandNo = 0; | ||||
861 | for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); | ||||
862 | CI != CE; ++CI, ++OperandNo) { | ||||
863 | // Only look at the no-capture or byval pointer arguments. If this | ||||
864 | // pointer were passed to arguments that were neither of these, then it | ||||
865 | // couldn't be no-capture. | ||||
866 | if (!(*CI)->getType()->isPointerTy() || | ||||
867 | (!Call->doesNotCapture(OperandNo) && | ||||
868 | OperandNo < Call->getNumArgOperands() && | ||||
869 | !Call->isByValArgument(OperandNo))) | ||||
870 | continue; | ||||
871 | |||||
872 | // Call doesn't access memory through this operand, so we don't care | ||||
873 | // if it aliases with Object. | ||||
874 | if (Call->doesNotAccessMemory(OperandNo)) | ||||
875 | continue; | ||||
876 | |||||
877 | // If this is a no-capture pointer argument, see if we can tell that it | ||||
878 | // is impossible to alias the pointer we're checking. | ||||
879 | AliasResult AR = getBestAAResults().alias( | ||||
880 | MemoryLocation::getBeforeOrAfter(*CI), | ||||
881 | MemoryLocation::getBeforeOrAfter(Object), AAQI); | ||||
882 | if (AR != MustAlias) | ||||
883 | IsMustAlias = false; | ||||
884 | // Operand doesn't alias 'Object', continue looking for other aliases | ||||
885 | if (AR == NoAlias) | ||||
886 | continue; | ||||
887 | // Operand aliases 'Object', but call doesn't modify it. Strengthen | ||||
888 | // initial assumption and keep looking in case if there are more aliases. | ||||
889 | if (Call->onlyReadsMemory(OperandNo)) { | ||||
890 | Result = setRef(Result); | ||||
891 | continue; | ||||
892 | } | ||||
893 | // Operand aliases 'Object' but call only writes into it. | ||||
894 | if (Call->doesNotReadMemory(OperandNo)) { | ||||
895 | Result = setMod(Result); | ||||
896 | continue; | ||||
897 | } | ||||
898 | // This operand aliases 'Object' and call reads and writes into it. | ||||
899 | // Setting ModRef will not yield an early return below, MustAlias is not | ||||
900 | // used further. | ||||
901 | Result = ModRefInfo::ModRef; | ||||
902 | break; | ||||
903 | } | ||||
904 | |||||
905 | // No operand aliases, reset Must bit. Add below if at least one aliases | ||||
906 | // and all aliases found are MustAlias. | ||||
907 | if (isNoModRef(Result)) | ||||
908 | IsMustAlias = false; | ||||
909 | |||||
910 | // Early return if we improved mod ref information | ||||
911 | if (!isModAndRefSet(Result)) { | ||||
912 | if (isNoModRef(Result)) | ||||
913 | return ModRefInfo::NoModRef; | ||||
914 | return IsMustAlias ? setMust(Result) : clearMust(Result); | ||||
915 | } | ||||
916 | } | ||||
917 | |||||
918 | // If the call is malloc/calloc like, we can assume that it doesn't | ||||
919 | // modify any IR visible value. This is only valid because we assume these | ||||
920 | // routines do not read values visible in the IR. TODO: Consider special | ||||
921 | // casing realloc and strdup routines which access only their arguments as | ||||
922 | // well. Or alternatively, replace all of this with inaccessiblememonly once | ||||
923 | // that's implemented fully. | ||||
924 | if (isMallocOrCallocLikeFn(Call, &TLI)) { | ||||
925 | // Be conservative if the accessed pointer may alias the allocation - | ||||
926 | // fallback to the generic handling below. | ||||
927 | if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), | ||||
928 | Loc, AAQI) == NoAlias) | ||||
929 | return ModRefInfo::NoModRef; | ||||
930 | } | ||||
931 | |||||
932 | // The semantics of memcpy intrinsics either exactly overlap or do not | ||||
933 | // overlap, i.e., source and destination of any given memcpy are either | ||||
934 | // no-alias or must-alias. | ||||
935 | if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) { | ||||
936 | AliasResult SrcAA = | ||||
937 | getBestAAResults().alias(MemoryLocation::getForSource(Inst), Loc, AAQI); | ||||
938 | AliasResult DestAA = | ||||
939 | getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI); | ||||
940 | // It's also possible for Loc to alias both src and dest, or neither. | ||||
941 | ModRefInfo rv = ModRefInfo::NoModRef; | ||||
942 | if (SrcAA != NoAlias) | ||||
943 | rv = setRef(rv); | ||||
944 | if (DestAA != NoAlias) | ||||
945 | rv = setMod(rv); | ||||
946 | return rv; | ||||
947 | } | ||||
948 | |||||
949 | // While the assume intrinsic is marked as arbitrarily writing so that | ||||
950 | // proper control dependencies will be maintained, it never aliases any | ||||
951 | // particular memory location. | ||||
952 | if (isIntrinsicCall(Call, Intrinsic::assume)) | ||||
953 | return ModRefInfo::NoModRef; | ||||
954 | |||||
955 | // Like assumes, guard intrinsics are also marked as arbitrarily writing so | ||||
956 | // that proper control dependencies are maintained but they never mods any | ||||
957 | // particular memory location. | ||||
958 | // | ||||
959 | // *Unlike* assumes, guard intrinsics are modeled as reading memory since the | ||||
960 | // heap state at the point the guard is issued needs to be consistent in case | ||||
961 | // the guard invokes the "deopt" continuation. | ||||
962 | if (isIntrinsicCall(Call, Intrinsic::experimental_guard)) | ||||
963 | return ModRefInfo::Ref; | ||||
964 | // The same applies to deoptimize which is essentially a guard(false). | ||||
965 | if (isIntrinsicCall(Call, Intrinsic::experimental_deoptimize)) | ||||
966 | return ModRefInfo::Ref; | ||||
967 | |||||
968 | // Like assumes, invariant.start intrinsics were also marked as arbitrarily | ||||
969 | // writing so that proper control dependencies are maintained but they never | ||||
970 | // mod any particular memory location visible to the IR. | ||||
971 | // *Unlike* assumes (which are now modeled as NoModRef), invariant.start | ||||
972 | // intrinsic is now modeled as reading memory. This prevents hoisting the | ||||
973 | // invariant.start intrinsic over stores. Consider: | ||||
974 | // *ptr = 40; | ||||
975 | // *ptr = 50; | ||||
976 | // invariant_start(ptr) | ||||
977 | // int val = *ptr; | ||||
978 | // print(val); | ||||
979 | // | ||||
980 | // This cannot be transformed to: | ||||
981 | // | ||||
982 | // *ptr = 40; | ||||
983 | // invariant_start(ptr) | ||||
984 | // *ptr = 50; | ||||
985 | // int val = *ptr; | ||||
986 | // print(val); | ||||
987 | // | ||||
988 | // The transformation will cause the second store to be ignored (based on | ||||
989 | // rules of invariant.start) and print 40, while the first program always | ||||
990 | // prints 50. | ||||
991 | if (isIntrinsicCall(Call, Intrinsic::invariant_start)) | ||||
992 | return ModRefInfo::Ref; | ||||
993 | |||||
994 | // The AAResultBase base class has some smarts, lets use them. | ||||
995 | return AAResultBase::getModRefInfo(Call, Loc, AAQI); | ||||
996 | } | ||||
997 | |||||
998 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, | ||||
999 | const CallBase *Call2, | ||||
1000 | AAQueryInfo &AAQI) { | ||||
1001 | // While the assume intrinsic is marked as arbitrarily writing so that | ||||
1002 | // proper control dependencies will be maintained, it never aliases any | ||||
1003 | // particular memory location. | ||||
1004 | if (isIntrinsicCall(Call1, Intrinsic::assume) || | ||||
1005 | isIntrinsicCall(Call2, Intrinsic::assume)) | ||||
1006 | return ModRefInfo::NoModRef; | ||||
1007 | |||||
1008 | // Like assumes, guard intrinsics are also marked as arbitrarily writing so | ||||
1009 | // that proper control dependencies are maintained but they never mod any | ||||
1010 | // particular memory location. | ||||
1011 | // | ||||
1012 | // *Unlike* assumes, guard intrinsics are modeled as reading memory since the | ||||
1013 | // heap state at the point the guard is issued needs to be consistent in case | ||||
1014 | // the guard invokes the "deopt" continuation. | ||||
1015 | |||||
1016 | // NB! This function is *not* commutative, so we special case two | ||||
1017 | // possibilities for guard intrinsics. | ||||
1018 | |||||
1019 | if (isIntrinsicCall(Call1, Intrinsic::experimental_guard)) | ||||
1020 | return isModSet(createModRefInfo(getModRefBehavior(Call2))) | ||||
1021 | ? ModRefInfo::Ref | ||||
1022 | : ModRefInfo::NoModRef; | ||||
1023 | |||||
1024 | if (isIntrinsicCall(Call2, Intrinsic::experimental_guard)) | ||||
1025 | return isModSet(createModRefInfo(getModRefBehavior(Call1))) | ||||
1026 | ? ModRefInfo::Mod | ||||
1027 | : ModRefInfo::NoModRef; | ||||
1028 | |||||
1029 | // The AAResultBase base class has some smarts, lets use them. | ||||
1030 | return AAResultBase::getModRefInfo(Call1, Call2, AAQI); | ||||
1031 | } | ||||
1032 | |||||
1033 | /// Provide ad-hoc rules to disambiguate accesses through two GEP operators, | ||||
1034 | /// both having the exact same pointer operand. | ||||
1035 | static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, | ||||
1036 | LocationSize MaybeV1Size, | ||||
1037 | const GEPOperator *GEP2, | ||||
1038 | LocationSize MaybeV2Size, | ||||
1039 | const DataLayout &DL) { | ||||
1040 | assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==((GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups () == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups () && GEP1->getPointerOperandType() == GEP2->getPointerOperandType () && "Expected GEPs with the same pointer operand") ? static_cast<void> (0) : __assert_fail ("GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType() && \"Expected GEPs with the same pointer operand\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1043, __PRETTY_FUNCTION__)) | ||||
1041 | GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&((GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups () == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups () && GEP1->getPointerOperandType() == GEP2->getPointerOperandType () && "Expected GEPs with the same pointer operand") ? static_cast<void> (0) : __assert_fail ("GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType() && \"Expected GEPs with the same pointer operand\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1043, __PRETTY_FUNCTION__)) | ||||
1042 | GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&((GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups () == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups () && GEP1->getPointerOperandType() == GEP2->getPointerOperandType () && "Expected GEPs with the same pointer operand") ? static_cast<void> (0) : __assert_fail ("GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType() && \"Expected GEPs with the same pointer operand\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1043, __PRETTY_FUNCTION__)) | ||||
1043 | "Expected GEPs with the same pointer operand")((GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups () == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups () && GEP1->getPointerOperandType() == GEP2->getPointerOperandType () && "Expected GEPs with the same pointer operand") ? static_cast<void> (0) : __assert_fail ("GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType() && \"Expected GEPs with the same pointer operand\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1043, __PRETTY_FUNCTION__)); | ||||
1044 | |||||
1045 | // Try to determine whether GEP1 and GEP2 index through arrays, into structs, | ||||
1046 | // such that the struct field accesses provably cannot alias. | ||||
1047 | // We also need at least two indices (the pointer, and the struct field). | ||||
1048 | if (GEP1->getNumIndices() != GEP2->getNumIndices() || | ||||
1049 | GEP1->getNumIndices() < 2) | ||||
1050 | return MayAlias; | ||||
1051 | |||||
1052 | // If we don't know the size of the accesses through both GEPs, we can't | ||||
1053 | // determine whether the struct fields accessed can't alias. | ||||
1054 | if (!MaybeV1Size.hasValue() || !MaybeV2Size.hasValue()) | ||||
1055 | return MayAlias; | ||||
1056 | |||||
1057 | const uint64_t V1Size = MaybeV1Size.getValue(); | ||||
1058 | const uint64_t V2Size = MaybeV2Size.getValue(); | ||||
1059 | |||||
1060 | ConstantInt *C1 = | ||||
1061 | dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1)); | ||||
1062 | ConstantInt *C2 = | ||||
1063 | dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1)); | ||||
1064 | |||||
1065 | // If the last (struct) indices are constants and are equal, the other indices | ||||
1066 | // might be also be dynamically equal, so the GEPs can alias. | ||||
1067 | if (C1 && C2) { | ||||
1068 | unsigned BitWidth = std::max(C1->getBitWidth(), C2->getBitWidth()); | ||||
1069 | if (C1->getValue().sextOrSelf(BitWidth) == | ||||
1070 | C2->getValue().sextOrSelf(BitWidth)) | ||||
1071 | return MayAlias; | ||||
1072 | } | ||||
1073 | |||||
1074 | // Find the last-indexed type of the GEP, i.e., the type you'd get if | ||||
1075 | // you stripped the last index. | ||||
1076 | // On the way, look at each indexed type. If there's something other | ||||
1077 | // than an array, different indices can lead to different final types. | ||||
1078 | SmallVector<Value *, 8> IntermediateIndices; | ||||
1079 | |||||
1080 | // Insert the first index; we don't need to check the type indexed | ||||
1081 | // through it as it only drops the pointer indirection. | ||||
1082 | assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine")((GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine" ) ? static_cast<void> (0) : __assert_fail ("GEP1->getNumIndices() > 1 && \"Not enough GEP indices to examine\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1082, __PRETTY_FUNCTION__)); | ||||
1083 | IntermediateIndices.push_back(GEP1->getOperand(1)); | ||||
1084 | |||||
1085 | // Insert all the remaining indices but the last one. | ||||
1086 | // Also, check that they all index through arrays. | ||||
1087 | for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) { | ||||
1088 | if (!isa<ArrayType>(GetElementPtrInst::getIndexedType( | ||||
1089 | GEP1->getSourceElementType(), IntermediateIndices))) | ||||
1090 | return MayAlias; | ||||
1091 | IntermediateIndices.push_back(GEP1->getOperand(i + 1)); | ||||
1092 | } | ||||
1093 | |||||
1094 | auto *Ty = GetElementPtrInst::getIndexedType( | ||||
1095 | GEP1->getSourceElementType(), IntermediateIndices); | ||||
1096 | if (isa<ArrayType>(Ty) || isa<VectorType>(Ty)) { | ||||
1097 | // We know that: | ||||
1098 | // - both GEPs begin indexing from the exact same pointer; | ||||
1099 | // - the last indices in both GEPs are constants, indexing into a sequential | ||||
1100 | // type (array or vector); | ||||
1101 | // - both GEPs only index through arrays prior to that. | ||||
1102 | // | ||||
1103 | // Because array indices greater than the number of elements are valid in | ||||
1104 | // GEPs, unless we know the intermediate indices are identical between | ||||
1105 | // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't | ||||
1106 | // partially overlap. We also need to check that the loaded size matches | ||||
1107 | // the element size, otherwise we could still have overlap. | ||||
1108 | Type *LastElementTy = GetElementPtrInst::getTypeAtIndex(Ty, (uint64_t)0); | ||||
1109 | const uint64_t ElementSize = | ||||
1110 | DL.getTypeStoreSize(LastElementTy).getFixedSize(); | ||||
1111 | if (V1Size != ElementSize || V2Size != ElementSize) | ||||
1112 | return MayAlias; | ||||
1113 | |||||
1114 | for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i) | ||||
1115 | if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1)) | ||||
1116 | return MayAlias; | ||||
1117 | |||||
1118 | // Now we know that the array/pointer that GEP1 indexes into and that | ||||
1119 | // that GEP2 indexes into must either precisely overlap or be disjoint. | ||||
1120 | // Because they cannot partially overlap and because fields in an array | ||||
1121 | // cannot overlap, if we can prove the final indices are different between | ||||
1122 | // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias. | ||||
1123 | |||||
1124 | // If the last indices are constants, we've already checked they don't | ||||
1125 | // equal each other so we can exit early. | ||||
1126 | if (C1 && C2) | ||||
1127 | return NoAlias; | ||||
1128 | { | ||||
1129 | Value *GEP1LastIdx = GEP1->getOperand(GEP1->getNumOperands() - 1); | ||||
1130 | Value *GEP2LastIdx = GEP2->getOperand(GEP2->getNumOperands() - 1); | ||||
1131 | if (isa<PHINode>(GEP1LastIdx) || isa<PHINode>(GEP2LastIdx)) { | ||||
1132 | // If one of the indices is a PHI node, be safe and only use | ||||
1133 | // computeKnownBits so we don't make any assumptions about the | ||||
1134 | // relationships between the two indices. This is important if we're | ||||
1135 | // asking about values from different loop iterations. See PR32314. | ||||
1136 | // TODO: We may be able to change the check so we only do this when | ||||
1137 | // we definitely looked through a PHINode. | ||||
1138 | if (GEP1LastIdx != GEP2LastIdx && | ||||
1139 | GEP1LastIdx->getType() == GEP2LastIdx->getType()) { | ||||
1140 | KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL); | ||||
1141 | KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL); | ||||
1142 | if (Known1.Zero.intersects(Known2.One) || | ||||
1143 | Known1.One.intersects(Known2.Zero)) | ||||
1144 | return NoAlias; | ||||
1145 | } | ||||
1146 | } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL)) | ||||
1147 | return NoAlias; | ||||
1148 | } | ||||
1149 | } | ||||
1150 | return MayAlias; | ||||
1151 | } | ||||
1152 | |||||
1153 | // If a we have (a) a GEP and (b) a pointer based on an alloca, and the | ||||
1154 | // beginning of the object the GEP points would have a negative offset with | ||||
1155 | // repsect to the alloca, that means the GEP can not alias pointer (b). | ||||
1156 | // Note that the pointer based on the alloca may not be a GEP. For | ||||
1157 | // example, it may be the alloca itself. | ||||
1158 | // The same applies if (b) is based on a GlobalVariable. Note that just being | ||||
1159 | // based on isIdentifiedObject() is not enough - we need an identified object | ||||
1160 | // that does not permit access to negative offsets. For example, a negative | ||||
1161 | // offset from a noalias argument or call can be inbounds w.r.t the actual | ||||
1162 | // underlying object. | ||||
1163 | // | ||||
1164 | // For example, consider: | ||||
1165 | // | ||||
1166 | // struct { int f0, int f1, ...} foo; | ||||
1167 | // foo alloca; | ||||
1168 | // foo* random = bar(alloca); | ||||
1169 | // int *f0 = &alloca.f0 | ||||
1170 | // int *f1 = &random->f1; | ||||
1171 | // | ||||
1172 | // Which is lowered, approximately, to: | ||||
1173 | // | ||||
1174 | // %alloca = alloca %struct.foo | ||||
1175 | // %random = call %struct.foo* @random(%struct.foo* %alloca) | ||||
1176 | // %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0 | ||||
1177 | // %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1 | ||||
1178 | // | ||||
1179 | // Assume %f1 and %f0 alias. Then %f1 would point into the object allocated | ||||
1180 | // by %alloca. Since the %f1 GEP is inbounds, that means %random must also | ||||
1181 | // point into the same object. But since %f0 points to the beginning of %alloca, | ||||
1182 | // the highest %f1 can be is (%alloca + 3). This means %random can not be higher | ||||
1183 | // than (%alloca - 1), and so is not inbounds, a contradiction. | ||||
1184 | bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, | ||||
1185 | const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, | ||||
1186 | LocationSize MaybeObjectAccessSize) { | ||||
1187 | // If the object access size is unknown, or the GEP isn't inbounds, bail. | ||||
1188 | if (!MaybeObjectAccessSize.hasValue() || !GEPOp->isInBounds()) | ||||
1189 | return false; | ||||
1190 | |||||
1191 | const uint64_t ObjectAccessSize = MaybeObjectAccessSize.getValue(); | ||||
1192 | |||||
1193 | // We need the object to be an alloca or a globalvariable, and want to know | ||||
1194 | // the offset of the pointer from the object precisely, so no variable | ||||
1195 | // indices are allowed. | ||||
1196 | if (!(isa<AllocaInst>(DecompObject.Base) || | ||||
1197 | isa<GlobalVariable>(DecompObject.Base)) || | ||||
1198 | !DecompObject.VarIndices.empty()) | ||||
1199 | return false; | ||||
1200 | |||||
1201 | // If the GEP has no variable indices, we know the precise offset | ||||
1202 | // from the base, then use it. If the GEP has variable indices, | ||||
1203 | // we can't get exact GEP offset to identify pointer alias. So return | ||||
1204 | // false in that case. | ||||
1205 | if (!DecompGEP.VarIndices.empty()) | ||||
1206 | return false; | ||||
1207 | |||||
1208 | return DecompGEP.Offset.sge(DecompObject.Offset + (int64_t)ObjectAccessSize); | ||||
1209 | } | ||||
1210 | |||||
1211 | /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against | ||||
1212 | /// another pointer. | ||||
1213 | /// | ||||
1214 | /// We know that V1 is a GEP, but we don't know anything about V2. | ||||
1215 | /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for | ||||
1216 | /// V2. | ||||
1217 | AliasResult BasicAAResult::aliasGEP( | ||||
1218 | const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo, | ||||
1219 | const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, | ||||
1220 | const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { | ||||
1221 | DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT); | ||||
1222 | DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT); | ||||
1223 | |||||
1224 | // Don't attempt to analyze the decomposed GEP if index scale is not a | ||||
1225 | // compile-time constant. | ||||
1226 | if (!DecompGEP1.HasCompileTimeConstantScale || | ||||
1227 | !DecompGEP2.HasCompileTimeConstantScale) | ||||
1228 | return MayAlias; | ||||
1229 | |||||
1230 | assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&((DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && "DecomposeGEPExpression returned a result different from " "getUnderlyingObject") ? static_cast<void> (0) : __assert_fail ("DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && \"DecomposeGEPExpression returned a result different from \" \"getUnderlyingObject\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1232, __PRETTY_FUNCTION__)) | ||||
1231 | "DecomposeGEPExpression returned a result different from "((DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && "DecomposeGEPExpression returned a result different from " "getUnderlyingObject") ? static_cast<void> (0) : __assert_fail ("DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && \"DecomposeGEPExpression returned a result different from \" \"getUnderlyingObject\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1232, __PRETTY_FUNCTION__)) | ||||
1232 | "getUnderlyingObject")((DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && "DecomposeGEPExpression returned a result different from " "getUnderlyingObject") ? static_cast<void> (0) : __assert_fail ("DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && \"DecomposeGEPExpression returned a result different from \" \"getUnderlyingObject\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1232, __PRETTY_FUNCTION__)); | ||||
1233 | |||||
1234 | // If the GEP's offset relative to its base is such that the base would | ||||
1235 | // fall below the start of the object underlying V2, then the GEP and V2 | ||||
1236 | // cannot alias. | ||||
1237 | if (isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size)) | ||||
1238 | return NoAlias; | ||||
1239 | // If we have two gep instructions with must-alias or not-alias'ing base | ||||
1240 | // pointers, figure out if the indexes to the GEP tell us anything about the | ||||
1241 | // derived pointer. | ||||
1242 | if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { | ||||
1243 | // Check for the GEP base being at a negative offset, this time in the other | ||||
1244 | // direction. | ||||
1245 | if (isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) | ||||
1246 | return NoAlias; | ||||
1247 | // Do the base pointers alias? | ||||
1248 | AliasResult BaseAlias = aliasCheck( | ||||
1249 | UnderlyingV1, LocationSize::beforeOrAfterPointer(), AAMDNodes(), | ||||
1250 | UnderlyingV2, LocationSize::beforeOrAfterPointer(), AAMDNodes(), AAQI); | ||||
1251 | |||||
1252 | // For GEPs with identical offsets, we can preserve the size and AAInfo | ||||
1253 | // when performing the alias check on the underlying objects. | ||||
1254 | if (BaseAlias == MayAlias && DecompGEP1.Offset == DecompGEP2.Offset && | ||||
1255 | DecompGEP1.VarIndices == DecompGEP2.VarIndices) { | ||||
1256 | AliasResult PreciseBaseAlias = aliasCheck( | ||||
1257 | UnderlyingV1, V1Size, V1AAInfo, UnderlyingV2, V2Size, V2AAInfo, AAQI); | ||||
1258 | if (PreciseBaseAlias == NoAlias) | ||||
1259 | return NoAlias; | ||||
1260 | } | ||||
1261 | |||||
1262 | // If we get a No or May, then return it immediately, no amount of analysis | ||||
1263 | // will improve this situation. | ||||
1264 | if (BaseAlias != MustAlias) { | ||||
1265 | assert(BaseAlias == NoAlias || BaseAlias == MayAlias)((BaseAlias == NoAlias || BaseAlias == MayAlias) ? static_cast <void> (0) : __assert_fail ("BaseAlias == NoAlias || BaseAlias == MayAlias" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1265, __PRETTY_FUNCTION__)); | ||||
1266 | return BaseAlias; | ||||
1267 | } | ||||
1268 | |||||
1269 | // Otherwise, we have a MustAlias. Since the base pointers alias each other | ||||
1270 | // exactly, see if the computed offset from the common pointer tells us | ||||
1271 | // about the relation of the resulting pointer. | ||||
1272 | // If we know the two GEPs are based off of the exact same pointer (and not | ||||
1273 | // just the same underlying object), see if that tells us anything about | ||||
1274 | // the resulting pointers. | ||||
1275 | if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == | ||||
1276 | GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && | ||||
1277 | GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) { | ||||
1278 | AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL); | ||||
1279 | // If we couldn't find anything interesting, don't abandon just yet. | ||||
1280 | if (R != MayAlias) | ||||
1281 | return R; | ||||
1282 | } | ||||
1283 | |||||
1284 | // Subtract the GEP2 pointer from the GEP1 pointer to find out their | ||||
1285 | // symbolic difference. | ||||
1286 | DecompGEP1.Offset -= DecompGEP2.Offset; | ||||
1287 | GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); | ||||
1288 | |||||
1289 | } else { | ||||
1290 | // Check to see if these two pointers are related by the getelementptr | ||||
1291 | // instruction. If one pointer is a GEP with a non-zero index of the other | ||||
1292 | // pointer, we know they cannot alias. | ||||
1293 | |||||
1294 | // If both accesses are unknown size, we can't do anything useful here. | ||||
1295 | if (!V1Size.hasValue() && !V2Size.hasValue()) | ||||
1296 | return MayAlias; | ||||
1297 | |||||
1298 | AliasResult R = aliasCheck( | ||||
1299 | UnderlyingV1, LocationSize::beforeOrAfterPointer(), AAMDNodes(), | ||||
1300 | V2, V2Size, V2AAInfo, AAQI, nullptr, UnderlyingV2); | ||||
1301 | if (R != MustAlias) { | ||||
1302 | // If V2 may alias GEP base pointer, conservatively returns MayAlias. | ||||
1303 | // If V2 is known not to alias GEP base pointer, then the two values | ||||
1304 | // cannot alias per GEP semantics: "Any memory access must be done through | ||||
1305 | // a pointer value associated with an address range of the memory access, | ||||
1306 | // otherwise the behavior is undefined.". | ||||
1307 | assert(R == NoAlias || R == MayAlias)((R == NoAlias || R == MayAlias) ? static_cast<void> (0 ) : __assert_fail ("R == NoAlias || R == MayAlias", "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1307, __PRETTY_FUNCTION__)); | ||||
1308 | return R; | ||||
1309 | } | ||||
1310 | } | ||||
1311 | |||||
1312 | // In the two GEP Case, if there is no difference in the offsets of the | ||||
1313 | // computed pointers, the resultant pointers are a must alias. This | ||||
1314 | // happens when we have two lexically identical GEP's (for example). | ||||
1315 | // | ||||
1316 | // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 | ||||
1317 | // must aliases the GEP, the end result is a must alias also. | ||||
1318 | if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) | ||||
1319 | return MustAlias; | ||||
1320 | |||||
1321 | // If there is a constant difference between the pointers, but the difference | ||||
1322 | // is less than the size of the associated memory object, then we know | ||||
1323 | // that the objects are partially overlapping. If the difference is | ||||
1324 | // greater, we know they do not overlap. | ||||
1325 | if (DecompGEP1.Offset != 0 && DecompGEP1.VarIndices.empty()) { | ||||
1326 | if (DecompGEP1.Offset.sge(0)) { | ||||
1327 | if (V2Size.hasValue()) { | ||||
1328 | if (DecompGEP1.Offset.ult(V2Size.getValue())) | ||||
1329 | return PartialAlias; | ||||
1330 | return NoAlias; | ||||
1331 | } | ||||
1332 | } else { | ||||
1333 | // We have the situation where: | ||||
1334 | // + + | ||||
1335 | // | BaseOffset | | ||||
1336 | // ---------------->| | ||||
1337 | // |-->V1Size |-------> V2Size | ||||
1338 | // GEP1 V2 | ||||
1339 | if (V1Size.hasValue()) { | ||||
1340 | if ((-DecompGEP1.Offset).ult(V1Size.getValue())) | ||||
1341 | return PartialAlias; | ||||
1342 | return NoAlias; | ||||
1343 | } | ||||
1344 | } | ||||
1345 | } | ||||
1346 | |||||
1347 | if (!DecompGEP1.VarIndices.empty()) { | ||||
1348 | APInt GCD; | ||||
1349 | bool AllNonNegative = DecompGEP1.Offset.isNonNegative(); | ||||
1350 | bool AllNonPositive = DecompGEP1.Offset.isNonPositive(); | ||||
1351 | for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { | ||||
1352 | const APInt &Scale = DecompGEP1.VarIndices[i].Scale; | ||||
1353 | if (i == 0) | ||||
1354 | GCD = Scale.abs(); | ||||
1355 | else | ||||
1356 | GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs()); | ||||
1357 | |||||
1358 | if (AllNonNegative || AllNonPositive) { | ||||
1359 | // If the Value could change between cycles, then any reasoning about | ||||
1360 | // the Value this cycle may not hold in the next cycle. We'll just | ||||
1361 | // give up if we can't determine conditions that hold for every cycle: | ||||
1362 | const Value *V = DecompGEP1.VarIndices[i].V; | ||||
1363 | |||||
1364 | KnownBits Known = | ||||
1365 | computeKnownBits(V, DL, 0, &AC, dyn_cast<Instruction>(GEP1), DT); | ||||
1366 | bool SignKnownZero = Known.isNonNegative(); | ||||
1367 | bool SignKnownOne = Known.isNegative(); | ||||
1368 | |||||
1369 | // Zero-extension widens the variable, and so forces the sign | ||||
1370 | // bit to zero. | ||||
1371 | bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V); | ||||
1372 | SignKnownZero |= IsZExt; | ||||
1373 | SignKnownOne &= !IsZExt; | ||||
1374 | |||||
1375 | AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) || | ||||
1376 | (SignKnownOne && Scale.isNonPositive()); | ||||
1377 | AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) || | ||||
1378 | (SignKnownOne && Scale.isNonNegative()); | ||||
1379 | } | ||||
1380 | } | ||||
1381 | |||||
1382 | // We now have accesses at two offsets from the same base: | ||||
1383 | // 1. (...)*GCD + DecompGEP1.Offset with size V1Size | ||||
1384 | // 2. 0 with size V2Size | ||||
1385 | // Using arithmetic modulo GCD, the accesses are at | ||||
1386 | // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits | ||||
1387 | // into the range [V2Size..GCD), then we know they cannot overlap. | ||||
1388 | APInt ModOffset = DecompGEP1.Offset.srem(GCD); | ||||
1389 | if (ModOffset.isNegative()) | ||||
1390 | ModOffset += GCD; // We want mod, not rem. | ||||
1391 | if (V1Size.hasValue() && V2Size.hasValue() && | ||||
1392 | ModOffset.uge(V2Size.getValue()) && | ||||
1393 | (GCD - ModOffset).uge(V1Size.getValue())) | ||||
1394 | return NoAlias; | ||||
1395 | |||||
1396 | // If we know all the variables are non-negative, then the total offset is | ||||
1397 | // also non-negative and >= DecompGEP1.Offset. We have the following layout: | ||||
1398 | // [0, V2Size) ... [TotalOffset, TotalOffer+V1Size] | ||||
1399 | // If DecompGEP1.Offset >= V2Size, the accesses don't alias. | ||||
1400 | if (AllNonNegative && V2Size.hasValue() && | ||||
1401 | DecompGEP1.Offset.uge(V2Size.getValue())) | ||||
1402 | return NoAlias; | ||||
1403 | // Similarly, if the variables are non-positive, then the total offset is | ||||
1404 | // also non-positive and <= DecompGEP1.Offset. We have the following layout: | ||||
1405 | // [TotalOffset, TotalOffset+V1Size) ... [0, V2Size) | ||||
1406 | // If -DecompGEP1.Offset >= V1Size, the accesses don't alias. | ||||
1407 | if (AllNonPositive && V1Size.hasValue() && | ||||
1408 | (-DecompGEP1.Offset).uge(V1Size.getValue())) | ||||
1409 | return NoAlias; | ||||
1410 | |||||
1411 | if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size, | ||||
1412 | DecompGEP1.Offset, &AC, DT)) | ||||
1413 | return NoAlias; | ||||
1414 | } | ||||
1415 | |||||
1416 | // Statically, we can see that the base objects are the same, but the | ||||
1417 | // pointers have dynamic offsets which we can't resolve. And none of our | ||||
1418 | // little tricks above worked. | ||||
1419 | return MayAlias; | ||||
1420 | } | ||||
1421 | |||||
1422 | static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { | ||||
1423 | // If the results agree, take it. | ||||
1424 | if (A == B) | ||||
1425 | return A; | ||||
1426 | // A mix of PartialAlias and MustAlias is PartialAlias. | ||||
1427 | if ((A == PartialAlias && B == MustAlias) || | ||||
1428 | (B == PartialAlias && A == MustAlias)) | ||||
1429 | return PartialAlias; | ||||
1430 | // Otherwise, we don't know anything. | ||||
1431 | return MayAlias; | ||||
1432 | } | ||||
1433 | |||||
1434 | /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction | ||||
1435 | /// against another. | ||||
1436 | AliasResult | ||||
1437 | BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize, | ||||
1438 | const AAMDNodes &SIAAInfo, const Value *V2, | ||||
1439 | LocationSize V2Size, const AAMDNodes &V2AAInfo, | ||||
1440 | const Value *UnderV2, AAQueryInfo &AAQI) { | ||||
1441 | // If the values are Selects with the same condition, we can do a more precise | ||||
1442 | // check: just check for aliases between the values on corresponding arms. | ||||
1443 | if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) | ||||
1444 | if (SI->getCondition() == SI2->getCondition()) { | ||||
1445 | AliasResult Alias = | ||||
1446 | aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, SI2->getTrueValue(), | ||||
1447 | V2Size, V2AAInfo, AAQI); | ||||
1448 | if (Alias == MayAlias) | ||||
1449 | return MayAlias; | ||||
1450 | AliasResult ThisAlias = | ||||
1451 | aliasCheck(SI->getFalseValue(), SISize, SIAAInfo, | ||||
1452 | SI2->getFalseValue(), V2Size, V2AAInfo, AAQI); | ||||
1453 | return MergeAliasResults(ThisAlias, Alias); | ||||
1454 | } | ||||
1455 | |||||
1456 | // If both arms of the Select node NoAlias or MustAlias V2, then returns | ||||
1457 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | ||||
1458 | AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), | ||||
1459 | SISize, SIAAInfo, AAQI, UnderV2); | ||||
1460 | if (Alias == MayAlias) | ||||
1461 | return MayAlias; | ||||
1462 | |||||
1463 | AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), | ||||
1464 | SISize, SIAAInfo, AAQI, UnderV2); | ||||
1465 | return MergeAliasResults(ThisAlias, Alias); | ||||
1466 | } | ||||
1467 | |||||
1468 | /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against | ||||
1469 | /// another. | ||||
1470 | AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, | ||||
1471 | const AAMDNodes &PNAAInfo, const Value *V2, | ||||
1472 | LocationSize V2Size, | ||||
1473 | const AAMDNodes &V2AAInfo, | ||||
1474 | const Value *UnderV2, AAQueryInfo &AAQI) { | ||||
1475 | // If the values are PHIs in the same block, we can do a more precise | ||||
1476 | // as well as efficient check: just check for aliases between the values | ||||
1477 | // on corresponding edges. | ||||
1478 | if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) | ||||
1479 | if (PN2->getParent() == PN->getParent()) { | ||||
1480 | AAQueryInfo::LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), | ||||
1481 | MemoryLocation(V2, V2Size, V2AAInfo)); | ||||
1482 | if (PN > V2) | ||||
1483 | std::swap(Locs.first, Locs.second); | ||||
1484 | // Analyse the PHIs' inputs under the assumption that the PHIs are | ||||
1485 | // NoAlias. | ||||
1486 | // If the PHIs are May/MustAlias there must be (recursively) an input | ||||
1487 | // operand from outside the PHIs' cycle that is MayAlias/MustAlias or | ||||
1488 | // there must be an operation on the PHIs within the PHIs' value cycle | ||||
1489 | // that causes a MayAlias. | ||||
1490 | // Pretend the phis do not alias. | ||||
1491 | AliasResult Alias = NoAlias; | ||||
1492 | AliasResult OrigAliasResult; | ||||
1493 | { | ||||
1494 | // Limited lifetime iterator invalidated by the aliasCheck call below. | ||||
1495 | auto CacheIt = AAQI.AliasCache.find(Locs); | ||||
1496 | assert((CacheIt != AAQI.AliasCache.end()) &&(((CacheIt != AAQI.AliasCache.end()) && "There must exist an entry for the phi node" ) ? static_cast<void> (0) : __assert_fail ("(CacheIt != AAQI.AliasCache.end()) && \"There must exist an entry for the phi node\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1497, __PRETTY_FUNCTION__)) | ||||
1497 | "There must exist an entry for the phi node")(((CacheIt != AAQI.AliasCache.end()) && "There must exist an entry for the phi node" ) ? static_cast<void> (0) : __assert_fail ("(CacheIt != AAQI.AliasCache.end()) && \"There must exist an entry for the phi node\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/lib/Analysis/BasicAliasAnalysis.cpp" , 1497, __PRETTY_FUNCTION__)); | ||||
1498 | OrigAliasResult = CacheIt->second; | ||||
1499 | CacheIt->second = NoAlias; | ||||
1500 | } | ||||
1501 | |||||
1502 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | ||||
1503 | AliasResult ThisAlias = | ||||
1504 | aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, | ||||
1505 | PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), | ||||
1506 | V2Size, V2AAInfo, AAQI); | ||||
1507 | Alias = MergeAliasResults(ThisAlias, Alias); | ||||
1508 | if (Alias == MayAlias) | ||||
1509 | break; | ||||
1510 | } | ||||
1511 | |||||
1512 | // Reset if speculation failed. | ||||
1513 | if (Alias != NoAlias) | ||||
1514 | AAQI.updateResult(Locs, OrigAliasResult); | ||||
1515 | return Alias; | ||||
1516 | } | ||||
1517 | |||||
1518 | SmallVector<Value *, 4> V1Srcs; | ||||
1519 | // If a phi operand recurses back to the phi, we can still determine NoAlias | ||||
1520 | // if we don't alias the underlying objects of the other phi operands, as we | ||||
1521 | // know that the recursive phi needs to be based on them in some way. | ||||
1522 | bool isRecursive = false; | ||||
1523 | auto CheckForRecPhi = [&](Value *PV) { | ||||
1524 | if (!EnableRecPhiAnalysis) | ||||
1525 | return false; | ||||
1526 | if (getUnderlyingObject(PV) == PN) { | ||||
1527 | isRecursive = true; | ||||
1528 | return true; | ||||
1529 | } | ||||
1530 | return false; | ||||
1531 | }; | ||||
1532 | |||||
1533 | if (PV) { | ||||
1534 | // If we have PhiValues then use it to get the underlying phi values. | ||||
1535 | const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN); | ||||
1536 | // If we have more phi values than the search depth then return MayAlias | ||||
1537 | // conservatively to avoid compile time explosion. The worst possible case | ||||
1538 | // is if both sides are PHI nodes. In which case, this is O(m x n) time | ||||
1539 | // where 'm' and 'n' are the number of PHI sources. | ||||
1540 | if (PhiValueSet.size() > MaxLookupSearchDepth) | ||||
1541 | return MayAlias; | ||||
1542 | // Add the values to V1Srcs | ||||
1543 | for (Value *PV1 : PhiValueSet) { | ||||
1544 | if (CheckForRecPhi(PV1)) | ||||
1545 | continue; | ||||
1546 | V1Srcs.push_back(PV1); | ||||
1547 | } | ||||
1548 | } else { | ||||
1549 | // If we don't have PhiInfo then just look at the operands of the phi itself | ||||
1550 | // FIXME: Remove this once we can guarantee that we have PhiInfo always | ||||
1551 | SmallPtrSet<Value *, 4> UniqueSrc; | ||||
1552 | for (Value *PV1 : PN->incoming_values()) { | ||||
1553 | if (isa<PHINode>(PV1)) | ||||
1554 | // If any of the source itself is a PHI, return MayAlias conservatively | ||||
1555 | // to avoid compile time explosion. The worst possible case is if both | ||||
1556 | // sides are PHI nodes. In which case, this is O(m x n) time where 'm' | ||||
1557 | // and 'n' are the number of PHI sources. | ||||
1558 | return MayAlias; | ||||
1559 | |||||
1560 | if (CheckForRecPhi(PV1)) | ||||
1561 | continue; | ||||
1562 | |||||
1563 | if (UniqueSrc.insert(PV1).second) | ||||
1564 | V1Srcs.push_back(PV1); | ||||
1565 | } | ||||
1566 | } | ||||
1567 | |||||
1568 | // If V1Srcs is empty then that means that the phi has no underlying non-phi | ||||
1569 | // value. This should only be possible in blocks unreachable from the entry | ||||
1570 | // block, but return MayAlias just in case. | ||||
1571 | if (V1Srcs.empty()) | ||||
1572 | return MayAlias; | ||||
1573 | |||||
1574 | // If this PHI node is recursive, indicate that the pointer may be moved | ||||
1575 | // across iterations. We can only prove NoAlias if different underlying | ||||
1576 | // objects are involved. | ||||
1577 | if (isRecursive) | ||||
1578 | PNSize = LocationSize::beforeOrAfterPointer(); | ||||
1579 | |||||
1580 | // In the recursive alias queries below, we may compare values from two | ||||
1581 | // different loop iterations. Keep track of visited phi blocks, which will | ||||
1582 | // be used when determining value equivalence. | ||||
1583 | bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second; | ||||
1584 | auto _ = make_scope_exit([&]() { | ||||
1585 | if (BlockInserted) | ||||
1586 | VisitedPhiBBs.erase(PN->getParent()); | ||||
1587 | }); | ||||
1588 | |||||
1589 | // If we inserted a block into VisitedPhiBBs, alias analysis results that | ||||
1590 | // have been cached earlier may no longer be valid. Perform recursive queries | ||||
1591 | // with a new AAQueryInfo. | ||||
1592 | AAQueryInfo NewAAQI; | ||||
1593 | AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI; | ||||
1594 | |||||
1595 | AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, | ||||
1596 | PNAAInfo, *UseAAQI, UnderV2); | ||||
1597 | |||||
1598 | // Early exit if the check of the first PHI source against V2 is MayAlias. | ||||
1599 | // Other results are not possible. | ||||
1600 | if (Alias == MayAlias) | ||||
1601 | return MayAlias; | ||||
1602 | // With recursive phis we cannot guarantee that MustAlias/PartialAlias will | ||||
1603 | // remain valid to all elements and needs to conservatively return MayAlias. | ||||
1604 | if (isRecursive && Alias != NoAlias) | ||||
1605 | return MayAlias; | ||||
1606 | |||||
1607 | // If all sources of the PHI node NoAlias or MustAlias V2, then returns | ||||
1608 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | ||||
1609 | for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { | ||||
1610 | Value *V = V1Srcs[i]; | ||||
1611 | |||||
1612 | AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, | ||||
1613 | PNAAInfo, *UseAAQI, UnderV2); | ||||
1614 | Alias = MergeAliasResults(ThisAlias, Alias); | ||||
1615 | if (Alias == MayAlias) | ||||
1616 | break; | ||||
1617 | } | ||||
1618 | |||||
1619 | return Alias; | ||||
1620 | } | ||||
1621 | |||||
1622 | /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as | ||||
1623 | /// array references. | ||||
1624 | AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, | ||||
1625 | const AAMDNodes &V1AAInfo, | ||||
1626 | const Value *V2, LocationSize V2Size, | ||||
1627 | const AAMDNodes &V2AAInfo, | ||||
1628 | AAQueryInfo &AAQI, const Value *O1, | ||||
1629 | const Value *O2) { | ||||
1630 | // If either of the memory references is empty, it doesn't matter what the | ||||
1631 | // pointer values are. | ||||
1632 | if (V1Size.isZero() || V2Size.isZero()) | ||||
1633 | return NoAlias; | ||||
1634 | |||||
1635 | // Strip off any casts if they exist. | ||||
1636 | V1 = V1->stripPointerCastsAndInvariantGroups(); | ||||
1637 | V2 = V2->stripPointerCastsAndInvariantGroups(); | ||||
1638 | |||||
1639 | // If V1 or V2 is undef, the result is NoAlias because we can always pick a | ||||
1640 | // value for undef that aliases nothing in the program. | ||||
1641 | if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) | ||||
1642 | return NoAlias; | ||||
1643 | |||||
1644 | // Are we checking for alias of the same value? | ||||
1645 | // Because we look 'through' phi nodes, we could look at "Value" pointers from | ||||
1646 | // different iterations. We must therefore make sure that this is not the | ||||
1647 | // case. The function isValueEqualInPotentialCycles ensures that this cannot | ||||
1648 | // happen by looking at the visited phi nodes and making sure they cannot | ||||
1649 | // reach the value. | ||||
1650 | if (isValueEqualInPotentialCycles(V1, V2)) | ||||
1651 | return MustAlias; | ||||
1652 | |||||
1653 | if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) | ||||
1654 | return NoAlias; // Scalars cannot alias each other | ||||
1655 | |||||
1656 | // Figure out what objects these things are pointing to if we can. | ||||
1657 | if (O1 == nullptr) | ||||
1658 | O1 = getUnderlyingObject(V1, MaxLookupSearchDepth); | ||||
1659 | |||||
1660 | if (O2 == nullptr) | ||||
1661 | O2 = getUnderlyingObject(V2, MaxLookupSearchDepth); | ||||
1662 | |||||
1663 | // Null values in the default address space don't point to any object, so they | ||||
1664 | // don't alias any other pointer. | ||||
1665 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) | ||||
1666 | if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) | ||||
1667 | return NoAlias; | ||||
1668 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) | ||||
1669 | if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) | ||||
1670 | return NoAlias; | ||||
1671 | |||||
1672 | if (O1 != O2) { | ||||
1673 | // If V1/V2 point to two different objects, we know that we have no alias. | ||||
1674 | if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) | ||||
1675 | return NoAlias; | ||||
1676 | |||||
1677 | // Constant pointers can't alias with non-const isIdentifiedObject objects. | ||||
1678 | if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || | ||||
1679 | (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) | ||||
1680 | return NoAlias; | ||||
1681 | |||||
1682 | // Function arguments can't alias with things that are known to be | ||||
1683 | // unambigously identified at the function level. | ||||
1684 | if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || | ||||
1685 | (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) | ||||
1686 | return NoAlias; | ||||
1687 | |||||
1688 | // If one pointer is the result of a call/invoke or load and the other is a | ||||
1689 | // non-escaping local object within the same function, then we know the | ||||
1690 | // object couldn't escape to a point where the call could return it. | ||||
1691 | // | ||||
1692 | // Note that if the pointers are in different functions, there are a | ||||
1693 | // variety of complications. A call with a nocapture argument may still | ||||
1694 | // temporary store the nocapture argument's value in a temporary memory | ||||
1695 | // location if that memory location doesn't escape. Or it may pass a | ||||
1696 | // nocapture value to other functions as long as they don't capture it. | ||||
1697 | if (isEscapeSource(O1) && | ||||
1698 | isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache)) | ||||
1699 | return NoAlias; | ||||
1700 | if (isEscapeSource(O2) && | ||||
1701 | isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache)) | ||||
1702 | return NoAlias; | ||||
1703 | } | ||||
1704 | |||||
1705 | // If the size of one access is larger than the entire object on the other | ||||
1706 | // side, then we know such behavior is undefined and can assume no alias. | ||||
1707 | bool NullIsValidLocation = NullPointerIsDefined(&F); | ||||
1708 | if ((isObjectSmallerThan( | ||||
1709 | O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL, | ||||
1710 | TLI, NullIsValidLocation)) || | ||||
1711 | (isObjectSmallerThan( | ||||
1712 | O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL, | ||||
1713 | TLI, NullIsValidLocation))) | ||||
1714 | return NoAlias; | ||||
1715 | |||||
1716 | // If one the accesses may be before the accessed pointer, canonicalize this | ||||
1717 | // by using unknown after-pointer sizes for both accesses. This is | ||||
1718 | // equivalent, because regardless of which pointer is lower, one of them | ||||
1719 | // will always came after the other, as long as the underlying objects aren't | ||||
1720 | // disjoint. We do this so that the rest of BasicAA does not have to deal | ||||
1721 | // with accesses before the base pointer, and to improve cache utilization by | ||||
1722 | // merging equivalent states. | ||||
1723 | if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) { | ||||
1724 | V1Size = LocationSize::afterPointer(); | ||||
1725 | V2Size = LocationSize::afterPointer(); | ||||
1726 | } | ||||
1727 | |||||
1728 | // Check the cache before climbing up use-def chains. This also terminates | ||||
1729 | // otherwise infinitely recursive queries. | ||||
1730 | AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), | ||||
1731 | MemoryLocation(V2, V2Size, V2AAInfo)); | ||||
1732 | if (V1 > V2) | ||||
1733 | std::swap(Locs.first, Locs.second); | ||||
1734 | std::pair<AAQueryInfo::AliasCacheT::iterator, bool> Pair = | ||||
1735 | AAQI.AliasCache.try_emplace(Locs, MayAlias); | ||||
1736 | if (!Pair.second) | ||||
1737 | return Pair.first->second; | ||||
1738 | |||||
1739 | if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { | ||||
1740 | AliasResult Result = | ||||
1741 | aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI); | ||||
1742 | if (Result != MayAlias) | ||||
1743 | return AAQI.updateResult(Locs, Result); | ||||
1744 | } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) { | ||||
1745 | AliasResult Result = | ||||
1746 | aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI); | ||||
1747 | if (Result != MayAlias) | ||||
1748 | return AAQI.updateResult(Locs, Result); | ||||
1749 | } | ||||
1750 | |||||
1751 | if (const PHINode *PN = dyn_cast<PHINode>(V1)) { | ||||
1752 | AliasResult Result = | ||||
1753 | aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); | ||||
1754 | if (Result != MayAlias) | ||||
1755 | return AAQI.updateResult(Locs, Result); | ||||
1756 | } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) { | ||||
1757 | AliasResult Result = | ||||
1758 | aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI); | ||||
1759 | if (Result != MayAlias) | ||||
1760 | return AAQI.updateResult(Locs, Result); | ||||
1761 | } | ||||
1762 | |||||
1763 | if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { | ||||
1764 | AliasResult Result = | ||||
1765 | aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); | ||||
1766 | if (Result != MayAlias) | ||||
1767 | return AAQI.updateResult(Locs, Result); | ||||
1768 | } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) { | ||||
1769 | AliasResult Result = | ||||
1770 | aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI); | ||||
1771 | if (Result != MayAlias) | ||||
1772 | return AAQI.updateResult(Locs, Result); | ||||
1773 | } | ||||
1774 | |||||
1775 | // If both pointers are pointing into the same object and one of them | ||||
1776 | // accesses the entire object, then the accesses must overlap in some way. | ||||
1777 | if (O1 == O2) | ||||
1778 | if (V1Size.isPrecise() && V2Size.isPrecise() && | ||||
1779 | (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || | ||||
1780 | isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) | ||||
1781 | return AAQI.updateResult(Locs, PartialAlias); | ||||
1782 | |||||
1783 | // Recurse back into the best AA results we have, potentially with refined | ||||
1784 | // memory locations. We have already ensured that BasicAA has a MayAlias | ||||
1785 | // cache result for these, so any recursion back into BasicAA won't loop. | ||||
1786 | AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second, AAQI); | ||||
1787 | if (Result != MayAlias) | ||||
1788 | return AAQI.updateResult(Locs, Result); | ||||
1789 | |||||
1790 | // MayAlias is already in the cache. | ||||
1791 | return MayAlias; | ||||
1792 | } | ||||
1793 | |||||
1794 | /// Check whether two Values can be considered equivalent. | ||||
1795 | /// | ||||
1796 | /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether | ||||
1797 | /// they can not be part of a cycle in the value graph by looking at all | ||||
1798 | /// visited phi nodes an making sure that the phis cannot reach the value. We | ||||
1799 | /// have to do this because we are looking through phi nodes (That is we say | ||||
1800 | /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). | ||||
1801 | bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, | ||||
1802 | const Value *V2) { | ||||
1803 | if (V != V2) | ||||
1804 | return false; | ||||
1805 | |||||
1806 | const Instruction *Inst = dyn_cast<Instruction>(V); | ||||
1807 | if (!Inst) | ||||
1808 | return true; | ||||
1809 | |||||
1810 | if (VisitedPhiBBs.empty()) | ||||
1811 | return true; | ||||
1812 | |||||
1813 | if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) | ||||
1814 | return false; | ||||
1815 | |||||
1816 | // Make sure that the visited phis cannot reach the Value. This ensures that | ||||
1817 | // the Values cannot come from different iterations of a potential cycle the | ||||
1818 | // phi nodes could be involved in. | ||||
1819 | for (auto *P : VisitedPhiBBs) | ||||
1820 | if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI)) | ||||
1821 | return false; | ||||
1822 | |||||
1823 | return true; | ||||
1824 | } | ||||
1825 | |||||
1826 | /// Computes the symbolic difference between two de-composed GEPs. | ||||
1827 | /// | ||||
1828 | /// Dest and Src are the variable indices from two decomposed GetElementPtr | ||||
1829 | /// instructions GEP1 and GEP2 which have common base pointers. | ||||
1830 | void BasicAAResult::GetIndexDifference( | ||||
1831 | SmallVectorImpl<VariableGEPIndex> &Dest, | ||||
1832 | const SmallVectorImpl<VariableGEPIndex> &Src) { | ||||
1833 | if (Src.empty()) | ||||
1834 | return; | ||||
1835 | |||||
1836 | for (unsigned i = 0, e = Src.size(); i != e; ++i) { | ||||
1837 | const Value *V = Src[i].V; | ||||
1838 | unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits; | ||||
1839 | APInt Scale = Src[i].Scale; | ||||
1840 | |||||
1841 | // Find V in Dest. This is N^2, but pointer indices almost never have more | ||||
1842 | // than a few variable indexes. | ||||
1843 | for (unsigned j = 0, e = Dest.size(); j != e; ++j) { | ||||
1844 | if (!isValueEqualInPotentialCycles(Dest[j].V, V) || | ||||
1845 | Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits) | ||||
1846 | continue; | ||||
1847 | |||||
1848 | // If we found it, subtract off Scale V's from the entry in Dest. If it | ||||
1849 | // goes to zero, remove the entry. | ||||
1850 | if (Dest[j].Scale != Scale) | ||||
1851 | Dest[j].Scale -= Scale; | ||||
1852 | else | ||||
1853 | Dest.erase(Dest.begin() + j); | ||||
1854 | Scale = 0; | ||||
1855 | break; | ||||
1856 | } | ||||
1857 | |||||
1858 | // If we didn't consume this entry, add it to the end of the Dest list. | ||||
1859 | if (!!Scale) { | ||||
1860 | VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale}; | ||||
1861 | Dest.push_back(Entry); | ||||
1862 | } | ||||
1863 | } | ||||
1864 | } | ||||
1865 | |||||
1866 | bool BasicAAResult::constantOffsetHeuristic( | ||||
1867 | const SmallVectorImpl<VariableGEPIndex> &VarIndices, | ||||
1868 | LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset, | ||||
1869 | AssumptionCache *AC, DominatorTree *DT) { | ||||
1870 | if (VarIndices.size() != 2 || !MaybeV1Size.hasValue() || | ||||
| |||||
1871 | !MaybeV2Size.hasValue()) | ||||
1872 | return false; | ||||
1873 | |||||
1874 | const uint64_t V1Size = MaybeV1Size.getValue(); | ||||
1875 | const uint64_t V2Size = MaybeV2Size.getValue(); | ||||
1876 | |||||
1877 | const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1]; | ||||
1878 | |||||
1879 | if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits || | ||||
1880 | Var0.Scale != -Var1.Scale) | ||||
1881 | return false; | ||||
1882 | |||||
1883 | unsigned Width = Var1.V->getType()->getIntegerBitWidth(); | ||||
1884 | |||||
1885 | // We'll strip off the Extensions of Var0 and Var1 and do another round | ||||
1886 | // of GetLinearExpression decomposition. In the example above, if Var0 | ||||
1887 | // is zext(%x + 1) we should get V1 == %x and V1Offset == 1. | ||||
1888 | |||||
1889 | APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0), | ||||
1890 | V1Offset(Width, 0); | ||||
1891 | bool NSW = true, NUW = true; | ||||
1892 | unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0; | ||||
1893 | const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, | ||||
1894 | V0SExtBits, DL, 0, AC, DT, NSW, NUW); | ||||
1895 | NSW = true; | ||||
1896 | NUW = true; | ||||
1897 | const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, | ||||
1898 | V1SExtBits, DL, 0, AC, DT, NSW, NUW); | ||||
1899 | |||||
1900 | if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits || | ||||
1901 | V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1)) | ||||
1902 | return false; | ||||
1903 | |||||
1904 | // We have a hit - Var0 and Var1 only differ by a constant offset! | ||||
1905 | |||||
1906 | // If we've been sext'ed then zext'd the maximum difference between Var0 and | ||||
1907 | // Var1 is possible to calculate, but we're just interested in the absolute | ||||
1908 | // minimum difference between the two. The minimum distance may occur due to | ||||
1909 | // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so | ||||
1910 | // the minimum distance between %i and %i + 5 is 3. | ||||
1911 | APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff; | ||||
1912 | MinDiff = APIntOps::umin(MinDiff, Wrapped); | ||||
1913 | APInt MinDiffBytes = | ||||
1914 | MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs(); | ||||
1915 | |||||
1916 | // We can't definitely say whether GEP1 is before or after V2 due to wrapping | ||||
1917 | // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other | ||||
1918 | // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and | ||||
1919 | // V2Size can fit in the MinDiffBytes gap. | ||||
1920 | return MinDiffBytes.uge(V1Size + BaseOffset.abs()) && | ||||
1921 | MinDiffBytes.uge(V2Size + BaseOffset.abs()); | ||||
1922 | } | ||||
1923 | |||||
1924 | //===----------------------------------------------------------------------===// | ||||
1925 | // BasicAliasAnalysis Pass | ||||
1926 | //===----------------------------------------------------------------------===// | ||||
1927 | |||||
1928 | AnalysisKey BasicAA::Key; | ||||
1929 | |||||
1930 | BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { | ||||
1931 | return BasicAAResult(F.getParent()->getDataLayout(), | ||||
1932 | F, | ||||
1933 | AM.getResult<TargetLibraryAnalysis>(F), | ||||
1934 | AM.getResult<AssumptionAnalysis>(F), | ||||
1935 | &AM.getResult<DominatorTreeAnalysis>(F), | ||||
1936 | AM.getCachedResult<LoopAnalysis>(F), | ||||
1937 | AM.getCachedResult<PhiValuesAnalysis>(F)); | ||||
1938 | } | ||||
1939 | |||||
1940 | BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { | ||||
1941 | initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); | ||||
1942 | } | ||||
1943 | |||||
1944 | char BasicAAWrapperPass::ID = 0; | ||||
1945 | |||||
1946 | void BasicAAWrapperPass::anchor() {} | ||||
1947 | |||||
1948 | INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa",static void *initializeBasicAAWrapperPassPassOnce(PassRegistry &Registry) { | ||||
1949 | "Basic Alias Analysis (stateless AA impl)", true, true)static void *initializeBasicAAWrapperPassPassOnce(PassRegistry &Registry) { | ||||
1950 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | ||||
1951 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | ||||
1952 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry); | ||||
1953 | INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass)initializePhiValuesWrapperPassPass(Registry); | ||||
1954 | INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa",PassInfo *PI = new PassInfo( "Basic Alias Analysis (stateless AA impl)" , "basic-aa", &BasicAAWrapperPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<BasicAAWrapperPass>), true, true); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeBasicAAWrapperPassPassFlag; void llvm::initializeBasicAAWrapperPassPass (PassRegistry &Registry) { llvm::call_once(InitializeBasicAAWrapperPassPassFlag , initializeBasicAAWrapperPassPassOnce, std::ref(Registry)); } | ||||
1955 | "Basic Alias Analysis (stateless AA impl)", true, true)PassInfo *PI = new PassInfo( "Basic Alias Analysis (stateless AA impl)" , "basic-aa", &BasicAAWrapperPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<BasicAAWrapperPass>), true, true); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeBasicAAWrapperPassPassFlag; void llvm::initializeBasicAAWrapperPassPass (PassRegistry &Registry) { llvm::call_once(InitializeBasicAAWrapperPassPassFlag , initializeBasicAAWrapperPassPassOnce, std::ref(Registry)); } | ||||
1956 | |||||
1957 | FunctionPass *llvm::createBasicAAWrapperPass() { | ||||
1958 | return new BasicAAWrapperPass(); | ||||
1959 | } | ||||
1960 | |||||
1961 | bool BasicAAWrapperPass::runOnFunction(Function &F) { | ||||
1962 | auto &ACT = getAnalysis<AssumptionCacheTracker>(); | ||||
1963 | auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); | ||||
1964 | auto &DTWP = getAnalysis<DominatorTreeWrapperPass>(); | ||||
1965 | auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); | ||||
1966 | auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>(); | ||||
1967 | |||||
1968 | Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, | ||||
1969 | TLIWP.getTLI(F), ACT.getAssumptionCache(F), | ||||
1970 | &DTWP.getDomTree(), | ||||
1971 | LIWP ? &LIWP->getLoopInfo() : nullptr, | ||||
1972 | PVWP ? &PVWP->getResult() : nullptr)); | ||||
1973 | |||||
1974 | return false; | ||||
1975 | } | ||||
1976 | |||||
1977 | void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | ||||
1978 | AU.setPreservesAll(); | ||||
1979 | AU.addRequired<AssumptionCacheTracker>(); | ||||
1980 | AU.addRequired<DominatorTreeWrapperPass>(); | ||||
1981 | AU.addRequired<TargetLibraryInfoWrapperPass>(); | ||||
1982 | AU.addUsedIfAvailable<PhiValuesWrapperPass>(); | ||||
1983 | } | ||||
1984 | |||||
1985 | BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { | ||||
1986 | return BasicAAResult( | ||||
1987 | F.getParent()->getDataLayout(), F, | ||||
1988 | P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F), | ||||
1989 | P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F)); | ||||
1990 | } |
1 | //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | /// | |||
9 | /// \file | |||
10 | /// This file implements a class to represent arbitrary precision | |||
11 | /// integral constant values and operations on them. | |||
12 | /// | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #ifndef LLVM_ADT_APINT_H | |||
16 | #define LLVM_ADT_APINT_H | |||
17 | ||||
18 | #include "llvm/Support/Compiler.h" | |||
19 | #include "llvm/Support/MathExtras.h" | |||
20 | #include <cassert> | |||
21 | #include <climits> | |||
22 | #include <cstring> | |||
23 | #include <string> | |||
24 | ||||
25 | namespace llvm { | |||
26 | class FoldingSetNodeID; | |||
27 | class StringRef; | |||
28 | class hash_code; | |||
29 | class raw_ostream; | |||
30 | ||||
31 | template <typename T> class SmallVectorImpl; | |||
32 | template <typename T> class ArrayRef; | |||
33 | template <typename T> class Optional; | |||
34 | template <typename T> struct DenseMapInfo; | |||
35 | ||||
36 | class APInt; | |||
37 | ||||
38 | inline APInt operator-(APInt); | |||
39 | ||||
40 | //===----------------------------------------------------------------------===// | |||
41 | // APInt Class | |||
42 | //===----------------------------------------------------------------------===// | |||
43 | ||||
44 | /// Class for arbitrary precision integers. | |||
45 | /// | |||
46 | /// APInt is a functional replacement for common case unsigned integer type like | |||
47 | /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width | |||
48 | /// integer sizes and large integer value types such as 3-bits, 15-bits, or more | |||
49 | /// than 64-bits of precision. APInt provides a variety of arithmetic operators | |||
50 | /// and methods to manipulate integer values of any bit-width. It supports both | |||
51 | /// the typical integer arithmetic and comparison operations as well as bitwise | |||
52 | /// manipulation. | |||
53 | /// | |||
54 | /// The class has several invariants worth noting: | |||
55 | /// * All bit, byte, and word positions are zero-based. | |||
56 | /// * Once the bit width is set, it doesn't change except by the Truncate, | |||
57 | /// SignExtend, or ZeroExtend operations. | |||
58 | /// * All binary operators must be on APInt instances of the same bit width. | |||
59 | /// Attempting to use these operators on instances with different bit | |||
60 | /// widths will yield an assertion. | |||
61 | /// * The value is stored canonically as an unsigned value. For operations | |||
62 | /// where it makes a difference, there are both signed and unsigned variants | |||
63 | /// of the operation. For example, sdiv and udiv. However, because the bit | |||
64 | /// widths must be the same, operations such as Mul and Add produce the same | |||
65 | /// results regardless of whether the values are interpreted as signed or | |||
66 | /// not. | |||
67 | /// * In general, the class tries to follow the style of computation that LLVM | |||
68 | /// uses in its IR. This simplifies its use for LLVM. | |||
69 | /// | |||
70 | class LLVM_NODISCARD[[clang::warn_unused_result]] APInt { | |||
71 | public: | |||
72 | typedef uint64_t WordType; | |||
73 | ||||
74 | /// This enum is used to hold the constants we needed for APInt. | |||
75 | enum : unsigned { | |||
76 | /// Byte size of a word. | |||
77 | APINT_WORD_SIZE = sizeof(WordType), | |||
78 | /// Bits in a word. | |||
79 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8 | |||
80 | }; | |||
81 | ||||
82 | enum class Rounding { | |||
83 | DOWN, | |||
84 | TOWARD_ZERO, | |||
85 | UP, | |||
86 | }; | |||
87 | ||||
88 | static constexpr WordType WORDTYPE_MAX = ~WordType(0); | |||
89 | ||||
90 | private: | |||
91 | /// This union is used to store the integer value. When the | |||
92 | /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. | |||
93 | union { | |||
94 | uint64_t VAL; ///< Used to store the <= 64 bits integer value. | |||
95 | uint64_t *pVal; ///< Used to store the >64 bits integer value. | |||
96 | } U; | |||
97 | ||||
98 | unsigned BitWidth; ///< The number of bits in this APInt. | |||
99 | ||||
100 | friend struct DenseMapInfo<APInt>; | |||
101 | ||||
102 | friend class APSInt; | |||
103 | ||||
104 | /// Fast internal constructor | |||
105 | /// | |||
106 | /// This constructor is used only internally for speed of construction of | |||
107 | /// temporaries. It is unsafe for general use so it is not public. | |||
108 | APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { | |||
109 | U.pVal = val; | |||
110 | } | |||
111 | ||||
112 | /// Determine if this APInt just has one word to store value. | |||
113 | /// | |||
114 | /// \returns true if the number of bits <= 64, false otherwise. | |||
115 | bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } | |||
116 | ||||
117 | /// Determine which word a bit is in. | |||
118 | /// | |||
119 | /// \returns the word position for the specified bit position. | |||
120 | static unsigned whichWord(unsigned bitPosition) { | |||
121 | return bitPosition / APINT_BITS_PER_WORD; | |||
122 | } | |||
123 | ||||
124 | /// Determine which bit in a word a bit is in. | |||
125 | /// | |||
126 | /// \returns the bit position in a word for the specified bit position | |||
127 | /// in the APInt. | |||
128 | static unsigned whichBit(unsigned bitPosition) { | |||
129 | return bitPosition % APINT_BITS_PER_WORD; | |||
130 | } | |||
131 | ||||
132 | /// Get a single bit mask. | |||
133 | /// | |||
134 | /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set | |||
135 | /// This method generates and returns a uint64_t (word) mask for a single | |||
136 | /// bit at a specific bit position. This is used to mask the bit in the | |||
137 | /// corresponding word. | |||
138 | static uint64_t maskBit(unsigned bitPosition) { | |||
139 | return 1ULL << whichBit(bitPosition); | |||
140 | } | |||
141 | ||||
142 | /// Clear unused high order bits | |||
143 | /// | |||
144 | /// This method is used internally to clear the top "N" bits in the high order | |||
145 | /// word that are not used by the APInt. This is needed after the most | |||
146 | /// significant word is assigned a value to ensure that those bits are | |||
147 | /// zero'd out. | |||
148 | APInt &clearUnusedBits() { | |||
149 | // Compute how many bits are used in the final word | |||
150 | unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1; | |||
151 | ||||
152 | // Mask out the high bits. | |||
153 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits); | |||
154 | if (isSingleWord()) | |||
155 | U.VAL &= mask; | |||
156 | else | |||
157 | U.pVal[getNumWords() - 1] &= mask; | |||
158 | return *this; | |||
159 | } | |||
160 | ||||
161 | /// Get the word corresponding to a bit position | |||
162 | /// \returns the corresponding word for the specified bit position. | |||
163 | uint64_t getWord(unsigned bitPosition) const { | |||
164 | return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; | |||
165 | } | |||
166 | ||||
167 | /// Utility method to change the bit width of this APInt to new bit width, | |||
168 | /// allocating and/or deallocating as necessary. There is no guarantee on the | |||
169 | /// value of any bits upon return. Caller should populate the bits after. | |||
170 | void reallocate(unsigned NewBitWidth); | |||
171 | ||||
172 | /// Convert a char array into an APInt | |||
173 | /// | |||
174 | /// \param radix 2, 8, 10, 16, or 36 | |||
175 | /// Converts a string into a number. The string must be non-empty | |||
176 | /// and well-formed as a number of the given base. The bit-width | |||
177 | /// must be sufficient to hold the result. | |||
178 | /// | |||
179 | /// This is used by the constructors that take string arguments. | |||
180 | /// | |||
181 | /// StringRef::getAsInteger is superficially similar but (1) does | |||
182 | /// not assume that the string is well-formed and (2) grows the | |||
183 | /// result to hold the input. | |||
184 | void fromString(unsigned numBits, StringRef str, uint8_t radix); | |||
185 | ||||
186 | /// An internal division function for dividing APInts. | |||
187 | /// | |||
188 | /// This is used by the toString method to divide by the radix. It simply | |||
189 | /// provides a more convenient form of divide for internal use since KnuthDiv | |||
190 | /// has specific constraints on its inputs. If those constraints are not met | |||
191 | /// then it provides a simpler form of divide. | |||
192 | static void divide(const WordType *LHS, unsigned lhsWords, | |||
193 | const WordType *RHS, unsigned rhsWords, WordType *Quotient, | |||
194 | WordType *Remainder); | |||
195 | ||||
196 | /// out-of-line slow case for inline constructor | |||
197 | void initSlowCase(uint64_t val, bool isSigned); | |||
198 | ||||
199 | /// shared code between two array constructors | |||
200 | void initFromArray(ArrayRef<uint64_t> array); | |||
201 | ||||
202 | /// out-of-line slow case for inline copy constructor | |||
203 | void initSlowCase(const APInt &that); | |||
204 | ||||
205 | /// out-of-line slow case for shl | |||
206 | void shlSlowCase(unsigned ShiftAmt); | |||
207 | ||||
208 | /// out-of-line slow case for lshr. | |||
209 | void lshrSlowCase(unsigned ShiftAmt); | |||
210 | ||||
211 | /// out-of-line slow case for ashr. | |||
212 | void ashrSlowCase(unsigned ShiftAmt); | |||
213 | ||||
214 | /// out-of-line slow case for operator= | |||
215 | void AssignSlowCase(const APInt &RHS); | |||
216 | ||||
217 | /// out-of-line slow case for operator== | |||
218 | bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
219 | ||||
220 | /// out-of-line slow case for countLeadingZeros | |||
221 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
222 | ||||
223 | /// out-of-line slow case for countLeadingOnes. | |||
224 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
225 | ||||
226 | /// out-of-line slow case for countTrailingZeros. | |||
227 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
228 | ||||
229 | /// out-of-line slow case for countTrailingOnes | |||
230 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
231 | ||||
232 | /// out-of-line slow case for countPopulation | |||
233 | unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
234 | ||||
235 | /// out-of-line slow case for intersects. | |||
236 | bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
237 | ||||
238 | /// out-of-line slow case for isSubsetOf. | |||
239 | bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
240 | ||||
241 | /// out-of-line slow case for setBits. | |||
242 | void setBitsSlowCase(unsigned loBit, unsigned hiBit); | |||
243 | ||||
244 | /// out-of-line slow case for flipAllBits. | |||
245 | void flipAllBitsSlowCase(); | |||
246 | ||||
247 | /// out-of-line slow case for operator&=. | |||
248 | void AndAssignSlowCase(const APInt& RHS); | |||
249 | ||||
250 | /// out-of-line slow case for operator|=. | |||
251 | void OrAssignSlowCase(const APInt& RHS); | |||
252 | ||||
253 | /// out-of-line slow case for operator^=. | |||
254 | void XorAssignSlowCase(const APInt& RHS); | |||
255 | ||||
256 | /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
257 | /// to, or greater than RHS. | |||
258 | int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
259 | ||||
260 | /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
261 | /// to, or greater than RHS. | |||
262 | int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
263 | ||||
264 | public: | |||
265 | /// \name Constructors | |||
266 | /// @{ | |||
267 | ||||
268 | /// Create a new APInt of numBits width, initialized as val. | |||
269 | /// | |||
270 | /// If isSigned is true then val is treated as if it were a signed value | |||
271 | /// (i.e. as an int64_t) and the appropriate sign extension to the bit width | |||
272 | /// will be done. Otherwise, no sign extension occurs (high order bits beyond | |||
273 | /// the range of val are zero filled). | |||
274 | /// | |||
275 | /// \param numBits the bit width of the constructed APInt | |||
276 | /// \param val the initial value of the APInt | |||
277 | /// \param isSigned how to treat signedness of val | |||
278 | APInt(unsigned numBits, uint64_t val, bool isSigned = false) | |||
279 | : BitWidth(numBits) { | |||
280 | assert(BitWidth && "bitwidth too small")((BitWidth && "bitwidth too small") ? static_cast< void> (0) : __assert_fail ("BitWidth && \"bitwidth too small\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 280, __PRETTY_FUNCTION__)); | |||
281 | if (isSingleWord()) { | |||
282 | U.VAL = val; | |||
283 | clearUnusedBits(); | |||
284 | } else { | |||
285 | initSlowCase(val, isSigned); | |||
286 | } | |||
287 | } | |||
288 | ||||
289 | /// Construct an APInt of numBits width, initialized as bigVal[]. | |||
290 | /// | |||
291 | /// Note that bigVal.size() can be smaller or larger than the corresponding | |||
292 | /// bit width but any extraneous bits will be dropped. | |||
293 | /// | |||
294 | /// \param numBits the bit width of the constructed APInt | |||
295 | /// \param bigVal a sequence of words to form the initial value of the APInt | |||
296 | APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); | |||
297 | ||||
298 | /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but | |||
299 | /// deprecated because this constructor is prone to ambiguity with the | |||
300 | /// APInt(unsigned, uint64_t, bool) constructor. | |||
301 | /// | |||
302 | /// If this overload is ever deleted, care should be taken to prevent calls | |||
303 | /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) | |||
304 | /// constructor. | |||
305 | APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); | |||
306 | ||||
307 | /// Construct an APInt from a string representation. | |||
308 | /// | |||
309 | /// This constructor interprets the string \p str in the given radix. The | |||
310 | /// interpretation stops when the first character that is not suitable for the | |||
311 | /// radix is encountered, or the end of the string. Acceptable radix values | |||
312 | /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the | |||
313 | /// string to require more bits than numBits. | |||
314 | /// | |||
315 | /// \param numBits the bit width of the constructed APInt | |||
316 | /// \param str the string to be interpreted | |||
317 | /// \param radix the radix to use for the conversion | |||
318 | APInt(unsigned numBits, StringRef str, uint8_t radix); | |||
319 | ||||
320 | /// Simply makes *this a copy of that. | |||
321 | /// Copy Constructor. | |||
322 | APInt(const APInt &that) : BitWidth(that.BitWidth) { | |||
323 | if (isSingleWord()) | |||
324 | U.VAL = that.U.VAL; | |||
325 | else | |||
326 | initSlowCase(that); | |||
327 | } | |||
328 | ||||
329 | /// Move Constructor. | |||
330 | APInt(APInt &&that) : BitWidth(that.BitWidth) { | |||
331 | memcpy(&U, &that.U, sizeof(U)); | |||
332 | that.BitWidth = 0; | |||
333 | } | |||
334 | ||||
335 | /// Destructor. | |||
336 | ~APInt() { | |||
337 | if (needsCleanup()) | |||
338 | delete[] U.pVal; | |||
339 | } | |||
340 | ||||
341 | /// Default constructor that creates an uninteresting APInt | |||
342 | /// representing a 1-bit zero value. | |||
343 | /// | |||
344 | /// This is useful for object deserialization (pair this with the static | |||
345 | /// method Read). | |||
346 | explicit APInt() : BitWidth(1) { U.VAL = 0; } | |||
347 | ||||
348 | /// Returns whether this instance allocated memory. | |||
349 | bool needsCleanup() const { return !isSingleWord(); } | |||
350 | ||||
351 | /// Used to insert APInt objects, or objects that contain APInt objects, into | |||
352 | /// FoldingSets. | |||
353 | void Profile(FoldingSetNodeID &id) const; | |||
354 | ||||
355 | /// @} | |||
356 | /// \name Value Tests | |||
357 | /// @{ | |||
358 | ||||
359 | /// Determine sign of this APInt. | |||
360 | /// | |||
361 | /// This tests the high bit of this APInt to determine if it is set. | |||
362 | /// | |||
363 | /// \returns true if this APInt is negative, false otherwise | |||
364 | bool isNegative() const { return (*this)[BitWidth - 1]; } | |||
365 | ||||
366 | /// Determine if this APInt Value is non-negative (>= 0) | |||
367 | /// | |||
368 | /// This tests the high bit of the APInt to determine if it is unset. | |||
369 | bool isNonNegative() const { return !isNegative(); } | |||
370 | ||||
371 | /// Determine if sign bit of this APInt is set. | |||
372 | /// | |||
373 | /// This tests the high bit of this APInt to determine if it is set. | |||
374 | /// | |||
375 | /// \returns true if this APInt has its sign bit set, false otherwise. | |||
376 | bool isSignBitSet() const { return (*this)[BitWidth-1]; } | |||
377 | ||||
378 | /// Determine if sign bit of this APInt is clear. | |||
379 | /// | |||
380 | /// This tests the high bit of this APInt to determine if it is clear. | |||
381 | /// | |||
382 | /// \returns true if this APInt has its sign bit clear, false otherwise. | |||
383 | bool isSignBitClear() const { return !isSignBitSet(); } | |||
384 | ||||
385 | /// Determine if this APInt Value is positive. | |||
386 | /// | |||
387 | /// This tests if the value of this APInt is positive (> 0). Note | |||
388 | /// that 0 is not a positive value. | |||
389 | /// | |||
390 | /// \returns true if this APInt is positive. | |||
391 | bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); } | |||
392 | ||||
393 | /// Determine if this APInt Value is non-positive (<= 0). | |||
394 | /// | |||
395 | /// \returns true if this APInt is non-positive. | |||
396 | bool isNonPositive() const { return !isStrictlyPositive(); } | |||
397 | ||||
398 | /// Determine if all bits are set | |||
399 | /// | |||
400 | /// This checks to see if the value has all bits of the APInt are set or not. | |||
401 | bool isAllOnesValue() const { | |||
402 | if (isSingleWord()) | |||
403 | return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth); | |||
404 | return countTrailingOnesSlowCase() == BitWidth; | |||
405 | } | |||
406 | ||||
407 | /// Determine if all bits are clear | |||
408 | /// | |||
409 | /// This checks to see if the value has all bits of the APInt are clear or | |||
410 | /// not. | |||
411 | bool isNullValue() const { return !*this; } | |||
412 | ||||
413 | /// Determine if this is a value of 1. | |||
414 | /// | |||
415 | /// This checks to see if the value of this APInt is one. | |||
416 | bool isOneValue() const { | |||
417 | if (isSingleWord()) | |||
418 | return U.VAL == 1; | |||
419 | return countLeadingZerosSlowCase() == BitWidth - 1; | |||
420 | } | |||
421 | ||||
422 | /// Determine if this is the largest unsigned value. | |||
423 | /// | |||
424 | /// This checks to see if the value of this APInt is the maximum unsigned | |||
425 | /// value for the APInt's bit width. | |||
426 | bool isMaxValue() const { return isAllOnesValue(); } | |||
427 | ||||
428 | /// Determine if this is the largest signed value. | |||
429 | /// | |||
430 | /// This checks to see if the value of this APInt is the maximum signed | |||
431 | /// value for the APInt's bit width. | |||
432 | bool isMaxSignedValue() const { | |||
433 | if (isSingleWord()) | |||
434 | return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); | |||
435 | return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; | |||
436 | } | |||
437 | ||||
438 | /// Determine if this is the smallest unsigned value. | |||
439 | /// | |||
440 | /// This checks to see if the value of this APInt is the minimum unsigned | |||
441 | /// value for the APInt's bit width. | |||
442 | bool isMinValue() const { return isNullValue(); } | |||
443 | ||||
444 | /// Determine if this is the smallest signed value. | |||
445 | /// | |||
446 | /// This checks to see if the value of this APInt is the minimum signed | |||
447 | /// value for the APInt's bit width. | |||
448 | bool isMinSignedValue() const { | |||
449 | if (isSingleWord()) | |||
450 | return U.VAL == (WordType(1) << (BitWidth - 1)); | |||
451 | return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; | |||
452 | } | |||
453 | ||||
454 | /// Check if this APInt has an N-bits unsigned integer value. | |||
455 | bool isIntN(unsigned N) const { | |||
456 | assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail ("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 456, __PRETTY_FUNCTION__)); | |||
457 | return getActiveBits() <= N; | |||
458 | } | |||
459 | ||||
460 | /// Check if this APInt has an N-bits signed integer value. | |||
461 | bool isSignedIntN(unsigned N) const { | |||
462 | assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail ("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 462, __PRETTY_FUNCTION__)); | |||
463 | return getMinSignedBits() <= N; | |||
464 | } | |||
465 | ||||
466 | /// Check if this APInt's value is a power of two greater than zero. | |||
467 | /// | |||
468 | /// \returns true if the argument APInt value is a power of two > 0. | |||
469 | bool isPowerOf2() const { | |||
470 | if (isSingleWord()) | |||
471 | return isPowerOf2_64(U.VAL); | |||
472 | return countPopulationSlowCase() == 1; | |||
473 | } | |||
474 | ||||
475 | /// Check if the APInt's value is returned by getSignMask. | |||
476 | /// | |||
477 | /// \returns true if this is the value returned by getSignMask. | |||
478 | bool isSignMask() const { return isMinSignedValue(); } | |||
479 | ||||
480 | /// Convert APInt to a boolean value. | |||
481 | /// | |||
482 | /// This converts the APInt to a boolean value as a test against zero. | |||
483 | bool getBoolValue() const { return !!*this; } | |||
484 | ||||
485 | /// If this value is smaller than the specified limit, return it, otherwise | |||
486 | /// return the limit value. This causes the value to saturate to the limit. | |||
487 | uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const { | |||
488 | return ugt(Limit) ? Limit : getZExtValue(); | |||
489 | } | |||
490 | ||||
491 | /// Check if the APInt consists of a repeated bit pattern. | |||
492 | /// | |||
493 | /// e.g. 0x01010101 satisfies isSplat(8). | |||
494 | /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit | |||
495 | /// width without remainder. | |||
496 | bool isSplat(unsigned SplatSizeInBits) const; | |||
497 | ||||
498 | /// \returns true if this APInt value is a sequence of \param numBits ones | |||
499 | /// starting at the least significant bit with the remainder zero. | |||
500 | bool isMask(unsigned numBits) const { | |||
501 | assert(numBits != 0 && "numBits must be non-zero")((numBits != 0 && "numBits must be non-zero") ? static_cast <void> (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 501, __PRETTY_FUNCTION__)); | |||
502 | assert(numBits <= BitWidth && "numBits out of range")((numBits <= BitWidth && "numBits out of range") ? static_cast<void> (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 502, __PRETTY_FUNCTION__)); | |||
503 | if (isSingleWord()) | |||
504 | return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits)); | |||
505 | unsigned Ones = countTrailingOnesSlowCase(); | |||
506 | return (numBits == Ones) && | |||
507 | ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
508 | } | |||
509 | ||||
510 | /// \returns true if this APInt is a non-empty sequence of ones starting at | |||
511 | /// the least significant bit with the remainder zero. | |||
512 | /// Ex. isMask(0x0000FFFFU) == true. | |||
513 | bool isMask() const { | |||
514 | if (isSingleWord()) | |||
515 | return isMask_64(U.VAL); | |||
516 | unsigned Ones = countTrailingOnesSlowCase(); | |||
517 | return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
518 | } | |||
519 | ||||
520 | /// Return true if this APInt value contains a sequence of ones with | |||
521 | /// the remainder zero. | |||
522 | bool isShiftedMask() const { | |||
523 | if (isSingleWord()) | |||
524 | return isShiftedMask_64(U.VAL); | |||
525 | unsigned Ones = countPopulationSlowCase(); | |||
526 | unsigned LeadZ = countLeadingZerosSlowCase(); | |||
527 | return (Ones + LeadZ + countTrailingZeros()) == BitWidth; | |||
528 | } | |||
529 | ||||
530 | /// @} | |||
531 | /// \name Value Generators | |||
532 | /// @{ | |||
533 | ||||
534 | /// Gets maximum unsigned value of APInt for specific bit width. | |||
535 | static APInt getMaxValue(unsigned numBits) { | |||
536 | return getAllOnesValue(numBits); | |||
537 | } | |||
538 | ||||
539 | /// Gets maximum signed value of APInt for a specific bit width. | |||
540 | static APInt getSignedMaxValue(unsigned numBits) { | |||
541 | APInt API = getAllOnesValue(numBits); | |||
542 | API.clearBit(numBits - 1); | |||
543 | return API; | |||
544 | } | |||
545 | ||||
546 | /// Gets minimum unsigned value of APInt for a specific bit width. | |||
547 | static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } | |||
548 | ||||
549 | /// Gets minimum signed value of APInt for a specific bit width. | |||
550 | static APInt getSignedMinValue(unsigned numBits) { | |||
551 | APInt API(numBits, 0); | |||
552 | API.setBit(numBits - 1); | |||
553 | return API; | |||
554 | } | |||
555 | ||||
556 | /// Get the SignMask for a specific bit width. | |||
557 | /// | |||
558 | /// This is just a wrapper function of getSignedMinValue(), and it helps code | |||
559 | /// readability when we want to get a SignMask. | |||
560 | static APInt getSignMask(unsigned BitWidth) { | |||
561 | return getSignedMinValue(BitWidth); | |||
562 | } | |||
563 | ||||
564 | /// Get the all-ones value. | |||
565 | /// | |||
566 | /// \returns the all-ones value for an APInt of the specified bit-width. | |||
567 | static APInt getAllOnesValue(unsigned numBits) { | |||
568 | return APInt(numBits, WORDTYPE_MAX, true); | |||
569 | } | |||
570 | ||||
571 | /// Get the '0' value. | |||
572 | /// | |||
573 | /// \returns the '0' value for an APInt of the specified bit-width. | |||
574 | static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); } | |||
575 | ||||
576 | /// Compute an APInt containing numBits highbits from this APInt. | |||
577 | /// | |||
578 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
579 | /// the low bits and right shift to the least significant bit. | |||
580 | /// | |||
581 | /// \returns the high "numBits" bits of this APInt. | |||
582 | APInt getHiBits(unsigned numBits) const; | |||
583 | ||||
584 | /// Compute an APInt containing numBits lowbits from this APInt. | |||
585 | /// | |||
586 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
587 | /// the high bits. | |||
588 | /// | |||
589 | /// \returns the low "numBits" bits of this APInt. | |||
590 | APInt getLoBits(unsigned numBits) const; | |||
591 | ||||
592 | /// Return an APInt with exactly one bit set in the result. | |||
593 | static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { | |||
594 | APInt Res(numBits, 0); | |||
595 | Res.setBit(BitNo); | |||
596 | return Res; | |||
597 | } | |||
598 | ||||
599 | /// Get a value with a block of bits set. | |||
600 | /// | |||
601 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
602 | /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other | |||
603 | /// bits will be zero. For example, with parameters(32, 0, 16) you would get | |||
604 | /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than | |||
605 | /// \p hiBit. | |||
606 | /// | |||
607 | /// \param numBits the intended bit width of the result | |||
608 | /// \param loBit the index of the lowest bit set. | |||
609 | /// \param hiBit the index of the highest bit set. | |||
610 | /// | |||
611 | /// \returns An APInt value with the requested bits set. | |||
612 | static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { | |||
613 | assert(loBit <= hiBit && "loBit greater than hiBit")((loBit <= hiBit && "loBit greater than hiBit") ? static_cast <void> (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 613, __PRETTY_FUNCTION__)); | |||
614 | APInt Res(numBits, 0); | |||
615 | Res.setBits(loBit, hiBit); | |||
616 | return Res; | |||
617 | } | |||
618 | ||||
619 | /// Wrap version of getBitsSet. | |||
620 | /// If \p hiBit is bigger than \p loBit, this is same with getBitsSet. | |||
621 | /// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example, | |||
622 | /// with parameters (32, 28, 4), you would get 0xF000000F. | |||
623 | /// If \p hiBit is equal to \p loBit, you would get a result with all bits | |||
624 | /// set. | |||
625 | static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, | |||
626 | unsigned hiBit) { | |||
627 | APInt Res(numBits, 0); | |||
628 | Res.setBitsWithWrap(loBit, hiBit); | |||
629 | return Res; | |||
630 | } | |||
631 | ||||
632 | /// Get a value with upper bits starting at loBit set. | |||
633 | /// | |||
634 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
635 | /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other | |||
636 | /// bits will be zero. For example, with parameters(32, 12) you would get | |||
637 | /// 0xFFFFF000. | |||
638 | /// | |||
639 | /// \param numBits the intended bit width of the result | |||
640 | /// \param loBit the index of the lowest bit to set. | |||
641 | /// | |||
642 | /// \returns An APInt value with the requested bits set. | |||
643 | static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { | |||
644 | APInt Res(numBits, 0); | |||
645 | Res.setBitsFrom(loBit); | |||
646 | return Res; | |||
647 | } | |||
648 | ||||
649 | /// Get a value with high bits set | |||
650 | /// | |||
651 | /// Constructs an APInt value that has the top hiBitsSet bits set. | |||
652 | /// | |||
653 | /// \param numBits the bitwidth of the result | |||
654 | /// \param hiBitsSet the number of high-order bits set in the result. | |||
655 | static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { | |||
656 | APInt Res(numBits, 0); | |||
657 | Res.setHighBits(hiBitsSet); | |||
658 | return Res; | |||
659 | } | |||
660 | ||||
661 | /// Get a value with low bits set | |||
662 | /// | |||
663 | /// Constructs an APInt value that has the bottom loBitsSet bits set. | |||
664 | /// | |||
665 | /// \param numBits the bitwidth of the result | |||
666 | /// \param loBitsSet the number of low-order bits set in the result. | |||
667 | static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { | |||
668 | APInt Res(numBits, 0); | |||
669 | Res.setLowBits(loBitsSet); | |||
670 | return Res; | |||
671 | } | |||
672 | ||||
673 | /// Return a value containing V broadcasted over NewLen bits. | |||
674 | static APInt getSplat(unsigned NewLen, const APInt &V); | |||
675 | ||||
676 | /// Determine if two APInts have the same value, after zero-extending | |||
677 | /// one of them (if needed!) to ensure that the bit-widths match. | |||
678 | static bool isSameValue(const APInt &I1, const APInt &I2) { | |||
679 | if (I1.getBitWidth() == I2.getBitWidth()) | |||
680 | return I1 == I2; | |||
681 | ||||
682 | if (I1.getBitWidth() > I2.getBitWidth()) | |||
683 | return I1 == I2.zext(I1.getBitWidth()); | |||
684 | ||||
685 | return I1.zext(I2.getBitWidth()) == I2; | |||
686 | } | |||
687 | ||||
688 | /// Overload to compute a hash_code for an APInt value. | |||
689 | friend hash_code hash_value(const APInt &Arg); | |||
690 | ||||
691 | /// This function returns a pointer to the internal storage of the APInt. | |||
692 | /// This is useful for writing out the APInt in binary form without any | |||
693 | /// conversions. | |||
694 | const uint64_t *getRawData() const { | |||
695 | if (isSingleWord()) | |||
696 | return &U.VAL; | |||
697 | return &U.pVal[0]; | |||
698 | } | |||
699 | ||||
700 | /// @} | |||
701 | /// \name Unary Operators | |||
702 | /// @{ | |||
703 | ||||
704 | /// Postfix increment operator. | |||
705 | /// | |||
706 | /// Increments *this by 1. | |||
707 | /// | |||
708 | /// \returns a new APInt value representing the original value of *this. | |||
709 | const APInt operator++(int) { | |||
710 | APInt API(*this); | |||
711 | ++(*this); | |||
712 | return API; | |||
713 | } | |||
714 | ||||
715 | /// Prefix increment operator. | |||
716 | /// | |||
717 | /// \returns *this incremented by one | |||
718 | APInt &operator++(); | |||
719 | ||||
720 | /// Postfix decrement operator. | |||
721 | /// | |||
722 | /// Decrements *this by 1. | |||
723 | /// | |||
724 | /// \returns a new APInt value representing the original value of *this. | |||
725 | const APInt operator--(int) { | |||
726 | APInt API(*this); | |||
727 | --(*this); | |||
728 | return API; | |||
729 | } | |||
730 | ||||
731 | /// Prefix decrement operator. | |||
732 | /// | |||
733 | /// \returns *this decremented by one. | |||
734 | APInt &operator--(); | |||
735 | ||||
736 | /// Logical negation operator. | |||
737 | /// | |||
738 | /// Performs logical negation operation on this APInt. | |||
739 | /// | |||
740 | /// \returns true if *this is zero, false otherwise. | |||
741 | bool operator!() const { | |||
742 | if (isSingleWord()) | |||
743 | return U.VAL == 0; | |||
744 | return countLeadingZerosSlowCase() == BitWidth; | |||
745 | } | |||
746 | ||||
747 | /// @} | |||
748 | /// \name Assignment Operators | |||
749 | /// @{ | |||
750 | ||||
751 | /// Copy assignment operator. | |||
752 | /// | |||
753 | /// \returns *this after assignment of RHS. | |||
754 | APInt &operator=(const APInt &RHS) { | |||
755 | // If the bitwidths are the same, we can avoid mucking with memory | |||
756 | if (isSingleWord() && RHS.isSingleWord()) { | |||
757 | U.VAL = RHS.U.VAL; | |||
758 | BitWidth = RHS.BitWidth; | |||
759 | return clearUnusedBits(); | |||
760 | } | |||
761 | ||||
762 | AssignSlowCase(RHS); | |||
763 | return *this; | |||
764 | } | |||
765 | ||||
766 | /// Move assignment operator. | |||
767 | APInt &operator=(APInt &&that) { | |||
768 | #ifdef EXPENSIVE_CHECKS | |||
769 | // Some std::shuffle implementations still do self-assignment. | |||
770 | if (this == &that) | |||
771 | return *this; | |||
772 | #endif | |||
773 | assert(this != &that && "Self-move not supported")((this != &that && "Self-move not supported") ? static_cast <void> (0) : __assert_fail ("this != &that && \"Self-move not supported\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 773, __PRETTY_FUNCTION__)); | |||
774 | if (!isSingleWord()) | |||
775 | delete[] U.pVal; | |||
776 | ||||
777 | // Use memcpy so that type based alias analysis sees both VAL and pVal | |||
778 | // as modified. | |||
779 | memcpy(&U, &that.U, sizeof(U)); | |||
780 | ||||
781 | BitWidth = that.BitWidth; | |||
782 | that.BitWidth = 0; | |||
783 | ||||
784 | return *this; | |||
785 | } | |||
786 | ||||
787 | /// Assignment operator. | |||
788 | /// | |||
789 | /// The RHS value is assigned to *this. If the significant bits in RHS exceed | |||
790 | /// the bit width, the excess bits are truncated. If the bit width is larger | |||
791 | /// than 64, the value is zero filled in the unspecified high order bits. | |||
792 | /// | |||
793 | /// \returns *this after assignment of RHS value. | |||
794 | APInt &operator=(uint64_t RHS) { | |||
795 | if (isSingleWord()) { | |||
796 | U.VAL = RHS; | |||
797 | return clearUnusedBits(); | |||
798 | } | |||
799 | U.pVal[0] = RHS; | |||
800 | memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
801 | return *this; | |||
802 | } | |||
803 | ||||
804 | /// Bitwise AND assignment operator. | |||
805 | /// | |||
806 | /// Performs a bitwise AND operation on this APInt and RHS. The result is | |||
807 | /// assigned to *this. | |||
808 | /// | |||
809 | /// \returns *this after ANDing with RHS. | |||
810 | APInt &operator&=(const APInt &RHS) { | |||
811 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 811, __PRETTY_FUNCTION__)); | |||
812 | if (isSingleWord()) | |||
813 | U.VAL &= RHS.U.VAL; | |||
814 | else | |||
815 | AndAssignSlowCase(RHS); | |||
816 | return *this; | |||
817 | } | |||
818 | ||||
819 | /// Bitwise AND assignment operator. | |||
820 | /// | |||
821 | /// Performs a bitwise AND 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 | return *this; | |||
828 | } | |||
829 | U.pVal[0] &= RHS; | |||
830 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
831 | return *this; | |||
832 | } | |||
833 | ||||
834 | /// Bitwise OR assignment operator. | |||
835 | /// | |||
836 | /// Performs a bitwise OR operation on this APInt and RHS. The result is | |||
837 | /// assigned *this; | |||
838 | /// | |||
839 | /// \returns *this after ORing with RHS. | |||
840 | APInt &operator|=(const APInt &RHS) { | |||
841 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 841, __PRETTY_FUNCTION__)); | |||
842 | if (isSingleWord()) | |||
843 | U.VAL |= RHS.U.VAL; | |||
844 | else | |||
845 | OrAssignSlowCase(RHS); | |||
846 | return *this; | |||
847 | } | |||
848 | ||||
849 | /// Bitwise OR assignment operator. | |||
850 | /// | |||
851 | /// Performs a bitwise OR 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 | return clearUnusedBits(); | |||
858 | } | |||
859 | U.pVal[0] |= RHS; | |||
860 | return *this; | |||
861 | } | |||
862 | ||||
863 | /// Bitwise XOR assignment operator. | |||
864 | /// | |||
865 | /// Performs a bitwise XOR operation on this APInt and RHS. The result is | |||
866 | /// assigned to *this. | |||
867 | /// | |||
868 | /// \returns *this after XORing with RHS. | |||
869 | APInt &operator^=(const APInt &RHS) { | |||
870 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 870, __PRETTY_FUNCTION__)); | |||
871 | if (isSingleWord()) | |||
872 | U.VAL ^= RHS.U.VAL; | |||
873 | else | |||
874 | XorAssignSlowCase(RHS); | |||
875 | return *this; | |||
876 | } | |||
877 | ||||
878 | /// Bitwise XOR assignment operator. | |||
879 | /// | |||
880 | /// Performs a bitwise XOR operation on this APInt and RHS. RHS is | |||
881 | /// logically zero-extended or truncated to match the bit-width of | |||
882 | /// the LHS. | |||
883 | APInt &operator^=(uint64_t RHS) { | |||
884 | if (isSingleWord()) { | |||
885 | U.VAL ^= RHS; | |||
886 | return clearUnusedBits(); | |||
887 | } | |||
888 | U.pVal[0] ^= RHS; | |||
889 | return *this; | |||
890 | } | |||
891 | ||||
892 | /// Multiplication assignment operator. | |||
893 | /// | |||
894 | /// Multiplies this APInt by RHS and assigns the result to *this. | |||
895 | /// | |||
896 | /// \returns *this | |||
897 | APInt &operator*=(const APInt &RHS); | |||
898 | APInt &operator*=(uint64_t RHS); | |||
899 | ||||
900 | /// Addition assignment operator. | |||
901 | /// | |||
902 | /// Adds RHS to *this and assigns the result to *this. | |||
903 | /// | |||
904 | /// \returns *this | |||
905 | APInt &operator+=(const APInt &RHS); | |||
906 | APInt &operator+=(uint64_t RHS); | |||
907 | ||||
908 | /// Subtraction assignment operator. | |||
909 | /// | |||
910 | /// Subtracts RHS from *this and assigns the result to *this. | |||
911 | /// | |||
912 | /// \returns *this | |||
913 | APInt &operator-=(const APInt &RHS); | |||
914 | APInt &operator-=(uint64_t RHS); | |||
915 | ||||
916 | /// Left-shift assignment function. | |||
917 | /// | |||
918 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
919 | /// | |||
920 | /// \returns *this after shifting left by ShiftAmt | |||
921 | APInt &operator<<=(unsigned ShiftAmt) { | |||
922 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ? static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 922, __PRETTY_FUNCTION__)); | |||
923 | if (isSingleWord()) { | |||
924 | if (ShiftAmt == BitWidth) | |||
925 | U.VAL = 0; | |||
926 | else | |||
927 | U.VAL <<= ShiftAmt; | |||
| ||||
928 | return clearUnusedBits(); | |||
929 | } | |||
930 | shlSlowCase(ShiftAmt); | |||
931 | return *this; | |||
932 | } | |||
933 | ||||
934 | /// Left-shift assignment function. | |||
935 | /// | |||
936 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
937 | /// | |||
938 | /// \returns *this after shifting left by ShiftAmt | |||
939 | APInt &operator<<=(const APInt &ShiftAmt); | |||
940 | ||||
941 | /// @} | |||
942 | /// \name Binary Operators | |||
943 | /// @{ | |||
944 | ||||
945 | /// Multiplication operator. | |||
946 | /// | |||
947 | /// Multiplies this APInt by RHS and returns the result. | |||
948 | APInt operator*(const APInt &RHS) const; | |||
949 | ||||
950 | /// Left logical shift operator. | |||
951 | /// | |||
952 | /// Shifts this APInt left by \p Bits and returns the result. | |||
953 | APInt operator<<(unsigned Bits) const { return shl(Bits); } | |||
954 | ||||
955 | /// Left logical shift operator. | |||
956 | /// | |||
957 | /// Shifts this APInt left by \p Bits and returns the result. | |||
958 | APInt operator<<(const APInt &Bits) const { return shl(Bits); } | |||
959 | ||||
960 | /// Arithmetic right-shift function. | |||
961 | /// | |||
962 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
963 | APInt ashr(unsigned ShiftAmt) const { | |||
964 | APInt R(*this); | |||
965 | R.ashrInPlace(ShiftAmt); | |||
966 | return R; | |||
967 | } | |||
968 | ||||
969 | /// Arithmetic right-shift this APInt by ShiftAmt in place. | |||
970 | void ashrInPlace(unsigned ShiftAmt) { | |||
971 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ? static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 971, __PRETTY_FUNCTION__)); | |||
972 | if (isSingleWord()) { | |||
973 | int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); | |||
974 | if (ShiftAmt == BitWidth) | |||
975 | U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit. | |||
976 | else | |||
977 | U.VAL = SExtVAL >> ShiftAmt; | |||
978 | clearUnusedBits(); | |||
979 | return; | |||
980 | } | |||
981 | ashrSlowCase(ShiftAmt); | |||
982 | } | |||
983 | ||||
984 | /// Logical right-shift function. | |||
985 | /// | |||
986 | /// Logical right-shift this APInt by shiftAmt. | |||
987 | APInt lshr(unsigned shiftAmt) const { | |||
988 | APInt R(*this); | |||
989 | R.lshrInPlace(shiftAmt); | |||
990 | return R; | |||
991 | } | |||
992 | ||||
993 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
994 | void lshrInPlace(unsigned ShiftAmt) { | |||
995 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ? static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 995, __PRETTY_FUNCTION__)); | |||
996 | if (isSingleWord()) { | |||
997 | if (ShiftAmt == BitWidth) | |||
998 | U.VAL = 0; | |||
999 | else | |||
1000 | U.VAL >>= ShiftAmt; | |||
1001 | return; | |||
1002 | } | |||
1003 | lshrSlowCase(ShiftAmt); | |||
1004 | } | |||
1005 | ||||
1006 | /// Left-shift function. | |||
1007 | /// | |||
1008 | /// Left-shift this APInt by shiftAmt. | |||
1009 | APInt shl(unsigned shiftAmt) const { | |||
1010 | APInt R(*this); | |||
1011 | R <<= shiftAmt; | |||
1012 | return R; | |||
1013 | } | |||
1014 | ||||
1015 | /// Rotate left by rotateAmt. | |||
1016 | APInt rotl(unsigned rotateAmt) const; | |||
1017 | ||||
1018 | /// Rotate right by rotateAmt. | |||
1019 | APInt rotr(unsigned rotateAmt) const; | |||
1020 | ||||
1021 | /// Arithmetic right-shift function. | |||
1022 | /// | |||
1023 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
1024 | APInt ashr(const APInt &ShiftAmt) const { | |||
1025 | APInt R(*this); | |||
1026 | R.ashrInPlace(ShiftAmt); | |||
1027 | return R; | |||
1028 | } | |||
1029 | ||||
1030 | /// Arithmetic right-shift this APInt by shiftAmt in place. | |||
1031 | void ashrInPlace(const APInt &shiftAmt); | |||
1032 | ||||
1033 | /// Logical right-shift function. | |||
1034 | /// | |||
1035 | /// Logical right-shift this APInt by shiftAmt. | |||
1036 | APInt lshr(const APInt &ShiftAmt) const { | |||
1037 | APInt R(*this); | |||
1038 | R.lshrInPlace(ShiftAmt); | |||
1039 | return R; | |||
1040 | } | |||
1041 | ||||
1042 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
1043 | void lshrInPlace(const APInt &ShiftAmt); | |||
1044 | ||||
1045 | /// Left-shift function. | |||
1046 | /// | |||
1047 | /// Left-shift this APInt by shiftAmt. | |||
1048 | APInt shl(const APInt &ShiftAmt) const { | |||
1049 | APInt R(*this); | |||
1050 | R <<= ShiftAmt; | |||
1051 | return R; | |||
1052 | } | |||
1053 | ||||
1054 | /// Rotate left by rotateAmt. | |||
1055 | APInt rotl(const APInt &rotateAmt) const; | |||
1056 | ||||
1057 | /// Rotate right by rotateAmt. | |||
1058 | APInt rotr(const APInt &rotateAmt) const; | |||
1059 | ||||
1060 | /// Unsigned division operation. | |||
1061 | /// | |||
1062 | /// Perform an unsigned divide operation on this APInt by RHS. Both this and | |||
1063 | /// RHS are treated as unsigned quantities for purposes of this division. | |||
1064 | /// | |||
1065 | /// \returns a new APInt value containing the division result, rounded towards | |||
1066 | /// zero. | |||
1067 | APInt udiv(const APInt &RHS) const; | |||
1068 | APInt udiv(uint64_t RHS) const; | |||
1069 | ||||
1070 | /// Signed division function for APInt. | |||
1071 | /// | |||
1072 | /// Signed divide this APInt by APInt RHS. | |||
1073 | /// | |||
1074 | /// The result is rounded towards zero. | |||
1075 | APInt sdiv(const APInt &RHS) const; | |||
1076 | APInt sdiv(int64_t RHS) const; | |||
1077 | ||||
1078 | /// Unsigned remainder operation. | |||
1079 | /// | |||
1080 | /// Perform an unsigned remainder operation on this APInt with RHS being the | |||
1081 | /// divisor. Both this and RHS are treated as unsigned quantities for purposes | |||
1082 | /// of this operation. Note that this is a true remainder operation and not a | |||
1083 | /// modulo operation because the sign follows the sign of the dividend which | |||
1084 | /// is *this. | |||
1085 | /// | |||
1086 | /// \returns a new APInt value containing the remainder result | |||
1087 | APInt urem(const APInt &RHS) const; | |||
1088 | uint64_t urem(uint64_t RHS) const; | |||
1089 | ||||
1090 | /// Function for signed remainder operation. | |||
1091 | /// | |||
1092 | /// Signed remainder operation on APInt. | |||
1093 | APInt srem(const APInt &RHS) const; | |||
1094 | int64_t srem(int64_t RHS) const; | |||
1095 | ||||
1096 | /// Dual division/remainder interface. | |||
1097 | /// | |||
1098 | /// Sometimes it is convenient to divide two APInt values and obtain both the | |||
1099 | /// quotient and remainder. This function does both operations in the same | |||
1100 | /// computation making it a little more efficient. The pair of input arguments | |||
1101 | /// may overlap with the pair of output arguments. It is safe to call | |||
1102 | /// udivrem(X, Y, X, Y), for example. | |||
1103 | static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
1104 | APInt &Remainder); | |||
1105 | static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, | |||
1106 | uint64_t &Remainder); | |||
1107 | ||||
1108 | static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
1109 | APInt &Remainder); | |||
1110 | static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, | |||
1111 | int64_t &Remainder); | |||
1112 | ||||
1113 | // Operations that return overflow indicators. | |||
1114 | APInt sadd_ov(const APInt &RHS, bool &Overflow) const; | |||
1115 | APInt uadd_ov(const APInt &RHS, bool &Overflow) const; | |||
1116 | APInt ssub_ov(const APInt &RHS, bool &Overflow) const; | |||
1117 | APInt usub_ov(const APInt &RHS, bool &Overflow) const; | |||
1118 | APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; | |||
1119 | APInt smul_ov(const APInt &RHS, bool &Overflow) const; | |||
1120 | APInt umul_ov(const APInt &RHS, bool &Overflow) const; | |||
1121 | APInt sshl_ov(const APInt &Amt, bool &Overflow) const; | |||
1122 | APInt ushl_ov(const APInt &Amt, bool &Overflow) const; | |||
1123 | ||||
1124 | // Operations that saturate | |||
1125 | APInt sadd_sat(const APInt &RHS) const; | |||
1126 | APInt uadd_sat(const APInt &RHS) const; | |||
1127 | APInt ssub_sat(const APInt &RHS) const; | |||
1128 | APInt usub_sat(const APInt &RHS) const; | |||
1129 | APInt smul_sat(const APInt &RHS) const; | |||
1130 | APInt umul_sat(const APInt &RHS) const; | |||
1131 | APInt sshl_sat(const APInt &RHS) const; | |||
1132 | APInt ushl_sat(const APInt &RHS) const; | |||
1133 | ||||
1134 | /// Array-indexing support. | |||
1135 | /// | |||
1136 | /// \returns the bit value at bitPosition | |||
1137 | bool operator[](unsigned bitPosition) const { | |||
1138 | assert(bitPosition < getBitWidth() && "Bit position out of bounds!")((bitPosition < getBitWidth() && "Bit position out of bounds!" ) ? static_cast<void> (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1138, __PRETTY_FUNCTION__)); | |||
1139 | return (maskBit(bitPosition) & getWord(bitPosition)) != 0; | |||
1140 | } | |||
1141 | ||||
1142 | /// @} | |||
1143 | /// \name Comparison Operators | |||
1144 | /// @{ | |||
1145 | ||||
1146 | /// Equality operator. | |||
1147 | /// | |||
1148 | /// Compares this APInt with RHS for the validity of the equality | |||
1149 | /// relationship. | |||
1150 | bool operator==(const APInt &RHS) const { | |||
1151 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")((BitWidth == RHS.BitWidth && "Comparison requires equal bit widths" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1151, __PRETTY_FUNCTION__)); | |||
1152 | if (isSingleWord()) | |||
1153 | return U.VAL == RHS.U.VAL; | |||
1154 | return EqualSlowCase(RHS); | |||
1155 | } | |||
1156 | ||||
1157 | /// Equality operator. | |||
1158 | /// | |||
1159 | /// Compares this APInt with a uint64_t for the validity of the equality | |||
1160 | /// relationship. | |||
1161 | /// | |||
1162 | /// \returns true if *this == Val | |||
1163 | bool operator==(uint64_t Val) const { | |||
1164 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; | |||
1165 | } | |||
1166 | ||||
1167 | /// Equality comparison. | |||
1168 | /// | |||
1169 | /// Compares this APInt with RHS for the validity of the equality | |||
1170 | /// relationship. | |||
1171 | /// | |||
1172 | /// \returns true if *this == Val | |||
1173 | bool eq(const APInt &RHS) const { return (*this) == RHS; } | |||
1174 | ||||
1175 | /// Inequality operator. | |||
1176 | /// | |||
1177 | /// Compares this APInt with RHS for the validity of the inequality | |||
1178 | /// relationship. | |||
1179 | /// | |||
1180 | /// \returns true if *this != Val | |||
1181 | bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } | |||
1182 | ||||
1183 | /// Inequality operator. | |||
1184 | /// | |||
1185 | /// Compares this APInt with a uint64_t for the validity of the inequality | |||
1186 | /// relationship. | |||
1187 | /// | |||
1188 | /// \returns true if *this != Val | |||
1189 | bool operator!=(uint64_t Val) const { return !((*this) == Val); } | |||
1190 | ||||
1191 | /// Inequality comparison | |||
1192 | /// | |||
1193 | /// Compares this APInt with RHS for the validity of the inequality | |||
1194 | /// relationship. | |||
1195 | /// | |||
1196 | /// \returns true if *this != Val | |||
1197 | bool ne(const APInt &RHS) const { return !((*this) == RHS); } | |||
1198 | ||||
1199 | /// Unsigned less than comparison | |||
1200 | /// | |||
1201 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1202 | /// the validity of the less-than relationship. | |||
1203 | /// | |||
1204 | /// \returns true if *this < RHS when both are considered unsigned. | |||
1205 | bool ult(const APInt &RHS) const { return compare(RHS) < 0; } | |||
1206 | ||||
1207 | /// Unsigned less than comparison | |||
1208 | /// | |||
1209 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1210 | /// the validity of the less-than relationship. | |||
1211 | /// | |||
1212 | /// \returns true if *this < RHS when considered unsigned. | |||
1213 | bool ult(uint64_t RHS) const { | |||
1214 | // Only need to check active bits if not a single word. | |||
1215 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; | |||
1216 | } | |||
1217 | ||||
1218 | /// Signed less than comparison | |||
1219 | /// | |||
1220 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1221 | /// validity of the less-than relationship. | |||
1222 | /// | |||
1223 | /// \returns true if *this < RHS when both are considered signed. | |||
1224 | bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } | |||
1225 | ||||
1226 | /// Signed less than comparison | |||
1227 | /// | |||
1228 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1229 | /// the validity of the less-than relationship. | |||
1230 | /// | |||
1231 | /// \returns true if *this < RHS when considered signed. | |||
1232 | bool slt(int64_t RHS) const { | |||
1233 | return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative() | |||
1234 | : getSExtValue() < RHS; | |||
1235 | } | |||
1236 | ||||
1237 | /// Unsigned less or equal comparison | |||
1238 | /// | |||
1239 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1240 | /// validity of the less-or-equal relationship. | |||
1241 | /// | |||
1242 | /// \returns true if *this <= RHS when both are considered unsigned. | |||
1243 | bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } | |||
1244 | ||||
1245 | /// Unsigned less or equal comparison | |||
1246 | /// | |||
1247 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1248 | /// the validity of the less-or-equal relationship. | |||
1249 | /// | |||
1250 | /// \returns true if *this <= RHS when considered unsigned. | |||
1251 | bool ule(uint64_t RHS) const { return !ugt(RHS); } | |||
1252 | ||||
1253 | /// Signed less or equal comparison | |||
1254 | /// | |||
1255 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1256 | /// validity of the less-or-equal relationship. | |||
1257 | /// | |||
1258 | /// \returns true if *this <= RHS when both are considered signed. | |||
1259 | bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } | |||
1260 | ||||
1261 | /// Signed less or equal comparison | |||
1262 | /// | |||
1263 | /// Regards both *this as a signed quantity and compares it with RHS for the | |||
1264 | /// validity of the less-or-equal relationship. | |||
1265 | /// | |||
1266 | /// \returns true if *this <= RHS when considered signed. | |||
1267 | bool sle(uint64_t RHS) const { return !sgt(RHS); } | |||
1268 | ||||
1269 | /// Unsigned greater than comparison | |||
1270 | /// | |||
1271 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1272 | /// the validity of the greater-than relationship. | |||
1273 | /// | |||
1274 | /// \returns true if *this > RHS when both are considered unsigned. | |||
1275 | bool ugt(const APInt &RHS) const { return !ule(RHS); } | |||
1276 | ||||
1277 | /// Unsigned greater than comparison | |||
1278 | /// | |||
1279 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1280 | /// the validity of the greater-than relationship. | |||
1281 | /// | |||
1282 | /// \returns true if *this > RHS when considered unsigned. | |||
1283 | bool ugt(uint64_t RHS) const { | |||
1284 | // Only need to check active bits if not a single word. | |||
1285 | return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; | |||
1286 | } | |||
1287 | ||||
1288 | /// Signed greater than comparison | |||
1289 | /// | |||
1290 | /// Regards both *this and RHS as signed quantities and compares them for the | |||
1291 | /// validity of the greater-than relationship. | |||
1292 | /// | |||
1293 | /// \returns true if *this > RHS when both are considered signed. | |||
1294 | bool sgt(const APInt &RHS) const { return !sle(RHS); } | |||
1295 | ||||
1296 | /// Signed greater than comparison | |||
1297 | /// | |||
1298 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1299 | /// the validity of the greater-than relationship. | |||
1300 | /// | |||
1301 | /// \returns true if *this > RHS when considered signed. | |||
1302 | bool sgt(int64_t RHS) const { | |||
1303 | return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative() | |||
1304 | : getSExtValue() > RHS; | |||
1305 | } | |||
1306 | ||||
1307 | /// Unsigned greater or equal comparison | |||
1308 | /// | |||
1309 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
1310 | /// validity of the greater-or-equal relationship. | |||
1311 | /// | |||
1312 | /// \returns true if *this >= RHS when both are considered unsigned. | |||
1313 | bool uge(const APInt &RHS) const { return !ult(RHS); } | |||
1314 | ||||
1315 | /// Unsigned greater or equal comparison | |||
1316 | /// | |||
1317 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
1318 | /// the validity of the greater-or-equal relationship. | |||
1319 | /// | |||
1320 | /// \returns true if *this >= RHS when considered unsigned. | |||
1321 | bool uge(uint64_t RHS) const { return !ult(RHS); } | |||
1322 | ||||
1323 | /// Signed greater or equal comparison | |||
1324 | /// | |||
1325 | /// Regards both *this and RHS as signed quantities and compares them for | |||
1326 | /// validity of the greater-or-equal relationship. | |||
1327 | /// | |||
1328 | /// \returns true if *this >= RHS when both are considered signed. | |||
1329 | bool sge(const APInt &RHS) const { return !slt(RHS); } | |||
1330 | ||||
1331 | /// Signed greater or equal comparison | |||
1332 | /// | |||
1333 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
1334 | /// the validity of the greater-or-equal relationship. | |||
1335 | /// | |||
1336 | /// \returns true if *this >= RHS when considered signed. | |||
1337 | bool sge(int64_t RHS) const { return !slt(RHS); } | |||
1338 | ||||
1339 | /// This operation tests if there are any pairs of corresponding bits | |||
1340 | /// between this APInt and RHS that are both set. | |||
1341 | bool intersects(const APInt &RHS) const { | |||
1342 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1342, __PRETTY_FUNCTION__)); | |||
1343 | if (isSingleWord()) | |||
1344 | return (U.VAL & RHS.U.VAL) != 0; | |||
1345 | return intersectsSlowCase(RHS); | |||
1346 | } | |||
1347 | ||||
1348 | /// This operation checks that all bits set in this APInt are also set in RHS. | |||
1349 | bool isSubsetOf(const APInt &RHS) const { | |||
1350 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same" ) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1350, __PRETTY_FUNCTION__)); | |||
1351 | if (isSingleWord()) | |||
1352 | return (U.VAL & ~RHS.U.VAL) == 0; | |||
1353 | return isSubsetOfSlowCase(RHS); | |||
1354 | } | |||
1355 | ||||
1356 | /// @} | |||
1357 | /// \name Resizing Operators | |||
1358 | /// @{ | |||
1359 | ||||
1360 | /// Truncate to new width. | |||
1361 | /// | |||
1362 | /// Truncate the APInt to a specified width. It is an error to specify a width | |||
1363 | /// that is greater than or equal to the current width. | |||
1364 | APInt trunc(unsigned width) const; | |||
1365 | ||||
1366 | /// Truncate to new width with unsigned saturation. | |||
1367 | /// | |||
1368 | /// If the APInt, treated as unsigned integer, can be losslessly truncated to | |||
1369 | /// the new bitwidth, then return truncated APInt. Else, return max value. | |||
1370 | APInt truncUSat(unsigned width) const; | |||
1371 | ||||
1372 | /// Truncate to new width with signed saturation. | |||
1373 | /// | |||
1374 | /// If this APInt, treated as signed integer, can be losslessly truncated to | |||
1375 | /// the new bitwidth, then return truncated APInt. Else, return either | |||
1376 | /// signed min value if the APInt was negative, or signed max value. | |||
1377 | APInt truncSSat(unsigned width) const; | |||
1378 | ||||
1379 | /// Sign extend to a new width. | |||
1380 | /// | |||
1381 | /// This operation sign extends the APInt to a new width. If the high order | |||
1382 | /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. | |||
1383 | /// It is an error to specify a width that is less than or equal to the | |||
1384 | /// current width. | |||
1385 | APInt sext(unsigned width) const; | |||
1386 | ||||
1387 | /// Zero extend to a new width. | |||
1388 | /// | |||
1389 | /// This operation zero extends the APInt to a new width. The high order bits | |||
1390 | /// are filled with 0 bits. It is an error to specify a width that is less | |||
1391 | /// than or equal to the current width. | |||
1392 | APInt zext(unsigned width) const; | |||
1393 | ||||
1394 | /// Sign extend or truncate to width | |||
1395 | /// | |||
1396 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
1397 | /// extended, truncated, or left alone to make it that width. | |||
1398 | APInt sextOrTrunc(unsigned width) const; | |||
1399 | ||||
1400 | /// Zero extend or truncate to width | |||
1401 | /// | |||
1402 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
1403 | /// extended, truncated, or left alone to make it that width. | |||
1404 | APInt zextOrTrunc(unsigned width) const; | |||
1405 | ||||
1406 | /// Truncate to width | |||
1407 | /// | |||
1408 | /// Make this APInt have the bit width given by \p width. The value is | |||
1409 | /// truncated or left alone to make it that width. | |||
1410 | APInt truncOrSelf(unsigned width) const; | |||
1411 | ||||
1412 | /// Sign extend or truncate to width | |||
1413 | /// | |||
1414 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
1415 | /// extended, or left alone to make it that width. | |||
1416 | APInt sextOrSelf(unsigned width) const; | |||
1417 | ||||
1418 | /// Zero extend or truncate to width | |||
1419 | /// | |||
1420 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
1421 | /// extended, or left alone to make it that width. | |||
1422 | APInt zextOrSelf(unsigned width) const; | |||
1423 | ||||
1424 | /// @} | |||
1425 | /// \name Bit Manipulation Operators | |||
1426 | /// @{ | |||
1427 | ||||
1428 | /// Set every bit to 1. | |||
1429 | void setAllBits() { | |||
1430 | if (isSingleWord()) | |||
1431 | U.VAL = WORDTYPE_MAX; | |||
1432 | else | |||
1433 | // Set all the bits in all the words. | |||
1434 | memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); | |||
1435 | // Clear the unused ones | |||
1436 | clearUnusedBits(); | |||
1437 | } | |||
1438 | ||||
1439 | /// Set a given bit to 1. | |||
1440 | /// | |||
1441 | /// Set the given bit to 1 whose position is given as "bitPosition". | |||
1442 | void setBit(unsigned BitPosition) { | |||
1443 | assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range" ) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1443, __PRETTY_FUNCTION__)); | |||
1444 | WordType Mask = maskBit(BitPosition); | |||
1445 | if (isSingleWord()) | |||
1446 | U.VAL |= Mask; | |||
1447 | else | |||
1448 | U.pVal[whichWord(BitPosition)] |= Mask; | |||
1449 | } | |||
1450 | ||||
1451 | /// Set the sign bit to 1. | |||
1452 | void setSignBit() { | |||
1453 | setBit(BitWidth - 1); | |||
1454 | } | |||
1455 | ||||
1456 | /// Set a given bit to a given value. | |||
1457 | void setBitVal(unsigned BitPosition, bool BitValue) { | |||
1458 | if (BitValue) | |||
1459 | setBit(BitPosition); | |||
1460 | else | |||
1461 | clearBit(BitPosition); | |||
1462 | } | |||
1463 | ||||
1464 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. | |||
1465 | /// This function handles "wrap" case when \p loBit >= \p hiBit, and calls | |||
1466 | /// setBits when \p loBit < \p hiBit. | |||
1467 | /// For \p loBit == \p hiBit wrap case, set every bit to 1. | |||
1468 | void setBitsWithWrap(unsigned loBit, unsigned hiBit) { | |||
1469 | assert(hiBit <= BitWidth && "hiBit out of range")((hiBit <= BitWidth && "hiBit out of range") ? static_cast <void> (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1469, __PRETTY_FUNCTION__)); | |||
1470 | assert(loBit <= BitWidth && "loBit out of range")((loBit <= BitWidth && "loBit out of range") ? static_cast <void> (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1470, __PRETTY_FUNCTION__)); | |||
1471 | if (loBit < hiBit) { | |||
1472 | setBits(loBit, hiBit); | |||
1473 | return; | |||
1474 | } | |||
1475 | setLowBits(hiBit); | |||
1476 | setHighBits(BitWidth - loBit); | |||
1477 | } | |||
1478 | ||||
1479 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. | |||
1480 | /// This function handles case when \p loBit <= \p hiBit. | |||
1481 | void setBits(unsigned loBit, unsigned hiBit) { | |||
1482 | assert(hiBit <= BitWidth && "hiBit out of range")((hiBit <= BitWidth && "hiBit out of range") ? static_cast <void> (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1482, __PRETTY_FUNCTION__)); | |||
1483 | assert(loBit <= BitWidth && "loBit out of range")((loBit <= BitWidth && "loBit out of range") ? static_cast <void> (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1483, __PRETTY_FUNCTION__)); | |||
1484 | assert(loBit <= hiBit && "loBit greater than hiBit")((loBit <= hiBit && "loBit greater than hiBit") ? static_cast <void> (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1484, __PRETTY_FUNCTION__)); | |||
1485 | if (loBit == hiBit) | |||
1486 | return; | |||
1487 | if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { | |||
1488 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); | |||
1489 | mask <<= loBit; | |||
1490 | if (isSingleWord()) | |||
1491 | U.VAL |= mask; | |||
1492 | else | |||
1493 | U.pVal[0] |= mask; | |||
1494 | } else { | |||
1495 | setBitsSlowCase(loBit, hiBit); | |||
1496 | } | |||
1497 | } | |||
1498 | ||||
1499 | /// Set the top bits starting from loBit. | |||
1500 | void setBitsFrom(unsigned loBit) { | |||
1501 | return setBits(loBit, BitWidth); | |||
1502 | } | |||
1503 | ||||
1504 | /// Set the bottom loBits bits. | |||
1505 | void setLowBits(unsigned loBits) { | |||
1506 | return setBits(0, loBits); | |||
1507 | } | |||
1508 | ||||
1509 | /// Set the top hiBits bits. | |||
1510 | void setHighBits(unsigned hiBits) { | |||
1511 | return setBits(BitWidth - hiBits, BitWidth); | |||
1512 | } | |||
1513 | ||||
1514 | /// Set every bit to 0. | |||
1515 | void clearAllBits() { | |||
1516 | if (isSingleWord()) | |||
1517 | U.VAL = 0; | |||
1518 | else | |||
1519 | memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); | |||
1520 | } | |||
1521 | ||||
1522 | /// Set a given bit to 0. | |||
1523 | /// | |||
1524 | /// Set the given bit to 0 whose position is given as "bitPosition". | |||
1525 | void clearBit(unsigned BitPosition) { | |||
1526 | assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range" ) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1526, __PRETTY_FUNCTION__)); | |||
1527 | WordType Mask = ~maskBit(BitPosition); | |||
1528 | if (isSingleWord()) | |||
1529 | U.VAL &= Mask; | |||
1530 | else | |||
1531 | U.pVal[whichWord(BitPosition)] &= Mask; | |||
1532 | } | |||
1533 | ||||
1534 | /// Set bottom loBits bits to 0. | |||
1535 | void clearLowBits(unsigned loBits) { | |||
1536 | assert(loBits <= BitWidth && "More bits than bitwidth")((loBits <= BitWidth && "More bits than bitwidth") ? static_cast<void> (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1536, __PRETTY_FUNCTION__)); | |||
1537 | APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits); | |||
1538 | *this &= Keep; | |||
1539 | } | |||
1540 | ||||
1541 | /// Set the sign bit to 0. | |||
1542 | void clearSignBit() { | |||
1543 | clearBit(BitWidth - 1); | |||
1544 | } | |||
1545 | ||||
1546 | /// Toggle every bit to its opposite value. | |||
1547 | void flipAllBits() { | |||
1548 | if (isSingleWord()) { | |||
1549 | U.VAL ^= WORDTYPE_MAX; | |||
1550 | clearUnusedBits(); | |||
1551 | } else { | |||
1552 | flipAllBitsSlowCase(); | |||
1553 | } | |||
1554 | } | |||
1555 | ||||
1556 | /// Toggles a given bit to its opposite value. | |||
1557 | /// | |||
1558 | /// Toggle a given bit to its opposite value whose position is given | |||
1559 | /// as "bitPosition". | |||
1560 | void flipBit(unsigned bitPosition); | |||
1561 | ||||
1562 | /// Negate this APInt in place. | |||
1563 | void negate() { | |||
1564 | flipAllBits(); | |||
1565 | ++(*this); | |||
1566 | } | |||
1567 | ||||
1568 | /// Insert the bits from a smaller APInt starting at bitPosition. | |||
1569 | void insertBits(const APInt &SubBits, unsigned bitPosition); | |||
1570 | void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits); | |||
1571 | ||||
1572 | /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). | |||
1573 | APInt extractBits(unsigned numBits, unsigned bitPosition) const; | |||
1574 | uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const; | |||
1575 | ||||
1576 | /// @} | |||
1577 | /// \name Value Characterization Functions | |||
1578 | /// @{ | |||
1579 | ||||
1580 | /// Return the number of bits in the APInt. | |||
1581 | unsigned getBitWidth() const { return BitWidth; } | |||
1582 | ||||
1583 | /// Get the number of words. | |||
1584 | /// | |||
1585 | /// Here one word's bitwidth equals to that of uint64_t. | |||
1586 | /// | |||
1587 | /// \returns the number of words to hold the integer value of this APInt. | |||
1588 | unsigned getNumWords() const { return getNumWords(BitWidth); } | |||
1589 | ||||
1590 | /// Get the number of words. | |||
1591 | /// | |||
1592 | /// *NOTE* Here one word's bitwidth equals to that of uint64_t. | |||
1593 | /// | |||
1594 | /// \returns the number of words to hold the integer value with a given bit | |||
1595 | /// width. | |||
1596 | static unsigned getNumWords(unsigned BitWidth) { | |||
1597 | return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; | |||
1598 | } | |||
1599 | ||||
1600 | /// Compute the number of active bits in the value | |||
1601 | /// | |||
1602 | /// This function returns the number of active bits which is defined as the | |||
1603 | /// bit width minus the number of leading zeros. This is used in several | |||
1604 | /// computations to see how "wide" the value is. | |||
1605 | unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); } | |||
1606 | ||||
1607 | /// Compute the number of active words in the value of this APInt. | |||
1608 | /// | |||
1609 | /// This is used in conjunction with getActiveData to extract the raw value of | |||
1610 | /// the APInt. | |||
1611 | unsigned getActiveWords() const { | |||
1612 | unsigned numActiveBits = getActiveBits(); | |||
1613 | return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; | |||
1614 | } | |||
1615 | ||||
1616 | /// Get the minimum bit size for this signed APInt | |||
1617 | /// | |||
1618 | /// Computes the minimum bit width for this APInt while considering it to be a | |||
1619 | /// signed (and probably negative) value. If the value is not negative, this | |||
1620 | /// function returns the same value as getActiveBits()+1. Otherwise, it | |||
1621 | /// returns the smallest bit width that will retain the negative value. For | |||
1622 | /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so | |||
1623 | /// for -1, this function will always return 1. | |||
1624 | unsigned getMinSignedBits() const { return BitWidth - getNumSignBits() + 1; } | |||
1625 | ||||
1626 | /// Get zero extended value | |||
1627 | /// | |||
1628 | /// This method attempts to return the value of this APInt as a zero extended | |||
1629 | /// uint64_t. The bitwidth must be <= 64 or the value must fit within a | |||
1630 | /// uint64_t. Otherwise an assertion will result. | |||
1631 | uint64_t getZExtValue() const { | |||
1632 | if (isSingleWord()) | |||
1633 | return U.VAL; | |||
1634 | assert(getActiveBits() <= 64 && "Too many bits for uint64_t")((getActiveBits() <= 64 && "Too many bits for uint64_t" ) ? static_cast<void> (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1634, __PRETTY_FUNCTION__)); | |||
1635 | return U.pVal[0]; | |||
1636 | } | |||
1637 | ||||
1638 | /// Get sign extended value | |||
1639 | /// | |||
1640 | /// This method attempts to return the value of this APInt as a sign extended | |||
1641 | /// int64_t. The bit width must be <= 64 or the value must fit within an | |||
1642 | /// int64_t. Otherwise an assertion will result. | |||
1643 | int64_t getSExtValue() const { | |||
1644 | if (isSingleWord()) | |||
1645 | return SignExtend64(U.VAL, BitWidth); | |||
1646 | assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")((getMinSignedBits() <= 64 && "Too many bits for int64_t" ) ? static_cast<void> (0) : __assert_fail ("getMinSignedBits() <= 64 && \"Too many bits for int64_t\"" , "/build/llvm-toolchain-snapshot-12~++20201205111132+f8afba5f7a2/llvm/include/llvm/ADT/APInt.h" , 1646, __PRETTY_FUNCTION__)); | |||
1647 | return int64_t(U.pVal[0]); | |||
1648 | } | |||
1649 | ||||
1650 | /// Get bits required for string value. | |||
1651 | /// | |||
1652 | /// This method determines how many bits are required to hold the APInt | |||
1653 | /// equivalent of the string given by \p str. | |||
1654 | static unsigned getBitsNeeded(StringRef str, uint8_t radix); | |||
1655 | ||||
1656 | /// The APInt version of the countLeadingZeros functions in | |||
1657 | /// MathExtras.h. | |||
1658 | /// | |||
1659 | /// It counts the number of zeros from the most significant bit to the first | |||
1660 | /// one bit. | |||
1661 | /// | |||
1662 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
1663 | /// zeros from the most significant bit to the first one bits. | |||
1664 | unsigned countLeadingZeros() const { | |||
1665 | if (isSingleWord()) { | |||
1666 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; | |||
1667 | return llvm::countLeadingZeros(U.VAL) - unusedBits; | |||
1668 | } | |||
1669 | return countLeadingZerosSlowCase(); | |||
1670 | } | |||
1671 | ||||
1672 | /// Count the number of leading one bits. | |||
1673 | /// | |||
1674 | /// This function is an APInt version of the countLeadingOnes | |||
1675 | /// functions in MathExtras.h. It counts the number of ones from the most | |||
1676 | /// significant bit to the first zero bit. | |||
1677 | /// | |||
1678 | /// \returns 0 if the high order bit is not set, otherwise returns the number | |||
1679 | /// of 1 bits from the most significant to the least | |||
1680 | unsigned countLeadingOnes() const { | |||
1681 | if (isSingleWord()) | |||
1682 | return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); | |||
1683 | return countLeadingOnesSlowCase(); | |||
1684 | } | |||
1685 | ||||
1686 | /// Computes the number of leading bits of this APInt that are equal to its | |||
1687 | /// sign bit. | |||
1688 | unsigned getNumSignBits() const { | |||
1689 | return isNegative() ? countLeadingOnes() : countLeadingZeros(); | |||
1690 | } | |||
1691 | ||||
1692 | /// Count the number of trailing zero bits. | |||
1693 | /// | |||
1694 | /// This function is an APInt version of the countTrailingZeros | |||
1695 | /// functions in MathExtras.h. It counts the number of zeros from the least | |||
1696 | /// significant bit to the first set bit. | |||
1697 | /// | |||
1698 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
1699 | /// zeros from the least significant bit to the first one bit. | |||
1700 | unsigned countTrailingZeros() const { | |||
1701 | if (isSingleWord()) | |||
1702 | return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth); | |||
1703 | return countTrailingZerosSlowCase(); | |||
1704 | } | |||
1705 | ||||
1706 | /// Count the number of trailing one bits. | |||
1707 | /// | |||
1708 | /// This function is an APInt version of the countTrailingOnes | |||
1709 | /// functions in MathExtras.h. It counts the number of ones from the least | |||
1710 | /// significant bit to the first zero bit. | |||
1711 | /// | |||
1712 | /// \returns BitWidth if the value is all ones, otherwise returns the number | |||
1713 | /// of ones from the least significant bit to the first zero bit. | |||
1714 | unsigned countTrailingOnes() const { | |||
1715 | if (isSingleWord()) | |||
1716 | return llvm::countTrailingOnes(U.VAL); | |||
1717 | return countTrailingOnesSlowCase(); | |||
1718 | } | |||
1719 | ||||
1720 | /// Count the number of bits set. | |||
1721 | /// | |||
1722 | /// This function is an APInt version of the countPopulation functions | |||
1723 | /// in MathExtras.h. It counts the number of 1 bits in the APInt value. | |||
1724 | /// | |||
1725 | /// \returns 0 if the value is zero, otherwise returns the number of set bits. | |||
1726 | unsigned countPopulation() const { | |||
1727 | if (isSingleWord()) | |||
1728 | return llvm::countPopulation(U.VAL); | |||
1729 | return countPopulationSlowCase(); | |||
1730 | } | |||
1731 | ||||
1732 | /// @} | |||
1733 | /// \name Conversion Functions | |||
1734 | /// @{ | |||
1735 | void print(raw_ostream &OS, bool isSigned) const; | |||
1736 | ||||
1737 | /// Converts an APInt to a string and append it to Str. Str is commonly a | |||
1738 | /// SmallString. | |||
1739 | void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, | |||
1740 | bool formatAsCLiteral = false) const; | |||
1741 | ||||
1742 | /// Considers the APInt to be unsigned and converts it into a string in the | |||
1743 | /// radix given. The radix can be 2, 8, 10 16, or 36. | |||
1744 | void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
1745 | toString(Str, Radix, false, false); | |||
1746 | } | |||
1747 | ||||
1748 | /// Considers the APInt to be signed and converts it into a string in the | |||
1749 | /// radix given. The radix can be 2, 8, 10, 16, or 36. | |||
1750 | void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
1751 | toString(Str, Radix, true, false); | |||
1752 | } | |||
1753 | ||||
1754 | /// Return the APInt as a std::string. | |||
1755 | /// | |||
1756 | /// Note that this is an inefficient method. It is better to pass in a | |||
1757 | /// SmallVector/SmallString to the methods above to avoid thrashing the heap | |||
1758 | /// for the string. | |||
1759 | std::string toString(unsigned Radix, bool Signed) const; | |||
1760 | ||||
1761 | /// \returns a byte-swapped representation of this APInt Value. | |||
1762 | APInt byteSwap() const; | |||
1763 | ||||
1764 | /// \returns the value with the bit representation reversed of this APInt | |||
1765 | /// Value. | |||
1766 | APInt reverseBits() const; | |||
1767 | ||||
1768 | /// Converts this APInt to a double value. | |||
1769 | double roundToDouble(bool isSigned) const; | |||
1770 | ||||
1771 | /// Converts this unsigned APInt to a double value. | |||
1772 | double roundToDouble() const { return roundToDouble(false); } | |||
1773 | ||||
1774 | /// Converts this signed APInt to a double value. | |||
1775 | double signedRoundToDouble() const { return roundToDouble(true); } | |||
1776 | ||||
1777 | /// Converts APInt bits to a double | |||
1778 | /// | |||
1779 | /// The conversion does not do a translation from integer to double, it just | |||
1780 | /// re-interprets the bits as a double. Note that it is valid to do this on | |||
1781 | /// any bit width. Exactly 64 bits will be translated. | |||
1782 | double bitsToDouble() const { | |||
1783 | return BitsToDouble(getWord(0)); | |||
1784 | } | |||
1785 | ||||
1786 | /// Converts APInt bits to a float | |||
1787 | /// | |||
1788 | /// The conversion does not do a translation from integer to float, it just | |||
1789 | /// re-interprets the bits as a float. Note that it is valid to do this on | |||
1790 | /// any bit width. Exactly 32 bits will be translated. | |||
1791 | float bitsToFloat() const { | |||
1792 | return BitsToFloat(static_cast<uint32_t>(getWord(0))); | |||
1793 | } | |||
1794 | ||||
1795 | /// Converts a double to APInt bits. | |||
1796 | /// | |||
1797 | /// The conversion does not do a translation from double to integer, it just | |||
1798 | /// re-interprets the bits of the double. | |||
1799 | static APInt doubleToBits(double V) { | |||
1800 | return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V)); | |||
1801 | } | |||
1802 | ||||
1803 | /// Converts a float to APInt bits. | |||
1804 | /// | |||
1805 | /// The conversion does not do a translation from float to integer, it just | |||
1806 | /// re-interprets the bits of the float. | |||
1807 | static APInt floatToBits(float V) { | |||
1808 | return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V)); | |||
1809 | } | |||
1810 | ||||
1811 | /// @} | |||
1812 | /// \name Mathematics Operations | |||
1813 | /// @{ | |||
1814 | ||||
1815 | /// \returns the floor log base 2 of this APInt. | |||
1816 | unsigned logBase2() const { return getActiveBits() - 1; } | |||
1817 | ||||
1818 | /// \returns the ceil log base 2 of this APInt. | |||
1819 | unsigned ceilLogBase2() const { | |||
1820 | APInt temp(*this); | |||
1821 | --temp; | |||
1822 | return temp.getActiveBits(); | |||
1823 | } | |||
1824 | ||||
1825 | /// \returns the nearest log base 2 of this APInt. Ties round up. | |||
1826 | /// | |||
1827 | /// NOTE: When we have a BitWidth of 1, we define: | |||
1828 | /// | |||
1829 | /// log2(0) = UINT32_MAX | |||
1830 | /// log2(1) = 0 | |||
1831 | /// | |||
1832 | /// to get around any mathematical concerns resulting from | |||
1833 | /// referencing 2 in a space where 2 does no exist. | |||
1834 | unsigned nearestLogBase2() const { | |||
1835 | // Special case when we have a bitwidth of 1. If VAL is 1, then we | |||
1836 | // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to | |||
1837 | // UINT32_MAX. | |||
1838 | if (BitWidth == 1) | |||
1839 | return U.VAL - 1; | |||
1840 | ||||
1841 | // Handle the zero case. | |||
1842 | if (isNullValue()) | |||
1843 | return UINT32_MAX(4294967295U); | |||
1844 | ||||
1845 | // The non-zero case is handled by computing: | |||
1846 | // | |||
1847 | // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. | |||
1848 | // | |||
1849 | // where x[i] is referring to the value of the ith bit of x. | |||
1850 | unsigned lg = logBase2(); | |||
1851 | return lg + unsigned((*this)[lg - 1]); | |||
1852 | } | |||
1853 | ||||
1854 | /// \returns the log base 2 of this APInt if its an exact power of two, -1 | |||
1855 | /// otherwise | |||
1856 | int32_t exactLogBase2() const { | |||
1857 | if (!isPowerOf2()) | |||
1858 | return -1; | |||
1859 | return logBase2(); | |||
1860 | } | |||
1861 | ||||
1862 | /// Compute the square root | |||
1863 | APInt sqrt() const; | |||
1864 | ||||
1865 | /// Get the absolute value; | |||
1866 | /// | |||
1867 | /// If *this is < 0 then return -(*this), otherwise *this; | |||
1868 | APInt abs() const { | |||
1869 | if (isNegative()) | |||
1870 | return -(*this); | |||
1871 | return *this; | |||
1872 | } | |||
1873 | ||||
1874 | /// \returns the multiplicative inverse for a given modulo. | |||
1875 | APInt multiplicativeInverse(const APInt &modulo) const; | |||
1876 | ||||
1877 | /// @} | |||
1878 | /// \name Support for division by constant | |||
1879 | /// @{ | |||
1880 | ||||
1881 | /// Calculate the magic number for signed division by a constant. | |||
1882 | struct ms; | |||
1883 | ms magic() const; | |||
1884 | ||||
1885 | /// Calculate the magic number for unsigned division by a constant. | |||
1886 | struct mu; | |||
1887 | mu magicu(unsigned LeadingZeros = 0) const; | |||
1888 | ||||
1889 | /// @} | |||
1890 | /// \name Building-block Operations for APInt and APFloat | |||
1891 | /// @{ | |||
1892 | ||||
1893 | // These building block operations operate on a representation of arbitrary | |||
1894 | // precision, two's-complement, bignum integer values. They should be | |||
1895 | // sufficient to implement APInt and APFloat bignum requirements. Inputs are | |||
1896 | // generally a pointer to the base of an array of integer parts, representing | |||
1897 | // an unsigned bignum, and a count of how many parts there are. | |||
1898 | ||||
1899 | /// Sets the least significant part of a bignum to the input value, and zeroes | |||
1900 | /// out higher parts. | |||
1901 | static void tcSet(WordType *, WordType, unsigned); | |||
1902 | ||||
1903 | /// Assign one bignum to another. | |||
1904 | static void tcAssign(WordType *, const WordType *, unsigned); | |||
1905 | ||||
1906 | /// Returns true if a bignum is zero, false otherwise. | |||
1907 | static bool tcIsZero(const WordType *, unsigned); | |||
1908 | ||||
1909 | /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. | |||
1910 | static int tcExtractBit(const WordType *, unsigned bit); | |||
1911 | ||||
1912 | /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to | |||
1913 | /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least | |||
1914 | /// significant bit of DST. All high bits above srcBITS in DST are | |||
1915 | /// zero-filled. | |||
1916 | static void tcExtract(WordType *, unsigned dstCount, | |||
1917 | const WordType *, unsigned srcBits, | |||
1918 | unsigned srcLSB); | |||
1919 | ||||
1920 | /// Set the given bit of a bignum. Zero-based. | |||
1921 | static void tcSetBit(WordType *, unsigned bit); | |||
1922 | ||||
1923 | /// Clear the given bit of a bignum. Zero-based. | |||
1924 | static void tcClearBit(WordType *, unsigned bit); | |||
1925 | ||||
1926 | /// Returns the bit number of the least or most significant set bit of a | |||
1927 | /// number. If the input number has no bits set -1U is returned. | |||
1928 | static unsigned tcLSB(const WordType *, unsigned n); | |||
1929 | static unsigned tcMSB(const WordType *parts, unsigned n); | |||
1930 | ||||
1931 | /// Negate a bignum in-place. | |||
1932 | static void tcNegate(WordType *, unsigned); | |||
1933 | ||||
1934 | /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
1935 | static WordType tcAdd(WordType *, const WordType *, | |||
1936 | WordType carry, unsigned); | |||
1937 | /// DST += RHS. Returns the carry flag. | |||
1938 | static WordType tcAddPart(WordType *, WordType, unsigned); | |||
1939 | ||||
1940 | /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
1941 | static WordType tcSubtract(WordType *, const WordType *, | |||
1942 | WordType carry, unsigned); | |||
1943 | /// DST -= RHS. Returns the carry flag. | |||
1944 | static WordType tcSubtractPart(WordType *, WordType, unsigned); | |||
1945 | ||||
1946 | /// DST += SRC * MULTIPLIER + PART if add is true | |||
1947 | /// DST = SRC * MULTIPLIER + PART if add is false | |||
1948 | /// | |||
1949 | /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must | |||
1950 | /// start at the same point, i.e. DST == SRC. | |||
1951 | /// | |||
1952 | /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned. | |||
1953 | /// Otherwise DST is filled with the least significant DSTPARTS parts of the | |||
1954 | /// result, and if all of the omitted higher parts were zero return zero, | |||
1955 | /// otherwise overflow occurred and return one. | |||
1956 | static int tcMultiplyPart(WordType *dst, const WordType *src, | |||
1957 | WordType multiplier, WordType carry, | |||
1958 | unsigned srcParts, unsigned dstParts, | |||
1959 | bool add); | |||
1960 | ||||
1961 | /// DST = LHS * RHS, where DST has the same width as the operands and is | |||
1962 | /// filled with the least significant parts of the result. Returns one if | |||
1963 | /// overflow occurred, otherwise zero. DST must be disjoint from both | |||
1964 | /// operands. | |||
1965 | static int tcMultiply(WordType *, const WordType *, const WordType *, | |||
1966 | unsigned); | |||
1967 | ||||
1968 | /// DST = LHS * RHS, where DST has width the sum of the widths of the | |||
1969 | /// operands. No overflow occurs. DST must be disjoint from both operands. | |||
1970 | static void tcFullMultiply(WordType *, const WordType *, | |||
1971 | const WordType *, unsigned, unsigned); | |||
1972 | ||||
1973 | /// If RHS is zero LHS and REMAINDER are left unchanged, return one. | |||
1974 | /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set | |||
1975 | /// REMAINDER to the remainder, return zero. i.e. | |||
1976 | /// | |||
1977 | /// OLD_LHS = RHS * LHS + REMAINDER | |||
1978 | /// | |||
1979 | /// SCRATCH is a bignum of the same size as the operands and result for use by | |||
1980 | /// the routine; its contents need not be initialized and are destroyed. LHS, | |||
1981 | /// REMAINDER and SCRATCH must be distinct. | |||
1982 | static int tcDivide(WordType *lhs, const WordType *rhs, | |||
1983 | WordType *remainder, WordType *scratch, | |||
1984 | unsigned parts); | |||
1985 | ||||
1986 | /// Shift a bignum left Count bits. Shifted in bits are zero. There are no | |||
1987 | /// restrictions on Count. | |||
1988 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); | |||
1989 | ||||
1990 | /// Shift a bignum right Count bits. Shifted in bits are zero. There are no | |||
1991 | /// restrictions on Count. | |||
1992 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); | |||
1993 | ||||
1994 | /// The obvious AND, OR and XOR and complement operations. | |||
1995 | static void tcAnd(WordType *, const WordType *, unsigned); | |||
1996 | static void tcOr(WordType *, const WordType *, unsigned); | |||
1997 | static void tcXor(WordType *, const WordType *, unsigned); | |||
1998 | static void tcComplement(WordType *, unsigned); | |||
1999 | ||||
2000 | /// Comparison (unsigned) of two bignums. | |||
2001 | static int tcCompare(const WordType *, const WordType *, unsigned); | |||
2002 | ||||
2003 | /// Increment a bignum in-place. Return the carry flag. | |||
2004 | static WordType tcIncrement(WordType *dst, unsigned parts) { | |||
2005 | return tcAddPart(dst, 1, parts); | |||
2006 | } | |||
2007 | ||||
2008 | /// Decrement a bignum in-place. Return the borrow flag. | |||
2009 | static WordType tcDecrement(WordType *dst, unsigned parts) { | |||
2010 | return tcSubtractPart(dst, 1, parts); | |||
2011 | } | |||
2012 | ||||
2013 | /// Set the least significant BITS and clear the rest. | |||
2014 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); | |||
2015 | ||||
2016 | /// debug method | |||
2017 | void dump() const; | |||
2018 | ||||
2019 | /// @} | |||
2020 | }; | |||
2021 | ||||
2022 | /// Magic data for optimising signed division by a constant. | |||
2023 | struct APInt::ms { | |||
2024 | APInt m; ///< magic number | |||
2025 | unsigned s; ///< shift amount | |||
2026 | }; | |||
2027 | ||||
2028 | /// Magic data for optimising unsigned division by a constant. | |||
2029 | struct APInt::mu { | |||
2030 | APInt m; ///< magic number | |||
2031 | bool a; ///< add indicator | |||
2032 | unsigned s; ///< shift amount | |||
2033 | }; | |||
2034 | ||||
2035 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } | |||
2036 | ||||
2037 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } | |||
2038 | ||||
2039 | /// Unary bitwise complement operator. | |||
2040 | /// | |||
2041 | /// \returns an APInt that is the bitwise complement of \p v. | |||
2042 | inline APInt operator~(APInt v) { | |||
2043 | v.flipAllBits(); | |||
2044 | return v; | |||
2045 | } | |||
2046 | ||||
2047 | inline APInt operator&(APInt a, const APInt &b) { | |||
2048 | a &= b; | |||
2049 | return a; | |||
2050 | } | |||
2051 | ||||
2052 | inline APInt operator&(const APInt &a, APInt &&b) { | |||
2053 | b &= a; | |||
2054 | return std::move(b); | |||
2055 | } | |||
2056 | ||||
2057 | inline APInt operator&(APInt a, uint64_t RHS) { | |||
2058 | a &= RHS; | |||
2059 | return a; | |||
2060 | } | |||
2061 | ||||
2062 | inline APInt operator&(uint64_t LHS, APInt b) { | |||
2063 | b &= LHS; | |||
2064 | return b; | |||
2065 | } | |||
2066 | ||||
2067 | inline APInt operator|(APInt a, const APInt &b) { | |||
2068 | a |= b; | |||
2069 | return a; | |||
2070 | } | |||
2071 | ||||
2072 | inline APInt operator|(const APInt &a, APInt &&b) { | |||
2073 | b |= a; | |||
2074 | return std::move(b); | |||
2075 | } | |||
2076 | ||||
2077 | inline APInt operator|(APInt a, uint64_t RHS) { | |||
2078 | a |= RHS; | |||
2079 | return a; | |||
2080 | } | |||
2081 | ||||
2082 | inline APInt operator|(uint64_t LHS, APInt b) { | |||
2083 | b |= LHS; | |||
2084 | return b; | |||
2085 | } | |||
2086 | ||||
2087 | inline APInt operator^(APInt a, const APInt &b) { | |||
2088 | a ^= b; | |||
2089 | return a; | |||
2090 | } | |||
2091 | ||||
2092 | inline APInt operator^(const APInt &a, APInt &&b) { | |||
2093 | b ^= a; | |||
2094 | return std::move(b); | |||
2095 | } | |||
2096 | ||||
2097 | inline APInt operator^(APInt a, uint64_t RHS) { | |||
2098 | a ^= RHS; | |||
2099 | return a; | |||
2100 | } | |||
2101 | ||||
2102 | inline APInt operator^(uint64_t LHS, APInt b) { | |||
2103 | b ^= LHS; | |||
2104 | return b; | |||
2105 | } | |||
2106 | ||||
2107 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { | |||
2108 | I.print(OS, true); | |||
2109 | return OS; | |||
2110 | } | |||
2111 | ||||
2112 | inline APInt operator-(APInt v) { | |||
2113 | v.negate(); | |||
2114 | return v; | |||
2115 | } | |||
2116 | ||||
2117 | inline APInt operator+(APInt a, const APInt &b) { | |||
2118 | a += b; | |||
2119 | return a; | |||
2120 | } | |||
2121 | ||||
2122 | inline APInt operator+(const APInt &a, APInt &&b) { | |||
2123 | b += a; | |||
2124 | return std::move(b); | |||
2125 | } | |||
2126 | ||||
2127 | inline APInt operator+(APInt a, uint64_t RHS) { | |||
2128 | a += RHS; | |||
2129 | return a; | |||
2130 | } | |||
2131 | ||||
2132 | inline APInt operator+(uint64_t LHS, APInt b) { | |||
2133 | b += LHS; | |||
2134 | return b; | |||
2135 | } | |||
2136 | ||||
2137 | inline APInt operator-(APInt a, const APInt &b) { | |||
2138 | a -= b; | |||
2139 | return a; | |||
2140 | } | |||
2141 | ||||
2142 | inline APInt operator-(const APInt &a, APInt &&b) { | |||
2143 | b.negate(); | |||
2144 | b += a; | |||
2145 | return std::move(b); | |||
2146 | } | |||
2147 | ||||
2148 | inline APInt operator-(APInt a, uint64_t RHS) { | |||
2149 | a -= RHS; | |||
2150 | return a; | |||
2151 | } | |||
2152 | ||||
2153 | inline APInt operator-(uint64_t LHS, APInt b) { | |||
2154 | b.negate(); | |||
2155 | b += LHS; | |||
2156 | return b; | |||
2157 | } | |||
2158 | ||||
2159 | inline APInt operator*(APInt a, uint64_t RHS) { | |||
2160 | a *= RHS; | |||
2161 | return a; | |||
2162 | } | |||
2163 | ||||
2164 | inline APInt operator*(uint64_t LHS, APInt b) { | |||
2165 | b *= LHS; | |||
2166 | return b; | |||
2167 | } | |||
2168 | ||||
2169 | ||||
2170 | namespace APIntOps { | |||
2171 | ||||
2172 | /// Determine the smaller of two APInts considered to be signed. | |||
2173 | inline const APInt &smin(const APInt &A, const APInt &B) { | |||
2174 | return A.slt(B) ? A : B; | |||
2175 | } | |||
2176 | ||||
2177 | /// Determine the larger of two APInts considered to be signed. | |||
2178 | inline const APInt &smax(const APInt &A, const APInt &B) { | |||
2179 | return A.sgt(B) ? A : B; | |||
2180 | } | |||
2181 | ||||
2182 | /// Determine the smaller of two APInts considered to be signed. | |||
2183 | inline const APInt &umin(const APInt &A, const APInt &B) { | |||
2184 | return A.ult(B) ? A : B; | |||
2185 | } | |||
2186 | ||||
2187 | /// Determine the larger of two APInts considered to be unsigned. | |||
2188 | inline const APInt &umax(const APInt &A, const APInt &B) { | |||
2189 | return A.ugt(B) ? A : B; | |||
2190 | } | |||
2191 | ||||
2192 | /// Compute GCD of two unsigned APInt values. | |||
2193 | /// | |||
2194 | /// This function returns the greatest common divisor of the two APInt values | |||
2195 | /// using Stein's algorithm. | |||
2196 | /// | |||
2197 | /// \returns the greatest common divisor of A and B. | |||
2198 | APInt GreatestCommonDivisor(APInt A, APInt B); | |||
2199 | ||||
2200 | /// Converts the given APInt to a double value. | |||
2201 | /// | |||
2202 | /// Treats the APInt as an unsigned value for conversion purposes. | |||
2203 | inline double RoundAPIntToDouble(const APInt &APIVal) { | |||
2204 | return APIVal.roundToDouble(); | |||
2205 | } | |||
2206 | ||||
2207 | /// Converts the given APInt to a double value. | |||
2208 | /// | |||
2209 | /// Treats the APInt as a signed value for conversion purposes. | |||
2210 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { | |||
2211 | return APIVal.signedRoundToDouble(); | |||
2212 | } | |||
2213 | ||||
2214 | /// Converts the given APInt to a float vlalue. | |||
2215 | inline float RoundAPIntToFloat(const APInt &APIVal) { | |||
2216 | return float(RoundAPIntToDouble(APIVal)); | |||
2217 | } | |||
2218 | ||||
2219 | /// Converts the given APInt to a float value. | |||
2220 | /// | |||
2221 | /// Treats the APInt as a signed value for conversion purposes. | |||
2222 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { | |||
2223 | return float(APIVal.signedRoundToDouble()); | |||
2224 | } | |||
2225 | ||||
2226 | /// Converts the given double value into a APInt. | |||
2227 | /// | |||
2228 | /// This function convert a double value to an APInt value. | |||
2229 | APInt RoundDoubleToAPInt(double Double, unsigned width); | |||
2230 | ||||
2231 | /// Converts a float value into a APInt. | |||
2232 | /// | |||
2233 | /// Converts a float value into an APInt value. | |||
2234 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { | |||
2235 | return RoundDoubleToAPInt(double(Float), width); | |||
2236 | } | |||
2237 | ||||
2238 | /// Return A unsign-divided by B, rounded by the given rounding mode. | |||
2239 | APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); | |||
2240 | ||||
2241 | /// Return A sign-divided by B, rounded by the given rounding mode. | |||
2242 | APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); | |||
2243 | ||||
2244 | /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range | |||
2245 | /// (e.g. 32 for i32). | |||
2246 | /// This function finds the smallest number n, such that | |||
2247 | /// (a) n >= 0 and q(n) = 0, or | |||
2248 | /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all | |||
2249 | /// integers, belong to two different intervals [Rk, Rk+R), | |||
2250 | /// where R = 2^BW, and k is an integer. | |||
2251 | /// The idea here is to find when q(n) "overflows" 2^BW, while at the | |||
2252 | /// same time "allowing" subtraction. In unsigned modulo arithmetic a | |||
2253 | /// subtraction (treated as addition of negated numbers) would always | |||
2254 | /// count as an overflow, but here we want to allow values to decrease | |||
2255 | /// and increase as long as they are within the same interval. | |||
2256 | /// Specifically, adding of two negative numbers should not cause an | |||
2257 | /// overflow (as long as the magnitude does not exceed the bit width). | |||
2258 | /// On the other hand, given a positive number, adding a negative | |||
2259 | /// number to it can give a negative result, which would cause the | |||
2260 | /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is | |||
2261 | /// treated as a special case of an overflow. | |||
2262 | /// | |||
2263 | /// This function returns None if after finding k that minimizes the | |||
2264 | /// positive solution to q(n) = kR, both solutions are contained between | |||
2265 | /// two consecutive integers. | |||
2266 | /// | |||
2267 | /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation | |||
2268 | /// in arithmetic modulo 2^BW, and treating the values as signed) by the | |||
2269 | /// virtue of *signed* overflow. This function will *not* find such an n, | |||
2270 | /// however it may find a value of n satisfying the inequalities due to | |||
2271 | /// an *unsigned* overflow (if the values are treated as unsigned). | |||
2272 | /// To find a solution for a signed overflow, treat it as a problem of | |||
2273 | /// finding an unsigned overflow with a range with of BW-1. | |||
2274 | /// | |||
2275 | /// The returned value may have a different bit width from the input | |||
2276 | /// coefficients. | |||
2277 | Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, | |||
2278 | unsigned RangeWidth); | |||
2279 | ||||
2280 | /// Compare two values, and if they are different, return the position of the | |||
2281 | /// most significant bit that is different in the values. | |||
2282 | Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A, | |||
2283 | const APInt &B); | |||
2284 | ||||
2285 | } // End of APIntOps namespace | |||
2286 | ||||
2287 | // See friend declaration above. This additional declaration is required in | |||
2288 | // order to compile LLVM with IBM xlC compiler. | |||
2289 | hash_code hash_value(const APInt &Arg); | |||
2290 | ||||
2291 | /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst | |||
2292 | /// with the integer held in IntVal. | |||
2293 | void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes); | |||
2294 | ||||
2295 | /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting | |||
2296 | /// from Src into IntVal, which is assumed to be wide enough and to hold zero. | |||
2297 | void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); | |||
2298 | ||||
2299 | } // namespace llvm | |||
2300 | ||||
2301 | #endif |