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 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
570 | bool IgnoreLocals = false); |
571 | ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2, |
572 | AAQueryInfo &AAQIP); |
573 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
574 | AAQueryInfo &AAQI); |
575 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
576 | AAQueryInfo &AAQI); |
577 | ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, |
578 | AAQueryInfo &AAQI); |
579 | ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, |
580 | AAQueryInfo &AAQI); |
581 | ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, |
582 | AAQueryInfo &AAQI); |
583 | ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, |
584 | AAQueryInfo &AAQI); |
585 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
586 | const MemoryLocation &Loc, AAQueryInfo &AAQI); |
587 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, |
588 | AAQueryInfo &AAQI); |
589 | ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, |
590 | AAQueryInfo &AAQI); |
591 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, |
592 | AAQueryInfo &AAQI); |
593 | ModRefInfo getModRefInfo(const Instruction *I, |
594 | const std::optional<MemoryLocation> &OptLoc, |
595 | AAQueryInfo &AAQIP); |
596 | ModRefInfo callCapturesBefore(const Instruction *I, |
597 | const MemoryLocation &MemLoc, DominatorTree *DT, |
598 | AAQueryInfo &AAQIP); |
599 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); |
600 | |
601 | private: |
602 | class Concept; |
603 | |
604 | template <typename T> class Model; |
605 | |
606 | friend class AAResultBase; |
607 | |
608 | const TargetLibraryInfo &TLI; |
609 | |
610 | std::vector<std::unique_ptr<Concept>> AAs; |
611 | |
612 | std::vector<AnalysisKey *> AADeps; |
613 | |
614 | friend class BatchAAResults; |
615 | }; |
616 | |
617 | /// This class is a wrapper over an AAResults, and it is intended to be used |
618 | /// only when there are no IR changes inbetween queries. BatchAAResults is |
619 | /// reusing the same `AAQueryInfo` to preserve the state across queries, |
620 | /// esentially making AA work in "batch mode". The internal state cannot be |
621 | /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, |
622 | /// or create a new BatchAAResults. |
623 | class BatchAAResults { |
624 | AAResults &AA; |
625 | AAQueryInfo AAQI; |
626 | SimpleCaptureInfo SimpleCI; |
627 | |
628 | public: |
629 | BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {} |
630 | BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {} |
631 | |
632 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
633 | return AA.alias(LocA, LocB, AAQI); |
634 | } |
635 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { |
636 | return isNoModRef(MRI: AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals: OrLocal)); |
637 | } |
638 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, |
639 | bool IgnoreLocals = false) { |
640 | return AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals); |
641 | } |
642 | ModRefInfo getModRefInfo(const Instruction *I, |
643 | const std::optional<MemoryLocation> &OptLoc) { |
644 | return AA.getModRefInfo(I, OptLoc, AAQIP&: AAQI); |
645 | } |
646 | ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2) { |
647 | return AA.getModRefInfo(I, Call2, AAQIP&: AAQI); |
648 | } |
649 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
650 | return AA.getArgModRefInfo(Call, ArgIdx); |
651 | } |
652 | MemoryEffects getMemoryEffects(const CallBase *Call) { |
653 | return AA.getMemoryEffects(Call, AAQI); |
654 | } |
655 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
656 | return alias(LocA, LocB) == AliasResult::MustAlias; |
657 | } |
658 | bool isMustAlias(const Value *V1, const Value *V2) { |
659 | return alias(LocA: MemoryLocation(V1, LocationSize::precise(Value: 1)), |
660 | LocB: MemoryLocation(V2, LocationSize::precise(Value: 1))) == |
661 | AliasResult::MustAlias; |
662 | } |
663 | ModRefInfo callCapturesBefore(const Instruction *I, |
664 | const MemoryLocation &MemLoc, |
665 | DominatorTree *DT) { |
666 | return AA.callCapturesBefore(I, MemLoc, DT, AAQIP&: AAQI); |
667 | } |
668 | |
669 | /// Assume that values may come from different cycle iterations. |
670 | void enableCrossIterationMode() { |
671 | AAQI.MayBeCrossIteration = true; |
672 | } |
673 | |
674 | /// Disable the use of the dominator tree during alias analysis queries. |
675 | void disableDominatorTree() { AAQI.UseDominatorTree = false; } |
676 | }; |
677 | |
678 | /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis |
679 | /// pointer or reference. |
680 | using AliasAnalysis = AAResults; |
681 | |
682 | /// A private abstract base class describing the concept of an individual alias |
683 | /// analysis implementation. |
684 | /// |
685 | /// This interface is implemented by any \c Model instantiation. It is also the |
686 | /// interface which a type used to instantiate the model must provide. |
687 | /// |
688 | /// All of these methods model methods by the same name in the \c |
689 | /// AAResults class. Only differences and specifics to how the |
690 | /// implementations are called are documented here. |
691 | class AAResults::Concept { |
692 | public: |
693 | virtual ~Concept() = 0; |
694 | |
695 | //===--------------------------------------------------------------------===// |
696 | /// \name Alias Queries |
697 | /// @{ |
698 | |
699 | /// The main low level interface to the alias analysis implementation. |
700 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
701 | /// each other. This is the interface that must be implemented by specific |
702 | /// alias analysis implementations. |
703 | virtual AliasResult alias(const MemoryLocation &LocA, |
704 | const MemoryLocation &LocB, AAQueryInfo &AAQI, |
705 | const Instruction *CtxI) = 0; |
706 | |
707 | /// @} |
708 | //===--------------------------------------------------------------------===// |
709 | /// \name Simple mod/ref information |
710 | /// @{ |
711 | |
712 | /// Returns a bitmask that should be unconditionally applied to the ModRef |
713 | /// info of a memory location. This allows us to eliminate Mod and/or Ref from |
714 | /// the ModRef info based on the knowledge that the memory location points to |
715 | /// constant and/or locally-invariant memory. |
716 | virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, |
717 | AAQueryInfo &AAQI, |
718 | bool IgnoreLocals) = 0; |
719 | |
720 | /// Get the ModRef info associated with a pointer argument of a callsite. The |
721 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
722 | /// that these bits do not necessarily account for the overall behavior of |
723 | /// the function, but rather only provide additional per-argument |
724 | /// information. |
725 | virtual ModRefInfo getArgModRefInfo(const CallBase *Call, |
726 | unsigned ArgIdx) = 0; |
727 | |
728 | /// Return the behavior of the given call site. |
729 | virtual MemoryEffects getMemoryEffects(const CallBase *Call, |
730 | AAQueryInfo &AAQI) = 0; |
731 | |
732 | /// Return the behavior when calling the given function. |
733 | virtual MemoryEffects getMemoryEffects(const Function *F) = 0; |
734 | |
735 | /// getModRefInfo (for call sites) - Return information about whether |
736 | /// a particular call site modifies or reads the specified memory location. |
737 | virtual ModRefInfo getModRefInfo(const CallBase *Call, |
738 | const MemoryLocation &Loc, |
739 | AAQueryInfo &AAQI) = 0; |
740 | |
741 | /// Return information about whether two call sites may refer to the same set |
742 | /// of memory locations. See the AA documentation for details: |
743 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
744 | virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
745 | AAQueryInfo &AAQI) = 0; |
746 | |
747 | /// @} |
748 | }; |
749 | |
750 | /// A private class template which derives from \c Concept and wraps some other |
751 | /// type. |
752 | /// |
753 | /// This models the concept by directly forwarding each interface point to the |
754 | /// wrapped type which must implement a compatible interface. This provides |
755 | /// a type erased binding. |
756 | template <typename AAResultT> class AAResults::Model final : public Concept { |
757 | AAResultT &Result; |
758 | |
759 | public: |
760 | explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {} |
761 | ~Model() override = default; |
762 | |
763 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
764 | AAQueryInfo &AAQI, const Instruction *CtxI) override { |
765 | return Result.alias(LocA, LocB, AAQI, CtxI); |
766 | } |
767 | |
768 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
769 | bool IgnoreLocals) override { |
770 | return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals); |
771 | } |
772 | |
773 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { |
774 | return Result.getArgModRefInfo(Call, ArgIdx); |
775 | } |
776 | |
777 | MemoryEffects getMemoryEffects(const CallBase *Call, |
778 | AAQueryInfo &AAQI) override { |
779 | return Result.getMemoryEffects(Call, AAQI); |
780 | } |
781 | |
782 | MemoryEffects getMemoryEffects(const Function *F) override { |
783 | return Result.getMemoryEffects(F); |
784 | } |
785 | |
786 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
787 | AAQueryInfo &AAQI) override { |
788 | return Result.getModRefInfo(Call, Loc, AAQI); |
789 | } |
790 | |
791 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
792 | AAQueryInfo &AAQI) override { |
793 | return Result.getModRefInfo(Call1, Call2, AAQI); |
794 | } |
795 | }; |
796 | |
797 | /// A base class to help implement the function alias analysis results concept. |
798 | /// |
799 | /// Because of the nature of many alias analysis implementations, they often |
800 | /// only implement a subset of the interface. This base class will attempt to |
801 | /// implement the remaining portions of the interface in terms of simpler forms |
802 | /// of the interface where possible, and otherwise provide conservatively |
803 | /// correct fallback implementations. |
804 | /// |
805 | /// Implementors of an alias analysis should derive from this class, and then |
806 | /// override specific methods that they wish to customize. There is no need to |
807 | /// use virtual anywhere. |
808 | class AAResultBase { |
809 | protected: |
810 | explicit AAResultBase() = default; |
811 | |
812 | // Provide all the copy and move constructors so that derived types aren't |
813 | // constrained. |
814 | AAResultBase(const AAResultBase &Arg) {} |
815 | AAResultBase(AAResultBase &&Arg) {} |
816 | |
817 | public: |
818 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
819 | AAQueryInfo &AAQI, const Instruction *I) { |
820 | return AliasResult::MayAlias; |
821 | } |
822 | |
823 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
824 | bool IgnoreLocals) { |
825 | return ModRefInfo::ModRef; |
826 | } |
827 | |
828 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
829 | return ModRefInfo::ModRef; |
830 | } |
831 | |
832 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) { |
833 | return MemoryEffects::unknown(); |
834 | } |
835 | |
836 | MemoryEffects getMemoryEffects(const Function *F) { |
837 | return MemoryEffects::unknown(); |
838 | } |
839 | |
840 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
841 | AAQueryInfo &AAQI) { |
842 | return ModRefInfo::ModRef; |
843 | } |
844 | |
845 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
846 | AAQueryInfo &AAQI) { |
847 | return ModRefInfo::ModRef; |
848 | } |
849 | }; |
850 | |
851 | /// Return true if this pointer is returned by a noalias function. |
852 | bool isNoAliasCall(const Value *V); |
853 | |
854 | /// Return true if this pointer refers to a distinct and identifiable object. |
855 | /// This returns true for: |
856 | /// Global Variables and Functions (but not Global Aliases) |
857 | /// Allocas |
858 | /// ByVal and NoAlias Arguments |
859 | /// NoAlias returns (e.g. calls to malloc) |
860 | /// |
861 | bool isIdentifiedObject(const Value *V); |
862 | |
863 | /// Return true if V is umabigously identified at the function-level. |
864 | /// Different IdentifiedFunctionLocals can't alias. |
865 | /// Further, an IdentifiedFunctionLocal can not alias with any function |
866 | /// arguments other than itself, which is not necessarily true for |
867 | /// IdentifiedObjects. |
868 | bool isIdentifiedFunctionLocal(const Value *V); |
869 | |
870 | /// Returns true if the pointer is one which would have been considered an |
871 | /// escape by isNonEscapingLocalObject. |
872 | bool isEscapeSource(const Value *V); |
873 | |
874 | /// Return true if Object memory is not visible after an unwind, in the sense |
875 | /// that program semantics cannot depend on Object containing any particular |
876 | /// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set |
877 | /// to true, then the memory is only not visible if the object has not been |
878 | /// captured prior to the unwind. Otherwise it is not visible even if captured. |
879 | bool isNotVisibleOnUnwind(const Value *Object, |
880 | bool &RequiresNoCaptureBeforeUnwind); |
881 | |
882 | /// Return true if the Object is writable, in the sense that any location based |
883 | /// on this pointer that can be loaded can also be stored to without trapping. |
884 | /// Additionally, at the point Object is declared, stores can be introduced |
885 | /// without data races. At later points, this is only the case if the pointer |
886 | /// can not escape to a different thread. |
887 | /// |
888 | /// If ExplicitlyDereferenceableOnly is set to true, this property only holds |
889 | /// for the part of Object that is explicitly marked as dereferenceable, e.g. |
890 | /// using the dereferenceable(N) attribute. It does not necessarily hold for |
891 | /// parts that are only known to be dereferenceable due to the presence of |
892 | /// loads. |
893 | bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly); |
894 | |
895 | /// A manager for alias analyses. |
896 | /// |
897 | /// This class can have analyses registered with it and when run, it will run |
898 | /// all of them and aggregate their results into single AA results interface |
899 | /// that dispatches across all of the alias analysis results available. |
900 | /// |
901 | /// Note that the order in which analyses are registered is very significant. |
902 | /// That is the order in which the results will be aggregated and queried. |
903 | /// |
904 | /// This manager effectively wraps the AnalysisManager for registering alias |
905 | /// analyses. When you register your alias analysis with this manager, it will |
906 | /// ensure the analysis itself is registered with its AnalysisManager. |
907 | /// |
908 | /// The result of this analysis is only invalidated if one of the particular |
909 | /// aggregated AA results end up being invalidated. This removes the need to |
910 | /// explicitly preserve the results of `AAManager`. Note that analyses should no |
911 | /// longer be registered once the `AAManager` is run. |
912 | class AAManager : public AnalysisInfoMixin<AAManager> { |
913 | public: |
914 | using Result = AAResults; |
915 | |
916 | /// Register a specific AA result. |
917 | template <typename AnalysisT> void registerFunctionAnalysis() { |
918 | ResultGetters.push_back(Elt: &getFunctionAAResultImpl<AnalysisT>); |
919 | } |
920 | |
921 | /// Register a specific AA result. |
922 | template <typename AnalysisT> void registerModuleAnalysis() { |
923 | ResultGetters.push_back(Elt: &getModuleAAResultImpl<AnalysisT>); |
924 | } |
925 | |
926 | Result run(Function &F, FunctionAnalysisManager &AM); |
927 | |
928 | private: |
929 | friend AnalysisInfoMixin<AAManager>; |
930 | |
931 | static AnalysisKey Key; |
932 | |
933 | SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, |
934 | AAResults &AAResults), |
935 | 4> ResultGetters; |
936 | |
937 | template <typename AnalysisT> |
938 | static void getFunctionAAResultImpl(Function &F, |
939 | FunctionAnalysisManager &AM, |
940 | AAResults &AAResults) { |
941 | AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); |
942 | AAResults.addAADependencyID(ID: AnalysisT::ID()); |
943 | } |
944 | |
945 | template <typename AnalysisT> |
946 | static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, |
947 | AAResults &AAResults) { |
948 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F); |
949 | if (auto *R = |
950 | MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { |
951 | AAResults.addAAResult(*R); |
952 | MAMProxy |
953 | .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); |
954 | } |
955 | } |
956 | }; |
957 | |
958 | /// A wrapper pass to provide the legacy pass manager access to a suitably |
959 | /// prepared AAResults object. |
960 | class AAResultsWrapperPass : public FunctionPass { |
961 | std::unique_ptr<AAResults> AAR; |
962 | |
963 | public: |
964 | static char ID; |
965 | |
966 | AAResultsWrapperPass(); |
967 | |
968 | AAResults &getAAResults() { return *AAR; } |
969 | const AAResults &getAAResults() const { return *AAR; } |
970 | |
971 | bool runOnFunction(Function &F) override; |
972 | |
973 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
974 | }; |
975 | |
976 | /// A wrapper pass for external alias analyses. This just squirrels away the |
977 | /// callback used to run any analyses and register their results. |
978 | struct ExternalAAWrapperPass : ImmutablePass { |
979 | using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; |
980 | |
981 | CallbackT CB; |
982 | |
983 | static char ID; |
984 | |
985 | ExternalAAWrapperPass(); |
986 | |
987 | explicit ExternalAAWrapperPass(CallbackT CB); |
988 | |
989 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
990 | AU.setPreservesAll(); |
991 | } |
992 | }; |
993 | |
994 | /// A wrapper pass around a callback which can be used to populate the |
995 | /// AAResults in the AAResultsWrapperPass from an external AA. |
996 | /// |
997 | /// The callback provided here will be used each time we prepare an AAResults |
998 | /// object, and will receive a reference to the function wrapper pass, the |
999 | /// function, and the AAResults object to populate. This should be used when |
1000 | /// setting up a custom pass pipeline to inject a hook into the AA results. |
1001 | ImmutablePass *createExternalAAWrapperPass( |
1002 | std::function<void(Pass &, Function &, AAResults &)> Callback); |
1003 | |
1004 | } // end namespace llvm |
1005 | |
1006 | #endif // LLVM_ANALYSIS_ALIASANALYSIS_H |
1007 | |