1 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the generic AliasAnalysis interface, which is used as the
11 // common interface used by all clients of alias analysis information, and
12 // implemented by all alias analysis implementations. Mod/Ref information is
13 // also captured by this interface.
15 // Implementations of this interface must implement the various virtual methods,
16 // which automatically provides functionality for the entire suite of client
19 // This API identifies memory regions with the MemoryLocation class. The pointer
20 // component specifies the base memory address of the region. The Size specifies
21 // the maximum size (in address units) of the memory region, or
22 // MemoryLocation::UnknownSize if the size is not known. The TBAA tag
23 // identifies the "type" of the memory reference; see the
24 // TypeBasedAliasAnalysis class for details.
26 // Some non-obvious details include:
27 // - Pointers that point to two completely different objects in memory never
28 // alias, regardless of the value of the Size component.
29 // - NoAlias doesn't imply inequal pointers. The most obvious example of this
30 // is two pointers to constant memory. Even if they are equal, constant
31 // memory is never stored to, so there will never be any dependencies.
32 // In this and other situations, the pointers may be both NoAlias and
33 // MustAlias at the same time. The current API can only return one result,
34 // though this is rarely a problem in practice.
36 //===----------------------------------------------------------------------===//
38 #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
39 #define LLVM_ANALYSIS_ALIASANALYSIS_H
41 #include "llvm/ADT/DenseMap.h"
42 #include "llvm/IR/CallSite.h"
43 #include "llvm/IR/Metadata.h"
44 #include "llvm/IR/PassManager.h"
45 #include "llvm/Analysis/MemoryLocation.h"
53 class TargetLibraryInfo;
56 class MemTransferInst;
59 class OrderedBasicBlock;
61 /// The possible results of an alias query.
63 /// These results are always computed between two MemoryLocation objects as
64 /// a query to some alias analysis.
66 /// Note that these are unscoped enumerations because we would like to support
67 /// implicitly testing a result for the existence of any possible aliasing with
68 /// a conversion to bool, but an "enum class" doesn't support this. The
69 /// canonical names from the literature are suffixed and unique anyways, and so
70 /// they serve as global constants in LLVM for these results.
72 /// See docs/AliasAnalysis.html for more information on the specific meanings
75 /// The two locations do not alias at all.
77 /// This value is arranged to convert to false, while all other values
78 /// convert to true. This allows a boolean context to convert the result to
79 /// a binary flag indicating whether there is the possibility of aliasing.
81 /// The two locations may or may not alias. This is the least precise result.
83 /// The two locations alias, but only due to a partial overlap.
85 /// The two locations precisely alias each other.
89 /// Flags indicating whether a memory access modifies or references memory.
91 /// This is no access at all, a modification, a reference, or both
92 /// a modification and a reference. These are specifically structured such that
93 /// they form a two bit matrix and bit-tests for 'mod' or 'ref' work with any
94 /// of the possible values.
96 /// The access neither references nor modifies the value stored in memory.
98 /// The access references the value stored in memory.
100 /// The access modifies the value stored in memory.
102 /// The access both references and modifies the value stored in memory.
103 MRI_ModRef = MRI_Ref | MRI_Mod
106 /// The locations at which a function might access memory.
108 /// These are primarily used in conjunction with the \c AccessKind bits to
109 /// describe both the nature of access and the locations of access for a
111 enum FunctionModRefLocation {
112 /// Base case is no access to memory.
114 /// Access to memory via argument pointers.
115 FMRL_ArgumentPointees = 4,
116 /// Access to any memory.
117 FMRL_Anywhere = 8 | FMRL_ArgumentPointees
120 /// Summary of how a function affects memory in the program.
122 /// Loads from constant globals are not considered memory accesses for this
123 /// interface. Also, functions may freely modify stack space local to their
124 /// invocation without having to report it through these interfaces.
125 enum FunctionModRefBehavior {
126 /// This function does not perform any non-local loads or stores to memory.
128 /// This property corresponds to the GCC 'const' attribute.
129 /// This property corresponds to the LLVM IR 'readnone' attribute.
130 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
131 FMRB_DoesNotAccessMemory = FMRL_Nowhere | MRI_NoModRef,
133 /// The only memory references in this function (if it has any) are
134 /// non-volatile loads from objects pointed to by its pointer-typed
135 /// arguments, with arbitrary offsets.
137 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
138 FMRB_OnlyReadsArgumentPointees = FMRL_ArgumentPointees | MRI_Ref,
140 /// The only memory references in this function (if it has any) are
141 /// non-volatile loads and stores from objects pointed to by its
142 /// pointer-typed arguments, with arbitrary offsets.
144 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
145 FMRB_OnlyAccessesArgumentPointees = FMRL_ArgumentPointees | MRI_ModRef,
147 /// This function does not perform any non-local stores or volatile loads,
148 /// but may read from any memory location.
150 /// This property corresponds to the GCC 'pure' attribute.
151 /// This property corresponds to the LLVM IR 'readonly' attribute.
152 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
153 FMRB_OnlyReadsMemory = FMRL_Anywhere | MRI_Ref,
155 /// This indicates that the function could not be classified into one of the
157 FMRB_UnknownModRefBehavior = FMRL_Anywhere | MRI_ModRef
162 // Make these results default constructable and movable. We have to spell
163 // these out because MSVC won't synthesize them.
165 AAResults(AAResults &&Arg);
166 AAResults &operator=(AAResults &&Arg);
169 /// Register a specific AA result.
170 template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
171 // FIXME: We should use a much lighter weight system than the usual
172 // polymorphic pattern because we don't own AAResult. It should
173 // ideally involve two pointers and no separate allocation.
174 AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
177 //===--------------------------------------------------------------------===//
178 /// \name Alias Queries
181 /// The main low level interface to the alias analysis implementation.
182 /// Returns an AliasResult indicating whether the two pointers are aliased to
183 /// each other. This is the interface that must be implemented by specific
184 /// alias analysis implementations.
185 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
187 /// A convenience wrapper around the primary \c alias interface.
188 AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2,
190 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
193 /// A convenience wrapper around the primary \c alias interface.
194 AliasResult alias(const Value *V1, const Value *V2) {
195 return alias(V1, MemoryLocation::UnknownSize, V2,
196 MemoryLocation::UnknownSize);
199 /// A trivial helper function to check to see if the specified pointers are
201 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
202 return alias(LocA, LocB) == NoAlias;
205 /// A convenience wrapper around the \c isNoAlias helper interface.
206 bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2,
208 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
211 /// A convenience wrapper around the \c isNoAlias helper interface.
212 bool isNoAlias(const Value *V1, const Value *V2) {
213 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
216 /// A trivial helper function to check to see if the specified pointers are
218 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
219 return alias(LocA, LocB) == MustAlias;
222 /// A convenience wrapper around the \c isMustAlias helper interface.
223 bool isMustAlias(const Value *V1, const Value *V2) {
224 return alias(V1, 1, V2, 1) == MustAlias;
227 /// Checks whether the given location points to constant memory, or if
228 /// \p OrLocal is true whether it points to a local alloca.
229 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
231 /// A convenience wrapper around the primary \c pointsToConstantMemory
233 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
234 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
238 //===--------------------------------------------------------------------===//
239 /// \name Simple mod/ref information
242 /// Get the ModRef info associated with a pointer argument of a callsite. The
243 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
244 /// that these bits do not necessarily account for the overall behavior of
245 /// the function, but rather only provide additional per-argument
247 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
249 /// Return the behavior of the given call site.
250 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
252 /// Return the behavior when calling the given function.
253 FunctionModRefBehavior getModRefBehavior(const Function *F);
255 /// Checks if the specified call is known to never read or write memory.
257 /// Note that if the call only reads from known-constant memory, it is also
258 /// legal to return true. Also, calls that unwind the stack are legal for
261 /// Many optimizations (such as CSE and LICM) can be performed on such calls
262 /// without worrying about aliasing properties, and many calls have this
263 /// property (e.g. calls to 'sin' and 'cos').
265 /// This property corresponds to the GCC 'const' attribute.
266 bool doesNotAccessMemory(ImmutableCallSite CS) {
267 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
270 /// Checks if the specified function is known to never read or write memory.
272 /// Note that if the function only reads from known-constant memory, it is
273 /// also legal to return true. Also, function that unwind the stack are legal
274 /// for this predicate.
276 /// Many optimizations (such as CSE and LICM) can be performed on such calls
277 /// to such functions without worrying about aliasing properties, and many
278 /// functions have this property (e.g. 'sin' and 'cos').
280 /// This property corresponds to the GCC 'const' attribute.
281 bool doesNotAccessMemory(const Function *F) {
282 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
285 /// Checks if the specified call is known to only read from non-volatile
286 /// memory (or not access memory at all).
288 /// Calls that unwind the stack are legal for this predicate.
290 /// This property allows many common optimizations to be performed in the
291 /// absence of interfering store instructions, such as CSE of strlen calls.
293 /// This property corresponds to the GCC 'pure' attribute.
294 bool onlyReadsMemory(ImmutableCallSite CS) {
295 return onlyReadsMemory(getModRefBehavior(CS));
298 /// Checks if the specified function is known to only read from non-volatile
299 /// memory (or not access memory at all).
301 /// Functions that unwind the stack are legal for this predicate.
303 /// This property allows many common optimizations to be performed in the
304 /// absence of interfering store instructions, such as CSE of strlen calls.
306 /// This property corresponds to the GCC 'pure' attribute.
307 bool onlyReadsMemory(const Function *F) {
308 return onlyReadsMemory(getModRefBehavior(F));
311 /// Checks if functions with the specified behavior are known to only read
312 /// from non-volatile memory (or not access memory at all).
313 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
314 return !(MRB & MRI_Mod);
317 /// Checks if functions with the specified behavior are known to read and
318 /// write at most from objects pointed to by their pointer-typed arguments
319 /// (with arbitrary offsets).
320 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
321 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
324 /// Checks if functions with the specified behavior are known to potentially
325 /// read or write from objects pointed to be their pointer-typed arguments
326 /// (with arbitrary offsets).
327 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
328 return (MRB & MRI_ModRef) && (MRB & FMRL_ArgumentPointees);
331 /// getModRefInfo (for call sites) - Return information about whether
332 /// a particular call site modifies or reads the specified memory location.
333 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
335 /// getModRefInfo (for call sites) - A convenience wrapper.
336 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
338 return getModRefInfo(CS, MemoryLocation(P, Size));
341 /// getModRefInfo (for calls) - Return information about whether
342 /// a particular call modifies or reads the specified memory location.
343 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
344 return getModRefInfo(ImmutableCallSite(C), Loc);
347 /// getModRefInfo (for calls) - A convenience wrapper.
348 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
349 return getModRefInfo(C, MemoryLocation(P, Size));
352 /// getModRefInfo (for invokes) - Return information about whether
353 /// a particular invoke modifies or reads the specified memory location.
354 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
355 return getModRefInfo(ImmutableCallSite(I), Loc);
358 /// getModRefInfo (for invokes) - A convenience wrapper.
359 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
360 return getModRefInfo(I, MemoryLocation(P, Size));
363 /// getModRefInfo (for loads) - Return information about whether
364 /// a particular load modifies or reads the specified memory location.
365 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
367 /// getModRefInfo (for loads) - A convenience wrapper.
368 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
369 return getModRefInfo(L, MemoryLocation(P, Size));
372 /// getModRefInfo (for stores) - Return information about whether
373 /// a particular store modifies or reads the specified memory location.
374 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
376 /// getModRefInfo (for stores) - A convenience wrapper.
377 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
378 return getModRefInfo(S, MemoryLocation(P, Size));
381 /// getModRefInfo (for fences) - Return information about whether
382 /// a particular store modifies or reads the specified memory location.
383 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
384 // Conservatively correct. (We could possibly be a bit smarter if
385 // Loc is a alloca that doesn't escape.)
389 /// getModRefInfo (for fences) - A convenience wrapper.
390 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
391 return getModRefInfo(S, MemoryLocation(P, Size));
394 /// getModRefInfo (for cmpxchges) - Return information about whether
395 /// a particular cmpxchg modifies or reads the specified memory location.
396 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
397 const MemoryLocation &Loc);
399 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
400 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
402 return getModRefInfo(CX, MemoryLocation(P, Size));
405 /// getModRefInfo (for atomicrmws) - Return information about whether
406 /// a particular atomicrmw modifies or reads the specified memory location.
407 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
409 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
410 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
412 return getModRefInfo(RMW, MemoryLocation(P, Size));
415 /// getModRefInfo (for va_args) - Return information about whether
416 /// a particular va_arg modifies or reads the specified memory location.
417 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
419 /// getModRefInfo (for va_args) - A convenience wrapper.
420 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
421 return getModRefInfo(I, MemoryLocation(P, Size));
424 /// Check whether or not an instruction may read or write memory (without
425 /// regard to a specific location).
427 /// For function calls, this delegates to the alias-analysis specific
428 /// call-site mod-ref behavior queries. Otherwise it delegates to the generic
429 /// mod ref information query without a location.
430 ModRefInfo getModRefInfo(const Instruction *I) {
431 if (auto CS = ImmutableCallSite(I)) {
432 auto MRB = getModRefBehavior(CS);
433 if (MRB & MRI_ModRef)
435 else if (MRB & MRI_Ref)
437 else if (MRB & MRI_Mod)
442 return getModRefInfo(I, MemoryLocation());
445 /// Check whether or not an instruction may read or write the specified
448 /// An instruction that doesn't read or write memory may be trivially LICM'd
451 /// This primarily delegates to specific helpers above.
452 ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
453 switch (I->getOpcode()) {
454 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
455 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
456 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
457 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
458 case Instruction::AtomicCmpXchg:
459 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
460 case Instruction::AtomicRMW:
461 return getModRefInfo((const AtomicRMWInst*)I, Loc);
462 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
463 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
469 /// A convenience wrapper for constructing the memory location.
470 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
472 return getModRefInfo(I, MemoryLocation(P, Size));
475 /// Return information about whether a call and an instruction may refer to
476 /// the same memory locations.
477 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
479 /// Return information about whether two call sites may refer to the same set
480 /// of memory locations. See the AA documentation for details:
481 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
482 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
484 /// \brief Return information about whether a particular call site modifies
485 /// or reads the specified memory location \p MemLoc before instruction \p I
486 /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
487 /// instruction ordering queries inside the BasicBlock containing \p I.
488 ModRefInfo callCapturesBefore(const Instruction *I,
489 const MemoryLocation &MemLoc, DominatorTree *DT,
490 OrderedBasicBlock *OBB = nullptr);
492 /// \brief A convenience wrapper to synthesize a memory location.
493 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
494 uint64_t Size, DominatorTree *DT,
495 OrderedBasicBlock *OBB = nullptr) {
496 return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
500 //===--------------------------------------------------------------------===//
501 /// \name Higher level methods for querying mod/ref information.
504 /// Check if it is possible for execution of the specified basic block to
505 /// modify the location Loc.
506 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
508 /// A convenience wrapper synthesizing a memory location.
509 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
511 return canBasicBlockModify(BB, MemoryLocation(P, Size));
514 /// Check if it is possible for the execution of the specified instructions
515 /// to mod\ref (according to the mode) the location Loc.
517 /// The instructions to consider are all of the instructions in the range of
518 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
519 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
520 const MemoryLocation &Loc,
521 const ModRefInfo Mode);
523 /// A convenience wrapper synthesizing a memory location.
524 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
525 const Value *Ptr, uint64_t Size,
526 const ModRefInfo Mode) {
527 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
532 template <typename T> class Model;
534 template <typename T> friend class AAResultBase;
536 std::vector<std::unique_ptr<Concept>> AAs;
539 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
540 /// pointer or reference.
541 typedef AAResults AliasAnalysis;
543 /// A private abstract base class describing the concept of an individual alias
544 /// analysis implementation.
546 /// This interface is implemented by any \c Model instantiation. It is also the
547 /// interface which a type used to instantiate the model must provide.
549 /// All of these methods model methods by the same name in the \c
550 /// AAResults class. Only differences and specifics to how the
551 /// implementations are called are documented here.
552 class AAResults::Concept {
554 virtual ~Concept() = 0;
556 /// An update API used internally by the AAResults to provide
557 /// a handle back to the top level aggregation.
558 virtual void setAAResults(AAResults *NewAAR) = 0;
560 //===--------------------------------------------------------------------===//
561 /// \name Alias Queries
564 /// The main low level interface to the alias analysis implementation.
565 /// Returns an AliasResult indicating whether the two pointers are aliased to
566 /// each other. This is the interface that must be implemented by specific
567 /// alias analysis implementations.
568 virtual AliasResult alias(const MemoryLocation &LocA,
569 const MemoryLocation &LocB) = 0;
571 /// Checks whether the given location points to constant memory, or if
572 /// \p OrLocal is true whether it points to a local alloca.
573 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
577 //===--------------------------------------------------------------------===//
578 /// \name Simple mod/ref information
581 /// Get the ModRef info associated with a pointer argument of a callsite. The
582 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
583 /// that these bits do not necessarily account for the overall behavior of
584 /// the function, but rather only provide additional per-argument
586 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS,
587 unsigned ArgIdx) = 0;
589 /// Return the behavior of the given call site.
590 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) = 0;
592 /// Return the behavior when calling the given function.
593 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
595 /// getModRefInfo (for call sites) - Return information about whether
596 /// a particular call site modifies or reads the specified memory location.
597 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
598 const MemoryLocation &Loc) = 0;
600 /// Return information about whether two call sites may refer to the same set
601 /// of memory locations. See the AA documentation for details:
602 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
603 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
604 ImmutableCallSite CS2) = 0;
609 /// A private class template which derives from \c Concept and wraps some other
612 /// This models the concept by directly forwarding each interface point to the
613 /// wrapped type which must implement a compatible interface. This provides
614 /// a type erased binding.
615 template <typename AAResultT> class AAResults::Model final : public Concept {
619 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
620 Result.setAAResults(&AAR);
624 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
626 AliasResult alias(const MemoryLocation &LocA,
627 const MemoryLocation &LocB) override {
628 return Result.alias(LocA, LocB);
631 bool pointsToConstantMemory(const MemoryLocation &Loc,
632 bool OrLocal) override {
633 return Result.pointsToConstantMemory(Loc, OrLocal);
636 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override {
637 return Result.getArgModRefInfo(CS, ArgIdx);
640 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override {
641 return Result.getModRefBehavior(CS);
644 FunctionModRefBehavior getModRefBehavior(const Function *F) override {
645 return Result.getModRefBehavior(F);
648 ModRefInfo getModRefInfo(ImmutableCallSite CS,
649 const MemoryLocation &Loc) override {
650 return Result.getModRefInfo(CS, Loc);
653 ModRefInfo getModRefInfo(ImmutableCallSite CS1,
654 ImmutableCallSite CS2) override {
655 return Result.getModRefInfo(CS1, CS2);
659 /// A CRTP-driven "mixin" base class to help implement the function alias
660 /// analysis results concept.
662 /// Because of the nature of many alias analysis implementations, they often
663 /// only implement a subset of the interface. This base class will attempt to
664 /// implement the remaining portions of the interface in terms of simpler forms
665 /// of the interface where possible, and otherwise provide conservatively
666 /// correct fallback implementations.
668 /// Implementors of an alias analysis should derive from this CRTP, and then
669 /// override specific methods that they wish to customize. There is no need to
670 /// use virtual anywhere, the CRTP base class does static dispatch to the
671 /// derived type passed into it.
672 template <typename DerivedT> class AAResultBase {
673 // Expose some parts of the interface only to the AAResults::Model
674 // for wrapping. Specifically, this allows the model to call our
675 // setAAResults method without exposing it as a fully public API.
676 friend class AAResults::Model<DerivedT>;
678 /// A pointer to the AAResults object that this AAResult is
679 /// aggregated within. May be null if not aggregated.
682 /// Helper to dispatch calls back through the derived type.
683 DerivedT &derived() { return static_cast<DerivedT &>(*this); }
685 /// A setter for the AAResults pointer, which is used to satisfy the
686 /// AAResults::Model contract.
687 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
690 /// This proxy class models a common pattern where we delegate to either the
691 /// top-level \c AAResults aggregation if one is registered, or to the
692 /// current result if none are registered.
693 class AAResultsProxy {
695 DerivedT &CurrentResult;
698 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
699 : AAR(AAR), CurrentResult(CurrentResult) {}
701 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
702 return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB);
705 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
706 return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal)
707 : CurrentResult.pointsToConstantMemory(Loc, OrLocal);
710 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
711 return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx);
714 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
715 return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS);
718 FunctionModRefBehavior getModRefBehavior(const Function *F) {
719 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
722 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
723 return AAR ? AAR->getModRefInfo(CS, Loc)
724 : CurrentResult.getModRefInfo(CS, Loc);
727 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
728 return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2);
732 const TargetLibraryInfo &TLI;
734 explicit AAResultBase(const TargetLibraryInfo &TLI) : TLI(TLI) {}
736 // Provide all the copy and move constructors so that derived types aren't
738 AAResultBase(const AAResultBase &Arg) : TLI(Arg.TLI) {}
739 AAResultBase(AAResultBase &&Arg) : TLI(Arg.TLI) {}
741 /// Get a proxy for the best AA result set to query at this time.
743 /// When this result is part of a larger aggregation, this will proxy to that
744 /// aggregation. When this result is used in isolation, it will just delegate
745 /// back to the derived class's implementation.
746 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
749 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
753 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
757 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
761 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
762 if (!CS.hasOperandBundles())
763 // If CS has operand bundles then aliasing attributes from the function it
764 // calls do not directly apply to the CallSite. This can be made more
765 // precise in the future.
766 if (const Function *F = CS.getCalledFunction())
767 return getBestAAResults().getModRefBehavior(F);
769 return FMRB_UnknownModRefBehavior;
772 FunctionModRefBehavior getModRefBehavior(const Function *F) {
773 return FMRB_UnknownModRefBehavior;
776 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
778 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
781 /// Synthesize \c ModRefInfo for a call site and memory location by examining
782 /// the general behavior of the call site and any specific information for its
785 /// This essentially, delegates across the alias analysis interface to collect
786 /// information which may be enough to (conservatively) fulfill the query.
787 template <typename DerivedT>
788 ModRefInfo AAResultBase<DerivedT>::getModRefInfo(ImmutableCallSite CS,
789 const MemoryLocation &Loc) {
790 auto MRB = getBestAAResults().getModRefBehavior(CS);
791 if (MRB == FMRB_DoesNotAccessMemory)
794 ModRefInfo Mask = MRI_ModRef;
795 if (AAResults::onlyReadsMemory(MRB))
798 if (AAResults::onlyAccessesArgPointees(MRB)) {
799 bool DoesAlias = false;
800 ModRefInfo AllArgsMask = MRI_NoModRef;
801 if (AAResults::doesAccessArgPointees(MRB)) {
802 for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(),
805 const Value *Arg = *AI;
806 if (!Arg->getType()->isPointerTy())
808 unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
809 MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
810 AliasResult ArgAlias = getBestAAResults().alias(ArgLoc, Loc);
811 if (ArgAlias != NoAlias) {
812 ModRefInfo ArgMask = getBestAAResults().getArgModRefInfo(CS, ArgIdx);
814 AllArgsMask = ModRefInfo(AllArgsMask | ArgMask);
820 Mask = ModRefInfo(Mask & AllArgsMask);
823 // If Loc is a constant memory location, the call definitely could not
824 // modify the memory location.
825 if ((Mask & MRI_Mod) &&
826 getBestAAResults().pointsToConstantMemory(Loc, /*OrLocal*/ false))
827 Mask = ModRefInfo(Mask & ~MRI_Mod);
832 /// Synthesize \c ModRefInfo for two call sites by examining the general
833 /// behavior of the call site and any specific information for its arguments.
835 /// This essentially, delegates across the alias analysis interface to collect
836 /// information which may be enough to (conservatively) fulfill the query.
837 template <typename DerivedT>
838 ModRefInfo AAResultBase<DerivedT>::getModRefInfo(ImmutableCallSite CS1,
839 ImmutableCallSite CS2) {
840 // If CS1 or CS2 are readnone, they don't interact.
841 auto CS1B = getBestAAResults().getModRefBehavior(CS1);
842 if (CS1B == FMRB_DoesNotAccessMemory)
845 auto CS2B = getBestAAResults().getModRefBehavior(CS2);
846 if (CS2B == FMRB_DoesNotAccessMemory)
849 // If they both only read from memory, there is no dependence.
850 if (AAResults::onlyReadsMemory(CS1B) && AAResults::onlyReadsMemory(CS2B))
853 ModRefInfo Mask = MRI_ModRef;
855 // If CS1 only reads memory, the only dependence on CS2 can be
856 // from CS1 reading memory written by CS2.
857 if (AAResults::onlyReadsMemory(CS1B))
858 Mask = ModRefInfo(Mask & MRI_Ref);
860 // If CS2 only access memory through arguments, accumulate the mod/ref
861 // information from CS1's references to the memory referenced by
863 if (AAResults::onlyAccessesArgPointees(CS2B)) {
864 ModRefInfo R = MRI_NoModRef;
865 if (AAResults::doesAccessArgPointees(CS2B)) {
866 for (ImmutableCallSite::arg_iterator I = CS2.arg_begin(),
869 const Value *Arg = *I;
870 if (!Arg->getType()->isPointerTy())
872 unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
873 auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
875 // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence
876 // of CS1 on that location is the inverse.
878 getBestAAResults().getArgModRefInfo(CS2, CS2ArgIdx);
879 if (ArgMask == MRI_Mod)
880 ArgMask = MRI_ModRef;
881 else if (ArgMask == MRI_Ref)
884 ArgMask = ModRefInfo(ArgMask &
885 getBestAAResults().getModRefInfo(CS1, CS2ArgLoc));
887 R = ModRefInfo((R | ArgMask) & Mask);
895 // If CS1 only accesses memory through arguments, check if CS2 references
896 // any of the memory referenced by CS1's arguments. If not, return NoModRef.
897 if (AAResults::onlyAccessesArgPointees(CS1B)) {
898 ModRefInfo R = MRI_NoModRef;
899 if (AAResults::doesAccessArgPointees(CS1B)) {
900 for (ImmutableCallSite::arg_iterator I = CS1.arg_begin(),
903 const Value *Arg = *I;
904 if (!Arg->getType()->isPointerTy())
906 unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
907 auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
909 // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
910 // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
911 // might Ref, then we care only about a Mod by CS2.
912 ModRefInfo ArgMask = getBestAAResults().getArgModRefInfo(CS1, CS1ArgIdx);
913 ModRefInfo ArgR = getBestAAResults().getModRefInfo(CS2, CS1ArgLoc);
914 if (((ArgMask & MRI_Mod) != MRI_NoModRef &&
915 (ArgR & MRI_ModRef) != MRI_NoModRef) ||
916 ((ArgMask & MRI_Ref) != MRI_NoModRef &&
917 (ArgR & MRI_Mod) != MRI_NoModRef))
918 R = ModRefInfo((R | ArgMask) & Mask);
930 /// isNoAliasCall - Return true if this pointer is returned by a noalias
932 bool isNoAliasCall(const Value *V);
934 /// isNoAliasArgument - Return true if this is an argument with the noalias
936 bool isNoAliasArgument(const Value *V);
938 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
939 /// identifiable object. This returns true for:
940 /// Global Variables and Functions (but not Global Aliases)
942 /// ByVal and NoAlias Arguments
943 /// NoAlias returns (e.g. calls to malloc)
945 bool isIdentifiedObject(const Value *V);
947 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
948 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
949 /// Further, an IdentifiedFunctionLocal can not alias with any function
950 /// arguments other than itself, which is not necessarily true for
951 /// IdentifiedObjects.
952 bool isIdentifiedFunctionLocal(const Value *V);
954 /// A manager for alias analyses.
956 /// This class can have analyses registered with it and when run, it will run
957 /// all of them and aggregate their results into single AA results interface
958 /// that dispatches across all of the alias analysis results available.
960 /// Note that the order in which analyses are registered is very significant.
961 /// That is the order in which the results will be aggregated and queried.
963 /// This manager effectively wraps the AnalysisManager for registering alias
964 /// analyses. When you register your alias analysis with this manager, it will
965 /// ensure the analysis itself is registered with its AnalysisManager.
968 typedef AAResults Result;
970 // This type hase value semantics. We have to spell these out because MSVC
971 // won't synthesize them.
973 AAManager(AAManager &&Arg)
974 : FunctionResultGetters(std::move(Arg.FunctionResultGetters)) {}
975 AAManager(const AAManager &Arg)
976 : FunctionResultGetters(Arg.FunctionResultGetters) {}
977 AAManager &operator=(AAManager &&RHS) {
978 FunctionResultGetters = std::move(RHS.FunctionResultGetters);
981 AAManager &operator=(const AAManager &RHS) {
982 FunctionResultGetters = RHS.FunctionResultGetters;
986 /// Register a specific AA result.
987 template <typename AnalysisT> void registerFunctionAnalysis() {
988 FunctionResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
991 Result run(Function &F, AnalysisManager<Function> &AM) {
993 for (auto &Getter : FunctionResultGetters)
999 SmallVector<void (*)(Function &F, AnalysisManager<Function> &AM,
1000 AAResults &AAResults),
1001 4> FunctionResultGetters;
1003 template <typename AnalysisT>
1004 static void getFunctionAAResultImpl(Function &F,
1005 AnalysisManager<Function> &AM,
1006 AAResults &AAResults) {
1007 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1011 /// A wrapper pass to provide the legacy pass manager access to a suitably
1012 /// prepared AAResults object.
1013 class AAResultsWrapperPass : public FunctionPass {
1014 std::unique_ptr<AAResults> AAR;
1019 AAResultsWrapperPass();
1021 AAResults &getAAResults() { return *AAR; }
1022 const AAResults &getAAResults() const { return *AAR; }
1024 bool runOnFunction(Function &F) override;
1026 void getAnalysisUsage(AnalysisUsage &AU) const override;
1029 FunctionPass *createAAResultsWrapperPass();
1031 /// A wrapper pass around a callback which can be used to populate the
1032 /// AAResults in the AAResultsWrapperPass from an external AA.
1034 /// The callback provided here will be used each time we prepare an AAResults
1035 /// object, and will receive a reference to the function wrapper pass, the
1036 /// function, and the AAResults object to populate. This should be used when
1037 /// setting up a custom pass pipeline to inject a hook into the AA results.
1038 ImmutablePass *createExternalAAWrapperPass(
1039 std::function<void(Pass &, Function &, AAResults &)> Callback);
1041 /// A helper for the legacy pass manager to create a \c AAResults
1042 /// object populated to the best of our ability for a particular function when
1043 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
1044 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
1046 } // End llvm namespace