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/MemoryBuiltins.h" |
26 | #include "llvm/Analysis/MemoryLocation.h" |
27 | #include "llvm/Analysis/TargetLibraryInfo.h" |
28 | #include "llvm/Analysis/ValueTracking.h" |
29 | #include "llvm/IR/Argument.h" |
30 | #include "llvm/IR/Attributes.h" |
31 | #include "llvm/IR/Constant.h" |
32 | #include "llvm/IR/ConstantRange.h" |
33 | #include "llvm/IR/Constants.h" |
34 | #include "llvm/IR/DataLayout.h" |
35 | #include "llvm/IR/DerivedTypes.h" |
36 | #include "llvm/IR/Dominators.h" |
37 | #include "llvm/IR/Function.h" |
38 | #include "llvm/IR/GetElementPtrTypeIterator.h" |
39 | #include "llvm/IR/GlobalAlias.h" |
40 | #include "llvm/IR/GlobalVariable.h" |
41 | #include "llvm/IR/InstrTypes.h" |
42 | #include "llvm/IR/Instruction.h" |
43 | #include "llvm/IR/Instructions.h" |
44 | #include "llvm/IR/IntrinsicInst.h" |
45 | #include "llvm/IR/Intrinsics.h" |
46 | #include "llvm/IR/Operator.h" |
47 | #include "llvm/IR/Type.h" |
48 | #include "llvm/IR/User.h" |
49 | #include "llvm/IR/Value.h" |
50 | #include "llvm/InitializePasses.h" |
51 | #include "llvm/Pass.h" |
52 | #include "llvm/Support/Casting.h" |
53 | #include "llvm/Support/CommandLine.h" |
54 | #include "llvm/Support/Compiler.h" |
55 | #include "llvm/Support/KnownBits.h" |
56 | #include "llvm/Support/SaveAndRestore.h" |
57 | #include <cassert> |
58 | #include <cstdint> |
59 | #include <cstdlib> |
60 | #include <optional> |
61 | #include <utility> |
62 | |
63 | #define DEBUG_TYPE "basicaa" |
64 | |
65 | using namespace llvm; |
66 | |
67 | /// Enable analysis of recursive PHI nodes. |
68 | static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi" , cl::Hidden, |
69 | cl::init(Val: true)); |
70 | |
71 | static cl::opt<bool> EnableSeparateStorageAnalysis("basic-aa-separate-storage" , |
72 | cl::Hidden, cl::init(Val: true)); |
73 | |
74 | /// SearchLimitReached / SearchTimes shows how often the limit of |
75 | /// to decompose GEPs is reached. It will affect the precision |
76 | /// of basic alias analysis. |
77 | STATISTIC(SearchLimitReached, "Number of times the limit to " |
78 | "decompose GEPs is reached" ); |
79 | STATISTIC(SearchTimes, "Number of times a GEP is decomposed" ); |
80 | |
81 | // The max limit of the search depth in DecomposeGEPExpression() and |
82 | // getUnderlyingObject(). |
83 | static const unsigned MaxLookupSearchDepth = 6; |
84 | |
85 | bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA, |
86 | FunctionAnalysisManager::Invalidator &Inv) { |
87 | // We don't care if this analysis itself is preserved, it has no state. But |
88 | // we need to check that the analyses it depends on have been. Note that we |
89 | // may be created without handles to some analyses and in that case don't |
90 | // depend on them. |
91 | if (Inv.invalidate<AssumptionAnalysis>(IR&: Fn, PA) || |
92 | (DT_ && Inv.invalidate<DominatorTreeAnalysis>(IR&: Fn, PA))) |
93 | return true; |
94 | |
95 | // Otherwise this analysis result remains valid. |
96 | return false; |
97 | } |
98 | |
99 | //===----------------------------------------------------------------------===// |
100 | // Useful predicates |
101 | //===----------------------------------------------------------------------===// |
102 | |
103 | /// Returns the size of the object specified by V or UnknownSize if unknown. |
104 | static std::optional<TypeSize> getObjectSize(const Value *V, |
105 | const DataLayout &DL, |
106 | const TargetLibraryInfo &TLI, |
107 | bool NullIsValidLoc, |
108 | bool RoundToAlign = false) { |
109 | uint64_t Size; |
110 | ObjectSizeOpts Opts; |
111 | Opts.RoundToAlign = RoundToAlign; |
112 | Opts.NullIsUnknownSize = NullIsValidLoc; |
113 | if (getObjectSize(Ptr: V, Size, DL, TLI: &TLI, Opts)) |
114 | return TypeSize::getFixed(ExactSize: Size); |
115 | return std::nullopt; |
116 | } |
117 | |
118 | /// Returns true if we can prove that the object specified by V is smaller than |
119 | /// Size. |
120 | static bool isObjectSmallerThan(const Value *V, TypeSize Size, |
121 | const DataLayout &DL, |
122 | const TargetLibraryInfo &TLI, |
123 | bool NullIsValidLoc) { |
124 | // Note that the meanings of the "object" are slightly different in the |
125 | // following contexts: |
126 | // c1: llvm::getObjectSize() |
127 | // c2: llvm.objectsize() intrinsic |
128 | // c3: isObjectSmallerThan() |
129 | // c1 and c2 share the same meaning; however, the meaning of "object" in c3 |
130 | // refers to the "entire object". |
131 | // |
132 | // Consider this example: |
133 | // char *p = (char*)malloc(100) |
134 | // char *q = p+80; |
135 | // |
136 | // In the context of c1 and c2, the "object" pointed by q refers to the |
137 | // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. |
138 | // |
139 | // However, in the context of c3, the "object" refers to the chunk of memory |
140 | // being allocated. So, the "object" has 100 bytes, and q points to the middle |
141 | // the "object". In case q is passed to isObjectSmallerThan() as the 1st |
142 | // parameter, before the llvm::getObjectSize() is called to get the size of |
143 | // entire object, we should: |
144 | // - either rewind the pointer q to the base-address of the object in |
145 | // question (in this case rewind to p), or |
146 | // - just give up. It is up to caller to make sure the pointer is pointing |
147 | // to the base address the object. |
148 | // |
149 | // We go for 2nd option for simplicity. |
150 | if (!isIdentifiedObject(V)) |
151 | return false; |
152 | |
153 | // This function needs to use the aligned object size because we allow |
154 | // reads a bit past the end given sufficient alignment. |
155 | std::optional<TypeSize> ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc, |
156 | /*RoundToAlign*/ true); |
157 | |
158 | return ObjectSize && TypeSize::isKnownLT(LHS: *ObjectSize, RHS: Size); |
159 | } |
160 | |
161 | /// Return the minimal extent from \p V to the end of the underlying object, |
162 | /// assuming the result is used in an aliasing query. E.g., we do use the query |
163 | /// location size and the fact that null pointers cannot alias here. |
164 | static TypeSize getMinimalExtentFrom(const Value &V, |
165 | const LocationSize &LocSize, |
166 | const DataLayout &DL, |
167 | bool NullIsValidLoc) { |
168 | // If we have dereferenceability information we know a lower bound for the |
169 | // extent as accesses for a lower offset would be valid. We need to exclude |
170 | // the "or null" part if null is a valid pointer. We can ignore frees, as an |
171 | // access after free would be undefined behavior. |
172 | bool CanBeNull, CanBeFreed; |
173 | uint64_t DerefBytes = |
174 | V.getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed); |
175 | DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes; |
176 | // If queried with a precise location size, we assume that location size to be |
177 | // accessed, thus valid. |
178 | if (LocSize.isPrecise()) |
179 | DerefBytes = std::max(a: DerefBytes, b: LocSize.getValue().getKnownMinValue()); |
180 | return TypeSize::getFixed(ExactSize: DerefBytes); |
181 | } |
182 | |
183 | /// Returns true if we can prove that the object specified by V has size Size. |
184 | static bool isObjectSize(const Value *V, TypeSize Size, const DataLayout &DL, |
185 | const TargetLibraryInfo &TLI, bool NullIsValidLoc) { |
186 | std::optional<TypeSize> ObjectSize = |
187 | getObjectSize(V, DL, TLI, NullIsValidLoc); |
188 | return ObjectSize && *ObjectSize == Size; |
189 | } |
190 | |
191 | /// Return true if both V1 and V2 are VScale |
192 | static bool areBothVScale(const Value *V1, const Value *V2) { |
193 | return PatternMatch::match(V: V1, P: PatternMatch::m_VScale()) && |
194 | PatternMatch::match(V: V2, P: PatternMatch::m_VScale()); |
195 | } |
196 | |
197 | //===----------------------------------------------------------------------===// |
198 | // CaptureInfo implementations |
199 | //===----------------------------------------------------------------------===// |
200 | |
201 | CaptureInfo::~CaptureInfo() = default; |
202 | |
203 | bool SimpleCaptureInfo::isNotCapturedBefore(const Value *Object, |
204 | const Instruction *I, bool OrAt) { |
205 | return isNonEscapingLocalObject(V: Object, IsCapturedCache: &IsCapturedCache); |
206 | } |
207 | |
208 | static bool isNotInCycle(const Instruction *I, const DominatorTree *DT, |
209 | const LoopInfo *LI) { |
210 | BasicBlock *BB = const_cast<BasicBlock *>(I->getParent()); |
211 | SmallVector<BasicBlock *> Succs(successors(BB)); |
212 | return Succs.empty() || |
213 | !isPotentiallyReachableFromMany(Worklist&: Succs, StopBB: BB, ExclusionSet: nullptr, DT, LI); |
214 | } |
215 | |
216 | bool EarliestEscapeInfo::isNotCapturedBefore(const Value *Object, |
217 | const Instruction *I, bool OrAt) { |
218 | if (!isIdentifiedFunctionLocal(V: Object)) |
219 | return false; |
220 | |
221 | auto Iter = EarliestEscapes.insert(KV: {Object, nullptr}); |
222 | if (Iter.second) { |
223 | Instruction *EarliestCapture = FindEarliestCapture( |
224 | V: Object, F&: *const_cast<Function *>(DT.getRoot()->getParent()), |
225 | /*ReturnCaptures=*/false, /*StoreCaptures=*/true, DT); |
226 | if (EarliestCapture) { |
227 | auto Ins = Inst2Obj.insert(KV: {EarliestCapture, {}}); |
228 | Ins.first->second.push_back(NewVal: Object); |
229 | } |
230 | Iter.first->second = EarliestCapture; |
231 | } |
232 | |
233 | // No capturing instruction. |
234 | if (!Iter.first->second) |
235 | return true; |
236 | |
237 | // No context instruction means any use is capturing. |
238 | if (!I) |
239 | return false; |
240 | |
241 | if (I == Iter.first->second) { |
242 | if (OrAt) |
243 | return false; |
244 | return isNotInCycle(I, DT: &DT, LI); |
245 | } |
246 | |
247 | return !isPotentiallyReachable(From: Iter.first->second, To: I, ExclusionSet: nullptr, DT: &DT, LI); |
248 | } |
249 | |
250 | void EarliestEscapeInfo::removeInstruction(Instruction *I) { |
251 | auto Iter = Inst2Obj.find(Val: I); |
252 | if (Iter != Inst2Obj.end()) { |
253 | for (const Value *Obj : Iter->second) |
254 | EarliestEscapes.erase(Val: Obj); |
255 | Inst2Obj.erase(Val: I); |
256 | } |
257 | } |
258 | |
259 | //===----------------------------------------------------------------------===// |
260 | // GetElementPtr Instruction Decomposition and Analysis |
261 | //===----------------------------------------------------------------------===// |
262 | |
263 | namespace { |
264 | /// Represents zext(sext(trunc(V))). |
265 | struct CastedValue { |
266 | const Value *V; |
267 | unsigned ZExtBits = 0; |
268 | unsigned SExtBits = 0; |
269 | unsigned TruncBits = 0; |
270 | |
271 | explicit CastedValue(const Value *V) : V(V) {} |
272 | explicit CastedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits, |
273 | unsigned TruncBits) |
274 | : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {} |
275 | |
276 | unsigned getBitWidth() const { |
277 | return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits + |
278 | SExtBits; |
279 | } |
280 | |
281 | CastedValue withValue(const Value *NewV) const { |
282 | return CastedValue(NewV, ZExtBits, SExtBits, TruncBits); |
283 | } |
284 | |
285 | /// Replace V with zext(NewV) |
286 | CastedValue withZExtOfValue(const Value *NewV) const { |
287 | unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - |
288 | NewV->getType()->getPrimitiveSizeInBits(); |
289 | if (ExtendBy <= TruncBits) |
290 | return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy); |
291 | |
292 | // zext(sext(zext(NewV))) == zext(zext(zext(NewV))) |
293 | ExtendBy -= TruncBits; |
294 | return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0); |
295 | } |
296 | |
297 | /// Replace V with sext(NewV) |
298 | CastedValue withSExtOfValue(const Value *NewV) const { |
299 | unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - |
300 | NewV->getType()->getPrimitiveSizeInBits(); |
301 | if (ExtendBy <= TruncBits) |
302 | return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy); |
303 | |
304 | // zext(sext(sext(NewV))) |
305 | ExtendBy -= TruncBits; |
306 | return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0); |
307 | } |
308 | |
309 | APInt evaluateWith(APInt N) const { |
310 | assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && |
311 | "Incompatible bit width" ); |
312 | if (TruncBits) N = N.trunc(width: N.getBitWidth() - TruncBits); |
313 | if (SExtBits) N = N.sext(width: N.getBitWidth() + SExtBits); |
314 | if (ZExtBits) N = N.zext(width: N.getBitWidth() + ZExtBits); |
315 | return N; |
316 | } |
317 | |
318 | ConstantRange evaluateWith(ConstantRange N) const { |
319 | assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && |
320 | "Incompatible bit width" ); |
321 | if (TruncBits) N = N.truncate(BitWidth: N.getBitWidth() - TruncBits); |
322 | if (SExtBits) N = N.signExtend(BitWidth: N.getBitWidth() + SExtBits); |
323 | if (ZExtBits) N = N.zeroExtend(BitWidth: N.getBitWidth() + ZExtBits); |
324 | return N; |
325 | } |
326 | |
327 | bool canDistributeOver(bool NUW, bool NSW) const { |
328 | // zext(x op<nuw> y) == zext(x) op<nuw> zext(y) |
329 | // sext(x op<nsw> y) == sext(x) op<nsw> sext(y) |
330 | // trunc(x op y) == trunc(x) op trunc(y) |
331 | return (!ZExtBits || NUW) && (!SExtBits || NSW); |
332 | } |
333 | |
334 | bool hasSameCastsAs(const CastedValue &Other) const { |
335 | return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits && |
336 | TruncBits == Other.TruncBits; |
337 | } |
338 | }; |
339 | |
340 | /// Represents zext(sext(trunc(V))) * Scale + Offset. |
341 | struct LinearExpression { |
342 | CastedValue Val; |
343 | APInt Scale; |
344 | APInt Offset; |
345 | |
346 | /// True if all operations in this expression are NSW. |
347 | bool IsNSW; |
348 | |
349 | LinearExpression(const CastedValue &Val, const APInt &Scale, |
350 | const APInt &Offset, bool IsNSW) |
351 | : Val(Val), Scale(Scale), Offset(Offset), IsNSW(IsNSW) {} |
352 | |
353 | LinearExpression(const CastedValue &Val) : Val(Val), IsNSW(true) { |
354 | unsigned BitWidth = Val.getBitWidth(); |
355 | Scale = APInt(BitWidth, 1); |
356 | Offset = APInt(BitWidth, 0); |
357 | } |
358 | |
359 | LinearExpression mul(const APInt &Other, bool MulIsNSW) const { |
360 | // The check for zero offset is necessary, because generally |
361 | // (X +nsw Y) *nsw Z does not imply (X *nsw Z) +nsw (Y *nsw Z). |
362 | bool NSW = IsNSW && (Other.isOne() || (MulIsNSW && Offset.isZero())); |
363 | return LinearExpression(Val, Scale * Other, Offset * Other, NSW); |
364 | } |
365 | }; |
366 | } |
367 | |
368 | /// Analyzes the specified value as a linear expression: "A*V + B", where A and |
369 | /// B are constant integers. |
370 | static LinearExpression GetLinearExpression( |
371 | const CastedValue &Val, const DataLayout &DL, unsigned Depth, |
372 | AssumptionCache *AC, DominatorTree *DT) { |
373 | // Limit our recursion depth. |
374 | if (Depth == 6) |
375 | return Val; |
376 | |
377 | if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val: Val.V)) |
378 | return LinearExpression(Val, APInt(Val.getBitWidth(), 0), |
379 | Val.evaluateWith(N: Const->getValue()), true); |
380 | |
381 | if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val: Val.V)) { |
382 | if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Val: BOp->getOperand(i_nocapture: 1))) { |
383 | APInt RHS = Val.evaluateWith(N: RHSC->getValue()); |
384 | // The only non-OBO case we deal with is or, and only limited to the |
385 | // case where it is both nuw and nsw. |
386 | bool NUW = true, NSW = true; |
387 | if (isa<OverflowingBinaryOperator>(Val: BOp)) { |
388 | NUW &= BOp->hasNoUnsignedWrap(); |
389 | NSW &= BOp->hasNoSignedWrap(); |
390 | } |
391 | if (!Val.canDistributeOver(NUW, NSW)) |
392 | return Val; |
393 | |
394 | // While we can distribute over trunc, we cannot preserve nowrap flags |
395 | // in that case. |
396 | if (Val.TruncBits) |
397 | NUW = NSW = false; |
398 | |
399 | LinearExpression E(Val); |
400 | switch (BOp->getOpcode()) { |
401 | default: |
402 | // We don't understand this instruction, so we can't decompose it any |
403 | // further. |
404 | return Val; |
405 | case Instruction::Or: |
406 | // X|C == X+C if it is disjoint. Otherwise we can't analyze it. |
407 | if (!cast<PossiblyDisjointInst>(Val: BOp)->isDisjoint()) |
408 | return Val; |
409 | |
410 | [[fallthrough]]; |
411 | case Instruction::Add: { |
412 | E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0)), DL, |
413 | Depth: Depth + 1, AC, DT); |
414 | E.Offset += RHS; |
415 | E.IsNSW &= NSW; |
416 | break; |
417 | } |
418 | case Instruction::Sub: { |
419 | E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0)), DL, |
420 | Depth: Depth + 1, AC, DT); |
421 | E.Offset -= RHS; |
422 | E.IsNSW &= NSW; |
423 | break; |
424 | } |
425 | case Instruction::Mul: |
426 | E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0)), DL, |
427 | Depth: Depth + 1, AC, DT) |
428 | .mul(Other: RHS, MulIsNSW: NSW); |
429 | break; |
430 | case Instruction::Shl: |
431 | // We're trying to linearize an expression of the kind: |
432 | // shl i8 -128, 36 |
433 | // where the shift count exceeds the bitwidth of the type. |
434 | // We can't decompose this further (the expression would return |
435 | // a poison value). |
436 | if (RHS.getLimitedValue() > Val.getBitWidth()) |
437 | return Val; |
438 | |
439 | E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0)), DL, |
440 | Depth: Depth + 1, AC, DT); |
441 | E.Offset <<= RHS.getLimitedValue(); |
442 | E.Scale <<= RHS.getLimitedValue(); |
443 | E.IsNSW &= NSW; |
444 | break; |
445 | } |
446 | return E; |
447 | } |
448 | } |
449 | |
450 | if (isa<ZExtInst>(Val: Val.V)) |
451 | return GetLinearExpression( |
452 | Val: Val.withZExtOfValue(NewV: cast<CastInst>(Val: Val.V)->getOperand(i_nocapture: 0)), |
453 | DL, Depth: Depth + 1, AC, DT); |
454 | |
455 | if (isa<SExtInst>(Val: Val.V)) |
456 | return GetLinearExpression( |
457 | Val: Val.withSExtOfValue(NewV: cast<CastInst>(Val: Val.V)->getOperand(i_nocapture: 0)), |
458 | DL, Depth: Depth + 1, AC, DT); |
459 | |
460 | return Val; |
461 | } |
462 | |
463 | /// To ensure a pointer offset fits in an integer of size IndexSize |
464 | /// (in bits) when that size is smaller than the maximum index size. This is |
465 | /// an issue, for example, in particular for 32b pointers with negative indices |
466 | /// that rely on two's complement wrap-arounds for precise alias information |
467 | /// where the maximum index size is 64b. |
468 | static void adjustToIndexSize(APInt &Offset, unsigned IndexSize) { |
469 | assert(IndexSize <= Offset.getBitWidth() && "Invalid IndexSize!" ); |
470 | unsigned ShiftBits = Offset.getBitWidth() - IndexSize; |
471 | if (ShiftBits != 0) { |
472 | Offset <<= ShiftBits; |
473 | Offset.ashrInPlace(ShiftAmt: ShiftBits); |
474 | } |
475 | } |
476 | |
477 | namespace { |
478 | // A linear transformation of a Value; this class represents |
479 | // ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale. |
480 | struct VariableGEPIndex { |
481 | CastedValue Val; |
482 | APInt Scale; |
483 | |
484 | // Context instruction to use when querying information about this index. |
485 | const Instruction *CxtI; |
486 | |
487 | /// True if all operations in this expression are NSW. |
488 | bool IsNSW; |
489 | |
490 | /// True if the index should be subtracted rather than added. We don't simply |
491 | /// negate the Scale, to avoid losing the NSW flag: X - INT_MIN*1 may be |
492 | /// non-wrapping, while X + INT_MIN*(-1) wraps. |
493 | bool IsNegated; |
494 | |
495 | bool hasNegatedScaleOf(const VariableGEPIndex &Other) const { |
496 | if (IsNegated == Other.IsNegated) |
497 | return Scale == -Other.Scale; |
498 | return Scale == Other.Scale; |
499 | } |
500 | |
501 | void dump() const { |
502 | print(OS&: dbgs()); |
503 | dbgs() << "\n" ; |
504 | } |
505 | void print(raw_ostream &OS) const { |
506 | OS << "(V=" << Val.V->getName() |
507 | << ", zextbits=" << Val.ZExtBits |
508 | << ", sextbits=" << Val.SExtBits |
509 | << ", truncbits=" << Val.TruncBits |
510 | << ", scale=" << Scale |
511 | << ", nsw=" << IsNSW |
512 | << ", negated=" << IsNegated << ")" ; |
513 | } |
514 | }; |
515 | } |
516 | |
517 | // Represents the internal structure of a GEP, decomposed into a base pointer, |
518 | // constant offsets, and variable scaled indices. |
519 | struct BasicAAResult::DecomposedGEP { |
520 | // Base pointer of the GEP |
521 | const Value *Base; |
522 | // Total constant offset from base. |
523 | APInt Offset; |
524 | // Scaled variable (non-constant) indices. |
525 | SmallVector<VariableGEPIndex, 4> VarIndices; |
526 | // Are all operations inbounds GEPs or non-indexing operations? |
527 | // (std::nullopt iff expression doesn't involve any geps) |
528 | std::optional<bool> InBounds; |
529 | |
530 | void dump() const { |
531 | print(OS&: dbgs()); |
532 | dbgs() << "\n" ; |
533 | } |
534 | void print(raw_ostream &OS) const { |
535 | OS << "(DecomposedGEP Base=" << Base->getName() |
536 | << ", Offset=" << Offset |
537 | << ", VarIndices=[" ; |
538 | for (size_t i = 0; i < VarIndices.size(); i++) { |
539 | if (i != 0) |
540 | OS << ", " ; |
541 | VarIndices[i].print(OS); |
542 | } |
543 | OS << "])" ; |
544 | } |
545 | }; |
546 | |
547 | |
548 | /// If V is a symbolic pointer expression, decompose it into a base pointer |
549 | /// with a constant offset and a number of scaled symbolic offsets. |
550 | /// |
551 | /// The scaled symbolic offsets (represented by pairs of a Value* and a scale |
552 | /// in the VarIndices vector) are Value*'s that are known to be scaled by the |
553 | /// specified amount, but which may have other unrepresented high bits. As |
554 | /// such, the gep cannot necessarily be reconstructed from its decomposed form. |
555 | BasicAAResult::DecomposedGEP |
556 | BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, |
557 | AssumptionCache *AC, DominatorTree *DT) { |
558 | // Limit recursion depth to limit compile time in crazy cases. |
559 | unsigned MaxLookup = MaxLookupSearchDepth; |
560 | SearchTimes++; |
561 | const Instruction *CxtI = dyn_cast<Instruction>(Val: V); |
562 | |
563 | unsigned MaxIndexSize = DL.getMaxIndexSizeInBits(); |
564 | DecomposedGEP Decomposed; |
565 | Decomposed.Offset = APInt(MaxIndexSize, 0); |
566 | do { |
567 | // See if this is a bitcast or GEP. |
568 | const Operator *Op = dyn_cast<Operator>(Val: V); |
569 | if (!Op) { |
570 | // The only non-operator case we can handle are GlobalAliases. |
571 | if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V)) { |
572 | if (!GA->isInterposable()) { |
573 | V = GA->getAliasee(); |
574 | continue; |
575 | } |
576 | } |
577 | Decomposed.Base = V; |
578 | return Decomposed; |
579 | } |
580 | |
581 | if (Op->getOpcode() == Instruction::BitCast || |
582 | Op->getOpcode() == Instruction::AddrSpaceCast) { |
583 | V = Op->getOperand(i: 0); |
584 | continue; |
585 | } |
586 | |
587 | const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Val: Op); |
588 | if (!GEPOp) { |
589 | if (const auto *PHI = dyn_cast<PHINode>(Val: V)) { |
590 | // Look through single-arg phi nodes created by LCSSA. |
591 | if (PHI->getNumIncomingValues() == 1) { |
592 | V = PHI->getIncomingValue(i: 0); |
593 | continue; |
594 | } |
595 | } else if (const auto *Call = dyn_cast<CallBase>(Val: V)) { |
596 | // CaptureTracking can know about special capturing properties of some |
597 | // intrinsics like launder.invariant.group, that can't be expressed with |
598 | // the attributes, but have properties like returning aliasing pointer. |
599 | // Because some analysis may assume that nocaptured pointer is not |
600 | // returned from some special intrinsic (because function would have to |
601 | // be marked with returns attribute), it is crucial to use this function |
602 | // because it should be in sync with CaptureTracking. Not using it may |
603 | // cause weird miscompilations where 2 aliasing pointers are assumed to |
604 | // noalias. |
605 | if (auto *RP = getArgumentAliasingToReturnedPointer(Call, MustPreserveNullness: false)) { |
606 | V = RP; |
607 | continue; |
608 | } |
609 | } |
610 | |
611 | Decomposed.Base = V; |
612 | return Decomposed; |
613 | } |
614 | |
615 | // Track whether we've seen at least one in bounds gep, and if so, whether |
616 | // all geps parsed were in bounds. |
617 | if (Decomposed.InBounds == std::nullopt) |
618 | Decomposed.InBounds = GEPOp->isInBounds(); |
619 | else if (!GEPOp->isInBounds()) |
620 | Decomposed.InBounds = false; |
621 | |
622 | assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized" ); |
623 | |
624 | unsigned AS = GEPOp->getPointerAddressSpace(); |
625 | // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. |
626 | gep_type_iterator GTI = gep_type_begin(GEP: GEPOp); |
627 | unsigned IndexSize = DL.getIndexSizeInBits(AS); |
628 | // Assume all GEP operands are constants until proven otherwise. |
629 | bool GepHasConstantOffset = true; |
630 | for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); |
631 | I != E; ++I, ++GTI) { |
632 | const Value *Index = *I; |
633 | // Compute the (potentially symbolic) offset in bytes for this index. |
634 | if (StructType *STy = GTI.getStructTypeOrNull()) { |
635 | // For a struct, add the member offset. |
636 | unsigned FieldNo = cast<ConstantInt>(Val: Index)->getZExtValue(); |
637 | if (FieldNo == 0) |
638 | continue; |
639 | |
640 | Decomposed.Offset += DL.getStructLayout(Ty: STy)->getElementOffset(Idx: FieldNo); |
641 | continue; |
642 | } |
643 | |
644 | // For an array/pointer, add the element offset, explicitly scaled. |
645 | if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Val: Index)) { |
646 | if (CIdx->isZero()) |
647 | continue; |
648 | |
649 | // Don't attempt to analyze GEPs if the scalable index is not zero. |
650 | TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL); |
651 | if (AllocTypeSize.isScalable()) { |
652 | Decomposed.Base = V; |
653 | return Decomposed; |
654 | } |
655 | |
656 | Decomposed.Offset += AllocTypeSize.getFixedValue() * |
657 | CIdx->getValue().sextOrTrunc(width: MaxIndexSize); |
658 | continue; |
659 | } |
660 | |
661 | TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL); |
662 | if (AllocTypeSize.isScalable()) { |
663 | Decomposed.Base = V; |
664 | return Decomposed; |
665 | } |
666 | |
667 | GepHasConstantOffset = false; |
668 | |
669 | // If the integer type is smaller than the index size, it is implicitly |
670 | // sign extended or truncated to index size. |
671 | unsigned Width = Index->getType()->getIntegerBitWidth(); |
672 | unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0; |
673 | unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0; |
674 | LinearExpression LE = GetLinearExpression( |
675 | Val: CastedValue(Index, 0, SExtBits, TruncBits), DL, Depth: 0, AC, DT); |
676 | |
677 | // Scale by the type size. |
678 | unsigned TypeSize = AllocTypeSize.getFixedValue(); |
679 | LE = LE.mul(Other: APInt(IndexSize, TypeSize), MulIsNSW: GEPOp->isInBounds()); |
680 | Decomposed.Offset += LE.Offset.sext(width: MaxIndexSize); |
681 | APInt Scale = LE.Scale.sext(width: MaxIndexSize); |
682 | |
683 | // If we already had an occurrence of this index variable, merge this |
684 | // scale into it. For example, we want to handle: |
685 | // A[x][x] -> x*16 + x*4 -> x*20 |
686 | // This also ensures that 'x' only appears in the index list once. |
687 | for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) { |
688 | if ((Decomposed.VarIndices[i].Val.V == LE.Val.V || |
689 | areBothVScale(V1: Decomposed.VarIndices[i].Val.V, V2: LE.Val.V)) && |
690 | Decomposed.VarIndices[i].Val.hasSameCastsAs(Other: LE.Val)) { |
691 | Scale += Decomposed.VarIndices[i].Scale; |
692 | LE.IsNSW = false; // We cannot guarantee nsw for the merge. |
693 | Decomposed.VarIndices.erase(CI: Decomposed.VarIndices.begin() + i); |
694 | break; |
695 | } |
696 | } |
697 | |
698 | // Make sure that we have a scale that makes sense for this target's |
699 | // index size. |
700 | adjustToIndexSize(Offset&: Scale, IndexSize); |
701 | |
702 | if (!!Scale) { |
703 | VariableGEPIndex Entry = {.Val: LE.Val, .Scale: Scale, .CxtI: CxtI, .IsNSW: LE.IsNSW, |
704 | /* IsNegated */ false}; |
705 | Decomposed.VarIndices.push_back(Elt: Entry); |
706 | } |
707 | } |
708 | |
709 | // Take care of wrap-arounds |
710 | if (GepHasConstantOffset) |
711 | adjustToIndexSize(Offset&: Decomposed.Offset, IndexSize); |
712 | |
713 | // Analyze the base pointer next. |
714 | V = GEPOp->getOperand(i_nocapture: 0); |
715 | } while (--MaxLookup); |
716 | |
717 | // If the chain of expressions is too deep, just return early. |
718 | Decomposed.Base = V; |
719 | SearchLimitReached++; |
720 | return Decomposed; |
721 | } |
722 | |
723 | ModRefInfo BasicAAResult::getModRefInfoMask(const MemoryLocation &Loc, |
724 | AAQueryInfo &AAQI, |
725 | bool IgnoreLocals) { |
726 | assert(Visited.empty() && "Visited must be cleared after use!" ); |
727 | auto _ = make_scope_exit(F: [&] { Visited.clear(); }); |
728 | |
729 | unsigned MaxLookup = 8; |
730 | SmallVector<const Value *, 16> Worklist; |
731 | Worklist.push_back(Elt: Loc.Ptr); |
732 | ModRefInfo Result = ModRefInfo::NoModRef; |
733 | |
734 | do { |
735 | const Value *V = getUnderlyingObject(V: Worklist.pop_back_val()); |
736 | if (!Visited.insert(Ptr: V).second) |
737 | continue; |
738 | |
739 | // Ignore allocas if we were instructed to do so. |
740 | if (IgnoreLocals && isa<AllocaInst>(Val: V)) |
741 | continue; |
742 | |
743 | // If the location points to memory that is known to be invariant for |
744 | // the life of the underlying SSA value, then we can exclude Mod from |
745 | // the set of valid memory effects. |
746 | // |
747 | // An argument that is marked readonly and noalias is known to be |
748 | // invariant while that function is executing. |
749 | if (const Argument *Arg = dyn_cast<Argument>(Val: V)) { |
750 | if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) { |
751 | Result |= ModRefInfo::Ref; |
752 | continue; |
753 | } |
754 | } |
755 | |
756 | // A global constant can't be mutated. |
757 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V)) { |
758 | // Note: this doesn't require GV to be "ODR" because it isn't legal for a |
759 | // global to be marked constant in some modules and non-constant in |
760 | // others. GV may even be a declaration, not a definition. |
761 | if (!GV->isConstant()) |
762 | return ModRefInfo::ModRef; |
763 | continue; |
764 | } |
765 | |
766 | // If both select values point to local memory, then so does the select. |
767 | if (const SelectInst *SI = dyn_cast<SelectInst>(Val: V)) { |
768 | Worklist.push_back(Elt: SI->getTrueValue()); |
769 | Worklist.push_back(Elt: SI->getFalseValue()); |
770 | continue; |
771 | } |
772 | |
773 | // If all values incoming to a phi node point to local memory, then so does |
774 | // the phi. |
775 | if (const PHINode *PN = dyn_cast<PHINode>(Val: V)) { |
776 | // Don't bother inspecting phi nodes with many operands. |
777 | if (PN->getNumIncomingValues() > MaxLookup) |
778 | return ModRefInfo::ModRef; |
779 | append_range(C&: Worklist, R: PN->incoming_values()); |
780 | continue; |
781 | } |
782 | |
783 | // Otherwise be conservative. |
784 | return ModRefInfo::ModRef; |
785 | } while (!Worklist.empty() && --MaxLookup); |
786 | |
787 | // If we hit the maximum number of instructions to examine, be conservative. |
788 | if (!Worklist.empty()) |
789 | return ModRefInfo::ModRef; |
790 | |
791 | return Result; |
792 | } |
793 | |
794 | static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { |
795 | const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: Call); |
796 | return II && II->getIntrinsicID() == IID; |
797 | } |
798 | |
799 | /// Returns the behavior when calling the given call site. |
800 | MemoryEffects BasicAAResult::getMemoryEffects(const CallBase *Call, |
801 | AAQueryInfo &AAQI) { |
802 | MemoryEffects Min = Call->getAttributes().getMemoryEffects(); |
803 | |
804 | if (const Function *F = dyn_cast<Function>(Val: Call->getCalledOperand())) { |
805 | MemoryEffects FuncME = AAQI.AAR.getMemoryEffects(F); |
806 | // Operand bundles on the call may also read or write memory, in addition |
807 | // to the behavior of the called function. |
808 | if (Call->hasReadingOperandBundles()) |
809 | FuncME |= MemoryEffects::readOnly(); |
810 | if (Call->hasClobberingOperandBundles()) |
811 | FuncME |= MemoryEffects::writeOnly(); |
812 | Min &= FuncME; |
813 | } |
814 | |
815 | return Min; |
816 | } |
817 | |
818 | /// Returns the behavior when calling the given function. For use when the call |
819 | /// site is not known. |
820 | MemoryEffects BasicAAResult::getMemoryEffects(const Function *F) { |
821 | switch (F->getIntrinsicID()) { |
822 | case Intrinsic::experimental_guard: |
823 | case Intrinsic::experimental_deoptimize: |
824 | // These intrinsics can read arbitrary memory, and additionally modref |
825 | // inaccessible memory to model control dependence. |
826 | return MemoryEffects::readOnly() | |
827 | MemoryEffects::inaccessibleMemOnly(MR: ModRefInfo::ModRef); |
828 | } |
829 | |
830 | return F->getMemoryEffects(); |
831 | } |
832 | |
833 | ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call, |
834 | unsigned ArgIdx) { |
835 | if (Call->paramHasAttr(ArgNo: ArgIdx, Attribute::Kind: WriteOnly)) |
836 | return ModRefInfo::Mod; |
837 | |
838 | if (Call->paramHasAttr(ArgNo: ArgIdx, Attribute::Kind: ReadOnly)) |
839 | return ModRefInfo::Ref; |
840 | |
841 | if (Call->paramHasAttr(ArgNo: ArgIdx, Attribute::Kind: ReadNone)) |
842 | return ModRefInfo::NoModRef; |
843 | |
844 | return ModRefInfo::ModRef; |
845 | } |
846 | |
847 | #ifndef NDEBUG |
848 | static const Function *getParent(const Value *V) { |
849 | if (const Instruction *inst = dyn_cast<Instruction>(Val: V)) { |
850 | if (!inst->getParent()) |
851 | return nullptr; |
852 | return inst->getParent()->getParent(); |
853 | } |
854 | |
855 | if (const Argument *arg = dyn_cast<Argument>(Val: V)) |
856 | return arg->getParent(); |
857 | |
858 | return nullptr; |
859 | } |
860 | |
861 | static bool notDifferentParent(const Value *O1, const Value *O2) { |
862 | |
863 | const Function *F1 = getParent(V: O1); |
864 | const Function *F2 = getParent(V: O2); |
865 | |
866 | return !F1 || !F2 || F1 == F2; |
867 | } |
868 | #endif |
869 | |
870 | AliasResult BasicAAResult::alias(const MemoryLocation &LocA, |
871 | const MemoryLocation &LocB, AAQueryInfo &AAQI, |
872 | const Instruction *CtxI) { |
873 | assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && |
874 | "BasicAliasAnalysis doesn't support interprocedural queries." ); |
875 | return aliasCheck(V1: LocA.Ptr, V1Size: LocA.Size, V2: LocB.Ptr, V2Size: LocB.Size, AAQI, CtxI); |
876 | } |
877 | |
878 | /// Checks to see if the specified callsite can clobber the specified memory |
879 | /// object. |
880 | /// |
881 | /// Since we only look at local properties of this function, we really can't |
882 | /// say much about this query. We do, however, use simple "address taken" |
883 | /// analysis on local objects. |
884 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, |
885 | const MemoryLocation &Loc, |
886 | AAQueryInfo &AAQI) { |
887 | assert(notDifferentParent(Call, Loc.Ptr) && |
888 | "AliasAnalysis query involving multiple functions!" ); |
889 | |
890 | const Value *Object = getUnderlyingObject(V: Loc.Ptr); |
891 | |
892 | // Calls marked 'tail' cannot read or write allocas from the current frame |
893 | // because the current frame might be destroyed by the time they run. However, |
894 | // a tail call may use an alloca with byval. Calling with byval copies the |
895 | // contents of the alloca into argument registers or stack slots, so there is |
896 | // no lifetime issue. |
897 | if (isa<AllocaInst>(Val: Object)) |
898 | if (const CallInst *CI = dyn_cast<CallInst>(Val: Call)) |
899 | if (CI->isTailCall() && |
900 | !CI->getAttributes().hasAttrSomewhere(Attribute::Kind: ByVal)) |
901 | return ModRefInfo::NoModRef; |
902 | |
903 | // Stack restore is able to modify unescaped dynamic allocas. Assume it may |
904 | // modify them even though the alloca is not escaped. |
905 | if (auto *AI = dyn_cast<AllocaInst>(Val: Object)) |
906 | if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) |
907 | return ModRefInfo::Mod; |
908 | |
909 | // A call can access a locally allocated object either because it is passed as |
910 | // an argument to the call, or because it has escaped prior to the call. |
911 | // |
912 | // Make sure the object has not escaped here, and then check that none of the |
913 | // call arguments alias the object below. |
914 | if (!isa<Constant>(Val: Object) && Call != Object && |
915 | AAQI.CI->isNotCapturedBefore(Object, I: Call, /*OrAt*/ false)) { |
916 | |
917 | // Optimistically assume that call doesn't touch Object and check this |
918 | // assumption in the following loop. |
919 | ModRefInfo Result = ModRefInfo::NoModRef; |
920 | |
921 | unsigned OperandNo = 0; |
922 | for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); |
923 | CI != CE; ++CI, ++OperandNo) { |
924 | if (!(*CI)->getType()->isPointerTy()) |
925 | continue; |
926 | |
927 | // Call doesn't access memory through this operand, so we don't care |
928 | // if it aliases with Object. |
929 | if (Call->doesNotAccessMemory(OpNo: OperandNo)) |
930 | continue; |
931 | |
932 | // If this is a no-capture pointer argument, see if we can tell that it |
933 | // is impossible to alias the pointer we're checking. |
934 | AliasResult AR = |
935 | AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: *CI), |
936 | LocB: MemoryLocation::getBeforeOrAfter(Ptr: Object), AAQI); |
937 | // Operand doesn't alias 'Object', continue looking for other aliases |
938 | if (AR == AliasResult::NoAlias) |
939 | continue; |
940 | // Operand aliases 'Object', but call doesn't modify it. Strengthen |
941 | // initial assumption and keep looking in case if there are more aliases. |
942 | if (Call->onlyReadsMemory(OpNo: OperandNo)) { |
943 | Result |= ModRefInfo::Ref; |
944 | continue; |
945 | } |
946 | // Operand aliases 'Object' but call only writes into it. |
947 | if (Call->onlyWritesMemory(OpNo: OperandNo)) { |
948 | Result |= ModRefInfo::Mod; |
949 | continue; |
950 | } |
951 | // This operand aliases 'Object' and call reads and writes into it. |
952 | // Setting ModRef will not yield an early return below, MustAlias is not |
953 | // used further. |
954 | Result = ModRefInfo::ModRef; |
955 | break; |
956 | } |
957 | |
958 | // Early return if we improved mod ref information |
959 | if (!isModAndRefSet(MRI: Result)) |
960 | return Result; |
961 | } |
962 | |
963 | // If the call is malloc/calloc like, we can assume that it doesn't |
964 | // modify any IR visible value. This is only valid because we assume these |
965 | // routines do not read values visible in the IR. TODO: Consider special |
966 | // casing realloc and strdup routines which access only their arguments as |
967 | // well. Or alternatively, replace all of this with inaccessiblememonly once |
968 | // that's implemented fully. |
969 | if (isMallocOrCallocLikeFn(V: Call, TLI: &TLI)) { |
970 | // Be conservative if the accessed pointer may alias the allocation - |
971 | // fallback to the generic handling below. |
972 | if (AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: Call), LocB: Loc, AAQI) == |
973 | AliasResult::NoAlias) |
974 | return ModRefInfo::NoModRef; |
975 | } |
976 | |
977 | // Like assumes, invariant.start intrinsics were also marked as arbitrarily |
978 | // writing so that proper control dependencies are maintained but they never |
979 | // mod any particular memory location visible to the IR. |
980 | // *Unlike* assumes (which are now modeled as NoModRef), invariant.start |
981 | // intrinsic is now modeled as reading memory. This prevents hoisting the |
982 | // invariant.start intrinsic over stores. Consider: |
983 | // *ptr = 40; |
984 | // *ptr = 50; |
985 | // invariant_start(ptr) |
986 | // int val = *ptr; |
987 | // print(val); |
988 | // |
989 | // This cannot be transformed to: |
990 | // |
991 | // *ptr = 40; |
992 | // invariant_start(ptr) |
993 | // *ptr = 50; |
994 | // int val = *ptr; |
995 | // print(val); |
996 | // |
997 | // The transformation will cause the second store to be ignored (based on |
998 | // rules of invariant.start) and print 40, while the first program always |
999 | // prints 50. |
1000 | if (isIntrinsicCall(Call, Intrinsic::invariant_start)) |
1001 | return ModRefInfo::Ref; |
1002 | |
1003 | // Be conservative. |
1004 | return ModRefInfo::ModRef; |
1005 | } |
1006 | |
1007 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, |
1008 | const CallBase *Call2, |
1009 | AAQueryInfo &AAQI) { |
1010 | // Guard intrinsics are marked as arbitrarily writing so that proper control |
1011 | // dependencies are maintained but they never mods any particular memory |
1012 | // location. |
1013 | // |
1014 | // *Unlike* assumes, guard intrinsics are modeled as reading memory since the |
1015 | // heap state at the point the guard is issued needs to be consistent in case |
1016 | // the guard invokes the "deopt" continuation. |
1017 | |
1018 | // NB! This function is *not* commutative, so we special case two |
1019 | // possibilities for guard intrinsics. |
1020 | |
1021 | if (isIntrinsicCall(Call1, Intrinsic::experimental_guard)) |
1022 | return isModSet(MRI: getMemoryEffects(Call: Call2, AAQI).getModRef()) |
1023 | ? ModRefInfo::Ref |
1024 | : ModRefInfo::NoModRef; |
1025 | |
1026 | if (isIntrinsicCall(Call2, Intrinsic::experimental_guard)) |
1027 | return isModSet(MRI: getMemoryEffects(Call: Call1, AAQI).getModRef()) |
1028 | ? ModRefInfo::Mod |
1029 | : ModRefInfo::NoModRef; |
1030 | |
1031 | // Be conservative. |
1032 | return ModRefInfo::ModRef; |
1033 | } |
1034 | |
1035 | /// Return true if we know V to the base address of the corresponding memory |
1036 | /// object. This implies that any address less than V must be out of bounds |
1037 | /// for the underlying object. Note that just being isIdentifiedObject() is |
1038 | /// not enough - For example, a negative offset from a noalias argument or call |
1039 | /// can be inbounds w.r.t the actual underlying object. |
1040 | static bool isBaseOfObject(const Value *V) { |
1041 | // TODO: We can handle other cases here |
1042 | // 1) For GC languages, arguments to functions are often required to be |
1043 | // base pointers. |
1044 | // 2) Result of allocation routines are often base pointers. Leverage TLI. |
1045 | return (isa<AllocaInst>(Val: V) || isa<GlobalVariable>(Val: V)); |
1046 | } |
1047 | |
1048 | /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against |
1049 | /// another pointer. |
1050 | /// |
1051 | /// We know that V1 is a GEP, but we don't know anything about V2. |
1052 | /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for |
1053 | /// V2. |
1054 | AliasResult BasicAAResult::aliasGEP( |
1055 | const GEPOperator *GEP1, LocationSize V1Size, |
1056 | const Value *V2, LocationSize V2Size, |
1057 | const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { |
1058 | if (!V1Size.hasValue() && !V2Size.hasValue()) { |
1059 | // TODO: This limitation exists for compile-time reasons. Relax it if we |
1060 | // can avoid exponential pathological cases. |
1061 | if (!isa<GEPOperator>(Val: V2)) |
1062 | return AliasResult::MayAlias; |
1063 | |
1064 | // If both accesses have unknown size, we can only check whether the base |
1065 | // objects don't alias. |
1066 | AliasResult BaseAlias = |
1067 | AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV1), |
1068 | LocB: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV2), AAQI); |
1069 | return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias |
1070 | : AliasResult::MayAlias; |
1071 | } |
1072 | |
1073 | DominatorTree *DT = getDT(AAQI); |
1074 | DecomposedGEP DecompGEP1 = DecomposeGEPExpression(V: GEP1, DL, AC: &AC, DT); |
1075 | DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V: V2, DL, AC: &AC, DT); |
1076 | |
1077 | // Bail if we were not able to decompose anything. |
1078 | if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2) |
1079 | return AliasResult::MayAlias; |
1080 | |
1081 | // Subtract the GEP2 pointer from the GEP1 pointer to find out their |
1082 | // symbolic difference. |
1083 | subtractDecomposedGEPs(DestGEP&: DecompGEP1, SrcGEP: DecompGEP2, AAQI); |
1084 | |
1085 | // If an inbounds GEP would have to start from an out of bounds address |
1086 | // for the two to alias, then we can assume noalias. |
1087 | // TODO: Remove !isScalable() once BasicAA fully support scalable location |
1088 | // size |
1089 | if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() && |
1090 | V2Size.hasValue() && !V2Size.isScalable() && |
1091 | DecompGEP1.Offset.sge(RHS: V2Size.getValue()) && |
1092 | isBaseOfObject(V: DecompGEP2.Base)) |
1093 | return AliasResult::NoAlias; |
1094 | |
1095 | if (isa<GEPOperator>(Val: V2)) { |
1096 | // Symmetric case to above. |
1097 | if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() && |
1098 | V1Size.hasValue() && !V1Size.isScalable() && |
1099 | DecompGEP1.Offset.sle(RHS: -V1Size.getValue()) && |
1100 | isBaseOfObject(V: DecompGEP1.Base)) |
1101 | return AliasResult::NoAlias; |
1102 | } |
1103 | |
1104 | // For GEPs with identical offsets, we can preserve the size and AAInfo |
1105 | // when performing the alias check on the underlying objects. |
1106 | if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) |
1107 | return AAQI.AAR.alias(LocA: MemoryLocation(DecompGEP1.Base, V1Size), |
1108 | LocB: MemoryLocation(DecompGEP2.Base, V2Size), AAQI); |
1109 | |
1110 | // Do the base pointers alias? |
1111 | AliasResult BaseAlias = |
1112 | AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP1.Base), |
1113 | LocB: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP2.Base), AAQI); |
1114 | |
1115 | // If we get a No or May, then return it immediately, no amount of analysis |
1116 | // will improve this situation. |
1117 | if (BaseAlias != AliasResult::MustAlias) { |
1118 | assert(BaseAlias == AliasResult::NoAlias || |
1119 | BaseAlias == AliasResult::MayAlias); |
1120 | return BaseAlias; |
1121 | } |
1122 | |
1123 | // If there is a constant difference between the pointers, but the difference |
1124 | // is less than the size of the associated memory object, then we know |
1125 | // that the objects are partially overlapping. If the difference is |
1126 | // greater, we know they do not overlap. |
1127 | if (DecompGEP1.VarIndices.empty()) { |
1128 | APInt &Off = DecompGEP1.Offset; |
1129 | |
1130 | // Initialize for Off >= 0 (V2 <= GEP1) case. |
1131 | const Value *LeftPtr = V2; |
1132 | const Value *RightPtr = GEP1; |
1133 | LocationSize VLeftSize = V2Size; |
1134 | LocationSize VRightSize = V1Size; |
1135 | const bool Swapped = Off.isNegative(); |
1136 | |
1137 | if (Swapped) { |
1138 | // Swap if we have the situation where: |
1139 | // + + |
1140 | // | BaseOffset | |
1141 | // ---------------->| |
1142 | // |-->V1Size |-------> V2Size |
1143 | // GEP1 V2 |
1144 | std::swap(a&: LeftPtr, b&: RightPtr); |
1145 | std::swap(a&: VLeftSize, b&: VRightSize); |
1146 | Off = -Off; |
1147 | } |
1148 | |
1149 | if (!VLeftSize.hasValue()) |
1150 | return AliasResult::MayAlias; |
1151 | |
1152 | const TypeSize LSize = VLeftSize.getValue(); |
1153 | if (!LSize.isScalable()) { |
1154 | if (Off.ult(RHS: LSize)) { |
1155 | // Conservatively drop processing if a phi was visited and/or offset is |
1156 | // too big. |
1157 | AliasResult AR = AliasResult::PartialAlias; |
1158 | if (VRightSize.hasValue() && !VRightSize.isScalable() && |
1159 | Off.ule(INT32_MAX) && (Off + VRightSize.getValue()).ule(RHS: LSize)) { |
1160 | // Memory referenced by right pointer is nested. Save the offset in |
1161 | // cache. Note that originally offset estimated as GEP1-V2, but |
1162 | // AliasResult contains the shift that represents GEP1+Offset=V2. |
1163 | AR.setOffset(-Off.getSExtValue()); |
1164 | AR.swap(DoSwap: Swapped); |
1165 | } |
1166 | return AR; |
1167 | } |
1168 | return AliasResult::NoAlias; |
1169 | } else { |
1170 | // We can use the getVScaleRange to prove that Off >= (CR.upper * LSize). |
1171 | ConstantRange CR = getVScaleRange(F: &F, BitWidth: Off.getBitWidth()); |
1172 | bool Overflow; |
1173 | APInt UpperRange = CR.getUnsignedMax().umul_ov( |
1174 | RHS: APInt(Off.getBitWidth(), LSize.getKnownMinValue()), Overflow); |
1175 | if (!Overflow && Off.uge(RHS: UpperRange)) |
1176 | return AliasResult::NoAlias; |
1177 | } |
1178 | } |
1179 | |
1180 | // VScale Alias Analysis - Given one scalable offset between accesses and a |
1181 | // scalable typesize, we can divide each side by vscale, treating both values |
1182 | // as a constant. We prove that Offset/vscale >= TypeSize/vscale. |
1183 | if (DecompGEP1.VarIndices.size() == 1 && |
1184 | DecompGEP1.VarIndices[0].Val.TruncBits == 0 && |
1185 | DecompGEP1.Offset.isZero() && |
1186 | PatternMatch::match(V: DecompGEP1.VarIndices[0].Val.V, |
1187 | P: PatternMatch::m_VScale())) { |
1188 | const VariableGEPIndex &ScalableVar = DecompGEP1.VarIndices[0]; |
1189 | APInt Scale = |
1190 | ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale; |
1191 | LocationSize VLeftSize = Scale.isNegative() ? V1Size : V2Size; |
1192 | |
1193 | // Check if the offset is known to not overflow, if it does then attempt to |
1194 | // prove it with the known values of vscale_range. |
1195 | bool Overflows = !DecompGEP1.VarIndices[0].IsNSW; |
1196 | if (Overflows) { |
1197 | ConstantRange CR = getVScaleRange(F: &F, BitWidth: Scale.getBitWidth()); |
1198 | (void)CR.getSignedMax().smul_ov(RHS: Scale, Overflow&: Overflows); |
1199 | } |
1200 | |
1201 | if (!Overflows) { |
1202 | // Note that we do not check that the typesize is scalable, as vscale >= 1 |
1203 | // so noalias still holds so long as the dependency distance is at least |
1204 | // as big as the typesize. |
1205 | if (VLeftSize.hasValue() && |
1206 | Scale.abs().uge(RHS: VLeftSize.getValue().getKnownMinValue())) |
1207 | return AliasResult::NoAlias; |
1208 | } |
1209 | } |
1210 | |
1211 | // Bail on analysing scalable LocationSize |
1212 | if (V1Size.isScalable() || V2Size.isScalable()) |
1213 | return AliasResult::MayAlias; |
1214 | |
1215 | // We need to know both acess sizes for all the following heuristics. |
1216 | if (!V1Size.hasValue() || !V2Size.hasValue()) |
1217 | return AliasResult::MayAlias; |
1218 | |
1219 | APInt GCD; |
1220 | ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset); |
1221 | for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { |
1222 | const VariableGEPIndex &Index = DecompGEP1.VarIndices[i]; |
1223 | const APInt &Scale = Index.Scale; |
1224 | APInt ScaleForGCD = Scale; |
1225 | if (!Index.IsNSW) |
1226 | ScaleForGCD = |
1227 | APInt::getOneBitSet(numBits: Scale.getBitWidth(), BitNo: Scale.countr_zero()); |
1228 | |
1229 | if (i == 0) |
1230 | GCD = ScaleForGCD.abs(); |
1231 | else |
1232 | GCD = APIntOps::GreatestCommonDivisor(A: GCD, B: ScaleForGCD.abs()); |
1233 | |
1234 | ConstantRange CR = computeConstantRange(V: Index.Val.V, /* ForSigned */ false, |
1235 | UseInstrInfo: true, AC: &AC, CtxI: Index.CxtI); |
1236 | KnownBits Known = |
1237 | computeKnownBits(V: Index.Val.V, DL, Depth: 0, AC: &AC, CxtI: Index.CxtI, DT); |
1238 | CR = CR.intersectWith( |
1239 | CR: ConstantRange::fromKnownBits(Known, /* Signed */ IsSigned: true), |
1240 | Type: ConstantRange::Signed); |
1241 | CR = Index.Val.evaluateWith(N: CR).sextOrTrunc(BitWidth: OffsetRange.getBitWidth()); |
1242 | |
1243 | assert(OffsetRange.getBitWidth() == Scale.getBitWidth() && |
1244 | "Bit widths are normalized to MaxIndexSize" ); |
1245 | if (Index.IsNSW) |
1246 | CR = CR.smul_sat(Other: ConstantRange(Scale)); |
1247 | else |
1248 | CR = CR.smul_fast(Other: ConstantRange(Scale)); |
1249 | |
1250 | if (Index.IsNegated) |
1251 | OffsetRange = OffsetRange.sub(Other: CR); |
1252 | else |
1253 | OffsetRange = OffsetRange.add(Other: CR); |
1254 | } |
1255 | |
1256 | // We now have accesses at two offsets from the same base: |
1257 | // 1. (...)*GCD + DecompGEP1.Offset with size V1Size |
1258 | // 2. 0 with size V2Size |
1259 | // Using arithmetic modulo GCD, the accesses are at |
1260 | // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits |
1261 | // into the range [V2Size..GCD), then we know they cannot overlap. |
1262 | APInt ModOffset = DecompGEP1.Offset.srem(RHS: GCD); |
1263 | if (ModOffset.isNegative()) |
1264 | ModOffset += GCD; // We want mod, not rem. |
1265 | if (ModOffset.uge(RHS: V2Size.getValue()) && |
1266 | (GCD - ModOffset).uge(RHS: V1Size.getValue())) |
1267 | return AliasResult::NoAlias; |
1268 | |
1269 | // Compute ranges of potentially accessed bytes for both accesses. If the |
1270 | // interseciton is empty, there can be no overlap. |
1271 | unsigned BW = OffsetRange.getBitWidth(); |
1272 | ConstantRange Range1 = OffsetRange.add( |
1273 | Other: ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue()))); |
1274 | ConstantRange Range2 = |
1275 | ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue())); |
1276 | if (Range1.intersectWith(CR: Range2).isEmptySet()) |
1277 | return AliasResult::NoAlias; |
1278 | |
1279 | // Try to determine the range of values for VarIndex such that |
1280 | // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex. |
1281 | std::optional<APInt> MinAbsVarIndex; |
1282 | if (DecompGEP1.VarIndices.size() == 1) { |
1283 | // VarIndex = Scale*V. |
1284 | const VariableGEPIndex &Var = DecompGEP1.VarIndices[0]; |
1285 | if (Var.Val.TruncBits == 0 && |
1286 | isKnownNonZero(V: Var.Val.V, DL, Depth: 0, AC: &AC, CxtI: Var.CxtI, DT)) { |
1287 | // Check if abs(V*Scale) >= abs(Scale) holds in the presence of |
1288 | // potentially wrapping math. |
1289 | auto MultiplyByScaleNoWrap = [](const VariableGEPIndex &Var) { |
1290 | if (Var.IsNSW) |
1291 | return true; |
1292 | |
1293 | int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits(); |
1294 | // If Scale is small enough so that abs(V*Scale) >= abs(Scale) holds. |
1295 | // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a |
1296 | // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap. |
1297 | int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW; |
1298 | if (MaxScaleValueBW <= 0) |
1299 | return false; |
1300 | return Var.Scale.ule( |
1301 | RHS: APInt::getMaxValue(numBits: MaxScaleValueBW).zext(width: Var.Scale.getBitWidth())); |
1302 | }; |
1303 | // Refine MinAbsVarIndex, if abs(Scale*V) >= abs(Scale) holds in the |
1304 | // presence of potentially wrapping math. |
1305 | if (MultiplyByScaleNoWrap(Var)) { |
1306 | // If V != 0 then abs(VarIndex) >= abs(Scale). |
1307 | MinAbsVarIndex = Var.Scale.abs(); |
1308 | } |
1309 | } |
1310 | } else if (DecompGEP1.VarIndices.size() == 2) { |
1311 | // VarIndex = Scale*V0 + (-Scale)*V1. |
1312 | // If V0 != V1 then abs(VarIndex) >= abs(Scale). |
1313 | // Check that MayBeCrossIteration is false, to avoid reasoning about |
1314 | // inequality of values across loop iterations. |
1315 | const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0]; |
1316 | const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1]; |
1317 | if (Var0.hasNegatedScaleOf(Other: Var1) && Var0.Val.TruncBits == 0 && |
1318 | Var0.Val.hasSameCastsAs(Other: Var1.Val) && !AAQI.MayBeCrossIteration && |
1319 | isKnownNonEqual(V1: Var0.Val.V, V2: Var1.Val.V, DL, AC: &AC, /* CxtI */ nullptr, |
1320 | DT)) |
1321 | MinAbsVarIndex = Var0.Scale.abs(); |
1322 | } |
1323 | |
1324 | if (MinAbsVarIndex) { |
1325 | // The constant offset will have added at least +/-MinAbsVarIndex to it. |
1326 | APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex; |
1327 | APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex; |
1328 | // We know that Offset <= OffsetLo || Offset >= OffsetHi |
1329 | if (OffsetLo.isNegative() && (-OffsetLo).uge(RHS: V1Size.getValue()) && |
1330 | OffsetHi.isNonNegative() && OffsetHi.uge(RHS: V2Size.getValue())) |
1331 | return AliasResult::NoAlias; |
1332 | } |
1333 | |
1334 | if (constantOffsetHeuristic(GEP: DecompGEP1, V1Size, V2Size, AC: &AC, DT, AAQI)) |
1335 | return AliasResult::NoAlias; |
1336 | |
1337 | // Statically, we can see that the base objects are the same, but the |
1338 | // pointers have dynamic offsets which we can't resolve. And none of our |
1339 | // little tricks above worked. |
1340 | return AliasResult::MayAlias; |
1341 | } |
1342 | |
1343 | static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { |
1344 | // If the results agree, take it. |
1345 | if (A == B) |
1346 | return A; |
1347 | // A mix of PartialAlias and MustAlias is PartialAlias. |
1348 | if ((A == AliasResult::PartialAlias && B == AliasResult::MustAlias) || |
1349 | (B == AliasResult::PartialAlias && A == AliasResult::MustAlias)) |
1350 | return AliasResult::PartialAlias; |
1351 | // Otherwise, we don't know anything. |
1352 | return AliasResult::MayAlias; |
1353 | } |
1354 | |
1355 | /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction |
1356 | /// against another. |
1357 | AliasResult |
1358 | BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize, |
1359 | const Value *V2, LocationSize V2Size, |
1360 | AAQueryInfo &AAQI) { |
1361 | // If the values are Selects with the same condition, we can do a more precise |
1362 | // check: just check for aliases between the values on corresponding arms. |
1363 | if (const SelectInst *SI2 = dyn_cast<SelectInst>(Val: V2)) |
1364 | if (isValueEqualInPotentialCycles(V1: SI->getCondition(), V2: SI2->getCondition(), |
1365 | AAQI)) { |
1366 | AliasResult Alias = |
1367 | AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize), |
1368 | LocB: MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); |
1369 | if (Alias == AliasResult::MayAlias) |
1370 | return AliasResult::MayAlias; |
1371 | AliasResult ThisAlias = |
1372 | AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize), |
1373 | LocB: MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); |
1374 | return MergeAliasResults(A: ThisAlias, B: Alias); |
1375 | } |
1376 | |
1377 | // If both arms of the Select node NoAlias or MustAlias V2, then returns |
1378 | // NoAlias / MustAlias. Otherwise, returns MayAlias. |
1379 | AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize), |
1380 | LocB: MemoryLocation(V2, V2Size), AAQI); |
1381 | if (Alias == AliasResult::MayAlias) |
1382 | return AliasResult::MayAlias; |
1383 | |
1384 | AliasResult ThisAlias = |
1385 | AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize), |
1386 | LocB: MemoryLocation(V2, V2Size), AAQI); |
1387 | return MergeAliasResults(A: ThisAlias, B: Alias); |
1388 | } |
1389 | |
1390 | /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against |
1391 | /// another. |
1392 | AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, |
1393 | const Value *V2, LocationSize V2Size, |
1394 | AAQueryInfo &AAQI) { |
1395 | if (!PN->getNumIncomingValues()) |
1396 | return AliasResult::NoAlias; |
1397 | // If the values are PHIs in the same block, we can do a more precise |
1398 | // as well as efficient check: just check for aliases between the values |
1399 | // on corresponding edges. |
1400 | if (const PHINode *PN2 = dyn_cast<PHINode>(Val: V2)) |
1401 | if (PN2->getParent() == PN->getParent()) { |
1402 | std::optional<AliasResult> Alias; |
1403 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
1404 | AliasResult ThisAlias = AAQI.AAR.alias( |
1405 | LocA: MemoryLocation(PN->getIncomingValue(i), PNSize), |
1406 | LocB: MemoryLocation( |
1407 | PN2->getIncomingValueForBlock(BB: PN->getIncomingBlock(i)), V2Size), |
1408 | AAQI); |
1409 | if (Alias) |
1410 | *Alias = MergeAliasResults(A: *Alias, B: ThisAlias); |
1411 | else |
1412 | Alias = ThisAlias; |
1413 | if (*Alias == AliasResult::MayAlias) |
1414 | break; |
1415 | } |
1416 | return *Alias; |
1417 | } |
1418 | |
1419 | SmallVector<Value *, 4> V1Srcs; |
1420 | // If a phi operand recurses back to the phi, we can still determine NoAlias |
1421 | // if we don't alias the underlying objects of the other phi operands, as we |
1422 | // know that the recursive phi needs to be based on them in some way. |
1423 | bool isRecursive = false; |
1424 | auto CheckForRecPhi = [&](Value *PV) { |
1425 | if (!EnableRecPhiAnalysis) |
1426 | return false; |
1427 | if (getUnderlyingObject(V: PV) == PN) { |
1428 | isRecursive = true; |
1429 | return true; |
1430 | } |
1431 | return false; |
1432 | }; |
1433 | |
1434 | SmallPtrSet<Value *, 4> UniqueSrc; |
1435 | Value *OnePhi = nullptr; |
1436 | for (Value *PV1 : PN->incoming_values()) { |
1437 | // Skip the phi itself being the incoming value. |
1438 | if (PV1 == PN) |
1439 | continue; |
1440 | |
1441 | if (isa<PHINode>(Val: PV1)) { |
1442 | if (OnePhi && OnePhi != PV1) { |
1443 | // To control potential compile time explosion, we choose to be |
1444 | // conserviate when we have more than one Phi input. It is important |
1445 | // that we handle the single phi case as that lets us handle LCSSA |
1446 | // phi nodes and (combined with the recursive phi handling) simple |
1447 | // pointer induction variable patterns. |
1448 | return AliasResult::MayAlias; |
1449 | } |
1450 | OnePhi = PV1; |
1451 | } |
1452 | |
1453 | if (CheckForRecPhi(PV1)) |
1454 | continue; |
1455 | |
1456 | if (UniqueSrc.insert(Ptr: PV1).second) |
1457 | V1Srcs.push_back(Elt: PV1); |
1458 | } |
1459 | |
1460 | if (OnePhi && UniqueSrc.size() > 1) |
1461 | // Out of an abundance of caution, allow only the trivial lcssa and |
1462 | // recursive phi cases. |
1463 | return AliasResult::MayAlias; |
1464 | |
1465 | // If V1Srcs is empty then that means that the phi has no underlying non-phi |
1466 | // value. This should only be possible in blocks unreachable from the entry |
1467 | // block, but return MayAlias just in case. |
1468 | if (V1Srcs.empty()) |
1469 | return AliasResult::MayAlias; |
1470 | |
1471 | // If this PHI node is recursive, indicate that the pointer may be moved |
1472 | // across iterations. We can only prove NoAlias if different underlying |
1473 | // objects are involved. |
1474 | if (isRecursive) |
1475 | PNSize = LocationSize::beforeOrAfterPointer(); |
1476 | |
1477 | // In the recursive alias queries below, we may compare values from two |
1478 | // different loop iterations. |
1479 | SaveAndRestore SavedMayBeCrossIteration(AAQI.MayBeCrossIteration, true); |
1480 | |
1481 | AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(V1Srcs[0], PNSize), |
1482 | LocB: MemoryLocation(V2, V2Size), AAQI); |
1483 | |
1484 | // Early exit if the check of the first PHI source against V2 is MayAlias. |
1485 | // Other results are not possible. |
1486 | if (Alias == AliasResult::MayAlias) |
1487 | return AliasResult::MayAlias; |
1488 | // With recursive phis we cannot guarantee that MustAlias/PartialAlias will |
1489 | // remain valid to all elements and needs to conservatively return MayAlias. |
1490 | if (isRecursive && Alias != AliasResult::NoAlias) |
1491 | return AliasResult::MayAlias; |
1492 | |
1493 | // If all sources of the PHI node NoAlias or MustAlias V2, then returns |
1494 | // NoAlias / MustAlias. Otherwise, returns MayAlias. |
1495 | for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { |
1496 | Value *V = V1Srcs[i]; |
1497 | |
1498 | AliasResult ThisAlias = AAQI.AAR.alias( |
1499 | LocA: MemoryLocation(V, PNSize), LocB: MemoryLocation(V2, V2Size), AAQI); |
1500 | Alias = MergeAliasResults(A: ThisAlias, B: Alias); |
1501 | if (Alias == AliasResult::MayAlias) |
1502 | break; |
1503 | } |
1504 | |
1505 | return Alias; |
1506 | } |
1507 | |
1508 | /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as |
1509 | /// array references. |
1510 | AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, |
1511 | const Value *V2, LocationSize V2Size, |
1512 | AAQueryInfo &AAQI, |
1513 | const Instruction *CtxI) { |
1514 | // If either of the memory references is empty, it doesn't matter what the |
1515 | // pointer values are. |
1516 | if (V1Size.isZero() || V2Size.isZero()) |
1517 | return AliasResult::NoAlias; |
1518 | |
1519 | // Strip off any casts if they exist. |
1520 | V1 = V1->stripPointerCastsForAliasAnalysis(); |
1521 | V2 = V2->stripPointerCastsForAliasAnalysis(); |
1522 | |
1523 | // If V1 or V2 is undef, the result is NoAlias because we can always pick a |
1524 | // value for undef that aliases nothing in the program. |
1525 | if (isa<UndefValue>(Val: V1) || isa<UndefValue>(Val: V2)) |
1526 | return AliasResult::NoAlias; |
1527 | |
1528 | // Are we checking for alias of the same value? |
1529 | // Because we look 'through' phi nodes, we could look at "Value" pointers from |
1530 | // different iterations. We must therefore make sure that this is not the |
1531 | // case. The function isValueEqualInPotentialCycles ensures that this cannot |
1532 | // happen by looking at the visited phi nodes and making sure they cannot |
1533 | // reach the value. |
1534 | if (isValueEqualInPotentialCycles(V1, V2, AAQI)) |
1535 | return AliasResult::MustAlias; |
1536 | |
1537 | if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) |
1538 | return AliasResult::NoAlias; // Scalars cannot alias each other |
1539 | |
1540 | // Figure out what objects these things are pointing to if we can. |
1541 | const Value *O1 = getUnderlyingObject(V: V1, MaxLookup: MaxLookupSearchDepth); |
1542 | const Value *O2 = getUnderlyingObject(V: V2, MaxLookup: MaxLookupSearchDepth); |
1543 | |
1544 | // Null values in the default address space don't point to any object, so they |
1545 | // don't alias any other pointer. |
1546 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O1)) |
1547 | if (!NullPointerIsDefined(F: &F, AS: CPN->getType()->getAddressSpace())) |
1548 | return AliasResult::NoAlias; |
1549 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O2)) |
1550 | if (!NullPointerIsDefined(F: &F, AS: CPN->getType()->getAddressSpace())) |
1551 | return AliasResult::NoAlias; |
1552 | |
1553 | if (O1 != O2) { |
1554 | // If V1/V2 point to two different objects, we know that we have no alias. |
1555 | if (isIdentifiedObject(V: O1) && isIdentifiedObject(V: O2)) |
1556 | return AliasResult::NoAlias; |
1557 | |
1558 | // Function arguments can't alias with things that are known to be |
1559 | // unambigously identified at the function level. |
1560 | if ((isa<Argument>(Val: O1) && isIdentifiedFunctionLocal(V: O2)) || |
1561 | (isa<Argument>(Val: O2) && isIdentifiedFunctionLocal(V: O1))) |
1562 | return AliasResult::NoAlias; |
1563 | |
1564 | // If one pointer is the result of a call/invoke or load and the other is a |
1565 | // non-escaping local object within the same function, then we know the |
1566 | // object couldn't escape to a point where the call could return it. |
1567 | // |
1568 | // Note that if the pointers are in different functions, there are a |
1569 | // variety of complications. A call with a nocapture argument may still |
1570 | // temporary store the nocapture argument's value in a temporary memory |
1571 | // location if that memory location doesn't escape. Or it may pass a |
1572 | // nocapture value to other functions as long as they don't capture it. |
1573 | if (isEscapeSource(V: O1) && AAQI.CI->isNotCapturedBefore( |
1574 | Object: O2, I: dyn_cast<Instruction>(Val: O1), /*OrAt*/ true)) |
1575 | return AliasResult::NoAlias; |
1576 | if (isEscapeSource(V: O2) && AAQI.CI->isNotCapturedBefore( |
1577 | Object: O1, I: dyn_cast<Instruction>(Val: O2), /*OrAt*/ true)) |
1578 | return AliasResult::NoAlias; |
1579 | } |
1580 | |
1581 | // If the size of one access is larger than the entire object on the other |
1582 | // side, then we know such behavior is undefined and can assume no alias. |
1583 | bool NullIsValidLocation = NullPointerIsDefined(F: &F); |
1584 | if ((isObjectSmallerThan( |
1585 | V: O2, Size: getMinimalExtentFrom(V: *V1, LocSize: V1Size, DL, NullIsValidLoc: NullIsValidLocation), DL, |
1586 | TLI, NullIsValidLoc: NullIsValidLocation)) || |
1587 | (isObjectSmallerThan( |
1588 | V: O1, Size: getMinimalExtentFrom(V: *V2, LocSize: V2Size, DL, NullIsValidLoc: NullIsValidLocation), DL, |
1589 | TLI, NullIsValidLoc: NullIsValidLocation))) |
1590 | return AliasResult::NoAlias; |
1591 | |
1592 | if (EnableSeparateStorageAnalysis) { |
1593 | for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V: O1)) { |
1594 | if (!Elem || Elem.Index == AssumptionCache::ExprResultIdx) |
1595 | continue; |
1596 | |
1597 | AssumeInst *Assume = cast<AssumeInst>(Val&: Elem); |
1598 | OperandBundleUse OBU = Assume->getOperandBundleAt(Index: Elem.Index); |
1599 | if (OBU.getTagName() == "separate_storage" ) { |
1600 | assert(OBU.Inputs.size() == 2); |
1601 | const Value *Hint1 = OBU.Inputs[0].get(); |
1602 | const Value *Hint2 = OBU.Inputs[1].get(); |
1603 | // This is often a no-op; instcombine rewrites this for us. No-op |
1604 | // getUnderlyingObject calls are fast, though. |
1605 | const Value *HintO1 = getUnderlyingObject(V: Hint1); |
1606 | const Value *HintO2 = getUnderlyingObject(V: Hint2); |
1607 | |
1608 | DominatorTree *DT = getDT(AAQI); |
1609 | auto ValidAssumeForPtrContext = [&](const Value *Ptr) { |
1610 | if (const Instruction *PtrI = dyn_cast<Instruction>(Val: Ptr)) { |
1611 | return isValidAssumeForContext(I: Assume, CxtI: PtrI, DT, |
1612 | /* AllowEphemerals */ true); |
1613 | } |
1614 | if (const Argument *PtrA = dyn_cast<Argument>(Val: Ptr)) { |
1615 | const Instruction *FirstI = |
1616 | &*PtrA->getParent()->getEntryBlock().begin(); |
1617 | return isValidAssumeForContext(I: Assume, CxtI: FirstI, DT, |
1618 | /* AllowEphemerals */ true); |
1619 | } |
1620 | return false; |
1621 | }; |
1622 | |
1623 | if ((O1 == HintO1 && O2 == HintO2) || (O1 == HintO2 && O2 == HintO1)) { |
1624 | // Note that we go back to V1 and V2 for the |
1625 | // ValidAssumeForPtrContext checks; they're dominated by O1 and O2, |
1626 | // so strictly more assumptions are valid for them. |
1627 | if ((CtxI && isValidAssumeForContext(I: Assume, CxtI: CtxI, DT, |
1628 | /* AllowEphemerals */ true)) || |
1629 | ValidAssumeForPtrContext(V1) || ValidAssumeForPtrContext(V2)) { |
1630 | return AliasResult::NoAlias; |
1631 | } |
1632 | } |
1633 | } |
1634 | } |
1635 | } |
1636 | |
1637 | // If one the accesses may be before the accessed pointer, canonicalize this |
1638 | // by using unknown after-pointer sizes for both accesses. This is |
1639 | // equivalent, because regardless of which pointer is lower, one of them |
1640 | // will always came after the other, as long as the underlying objects aren't |
1641 | // disjoint. We do this so that the rest of BasicAA does not have to deal |
1642 | // with accesses before the base pointer, and to improve cache utilization by |
1643 | // merging equivalent states. |
1644 | if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) { |
1645 | V1Size = LocationSize::afterPointer(); |
1646 | V2Size = LocationSize::afterPointer(); |
1647 | } |
1648 | |
1649 | // FIXME: If this depth limit is hit, then we may cache sub-optimal results |
1650 | // for recursive queries. For this reason, this limit is chosen to be large |
1651 | // enough to be very rarely hit, while still being small enough to avoid |
1652 | // stack overflows. |
1653 | if (AAQI.Depth >= 512) |
1654 | return AliasResult::MayAlias; |
1655 | |
1656 | // Check the cache before climbing up use-def chains. This also terminates |
1657 | // otherwise infinitely recursive queries. Include MayBeCrossIteration in the |
1658 | // cache key, because some cases where MayBeCrossIteration==false returns |
1659 | // MustAlias or NoAlias may become MayAlias under MayBeCrossIteration==true. |
1660 | AAQueryInfo::LocPair Locs({V1, V1Size, AAQI.MayBeCrossIteration}, |
1661 | {V2, V2Size, AAQI.MayBeCrossIteration}); |
1662 | const bool Swapped = V1 > V2; |
1663 | if (Swapped) |
1664 | std::swap(a&: Locs.first, b&: Locs.second); |
1665 | const auto &Pair = AAQI.AliasCache.try_emplace( |
1666 | Key: Locs, Args: AAQueryInfo::CacheEntry{.Result: AliasResult::NoAlias, .NumAssumptionUses: 0}); |
1667 | if (!Pair.second) { |
1668 | auto &Entry = Pair.first->second; |
1669 | if (!Entry.isDefinitive()) { |
1670 | // Remember that we used an assumption. |
1671 | ++Entry.NumAssumptionUses; |
1672 | ++AAQI.NumAssumptionUses; |
1673 | } |
1674 | // Cache contains sorted {V1,V2} pairs but we should return original order. |
1675 | auto Result = Entry.Result; |
1676 | Result.swap(DoSwap: Swapped); |
1677 | return Result; |
1678 | } |
1679 | |
1680 | int OrigNumAssumptionUses = AAQI.NumAssumptionUses; |
1681 | unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size(); |
1682 | AliasResult Result = |
1683 | aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2); |
1684 | |
1685 | auto It = AAQI.AliasCache.find(Val: Locs); |
1686 | assert(It != AAQI.AliasCache.end() && "Must be in cache" ); |
1687 | auto &Entry = It->second; |
1688 | |
1689 | // Check whether a NoAlias assumption has been used, but disproven. |
1690 | bool AssumptionDisproven = |
1691 | Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias; |
1692 | if (AssumptionDisproven) |
1693 | Result = AliasResult::MayAlias; |
1694 | |
1695 | // This is a definitive result now, when considered as a root query. |
1696 | AAQI.NumAssumptionUses -= Entry.NumAssumptionUses; |
1697 | Entry.Result = Result; |
1698 | // Cache contains sorted {V1,V2} pairs. |
1699 | Entry.Result.swap(DoSwap: Swapped); |
1700 | Entry.NumAssumptionUses = -1; |
1701 | |
1702 | // If the assumption has been disproven, remove any results that may have |
1703 | // been based on this assumption. Do this after the Entry updates above to |
1704 | // avoid iterator invalidation. |
1705 | if (AssumptionDisproven) |
1706 | while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults) |
1707 | AAQI.AliasCache.erase(Val: AAQI.AssumptionBasedResults.pop_back_val()); |
1708 | |
1709 | // The result may still be based on assumptions higher up in the chain. |
1710 | // Remember it, so it can be purged from the cache later. |
1711 | if (OrigNumAssumptionUses != AAQI.NumAssumptionUses && |
1712 | Result != AliasResult::MayAlias) |
1713 | AAQI.AssumptionBasedResults.push_back(Elt: Locs); |
1714 | return Result; |
1715 | } |
1716 | |
1717 | AliasResult BasicAAResult::aliasCheckRecursive( |
1718 | const Value *V1, LocationSize V1Size, |
1719 | const Value *V2, LocationSize V2Size, |
1720 | AAQueryInfo &AAQI, const Value *O1, const Value *O2) { |
1721 | if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(Val: V1)) { |
1722 | AliasResult Result = aliasGEP(GEP1: GV1, V1Size, V2, V2Size, UnderlyingV1: O1, UnderlyingV2: O2, AAQI); |
1723 | if (Result != AliasResult::MayAlias) |
1724 | return Result; |
1725 | } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(Val: V2)) { |
1726 | AliasResult Result = aliasGEP(GEP1: GV2, V1Size: V2Size, V2: V1, V2Size: V1Size, UnderlyingV1: O2, UnderlyingV2: O1, AAQI); |
1727 | Result.swap(); |
1728 | if (Result != AliasResult::MayAlias) |
1729 | return Result; |
1730 | } |
1731 | |
1732 | if (const PHINode *PN = dyn_cast<PHINode>(Val: V1)) { |
1733 | AliasResult Result = aliasPHI(PN, PNSize: V1Size, V2, V2Size, AAQI); |
1734 | if (Result != AliasResult::MayAlias) |
1735 | return Result; |
1736 | } else if (const PHINode *PN = dyn_cast<PHINode>(Val: V2)) { |
1737 | AliasResult Result = aliasPHI(PN, PNSize: V2Size, V2: V1, V2Size: V1Size, AAQI); |
1738 | Result.swap(); |
1739 | if (Result != AliasResult::MayAlias) |
1740 | return Result; |
1741 | } |
1742 | |
1743 | if (const SelectInst *S1 = dyn_cast<SelectInst>(Val: V1)) { |
1744 | AliasResult Result = aliasSelect(SI: S1, SISize: V1Size, V2, V2Size, AAQI); |
1745 | if (Result != AliasResult::MayAlias) |
1746 | return Result; |
1747 | } else if (const SelectInst *S2 = dyn_cast<SelectInst>(Val: V2)) { |
1748 | AliasResult Result = aliasSelect(SI: S2, SISize: V2Size, V2: V1, V2Size: V1Size, AAQI); |
1749 | Result.swap(); |
1750 | if (Result != AliasResult::MayAlias) |
1751 | return Result; |
1752 | } |
1753 | |
1754 | // If both pointers are pointing into the same object and one of them |
1755 | // accesses the entire object, then the accesses must overlap in some way. |
1756 | if (O1 == O2) { |
1757 | bool NullIsValidLocation = NullPointerIsDefined(F: &F); |
1758 | if (V1Size.isPrecise() && V2Size.isPrecise() && |
1759 | (isObjectSize(V: O1, Size: V1Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation) || |
1760 | isObjectSize(V: O2, Size: V2Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation))) |
1761 | return AliasResult::PartialAlias; |
1762 | } |
1763 | |
1764 | return AliasResult::MayAlias; |
1765 | } |
1766 | |
1767 | /// Check whether two Values can be considered equivalent. |
1768 | /// |
1769 | /// If the values may come from different cycle iterations, this will also |
1770 | /// check that the values are not part of cycle. We have to do this because we |
1771 | /// are looking through phi nodes, that is we say |
1772 | /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). |
1773 | bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, |
1774 | const Value *V2, |
1775 | const AAQueryInfo &AAQI) { |
1776 | if (V != V2) |
1777 | return false; |
1778 | |
1779 | if (!AAQI.MayBeCrossIteration) |
1780 | return true; |
1781 | |
1782 | // Non-instructions and instructions in the entry block cannot be part of |
1783 | // a loop. |
1784 | const Instruction *Inst = dyn_cast<Instruction>(Val: V); |
1785 | if (!Inst || Inst->getParent()->isEntryBlock()) |
1786 | return true; |
1787 | |
1788 | return isNotInCycle(I: Inst, DT: getDT(AAQI), /*LI*/ nullptr); |
1789 | } |
1790 | |
1791 | /// Computes the symbolic difference between two de-composed GEPs. |
1792 | void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP, |
1793 | const DecomposedGEP &SrcGEP, |
1794 | const AAQueryInfo &AAQI) { |
1795 | DestGEP.Offset -= SrcGEP.Offset; |
1796 | for (const VariableGEPIndex &Src : SrcGEP.VarIndices) { |
1797 | // Find V in Dest. This is N^2, but pointer indices almost never have more |
1798 | // than a few variable indexes. |
1799 | bool Found = false; |
1800 | for (auto I : enumerate(First&: DestGEP.VarIndices)) { |
1801 | VariableGEPIndex &Dest = I.value(); |
1802 | if ((!isValueEqualInPotentialCycles(V: Dest.Val.V, V2: Src.Val.V, AAQI) && |
1803 | !areBothVScale(V1: Dest.Val.V, V2: Src.Val.V)) || |
1804 | !Dest.Val.hasSameCastsAs(Other: Src.Val)) |
1805 | continue; |
1806 | |
1807 | // Normalize IsNegated if we're going to lose the NSW flag anyway. |
1808 | if (Dest.IsNegated) { |
1809 | Dest.Scale = -Dest.Scale; |
1810 | Dest.IsNegated = false; |
1811 | Dest.IsNSW = false; |
1812 | } |
1813 | |
1814 | // If we found it, subtract off Scale V's from the entry in Dest. If it |
1815 | // goes to zero, remove the entry. |
1816 | if (Dest.Scale != Src.Scale) { |
1817 | Dest.Scale -= Src.Scale; |
1818 | Dest.IsNSW = false; |
1819 | } else { |
1820 | DestGEP.VarIndices.erase(CI: DestGEP.VarIndices.begin() + I.index()); |
1821 | } |
1822 | Found = true; |
1823 | break; |
1824 | } |
1825 | |
1826 | // If we didn't consume this entry, add it to the end of the Dest list. |
1827 | if (!Found) { |
1828 | VariableGEPIndex Entry = {.Val: Src.Val, .Scale: Src.Scale, .CxtI: Src.CxtI, .IsNSW: Src.IsNSW, |
1829 | /* IsNegated */ true}; |
1830 | DestGEP.VarIndices.push_back(Elt: Entry); |
1831 | } |
1832 | } |
1833 | } |
1834 | |
1835 | bool BasicAAResult::constantOffsetHeuristic(const DecomposedGEP &GEP, |
1836 | LocationSize MaybeV1Size, |
1837 | LocationSize MaybeV2Size, |
1838 | AssumptionCache *AC, |
1839 | DominatorTree *DT, |
1840 | const AAQueryInfo &AAQI) { |
1841 | if (GEP.VarIndices.size() != 2 || !MaybeV1Size.hasValue() || |
1842 | !MaybeV2Size.hasValue()) |
1843 | return false; |
1844 | |
1845 | const uint64_t V1Size = MaybeV1Size.getValue(); |
1846 | const uint64_t V2Size = MaybeV2Size.getValue(); |
1847 | |
1848 | const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1]; |
1849 | |
1850 | if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Other: Var1.Val) || |
1851 | !Var0.hasNegatedScaleOf(Other: Var1) || |
1852 | Var0.Val.V->getType() != Var1.Val.V->getType()) |
1853 | return false; |
1854 | |
1855 | // We'll strip off the Extensions of Var0 and Var1 and do another round |
1856 | // of GetLinearExpression decomposition. In the example above, if Var0 |
1857 | // is zext(%x + 1) we should get V1 == %x and V1Offset == 1. |
1858 | |
1859 | LinearExpression E0 = |
1860 | GetLinearExpression(Val: CastedValue(Var0.Val.V), DL, Depth: 0, AC, DT); |
1861 | LinearExpression E1 = |
1862 | GetLinearExpression(Val: CastedValue(Var1.Val.V), DL, Depth: 0, AC, DT); |
1863 | if (E0.Scale != E1.Scale || !E0.Val.hasSameCastsAs(Other: E1.Val) || |
1864 | !isValueEqualInPotentialCycles(V: E0.Val.V, V2: E1.Val.V, AAQI)) |
1865 | return false; |
1866 | |
1867 | // We have a hit - Var0 and Var1 only differ by a constant offset! |
1868 | |
1869 | // If we've been sext'ed then zext'd the maximum difference between Var0 and |
1870 | // Var1 is possible to calculate, but we're just interested in the absolute |
1871 | // minimum difference between the two. The minimum distance may occur due to |
1872 | // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so |
1873 | // the minimum distance between %i and %i + 5 is 3. |
1874 | APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff; |
1875 | MinDiff = APIntOps::umin(A: MinDiff, B: Wrapped); |
1876 | APInt MinDiffBytes = |
1877 | MinDiff.zextOrTrunc(width: Var0.Scale.getBitWidth()) * Var0.Scale.abs(); |
1878 | |
1879 | // We can't definitely say whether GEP1 is before or after V2 due to wrapping |
1880 | // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other |
1881 | // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and |
1882 | // V2Size can fit in the MinDiffBytes gap. |
1883 | return MinDiffBytes.uge(RHS: V1Size + GEP.Offset.abs()) && |
1884 | MinDiffBytes.uge(RHS: V2Size + GEP.Offset.abs()); |
1885 | } |
1886 | |
1887 | //===----------------------------------------------------------------------===// |
1888 | // BasicAliasAnalysis Pass |
1889 | //===----------------------------------------------------------------------===// |
1890 | |
1891 | AnalysisKey BasicAA::Key; |
1892 | |
1893 | BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { |
1894 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F); |
1895 | auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F); |
1896 | auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F); |
1897 | return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT); |
1898 | } |
1899 | |
1900 | BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { |
1901 | initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
1902 | } |
1903 | |
1904 | char BasicAAWrapperPass::ID = 0; |
1905 | |
1906 | void BasicAAWrapperPass::anchor() {} |
1907 | |
1908 | INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa" , |
1909 | "Basic Alias Analysis (stateless AA impl)" , true, true) |
1910 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
1911 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
1912 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
1913 | INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa" , |
1914 | "Basic Alias Analysis (stateless AA impl)" , true, true) |
1915 | |
1916 | FunctionPass *llvm::createBasicAAWrapperPass() { |
1917 | return new BasicAAWrapperPass(); |
1918 | } |
1919 | |
1920 | bool BasicAAWrapperPass::runOnFunction(Function &F) { |
1921 | auto &ACT = getAnalysis<AssumptionCacheTracker>(); |
1922 | auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); |
1923 | auto &DTWP = getAnalysis<DominatorTreeWrapperPass>(); |
1924 | |
1925 | Result.reset(p: new BasicAAResult(F.getParent()->getDataLayout(), F, |
1926 | TLIWP.getTLI(F), ACT.getAssumptionCache(F), |
1927 | &DTWP.getDomTree())); |
1928 | |
1929 | return false; |
1930 | } |
1931 | |
1932 | void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
1933 | AU.setPreservesAll(); |
1934 | AU.addRequiredTransitive<AssumptionCacheTracker>(); |
1935 | AU.addRequiredTransitive<DominatorTreeWrapperPass>(); |
1936 | AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>(); |
1937 | } |
1938 | |