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/None.h"
42 #include "llvm/ADT/Optional.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/Analysis/MemoryLocation.h"
45 #include "llvm/Analysis/TargetLibraryInfo.h"
46 #include "llvm/IR/CallSite.h"
47 #include "llvm/IR/Function.h"
48 #include "llvm/IR/Instruction.h"
49 #include "llvm/IR/Instructions.h"
50 #include "llvm/IR/PassManager.h"
51 #include "llvm/Pass.h"
63 class OrderedBasicBlock;
66 /// The possible results of an alias query.
68 /// These results are always computed between two MemoryLocation objects as
69 /// a query to some alias analysis.
71 /// Note that these are unscoped enumerations because we would like to support
72 /// implicitly testing a result for the existence of any possible aliasing with
73 /// a conversion to bool, but an "enum class" doesn't support this. The
74 /// canonical names from the literature are suffixed and unique anyways, and so
75 /// they serve as global constants in LLVM for these results.
77 /// See docs/AliasAnalysis.html for more information on the specific meanings
80 /// The two locations do not alias at all.
82 /// This value is arranged to convert to false, while all other values
83 /// convert to true. This allows a boolean context to convert the result to
84 /// a binary flag indicating whether there is the possibility of aliasing.
86 /// The two locations may or may not alias. This is the least precise result.
88 /// The two locations alias, but only due to a partial overlap.
90 /// The two locations precisely alias each other.
94 /// Flags indicating whether a memory access modifies or references memory.
96 /// This is no access at all, a modification, a reference, or both
97 /// a modification and a reference. These are specifically structured such that
98 /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
99 /// work with any of the possible values.
100 enum class ModRefInfo {
101 /// Must is provided for completeness, but no routines will return only
102 /// Must today. See definition of Must below.
104 /// The access may reference the value stored in memory,
105 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
107 /// The access may modify the value stored in memory,
108 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
110 /// The access may reference, modify or both the value stored in memory,
111 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
112 MustModRef = MustRef | MustMod,
113 /// The access neither references nor modifies the value stored in memory.
115 /// The access may reference the value stored in memory.
116 Ref = NoModRef | MustRef,
117 /// The access may modify the value stored in memory.
118 Mod = NoModRef | MustMod,
119 /// The access may reference and may modify the value stored in memory.
123 /// Must is set in a best effort manner.
124 /// We usually do not try our best to infer Must, instead it is merely
125 /// another piece of "free" information that is presented when available.
126 /// Must set means there was certainly a MustAlias found. For calls,
127 /// where multiple arguments are checked (argmemonly), this translates to
128 /// only MustAlias or NoAlias was found.
129 /// Must is not set for RAR accesses, even if the two locations must
130 /// alias. The reason is that two read accesses translate to an early return
131 /// of NoModRef. An additional alias check to set Must may be
132 /// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
133 /// We refer to Must being *set* when the most significant bit is *cleared*.
134 /// Conversely we *clear* Must information by *setting* the Must bit to 1.
137 LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) {
138 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
139 static_cast<int>(ModRefInfo::Must);
141 LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) {
142 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
144 LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) {
145 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
146 static_cast<int>(ModRefInfo::MustModRef);
148 LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) {
149 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
151 LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) {
152 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
154 LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) {
155 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
158 LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) {
159 return ModRefInfo(static_cast<int>(MRI) |
160 static_cast<int>(ModRefInfo::MustMod));
162 LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) {
163 return ModRefInfo(static_cast<int>(MRI) |
164 static_cast<int>(ModRefInfo::MustRef));
166 LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) {
167 return ModRefInfo(static_cast<int>(MRI) &
168 static_cast<int>(ModRefInfo::MustModRef));
170 LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
171 return ModRefInfo(static_cast<int>(MRI) |
172 static_cast<int>(ModRefInfo::MustModRef));
174 LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) {
175 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
177 LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) {
178 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
180 LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) {
181 return ModRefInfo(static_cast<int>(MRI) |
182 static_cast<int>(ModRefInfo::NoModRef));
184 LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1,
185 const ModRefInfo MRI2) {
186 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
188 LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1,
189 const ModRefInfo MRI2) {
190 return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
193 /// The locations at which a function might access memory.
195 /// These are primarily used in conjunction with the \c AccessKind bits to
196 /// describe both the nature of access and the locations of access for a
198 enum FunctionModRefLocation {
199 /// Base case is no access to memory.
201 /// Access to memory via argument pointers.
202 FMRL_ArgumentPointees = 8,
203 /// Memory that is inaccessible via LLVM IR.
204 FMRL_InaccessibleMem = 16,
205 /// Access to any memory.
206 FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees
209 /// Summary of how a function affects memory in the program.
211 /// Loads from constant globals are not considered memory accesses for this
212 /// interface. Also, functions may freely modify stack space local to their
213 /// invocation without having to report it through these interfaces.
214 enum FunctionModRefBehavior {
215 /// This function does not perform any non-local loads or stores to memory.
217 /// This property corresponds to the GCC 'const' attribute.
218 /// This property corresponds to the LLVM IR 'readnone' attribute.
219 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
220 FMRB_DoesNotAccessMemory =
221 FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),
223 /// The only memory references in this function (if it has any) are
224 /// non-volatile loads from objects pointed to by its pointer-typed
225 /// arguments, with arbitrary offsets.
227 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
228 FMRB_OnlyReadsArgumentPointees =
229 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),
231 /// The only memory references in this function (if it has any) are
232 /// non-volatile loads and stores from objects pointed to by its
233 /// pointer-typed arguments, with arbitrary offsets.
235 /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
236 FMRB_OnlyAccessesArgumentPointees =
237 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),
239 /// The only memory references in this function (if it has any) are
240 /// references of memory that is otherwise inaccessible via LLVM IR.
242 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
243 FMRB_OnlyAccessesInaccessibleMem =
244 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),
246 /// The function may perform non-volatile loads and stores of objects
247 /// pointed to by its pointer-typed arguments, with arbitrary offsets, and
248 /// it may also perform loads and stores of memory that is otherwise
249 /// inaccessible via LLVM IR.
251 /// This property corresponds to the LLVM IR
252 /// inaccessiblemem_or_argmemonly attribute.
253 FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem |
254 FMRL_ArgumentPointees |
255 static_cast<int>(ModRefInfo::ModRef),
257 /// This function does not perform any non-local stores or volatile loads,
258 /// but may read from any memory location.
260 /// This property corresponds to the GCC 'pure' attribute.
261 /// This property corresponds to the LLVM IR 'readonly' attribute.
262 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
263 FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref),
265 // This function does not read from memory anywhere, but may write to any
268 // This property corresponds to the LLVM IR 'writeonly' attribute.
269 // This property corresponds to the IntrWriteMem LLVM intrinsic flag.
270 FMRB_DoesNotReadMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod),
272 /// This indicates that the function could not be classified into one of the
274 FMRB_UnknownModRefBehavior =
275 FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
278 // Wrapper method strips bits significant only in FunctionModRefBehavior,
279 // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
280 // ModRefInfo enum changes, the wrapper can be updated to & with the new enum
281 // entry with all bits set to 1.
282 LLVM_NODISCARD inline ModRefInfo
283 createModRefInfo(const FunctionModRefBehavior FMRB) {
284 return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
289 // Make these results default constructable and movable. We have to spell
290 // these out because MSVC won't synthesize them.
291 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
292 AAResults(AAResults &&Arg);
295 /// Register a specific AA result.
296 template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
297 // FIXME: We should use a much lighter weight system than the usual
298 // polymorphic pattern because we don't own AAResult. It should
299 // ideally involve two pointers and no separate allocation.
300 AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
303 /// Register a function analysis ID that the results aggregation depends on.
305 /// This is used in the new pass manager to implement the invalidation logic
306 /// where we must invalidate the results aggregation if any of our component
307 /// analyses become invalid.
308 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }
310 /// Handle invalidation events in the new pass manager.
312 /// The aggregation is invalidated if any of the underlying analyses is
314 bool invalidate(Function &F, const PreservedAnalyses &PA,
315 FunctionAnalysisManager::Invalidator &Inv);
317 //===--------------------------------------------------------------------===//
318 /// \name Alias Queries
321 /// The main low level interface to the alias analysis implementation.
322 /// Returns an AliasResult indicating whether the two pointers are aliased to
323 /// each other. This is the interface that must be implemented by specific
324 /// alias analysis implementations.
325 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
327 /// A convenience wrapper around the primary \c alias interface.
328 AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2,
330 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
333 /// A convenience wrapper around the primary \c alias interface.
334 AliasResult alias(const Value *V1, const Value *V2) {
335 return alias(V1, MemoryLocation::UnknownSize, V2,
336 MemoryLocation::UnknownSize);
339 /// A trivial helper function to check to see if the specified pointers are
341 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
342 return alias(LocA, LocB) == NoAlias;
345 /// A convenience wrapper around the \c isNoAlias helper interface.
346 bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2,
348 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
351 /// A convenience wrapper around the \c isNoAlias helper interface.
352 bool isNoAlias(const Value *V1, const Value *V2) {
353 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
356 /// A trivial helper function to check to see if the specified pointers are
358 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
359 return alias(LocA, LocB) == MustAlias;
362 /// A convenience wrapper around the \c isMustAlias helper interface.
363 bool isMustAlias(const Value *V1, const Value *V2) {
364 return alias(V1, 1, V2, 1) == MustAlias;
367 /// Checks whether the given location points to constant memory, or if
368 /// \p OrLocal is true whether it points to a local alloca.
369 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
371 /// A convenience wrapper around the primary \c pointsToConstantMemory
373 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
374 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
378 //===--------------------------------------------------------------------===//
379 /// \name Simple mod/ref information
382 /// Get the ModRef info associated with a pointer argument of a callsite. The
383 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
384 /// that these bits do not necessarily account for the overall behavior of
385 /// the function, but rather only provide additional per-argument
386 /// information. This never sets ModRefInfo::Must.
387 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
389 /// Return the behavior of the given call site.
390 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
392 /// Return the behavior when calling the given function.
393 FunctionModRefBehavior getModRefBehavior(const Function *F);
395 /// Checks if the specified call is known to never read or write memory.
397 /// Note that if the call only reads from known-constant memory, it is also
398 /// legal to return true. Also, calls that unwind the stack are legal for
401 /// Many optimizations (such as CSE and LICM) can be performed on such calls
402 /// without worrying about aliasing properties, and many calls have this
403 /// property (e.g. calls to 'sin' and 'cos').
405 /// This property corresponds to the GCC 'const' attribute.
406 bool doesNotAccessMemory(ImmutableCallSite CS) {
407 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
410 /// Checks if the specified function is known to never read or write memory.
412 /// Note that if the function only reads from known-constant memory, it is
413 /// also legal to return true. Also, function that unwind the stack are legal
414 /// for this predicate.
416 /// Many optimizations (such as CSE and LICM) can be performed on such calls
417 /// to such functions without worrying about aliasing properties, and many
418 /// functions have this property (e.g. 'sin' and 'cos').
420 /// This property corresponds to the GCC 'const' attribute.
421 bool doesNotAccessMemory(const Function *F) {
422 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
425 /// Checks if the specified call is known to only read from non-volatile
426 /// memory (or not access memory at all).
428 /// Calls that unwind the stack are legal for this predicate.
430 /// This property allows many common optimizations to be performed in the
431 /// absence of interfering store instructions, such as CSE of strlen calls.
433 /// This property corresponds to the GCC 'pure' attribute.
434 bool onlyReadsMemory(ImmutableCallSite CS) {
435 return onlyReadsMemory(getModRefBehavior(CS));
438 /// Checks if the specified function is known to only read from non-volatile
439 /// memory (or not access memory at all).
441 /// Functions that unwind the stack are legal for this predicate.
443 /// This property allows many common optimizations to be performed in the
444 /// absence of interfering store instructions, such as CSE of strlen calls.
446 /// This property corresponds to the GCC 'pure' attribute.
447 bool onlyReadsMemory(const Function *F) {
448 return onlyReadsMemory(getModRefBehavior(F));
451 /// Checks if functions with the specified behavior are known to only read
452 /// from non-volatile memory (or not access memory at all).
453 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
454 return !isModSet(createModRefInfo(MRB));
457 /// Checks if functions with the specified behavior are known to only write
458 /// memory (or not access memory at all).
459 static bool doesNotReadMemory(FunctionModRefBehavior MRB) {
460 return !isRefSet(createModRefInfo(MRB));
463 /// Checks if functions with the specified behavior are known to read and
464 /// write at most from objects pointed to by their pointer-typed arguments
465 /// (with arbitrary offsets).
466 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
467 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
470 /// Checks if functions with the specified behavior are known to potentially
471 /// read or write from objects pointed to be their pointer-typed arguments
472 /// (with arbitrary offsets).
473 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
474 return isModOrRefSet(createModRefInfo(MRB)) &&
475 (MRB & FMRL_ArgumentPointees);
478 /// Checks if functions with the specified behavior are known to read and
479 /// write at most from memory that is inaccessible from LLVM IR.
480 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) {
481 return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
484 /// Checks if functions with the specified behavior are known to potentially
485 /// read or write from memory that is inaccessible from LLVM IR.
486 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) {
487 return isModOrRefSet(createModRefInfo(MRB)) && (MRB & FMRL_InaccessibleMem);
490 /// Checks if functions with the specified behavior are known to read and
491 /// write at most from memory that is inaccessible from LLVM IR or objects
492 /// pointed to by their pointer-typed arguments (with arbitrary offsets).
493 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) {
494 return !(MRB & FMRL_Anywhere &
495 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees));
498 /// getModRefInfo (for call sites) - Return information about whether
499 /// a particular call site modifies or reads the specified memory location.
500 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
502 /// getModRefInfo (for call sites) - A convenience wrapper.
503 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
505 return getModRefInfo(CS, MemoryLocation(P, Size));
508 /// getModRefInfo (for calls) - Return information about whether
509 /// a particular call modifies or reads the specified memory location.
510 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
511 return getModRefInfo(ImmutableCallSite(C), Loc);
514 /// getModRefInfo (for calls) - A convenience wrapper.
515 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
516 return getModRefInfo(C, MemoryLocation(P, Size));
519 /// getModRefInfo (for invokes) - Return information about whether
520 /// a particular invoke modifies or reads the specified memory location.
521 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
522 return getModRefInfo(ImmutableCallSite(I), Loc);
525 /// getModRefInfo (for invokes) - A convenience wrapper.
526 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
527 return getModRefInfo(I, MemoryLocation(P, Size));
530 /// getModRefInfo (for loads) - Return information about whether
531 /// a particular load modifies or reads the specified memory location.
532 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
534 /// getModRefInfo (for loads) - A convenience wrapper.
535 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
536 return getModRefInfo(L, MemoryLocation(P, Size));
539 /// getModRefInfo (for stores) - Return information about whether
540 /// a particular store modifies or reads the specified memory location.
541 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
543 /// getModRefInfo (for stores) - A convenience wrapper.
544 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
545 return getModRefInfo(S, MemoryLocation(P, Size));
548 /// getModRefInfo (for fences) - Return information about whether
549 /// a particular store modifies or reads the specified memory location.
550 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
552 /// getModRefInfo (for fences) - A convenience wrapper.
553 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
554 return getModRefInfo(S, MemoryLocation(P, Size));
557 /// getModRefInfo (for cmpxchges) - Return information about whether
558 /// a particular cmpxchg modifies or reads the specified memory location.
559 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
560 const MemoryLocation &Loc);
562 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
563 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
565 return getModRefInfo(CX, MemoryLocation(P, Size));
568 /// getModRefInfo (for atomicrmws) - Return information about whether
569 /// a particular atomicrmw modifies or reads the specified memory location.
570 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
572 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
573 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
575 return getModRefInfo(RMW, MemoryLocation(P, Size));
578 /// getModRefInfo (for va_args) - Return information about whether
579 /// a particular va_arg modifies or reads the specified memory location.
580 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
582 /// getModRefInfo (for va_args) - A convenience wrapper.
583 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
584 return getModRefInfo(I, MemoryLocation(P, Size));
587 /// getModRefInfo (for catchpads) - Return information about whether
588 /// a particular catchpad modifies or reads the specified memory location.
589 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
591 /// getModRefInfo (for catchpads) - A convenience wrapper.
592 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
594 return getModRefInfo(I, MemoryLocation(P, Size));
597 /// getModRefInfo (for catchrets) - Return information about whether
598 /// a particular catchret modifies or reads the specified memory location.
599 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
601 /// getModRefInfo (for catchrets) - A convenience wrapper.
602 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
604 return getModRefInfo(I, MemoryLocation(P, Size));
607 /// Check whether or not an instruction may read or write the optionally
608 /// specified memory location.
611 /// An instruction that doesn't read or write memory may be trivially LICM'd
614 /// For function calls, this delegates to the alias-analysis specific
615 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
617 ModRefInfo getModRefInfo(const Instruction *I,
618 const Optional<MemoryLocation> &OptLoc) {
619 if (OptLoc == None) {
620 if (auto CS = ImmutableCallSite(I)) {
621 return createModRefInfo(getModRefBehavior(CS));
625 const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
627 switch (I->getOpcode()) {
628 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
629 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
630 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
631 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
632 case Instruction::AtomicCmpXchg:
633 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
634 case Instruction::AtomicRMW:
635 return getModRefInfo((const AtomicRMWInst*)I, Loc);
636 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
637 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
638 case Instruction::CatchPad:
639 return getModRefInfo((const CatchPadInst *)I, Loc);
640 case Instruction::CatchRet:
641 return getModRefInfo((const CatchReturnInst *)I, Loc);
643 return ModRefInfo::NoModRef;
647 /// A convenience wrapper for constructing the memory location.
648 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
650 return getModRefInfo(I, MemoryLocation(P, Size));
653 /// Return information about whether a call and an instruction may refer to
654 /// the same memory locations.
655 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
657 /// Return information about whether two call sites may refer to the same set
658 /// of memory locations. See the AA documentation for details:
659 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
660 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
662 /// \brief Return information about whether a particular call site modifies
663 /// or reads the specified memory location \p MemLoc before instruction \p I
664 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
665 /// instruction ordering queries inside the BasicBlock containing \p I.
666 /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
668 ModRefInfo callCapturesBefore(const Instruction *I,
669 const MemoryLocation &MemLoc, DominatorTree *DT,
670 OrderedBasicBlock *OBB = nullptr);
672 /// \brief A convenience wrapper to synthesize a memory location.
673 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
674 uint64_t Size, DominatorTree *DT,
675 OrderedBasicBlock *OBB = nullptr) {
676 return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
680 //===--------------------------------------------------------------------===//
681 /// \name Higher level methods for querying mod/ref information.
684 /// Check if it is possible for execution of the specified basic block to
685 /// modify the location Loc.
686 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
688 /// A convenience wrapper synthesizing a memory location.
689 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
691 return canBasicBlockModify(BB, MemoryLocation(P, Size));
694 /// Check if it is possible for the execution of the specified instructions
695 /// to mod\ref (according to the mode) the location Loc.
697 /// The instructions to consider are all of the instructions in the range of
698 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
699 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
700 const MemoryLocation &Loc,
701 const ModRefInfo Mode);
703 /// A convenience wrapper synthesizing a memory location.
704 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
705 const Value *Ptr, uint64_t Size,
706 const ModRefInfo Mode) {
707 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
713 template <typename T> class Model;
715 template <typename T> friend class AAResultBase;
717 const TargetLibraryInfo &TLI;
719 std::vector<std::unique_ptr<Concept>> AAs;
721 std::vector<AnalysisKey *> AADeps;
724 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
725 /// pointer or reference.
726 using AliasAnalysis = AAResults;
728 /// A private abstract base class describing the concept of an individual alias
729 /// analysis implementation.
731 /// This interface is implemented by any \c Model instantiation. It is also the
732 /// interface which a type used to instantiate the model must provide.
734 /// All of these methods model methods by the same name in the \c
735 /// AAResults class. Only differences and specifics to how the
736 /// implementations are called are documented here.
737 class AAResults::Concept {
739 virtual ~Concept() = 0;
741 /// An update API used internally by the AAResults to provide
742 /// a handle back to the top level aggregation.
743 virtual void setAAResults(AAResults *NewAAR) = 0;
745 //===--------------------------------------------------------------------===//
746 /// \name Alias Queries
749 /// The main low level interface to the alias analysis implementation.
750 /// Returns an AliasResult indicating whether the two pointers are aliased to
751 /// each other. This is the interface that must be implemented by specific
752 /// alias analysis implementations.
753 virtual AliasResult alias(const MemoryLocation &LocA,
754 const MemoryLocation &LocB) = 0;
756 /// Checks whether the given location points to constant memory, or if
757 /// \p OrLocal is true whether it points to a local alloca.
758 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
762 //===--------------------------------------------------------------------===//
763 /// \name Simple mod/ref information
766 /// Get the ModRef info associated with a pointer argument of a callsite. The
767 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
768 /// that these bits do not necessarily account for the overall behavior of
769 /// the function, but rather only provide additional per-argument
771 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS,
772 unsigned ArgIdx) = 0;
774 /// Return the behavior of the given call site.
775 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) = 0;
777 /// Return the behavior when calling the given function.
778 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
780 /// getModRefInfo (for call sites) - Return information about whether
781 /// a particular call site modifies or reads the specified memory location.
782 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
783 const MemoryLocation &Loc) = 0;
785 /// Return information about whether two call sites may refer to the same set
786 /// of memory locations. See the AA documentation for details:
787 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
788 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
789 ImmutableCallSite CS2) = 0;
794 /// A private class template which derives from \c Concept and wraps some other
797 /// This models the concept by directly forwarding each interface point to the
798 /// wrapped type which must implement a compatible interface. This provides
799 /// a type erased binding.
800 template <typename AAResultT> class AAResults::Model final : public Concept {
804 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
805 Result.setAAResults(&AAR);
807 ~Model() override = default;
809 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
811 AliasResult alias(const MemoryLocation &LocA,
812 const MemoryLocation &LocB) override {
813 return Result.alias(LocA, LocB);
816 bool pointsToConstantMemory(const MemoryLocation &Loc,
817 bool OrLocal) override {
818 return Result.pointsToConstantMemory(Loc, OrLocal);
821 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override {
822 return Result.getArgModRefInfo(CS, ArgIdx);
825 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override {
826 return Result.getModRefBehavior(CS);
829 FunctionModRefBehavior getModRefBehavior(const Function *F) override {
830 return Result.getModRefBehavior(F);
833 ModRefInfo getModRefInfo(ImmutableCallSite CS,
834 const MemoryLocation &Loc) override {
835 return Result.getModRefInfo(CS, Loc);
838 ModRefInfo getModRefInfo(ImmutableCallSite CS1,
839 ImmutableCallSite CS2) override {
840 return Result.getModRefInfo(CS1, CS2);
844 /// A CRTP-driven "mixin" base class to help implement the function alias
845 /// analysis results concept.
847 /// Because of the nature of many alias analysis implementations, they often
848 /// only implement a subset of the interface. This base class will attempt to
849 /// implement the remaining portions of the interface in terms of simpler forms
850 /// of the interface where possible, and otherwise provide conservatively
851 /// correct fallback implementations.
853 /// Implementors of an alias analysis should derive from this CRTP, and then
854 /// override specific methods that they wish to customize. There is no need to
855 /// use virtual anywhere, the CRTP base class does static dispatch to the
856 /// derived type passed into it.
857 template <typename DerivedT> class AAResultBase {
858 // Expose some parts of the interface only to the AAResults::Model
859 // for wrapping. Specifically, this allows the model to call our
860 // setAAResults method without exposing it as a fully public API.
861 friend class AAResults::Model<DerivedT>;
863 /// A pointer to the AAResults object that this AAResult is
864 /// aggregated within. May be null if not aggregated.
867 /// Helper to dispatch calls back through the derived type.
868 DerivedT &derived() { return static_cast<DerivedT &>(*this); }
870 /// A setter for the AAResults pointer, which is used to satisfy the
871 /// AAResults::Model contract.
872 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
875 /// This proxy class models a common pattern where we delegate to either the
876 /// top-level \c AAResults aggregation if one is registered, or to the
877 /// current result if none are registered.
878 class AAResultsProxy {
880 DerivedT &CurrentResult;
883 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
884 : AAR(AAR), CurrentResult(CurrentResult) {}
886 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
887 return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB);
890 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
891 return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal)
892 : CurrentResult.pointsToConstantMemory(Loc, OrLocal);
895 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
896 return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx);
899 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
900 return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS);
903 FunctionModRefBehavior getModRefBehavior(const Function *F) {
904 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
907 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
908 return AAR ? AAR->getModRefInfo(CS, Loc)
909 : CurrentResult.getModRefInfo(CS, Loc);
912 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
913 return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2);
917 explicit AAResultBase() = default;
919 // Provide all the copy and move constructors so that derived types aren't
921 AAResultBase(const AAResultBase &Arg) {}
922 AAResultBase(AAResultBase &&Arg) {}
924 /// Get a proxy for the best AA result set to query at this time.
926 /// When this result is part of a larger aggregation, this will proxy to that
927 /// aggregation. When this result is used in isolation, it will just delegate
928 /// back to the derived class's implementation.
930 /// Note that callers of this need to take considerable care to not cause
931 /// performance problems when they use this routine, in the case of a large
932 /// number of alias analyses being aggregated, it can be expensive to walk
933 /// back across the chain.
934 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
937 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
941 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
945 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
946 return ModRefInfo::ModRef;
949 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
950 return FMRB_UnknownModRefBehavior;
953 FunctionModRefBehavior getModRefBehavior(const Function *F) {
954 return FMRB_UnknownModRefBehavior;
957 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
958 return ModRefInfo::ModRef;
961 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
962 return ModRefInfo::ModRef;
966 /// Return true if this pointer is returned by a noalias function.
967 bool isNoAliasCall(const Value *V);
969 /// Return true if this is an argument with the noalias attribute.
970 bool isNoAliasArgument(const Value *V);
972 /// Return true if this pointer refers to a distinct and identifiable object.
973 /// This returns true for:
974 /// Global Variables and Functions (but not Global Aliases)
976 /// ByVal and NoAlias Arguments
977 /// NoAlias returns (e.g. calls to malloc)
979 bool isIdentifiedObject(const Value *V);
981 /// Return true if V is umabigously identified at the function-level.
982 /// Different IdentifiedFunctionLocals can't alias.
983 /// Further, an IdentifiedFunctionLocal can not alias with any function
984 /// arguments other than itself, which is not necessarily true for
985 /// IdentifiedObjects.
986 bool isIdentifiedFunctionLocal(const Value *V);
988 /// A manager for alias analyses.
990 /// This class can have analyses registered with it and when run, it will run
991 /// all of them and aggregate their results into single AA results interface
992 /// that dispatches across all of the alias analysis results available.
994 /// Note that the order in which analyses are registered is very significant.
995 /// That is the order in which the results will be aggregated and queried.
997 /// This manager effectively wraps the AnalysisManager for registering alias
998 /// analyses. When you register your alias analysis with this manager, it will
999 /// ensure the analysis itself is registered with its AnalysisManager.
1000 class AAManager : public AnalysisInfoMixin<AAManager> {
1002 using Result = AAResults;
1004 /// Register a specific AA result.
1005 template <typename AnalysisT> void registerFunctionAnalysis() {
1006 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
1009 /// Register a specific AA result.
1010 template <typename AnalysisT> void registerModuleAnalysis() {
1011 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
1014 Result run(Function &F, FunctionAnalysisManager &AM) {
1015 Result R(AM.getResult<TargetLibraryAnalysis>(F));
1016 for (auto &Getter : ResultGetters)
1017 (*Getter)(F, AM, R);
1022 friend AnalysisInfoMixin<AAManager>;
1024 static AnalysisKey Key;
1026 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
1027 AAResults &AAResults),
1030 template <typename AnalysisT>
1031 static void getFunctionAAResultImpl(Function &F,
1032 FunctionAnalysisManager &AM,
1033 AAResults &AAResults) {
1034 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1035 AAResults.addAADependencyID(AnalysisT::ID());
1038 template <typename AnalysisT>
1039 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
1040 AAResults &AAResults) {
1041 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1042 auto &MAM = MAMProxy.getManager();
1043 if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) {
1044 AAResults.addAAResult(*R);
1046 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
1051 /// A wrapper pass to provide the legacy pass manager access to a suitably
1052 /// prepared AAResults object.
1053 class AAResultsWrapperPass : public FunctionPass {
1054 std::unique_ptr<AAResults> AAR;
1059 AAResultsWrapperPass();
1061 AAResults &getAAResults() { return *AAR; }
1062 const AAResults &getAAResults() const { return *AAR; }
1064 bool runOnFunction(Function &F) override;
1066 void getAnalysisUsage(AnalysisUsage &AU) const override;
1069 FunctionPass *createAAResultsWrapperPass();
1071 /// A wrapper pass around a callback which can be used to populate the
1072 /// AAResults in the AAResultsWrapperPass from an external AA.
1074 /// The callback provided here will be used each time we prepare an AAResults
1075 /// object, and will receive a reference to the function wrapper pass, the
1076 /// function, and the AAResults object to populate. This should be used when
1077 /// setting up a custom pass pipeline to inject a hook into the AA results.
1078 ImmutablePass *createExternalAAWrapperPass(
1079 std::function<void(Pass &, Function &, AAResults &)> Callback);
1081 /// A helper for the legacy pass manager to create a \c AAResults
1082 /// object populated to the best of our ability for a particular function when
1083 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
1085 /// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1086 /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1087 /// getAnalysisUsage.
1088 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
1090 /// A helper for the legacy pass manager to populate \p AU to add uses to make
1091 /// sure the analyses required by \p createLegacyPMAAResults are available.
1092 void getAAResultsAnalysisUsage(AnalysisUsage &AU);
1094 } // end namespace llvm
1096 #endif // LLVM_ANALYSIS_ALIASANALYSIS_H