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.
90 const TargetLibraryInfo *TLI;
93 AliasAnalysis *AA; // Previous Alias Analysis to chain to.
96 /// InitializeAliasAnalysis - Subclasses must call this method to initialize
97 /// the AliasAnalysis interface before any other methods are called. This is
98 /// typically called by the run* methods of these subclasses. This may be
99 /// called multiple times.
101 void InitializeAliasAnalysis(Pass *P, const DataLayout *DL);
103 /// getAnalysisUsage - All alias analysis implementations should invoke this
104 /// directly (using AliasAnalysis::getAnalysisUsage(AU)).
105 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
108 static char ID; // Class identification, replacement for typeinfo
109 AliasAnalysis() : DL(nullptr), TLI(nullptr), AA(nullptr) {}
110 virtual ~AliasAnalysis(); // We want to be subclassed
112 /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo
113 /// object, or null if no TargetLibraryInfo object is available.
115 const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; }
117 /// getTypeStoreSize - Return the DataLayout store size for the given type,
118 /// if known, or a conservative value otherwise.
120 uint64_t getTypeStoreSize(Type *Ty);
122 //===--------------------------------------------------------------------===//
126 /// alias - The main low level interface to the alias analysis implementation.
127 /// Returns an AliasResult indicating whether the two pointers are aliased to
128 /// each other. This is the interface that must be implemented by specific
129 /// alias analysis implementations.
130 virtual AliasResult alias(const MemoryLocation &LocA,
131 const MemoryLocation &LocB);
133 /// alias - A convenience wrapper.
134 AliasResult alias(const Value *V1, uint64_t V1Size,
135 const Value *V2, uint64_t V2Size) {
136 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
139 /// alias - A convenience wrapper.
140 AliasResult alias(const Value *V1, const Value *V2) {
141 return alias(V1, MemoryLocation::UnknownSize, V2,
142 MemoryLocation::UnknownSize);
145 /// isNoAlias - A trivial helper function to check to see if the specified
146 /// pointers are no-alias.
147 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
148 return alias(LocA, LocB) == NoAlias;
151 /// isNoAlias - A convenience wrapper.
152 bool isNoAlias(const Value *V1, uint64_t V1Size,
153 const Value *V2, uint64_t V2Size) {
154 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
157 /// isNoAlias - A convenience wrapper.
158 bool isNoAlias(const Value *V1, const Value *V2) {
159 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
162 /// isMustAlias - A convenience wrapper.
163 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
164 return alias(LocA, LocB) == MustAlias;
167 /// isMustAlias - A convenience wrapper.
168 bool isMustAlias(const Value *V1, const Value *V2) {
169 return alias(V1, 1, V2, 1) == MustAlias;
172 /// pointsToConstantMemory - If the specified memory location is
173 /// known to be constant, return true. If OrLocal is true and the
174 /// specified memory location is known to be "local" (derived from
175 /// an alloca), return true. Otherwise return false.
176 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
177 bool OrLocal = false);
179 /// pointsToConstantMemory - A convenient wrapper.
180 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
181 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
184 //===--------------------------------------------------------------------===//
185 /// Simple mod/ref information...
188 /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are
189 /// bits which may be or'd together.
191 enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
193 /// These values define additional bits used to define the
194 /// ModRefBehavior values.
195 enum { Nowhere = 0, ArgumentPointees = 4, Anywhere = 8 | ArgumentPointees };
197 /// ModRefBehavior - Summary of how a function affects memory in the program.
198 /// Loads from constant globals are not considered memory accesses for this
199 /// interface. Also, functions may freely modify stack space local to their
200 /// invocation without having to report it through these interfaces.
201 enum ModRefBehavior {
202 /// DoesNotAccessMemory - This function does not perform any non-local loads
203 /// or stores to memory.
205 /// This property corresponds to the GCC 'const' attribute.
206 /// This property corresponds to the LLVM IR 'readnone' attribute.
207 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
208 DoesNotAccessMemory = Nowhere | NoModRef,
210 /// OnlyReadsArgumentPointees - The only memory references in this function
211 /// (if it has any) are non-volatile loads from objects pointed to by its
212 /// pointer-typed arguments, with arbitrary offsets.
214 /// This property corresponds to the LLVM IR 'argmemonly' attribute combined
215 /// with 'readonly' attribute.
216 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
217 OnlyReadsArgumentPointees = ArgumentPointees | Ref,
219 /// OnlyAccessesArgumentPointees - The only memory references in this
220 /// function (if it has any) are non-volatile loads and stores from objects
221 /// pointed to by its pointer-typed arguments, with arbitrary offsets.
223 /// This property corresponds to the LLVM IR 'argmemonly' attribute.
224 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
225 OnlyAccessesArgumentPointees = ArgumentPointees | ModRef,
227 /// OnlyReadsMemory - This function does not perform any non-local stores or
228 /// volatile loads, but may read from any memory location.
230 /// This property corresponds to the GCC 'pure' attribute.
231 /// This property corresponds to the LLVM IR 'readonly' attribute.
232 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
233 OnlyReadsMemory = Anywhere | Ref,
235 /// UnknownModRefBehavior - This indicates that the function could not be
236 /// classified into one of the behaviors above.
237 UnknownModRefBehavior = Anywhere | ModRef
240 /// Get the ModRef info associated with a pointer argument of a callsite. The
241 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
242 /// that these bits do not necessarily account for the overall behavior of
243 /// the function, but rather only provide additional per-argument
245 virtual ModRefResult getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
247 /// getModRefBehavior - Return the behavior when calling the given call site.
248 virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
250 /// getModRefBehavior - Return the behavior when calling the given function.
251 /// For use when the call site is not known.
252 virtual ModRefBehavior getModRefBehavior(const Function *F);
254 /// doesNotAccessMemory - If the specified call is known to never read or
255 /// write memory, return true. If the call only reads from known-constant
256 /// memory, it is also legal to return true. Calls that unwind the stack
257 /// are legal for this predicate.
259 /// Many optimizations (such as CSE and LICM) can be performed on such calls
260 /// without worrying about aliasing properties, and many calls have this
261 /// property (e.g. calls to 'sin' and 'cos').
263 /// This property corresponds to the GCC 'const' attribute.
265 bool doesNotAccessMemory(ImmutableCallSite CS) {
266 return getModRefBehavior(CS) == DoesNotAccessMemory;
269 /// doesNotAccessMemory - If the specified function is known to never read or
270 /// write memory, return true. For use when the call site is not known.
272 bool doesNotAccessMemory(const Function *F) {
273 return getModRefBehavior(F) == DoesNotAccessMemory;
276 /// onlyReadsMemory - If the specified call is known to only read from
277 /// non-volatile memory (or not access memory at all), return true. Calls
278 /// that unwind the stack are legal for this predicate.
280 /// This property allows many common optimizations to be performed in the
281 /// absence of interfering store instructions, such as CSE of strlen calls.
283 /// This property corresponds to the GCC 'pure' attribute.
285 bool onlyReadsMemory(ImmutableCallSite CS) {
286 return onlyReadsMemory(getModRefBehavior(CS));
289 /// onlyReadsMemory - If the specified function is known to only read from
290 /// non-volatile memory (or not access memory at all), return true. For use
291 /// when the call site is not known.
293 bool onlyReadsMemory(const Function *F) {
294 return onlyReadsMemory(getModRefBehavior(F));
297 /// onlyReadsMemory - Return true if functions with the specified behavior are
298 /// known to only read from non-volatile memory (or not access memory at all).
300 static bool onlyReadsMemory(ModRefBehavior MRB) {
304 /// onlyAccessesArgPointees - Return true if functions with the specified
305 /// behavior are known to read and write at most from objects pointed to by
306 /// their pointer-typed arguments (with arbitrary offsets).
308 static bool onlyAccessesArgPointees(ModRefBehavior MRB) {
309 return !(MRB & Anywhere & ~ArgumentPointees);
312 /// doesAccessArgPointees - Return true if functions with the specified
313 /// behavior are known to potentially read or write from objects pointed
314 /// to be their pointer-typed arguments (with arbitrary offsets).
316 static bool doesAccessArgPointees(ModRefBehavior MRB) {
317 return (MRB & ModRef) && (MRB & ArgumentPointees);
320 /// getModRefInfo - Return information about whether or not an
321 /// instruction may read or write memory (without regard to a
322 /// specific location)
323 ModRefResult getModRefInfo(const Instruction *I) {
324 if (auto CS = ImmutableCallSite(I)) {
325 auto MRB = getModRefBehavior(CS);
335 return getModRefInfo(I, MemoryLocation());
338 /// getModRefInfo - Return information about whether or not an instruction may
339 /// read or write the specified memory location. An instruction
340 /// that doesn't read or write memory may be trivially LICM'd for example.
341 ModRefResult getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
342 switch (I->getOpcode()) {
343 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
344 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
345 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
346 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
347 case Instruction::AtomicCmpXchg:
348 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
349 case Instruction::AtomicRMW:
350 return getModRefInfo((const AtomicRMWInst*)I, Loc);
351 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
352 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
353 default: return NoModRef;
357 /// getModRefInfo - A convenience wrapper.
358 ModRefResult getModRefInfo(const Instruction *I,
359 const Value *P, uint64_t Size) {
360 return getModRefInfo(I, MemoryLocation(P, Size));
363 /// getModRefInfo (for call sites) - Return information about whether
364 /// a particular call site modifies or reads the specified memory location.
365 virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
366 const MemoryLocation &Loc);
368 /// getModRefInfo (for call sites) - A convenience wrapper.
369 ModRefResult getModRefInfo(ImmutableCallSite CS,
370 const Value *P, uint64_t Size) {
371 return getModRefInfo(CS, MemoryLocation(P, Size));
374 /// getModRefInfo (for calls) - Return information about whether
375 /// a particular call modifies or reads the specified memory location.
376 ModRefResult getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
377 return getModRefInfo(ImmutableCallSite(C), Loc);
380 /// getModRefInfo (for calls) - A convenience wrapper.
381 ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
382 return getModRefInfo(C, MemoryLocation(P, Size));
385 /// getModRefInfo (for invokes) - Return information about whether
386 /// a particular invoke modifies or reads the specified memory location.
387 ModRefResult getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
388 return getModRefInfo(ImmutableCallSite(I), Loc);
391 /// getModRefInfo (for invokes) - A convenience wrapper.
392 ModRefResult getModRefInfo(const InvokeInst *I,
393 const Value *P, uint64_t Size) {
394 return getModRefInfo(I, MemoryLocation(P, Size));
397 /// getModRefInfo (for loads) - Return information about whether
398 /// a particular load modifies or reads the specified memory location.
399 ModRefResult getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
401 /// getModRefInfo (for loads) - A convenience wrapper.
402 ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
403 return getModRefInfo(L, MemoryLocation(P, Size));
406 /// getModRefInfo (for stores) - Return information about whether
407 /// a particular store modifies or reads the specified memory location.
408 ModRefResult getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
410 /// getModRefInfo (for stores) - A convenience wrapper.
411 ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){
412 return getModRefInfo(S, MemoryLocation(P, Size));
415 /// getModRefInfo (for fences) - Return information about whether
416 /// a particular store modifies or reads the specified memory location.
417 ModRefResult getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
418 // Conservatively correct. (We could possibly be a bit smarter if
419 // Loc is a alloca that doesn't escape.)
423 /// getModRefInfo (for fences) - A convenience wrapper.
424 ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){
425 return getModRefInfo(S, MemoryLocation(P, Size));
428 /// getModRefInfo (for cmpxchges) - Return information about whether
429 /// a particular cmpxchg modifies or reads the specified memory location.
430 ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX,
431 const MemoryLocation &Loc);
433 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
434 ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX,
435 const Value *P, unsigned Size) {
436 return getModRefInfo(CX, MemoryLocation(P, Size));
439 /// getModRefInfo (for atomicrmws) - Return information about whether
440 /// a particular atomicrmw modifies or reads the specified memory location.
441 ModRefResult getModRefInfo(const AtomicRMWInst *RMW,
442 const MemoryLocation &Loc);
444 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
445 ModRefResult getModRefInfo(const AtomicRMWInst *RMW,
446 const Value *P, unsigned Size) {
447 return getModRefInfo(RMW, MemoryLocation(P, Size));
450 /// getModRefInfo (for va_args) - Return information about whether
451 /// a particular va_arg modifies or reads the specified memory location.
452 ModRefResult getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
454 /// getModRefInfo (for va_args) - A convenience wrapper.
455 ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){
456 return getModRefInfo(I, MemoryLocation(P, Size));
458 /// getModRefInfo - Return information about whether a call and an instruction
459 /// may refer to the same memory locations.
460 ModRefResult getModRefInfo(Instruction *I,
461 ImmutableCallSite Call);
463 /// getModRefInfo - Return information about whether two call sites may refer
464 /// to the same set of memory locations. See
465 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
467 virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
468 ImmutableCallSite CS2);
470 /// callCapturesBefore - Return information about whether a particular call
471 /// site modifies or reads the specified memory location.
472 ModRefResult callCapturesBefore(const Instruction *I,
473 const MemoryLocation &MemLoc,
476 /// callCapturesBefore - A convenience wrapper.
477 ModRefResult callCapturesBefore(const Instruction *I, const Value *P,
478 uint64_t Size, DominatorTree *DT) {
479 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
482 //===--------------------------------------------------------------------===//
483 /// Higher level methods for querying mod/ref information.
486 /// canBasicBlockModify - Return true if it is possible for execution of the
487 /// specified basic block to modify the location Loc.
488 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
490 /// canBasicBlockModify - A convenience wrapper.
491 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){
492 return canBasicBlockModify(BB, MemoryLocation(P, Size));
495 /// canInstructionRangeModRef - Return true if it is possible for the
496 /// execution of the specified instructions to mod\ref (according to the
497 /// mode) the location Loc. The instructions to consider are all
498 /// of the instructions in the range of [I1,I2] INCLUSIVE.
499 /// I1 and I2 must be in the same basic block.
500 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
501 const MemoryLocation &Loc,
502 const ModRefResult Mode);
504 /// canInstructionRangeModRef - A convenience wrapper.
505 bool canInstructionRangeModRef(const Instruction &I1,
506 const Instruction &I2, const Value *Ptr,
507 uint64_t Size, const ModRefResult Mode) {
508 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
512 /// isNoAliasCall - Return true if this pointer is returned by a noalias
514 bool isNoAliasCall(const Value *V);
516 /// isNoAliasArgument - Return true if this is an argument with the noalias
518 bool isNoAliasArgument(const Value *V);
520 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
521 /// identifiable object. This returns true for:
522 /// Global Variables and Functions (but not Global Aliases)
524 /// ByVal and NoAlias Arguments
525 /// NoAlias returns (e.g. calls to malloc)
527 bool isIdentifiedObject(const Value *V);
529 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
530 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
531 /// Further, an IdentifiedFunctionLocal can not alias with any function
532 /// arguments other than itself, which is not necessarily true for
533 /// IdentifiedObjects.
534 bool isIdentifiedFunctionLocal(const Value *V);
536 } // End llvm namespace