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;
59 /// The possible results of an alias query.
61 /// These results are always computed between two MemoryLocation objects as
62 /// a query to some alias analysis.
64 /// Note that these are unscoped enumerations because we would like to support
65 /// implicitly testing a result for the existence of any possible aliasing with
66 /// a conversion to bool, but an "enum class" doesn't support this. The
67 /// canonical names from the literature are suffixed and unique anyways, and so
68 /// they serve as global constants in LLVM for these results.
70 /// See docs/AliasAnalysis.html for more information on the specific meanings
73 /// The two locations do not alias at all.
75 /// This value is arranged to convert to false, while all other values
76 /// convert to true. This allows a boolean context to convert the result to
77 /// a binary flag indicating whether there is the possibility of aliasing.
79 /// The two locations may or may not alias. This is the least precise result.
81 /// The two locations alias, but only due to a partial overlap.
83 /// The two locations precisely alias each other.
87 /// Flags indicating whether a memory access modifies or references memory.
89 /// This is no access at all, a modification, a reference, or both
90 /// a modification and a reference. These are specifically structured such that
91 /// they form a two bit matrix and bit-tests for 'mod' or 'ref' work with any
92 /// of the possible values.
94 /// The access neither references nor modifies the value stored in memory.
96 /// The access references the value stored in memory.
98 /// The access modifies the value stored in memory.
100 /// The access both references and modifies the value stored in memory.
101 MRI_ModRef = MRI_Ref | MRI_Mod
104 /// The locations at which a function might access memory.
106 /// These are primarily used in conjunction with the \c AccessKind bits to
107 /// describe both the nature of access and the locations of access for a
109 enum FunctionModRefLocation {
110 /// Base case is no access to memory.
112 /// Access to memory via argument pointers.
113 FMRL_ArgumentPointees = 4,
114 /// Access to any memory.
115 FMRL_Anywhere = 8 | FMRL_ArgumentPointees
118 /// Summary of how a function affects memory in the program.
120 /// Loads from constant globals are not considered memory accesses for this
121 /// interface. Also, functions may freely modify stack space local to their
122 /// invocation without having to report it through these interfaces.
123 enum FunctionModRefBehavior {
124 /// This function does not perform any non-local loads or stores to memory.
126 /// This property corresponds to the GCC 'const' attribute.
127 /// This property corresponds to the LLVM IR 'readnone' attribute.
128 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
129 FMRB_DoesNotAccessMemory = FMRL_Nowhere | MRI_NoModRef,
131 /// The only memory references in this function (if it has any) are
132 /// non-volatile loads from objects pointed to by its pointer-typed
133 /// arguments, with arbitrary offsets.
135 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
136 FMRB_OnlyReadsArgumentPointees = FMRL_ArgumentPointees | MRI_Ref,
138 /// The only memory references in this function (if it has any) are
139 /// non-volatile loads and stores from objects pointed to by its
140 /// pointer-typed arguments, with arbitrary offsets.
142 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
143 FMRB_OnlyAccessesArgumentPointees = FMRL_ArgumentPointees | MRI_ModRef,
145 /// This function does not perform any non-local stores or volatile loads,
146 /// but may read from any memory location.
148 /// This property corresponds to the GCC 'pure' attribute.
149 /// This property corresponds to the LLVM IR 'readonly' attribute.
150 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
151 FMRB_OnlyReadsMemory = FMRL_Anywhere | MRI_Ref,
153 /// This indicates that the function could not be classified into one of the
155 FMRB_UnknownModRefBehavior = FMRL_Anywhere | MRI_ModRef
158 class AliasAnalysis {
160 const DataLayout *DL;
161 const TargetLibraryInfo *TLI;
164 AliasAnalysis *AA; // Previous Alias Analysis to chain to.
167 /// InitializeAliasAnalysis - Subclasses must call this method to initialize
168 /// the AliasAnalysis interface before any other methods are called. This is
169 /// typically called by the run* methods of these subclasses. This may be
170 /// called multiple times.
172 void InitializeAliasAnalysis(Pass *P, const DataLayout *DL);
174 /// getAnalysisUsage - All alias analysis implementations should invoke this
175 /// directly (using AliasAnalysis::getAnalysisUsage(AU)).
176 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
179 static char ID; // Class identification, replacement for typeinfo
180 AliasAnalysis() : DL(nullptr), TLI(nullptr), AA(nullptr) {}
181 virtual ~AliasAnalysis(); // We want to be subclassed
183 /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo
184 /// object, or null if no TargetLibraryInfo object is available.
186 const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; }
188 /// getTypeStoreSize - Return the DataLayout store size for the given type,
189 /// if known, or a conservative value otherwise.
191 uint64_t getTypeStoreSize(Type *Ty);
193 //===--------------------------------------------------------------------===//
194 /// \name Alias Queries
197 /// The main low level interface to the alias analysis implementation.
198 /// Returns an AliasResult indicating whether the two pointers are aliased to
199 /// each other. This is the interface that must be implemented by specific
200 /// alias analysis implementations.
201 virtual AliasResult alias(const MemoryLocation &LocA,
202 const MemoryLocation &LocB);
204 /// A convenience wrapper around the primary \c alias interface.
205 AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2,
207 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
210 /// A convenience wrapper around the primary \c alias interface.
211 AliasResult alias(const Value *V1, const Value *V2) {
212 return alias(V1, MemoryLocation::UnknownSize, V2,
213 MemoryLocation::UnknownSize);
216 /// A trivial helper function to check to see if the specified pointers are
218 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
219 return alias(LocA, LocB) == NoAlias;
222 /// A convenience wrapper around the \c isNoAlias helper interface.
223 bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2,
225 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
228 /// A convenience wrapper around the \c isNoAlias helper interface.
229 bool isNoAlias(const Value *V1, const Value *V2) {
230 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
233 /// A trivial helper function to check to see if the specified pointers are
235 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
236 return alias(LocA, LocB) == MustAlias;
239 /// A convenience wrapper around the \c isMustAlias helper interface.
240 bool isMustAlias(const Value *V1, const Value *V2) {
241 return alias(V1, 1, V2, 1) == MustAlias;
244 /// Checks whether the given location points to constant memory, or if
245 /// \p OrLocal is true whether it points to a local alloca.
246 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
247 bool OrLocal = false);
249 /// A convenience wrapper around the primary \c pointsToConstantMemory
251 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
252 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
256 //===--------------------------------------------------------------------===//
257 /// \name Simple mod/ref information
260 /// Get the ModRef info associated with a pointer argument of a callsite. The
261 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
262 /// that these bits do not necessarily account for the overall behavior of
263 /// the function, but rather only provide additional per-argument
265 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
267 /// Return the behavior of the given call site.
268 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
270 /// Return the behavior when calling the given function.
271 virtual FunctionModRefBehavior getModRefBehavior(const Function *F);
273 /// Checks if the specified call is known to never read or write memory.
275 /// Note that if the call only reads from known-constant memory, it is also
276 /// legal to return true. Also, calls that unwind the stack are legal for
279 /// Many optimizations (such as CSE and LICM) can be performed on such calls
280 /// without worrying about aliasing properties, and many calls have this
281 /// property (e.g. calls to 'sin' and 'cos').
283 /// This property corresponds to the GCC 'const' attribute.
284 bool doesNotAccessMemory(ImmutableCallSite CS) {
285 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
288 /// Checks if the specified function is known to never read or write memory.
290 /// Note that if the function only reads from known-constant memory, it is
291 /// also legal to return true. Also, function that unwind the stack are legal
292 /// for this predicate.
294 /// Many optimizations (such as CSE and LICM) can be performed on such calls
295 /// to such functions without worrying about aliasing properties, and many
296 /// functions have this property (e.g. 'sin' and 'cos').
298 /// This property corresponds to the GCC 'const' attribute.
299 bool doesNotAccessMemory(const Function *F) {
300 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
303 /// Checks if the specified call is known to only read from non-volatile
304 /// memory (or not access memory at all).
306 /// Calls that unwind the stack are legal for this predicate.
308 /// This property allows many common optimizations to be performed in the
309 /// absence of interfering store instructions, such as CSE of strlen calls.
311 /// This property corresponds to the GCC 'pure' attribute.
312 bool onlyReadsMemory(ImmutableCallSite CS) {
313 return onlyReadsMemory(getModRefBehavior(CS));
316 /// Checks if the specified function is known to only read from non-volatile
317 /// memory (or not access memory at all).
319 /// Functions that unwind the stack are legal for this predicate.
321 /// This property allows many common optimizations to be performed in the
322 /// absence of interfering store instructions, such as CSE of strlen calls.
324 /// This property corresponds to the GCC 'pure' attribute.
325 bool onlyReadsMemory(const Function *F) {
326 return onlyReadsMemory(getModRefBehavior(F));
329 /// Checks if functions with the specified behavior are known to only read
330 /// from non-volatile memory (or not access memory at all).
331 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
332 return !(MRB & MRI_Mod);
335 /// Checks if functions with the specified behavior are known to read and
336 /// write at most from objects pointed to by their pointer-typed arguments
337 /// (with arbitrary offsets).
338 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
339 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
342 /// Checks if functions with the specified behavior are known to potentially
343 /// read or write from objects pointed to be their pointer-typed arguments
344 /// (with arbitrary offsets).
345 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
346 return (MRB & MRI_ModRef) && (MRB & FMRL_ArgumentPointees);
349 /// getModRefInfo (for call sites) - Return information about whether
350 /// a particular call site modifies or reads the specified memory location.
351 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
352 const MemoryLocation &Loc);
354 /// getModRefInfo (for call sites) - A convenience wrapper.
355 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
357 return getModRefInfo(CS, MemoryLocation(P, Size));
360 /// getModRefInfo (for calls) - Return information about whether
361 /// a particular call modifies or reads the specified memory location.
362 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
363 return getModRefInfo(ImmutableCallSite(C), Loc);
366 /// getModRefInfo (for calls) - A convenience wrapper.
367 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
368 return getModRefInfo(C, MemoryLocation(P, Size));
371 /// getModRefInfo (for invokes) - Return information about whether
372 /// a particular invoke modifies or reads the specified memory location.
373 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
374 return getModRefInfo(ImmutableCallSite(I), Loc);
377 /// getModRefInfo (for invokes) - A convenience wrapper.
378 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
379 return getModRefInfo(I, MemoryLocation(P, Size));
382 /// getModRefInfo (for loads) - Return information about whether
383 /// a particular load modifies or reads the specified memory location.
384 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
386 /// getModRefInfo (for loads) - A convenience wrapper.
387 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
388 return getModRefInfo(L, MemoryLocation(P, Size));
391 /// getModRefInfo (for stores) - Return information about whether
392 /// a particular store modifies or reads the specified memory location.
393 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
395 /// getModRefInfo (for stores) - A convenience wrapper.
396 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
397 return getModRefInfo(S, MemoryLocation(P, Size));
400 /// getModRefInfo (for fences) - Return information about whether
401 /// a particular store modifies or reads the specified memory location.
402 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
403 // Conservatively correct. (We could possibly be a bit smarter if
404 // Loc is a alloca that doesn't escape.)
408 /// getModRefInfo (for fences) - A convenience wrapper.
409 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
410 return getModRefInfo(S, MemoryLocation(P, Size));
413 /// getModRefInfo (for cmpxchges) - Return information about whether
414 /// a particular cmpxchg modifies or reads the specified memory location.
415 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
416 const MemoryLocation &Loc);
418 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
419 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
421 return getModRefInfo(CX, MemoryLocation(P, Size));
424 /// getModRefInfo (for atomicrmws) - Return information about whether
425 /// a particular atomicrmw modifies or reads the specified memory location.
426 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
428 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
429 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
431 return getModRefInfo(RMW, MemoryLocation(P, Size));
434 /// getModRefInfo (for va_args) - Return information about whether
435 /// a particular va_arg modifies or reads the specified memory location.
436 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
438 /// getModRefInfo (for va_args) - A convenience wrapper.
439 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
440 return getModRefInfo(I, MemoryLocation(P, Size));
443 /// Check whether or not an instruction may read or write memory (without
444 /// regard to a specific location).
446 /// For function calls, this delegates to the alias-analysis specific
447 /// call-site mod-ref behavior queries. Otherwise it delegates to the generic
448 /// mod ref information query without a location.
449 ModRefInfo getModRefInfo(const Instruction *I) {
450 if (auto CS = ImmutableCallSite(I)) {
451 auto MRB = getModRefBehavior(CS);
452 if (MRB & MRI_ModRef)
454 else if (MRB & MRI_Ref)
456 else if (MRB & MRI_Mod)
461 return getModRefInfo(I, MemoryLocation());
464 /// Check whether or not an instruction may read or write the specified
467 /// An instruction that doesn't read or write memory may be trivially LICM'd
470 /// This primarily delegates to specific helpers above.
471 ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
472 switch (I->getOpcode()) {
473 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
474 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
475 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
476 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
477 case Instruction::AtomicCmpXchg:
478 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
479 case Instruction::AtomicRMW:
480 return getModRefInfo((const AtomicRMWInst*)I, Loc);
481 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
482 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
488 /// A convenience wrapper for constructing the memory location.
489 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
491 return getModRefInfo(I, MemoryLocation(P, Size));
494 /// Return information about whether a call and an instruction may refer to
495 /// the same memory locations.
496 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
498 /// Return information about whether two call sites may refer to the same set
499 /// of memory locations. See the AA documentation for details:
500 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
501 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
502 ImmutableCallSite CS2);
504 /// Return information about whether a particular call site modifies or reads
505 /// the specified memory location.
506 ModRefInfo callCapturesBefore(const Instruction *I,
507 const MemoryLocation &MemLoc,
510 /// A convenience wrapper to synthesize a memory location.
511 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
512 uint64_t Size, DominatorTree *DT) {
513 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
517 //===--------------------------------------------------------------------===//
518 /// \name Higher level methods for querying mod/ref information.
521 /// Check if it is possible for execution of the specified basic block to
522 /// modify the location Loc.
523 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
525 /// A convenience wrapper synthesizing a memory location.
526 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
528 return canBasicBlockModify(BB, MemoryLocation(P, Size));
531 /// Check if it is possible for the execution of the specified instructions
532 /// to mod\ref (according to the mode) the location Loc.
534 /// The instructions to consider are all of the instructions in the range of
535 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
536 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
537 const MemoryLocation &Loc,
538 const ModRefInfo Mode);
540 /// A convenience wrapper synthesizing a memory location.
541 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
542 const Value *Ptr, uint64_t Size,
543 const ModRefInfo Mode) {
544 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
548 /// isNoAliasCall - Return true if this pointer is returned by a noalias
550 bool isNoAliasCall(const Value *V);
552 /// isNoAliasArgument - Return true if this is an argument with the noalias
554 bool isNoAliasArgument(const Value *V);
556 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
557 /// identifiable object. This returns true for:
558 /// Global Variables and Functions (but not Global Aliases)
560 /// ByVal and NoAlias Arguments
561 /// NoAlias returns (e.g. calls to malloc)
563 bool isIdentifiedObject(const Value *V);
565 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
566 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
567 /// Further, an IdentifiedFunctionLocal can not alias with any function
568 /// arguments other than itself, which is not necessarily true for
569 /// IdentifiedObjects.
570 bool isIdentifiedFunctionLocal(const Value *V);
572 } // End llvm namespace