• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
14 //
15 // Implementations of this interface must implement the various virtual methods,
16 // which automatically provides functionality for the entire suite of client
17 // APIs.
18 //
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.
25 //
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.
35 //
36 //===----------------------------------------------------------------------===//
37 
38 #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
39 #define LLVM_ANALYSIS_ALIASANALYSIS_H
40 
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"
52 #include <cstdint>
53 #include <functional>
54 #include <memory>
55 #include <vector>
56 
57 namespace llvm {
58 
59 class AnalysisUsage;
60 class BasicAAResult;
61 class BasicBlock;
62 class DominatorTree;
63 class OrderedBasicBlock;
64 class Value;
65 
66 /// The possible results of an alias query.
67 ///
68 /// These results are always computed between two MemoryLocation objects as
69 /// a query to some alias analysis.
70 ///
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.
76 ///
77 /// See docs/AliasAnalysis.html for more information on the specific meanings
78 /// of these values.
79 enum AliasResult : uint8_t {
80   /// The two locations do not alias at all.
81   ///
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.
85   NoAlias = 0,
86   /// The two locations may or may not alias. This is the least precise result.
87   MayAlias,
88   /// The two locations alias, but only due to a partial overlap.
89   PartialAlias,
90   /// The two locations precisely alias each other.
91   MustAlias,
92 };
93 
94 /// << operator for AliasResult.
95 raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);
96 
97 /// Flags indicating whether a memory access modifies or references memory.
98 ///
99 /// This is no access at all, a modification, a reference, or both
100 /// a modification and a reference. These are specifically structured such that
101 /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
102 /// work with any of the possible values.
103 enum class ModRefInfo : uint8_t {
104   /// Must is provided for completeness, but no routines will return only
105   /// Must today. See definition of Must below.
106   Must = 0,
107   /// The access may reference the value stored in memory,
108   /// a mustAlias relation was found, and no mayAlias or partialAlias found.
109   MustRef = 1,
110   /// The access may modify the value stored in memory,
111   /// a mustAlias relation was found, and no mayAlias or partialAlias found.
112   MustMod = 2,
113   /// The access may reference, modify or both the value stored in memory,
114   /// a mustAlias relation was found, and no mayAlias or partialAlias found.
115   MustModRef = MustRef | MustMod,
116   /// The access neither references nor modifies the value stored in memory.
117   NoModRef = 4,
118   /// The access may reference the value stored in memory.
119   Ref = NoModRef | MustRef,
120   /// The access may modify the value stored in memory.
121   Mod = NoModRef | MustMod,
122   /// The access may reference and may modify the value stored in memory.
123   ModRef = Ref | Mod,
124 
125   /// About Must:
126   /// Must is set in a best effort manner.
127   /// We usually do not try our best to infer Must, instead it is merely
128   /// another piece of "free" information that is presented when available.
129   /// Must set means there was certainly a MustAlias found. For calls,
130   /// where multiple arguments are checked (argmemonly), this translates to
131   /// only MustAlias or NoAlias was found.
132   /// Must is not set for RAR accesses, even if the two locations must
133   /// alias. The reason is that two read accesses translate to an early return
134   /// of NoModRef. An additional alias check to set Must may be
135   /// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
136   /// We refer to Must being *set* when the most significant bit is *cleared*.
137   /// Conversely we *clear* Must information by *setting* the Must bit to 1.
138 };
139 
isNoModRef(const ModRefInfo MRI)140 LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) {
141   return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
142          static_cast<int>(ModRefInfo::Must);
143 }
isModOrRefSet(const ModRefInfo MRI)144 LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) {
145   return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
146 }
isModAndRefSet(const ModRefInfo MRI)147 LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) {
148   return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
149          static_cast<int>(ModRefInfo::MustModRef);
150 }
isModSet(const ModRefInfo MRI)151 LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) {
152   return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
153 }
isRefSet(const ModRefInfo MRI)154 LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) {
155   return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
156 }
isMustSet(const ModRefInfo MRI)157 LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) {
158   return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
159 }
160 
setMod(const ModRefInfo MRI)161 LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) {
162   return ModRefInfo(static_cast<int>(MRI) |
163                     static_cast<int>(ModRefInfo::MustMod));
164 }
setRef(const ModRefInfo MRI)165 LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) {
166   return ModRefInfo(static_cast<int>(MRI) |
167                     static_cast<int>(ModRefInfo::MustRef));
168 }
setMust(const ModRefInfo MRI)169 LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) {
170   return ModRefInfo(static_cast<int>(MRI) &
171                     static_cast<int>(ModRefInfo::MustModRef));
172 }
setModAndRef(const ModRefInfo MRI)173 LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
174   return ModRefInfo(static_cast<int>(MRI) |
175                     static_cast<int>(ModRefInfo::MustModRef));
176 }
clearMod(const ModRefInfo MRI)177 LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) {
178   return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
179 }
clearRef(const ModRefInfo MRI)180 LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) {
181   return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
182 }
clearMust(const ModRefInfo MRI)183 LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) {
184   return ModRefInfo(static_cast<int>(MRI) |
185                     static_cast<int>(ModRefInfo::NoModRef));
186 }
unionModRef(const ModRefInfo MRI1,const ModRefInfo MRI2)187 LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1,
188                                              const ModRefInfo MRI2) {
189   return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
190 }
intersectModRef(const ModRefInfo MRI1,const ModRefInfo MRI2)191 LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1,
192                                                  const ModRefInfo MRI2) {
193   return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
194 }
195 
196 /// The locations at which a function might access memory.
197 ///
198 /// These are primarily used in conjunction with the \c AccessKind bits to
199 /// describe both the nature of access and the locations of access for a
200 /// function call.
201 enum FunctionModRefLocation {
202   /// Base case is no access to memory.
203   FMRL_Nowhere = 0,
204   /// Access to memory via argument pointers.
205   FMRL_ArgumentPointees = 8,
206   /// Memory that is inaccessible via LLVM IR.
207   FMRL_InaccessibleMem = 16,
208   /// Access to any memory.
209   FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees
210 };
211 
212 /// Summary of how a function affects memory in the program.
213 ///
214 /// Loads from constant globals are not considered memory accesses for this
215 /// interface. Also, functions may freely modify stack space local to their
216 /// invocation without having to report it through these interfaces.
217 enum FunctionModRefBehavior {
218   /// This function does not perform any non-local loads or stores to memory.
219   ///
220   /// This property corresponds to the GCC 'const' attribute.
221   /// This property corresponds to the LLVM IR 'readnone' attribute.
222   /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
223   FMRB_DoesNotAccessMemory =
224       FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),
225 
226   /// The only memory references in this function (if it has any) are
227   /// non-volatile loads from objects pointed to by its pointer-typed
228   /// arguments, with arbitrary offsets.
229   ///
230   /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
231   FMRB_OnlyReadsArgumentPointees =
232       FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),
233 
234   /// The only memory references in this function (if it has any) are
235   /// non-volatile loads and stores from objects pointed to by its
236   /// pointer-typed arguments, with arbitrary offsets.
237   ///
238   /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
239   FMRB_OnlyAccessesArgumentPointees =
240       FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),
241 
242   /// The only memory references in this function (if it has any) are
243   /// references of memory that is otherwise inaccessible via LLVM IR.
244   ///
245   /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
246   FMRB_OnlyAccessesInaccessibleMem =
247       FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),
248 
249   /// The function may perform non-volatile loads and stores of objects
250   /// pointed to by its pointer-typed arguments, with arbitrary offsets, and
251   /// it may also perform loads and stores of memory that is otherwise
252   /// inaccessible via LLVM IR.
253   ///
254   /// This property corresponds to the LLVM IR
255   /// inaccessiblemem_or_argmemonly attribute.
256   FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem |
257                                           FMRL_ArgumentPointees |
258                                           static_cast<int>(ModRefInfo::ModRef),
259 
260   /// This function does not perform any non-local stores or volatile loads,
261   /// but may read from any memory location.
262   ///
263   /// This property corresponds to the GCC 'pure' attribute.
264   /// This property corresponds to the LLVM IR 'readonly' attribute.
265   /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
266   FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref),
267 
268   // This function does not read from memory anywhere, but may write to any
269   // memory location.
270   //
271   // This property corresponds to the LLVM IR 'writeonly' attribute.
272   // This property corresponds to the IntrWriteMem LLVM intrinsic flag.
273   FMRB_DoesNotReadMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod),
274 
275   /// This indicates that the function could not be classified into one of the
276   /// behaviors above.
277   FMRB_UnknownModRefBehavior =
278       FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
279 };
280 
281 // Wrapper method strips bits significant only in FunctionModRefBehavior,
282 // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
283 // ModRefInfo enum changes, the wrapper can be updated to & with the new enum
284 // entry with all bits set to 1.
285 LLVM_NODISCARD inline ModRefInfo
createModRefInfo(const FunctionModRefBehavior FMRB)286 createModRefInfo(const FunctionModRefBehavior FMRB) {
287   return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
288 }
289 
290 class AAResults {
291 public:
292   // Make these results default constructable and movable. We have to spell
293   // these out because MSVC won't synthesize them.
AAResults(const TargetLibraryInfo & TLI)294   AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
295   AAResults(AAResults &&Arg);
296   ~AAResults();
297 
298   /// Register a specific AA result.
addAAResult(AAResultT & AAResult)299   template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
300     // FIXME: We should use a much lighter weight system than the usual
301     // polymorphic pattern because we don't own AAResult. It should
302     // ideally involve two pointers and no separate allocation.
303     AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
304   }
305 
306   /// Register a function analysis ID that the results aggregation depends on.
307   ///
308   /// This is used in the new pass manager to implement the invalidation logic
309   /// where we must invalidate the results aggregation if any of our component
310   /// analyses become invalid.
addAADependencyID(AnalysisKey * ID)311   void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }
312 
313   /// Handle invalidation events in the new pass manager.
314   ///
315   /// The aggregation is invalidated if any of the underlying analyses is
316   /// invalidated.
317   bool invalidate(Function &F, const PreservedAnalyses &PA,
318                   FunctionAnalysisManager::Invalidator &Inv);
319 
320   //===--------------------------------------------------------------------===//
321   /// \name Alias Queries
322   /// @{
323 
324   /// The main low level interface to the alias analysis implementation.
325   /// Returns an AliasResult indicating whether the two pointers are aliased to
326   /// each other. This is the interface that must be implemented by specific
327   /// alias analysis implementations.
328   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
329 
330   /// A convenience wrapper around the primary \c alias interface.
alias(const Value * V1,LocationSize V1Size,const Value * V2,LocationSize V2Size)331   AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
332                     LocationSize V2Size) {
333     return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
334   }
335 
336   /// A convenience wrapper around the primary \c alias interface.
alias(const Value * V1,const Value * V2)337   AliasResult alias(const Value *V1, const Value *V2) {
338     return alias(V1, MemoryLocation::UnknownSize, V2,
339                  MemoryLocation::UnknownSize);
340   }
341 
342   /// A trivial helper function to check to see if the specified pointers are
343   /// no-alias.
isNoAlias(const MemoryLocation & LocA,const MemoryLocation & LocB)344   bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
345     return alias(LocA, LocB) == NoAlias;
346   }
347 
348   /// A convenience wrapper around the \c isNoAlias helper interface.
isNoAlias(const Value * V1,LocationSize V1Size,const Value * V2,LocationSize V2Size)349   bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
350                  LocationSize V2Size) {
351     return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
352   }
353 
354   /// A convenience wrapper around the \c isNoAlias helper interface.
isNoAlias(const Value * V1,const Value * V2)355   bool isNoAlias(const Value *V1, const Value *V2) {
356     return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
357   }
358 
359   /// A trivial helper function to check to see if the specified pointers are
360   /// must-alias.
isMustAlias(const MemoryLocation & LocA,const MemoryLocation & LocB)361   bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
362     return alias(LocA, LocB) == MustAlias;
363   }
364 
365   /// A convenience wrapper around the \c isMustAlias helper interface.
isMustAlias(const Value * V1,const Value * V2)366   bool isMustAlias(const Value *V1, const Value *V2) {
367     return alias(V1, 1, V2, 1) == MustAlias;
368   }
369 
370   /// Checks whether the given location points to constant memory, or if
371   /// \p OrLocal is true whether it points to a local alloca.
372   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
373 
374   /// A convenience wrapper around the primary \c pointsToConstantMemory
375   /// interface.
376   bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
377     return pointsToConstantMemory(MemoryLocation(P), OrLocal);
378   }
379 
380   /// @}
381   //===--------------------------------------------------------------------===//
382   /// \name Simple mod/ref information
383   /// @{
384 
385   /// Get the ModRef info associated with a pointer argument of a callsite. The
386   /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
387   /// that these bits do not necessarily account for the overall behavior of
388   /// the function, but rather only provide additional per-argument
389   /// information. This never sets ModRefInfo::Must.
390   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
391 
392   /// Return the behavior of the given call site.
393   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
394 
395   /// Return the behavior when calling the given function.
396   FunctionModRefBehavior getModRefBehavior(const Function *F);
397 
398   /// Checks if the specified call is known to never read or write memory.
399   ///
400   /// Note that if the call only reads from known-constant memory, it is also
401   /// legal to return true. Also, calls that unwind the stack are legal for
402   /// this predicate.
403   ///
404   /// Many optimizations (such as CSE and LICM) can be performed on such calls
405   /// without worrying about aliasing properties, and many calls have this
406   /// property (e.g. calls to 'sin' and 'cos').
407   ///
408   /// This property corresponds to the GCC 'const' attribute.
doesNotAccessMemory(ImmutableCallSite CS)409   bool doesNotAccessMemory(ImmutableCallSite CS) {
410     return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory;
411   }
412 
413   /// Checks if the specified function is known to never read or write memory.
414   ///
415   /// Note that if the function only reads from known-constant memory, it is
416   /// also legal to return true. Also, function that unwind the stack are legal
417   /// for this predicate.
418   ///
419   /// Many optimizations (such as CSE and LICM) can be performed on such calls
420   /// to such functions without worrying about aliasing properties, and many
421   /// functions have this property (e.g. 'sin' and 'cos').
422   ///
423   /// This property corresponds to the GCC 'const' attribute.
doesNotAccessMemory(const Function * F)424   bool doesNotAccessMemory(const Function *F) {
425     return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
426   }
427 
428   /// Checks if the specified call is known to only read from non-volatile
429   /// memory (or not access memory at all).
430   ///
431   /// Calls that unwind the stack are legal for this predicate.
432   ///
433   /// This property allows many common optimizations to be performed in the
434   /// absence of interfering store instructions, such as CSE of strlen calls.
435   ///
436   /// This property corresponds to the GCC 'pure' attribute.
onlyReadsMemory(ImmutableCallSite CS)437   bool onlyReadsMemory(ImmutableCallSite CS) {
438     return onlyReadsMemory(getModRefBehavior(CS));
439   }
440 
441   /// Checks if the specified function is known to only read from non-volatile
442   /// memory (or not access memory at all).
443   ///
444   /// Functions that unwind the stack are legal for this predicate.
445   ///
446   /// This property allows many common optimizations to be performed in the
447   /// absence of interfering store instructions, such as CSE of strlen calls.
448   ///
449   /// This property corresponds to the GCC 'pure' attribute.
onlyReadsMemory(const Function * F)450   bool onlyReadsMemory(const Function *F) {
451     return onlyReadsMemory(getModRefBehavior(F));
452   }
453 
454   /// Checks if functions with the specified behavior are known to only read
455   /// from non-volatile memory (or not access memory at all).
onlyReadsMemory(FunctionModRefBehavior MRB)456   static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
457     return !isModSet(createModRefInfo(MRB));
458   }
459 
460   /// Checks if functions with the specified behavior are known to only write
461   /// memory (or not access memory at all).
doesNotReadMemory(FunctionModRefBehavior MRB)462   static bool doesNotReadMemory(FunctionModRefBehavior MRB) {
463     return !isRefSet(createModRefInfo(MRB));
464   }
465 
466   /// Checks if functions with the specified behavior are known to read and
467   /// write at most from objects pointed to by their pointer-typed arguments
468   /// (with arbitrary offsets).
onlyAccessesArgPointees(FunctionModRefBehavior MRB)469   static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
470     return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
471   }
472 
473   /// Checks if functions with the specified behavior are known to potentially
474   /// read or write from objects pointed to be their pointer-typed arguments
475   /// (with arbitrary offsets).
doesAccessArgPointees(FunctionModRefBehavior MRB)476   static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
477     return isModOrRefSet(createModRefInfo(MRB)) &&
478            (MRB & FMRL_ArgumentPointees);
479   }
480 
481   /// Checks if functions with the specified behavior are known to read and
482   /// write at most from memory that is inaccessible from LLVM IR.
onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB)483   static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) {
484     return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
485   }
486 
487   /// Checks if functions with the specified behavior are known to potentially
488   /// read or write from memory that is inaccessible from LLVM IR.
doesAccessInaccessibleMem(FunctionModRefBehavior MRB)489   static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) {
490     return isModOrRefSet(createModRefInfo(MRB)) && (MRB & FMRL_InaccessibleMem);
491   }
492 
493   /// Checks if functions with the specified behavior are known to read and
494   /// write at most from memory that is inaccessible from LLVM IR or objects
495   /// pointed to by their pointer-typed arguments (with arbitrary offsets).
onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB)496   static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) {
497     return !(MRB & FMRL_Anywhere &
498              ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees));
499   }
500 
501   /// getModRefInfo (for call sites) - Return information about whether
502   /// a particular call site modifies or reads the specified memory location.
503   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
504 
505   /// getModRefInfo (for call sites) - A convenience wrapper.
getModRefInfo(ImmutableCallSite CS,const Value * P,LocationSize Size)506   ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
507                            LocationSize Size) {
508     return getModRefInfo(CS, MemoryLocation(P, Size));
509   }
510 
511   /// getModRefInfo (for calls) - Return information about whether
512   /// a particular call modifies or reads the specified memory location.
getModRefInfo(const CallInst * C,const MemoryLocation & Loc)513   ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
514     return getModRefInfo(ImmutableCallSite(C), Loc);
515   }
516 
517   /// getModRefInfo (for calls) - A convenience wrapper.
getModRefInfo(const CallInst * C,const Value * P,LocationSize Size)518   ModRefInfo getModRefInfo(const CallInst *C, const Value *P,
519                            LocationSize Size) {
520     return getModRefInfo(C, MemoryLocation(P, Size));
521   }
522 
523   /// getModRefInfo (for invokes) - Return information about whether
524   /// a particular invoke modifies or reads the specified memory location.
getModRefInfo(const InvokeInst * I,const MemoryLocation & Loc)525   ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
526     return getModRefInfo(ImmutableCallSite(I), Loc);
527   }
528 
529   /// getModRefInfo (for invokes) - A convenience wrapper.
getModRefInfo(const InvokeInst * I,const Value * P,LocationSize Size)530   ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P,
531                            LocationSize Size) {
532     return getModRefInfo(I, MemoryLocation(P, Size));
533   }
534 
535   /// getModRefInfo (for loads) - Return information about whether
536   /// a particular load modifies or reads the specified memory location.
537   ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
538 
539   /// getModRefInfo (for loads) - A convenience wrapper.
getModRefInfo(const LoadInst * L,const Value * P,LocationSize Size)540   ModRefInfo getModRefInfo(const LoadInst *L, const Value *P,
541                            LocationSize Size) {
542     return getModRefInfo(L, MemoryLocation(P, Size));
543   }
544 
545   /// getModRefInfo (for stores) - Return information about whether
546   /// a particular store modifies or reads the specified memory location.
547   ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
548 
549   /// getModRefInfo (for stores) - A convenience wrapper.
getModRefInfo(const StoreInst * S,const Value * P,LocationSize Size)550   ModRefInfo getModRefInfo(const StoreInst *S, const Value *P,
551                            LocationSize Size) {
552     return getModRefInfo(S, MemoryLocation(P, Size));
553   }
554 
555   /// getModRefInfo (for fences) - Return information about whether
556   /// a particular store modifies or reads the specified memory location.
557   ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
558 
559   /// getModRefInfo (for fences) - A convenience wrapper.
getModRefInfo(const FenceInst * S,const Value * P,LocationSize Size)560   ModRefInfo getModRefInfo(const FenceInst *S, const Value *P,
561                            LocationSize Size) {
562     return getModRefInfo(S, MemoryLocation(P, Size));
563   }
564 
565   /// getModRefInfo (for cmpxchges) - Return information about whether
566   /// a particular cmpxchg modifies or reads the specified memory location.
567   ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
568                            const MemoryLocation &Loc);
569 
570   /// getModRefInfo (for cmpxchges) - A convenience wrapper.
getModRefInfo(const AtomicCmpXchgInst * CX,const Value * P,unsigned Size)571   ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
572                            unsigned Size) {
573     return getModRefInfo(CX, MemoryLocation(P, Size));
574   }
575 
576   /// getModRefInfo (for atomicrmws) - Return information about whether
577   /// a particular atomicrmw modifies or reads the specified memory location.
578   ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
579 
580   /// getModRefInfo (for atomicrmws) - A convenience wrapper.
getModRefInfo(const AtomicRMWInst * RMW,const Value * P,unsigned Size)581   ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
582                            unsigned Size) {
583     return getModRefInfo(RMW, MemoryLocation(P, Size));
584   }
585 
586   /// getModRefInfo (for va_args) - Return information about whether
587   /// a particular va_arg modifies or reads the specified memory location.
588   ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
589 
590   /// getModRefInfo (for va_args) - A convenience wrapper.
getModRefInfo(const VAArgInst * I,const Value * P,LocationSize Size)591   ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P,
592                            LocationSize Size) {
593     return getModRefInfo(I, MemoryLocation(P, Size));
594   }
595 
596   /// getModRefInfo (for catchpads) - Return information about whether
597   /// a particular catchpad modifies or reads the specified memory location.
598   ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
599 
600   /// getModRefInfo (for catchpads) - A convenience wrapper.
getModRefInfo(const CatchPadInst * I,const Value * P,LocationSize Size)601   ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
602                            LocationSize Size) {
603     return getModRefInfo(I, MemoryLocation(P, Size));
604   }
605 
606   /// getModRefInfo (for catchrets) - Return information about whether
607   /// a particular catchret modifies or reads the specified memory location.
608   ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
609 
610   /// getModRefInfo (for catchrets) - A convenience wrapper.
getModRefInfo(const CatchReturnInst * I,const Value * P,LocationSize Size)611   ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
612                            LocationSize Size) {
613     return getModRefInfo(I, MemoryLocation(P, Size));
614   }
615 
616   /// Check whether or not an instruction may read or write the optionally
617   /// specified memory location.
618   ///
619   ///
620   /// An instruction that doesn't read or write memory may be trivially LICM'd
621   /// for example.
622   ///
623   /// For function calls, this delegates to the alias-analysis specific
624   /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
625   /// helpers above.
getModRefInfo(const Instruction * I,const Optional<MemoryLocation> & OptLoc)626   ModRefInfo getModRefInfo(const Instruction *I,
627                            const Optional<MemoryLocation> &OptLoc) {
628     if (OptLoc == None) {
629       if (auto CS = ImmutableCallSite(I)) {
630         return createModRefInfo(getModRefBehavior(CS));
631       }
632     }
633 
634     const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
635 
636     switch (I->getOpcode()) {
637     case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, Loc);
638     case Instruction::Load:   return getModRefInfo((const LoadInst*)I,  Loc);
639     case Instruction::Store:  return getModRefInfo((const StoreInst*)I, Loc);
640     case Instruction::Fence:  return getModRefInfo((const FenceInst*)I, Loc);
641     case Instruction::AtomicCmpXchg:
642       return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
643     case Instruction::AtomicRMW:
644       return getModRefInfo((const AtomicRMWInst*)I, Loc);
645     case Instruction::Call:   return getModRefInfo((const CallInst*)I,  Loc);
646     case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
647     case Instruction::CatchPad:
648       return getModRefInfo((const CatchPadInst *)I, Loc);
649     case Instruction::CatchRet:
650       return getModRefInfo((const CatchReturnInst *)I, Loc);
651     default:
652       return ModRefInfo::NoModRef;
653     }
654   }
655 
656   /// A convenience wrapper for constructing the memory location.
getModRefInfo(const Instruction * I,const Value * P,LocationSize Size)657   ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
658                            LocationSize Size) {
659     return getModRefInfo(I, MemoryLocation(P, Size));
660   }
661 
662   /// Return information about whether a call and an instruction may refer to
663   /// the same memory locations.
664   ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
665 
666   /// Return information about whether two call sites may refer to the same set
667   /// of memory locations. See the AA documentation for details:
668   ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
669   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
670 
671   /// Return information about whether a particular call site modifies
672   /// or reads the specified memory location \p MemLoc before instruction \p I
673   /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
674   /// instruction ordering queries inside the BasicBlock containing \p I.
675   /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
676   /// set.
677   ModRefInfo callCapturesBefore(const Instruction *I,
678                                 const MemoryLocation &MemLoc, DominatorTree *DT,
679                                 OrderedBasicBlock *OBB = nullptr);
680 
681   /// A convenience wrapper to synthesize a memory location.
682   ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
683                                 LocationSize Size, DominatorTree *DT,
684                                 OrderedBasicBlock *OBB = nullptr) {
685     return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
686   }
687 
688   /// @}
689   //===--------------------------------------------------------------------===//
690   /// \name Higher level methods for querying mod/ref information.
691   /// @{
692 
693   /// Check if it is possible for execution of the specified basic block to
694   /// modify the location Loc.
695   bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
696 
697   /// A convenience wrapper synthesizing a memory location.
canBasicBlockModify(const BasicBlock & BB,const Value * P,LocationSize Size)698   bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
699                            LocationSize Size) {
700     return canBasicBlockModify(BB, MemoryLocation(P, Size));
701   }
702 
703   /// Check if it is possible for the execution of the specified instructions
704   /// to mod\ref (according to the mode) the location Loc.
705   ///
706   /// The instructions to consider are all of the instructions in the range of
707   /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
708   bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
709                                  const MemoryLocation &Loc,
710                                  const ModRefInfo Mode);
711 
712   /// A convenience wrapper synthesizing a memory location.
canInstructionRangeModRef(const Instruction & I1,const Instruction & I2,const Value * Ptr,LocationSize Size,const ModRefInfo Mode)713   bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
714                                  const Value *Ptr, LocationSize Size,
715                                  const ModRefInfo Mode) {
716     return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
717   }
718 
719 private:
720   class Concept;
721 
722   template <typename T> class Model;
723 
724   template <typename T> friend class AAResultBase;
725 
726   const TargetLibraryInfo &TLI;
727 
728   std::vector<std::unique_ptr<Concept>> AAs;
729 
730   std::vector<AnalysisKey *> AADeps;
731 };
732 
733 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
734 /// pointer or reference.
735 using AliasAnalysis = AAResults;
736 
737 /// A private abstract base class describing the concept of an individual alias
738 /// analysis implementation.
739 ///
740 /// This interface is implemented by any \c Model instantiation. It is also the
741 /// interface which a type used to instantiate the model must provide.
742 ///
743 /// All of these methods model methods by the same name in the \c
744 /// AAResults class. Only differences and specifics to how the
745 /// implementations are called are documented here.
746 class AAResults::Concept {
747 public:
748   virtual ~Concept() = 0;
749 
750   /// An update API used internally by the AAResults to provide
751   /// a handle back to the top level aggregation.
752   virtual void setAAResults(AAResults *NewAAR) = 0;
753 
754   //===--------------------------------------------------------------------===//
755   /// \name Alias Queries
756   /// @{
757 
758   /// The main low level interface to the alias analysis implementation.
759   /// Returns an AliasResult indicating whether the two pointers are aliased to
760   /// each other. This is the interface that must be implemented by specific
761   /// alias analysis implementations.
762   virtual AliasResult alias(const MemoryLocation &LocA,
763                             const MemoryLocation &LocB) = 0;
764 
765   /// Checks whether the given location points to constant memory, or if
766   /// \p OrLocal is true whether it points to a local alloca.
767   virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
768                                       bool OrLocal) = 0;
769 
770   /// @}
771   //===--------------------------------------------------------------------===//
772   /// \name Simple mod/ref information
773   /// @{
774 
775   /// Get the ModRef info associated with a pointer argument of a callsite. The
776   /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
777   /// that these bits do not necessarily account for the overall behavior of
778   /// the function, but rather only provide additional per-argument
779   /// information.
780   virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS,
781                                       unsigned ArgIdx) = 0;
782 
783   /// Return the behavior of the given call site.
784   virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) = 0;
785 
786   /// Return the behavior when calling the given function.
787   virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
788 
789   /// getModRefInfo (for call sites) - Return information about whether
790   /// a particular call site modifies or reads the specified memory location.
791   virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
792                                    const MemoryLocation &Loc) = 0;
793 
794   /// Return information about whether two call sites may refer to the same set
795   /// of memory locations. See the AA documentation for details:
796   ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
797   virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
798                                    ImmutableCallSite CS2) = 0;
799 
800   /// @}
801 };
802 
803 /// A private class template which derives from \c Concept and wraps some other
804 /// type.
805 ///
806 /// This models the concept by directly forwarding each interface point to the
807 /// wrapped type which must implement a compatible interface. This provides
808 /// a type erased binding.
809 template <typename AAResultT> class AAResults::Model final : public Concept {
810   AAResultT &Result;
811 
812 public:
Model(AAResultT & Result,AAResults & AAR)813   explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
814     Result.setAAResults(&AAR);
815   }
816   ~Model() override = default;
817 
setAAResults(AAResults * NewAAR)818   void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
819 
alias(const MemoryLocation & LocA,const MemoryLocation & LocB)820   AliasResult alias(const MemoryLocation &LocA,
821                     const MemoryLocation &LocB) override {
822     return Result.alias(LocA, LocB);
823   }
824 
pointsToConstantMemory(const MemoryLocation & Loc,bool OrLocal)825   bool pointsToConstantMemory(const MemoryLocation &Loc,
826                               bool OrLocal) override {
827     return Result.pointsToConstantMemory(Loc, OrLocal);
828   }
829 
getArgModRefInfo(ImmutableCallSite CS,unsigned ArgIdx)830   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override {
831     return Result.getArgModRefInfo(CS, ArgIdx);
832   }
833 
getModRefBehavior(ImmutableCallSite CS)834   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override {
835     return Result.getModRefBehavior(CS);
836   }
837 
getModRefBehavior(const Function * F)838   FunctionModRefBehavior getModRefBehavior(const Function *F) override {
839     return Result.getModRefBehavior(F);
840   }
841 
getModRefInfo(ImmutableCallSite CS,const MemoryLocation & Loc)842   ModRefInfo getModRefInfo(ImmutableCallSite CS,
843                            const MemoryLocation &Loc) override {
844     return Result.getModRefInfo(CS, Loc);
845   }
846 
getModRefInfo(ImmutableCallSite CS1,ImmutableCallSite CS2)847   ModRefInfo getModRefInfo(ImmutableCallSite CS1,
848                            ImmutableCallSite CS2) override {
849     return Result.getModRefInfo(CS1, CS2);
850   }
851 };
852 
853 /// A CRTP-driven "mixin" base class to help implement the function alias
854 /// analysis results concept.
855 ///
856 /// Because of the nature of many alias analysis implementations, they often
857 /// only implement a subset of the interface. This base class will attempt to
858 /// implement the remaining portions of the interface in terms of simpler forms
859 /// of the interface where possible, and otherwise provide conservatively
860 /// correct fallback implementations.
861 ///
862 /// Implementors of an alias analysis should derive from this CRTP, and then
863 /// override specific methods that they wish to customize. There is no need to
864 /// use virtual anywhere, the CRTP base class does static dispatch to the
865 /// derived type passed into it.
866 template <typename DerivedT> class AAResultBase {
867   // Expose some parts of the interface only to the AAResults::Model
868   // for wrapping. Specifically, this allows the model to call our
869   // setAAResults method without exposing it as a fully public API.
870   friend class AAResults::Model<DerivedT>;
871 
872   /// A pointer to the AAResults object that this AAResult is
873   /// aggregated within. May be null if not aggregated.
874   AAResults *AAR;
875 
876   /// Helper to dispatch calls back through the derived type.
derived()877   DerivedT &derived() { return static_cast<DerivedT &>(*this); }
878 
879   /// A setter for the AAResults pointer, which is used to satisfy the
880   /// AAResults::Model contract.
setAAResults(AAResults * NewAAR)881   void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
882 
883 protected:
884   /// This proxy class models a common pattern where we delegate to either the
885   /// top-level \c AAResults aggregation if one is registered, or to the
886   /// current result if none are registered.
887   class AAResultsProxy {
888     AAResults *AAR;
889     DerivedT &CurrentResult;
890 
891   public:
AAResultsProxy(AAResults * AAR,DerivedT & CurrentResult)892     AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
893         : AAR(AAR), CurrentResult(CurrentResult) {}
894 
alias(const MemoryLocation & LocA,const MemoryLocation & LocB)895     AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
896       return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB);
897     }
898 
pointsToConstantMemory(const MemoryLocation & Loc,bool OrLocal)899     bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
900       return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal)
901                  : CurrentResult.pointsToConstantMemory(Loc, OrLocal);
902     }
903 
getArgModRefInfo(ImmutableCallSite CS,unsigned ArgIdx)904     ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
905       return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx);
906     }
907 
getModRefBehavior(ImmutableCallSite CS)908     FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
909       return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS);
910     }
911 
getModRefBehavior(const Function * F)912     FunctionModRefBehavior getModRefBehavior(const Function *F) {
913       return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
914     }
915 
getModRefInfo(ImmutableCallSite CS,const MemoryLocation & Loc)916     ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
917       return AAR ? AAR->getModRefInfo(CS, Loc)
918                  : CurrentResult.getModRefInfo(CS, Loc);
919     }
920 
getModRefInfo(ImmutableCallSite CS1,ImmutableCallSite CS2)921     ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
922       return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2);
923     }
924   };
925 
926   explicit AAResultBase() = default;
927 
928   // Provide all the copy and move constructors so that derived types aren't
929   // constrained.
AAResultBase(const AAResultBase & Arg)930   AAResultBase(const AAResultBase &Arg) {}
AAResultBase(AAResultBase && Arg)931   AAResultBase(AAResultBase &&Arg) {}
932 
933   /// Get a proxy for the best AA result set to query at this time.
934   ///
935   /// When this result is part of a larger aggregation, this will proxy to that
936   /// aggregation. When this result is used in isolation, it will just delegate
937   /// back to the derived class's implementation.
938   ///
939   /// Note that callers of this need to take considerable care to not cause
940   /// performance problems when they use this routine, in the case of a large
941   /// number of alias analyses being aggregated, it can be expensive to walk
942   /// back across the chain.
getBestAAResults()943   AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
944 
945 public:
alias(const MemoryLocation & LocA,const MemoryLocation & LocB)946   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
947     return MayAlias;
948   }
949 
pointsToConstantMemory(const MemoryLocation & Loc,bool OrLocal)950   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
951     return false;
952   }
953 
getArgModRefInfo(ImmutableCallSite CS,unsigned ArgIdx)954   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
955     return ModRefInfo::ModRef;
956   }
957 
getModRefBehavior(ImmutableCallSite CS)958   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
959     return FMRB_UnknownModRefBehavior;
960   }
961 
getModRefBehavior(const Function * F)962   FunctionModRefBehavior getModRefBehavior(const Function *F) {
963     return FMRB_UnknownModRefBehavior;
964   }
965 
getModRefInfo(ImmutableCallSite CS,const MemoryLocation & Loc)966   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
967     return ModRefInfo::ModRef;
968   }
969 
getModRefInfo(ImmutableCallSite CS1,ImmutableCallSite CS2)970   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
971     return ModRefInfo::ModRef;
972   }
973 };
974 
975 /// Return true if this pointer is returned by a noalias function.
976 bool isNoAliasCall(const Value *V);
977 
978 /// Return true if this is an argument with the noalias attribute.
979 bool isNoAliasArgument(const Value *V);
980 
981 /// Return true if this pointer refers to a distinct and identifiable object.
982 /// This returns true for:
983 ///    Global Variables and Functions (but not Global Aliases)
984 ///    Allocas
985 ///    ByVal and NoAlias Arguments
986 ///    NoAlias returns (e.g. calls to malloc)
987 ///
988 bool isIdentifiedObject(const Value *V);
989 
990 /// Return true if V is umabigously identified at the function-level.
991 /// Different IdentifiedFunctionLocals can't alias.
992 /// Further, an IdentifiedFunctionLocal can not alias with any function
993 /// arguments other than itself, which is not necessarily true for
994 /// IdentifiedObjects.
995 bool isIdentifiedFunctionLocal(const Value *V);
996 
997 /// A manager for alias analyses.
998 ///
999 /// This class can have analyses registered with it and when run, it will run
1000 /// all of them and aggregate their results into single AA results interface
1001 /// that dispatches across all of the alias analysis results available.
1002 ///
1003 /// Note that the order in which analyses are registered is very significant.
1004 /// That is the order in which the results will be aggregated and queried.
1005 ///
1006 /// This manager effectively wraps the AnalysisManager for registering alias
1007 /// analyses. When you register your alias analysis with this manager, it will
1008 /// ensure the analysis itself is registered with its AnalysisManager.
1009 class AAManager : public AnalysisInfoMixin<AAManager> {
1010 public:
1011   using Result = AAResults;
1012 
1013   /// Register a specific AA result.
registerFunctionAnalysis()1014   template <typename AnalysisT> void registerFunctionAnalysis() {
1015     ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
1016   }
1017 
1018   /// Register a specific AA result.
registerModuleAnalysis()1019   template <typename AnalysisT> void registerModuleAnalysis() {
1020     ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
1021   }
1022 
run(Function & F,FunctionAnalysisManager & AM)1023   Result run(Function &F, FunctionAnalysisManager &AM) {
1024     Result R(AM.getResult<TargetLibraryAnalysis>(F));
1025     for (auto &Getter : ResultGetters)
1026       (*Getter)(F, AM, R);
1027     return R;
1028   }
1029 
1030 private:
1031   friend AnalysisInfoMixin<AAManager>;
1032 
1033   static AnalysisKey Key;
1034 
1035   SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
1036                        AAResults &AAResults),
1037               4> ResultGetters;
1038 
1039   template <typename AnalysisT>
getFunctionAAResultImpl(Function & F,FunctionAnalysisManager & AM,AAResults & AAResults)1040   static void getFunctionAAResultImpl(Function &F,
1041                                       FunctionAnalysisManager &AM,
1042                                       AAResults &AAResults) {
1043     AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1044     AAResults.addAADependencyID(AnalysisT::ID());
1045   }
1046 
1047   template <typename AnalysisT>
getModuleAAResultImpl(Function & F,FunctionAnalysisManager & AM,AAResults & AAResults)1048   static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
1049                                     AAResults &AAResults) {
1050     auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1051     auto &MAM = MAMProxy.getManager();
1052     if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) {
1053       AAResults.addAAResult(*R);
1054       MAMProxy
1055           .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
1056     }
1057   }
1058 };
1059 
1060 /// A wrapper pass to provide the legacy pass manager access to a suitably
1061 /// prepared AAResults object.
1062 class AAResultsWrapperPass : public FunctionPass {
1063   std::unique_ptr<AAResults> AAR;
1064 
1065 public:
1066   static char ID;
1067 
1068   AAResultsWrapperPass();
1069 
getAAResults()1070   AAResults &getAAResults() { return *AAR; }
getAAResults()1071   const AAResults &getAAResults() const { return *AAR; }
1072 
1073   bool runOnFunction(Function &F) override;
1074 
1075   void getAnalysisUsage(AnalysisUsage &AU) const override;
1076 };
1077 
1078 FunctionPass *createAAResultsWrapperPass();
1079 
1080 /// A wrapper pass around a callback which can be used to populate the
1081 /// AAResults in the AAResultsWrapperPass from an external AA.
1082 ///
1083 /// The callback provided here will be used each time we prepare an AAResults
1084 /// object, and will receive a reference to the function wrapper pass, the
1085 /// function, and the AAResults object to populate. This should be used when
1086 /// setting up a custom pass pipeline to inject a hook into the AA results.
1087 ImmutablePass *createExternalAAWrapperPass(
1088     std::function<void(Pass &, Function &, AAResults &)> Callback);
1089 
1090 /// A helper for the legacy pass manager to create a \c AAResults
1091 /// object populated to the best of our ability for a particular function when
1092 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
1093 ///
1094 /// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1095 /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1096 /// getAnalysisUsage.
1097 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
1098 
1099 /// A helper for the legacy pass manager to populate \p AU to add uses to make
1100 /// sure the analyses required by \p createLegacyPMAAResults are available.
1101 void getAAResultsAnalysisUsage(AnalysisUsage &AU);
1102 
1103 } // end namespace llvm
1104 
1105 #endif // LLVM_ANALYSIS_ALIASANALYSIS_H
1106