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 //===--------------------------------------------------------------------===//
197 /// alias - 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 /// alias - A convenience wrapper.
205 AliasResult alias(const Value *V1, uint64_t V1Size,
206 const Value *V2, uint64_t V2Size) {
207 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
210 /// alias - A convenience wrapper.
211 AliasResult alias(const Value *V1, const Value *V2) {
212 return alias(V1, MemoryLocation::UnknownSize, V2,
213 MemoryLocation::UnknownSize);
216 /// isNoAlias - A trivial helper function to check to see if the specified
217 /// pointers are no-alias.
218 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
219 return alias(LocA, LocB) == NoAlias;
222 /// isNoAlias - A convenience wrapper.
223 bool isNoAlias(const Value *V1, uint64_t V1Size,
224 const Value *V2, uint64_t V2Size) {
225 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
228 /// isNoAlias - A convenience wrapper.
229 bool isNoAlias(const Value *V1, const Value *V2) {
230 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
233 /// isMustAlias - A convenience wrapper.
234 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
235 return alias(LocA, LocB) == MustAlias;
238 /// isMustAlias - A convenience wrapper.
239 bool isMustAlias(const Value *V1, const Value *V2) {
240 return alias(V1, 1, V2, 1) == MustAlias;
243 /// pointsToConstantMemory - If the specified memory location is
244 /// known to be constant, return true. If OrLocal is true and the
245 /// specified memory location is known to be "local" (derived from
246 /// an alloca), return true. Otherwise return false.
247 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
248 bool OrLocal = false);
250 /// pointsToConstantMemory - A convenient wrapper.
251 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
252 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
255 //===--------------------------------------------------------------------===//
256 /// Simple mod/ref information...
259 /// Get the ModRef info associated with a pointer argument of a callsite. The
260 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
261 /// that these bits do not necessarily account for the overall behavior of
262 /// the function, but rather only provide additional per-argument
264 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
266 /// getModRefBehavior - Return the behavior when calling the given call site.
267 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
269 /// getModRefBehavior - Return the behavior when calling the given function.
270 /// For use when the call site is not known.
271 virtual FunctionModRefBehavior getModRefBehavior(const Function *F);
273 /// doesNotAccessMemory - If the specified call is known to never read or
274 /// write memory, return true. If the call only reads from known-constant
275 /// memory, it is also legal to return true. Calls that unwind the stack
276 /// are legal for this predicate.
278 /// Many optimizations (such as CSE and LICM) can be performed on such calls
279 /// without worrying about aliasing properties, and many calls have this
280 /// property (e.g. calls to 'sin' and 'cos').
282 /// This property corresponds to the GCC 'const' attribute.
284 bool doesNotAccessMemory(ImmutableCallSite CS) {
285 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
288 /// doesNotAccessMemory - If the specified function is known to never read or
289 /// write memory, return true. For use when the call site is not known.
291 bool doesNotAccessMemory(const Function *F) {
292 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
295 /// onlyReadsMemory - If the specified call is known to only read from
296 /// non-volatile memory (or not access memory at all), return true. Calls
297 /// that unwind the stack are legal for this predicate.
299 /// This property allows many common optimizations to be performed in the
300 /// absence of interfering store instructions, such as CSE of strlen calls.
302 /// This property corresponds to the GCC 'pure' attribute.
304 bool onlyReadsMemory(ImmutableCallSite CS) {
305 return onlyReadsMemory(getModRefBehavior(CS));
308 /// onlyReadsMemory - If the specified function is known to only read from
309 /// non-volatile memory (or not access memory at all), return true. For use
310 /// when the call site is not known.
312 bool onlyReadsMemory(const Function *F) {
313 return onlyReadsMemory(getModRefBehavior(F));
316 /// onlyReadsMemory - Return true if functions with the specified behavior are
317 /// known to only read from non-volatile memory (or not access memory at all).
319 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
320 return !(MRB & MRI_Mod);
323 /// onlyAccessesArgPointees - Return true if functions with the specified
324 /// behavior are known to read and write at most from objects pointed to by
325 /// their pointer-typed arguments (with arbitrary offsets).
327 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
328 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
331 /// doesAccessArgPointees - Return true if functions with the specified
332 /// behavior are known to potentially read or write from objects pointed
333 /// to be their pointer-typed arguments (with arbitrary offsets).
335 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
336 return (MRB & MRI_ModRef) && (MRB & FMRL_ArgumentPointees);
339 /// getModRefInfo - Return information about whether or not an
340 /// instruction may read or write memory (without regard to a
341 /// specific location)
342 ModRefInfo getModRefInfo(const Instruction *I) {
343 if (auto CS = ImmutableCallSite(I)) {
344 auto MRB = getModRefBehavior(CS);
345 if (MRB & MRI_ModRef)
347 else if (MRB & MRI_Ref)
349 else if (MRB & MRI_Mod)
354 return getModRefInfo(I, MemoryLocation());
357 /// getModRefInfo - Return information about whether or not an instruction may
358 /// read or write the specified memory location. An instruction
359 /// that doesn't read or write memory may be trivially LICM'd for example.
360 ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
361 switch (I->getOpcode()) {
362 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
363 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
364 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
365 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
366 case Instruction::AtomicCmpXchg:
367 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
368 case Instruction::AtomicRMW:
369 return getModRefInfo((const AtomicRMWInst*)I, Loc);
370 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
371 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
377 /// getModRefInfo - A convenience wrapper.
378 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
380 return getModRefInfo(I, MemoryLocation(P, Size));
383 /// getModRefInfo (for call sites) - Return information about whether
384 /// a particular call site modifies or reads the specified memory location.
385 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
386 const MemoryLocation &Loc);
388 /// getModRefInfo (for call sites) - A convenience wrapper.
389 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
391 return getModRefInfo(CS, MemoryLocation(P, Size));
394 /// getModRefInfo (for calls) - Return information about whether
395 /// a particular call modifies or reads the specified memory location.
396 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
397 return getModRefInfo(ImmutableCallSite(C), Loc);
400 /// getModRefInfo (for calls) - A convenience wrapper.
401 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
402 return getModRefInfo(C, MemoryLocation(P, Size));
405 /// getModRefInfo (for invokes) - Return information about whether
406 /// a particular invoke modifies or reads the specified memory location.
407 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
408 return getModRefInfo(ImmutableCallSite(I), Loc);
411 /// getModRefInfo (for invokes) - A convenience wrapper.
412 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
413 return getModRefInfo(I, MemoryLocation(P, Size));
416 /// getModRefInfo (for loads) - Return information about whether
417 /// a particular load modifies or reads the specified memory location.
418 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
420 /// getModRefInfo (for loads) - A convenience wrapper.
421 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
422 return getModRefInfo(L, MemoryLocation(P, Size));
425 /// getModRefInfo (for stores) - Return information about whether
426 /// a particular store modifies or reads the specified memory location.
427 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
429 /// getModRefInfo (for stores) - A convenience wrapper.
430 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
431 return getModRefInfo(S, MemoryLocation(P, Size));
434 /// getModRefInfo (for fences) - Return information about whether
435 /// a particular store modifies or reads the specified memory location.
436 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
437 // Conservatively correct. (We could possibly be a bit smarter if
438 // Loc is a alloca that doesn't escape.)
442 /// getModRefInfo (for fences) - A convenience wrapper.
443 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
444 return getModRefInfo(S, MemoryLocation(P, Size));
447 /// getModRefInfo (for cmpxchges) - Return information about whether
448 /// a particular cmpxchg modifies or reads the specified memory location.
449 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
450 const MemoryLocation &Loc);
452 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
453 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
455 return getModRefInfo(CX, MemoryLocation(P, Size));
458 /// getModRefInfo (for atomicrmws) - Return information about whether
459 /// a particular atomicrmw modifies or reads the specified memory location.
460 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
462 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
463 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
465 return getModRefInfo(RMW, MemoryLocation(P, Size));
468 /// getModRefInfo (for va_args) - Return information about whether
469 /// a particular va_arg modifies or reads the specified memory location.
470 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
472 /// getModRefInfo (for va_args) - A convenience wrapper.
473 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
474 return getModRefInfo(I, MemoryLocation(P, Size));
476 /// getModRefInfo - Return information about whether a call and an instruction
477 /// may refer to the same memory locations.
478 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
480 /// getModRefInfo - Return information about whether two call sites may refer
481 /// to the same set of memory locations. See
482 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
484 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
485 ImmutableCallSite CS2);
487 /// callCapturesBefore - Return information about whether a particular call
488 /// site modifies or reads the specified memory location.
489 ModRefInfo callCapturesBefore(const Instruction *I,
490 const MemoryLocation &MemLoc,
493 /// callCapturesBefore - A convenience wrapper.
494 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
495 uint64_t Size, DominatorTree *DT) {
496 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
499 //===--------------------------------------------------------------------===//
500 /// Higher level methods for querying mod/ref information.
503 /// canBasicBlockModify - Return true if it is possible for execution of the
504 /// specified basic block to modify the location Loc.
505 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
507 /// canBasicBlockModify - A convenience wrapper.
508 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){
509 return canBasicBlockModify(BB, MemoryLocation(P, Size));
512 /// canInstructionRangeModRef - Return true if it is possible for the
513 /// execution of the specified instructions to mod\ref (according to the
514 /// mode) the location Loc. The instructions to consider are all
515 /// of the instructions in the range of [I1,I2] INCLUSIVE.
516 /// I1 and I2 must be in the same basic block.
517 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
518 const MemoryLocation &Loc,
519 const ModRefInfo Mode);
521 /// canInstructionRangeModRef - A convenience wrapper.
522 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
523 const Value *Ptr, uint64_t Size,
524 const ModRefInfo Mode) {
525 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
529 /// isNoAliasCall - Return true if this pointer is returned by a noalias
531 bool isNoAliasCall(const Value *V);
533 /// isNoAliasArgument - Return true if this is an argument with the noalias
535 bool isNoAliasArgument(const Value *V);
537 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
538 /// identifiable object. This returns true for:
539 /// Global Variables and Functions (but not Global Aliases)
541 /// ByVal and NoAlias Arguments
542 /// NoAlias returns (e.g. calls to malloc)
544 bool isIdentifiedObject(const Value *V);
546 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
547 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
548 /// Further, an IdentifiedFunctionLocal can not alias with any function
549 /// arguments other than itself, which is not necessarily true for
550 /// IdentifiedObjects.
551 bool isIdentifiedFunctionLocal(const Value *V);
553 } // End llvm namespace