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 (const Function *F = CS.getCalledFunction())
763 return getBestAAResults().getModRefBehavior(F);
765 return FMRB_UnknownModRefBehavior;
768 FunctionModRefBehavior getModRefBehavior(const Function *F) {
769 return FMRB_UnknownModRefBehavior;
772 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
774 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
777 /// Synthesize \c ModRefInfo for a call site and memory location by examining
778 /// the general behavior of the call site and any specific information for its
781 /// This essentially, delegates across the alias analysis interface to collect
782 /// information which may be enough to (conservatively) fulfill the query.
783 template <typename DerivedT>
784 ModRefInfo AAResultBase<DerivedT>::getModRefInfo(ImmutableCallSite CS,
785 const MemoryLocation &Loc) {
786 auto MRB = getBestAAResults().getModRefBehavior(CS);
787 if (MRB == FMRB_DoesNotAccessMemory)
790 ModRefInfo Mask = MRI_ModRef;
791 if (AAResults::onlyReadsMemory(MRB))
794 if (AAResults::onlyAccessesArgPointees(MRB)) {
795 bool DoesAlias = false;
796 ModRefInfo AllArgsMask = MRI_NoModRef;
797 if (AAResults::doesAccessArgPointees(MRB)) {
798 for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(),
801 const Value *Arg = *AI;
802 if (!Arg->getType()->isPointerTy())
804 unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
805 MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
806 AliasResult ArgAlias = getBestAAResults().alias(ArgLoc, Loc);
807 if (ArgAlias != NoAlias) {
808 ModRefInfo ArgMask = getBestAAResults().getArgModRefInfo(CS, ArgIdx);
810 AllArgsMask = ModRefInfo(AllArgsMask | ArgMask);
816 Mask = ModRefInfo(Mask & AllArgsMask);
819 // If Loc is a constant memory location, the call definitely could not
820 // modify the memory location.
821 if ((Mask & MRI_Mod) &&
822 getBestAAResults().pointsToConstantMemory(Loc, /*OrLocal*/ false))
823 Mask = ModRefInfo(Mask & ~MRI_Mod);
828 /// Synthesize \c ModRefInfo for two call sites by examining the general
829 /// behavior of the call site and any specific information for its arguments.
831 /// This essentially, delegates across the alias analysis interface to collect
832 /// information which may be enough to (conservatively) fulfill the query.
833 template <typename DerivedT>
834 ModRefInfo AAResultBase<DerivedT>::getModRefInfo(ImmutableCallSite CS1,
835 ImmutableCallSite CS2) {
836 // If CS1 or CS2 are readnone, they don't interact.
837 auto CS1B = getBestAAResults().getModRefBehavior(CS1);
838 if (CS1B == FMRB_DoesNotAccessMemory)
841 auto CS2B = getBestAAResults().getModRefBehavior(CS2);
842 if (CS2B == FMRB_DoesNotAccessMemory)
845 // If they both only read from memory, there is no dependence.
846 if (AAResults::onlyReadsMemory(CS1B) && AAResults::onlyReadsMemory(CS2B))
849 ModRefInfo Mask = MRI_ModRef;
851 // If CS1 only reads memory, the only dependence on CS2 can be
852 // from CS1 reading memory written by CS2.
853 if (AAResults::onlyReadsMemory(CS1B))
854 Mask = ModRefInfo(Mask & MRI_Ref);
856 // If CS2 only access memory through arguments, accumulate the mod/ref
857 // information from CS1's references to the memory referenced by
859 if (AAResults::onlyAccessesArgPointees(CS2B)) {
860 ModRefInfo R = MRI_NoModRef;
861 if (AAResults::doesAccessArgPointees(CS2B)) {
862 for (ImmutableCallSite::arg_iterator I = CS2.arg_begin(),
865 const Value *Arg = *I;
866 if (!Arg->getType()->isPointerTy())
868 unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
869 auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
871 // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence
872 // of CS1 on that location is the inverse.
874 getBestAAResults().getArgModRefInfo(CS2, CS2ArgIdx);
875 if (ArgMask == MRI_Mod)
876 ArgMask = MRI_ModRef;
877 else if (ArgMask == MRI_Ref)
880 ArgMask = ModRefInfo(ArgMask &
881 getBestAAResults().getModRefInfo(CS1, CS2ArgLoc));
883 R = ModRefInfo((R | ArgMask) & Mask);
891 // If CS1 only accesses memory through arguments, check if CS2 references
892 // any of the memory referenced by CS1's arguments. If not, return NoModRef.
893 if (AAResults::onlyAccessesArgPointees(CS1B)) {
894 ModRefInfo R = MRI_NoModRef;
895 if (AAResults::doesAccessArgPointees(CS1B)) {
896 for (ImmutableCallSite::arg_iterator I = CS1.arg_begin(),
899 const Value *Arg = *I;
900 if (!Arg->getType()->isPointerTy())
902 unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
903 auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
905 // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
906 // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
907 // might Ref, then we care only about a Mod by CS2.
908 ModRefInfo ArgMask = getBestAAResults().getArgModRefInfo(CS1, CS1ArgIdx);
909 ModRefInfo ArgR = getBestAAResults().getModRefInfo(CS2, CS1ArgLoc);
910 if (((ArgMask & MRI_Mod) != MRI_NoModRef &&
911 (ArgR & MRI_ModRef) != MRI_NoModRef) ||
912 ((ArgMask & MRI_Ref) != MRI_NoModRef &&
913 (ArgR & MRI_Mod) != MRI_NoModRef))
914 R = ModRefInfo((R | ArgMask) & Mask);
926 /// isNoAliasCall - Return true if this pointer is returned by a noalias
928 bool isNoAliasCall(const Value *V);
930 /// isNoAliasArgument - Return true if this is an argument with the noalias
932 bool isNoAliasArgument(const Value *V);
934 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
935 /// identifiable object. This returns true for:
936 /// Global Variables and Functions (but not Global Aliases)
938 /// ByVal and NoAlias Arguments
939 /// NoAlias returns (e.g. calls to malloc)
941 bool isIdentifiedObject(const Value *V);
943 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
944 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
945 /// Further, an IdentifiedFunctionLocal can not alias with any function
946 /// arguments other than itself, which is not necessarily true for
947 /// IdentifiedObjects.
948 bool isIdentifiedFunctionLocal(const Value *V);
950 /// A manager for alias analyses.
952 /// This class can have analyses registered with it and when run, it will run
953 /// all of them and aggregate their results into single AA results interface
954 /// that dispatches across all of the alias analysis results available.
956 /// Note that the order in which analyses are registered is very significant.
957 /// That is the order in which the results will be aggregated and queried.
959 /// This manager effectively wraps the AnalysisManager for registering alias
960 /// analyses. When you register your alias analysis with this manager, it will
961 /// ensure the analysis itself is registered with its AnalysisManager.
964 typedef AAResults Result;
966 // This type hase value semantics. We have to spell these out because MSVC
967 // won't synthesize them.
969 AAManager(AAManager &&Arg)
970 : FunctionResultGetters(std::move(Arg.FunctionResultGetters)) {}
971 AAManager(const AAManager &Arg)
972 : FunctionResultGetters(Arg.FunctionResultGetters) {}
973 AAManager &operator=(AAManager &&RHS) {
974 FunctionResultGetters = std::move(RHS.FunctionResultGetters);
977 AAManager &operator=(const AAManager &RHS) {
978 FunctionResultGetters = RHS.FunctionResultGetters;
982 /// Register a specific AA result.
983 template <typename AnalysisT> void registerFunctionAnalysis() {
984 FunctionResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
987 Result run(Function &F, AnalysisManager<Function> &AM) {
989 for (auto &Getter : FunctionResultGetters)
995 SmallVector<void (*)(Function &F, AnalysisManager<Function> &AM,
996 AAResults &AAResults),
997 4> FunctionResultGetters;
999 template <typename AnalysisT>
1000 static void getFunctionAAResultImpl(Function &F,
1001 AnalysisManager<Function> &AM,
1002 AAResults &AAResults) {
1003 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1007 /// A wrapper pass to provide the legacy pass manager access to a suitably
1008 /// prepared AAResults object.
1009 class AAResultsWrapperPass : public FunctionPass {
1010 std::unique_ptr<AAResults> AAR;
1015 AAResultsWrapperPass();
1017 AAResults &getAAResults() { return *AAR; }
1018 const AAResults &getAAResults() const { return *AAR; }
1020 bool runOnFunction(Function &F) override;
1022 void getAnalysisUsage(AnalysisUsage &AU) const override;
1025 FunctionPass *createAAResultsWrapperPass();
1027 /// A helper for the legacy pass manager to create a \c AAResults
1028 /// object populated to the best of our ability for a particular function when
1029 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
1030 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
1032 } // End llvm namespace