1 | //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- 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 | // This file defines the generic AliasAnalysis interface, which is used as the |
10 | // common interface used by all clients of alias analysis information, and |
11 | // implemented by all alias analysis implementations. Mod/Ref information is |
12 | // also captured by this interface. |
13 | // |
14 | // Implementations of this interface must implement the various virtual methods, |
15 | // which automatically provides functionality for the entire suite of client |
16 | // APIs. |
17 | // |
18 | // This API identifies memory regions with the MemoryLocation class. The pointer |
19 | // component specifies the base memory address of the region. The Size specifies |
20 | // the maximum size (in address units) of the memory region, or |
21 | // MemoryLocation::UnknownSize if the size is not known. The TBAA tag |
22 | // identifies the "type" of the memory reference; see the |
23 | // TypeBasedAliasAnalysis class for details. |
24 | // |
25 | // Some non-obvious details include: |
26 | // - Pointers that point to two completely different objects in memory never |
27 | // alias, regardless of the value of the Size component. |
28 | // - NoAlias doesn't imply inequal pointers. The most obvious example of this |
29 | // is two pointers to constant memory. Even if they are equal, constant |
30 | // memory is never stored to, so there will never be any dependencies. |
31 | // In this and other situations, the pointers may be both NoAlias and |
32 | // MustAlias at the same time. The current API can only return one result, |
33 | // though this is rarely a problem in practice. |
34 | // |
35 | //===----------------------------------------------------------------------===// |
36 | |
37 | #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H |
38 | #define LLVM_ANALYSIS_ALIASANALYSIS_H |
39 | |
40 | #include "llvm/ADT/DenseMap.h" |
41 | #include "llvm/ADT/Sequence.h" |
42 | #include "llvm/ADT/SmallVector.h" |
43 | #include "llvm/Analysis/MemoryLocation.h" |
44 | #include "llvm/IR/PassManager.h" |
45 | #include "llvm/Pass.h" |
46 | #include "llvm/Support/ModRef.h" |
47 | #include <cstdint> |
48 | #include <functional> |
49 | #include <memory> |
50 | #include <optional> |
51 | #include <vector> |
52 | |
53 | namespace llvm { |
54 | |
55 | class AnalysisUsage; |
56 | class AtomicCmpXchgInst; |
57 | class BasicBlock; |
58 | class CatchPadInst; |
59 | class CatchReturnInst; |
60 | class DominatorTree; |
61 | class FenceInst; |
62 | class Function; |
63 | class LoopInfo; |
64 | class PreservedAnalyses; |
65 | class TargetLibraryInfo; |
66 | class Value; |
67 | |
68 | /// The possible results of an alias query. |
69 | /// |
70 | /// These results are always computed between two MemoryLocation objects as |
71 | /// a query to some alias analysis. |
72 | /// |
73 | /// Note that these are unscoped enumerations because we would like to support |
74 | /// implicitly testing a result for the existence of any possible aliasing with |
75 | /// a conversion to bool, but an "enum class" doesn't support this. The |
76 | /// canonical names from the literature are suffixed and unique anyways, and so |
77 | /// they serve as global constants in LLVM for these results. |
78 | /// |
79 | /// See docs/AliasAnalysis.html for more information on the specific meanings |
80 | /// of these values. |
81 | class AliasResult { |
82 | private: |
83 | static const int OffsetBits = 23; |
84 | static const int AliasBits = 8; |
85 | static_assert(AliasBits + 1 + OffsetBits <= 32, |
86 | "AliasResult size is intended to be 4 bytes!" ); |
87 | |
88 | unsigned int Alias : AliasBits; |
89 | unsigned int HasOffset : 1; |
90 | signed int Offset : OffsetBits; |
91 | |
92 | public: |
93 | enum Kind : uint8_t { |
94 | /// The two locations do not alias at all. |
95 | /// |
96 | /// This value is arranged to convert to false, while all other values |
97 | /// convert to true. This allows a boolean context to convert the result to |
98 | /// a binary flag indicating whether there is the possibility of aliasing. |
99 | NoAlias = 0, |
100 | /// The two locations may or may not alias. This is the least precise |
101 | /// result. |
102 | MayAlias, |
103 | /// The two locations alias, but only due to a partial overlap. |
104 | PartialAlias, |
105 | /// The two locations precisely alias each other. |
106 | MustAlias, |
107 | }; |
108 | static_assert(MustAlias < (1 << AliasBits), |
109 | "Not enough bit field size for the enum!" ); |
110 | |
111 | explicit AliasResult() = delete; |
112 | constexpr AliasResult(const Kind &Alias) |
113 | : Alias(Alias), HasOffset(false), Offset(0) {} |
114 | |
115 | operator Kind() const { return static_cast<Kind>(Alias); } |
116 | |
117 | bool operator==(const AliasResult &Other) const { |
118 | return Alias == Other.Alias && HasOffset == Other.HasOffset && |
119 | Offset == Other.Offset; |
120 | } |
121 | bool operator!=(const AliasResult &Other) const { return !(*this == Other); } |
122 | |
123 | bool operator==(Kind K) const { return Alias == K; } |
124 | bool operator!=(Kind K) const { return !(*this == K); } |
125 | |
126 | constexpr bool hasOffset() const { return HasOffset; } |
127 | constexpr int32_t getOffset() const { |
128 | assert(HasOffset && "No offset!" ); |
129 | return Offset; |
130 | } |
131 | void setOffset(int32_t NewOffset) { |
132 | if (isInt<OffsetBits>(x: NewOffset)) { |
133 | HasOffset = true; |
134 | Offset = NewOffset; |
135 | } |
136 | } |
137 | |
138 | /// Helper for processing AliasResult for swapped memory location pairs. |
139 | void swap(bool DoSwap = true) { |
140 | if (DoSwap && hasOffset()) |
141 | setOffset(-getOffset()); |
142 | } |
143 | }; |
144 | |
145 | static_assert(sizeof(AliasResult) == 4, |
146 | "AliasResult size is intended to be 4 bytes!" ); |
147 | |
148 | /// << operator for AliasResult. |
149 | raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); |
150 | |
151 | /// Virtual base class for providers of capture information. |
152 | struct CaptureInfo { |
153 | virtual ~CaptureInfo() = 0; |
154 | |
155 | /// Check whether Object is not captured before instruction I. If OrAt is |
156 | /// true, captures by instruction I itself are also considered. |
157 | /// |
158 | /// If I is nullptr, then captures at any point will be considered. |
159 | virtual bool isNotCapturedBefore(const Value *Object, const Instruction *I, |
160 | bool OrAt) = 0; |
161 | }; |
162 | |
163 | /// Context-free CaptureInfo provider, which computes and caches whether an |
164 | /// object is captured in the function at all, but does not distinguish whether |
165 | /// it was captured before or after the context instruction. |
166 | class SimpleCaptureInfo final : public CaptureInfo { |
167 | SmallDenseMap<const Value *, bool, 8> IsCapturedCache; |
168 | |
169 | public: |
170 | bool isNotCapturedBefore(const Value *Object, const Instruction *I, |
171 | bool OrAt) override; |
172 | }; |
173 | |
174 | /// Context-sensitive CaptureInfo provider, which computes and caches the |
175 | /// earliest common dominator closure of all captures. It provides a good |
176 | /// approximation to a precise "captures before" analysis. |
177 | class EarliestEscapeInfo final : public CaptureInfo { |
178 | DominatorTree &DT; |
179 | const LoopInfo *LI; |
180 | |
181 | /// Map from identified local object to an instruction before which it does |
182 | /// not escape, or nullptr if it never escapes. The "earliest" instruction |
183 | /// may be a conservative approximation, e.g. the first instruction in the |
184 | /// function is always a legal choice. |
185 | DenseMap<const Value *, Instruction *> EarliestEscapes; |
186 | |
187 | /// Reverse map from instruction to the objects it is the earliest escape for. |
188 | /// This is used for cache invalidation purposes. |
189 | DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj; |
190 | |
191 | public: |
192 | EarliestEscapeInfo(DominatorTree &DT, const LoopInfo *LI = nullptr) |
193 | : DT(DT), LI(LI) {} |
194 | |
195 | bool isNotCapturedBefore(const Value *Object, const Instruction *I, |
196 | bool OrAt) override; |
197 | |
198 | void removeInstruction(Instruction *I); |
199 | }; |
200 | |
201 | /// Cache key for BasicAA results. It only includes the pointer and size from |
202 | /// MemoryLocation, as BasicAA is AATags independent. Additionally, it includes |
203 | /// the value of MayBeCrossIteration, which may affect BasicAA results. |
204 | struct AACacheLoc { |
205 | using PtrTy = PointerIntPair<const Value *, 1, bool>; |
206 | PtrTy Ptr; |
207 | LocationSize Size; |
208 | |
209 | AACacheLoc(PtrTy Ptr, LocationSize Size) : Ptr(Ptr), Size(Size) {} |
210 | AACacheLoc(const Value *Ptr, LocationSize Size, bool MayBeCrossIteration) |
211 | : Ptr(Ptr, MayBeCrossIteration), Size(Size) {} |
212 | }; |
213 | |
214 | template <> struct DenseMapInfo<AACacheLoc> { |
215 | static inline AACacheLoc getEmptyKey() { |
216 | return {DenseMapInfo<AACacheLoc::PtrTy>::getEmptyKey(), |
217 | DenseMapInfo<LocationSize>::getEmptyKey()}; |
218 | } |
219 | static inline AACacheLoc getTombstoneKey() { |
220 | return {DenseMapInfo<AACacheLoc::PtrTy>::getTombstoneKey(), |
221 | DenseMapInfo<LocationSize>::getTombstoneKey()}; |
222 | } |
223 | static unsigned getHashValue(const AACacheLoc &Val) { |
224 | return DenseMapInfo<AACacheLoc::PtrTy>::getHashValue(V: Val.Ptr) ^ |
225 | DenseMapInfo<LocationSize>::getHashValue(Val: Val.Size); |
226 | } |
227 | static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { |
228 | return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; |
229 | } |
230 | }; |
231 | |
232 | class AAResults; |
233 | |
234 | /// This class stores info we want to provide to or retain within an alias |
235 | /// query. By default, the root query is stateless and starts with a freshly |
236 | /// constructed info object. Specific alias analyses can use this query info to |
237 | /// store per-query state that is important for recursive or nested queries to |
238 | /// avoid recomputing. To enable preserving this state across multiple queries |
239 | /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. |
240 | /// The information stored in an `AAQueryInfo` is currently limitted to the |
241 | /// caches used by BasicAA, but can further be extended to fit other AA needs. |
242 | class AAQueryInfo { |
243 | public: |
244 | using LocPair = std::pair<AACacheLoc, AACacheLoc>; |
245 | struct CacheEntry { |
246 | AliasResult Result; |
247 | /// Number of times a NoAlias assumption has been used. |
248 | /// 0 for assumptions that have not been used, -1 for definitive results. |
249 | int NumAssumptionUses; |
250 | /// Whether this is a definitive (non-assumption) result. |
251 | bool isDefinitive() const { return NumAssumptionUses < 0; } |
252 | }; |
253 | |
254 | // Alias analysis result aggregration using which this query is performed. |
255 | // Can be used to perform recursive queries. |
256 | AAResults &AAR; |
257 | |
258 | using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; |
259 | AliasCacheT AliasCache; |
260 | |
261 | CaptureInfo *CI; |
262 | |
263 | /// Query depth used to distinguish recursive queries. |
264 | unsigned Depth = 0; |
265 | |
266 | /// How many active NoAlias assumption uses there are. |
267 | int NumAssumptionUses = 0; |
268 | |
269 | /// Location pairs for which an assumption based result is currently stored. |
270 | /// Used to remove all potentially incorrect results from the cache if an |
271 | /// assumption is disproven. |
272 | SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; |
273 | |
274 | /// Tracks whether the accesses may be on different cycle iterations. |
275 | /// |
276 | /// When interpret "Value" pointer equality as value equality we need to make |
277 | /// sure that the "Value" is not part of a cycle. Otherwise, two uses could |
278 | /// come from different "iterations" of a cycle and see different values for |
279 | /// the same "Value" pointer. |
280 | /// |
281 | /// The following example shows the problem: |
282 | /// %p = phi(%alloca1, %addr2) |
283 | /// %l = load %ptr |
284 | /// %addr1 = gep, %alloca2, 0, %l |
285 | /// %addr2 = gep %alloca2, 0, (%l + 1) |
286 | /// alias(%p, %addr1) -> MayAlias ! |
287 | /// store %l, ... |
288 | bool MayBeCrossIteration = false; |
289 | |
290 | /// Whether alias analysis is allowed to use the dominator tree, for use by |
291 | /// passes that lazily update the DT while performing AA queries. |
292 | bool UseDominatorTree = true; |
293 | |
294 | AAQueryInfo(AAResults &AAR, CaptureInfo *CI) : AAR(AAR), CI(CI) {} |
295 | }; |
296 | |
297 | /// AAQueryInfo that uses SimpleCaptureInfo. |
298 | class SimpleAAQueryInfo : public AAQueryInfo { |
299 | SimpleCaptureInfo CI; |
300 | |
301 | public: |
302 | SimpleAAQueryInfo(AAResults &AAR) : AAQueryInfo(AAR, &CI) {} |
303 | }; |
304 | |
305 | class BatchAAResults; |
306 | |
307 | class AAResults { |
308 | public: |
309 | // Make these results default constructable and movable. We have to spell |
310 | // these out because MSVC won't synthesize them. |
311 | AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} |
312 | AAResults(AAResults &&Arg); |
313 | ~AAResults(); |
314 | |
315 | /// Register a specific AA result. |
316 | template <typename AAResultT> void addAAResult(AAResultT &AAResult) { |
317 | // FIXME: We should use a much lighter weight system than the usual |
318 | // polymorphic pattern because we don't own AAResult. It should |
319 | // ideally involve two pointers and no separate allocation. |
320 | AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); |
321 | } |
322 | |
323 | /// Register a function analysis ID that the results aggregation depends on. |
324 | /// |
325 | /// This is used in the new pass manager to implement the invalidation logic |
326 | /// where we must invalidate the results aggregation if any of our component |
327 | /// analyses become invalid. |
328 | void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(x: ID); } |
329 | |
330 | /// Handle invalidation events in the new pass manager. |
331 | /// |
332 | /// The aggregation is invalidated if any of the underlying analyses is |
333 | /// invalidated. |
334 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
335 | FunctionAnalysisManager::Invalidator &Inv); |
336 | |
337 | //===--------------------------------------------------------------------===// |
338 | /// \name Alias Queries |
339 | /// @{ |
340 | |
341 | /// The main low level interface to the alias analysis implementation. |
342 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
343 | /// each other. This is the interface that must be implemented by specific |
344 | /// alias analysis implementations. |
345 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); |
346 | |
347 | /// A convenience wrapper around the primary \c alias interface. |
348 | AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, |
349 | LocationSize V2Size) { |
350 | return alias(LocA: MemoryLocation(V1, V1Size), LocB: MemoryLocation(V2, V2Size)); |
351 | } |
352 | |
353 | /// A convenience wrapper around the primary \c alias interface. |
354 | AliasResult alias(const Value *V1, const Value *V2) { |
355 | return alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: V1), |
356 | LocB: MemoryLocation::getBeforeOrAfter(Ptr: V2)); |
357 | } |
358 | |
359 | /// A trivial helper function to check to see if the specified pointers are |
360 | /// no-alias. |
361 | bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
362 | return alias(LocA, LocB) == AliasResult::NoAlias; |
363 | } |
364 | |
365 | /// A convenience wrapper around the \c isNoAlias helper interface. |
366 | bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, |
367 | LocationSize V2Size) { |
368 | return isNoAlias(LocA: MemoryLocation(V1, V1Size), LocB: MemoryLocation(V2, V2Size)); |
369 | } |
370 | |
371 | /// A convenience wrapper around the \c isNoAlias helper interface. |
372 | bool isNoAlias(const Value *V1, const Value *V2) { |
373 | return isNoAlias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: V1), |
374 | LocB: MemoryLocation::getBeforeOrAfter(Ptr: V2)); |
375 | } |
376 | |
377 | /// A trivial helper function to check to see if the specified pointers are |
378 | /// must-alias. |
379 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
380 | return alias(LocA, LocB) == AliasResult::MustAlias; |
381 | } |
382 | |
383 | /// A convenience wrapper around the \c isMustAlias helper interface. |
384 | bool isMustAlias(const Value *V1, const Value *V2) { |
385 | return alias(V1, V1Size: LocationSize::precise(Value: 1), V2, V2Size: LocationSize::precise(Value: 1)) == |
386 | AliasResult::MustAlias; |
387 | } |
388 | |
389 | /// Checks whether the given location points to constant memory, or if |
390 | /// \p OrLocal is true whether it points to a local alloca. |
391 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { |
392 | return isNoModRef(MRI: getModRefInfoMask(Loc, IgnoreLocals: OrLocal)); |
393 | } |
394 | |
395 | /// A convenience wrapper around the primary \c pointsToConstantMemory |
396 | /// interface. |
397 | bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { |
398 | return pointsToConstantMemory(Loc: MemoryLocation::getBeforeOrAfter(Ptr: P), OrLocal); |
399 | } |
400 | |
401 | /// @} |
402 | //===--------------------------------------------------------------------===// |
403 | /// \name Simple mod/ref information |
404 | /// @{ |
405 | |
406 | /// Returns a bitmask that should be unconditionally applied to the ModRef |
407 | /// info of a memory location. This allows us to eliminate Mod and/or Ref |
408 | /// from the ModRef info based on the knowledge that the memory location |
409 | /// points to constant and/or locally-invariant memory. |
410 | /// |
411 | /// If IgnoreLocals is true, then this method returns NoModRef for memory |
412 | /// that points to a local alloca. |
413 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, |
414 | bool IgnoreLocals = false); |
415 | |
416 | /// A convenience wrapper around the primary \c getModRefInfoMask |
417 | /// interface. |
418 | ModRefInfo getModRefInfoMask(const Value *P, bool IgnoreLocals = false) { |
419 | return getModRefInfoMask(Loc: MemoryLocation::getBeforeOrAfter(Ptr: P), IgnoreLocals); |
420 | } |
421 | |
422 | /// Get the ModRef info associated with a pointer argument of a call. The |
423 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
424 | /// that these bits do not necessarily account for the overall behavior of |
425 | /// the function, but rather only provide additional per-argument |
426 | /// information. |
427 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
428 | |
429 | /// Return the behavior of the given call site. |
430 | MemoryEffects getMemoryEffects(const CallBase *Call); |
431 | |
432 | /// Return the behavior when calling the given function. |
433 | MemoryEffects getMemoryEffects(const Function *F); |
434 | |
435 | /// Checks if the specified call is known to never read or write memory. |
436 | /// |
437 | /// Note that if the call only reads from known-constant memory, it is also |
438 | /// legal to return true. Also, calls that unwind the stack are legal for |
439 | /// this predicate. |
440 | /// |
441 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
442 | /// without worrying about aliasing properties, and many calls have this |
443 | /// property (e.g. calls to 'sin' and 'cos'). |
444 | /// |
445 | /// This property corresponds to the GCC 'const' attribute. |
446 | bool doesNotAccessMemory(const CallBase *Call) { |
447 | return getMemoryEffects(Call).doesNotAccessMemory(); |
448 | } |
449 | |
450 | /// Checks if the specified function is known to never read or write memory. |
451 | /// |
452 | /// Note that if the function only reads from known-constant memory, it is |
453 | /// also legal to return true. Also, function that unwind the stack are legal |
454 | /// for this predicate. |
455 | /// |
456 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
457 | /// to such functions without worrying about aliasing properties, and many |
458 | /// functions have this property (e.g. 'sin' and 'cos'). |
459 | /// |
460 | /// This property corresponds to the GCC 'const' attribute. |
461 | bool doesNotAccessMemory(const Function *F) { |
462 | return getMemoryEffects(F).doesNotAccessMemory(); |
463 | } |
464 | |
465 | /// Checks if the specified call is known to only read from non-volatile |
466 | /// memory (or not access memory at all). |
467 | /// |
468 | /// Calls that unwind the stack are legal for this predicate. |
469 | /// |
470 | /// This property allows many common optimizations to be performed in the |
471 | /// absence of interfering store instructions, such as CSE of strlen calls. |
472 | /// |
473 | /// This property corresponds to the GCC 'pure' attribute. |
474 | bool onlyReadsMemory(const CallBase *Call) { |
475 | return getMemoryEffects(Call).onlyReadsMemory(); |
476 | } |
477 | |
478 | /// Checks if the specified function is known to only read from non-volatile |
479 | /// memory (or not access memory at all). |
480 | /// |
481 | /// Functions that unwind the stack are legal for this predicate. |
482 | /// |
483 | /// This property allows many common optimizations to be performed in the |
484 | /// absence of interfering store instructions, such as CSE of strlen calls. |
485 | /// |
486 | /// This property corresponds to the GCC 'pure' attribute. |
487 | bool onlyReadsMemory(const Function *F) { |
488 | return getMemoryEffects(F).onlyReadsMemory(); |
489 | } |
490 | |
491 | /// Check whether or not an instruction may read or write the optionally |
492 | /// specified memory location. |
493 | /// |
494 | /// |
495 | /// An instruction that doesn't read or write memory may be trivially LICM'd |
496 | /// for example. |
497 | /// |
498 | /// For function calls, this delegates to the alias-analysis specific |
499 | /// call-site mod-ref behavior queries. Otherwise it delegates to the specific |
500 | /// helpers above. |
501 | ModRefInfo getModRefInfo(const Instruction *I, |
502 | const std::optional<MemoryLocation> &OptLoc) { |
503 | SimpleAAQueryInfo AAQIP(*this); |
504 | return getModRefInfo(I, OptLoc, AAQIP); |
505 | } |
506 | |
507 | /// A convenience wrapper for constructing the memory location. |
508 | ModRefInfo getModRefInfo(const Instruction *I, const Value *P, |
509 | LocationSize Size) { |
510 | return getModRefInfo(I, OptLoc: MemoryLocation(P, Size)); |
511 | } |
512 | |
513 | /// Return information about whether a call and an instruction may refer to |
514 | /// the same memory locations. |
515 | ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call); |
516 | |
517 | /// Return information about whether a particular call site modifies |
518 | /// or reads the specified memory location \p MemLoc before instruction \p I |
519 | /// in a BasicBlock. |
520 | ModRefInfo callCapturesBefore(const Instruction *I, |
521 | const MemoryLocation &MemLoc, |
522 | DominatorTree *DT) { |
523 | SimpleAAQueryInfo AAQIP(*this); |
524 | return callCapturesBefore(I, MemLoc, DT, AAQIP); |
525 | } |
526 | |
527 | /// A convenience wrapper to synthesize a memory location. |
528 | ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, |
529 | LocationSize Size, DominatorTree *DT) { |
530 | return callCapturesBefore(I, MemLoc: MemoryLocation(P, Size), DT); |
531 | } |
532 | |
533 | /// @} |
534 | //===--------------------------------------------------------------------===// |
535 | /// \name Higher level methods for querying mod/ref information. |
536 | /// @{ |
537 | |
538 | /// Check if it is possible for execution of the specified basic block to |
539 | /// modify the location Loc. |
540 | bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); |
541 | |
542 | /// A convenience wrapper synthesizing a memory location. |
543 | bool canBasicBlockModify(const BasicBlock &BB, const Value *P, |
544 | LocationSize Size) { |
545 | return canBasicBlockModify(BB, Loc: MemoryLocation(P, Size)); |
546 | } |
547 | |
548 | /// Check if it is possible for the execution of the specified instructions |
549 | /// to mod\ref (according to the mode) the location Loc. |
550 | /// |
551 | /// The instructions to consider are all of the instructions in the range of |
552 | /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. |
553 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
554 | const MemoryLocation &Loc, |
555 | const ModRefInfo Mode); |
556 | |
557 | /// A convenience wrapper synthesizing a memory location. |
558 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
559 | const Value *Ptr, LocationSize Size, |
560 | const ModRefInfo Mode) { |
561 | return canInstructionRangeModRef(I1, I2, Loc: MemoryLocation(Ptr, Size), Mode); |
562 | } |
563 | |
564 | // CtxI can be nullptr, in which case the query is whether or not the aliasing |
565 | // relationship holds through the entire function. |
566 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
567 | AAQueryInfo &AAQI, const Instruction *CtxI = nullptr); |
568 | |
569 | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
570 | bool OrLocal = false); |
571 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
572 | bool IgnoreLocals = false); |
573 | ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2, |
574 | AAQueryInfo &AAQIP); |
575 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
576 | AAQueryInfo &AAQI); |
577 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
578 | AAQueryInfo &AAQI); |
579 | ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, |
580 | AAQueryInfo &AAQI); |
581 | ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, |
582 | AAQueryInfo &AAQI); |
583 | ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, |
584 | AAQueryInfo &AAQI); |
585 | ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, |
586 | AAQueryInfo &AAQI); |
587 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
588 | const MemoryLocation &Loc, AAQueryInfo &AAQI); |
589 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, |
590 | AAQueryInfo &AAQI); |
591 | ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, |
592 | AAQueryInfo &AAQI); |
593 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, |
594 | AAQueryInfo &AAQI); |
595 | ModRefInfo getModRefInfo(const Instruction *I, |
596 | const std::optional<MemoryLocation> &OptLoc, |
597 | AAQueryInfo &AAQIP); |
598 | ModRefInfo callCapturesBefore(const Instruction *I, |
599 | const MemoryLocation &MemLoc, DominatorTree *DT, |
600 | AAQueryInfo &AAQIP); |
601 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); |
602 | |
603 | private: |
604 | class Concept; |
605 | |
606 | template <typename T> class Model; |
607 | |
608 | friend class AAResultBase; |
609 | |
610 | const TargetLibraryInfo &TLI; |
611 | |
612 | std::vector<std::unique_ptr<Concept>> AAs; |
613 | |
614 | std::vector<AnalysisKey *> AADeps; |
615 | |
616 | friend class BatchAAResults; |
617 | }; |
618 | |
619 | /// This class is a wrapper over an AAResults, and it is intended to be used |
620 | /// only when there are no IR changes inbetween queries. BatchAAResults is |
621 | /// reusing the same `AAQueryInfo` to preserve the state across queries, |
622 | /// esentially making AA work in "batch mode". The internal state cannot be |
623 | /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, |
624 | /// or create a new BatchAAResults. |
625 | class BatchAAResults { |
626 | AAResults &AA; |
627 | AAQueryInfo AAQI; |
628 | SimpleCaptureInfo SimpleCI; |
629 | |
630 | public: |
631 | BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {} |
632 | BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {} |
633 | |
634 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
635 | return AA.alias(LocA, LocB, AAQI); |
636 | } |
637 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { |
638 | return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); |
639 | } |
640 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, |
641 | bool IgnoreLocals = false) { |
642 | return AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals); |
643 | } |
644 | ModRefInfo getModRefInfo(const Instruction *I, |
645 | const std::optional<MemoryLocation> &OptLoc) { |
646 | return AA.getModRefInfo(I, OptLoc, AAQIP&: AAQI); |
647 | } |
648 | ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2) { |
649 | return AA.getModRefInfo(I, Call2, AAQIP&: AAQI); |
650 | } |
651 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
652 | return AA.getArgModRefInfo(Call, ArgIdx); |
653 | } |
654 | MemoryEffects getMemoryEffects(const CallBase *Call) { |
655 | return AA.getMemoryEffects(Call, AAQI); |
656 | } |
657 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
658 | return alias(LocA, LocB) == AliasResult::MustAlias; |
659 | } |
660 | bool isMustAlias(const Value *V1, const Value *V2) { |
661 | return alias(LocA: MemoryLocation(V1, LocationSize::precise(Value: 1)), |
662 | LocB: MemoryLocation(V2, LocationSize::precise(Value: 1))) == |
663 | AliasResult::MustAlias; |
664 | } |
665 | ModRefInfo callCapturesBefore(const Instruction *I, |
666 | const MemoryLocation &MemLoc, |
667 | DominatorTree *DT) { |
668 | return AA.callCapturesBefore(I, MemLoc, DT, AAQIP&: AAQI); |
669 | } |
670 | |
671 | /// Assume that values may come from different cycle iterations. |
672 | void enableCrossIterationMode() { |
673 | AAQI.MayBeCrossIteration = true; |
674 | } |
675 | |
676 | /// Disable the use of the dominator tree during alias analysis queries. |
677 | void disableDominatorTree() { AAQI.UseDominatorTree = false; } |
678 | }; |
679 | |
680 | /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis |
681 | /// pointer or reference. |
682 | using AliasAnalysis = AAResults; |
683 | |
684 | /// A private abstract base class describing the concept of an individual alias |
685 | /// analysis implementation. |
686 | /// |
687 | /// This interface is implemented by any \c Model instantiation. It is also the |
688 | /// interface which a type used to instantiate the model must provide. |
689 | /// |
690 | /// All of these methods model methods by the same name in the \c |
691 | /// AAResults class. Only differences and specifics to how the |
692 | /// implementations are called are documented here. |
693 | class AAResults::Concept { |
694 | public: |
695 | virtual ~Concept() = 0; |
696 | |
697 | //===--------------------------------------------------------------------===// |
698 | /// \name Alias Queries |
699 | /// @{ |
700 | |
701 | /// The main low level interface to the alias analysis implementation. |
702 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
703 | /// each other. This is the interface that must be implemented by specific |
704 | /// alias analysis implementations. |
705 | virtual AliasResult alias(const MemoryLocation &LocA, |
706 | const MemoryLocation &LocB, AAQueryInfo &AAQI, |
707 | const Instruction *CtxI) = 0; |
708 | |
709 | /// @} |
710 | //===--------------------------------------------------------------------===// |
711 | /// \name Simple mod/ref information |
712 | /// @{ |
713 | |
714 | /// Returns a bitmask that should be unconditionally applied to the ModRef |
715 | /// info of a memory location. This allows us to eliminate Mod and/or Ref from |
716 | /// the ModRef info based on the knowledge that the memory location points to |
717 | /// constant and/or locally-invariant memory. |
718 | virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, |
719 | AAQueryInfo &AAQI, |
720 | bool IgnoreLocals) = 0; |
721 | |
722 | /// Get the ModRef info associated with a pointer argument of a callsite. The |
723 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
724 | /// that these bits do not necessarily account for the overall behavior of |
725 | /// the function, but rather only provide additional per-argument |
726 | /// information. |
727 | virtual ModRefInfo getArgModRefInfo(const CallBase *Call, |
728 | unsigned ArgIdx) = 0; |
729 | |
730 | /// Return the behavior of the given call site. |
731 | virtual MemoryEffects getMemoryEffects(const CallBase *Call, |
732 | AAQueryInfo &AAQI) = 0; |
733 | |
734 | /// Return the behavior when calling the given function. |
735 | virtual MemoryEffects getMemoryEffects(const Function *F) = 0; |
736 | |
737 | /// getModRefInfo (for call sites) - Return information about whether |
738 | /// a particular call site modifies or reads the specified memory location. |
739 | virtual ModRefInfo getModRefInfo(const CallBase *Call, |
740 | const MemoryLocation &Loc, |
741 | AAQueryInfo &AAQI) = 0; |
742 | |
743 | /// Return information about whether two call sites may refer to the same set |
744 | /// of memory locations. See the AA documentation for details: |
745 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
746 | virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
747 | AAQueryInfo &AAQI) = 0; |
748 | |
749 | /// @} |
750 | }; |
751 | |
752 | /// A private class template which derives from \c Concept and wraps some other |
753 | /// type. |
754 | /// |
755 | /// This models the concept by directly forwarding each interface point to the |
756 | /// wrapped type which must implement a compatible interface. This provides |
757 | /// a type erased binding. |
758 | template <typename AAResultT> class AAResults::Model final : public Concept { |
759 | AAResultT &Result; |
760 | |
761 | public: |
762 | explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {} |
763 | ~Model() override = default; |
764 | |
765 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
766 | AAQueryInfo &AAQI, const Instruction *CtxI) override { |
767 | return Result.alias(LocA, LocB, AAQI, CtxI); |
768 | } |
769 | |
770 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
771 | bool IgnoreLocals) override { |
772 | return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals); |
773 | } |
774 | |
775 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { |
776 | return Result.getArgModRefInfo(Call, ArgIdx); |
777 | } |
778 | |
779 | MemoryEffects getMemoryEffects(const CallBase *Call, |
780 | AAQueryInfo &AAQI) override { |
781 | return Result.getMemoryEffects(Call, AAQI); |
782 | } |
783 | |
784 | MemoryEffects getMemoryEffects(const Function *F) override { |
785 | return Result.getMemoryEffects(F); |
786 | } |
787 | |
788 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
789 | AAQueryInfo &AAQI) override { |
790 | return Result.getModRefInfo(Call, Loc, AAQI); |
791 | } |
792 | |
793 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
794 | AAQueryInfo &AAQI) override { |
795 | return Result.getModRefInfo(Call1, Call2, AAQI); |
796 | } |
797 | }; |
798 | |
799 | /// A base class to help implement the function alias analysis results concept. |
800 | /// |
801 | /// Because of the nature of many alias analysis implementations, they often |
802 | /// only implement a subset of the interface. This base class will attempt to |
803 | /// implement the remaining portions of the interface in terms of simpler forms |
804 | /// of the interface where possible, and otherwise provide conservatively |
805 | /// correct fallback implementations. |
806 | /// |
807 | /// Implementors of an alias analysis should derive from this class, and then |
808 | /// override specific methods that they wish to customize. There is no need to |
809 | /// use virtual anywhere. |
810 | class AAResultBase { |
811 | protected: |
812 | explicit AAResultBase() = default; |
813 | |
814 | // Provide all the copy and move constructors so that derived types aren't |
815 | // constrained. |
816 | AAResultBase(const AAResultBase &Arg) {} |
817 | AAResultBase(AAResultBase &&Arg) {} |
818 | |
819 | public: |
820 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
821 | AAQueryInfo &AAQI, const Instruction *I) { |
822 | return AliasResult::MayAlias; |
823 | } |
824 | |
825 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
826 | bool IgnoreLocals) { |
827 | return ModRefInfo::ModRef; |
828 | } |
829 | |
830 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
831 | return ModRefInfo::ModRef; |
832 | } |
833 | |
834 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) { |
835 | return MemoryEffects::unknown(); |
836 | } |
837 | |
838 | MemoryEffects getMemoryEffects(const Function *F) { |
839 | return MemoryEffects::unknown(); |
840 | } |
841 | |
842 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
843 | AAQueryInfo &AAQI) { |
844 | return ModRefInfo::ModRef; |
845 | } |
846 | |
847 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
848 | AAQueryInfo &AAQI) { |
849 | return ModRefInfo::ModRef; |
850 | } |
851 | }; |
852 | |
853 | /// Return true if this pointer is returned by a noalias function. |
854 | bool isNoAliasCall(const Value *V); |
855 | |
856 | /// Return true if this pointer refers to a distinct and identifiable object. |
857 | /// This returns true for: |
858 | /// Global Variables and Functions (but not Global Aliases) |
859 | /// Allocas |
860 | /// ByVal and NoAlias Arguments |
861 | /// NoAlias returns (e.g. calls to malloc) |
862 | /// |
863 | bool isIdentifiedObject(const Value *V); |
864 | |
865 | /// Return true if V is umabigously identified at the function-level. |
866 | /// Different IdentifiedFunctionLocals can't alias. |
867 | /// Further, an IdentifiedFunctionLocal can not alias with any function |
868 | /// arguments other than itself, which is not necessarily true for |
869 | /// IdentifiedObjects. |
870 | bool isIdentifiedFunctionLocal(const Value *V); |
871 | |
872 | /// Returns true if the pointer is one which would have been considered an |
873 | /// escape by isNonEscapingLocalObject. |
874 | bool isEscapeSource(const Value *V); |
875 | |
876 | /// Return true if Object memory is not visible after an unwind, in the sense |
877 | /// that program semantics cannot depend on Object containing any particular |
878 | /// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set |
879 | /// to true, then the memory is only not visible if the object has not been |
880 | /// captured prior to the unwind. Otherwise it is not visible even if captured. |
881 | bool isNotVisibleOnUnwind(const Value *Object, |
882 | bool &RequiresNoCaptureBeforeUnwind); |
883 | |
884 | /// Return true if the Object is writable, in the sense that any location based |
885 | /// on this pointer that can be loaded can also be stored to without trapping. |
886 | /// Additionally, at the point Object is declared, stores can be introduced |
887 | /// without data races. At later points, this is only the case if the pointer |
888 | /// can not escape to a different thread. |
889 | /// |
890 | /// If ExplicitlyDereferenceableOnly is set to true, this property only holds |
891 | /// for the part of Object that is explicitly marked as dereferenceable, e.g. |
892 | /// using the dereferenceable(N) attribute. It does not necessarily hold for |
893 | /// parts that are only known to be dereferenceable due to the presence of |
894 | /// loads. |
895 | bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly); |
896 | |
897 | /// A manager for alias analyses. |
898 | /// |
899 | /// This class can have analyses registered with it and when run, it will run |
900 | /// all of them and aggregate their results into single AA results interface |
901 | /// that dispatches across all of the alias analysis results available. |
902 | /// |
903 | /// Note that the order in which analyses are registered is very significant. |
904 | /// That is the order in which the results will be aggregated and queried. |
905 | /// |
906 | /// This manager effectively wraps the AnalysisManager for registering alias |
907 | /// analyses. When you register your alias analysis with this manager, it will |
908 | /// ensure the analysis itself is registered with its AnalysisManager. |
909 | /// |
910 | /// The result of this analysis is only invalidated if one of the particular |
911 | /// aggregated AA results end up being invalidated. This removes the need to |
912 | /// explicitly preserve the results of `AAManager`. Note that analyses should no |
913 | /// longer be registered once the `AAManager` is run. |
914 | class AAManager : public AnalysisInfoMixin<AAManager> { |
915 | public: |
916 | using Result = AAResults; |
917 | |
918 | /// Register a specific AA result. |
919 | template <typename AnalysisT> void registerFunctionAnalysis() { |
920 | ResultGetters.push_back(Elt: &getFunctionAAResultImpl<AnalysisT>); |
921 | } |
922 | |
923 | /// Register a specific AA result. |
924 | template <typename AnalysisT> void registerModuleAnalysis() { |
925 | ResultGetters.push_back(Elt: &getModuleAAResultImpl<AnalysisT>); |
926 | } |
927 | |
928 | Result run(Function &F, FunctionAnalysisManager &AM); |
929 | |
930 | private: |
931 | friend AnalysisInfoMixin<AAManager>; |
932 | |
933 | static AnalysisKey Key; |
934 | |
935 | SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, |
936 | AAResults &AAResults), |
937 | 4> ResultGetters; |
938 | |
939 | template <typename AnalysisT> |
940 | static void getFunctionAAResultImpl(Function &F, |
941 | FunctionAnalysisManager &AM, |
942 | AAResults &AAResults) { |
943 | AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); |
944 | AAResults.addAADependencyID(ID: AnalysisT::ID()); |
945 | } |
946 | |
947 | template <typename AnalysisT> |
948 | static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, |
949 | AAResults &AAResults) { |
950 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F); |
951 | if (auto *R = |
952 | MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { |
953 | AAResults.addAAResult(*R); |
954 | MAMProxy |
955 | .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); |
956 | } |
957 | } |
958 | }; |
959 | |
960 | /// A wrapper pass to provide the legacy pass manager access to a suitably |
961 | /// prepared AAResults object. |
962 | class AAResultsWrapperPass : public FunctionPass { |
963 | std::unique_ptr<AAResults> AAR; |
964 | |
965 | public: |
966 | static char ID; |
967 | |
968 | AAResultsWrapperPass(); |
969 | |
970 | AAResults &getAAResults() { return *AAR; } |
971 | const AAResults &getAAResults() const { return *AAR; } |
972 | |
973 | bool runOnFunction(Function &F) override; |
974 | |
975 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
976 | }; |
977 | |
978 | /// A wrapper pass for external alias analyses. This just squirrels away the |
979 | /// callback used to run any analyses and register their results. |
980 | struct ExternalAAWrapperPass : ImmutablePass { |
981 | using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; |
982 | |
983 | CallbackT CB; |
984 | |
985 | static char ID; |
986 | |
987 | ExternalAAWrapperPass(); |
988 | |
989 | explicit ExternalAAWrapperPass(CallbackT CB); |
990 | |
991 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
992 | AU.setPreservesAll(); |
993 | } |
994 | }; |
995 | |
996 | /// A wrapper pass around a callback which can be used to populate the |
997 | /// AAResults in the AAResultsWrapperPass from an external AA. |
998 | /// |
999 | /// The callback provided here will be used each time we prepare an AAResults |
1000 | /// object, and will receive a reference to the function wrapper pass, the |
1001 | /// function, and the AAResults object to populate. This should be used when |
1002 | /// setting up a custom pass pipeline to inject a hook into the AA results. |
1003 | ImmutablePass *createExternalAAWrapperPass( |
1004 | std::function<void(Pass &, Function &, AAResults &)> Callback); |
1005 | |
1006 | } // end namespace llvm |
1007 | |
1008 | #endif // LLVM_ANALYSIS_ALIASANALYSIS_H |
1009 | |