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 Location 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 UnknownSize if
22 // the size is not known. The TBAA tag identifies the "type" of the memory
23 // reference; see the TypeBasedAliasAnalysis class for details.
25 // Some non-obvious details include:
26 // - Pointers that point to two completely different objects in memory never
27 // alias, regardless of the value of the Size component.
28 // - NoAlias doesn't imply inequal pointers. The most obvious example of this
29 // is two pointers to constant memory. Even if they are equal, constant
30 // memory is never stored to, so there will never be any dependencies.
31 // In this and other situations, the pointers may be both NoAlias and
32 // MustAlias at the same time. The current API can only return one result,
33 // though this is rarely a problem in practice.
35 //===----------------------------------------------------------------------===//
37 #ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
38 #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
40 #include "llvm/Support/CallSite.h"
41 #include "llvm/ADT/DenseMap.h"
49 class TargetLibraryInfo
;
52 class MemTransferInst
;
59 const TargetLibraryInfo
*TLI
;
62 AliasAnalysis
*AA
; // Previous Alias Analysis to chain to.
65 /// InitializeAliasAnalysis - Subclasses must call this method to initialize
66 /// the AliasAnalysis interface before any other methods are called. This is
67 /// typically called by the run* methods of these subclasses. This may be
68 /// called multiple times.
70 void InitializeAliasAnalysis(Pass
*P
);
72 /// getAnalysisUsage - All alias analysis implementations should invoke this
73 /// directly (using AliasAnalysis::getAnalysisUsage(AU)).
74 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const;
77 static char ID
; // Class identification, replacement for typeinfo
78 AliasAnalysis() : TD(0), TLI(0), AA(0) {}
79 virtual ~AliasAnalysis(); // We want to be subclassed
81 /// UnknownSize - This is a special value which can be used with the
82 /// size arguments in alias queries to indicate that the caller does not
83 /// know the sizes of the potential memory references.
84 static uint64_t const UnknownSize
= ~UINT64_C(0);
86 /// getTargetData - Return a pointer to the current TargetData object, or
87 /// null if no TargetData object is available.
89 const TargetData
*getTargetData() const { return TD
; }
91 /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo
92 /// object, or null if no TargetLibraryInfo object is available.
94 const TargetLibraryInfo
*getTargetLibraryInfo() const { return TLI
; }
96 /// getTypeStoreSize - Return the TargetData store size for the given type,
97 /// if known, or a conservative value otherwise.
99 uint64_t getTypeStoreSize(Type
*Ty
);
101 //===--------------------------------------------------------------------===//
105 /// Location - A description of a memory location.
107 /// Ptr - The address of the start of the location.
109 /// Size - The maximum size of the location, in address-units, or
110 /// UnknownSize if the size is not known. Note that an unknown size does
111 /// not mean the pointer aliases the entire virtual address space, because
112 /// there are restrictions on stepping out of one object and into another.
113 /// See http://llvm.org/docs/LangRef.html#pointeraliasing
115 /// TBAATag - The metadata node which describes the TBAA type of
116 /// the location, or null if there is no known unique tag.
117 const MDNode
*TBAATag
;
119 explicit Location(const Value
*P
= 0, uint64_t S
= UnknownSize
,
121 : Ptr(P
), Size(S
), TBAATag(N
) {}
123 Location
getWithNewPtr(const Value
*NewPtr
) const {
124 Location
Copy(*this);
129 Location
getWithNewSize(uint64_t NewSize
) const {
130 Location
Copy(*this);
135 Location
getWithoutTBAATag() const {
136 Location
Copy(*this);
142 /// getLocation - Fill in Loc with information about the memory reference by
143 /// the given instruction.
144 Location
getLocation(const LoadInst
*LI
);
145 Location
getLocation(const StoreInst
*SI
);
146 Location
getLocation(const VAArgInst
*VI
);
147 Location
getLocation(const AtomicCmpXchgInst
*CXI
);
148 Location
getLocation(const AtomicRMWInst
*RMWI
);
149 static Location
getLocationForSource(const MemTransferInst
*MTI
);
150 static Location
getLocationForDest(const MemIntrinsic
*MI
);
152 /// Alias analysis result - Either we know for sure that it does not alias, we
153 /// know for sure it must alias, or we don't know anything: The two pointers
154 /// _might_ alias. This enum is designed so you can do things like:
155 /// if (AA.alias(P1, P2)) { ... }
156 /// to check to see if two pointers might alias.
158 /// See docs/AliasAnalysis.html for more information on the specific meanings
162 NoAlias
= 0, ///< No dependencies.
163 MayAlias
, ///< Anything goes.
164 PartialAlias
, ///< Pointers differ, but pointees overlap.
165 MustAlias
///< Pointers are equal.
168 /// alias - The main low level interface to the alias analysis implementation.
169 /// Returns an AliasResult indicating whether the two pointers are aliased to
170 /// each other. This is the interface that must be implemented by specific
171 /// alias analysis implementations.
172 virtual AliasResult
alias(const Location
&LocA
, const Location
&LocB
);
174 /// alias - A convenience wrapper.
175 AliasResult
alias(const Value
*V1
, uint64_t V1Size
,
176 const Value
*V2
, uint64_t V2Size
) {
177 return alias(Location(V1
, V1Size
), Location(V2
, V2Size
));
180 /// alias - A convenience wrapper.
181 AliasResult
alias(const Value
*V1
, const Value
*V2
) {
182 return alias(V1
, UnknownSize
, V2
, UnknownSize
);
185 /// isNoAlias - A trivial helper function to check to see if the specified
186 /// pointers are no-alias.
187 bool isNoAlias(const Location
&LocA
, const Location
&LocB
) {
188 return alias(LocA
, LocB
) == NoAlias
;
191 /// isNoAlias - A convenience wrapper.
192 bool isNoAlias(const Value
*V1
, uint64_t V1Size
,
193 const Value
*V2
, uint64_t V2Size
) {
194 return isNoAlias(Location(V1
, V1Size
), Location(V2
, V2Size
));
197 /// isNoAlias - A convenience wrapper.
198 bool isNoAlias(const Value
*V1
, const Value
*V2
) {
199 return isNoAlias(Location(V1
), Location(V2
));
202 /// isMustAlias - A convenience wrapper.
203 bool isMustAlias(const Location
&LocA
, const Location
&LocB
) {
204 return alias(LocA
, LocB
) == MustAlias
;
207 /// isMustAlias - A convenience wrapper.
208 bool isMustAlias(const Value
*V1
, const Value
*V2
) {
209 return alias(V1
, 1, V2
, 1) == MustAlias
;
212 /// pointsToConstantMemory - If the specified memory location is
213 /// known to be constant, return true. If OrLocal is true and the
214 /// specified memory location is known to be "local" (derived from
215 /// an alloca), return true. Otherwise return false.
216 virtual bool pointsToConstantMemory(const Location
&Loc
,
217 bool OrLocal
= false);
219 /// pointsToConstantMemory - A convenient wrapper.
220 bool pointsToConstantMemory(const Value
*P
, bool OrLocal
= false) {
221 return pointsToConstantMemory(Location(P
), OrLocal
);
224 //===--------------------------------------------------------------------===//
225 /// Simple mod/ref information...
228 /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are
229 /// bits which may be or'd together.
231 enum ModRefResult
{ NoModRef
= 0, Ref
= 1, Mod
= 2, ModRef
= 3 };
233 /// These values define additional bits used to define the
234 /// ModRefBehavior values.
235 enum { Nowhere
= 0, ArgumentPointees
= 4, Anywhere
= 8 | ArgumentPointees
};
237 /// ModRefBehavior - Summary of how a function affects memory in the program.
238 /// Loads from constant globals are not considered memory accesses for this
239 /// interface. Also, functions may freely modify stack space local to their
240 /// invocation without having to report it through these interfaces.
241 enum ModRefBehavior
{
242 /// DoesNotAccessMemory - This function does not perform any non-local loads
243 /// or stores to memory.
245 /// This property corresponds to the GCC 'const' attribute.
246 /// This property corresponds to the LLVM IR 'readnone' attribute.
247 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
248 DoesNotAccessMemory
= Nowhere
| NoModRef
,
250 /// OnlyReadsArgumentPointees - The only memory references in this function
251 /// (if it has any) are non-volatile loads from objects pointed to by its
252 /// pointer-typed arguments, with arbitrary offsets.
254 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
255 OnlyReadsArgumentPointees
= ArgumentPointees
| Ref
,
257 /// OnlyAccessesArgumentPointees - The only memory references in this
258 /// function (if it has any) are non-volatile loads and stores from objects
259 /// pointed to by its pointer-typed arguments, with arbitrary offsets.
261 /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag.
262 OnlyAccessesArgumentPointees
= ArgumentPointees
| ModRef
,
264 /// OnlyReadsMemory - This function does not perform any non-local stores or
265 /// volatile loads, but may read from any memory location.
267 /// This property corresponds to the GCC 'pure' attribute.
268 /// This property corresponds to the LLVM IR 'readonly' attribute.
269 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
270 OnlyReadsMemory
= Anywhere
| Ref
,
272 /// UnknownModRefBehavior - This indicates that the function could not be
273 /// classified into one of the behaviors above.
274 UnknownModRefBehavior
= Anywhere
| ModRef
277 /// getModRefBehavior - Return the behavior when calling the given call site.
278 virtual ModRefBehavior
getModRefBehavior(ImmutableCallSite CS
);
280 /// getModRefBehavior - Return the behavior when calling the given function.
281 /// For use when the call site is not known.
282 virtual ModRefBehavior
getModRefBehavior(const Function
*F
);
284 /// doesNotAccessMemory - If the specified call is known to never read or
285 /// write memory, return true. If the call only reads from known-constant
286 /// memory, it is also legal to return true. Calls that unwind the stack
287 /// are legal for this predicate.
289 /// Many optimizations (such as CSE and LICM) can be performed on such calls
290 /// without worrying about aliasing properties, and many calls have this
291 /// property (e.g. calls to 'sin' and 'cos').
293 /// This property corresponds to the GCC 'const' attribute.
295 bool doesNotAccessMemory(ImmutableCallSite CS
) {
296 return getModRefBehavior(CS
) == DoesNotAccessMemory
;
299 /// doesNotAccessMemory - If the specified function is known to never read or
300 /// write memory, return true. For use when the call site is not known.
302 bool doesNotAccessMemory(const Function
*F
) {
303 return getModRefBehavior(F
) == DoesNotAccessMemory
;
306 /// onlyReadsMemory - If the specified call is known to only read from
307 /// non-volatile memory (or not access memory at all), return true. Calls
308 /// that unwind the stack are legal for this predicate.
310 /// This property allows many common optimizations to be performed in the
311 /// absence of interfering store instructions, such as CSE of strlen calls.
313 /// This property corresponds to the GCC 'pure' attribute.
315 bool onlyReadsMemory(ImmutableCallSite CS
) {
316 return onlyReadsMemory(getModRefBehavior(CS
));
319 /// onlyReadsMemory - If the specified function is known to only read from
320 /// non-volatile memory (or not access memory at all), return true. For use
321 /// when the call site is not known.
323 bool onlyReadsMemory(const Function
*F
) {
324 return onlyReadsMemory(getModRefBehavior(F
));
327 /// onlyReadsMemory - Return true if functions with the specified behavior are
328 /// known to only read from non-volatile memory (or not access memory at all).
330 static bool onlyReadsMemory(ModRefBehavior MRB
) {
334 /// onlyAccessesArgPointees - Return true if functions with the specified
335 /// behavior are known to read and write at most from objects pointed to by
336 /// their pointer-typed arguments (with arbitrary offsets).
338 static bool onlyAccessesArgPointees(ModRefBehavior MRB
) {
339 return !(MRB
& Anywhere
& ~ArgumentPointees
);
342 /// doesAccessArgPointees - Return true if functions with the specified
343 /// behavior are known to potentially read or write from objects pointed
344 /// to be their pointer-typed arguments (with arbitrary offsets).
346 static bool doesAccessArgPointees(ModRefBehavior MRB
) {
347 return (MRB
& ModRef
) && (MRB
& ArgumentPointees
);
350 /// getModRefInfo - Return information about whether or not an instruction may
351 /// read or write the specified memory location. An instruction
352 /// that doesn't read or write memory may be trivially LICM'd for example.
353 ModRefResult
getModRefInfo(const Instruction
*I
,
354 const Location
&Loc
) {
355 switch (I
->getOpcode()) {
356 case Instruction::VAArg
: return getModRefInfo((const VAArgInst
*)I
, Loc
);
357 case Instruction::Load
: return getModRefInfo((const LoadInst
*)I
, Loc
);
358 case Instruction::Store
: return getModRefInfo((const StoreInst
*)I
, Loc
);
359 case Instruction::Fence
: return getModRefInfo((const FenceInst
*)I
, Loc
);
360 case Instruction::AtomicCmpXchg
:
361 return getModRefInfo((const AtomicCmpXchgInst
*)I
, Loc
);
362 case Instruction::AtomicRMW
:
363 return getModRefInfo((const AtomicRMWInst
*)I
, Loc
);
364 case Instruction::Call
: return getModRefInfo((const CallInst
*)I
, Loc
);
365 case Instruction::Invoke
: return getModRefInfo((const InvokeInst
*)I
,Loc
);
366 default: return NoModRef
;
370 /// getModRefInfo - A convenience wrapper.
371 ModRefResult
getModRefInfo(const Instruction
*I
,
372 const Value
*P
, uint64_t Size
) {
373 return getModRefInfo(I
, Location(P
, Size
));
376 /// getModRefInfo (for call sites) - Return whether information about whether
377 /// a particular call site modifies or reads the specified memory location.
378 virtual ModRefResult
getModRefInfo(ImmutableCallSite CS
,
379 const Location
&Loc
);
381 /// getModRefInfo (for call sites) - A convenience wrapper.
382 ModRefResult
getModRefInfo(ImmutableCallSite CS
,
383 const Value
*P
, uint64_t Size
) {
384 return getModRefInfo(CS
, Location(P
, Size
));
387 /// getModRefInfo (for calls) - Return whether information about whether
388 /// a particular call modifies or reads the specified memory location.
389 ModRefResult
getModRefInfo(const CallInst
*C
, const Location
&Loc
) {
390 return getModRefInfo(ImmutableCallSite(C
), Loc
);
393 /// getModRefInfo (for calls) - A convenience wrapper.
394 ModRefResult
getModRefInfo(const CallInst
*C
, const Value
*P
, uint64_t Size
) {
395 return getModRefInfo(C
, Location(P
, Size
));
398 /// getModRefInfo (for invokes) - Return whether information about whether
399 /// a particular invoke modifies or reads the specified memory location.
400 ModRefResult
getModRefInfo(const InvokeInst
*I
,
401 const Location
&Loc
) {
402 return getModRefInfo(ImmutableCallSite(I
), Loc
);
405 /// getModRefInfo (for invokes) - A convenience wrapper.
406 ModRefResult
getModRefInfo(const InvokeInst
*I
,
407 const Value
*P
, uint64_t Size
) {
408 return getModRefInfo(I
, Location(P
, Size
));
411 /// getModRefInfo (for loads) - Return whether information about whether
412 /// a particular load modifies or reads the specified memory location.
413 ModRefResult
getModRefInfo(const LoadInst
*L
, const Location
&Loc
);
415 /// getModRefInfo (for loads) - A convenience wrapper.
416 ModRefResult
getModRefInfo(const LoadInst
*L
, const Value
*P
, uint64_t Size
) {
417 return getModRefInfo(L
, Location(P
, Size
));
420 /// getModRefInfo (for stores) - Return whether information about whether
421 /// a particular store modifies or reads the specified memory location.
422 ModRefResult
getModRefInfo(const StoreInst
*S
, const Location
&Loc
);
424 /// getModRefInfo (for stores) - A convenience wrapper.
425 ModRefResult
getModRefInfo(const StoreInst
*S
, const Value
*P
, uint64_t Size
){
426 return getModRefInfo(S
, Location(P
, Size
));
429 /// getModRefInfo (for fences) - Return whether information about whether
430 /// a particular store modifies or reads the specified memory location.
431 ModRefResult
getModRefInfo(const FenceInst
*S
, const Location
&Loc
) {
432 // Conservatively correct. (We could possibly be a bit smarter if
433 // Loc is a alloca that doesn't escape.)
437 /// getModRefInfo (for fences) - A convenience wrapper.
438 ModRefResult
getModRefInfo(const FenceInst
*S
, const Value
*P
, uint64_t Size
){
439 return getModRefInfo(S
, Location(P
, Size
));
442 /// getModRefInfo (for cmpxchges) - Return whether information about whether
443 /// a particular cmpxchg modifies or reads the specified memory location.
444 ModRefResult
getModRefInfo(const AtomicCmpXchgInst
*CX
, const Location
&Loc
);
446 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
447 ModRefResult
getModRefInfo(const AtomicCmpXchgInst
*CX
,
448 const Value
*P
, unsigned Size
) {
449 return getModRefInfo(CX
, Location(P
, Size
));
452 /// getModRefInfo (for atomicrmws) - Return whether information about whether
453 /// a particular atomicrmw modifies or reads the specified memory location.
454 ModRefResult
getModRefInfo(const AtomicRMWInst
*RMW
, const Location
&Loc
);
456 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
457 ModRefResult
getModRefInfo(const AtomicRMWInst
*RMW
,
458 const Value
*P
, unsigned Size
) {
459 return getModRefInfo(RMW
, Location(P
, Size
));
462 /// getModRefInfo (for va_args) - Return whether information about whether
463 /// a particular va_arg modifies or reads the specified memory location.
464 ModRefResult
getModRefInfo(const VAArgInst
* I
, const Location
&Loc
);
466 /// getModRefInfo (for va_args) - A convenience wrapper.
467 ModRefResult
getModRefInfo(const VAArgInst
* I
, const Value
* P
, uint64_t Size
){
468 return getModRefInfo(I
, Location(P
, Size
));
471 /// getModRefInfo - Return information about whether two call sites may refer
472 /// to the same set of memory locations. See
473 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
475 virtual ModRefResult
getModRefInfo(ImmutableCallSite CS1
,
476 ImmutableCallSite CS2
);
478 /// callCapturesBefore - Return information about whether a particular call
479 /// site modifies or reads the specified memory location.
480 ModRefResult
callCapturesBefore(const Instruction
*I
,
481 const AliasAnalysis::Location
&MemLoc
,
484 /// callCapturesBefore - A convenience wrapper.
485 ModRefResult
callCapturesBefore(const Instruction
*I
, const Value
*P
,
486 uint64_t Size
, DominatorTree
*DT
) {
487 return callCapturesBefore(I
, Location(P
, Size
), DT
);
490 //===--------------------------------------------------------------------===//
491 /// Higher level methods for querying mod/ref information.
494 /// canBasicBlockModify - Return true if it is possible for execution of the
495 /// specified basic block to modify the value pointed to by Ptr.
496 bool canBasicBlockModify(const BasicBlock
&BB
, const Location
&Loc
);
498 /// canBasicBlockModify - A convenience wrapper.
499 bool canBasicBlockModify(const BasicBlock
&BB
, const Value
*P
, uint64_t Size
){
500 return canBasicBlockModify(BB
, Location(P
, Size
));
503 /// canInstructionRangeModify - Return true if it is possible for the
504 /// execution of the specified instructions to modify the value pointed to by
505 /// Ptr. The instructions to consider are all of the instructions in the
506 /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
507 bool canInstructionRangeModify(const Instruction
&I1
, const Instruction
&I2
,
508 const Location
&Loc
);
510 /// canInstructionRangeModify - A convenience wrapper.
511 bool canInstructionRangeModify(const Instruction
&I1
, const Instruction
&I2
,
512 const Value
*Ptr
, uint64_t Size
) {
513 return canInstructionRangeModify(I1
, I2
, Location(Ptr
, Size
));
516 //===--------------------------------------------------------------------===//
517 /// Methods that clients should call when they transform the program to allow
518 /// alias analyses to update their internal data structures. Note that these
519 /// methods may be called on any instruction, regardless of whether or not
520 /// they have pointer-analysis implications.
523 /// deleteValue - This method should be called whenever an LLVM Value is
524 /// deleted from the program, for example when an instruction is found to be
525 /// redundant and is eliminated.
527 virtual void deleteValue(Value
*V
);
529 /// copyValue - This method should be used whenever a preexisting value in the
530 /// program is copied or cloned, introducing a new value. Note that analysis
531 /// implementations should tolerate clients that use this method to introduce
532 /// the same value multiple times: if the analysis already knows about a
533 /// value, it should ignore the request.
535 virtual void copyValue(Value
*From
, Value
*To
);
537 /// addEscapingUse - This method should be used whenever an escaping use is
538 /// added to a pointer value. Analysis implementations may either return
539 /// conservative responses for that value in the future, or may recompute
540 /// some or all internal state to continue providing precise responses.
542 /// Escaping uses are considered by anything _except_ the following:
543 /// - GEPs or bitcasts of the pointer
544 /// - Loads through the pointer
545 /// - Stores through (but not of) the pointer
546 virtual void addEscapingUse(Use
&U
);
548 /// replaceWithNewValue - This method is the obvious combination of the two
549 /// above, and it provided as a helper to simplify client code.
551 void replaceWithNewValue(Value
*Old
, Value
*New
) {
557 // Specialize DenseMapInfo for Location.
559 struct DenseMapInfo
<AliasAnalysis::Location
> {
560 static inline AliasAnalysis::Location
getEmptyKey() {
562 AliasAnalysis::Location(DenseMapInfo
<const Value
*>::getEmptyKey(),
565 static inline AliasAnalysis::Location
getTombstoneKey() {
567 AliasAnalysis::Location(DenseMapInfo
<const Value
*>::getTombstoneKey(),
570 static unsigned getHashValue(const AliasAnalysis::Location
&Val
) {
571 return DenseMapInfo
<const Value
*>::getHashValue(Val
.Ptr
) ^
572 DenseMapInfo
<uint64_t>::getHashValue(Val
.Size
) ^
573 DenseMapInfo
<const MDNode
*>::getHashValue(Val
.TBAATag
);
575 static bool isEqual(const AliasAnalysis::Location
&LHS
,
576 const AliasAnalysis::Location
&RHS
) {
577 return LHS
.Ptr
== RHS
.Ptr
&&
578 LHS
.Size
== RHS
.Size
&&
579 LHS
.TBAATag
== RHS
.TBAATag
;
583 /// isNoAliasCall - Return true if this pointer is returned by a noalias
585 bool isNoAliasCall(const Value
*V
);
587 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
588 /// identifiable object. This returns true for:
589 /// Global Variables and Functions (but not Global Aliases)
590 /// Allocas and Mallocs
591 /// ByVal and NoAlias Arguments
594 bool isIdentifiedObject(const Value
*V
);
596 /// isKnownNonNull - Return true if this pointer couldn't possibly be null by
597 /// its definition. This returns true for allocas, non-extern-weak globals and
599 bool isKnownNonNull(const Value
*V
);
601 } // End llvm namespace