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/Analysis/MemoryLocation.h"
52 class TargetLibraryInfo;
55 class MemTransferInst;
58 class OrderedBasicBlock;
60 /// The possible results of an alias query.
62 /// These results are always computed between two MemoryLocation objects as
63 /// a query to some alias analysis.
65 /// Note that these are unscoped enumerations because we would like to support
66 /// implicitly testing a result for the existence of any possible aliasing with
67 /// a conversion to bool, but an "enum class" doesn't support this. The
68 /// canonical names from the literature are suffixed and unique anyways, and so
69 /// they serve as global constants in LLVM for these results.
71 /// See docs/AliasAnalysis.html for more information on the specific meanings
74 /// The two locations do not alias at all.
76 /// This value is arranged to convert to false, while all other values
77 /// convert to true. This allows a boolean context to convert the result to
78 /// a binary flag indicating whether there is the possibility of aliasing.
80 /// The two locations may or may not alias. This is the least precise result.
82 /// The two locations alias, but only due to a partial overlap.
84 /// The two locations precisely alias each other.
88 /// Flags indicating whether a memory access modifies or references memory.
90 /// This is no access at all, a modification, a reference, or both
91 /// a modification and a reference. These are specifically structured such that
92 /// they form a two bit matrix and bit-tests for 'mod' or 'ref' work with any
93 /// of the possible values.
95 /// The access neither references nor modifies the value stored in memory.
97 /// The access references the value stored in memory.
99 /// The access modifies the value stored in memory.
101 /// The access both references and modifies the value stored in memory.
102 MRI_ModRef = MRI_Ref | MRI_Mod
105 /// The locations at which a function might access memory.
107 /// These are primarily used in conjunction with the \c AccessKind bits to
108 /// describe both the nature of access and the locations of access for a
110 enum FunctionModRefLocation {
111 /// Base case is no access to memory.
113 /// Access to memory via argument pointers.
114 FMRL_ArgumentPointees = 4,
115 /// Access to any memory.
116 FMRL_Anywhere = 8 | FMRL_ArgumentPointees
119 /// Summary of how a function affects memory in the program.
121 /// Loads from constant globals are not considered memory accesses for this
122 /// interface. Also, functions may freely modify stack space local to their
123 /// invocation without having to report it through these interfaces.
124 enum FunctionModRefBehavior {
125 /// This function does not perform any non-local loads or stores to memory.
127 /// This property corresponds to the GCC 'const' attribute.
128 /// This property corresponds to the LLVM IR 'readnone' attribute.
129 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
130 FMRB_DoesNotAccessMemory = FMRL_Nowhere | MRI_NoModRef,
132 /// The only memory references in this function (if it has any) are
133 /// non-volatile loads from objects pointed to by its pointer-typed
134 /// arguments, with arbitrary offsets.
136 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
137 FMRB_OnlyReadsArgumentPointees = FMRL_ArgumentPointees | MRI_Ref,
139 /// The only memory references in this function (if it has any) are
140 /// non-volatile loads and stores from objects pointed to by its
141 /// pointer-typed arguments, with arbitrary offsets.
143 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
144 FMRB_OnlyAccessesArgumentPointees = FMRL_ArgumentPointees | MRI_ModRef,
146 /// This function does not perform any non-local stores or volatile loads,
147 /// but may read from any memory location.
149 /// This property corresponds to the GCC 'pure' attribute.
150 /// This property corresponds to the LLVM IR 'readonly' attribute.
151 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
152 FMRB_OnlyReadsMemory = FMRL_Anywhere | MRI_Ref,
154 /// This indicates that the function could not be classified into one of the
156 FMRB_UnknownModRefBehavior = FMRL_Anywhere | MRI_ModRef
159 class AliasAnalysis {
161 const DataLayout *DL;
162 const TargetLibraryInfo *TLI;
165 AliasAnalysis *AA; // Previous Alias Analysis to chain to.
168 /// InitializeAliasAnalysis - Subclasses must call this method to initialize
169 /// the AliasAnalysis interface before any other methods are called. This is
170 /// typically called by the run* methods of these subclasses. This may be
171 /// called multiple times.
173 void InitializeAliasAnalysis(Pass *P, const DataLayout *DL);
175 /// getAnalysisUsage - All alias analysis implementations should invoke this
176 /// directly (using AliasAnalysis::getAnalysisUsage(AU)).
177 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
180 static char ID; // Class identification, replacement for typeinfo
181 AliasAnalysis() : DL(nullptr), TLI(nullptr), AA(nullptr) {}
182 virtual ~AliasAnalysis(); // We want to be subclassed
184 /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo
185 /// object, or null if no TargetLibraryInfo object is available.
187 const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; }
189 //===--------------------------------------------------------------------===//
190 /// \name Alias Queries
193 /// The main low level interface to the alias analysis implementation.
194 /// Returns an AliasResult indicating whether the two pointers are aliased to
195 /// each other. This is the interface that must be implemented by specific
196 /// alias analysis implementations.
197 virtual AliasResult alias(const MemoryLocation &LocA,
198 const MemoryLocation &LocB);
200 /// A convenience wrapper around the primary \c alias interface.
201 AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2,
203 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
206 /// A convenience wrapper around the primary \c alias interface.
207 AliasResult alias(const Value *V1, const Value *V2) {
208 return alias(V1, MemoryLocation::UnknownSize, V2,
209 MemoryLocation::UnknownSize);
212 /// A trivial helper function to check to see if the specified pointers are
214 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
215 return alias(LocA, LocB) == NoAlias;
218 /// A convenience wrapper around the \c isNoAlias helper interface.
219 bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2,
221 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
224 /// A convenience wrapper around the \c isNoAlias helper interface.
225 bool isNoAlias(const Value *V1, const Value *V2) {
226 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
229 /// A trivial helper function to check to see if the specified pointers are
231 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
232 return alias(LocA, LocB) == MustAlias;
235 /// A convenience wrapper around the \c isMustAlias helper interface.
236 bool isMustAlias(const Value *V1, const Value *V2) {
237 return alias(V1, 1, V2, 1) == MustAlias;
240 /// Checks whether the given location points to constant memory, or if
241 /// \p OrLocal is true whether it points to a local alloca.
242 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
243 bool OrLocal = false);
245 /// A convenience wrapper around the primary \c pointsToConstantMemory
247 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
248 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
252 //===--------------------------------------------------------------------===//
253 /// \name Simple mod/ref information
256 /// Get the ModRef info associated with a pointer argument of a callsite. The
257 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
258 /// that these bits do not necessarily account for the overall behavior of
259 /// the function, but rather only provide additional per-argument
261 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
263 /// Return the behavior of the given call site.
264 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
266 /// Return the behavior when calling the given function.
267 virtual FunctionModRefBehavior getModRefBehavior(const Function *F);
269 /// Checks if the specified call is known to never read or write memory.
271 /// Note that if the call only reads from known-constant memory, it is also
272 /// legal to return true. Also, calls that unwind the stack are legal for
275 /// Many optimizations (such as CSE and LICM) can be performed on such calls
276 /// without worrying about aliasing properties, and many calls have this
277 /// property (e.g. calls to 'sin' and 'cos').
279 /// This property corresponds to the GCC 'const' attribute.
280 bool doesNotAccessMemory(ImmutableCallSite CS) {
281 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
284 /// Checks if the specified function is known to never read or write memory.
286 /// Note that if the function only reads from known-constant memory, it is
287 /// also legal to return true. Also, function that unwind the stack are legal
288 /// for this predicate.
290 /// Many optimizations (such as CSE and LICM) can be performed on such calls
291 /// to such functions without worrying about aliasing properties, and many
292 /// functions have this property (e.g. 'sin' and 'cos').
294 /// This property corresponds to the GCC 'const' attribute.
295 bool doesNotAccessMemory(const Function *F) {
296 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
299 /// Checks if the specified call is known to only read from non-volatile
300 /// memory (or not access memory at all).
302 /// Calls that unwind the stack are legal for this predicate.
304 /// This property allows many common optimizations to be performed in the
305 /// absence of interfering store instructions, such as CSE of strlen calls.
307 /// This property corresponds to the GCC 'pure' attribute.
308 bool onlyReadsMemory(ImmutableCallSite CS) {
309 return onlyReadsMemory(getModRefBehavior(CS));
312 /// Checks if the specified function is known to only read from non-volatile
313 /// memory (or not access memory at all).
315 /// Functions that unwind the stack are legal for this predicate.
317 /// This property allows many common optimizations to be performed in the
318 /// absence of interfering store instructions, such as CSE of strlen calls.
320 /// This property corresponds to the GCC 'pure' attribute.
321 bool onlyReadsMemory(const Function *F) {
322 return onlyReadsMemory(getModRefBehavior(F));
325 /// Checks if functions with the specified behavior are known to only read
326 /// from non-volatile memory (or not access memory at all).
327 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
328 return !(MRB & MRI_Mod);
331 /// Checks if functions with the specified behavior are known to read and
332 /// write at most from objects pointed to by their pointer-typed arguments
333 /// (with arbitrary offsets).
334 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
335 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
338 /// Checks if functions with the specified behavior are known to potentially
339 /// read or write from objects pointed to be their pointer-typed arguments
340 /// (with arbitrary offsets).
341 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
342 return (MRB & MRI_ModRef) && (MRB & FMRL_ArgumentPointees);
345 /// getModRefInfo (for call sites) - Return information about whether
346 /// a particular call site modifies or reads the specified memory location.
347 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
348 const MemoryLocation &Loc);
350 /// getModRefInfo (for call sites) - A convenience wrapper.
351 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
353 return getModRefInfo(CS, MemoryLocation(P, Size));
356 /// getModRefInfo (for calls) - Return information about whether
357 /// a particular call modifies or reads the specified memory location.
358 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
359 return getModRefInfo(ImmutableCallSite(C), Loc);
362 /// getModRefInfo (for calls) - A convenience wrapper.
363 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
364 return getModRefInfo(C, MemoryLocation(P, Size));
367 /// getModRefInfo (for invokes) - Return information about whether
368 /// a particular invoke modifies or reads the specified memory location.
369 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
370 return getModRefInfo(ImmutableCallSite(I), Loc);
373 /// getModRefInfo (for invokes) - A convenience wrapper.
374 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
375 return getModRefInfo(I, MemoryLocation(P, Size));
378 /// getModRefInfo (for loads) - Return information about whether
379 /// a particular load modifies or reads the specified memory location.
380 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
382 /// getModRefInfo (for loads) - A convenience wrapper.
383 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
384 return getModRefInfo(L, MemoryLocation(P, Size));
387 /// getModRefInfo (for stores) - Return information about whether
388 /// a particular store modifies or reads the specified memory location.
389 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
391 /// getModRefInfo (for stores) - A convenience wrapper.
392 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
393 return getModRefInfo(S, MemoryLocation(P, Size));
396 /// getModRefInfo (for fences) - Return information about whether
397 /// a particular store modifies or reads the specified memory location.
398 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
399 // Conservatively correct. (We could possibly be a bit smarter if
400 // Loc is a alloca that doesn't escape.)
404 /// getModRefInfo (for fences) - A convenience wrapper.
405 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
406 return getModRefInfo(S, MemoryLocation(P, Size));
409 /// getModRefInfo (for cmpxchges) - Return information about whether
410 /// a particular cmpxchg modifies or reads the specified memory location.
411 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
412 const MemoryLocation &Loc);
414 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
415 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
417 return getModRefInfo(CX, MemoryLocation(P, Size));
420 /// getModRefInfo (for atomicrmws) - Return information about whether
421 /// a particular atomicrmw modifies or reads the specified memory location.
422 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
424 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
425 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
427 return getModRefInfo(RMW, MemoryLocation(P, Size));
430 /// getModRefInfo (for va_args) - Return information about whether
431 /// a particular va_arg modifies or reads the specified memory location.
432 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
434 /// getModRefInfo (for va_args) - A convenience wrapper.
435 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
436 return getModRefInfo(I, MemoryLocation(P, Size));
439 /// Check whether or not an instruction may read or write memory (without
440 /// regard to a specific location).
442 /// For function calls, this delegates to the alias-analysis specific
443 /// call-site mod-ref behavior queries. Otherwise it delegates to the generic
444 /// mod ref information query without a location.
445 ModRefInfo getModRefInfo(const Instruction *I) {
446 if (auto CS = ImmutableCallSite(I)) {
447 auto MRB = getModRefBehavior(CS);
448 if (MRB & MRI_ModRef)
450 else if (MRB & MRI_Ref)
452 else if (MRB & MRI_Mod)
457 return getModRefInfo(I, MemoryLocation());
460 /// Check whether or not an instruction may read or write the specified
463 /// An instruction that doesn't read or write memory may be trivially LICM'd
466 /// This primarily delegates to specific helpers above.
467 ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
468 switch (I->getOpcode()) {
469 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
470 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
471 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
472 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
473 case Instruction::AtomicCmpXchg:
474 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
475 case Instruction::AtomicRMW:
476 return getModRefInfo((const AtomicRMWInst*)I, Loc);
477 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
478 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
484 /// A convenience wrapper for constructing the memory location.
485 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
487 return getModRefInfo(I, MemoryLocation(P, Size));
490 /// Return information about whether a call and an instruction may refer to
491 /// the same memory locations.
492 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
494 /// Return information about whether two call sites may refer to the same set
495 /// of memory locations. See the AA documentation for details:
496 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
497 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
498 ImmutableCallSite CS2);
500 /// \brief Return information about whether a particular call site modifies
501 /// or reads the specified memory location \p MemLoc before instruction \p I
502 /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
503 /// instruction ordering queries inside the BasicBlock containing \p I.
504 ModRefInfo callCapturesBefore(const Instruction *I,
505 const MemoryLocation &MemLoc, DominatorTree *DT,
506 OrderedBasicBlock *OBB = nullptr);
508 /// \brief A convenience wrapper to synthesize a memory location.
509 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
510 uint64_t Size, DominatorTree *DT,
511 OrderedBasicBlock *OBB = nullptr) {
512 return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
516 //===--------------------------------------------------------------------===//
517 /// \name Higher level methods for querying mod/ref information.
520 /// Check if it is possible for execution of the specified basic block to
521 /// modify the location Loc.
522 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
524 /// A convenience wrapper synthesizing a memory location.
525 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
527 return canBasicBlockModify(BB, MemoryLocation(P, Size));
530 /// Check if it is possible for the execution of the specified instructions
531 /// to mod\ref (according to the mode) the location Loc.
533 /// The instructions to consider are all of the instructions in the range of
534 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
535 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
536 const MemoryLocation &Loc,
537 const ModRefInfo Mode);
539 /// A convenience wrapper synthesizing a memory location.
540 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
541 const Value *Ptr, uint64_t Size,
542 const ModRefInfo Mode) {
543 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
547 /// isNoAliasCall - Return true if this pointer is returned by a noalias
549 bool isNoAliasCall(const Value *V);
551 /// isNoAliasArgument - Return true if this is an argument with the noalias
553 bool isNoAliasArgument(const Value *V);
555 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
556 /// identifiable object. This returns true for:
557 /// Global Variables and Functions (but not Global Aliases)
559 /// ByVal and NoAlias Arguments
560 /// NoAlias returns (e.g. calls to malloc)
562 bool isIdentifiedObject(const Value *V);
564 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
565 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
566 /// Further, an IdentifiedFunctionLocal can not alias with any function
567 /// arguments other than itself, which is not necessarily true for
568 /// IdentifiedObjects.
569 bool isIdentifiedFunctionLocal(const Value *V);
571 } // End llvm namespace