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 IntrReadArgMem LLVM intrinsic flag.
215 OnlyReadsArgumentPointees = ArgumentPointees | Ref,
217 /// OnlyAccessesArgumentPointees - The only memory references in this
218 /// function (if it has any) are non-volatile loads and stores from objects
219 /// pointed to by its pointer-typed arguments, with arbitrary offsets.
221 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
222 OnlyAccessesArgumentPointees = ArgumentPointees | ModRef,
224 /// OnlyReadsMemory - This function does not perform any non-local stores or
225 /// volatile loads, but may read from any memory location.
227 /// This property corresponds to the GCC 'pure' attribute.
228 /// This property corresponds to the LLVM IR 'readonly' attribute.
229 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
230 OnlyReadsMemory = Anywhere | Ref,
232 /// UnknownModRefBehavior - This indicates that the function could not be
233 /// classified into one of the behaviors above.
234 UnknownModRefBehavior = Anywhere | ModRef
237 /// Get the ModRef info associated with a pointer argument of a callsite. The
238 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
239 /// that these bits do not necessarily account for the overall behavior of
240 /// the function, but rather only provide additional per-argument
242 virtual ModRefResult getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
244 /// getModRefBehavior - Return the behavior when calling the given call site.
245 virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
247 /// getModRefBehavior - Return the behavior when calling the given function.
248 /// For use when the call site is not known.
249 virtual ModRefBehavior getModRefBehavior(const Function *F);
251 /// doesNotAccessMemory - If the specified call is known to never read or
252 /// write memory, return true. If the call only reads from known-constant
253 /// memory, it is also legal to return true. Calls that unwind the stack
254 /// are legal for this predicate.
256 /// Many optimizations (such as CSE and LICM) can be performed on such calls
257 /// without worrying about aliasing properties, and many calls have this
258 /// property (e.g. calls to 'sin' and 'cos').
260 /// This property corresponds to the GCC 'const' attribute.
262 bool doesNotAccessMemory(ImmutableCallSite CS) {
263 return getModRefBehavior(CS) == DoesNotAccessMemory;
266 /// doesNotAccessMemory - If the specified function is known to never read or
267 /// write memory, return true. For use when the call site is not known.
269 bool doesNotAccessMemory(const Function *F) {
270 return getModRefBehavior(F) == DoesNotAccessMemory;
273 /// onlyReadsMemory - If the specified call is known to only read from
274 /// non-volatile memory (or not access memory at all), return true. Calls
275 /// that unwind the stack are legal for this predicate.
277 /// This property allows many common optimizations to be performed in the
278 /// absence of interfering store instructions, such as CSE of strlen calls.
280 /// This property corresponds to the GCC 'pure' attribute.
282 bool onlyReadsMemory(ImmutableCallSite CS) {
283 return onlyReadsMemory(getModRefBehavior(CS));
286 /// onlyReadsMemory - If the specified function is known to only read from
287 /// non-volatile memory (or not access memory at all), return true. For use
288 /// when the call site is not known.
290 bool onlyReadsMemory(const Function *F) {
291 return onlyReadsMemory(getModRefBehavior(F));
294 /// onlyReadsMemory - Return true if functions with the specified behavior are
295 /// known to only read from non-volatile memory (or not access memory at all).
297 static bool onlyReadsMemory(ModRefBehavior MRB) {
301 /// onlyAccessesArgPointees - Return true if functions with the specified
302 /// behavior are known to read and write at most from objects pointed to by
303 /// their pointer-typed arguments (with arbitrary offsets).
305 static bool onlyAccessesArgPointees(ModRefBehavior MRB) {
306 return !(MRB & Anywhere & ~ArgumentPointees);
309 /// doesAccessArgPointees - Return true if functions with the specified
310 /// behavior are known to potentially read or write from objects pointed
311 /// to be their pointer-typed arguments (with arbitrary offsets).
313 static bool doesAccessArgPointees(ModRefBehavior MRB) {
314 return (MRB & ModRef) && (MRB & ArgumentPointees);
317 /// getModRefInfo - Return information about whether or not an
318 /// instruction may read or write memory (without regard to a
319 /// specific location)
320 ModRefResult getModRefInfo(const Instruction *I) {
321 if (auto CS = ImmutableCallSite(I)) {
322 auto MRB = getModRefBehavior(CS);
332 return getModRefInfo(I, MemoryLocation());
335 /// getModRefInfo - Return information about whether or not an instruction may
336 /// read or write the specified memory location. An instruction
337 /// that doesn't read or write memory may be trivially LICM'd for example.
338 ModRefResult getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
339 switch (I->getOpcode()) {
340 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
341 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
342 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
343 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
344 case Instruction::AtomicCmpXchg:
345 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
346 case Instruction::AtomicRMW:
347 return getModRefInfo((const AtomicRMWInst*)I, Loc);
348 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
349 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
350 default: return NoModRef;
354 /// getModRefInfo - A convenience wrapper.
355 ModRefResult getModRefInfo(const Instruction *I,
356 const Value *P, uint64_t Size) {
357 return getModRefInfo(I, MemoryLocation(P, Size));
360 /// getModRefInfo (for call sites) - Return information about whether
361 /// a particular call site modifies or reads the specified memory location.
362 virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
363 const MemoryLocation &Loc);
365 /// getModRefInfo (for call sites) - A convenience wrapper.
366 ModRefResult getModRefInfo(ImmutableCallSite CS,
367 const Value *P, uint64_t Size) {
368 return getModRefInfo(CS, MemoryLocation(P, Size));
371 /// getModRefInfo (for calls) - Return information about whether
372 /// a particular call modifies or reads the specified memory location.
373 ModRefResult getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
374 return getModRefInfo(ImmutableCallSite(C), Loc);
377 /// getModRefInfo (for calls) - A convenience wrapper.
378 ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
379 return getModRefInfo(C, MemoryLocation(P, Size));
382 /// getModRefInfo (for invokes) - Return information about whether
383 /// a particular invoke modifies or reads the specified memory location.
384 ModRefResult getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
385 return getModRefInfo(ImmutableCallSite(I), Loc);
388 /// getModRefInfo (for invokes) - A convenience wrapper.
389 ModRefResult getModRefInfo(const InvokeInst *I,
390 const Value *P, uint64_t Size) {
391 return getModRefInfo(I, MemoryLocation(P, Size));
394 /// getModRefInfo (for loads) - Return information about whether
395 /// a particular load modifies or reads the specified memory location.
396 ModRefResult getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
398 /// getModRefInfo (for loads) - A convenience wrapper.
399 ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
400 return getModRefInfo(L, MemoryLocation(P, Size));
403 /// getModRefInfo (for stores) - Return information about whether
404 /// a particular store modifies or reads the specified memory location.
405 ModRefResult getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
407 /// getModRefInfo (for stores) - A convenience wrapper.
408 ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){
409 return getModRefInfo(S, MemoryLocation(P, Size));
412 /// getModRefInfo (for fences) - Return information about whether
413 /// a particular store modifies or reads the specified memory location.
414 ModRefResult getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
415 // Conservatively correct. (We could possibly be a bit smarter if
416 // Loc is a alloca that doesn't escape.)
420 /// getModRefInfo (for fences) - A convenience wrapper.
421 ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){
422 return getModRefInfo(S, MemoryLocation(P, Size));
425 /// getModRefInfo (for cmpxchges) - Return information about whether
426 /// a particular cmpxchg modifies or reads the specified memory location.
427 ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX,
428 const MemoryLocation &Loc);
430 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
431 ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX,
432 const Value *P, unsigned Size) {
433 return getModRefInfo(CX, MemoryLocation(P, Size));
436 /// getModRefInfo (for atomicrmws) - Return information about whether
437 /// a particular atomicrmw modifies or reads the specified memory location.
438 ModRefResult getModRefInfo(const AtomicRMWInst *RMW,
439 const MemoryLocation &Loc);
441 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
442 ModRefResult getModRefInfo(const AtomicRMWInst *RMW,
443 const Value *P, unsigned Size) {
444 return getModRefInfo(RMW, MemoryLocation(P, Size));
447 /// getModRefInfo (for va_args) - Return information about whether
448 /// a particular va_arg modifies or reads the specified memory location.
449 ModRefResult getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
451 /// getModRefInfo (for va_args) - A convenience wrapper.
452 ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){
453 return getModRefInfo(I, MemoryLocation(P, Size));
455 /// getModRefInfo - Return information about whether a call and an instruction
456 /// may refer to the same memory locations.
457 ModRefResult getModRefInfo(Instruction *I,
458 ImmutableCallSite Call);
460 /// getModRefInfo - Return information about whether two call sites may refer
461 /// to the same set of memory locations. See
462 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
464 virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
465 ImmutableCallSite CS2);
467 /// callCapturesBefore - Return information about whether a particular call
468 /// site modifies or reads the specified memory location.
469 ModRefResult callCapturesBefore(const Instruction *I,
470 const MemoryLocation &MemLoc,
473 /// callCapturesBefore - A convenience wrapper.
474 ModRefResult callCapturesBefore(const Instruction *I, const Value *P,
475 uint64_t Size, DominatorTree *DT) {
476 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
479 //===--------------------------------------------------------------------===//
480 /// Higher level methods for querying mod/ref information.
483 /// canBasicBlockModify - Return true if it is possible for execution of the
484 /// specified basic block to modify the location Loc.
485 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
487 /// canBasicBlockModify - A convenience wrapper.
488 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){
489 return canBasicBlockModify(BB, MemoryLocation(P, Size));
492 /// canInstructionRangeModRef - Return true if it is possible for the
493 /// execution of the specified instructions to mod\ref (according to the
494 /// mode) the location Loc. The instructions to consider are all
495 /// of the instructions in the range of [I1,I2] INCLUSIVE.
496 /// I1 and I2 must be in the same basic block.
497 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
498 const MemoryLocation &Loc,
499 const ModRefResult Mode);
501 /// canInstructionRangeModRef - A convenience wrapper.
502 bool canInstructionRangeModRef(const Instruction &I1,
503 const Instruction &I2, const Value *Ptr,
504 uint64_t Size, const ModRefResult Mode) {
505 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
508 //===--------------------------------------------------------------------===//
509 /// Methods that clients should call when they transform the program to allow
510 /// alias analyses to update their internal data structures. Note that these
511 /// methods may be called on any instruction, regardless of whether or not
512 /// they have pointer-analysis implications.
515 /// deleteValue - This method should be called whenever an LLVM Value is
516 /// deleted from the program, for example when an instruction is found to be
517 /// redundant and is eliminated.
519 virtual void deleteValue(Value *V);
521 /// copyValue - This method should be used whenever a preexisting value in the
522 /// program is copied or cloned, introducing a new value. Note that analysis
523 /// implementations should tolerate clients that use this method to introduce
524 /// the same value multiple times: if the analysis already knows about a
525 /// value, it should ignore the request.
527 virtual void copyValue(Value *From, Value *To);
529 /// addEscapingUse - This method should be used whenever an escaping use is
530 /// added to a pointer value. Analysis implementations may either return
531 /// conservative responses for that value in the future, or may recompute
532 /// some or all internal state to continue providing precise responses.
534 /// Escaping uses are considered by anything _except_ the following:
535 /// - GEPs or bitcasts of the pointer
536 /// - Loads through the pointer
537 /// - Stores through (but not of) the pointer
538 virtual void addEscapingUse(Use &U);
540 /// replaceWithNewValue - This method is the obvious combination of the two
541 /// above, and it provided as a helper to simplify client code.
543 void replaceWithNewValue(Value *Old, Value *New) {
549 /// isNoAliasCall - Return true if this pointer is returned by a noalias
551 bool isNoAliasCall(const Value *V);
553 /// isNoAliasArgument - Return true if this is an argument with the noalias
555 bool isNoAliasArgument(const Value *V);
557 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
558 /// identifiable object. This returns true for:
559 /// Global Variables and Functions (but not Global Aliases)
561 /// ByVal and NoAlias Arguments
562 /// NoAlias returns (e.g. calls to malloc)
564 bool isIdentifiedObject(const Value *V);
566 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
567 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
568 /// Further, an IdentifiedFunctionLocal can not alias with any function
569 /// arguments other than itself, which is not necessarily true for
570 /// IdentifiedObjects.
571 bool isIdentifiedFunctionLocal(const Value *V);