LLVM  10.0.0svn
AliasAnalysis.h
Go to the documentation of this file.
1 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the generic AliasAnalysis interface, which is used as the
10 // common interface used by all clients of alias analysis information, and
11 // implemented by all alias analysis implementations. Mod/Ref information is
12 // also captured by this interface.
13 //
14 // Implementations of this interface must implement the various virtual methods,
15 // which automatically provides functionality for the entire suite of client
16 // APIs.
17 //
18 // This API identifies memory regions with the MemoryLocation class. The pointer
19 // component specifies the base memory address of the region. The Size specifies
20 // the maximum size (in address units) of the memory region, or
21 // MemoryLocation::UnknownSize if the size is not known. The TBAA tag
22 // identifies the "type" of the memory reference; see the
23 // TypeBasedAliasAnalysis class for details.
24 //
25 // Some non-obvious details include:
26 // - Pointers that point to two completely different objects in memory never
27 // alias, regardless of the value of the Size component.
28 // - NoAlias doesn't imply inequal pointers. The most obvious example of this
29 // is two pointers to constant memory. Even if they are equal, constant
30 // memory is never stored to, so there will never be any dependencies.
31 // In this and other situations, the pointers may be both NoAlias and
32 // MustAlias at the same time. The current API can only return one result,
33 // though this is rarely a problem in practice.
34 //
35 //===----------------------------------------------------------------------===//
36 
37 #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
38 #define LLVM_ANALYSIS_ALIASANALYSIS_H
39 
40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/None.h"
42 #include "llvm/ADT/Optional.h"
43 #include "llvm/ADT/SmallVector.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/IR/Instruction.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/PassManager.h"
50 #include "llvm/Pass.h"
51 #include <cstdint>
52 #include <functional>
53 #include <memory>
54 #include <vector>
55 
56 namespace llvm {
57 
58 class AnalysisUsage;
59 class BasicAAResult;
60 class BasicBlock;
61 class DominatorTree;
62 class OrderedBasicBlock;
63 class Value;
64 
65 /// The possible results of an alias query.
66 ///
67 /// These results are always computed between two MemoryLocation objects as
68 /// a query to some alias analysis.
69 ///
70 /// Note that these are unscoped enumerations because we would like to support
71 /// implicitly testing a result for the existence of any possible aliasing with
72 /// a conversion to bool, but an "enum class" doesn't support this. The
73 /// canonical names from the literature are suffixed and unique anyways, and so
74 /// they serve as global constants in LLVM for these results.
75 ///
76 /// See docs/AliasAnalysis.html for more information on the specific meanings
77 /// of these values.
78 enum AliasResult : uint8_t {
79  /// The two locations do not alias at all.
80  ///
81  /// This value is arranged to convert to false, while all other values
82  /// convert to true. This allows a boolean context to convert the result to
83  /// a binary flag indicating whether there is the possibility of aliasing.
84  NoAlias = 0,
85  /// The two locations may or may not alias. This is the least precise result.
87  /// The two locations alias, but only due to a partial overlap.
89  /// The two locations precisely alias each other.
91 };
92 
93 /// << operator for AliasResult.
95 
96 /// Flags indicating whether a memory access modifies or references memory.
97 ///
98 /// This is no access at all, a modification, a reference, or both
99 /// a modification and a reference. These are specifically structured such that
100 /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
101 /// work with any of the possible values.
102 enum class ModRefInfo : uint8_t {
103  /// Must is provided for completeness, but no routines will return only
104  /// Must today. See definition of Must below.
105  Must = 0,
106  /// The access may reference the value stored in memory,
107  /// a mustAlias relation was found, and no mayAlias or partialAlias found.
108  MustRef = 1,
109  /// The access may modify the value stored in memory,
110  /// a mustAlias relation was found, and no mayAlias or partialAlias found.
111  MustMod = 2,
112  /// The access may reference, modify or both the value stored in memory,
113  /// a mustAlias relation was found, and no mayAlias or partialAlias found.
115  /// The access neither references nor modifies the value stored in memory.
116  NoModRef = 4,
117  /// The access may reference the value stored in memory.
118  Ref = NoModRef | MustRef,
119  /// The access may modify the value stored in memory.
120  Mod = NoModRef | MustMod,
121  /// The access may reference and may modify the value stored in memory.
122  ModRef = Ref | Mod,
123 
124  /// About Must:
125  /// Must is set in a best effort manner.
126  /// We usually do not try our best to infer Must, instead it is merely
127  /// another piece of "free" information that is presented when available.
128  /// Must set means there was certainly a MustAlias found. For calls,
129  /// where multiple arguments are checked (argmemonly), this translates to
130  /// only MustAlias or NoAlias was found.
131  /// Must is not set for RAR accesses, even if the two locations must
132  /// alias. The reason is that two read accesses translate to an early return
133  /// of NoModRef. An additional alias check to set Must may be
134  /// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
135  /// We refer to Must being *set* when the most significant bit is *cleared*.
136  /// Conversely we *clear* Must information by *setting* the Must bit to 1.
137 };
138 
140  return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
141  static_cast<int>(ModRefInfo::Must);
142 }
144  return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
145 }
147  return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
148  static_cast<int>(ModRefInfo::MustModRef);
149 }
150 LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) {
151  return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
152 }
153 LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) {
154  return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
155 }
157  return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
158 }
159 
161  return ModRefInfo(static_cast<int>(MRI) |
162  static_cast<int>(ModRefInfo::MustMod));
163 }
165  return ModRefInfo(static_cast<int>(MRI) |
166  static_cast<int>(ModRefInfo::MustRef));
167 }
169  return ModRefInfo(static_cast<int>(MRI) &
170  static_cast<int>(ModRefInfo::MustModRef));
171 }
173  return ModRefInfo(static_cast<int>(MRI) |
174  static_cast<int>(ModRefInfo::MustModRef));
175 }
177  return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
178 }
180  return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
181 }
183  return ModRefInfo(static_cast<int>(MRI) |
184  static_cast<int>(ModRefInfo::NoModRef));
185 }
187  const ModRefInfo MRI2) {
188  return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
189 }
191  const ModRefInfo MRI2) {
192  return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
193 }
194 
195 /// The locations at which a function might access memory.
196 ///
197 /// These are primarily used in conjunction with the \c AccessKind bits to
198 /// describe both the nature of access and the locations of access for a
199 /// function call.
201  /// Base case is no access to memory.
203  /// Access to memory via argument pointers.
205  /// Memory that is inaccessible via LLVM IR.
207  /// Access to any memory.
209 };
210 
211 /// Summary of how a function affects memory in the program.
212 ///
213 /// Loads from constant globals are not considered memory accesses for this
214 /// interface. Also, functions may freely modify stack space local to their
215 /// invocation without having to report it through these interfaces.
217  /// This function does not perform any non-local loads or stores to memory.
218  ///
219  /// This property corresponds to the GCC 'const' attribute.
220  /// This property corresponds to the LLVM IR 'readnone' attribute.
221  /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
223  FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),
224 
225  /// The only memory references in this function (if it has any) are
226  /// non-volatile loads from objects pointed to by its pointer-typed
227  /// arguments, with arbitrary offsets.
228  ///
229  /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag.
231  FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),
232 
233  /// The only memory references in this function (if it has any) are
234  /// non-volatile loads and stores from objects pointed to by its
235  /// pointer-typed arguments, with arbitrary offsets.
236  ///
237  /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
239  FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),
240 
241  /// The only memory references in this function (if it has any) are
242  /// references of memory that is otherwise inaccessible via LLVM IR.
243  ///
244  /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
246  FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),
247 
248  /// The function may perform non-volatile loads and stores of objects
249  /// pointed to by its pointer-typed arguments, with arbitrary offsets, and
250  /// it may also perform loads and stores of memory that is otherwise
251  /// inaccessible via LLVM IR.
252  ///
253  /// This property corresponds to the LLVM IR
254  /// inaccessiblemem_or_argmemonly attribute.
257  static_cast<int>(ModRefInfo::ModRef),
258 
259  /// This function does not perform any non-local stores or volatile loads,
260  /// but may read from any memory location.
261  ///
262  /// This property corresponds to the GCC 'pure' attribute.
263  /// This property corresponds to the LLVM IR 'readonly' attribute.
264  /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
266 
267  // This function does not read from memory anywhere, but may write to any
268  // memory location.
269  //
270  // This property corresponds to the LLVM IR 'writeonly' attribute.
271  // This property corresponds to the IntrWriteMem LLVM intrinsic flag.
273 
274  /// This indicates that the function could not be classified into one of the
275  /// behaviors above.
277  FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
278 };
279 
280 // Wrapper method strips bits significant only in FunctionModRefBehavior,
281 // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
282 // ModRefInfo enum changes, the wrapper can be updated to & with the new enum
283 // entry with all bits set to 1.
286  return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
287 }
288 
289 /// This class stores info we want to provide to or retain within an alias
290 /// query. By default, the root query is stateless and starts with a freshly
291 /// constructed info object. Specific alias analyses can use this query info to
292 /// store per-query state that is important for recursive or nested queries to
293 /// avoid recomputing. To enable preserving this state across multiple queries
294 /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
295 /// The information stored in an `AAQueryInfo` is currently limitted to the
296 /// caches used by BasicAA, but can further be extended to fit other AA needs.
297 class AAQueryInfo {
298 public:
299  using LocPair = std::pair<MemoryLocation, MemoryLocation>;
302 
305 
306  AAQueryInfo() : AliasCache(), IsCapturedCache() {}
307 };
308 
309 class BatchAAResults;
310 
311 class AAResults {
312 public:
313  // Make these results default constructable and movable. We have to spell
314  // these out because MSVC won't synthesize them.
315  AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
317  ~AAResults();
318 
319  /// Register a specific AA result.
320  template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
321  // FIXME: We should use a much lighter weight system than the usual
322  // polymorphic pattern because we don't own AAResult. It should
323  // ideally involve two pointers and no separate allocation.
324  AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
325  }
326 
327  /// Register a function analysis ID that the results aggregation depends on.
328  ///
329  /// This is used in the new pass manager to implement the invalidation logic
330  /// where we must invalidate the results aggregation if any of our component
331  /// analyses become invalid.
332  void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }
333 
334  /// Handle invalidation events in the new pass manager.
335  ///
336  /// The aggregation is invalidated if any of the underlying analyses is
337  /// invalidated.
338  bool invalidate(Function &F, const PreservedAnalyses &PA,
340 
341  //===--------------------------------------------------------------------===//
342  /// \name Alias Queries
343  /// @{
344 
345  /// The main low level interface to the alias analysis implementation.
346  /// Returns an AliasResult indicating whether the two pointers are aliased to
347  /// each other. This is the interface that must be implemented by specific
348  /// alias analysis implementations.
349  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
350 
351  /// A convenience wrapper around the primary \c alias interface.
352  AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
353  LocationSize V2Size) {
354  return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
355  }
356 
357  /// A convenience wrapper around the primary \c alias interface.
358  AliasResult alias(const Value *V1, const Value *V2) {
359  return alias(V1, LocationSize::unknown(), V2, LocationSize::unknown());
360  }
361 
362  /// A trivial helper function to check to see if the specified pointers are
363  /// no-alias.
364  bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
365  return alias(LocA, LocB) == NoAlias;
366  }
367 
368  /// A convenience wrapper around the \c isNoAlias helper interface.
369  bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
370  LocationSize V2Size) {
371  return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
372  }
373 
374  /// A convenience wrapper around the \c isNoAlias helper interface.
375  bool isNoAlias(const Value *V1, const Value *V2) {
376  return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
377  }
378 
379  /// A trivial helper function to check to see if the specified pointers are
380  /// must-alias.
381  bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
382  return alias(LocA, LocB) == MustAlias;
383  }
384 
385  /// A convenience wrapper around the \c isMustAlias helper interface.
386  bool isMustAlias(const Value *V1, const Value *V2) {
387  return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) ==
388  MustAlias;
389  }
390 
391  /// Checks whether the given location points to constant memory, or if
392  /// \p OrLocal is true whether it points to a local alloca.
393  bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
394 
395  /// A convenience wrapper around the primary \c pointsToConstantMemory
396  /// interface.
397  bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
398  return pointsToConstantMemory(MemoryLocation(P), OrLocal);
399  }
400 
401  /// @}
402  //===--------------------------------------------------------------------===//
403  /// \name Simple mod/ref information
404  /// @{
405 
406  /// Get the ModRef info associated with a pointer argument of a call. The
407  /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
408  /// that these bits do not necessarily account for the overall behavior of
409  /// the function, but rather only provide additional per-argument
410  /// information. This never sets ModRefInfo::Must.
411  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
412 
413  /// Return the behavior of the given call site.
414  FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
415 
416  /// Return the behavior when calling the given function.
417  FunctionModRefBehavior getModRefBehavior(const Function *F);
418 
419  /// Checks if the specified call is known to never read or write memory.
420  ///
421  /// Note that if the call only reads from known-constant memory, it is also
422  /// legal to return true. Also, calls that unwind the stack are legal for
423  /// this predicate.
424  ///
425  /// Many optimizations (such as CSE and LICM) can be performed on such calls
426  /// without worrying about aliasing properties, and many calls have this
427  /// property (e.g. calls to 'sin' and 'cos').
428  ///
429  /// This property corresponds to the GCC 'const' attribute.
430  bool doesNotAccessMemory(const CallBase *Call) {
431  return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory;
432  }
433 
434  /// Checks if the specified function is known to never read or write memory.
435  ///
436  /// Note that if the function only reads from known-constant memory, it is
437  /// also legal to return true. Also, function that unwind the stack are legal
438  /// for this predicate.
439  ///
440  /// Many optimizations (such as CSE and LICM) can be performed on such calls
441  /// to such functions without worrying about aliasing properties, and many
442  /// functions have this property (e.g. 'sin' and 'cos').
443  ///
444  /// This property corresponds to the GCC 'const' attribute.
445  bool doesNotAccessMemory(const Function *F) {
446  return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
447  }
448 
449  /// Checks if the specified call is known to only read from non-volatile
450  /// memory (or not access memory at all).
451  ///
452  /// Calls that unwind the stack are legal for this predicate.
453  ///
454  /// This property allows many common optimizations to be performed in the
455  /// absence of interfering store instructions, such as CSE of strlen calls.
456  ///
457  /// This property corresponds to the GCC 'pure' attribute.
458  bool onlyReadsMemory(const CallBase *Call) {
459  return onlyReadsMemory(getModRefBehavior(Call));
460  }
461 
462  /// Checks if the specified function is known to only read from non-volatile
463  /// memory (or not access memory at all).
464  ///
465  /// Functions that unwind the stack are legal for this predicate.
466  ///
467  /// This property allows many common optimizations to be performed in the
468  /// absence of interfering store instructions, such as CSE of strlen calls.
469  ///
470  /// This property corresponds to the GCC 'pure' attribute.
471  bool onlyReadsMemory(const Function *F) {
472  return onlyReadsMemory(getModRefBehavior(F));
473  }
474 
475  /// Checks if functions with the specified behavior are known to only read
476  /// from non-volatile memory (or not access memory at all).
478  return !isModSet(createModRefInfo(MRB));
479  }
480 
481  /// Checks if functions with the specified behavior are known to only write
482  /// memory (or not access memory at all).
484  return !isRefSet(createModRefInfo(MRB));
485  }
486 
487  /// Checks if functions with the specified behavior are known to read and
488  /// write at most from objects pointed to by their pointer-typed arguments
489  /// (with arbitrary offsets).
491  return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
492  }
493 
494  /// Checks if functions with the specified behavior are known to potentially
495  /// read or write from objects pointed to be their pointer-typed arguments
496  /// (with arbitrary offsets).
498  return isModOrRefSet(createModRefInfo(MRB)) &&
499  (MRB & FMRL_ArgumentPointees);
500  }
501 
502  /// Checks if functions with the specified behavior are known to read and
503  /// write at most from memory that is inaccessible from LLVM IR.
505  return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
506  }
507 
508  /// Checks if functions with the specified behavior are known to potentially
509  /// read or write from memory that is inaccessible from LLVM IR.
511  return isModOrRefSet(createModRefInfo(MRB)) && (MRB & FMRL_InaccessibleMem);
512  }
513 
514  /// Checks if functions with the specified behavior are known to read and
515  /// write at most from memory that is inaccessible from LLVM IR or objects
516  /// pointed to by their pointer-typed arguments (with arbitrary offsets).
518  return !(MRB & FMRL_Anywhere &
520  }
521 
522  /// getModRefInfo (for call sites) - Return information about whether
523  /// a particular call site modifies or reads the specified memory location.
524  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc);
525 
526  /// getModRefInfo (for call sites) - A convenience wrapper.
527  ModRefInfo getModRefInfo(const CallBase *Call, const Value *P,
528  LocationSize Size) {
529  return getModRefInfo(Call, MemoryLocation(P, Size));
530  }
531 
532  /// getModRefInfo (for loads) - Return information about whether
533  /// a particular load modifies or reads the specified memory location.
534  ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
535 
536  /// getModRefInfo (for loads) - A convenience wrapper.
538  LocationSize Size) {
539  return getModRefInfo(L, MemoryLocation(P, Size));
540  }
541 
542  /// getModRefInfo (for stores) - Return information about whether
543  /// a particular store modifies or reads the specified memory location.
544  ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
545 
546  /// getModRefInfo (for stores) - A convenience wrapper.
548  LocationSize Size) {
549  return getModRefInfo(S, MemoryLocation(P, Size));
550  }
551 
552  /// getModRefInfo (for fences) - Return information about whether
553  /// a particular store modifies or reads the specified memory location.
554  ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
555 
556  /// getModRefInfo (for fences) - A convenience wrapper.
558  LocationSize Size) {
559  return getModRefInfo(S, MemoryLocation(P, Size));
560  }
561 
562  /// getModRefInfo (for cmpxchges) - Return information about whether
563  /// a particular cmpxchg modifies or reads the specified memory location.
564  ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
565  const MemoryLocation &Loc);
566 
567  /// getModRefInfo (for cmpxchges) - A convenience wrapper.
569  LocationSize Size) {
570  return getModRefInfo(CX, MemoryLocation(P, Size));
571  }
572 
573  /// getModRefInfo (for atomicrmws) - Return information about whether
574  /// a particular atomicrmw modifies or reads the specified memory location.
575  ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
576 
577  /// getModRefInfo (for atomicrmws) - A convenience wrapper.
579  LocationSize Size) {
580  return getModRefInfo(RMW, MemoryLocation(P, Size));
581  }
582 
583  /// getModRefInfo (for va_args) - Return information about whether
584  /// a particular va_arg modifies or reads the specified memory location.
585  ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
586 
587  /// getModRefInfo (for va_args) - A convenience wrapper.
589  LocationSize Size) {
590  return getModRefInfo(I, MemoryLocation(P, Size));
591  }
592 
593  /// getModRefInfo (for catchpads) - Return information about whether
594  /// a particular catchpad modifies or reads the specified memory location.
595  ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
596 
597  /// getModRefInfo (for catchpads) - A convenience wrapper.
599  LocationSize Size) {
600  return getModRefInfo(I, MemoryLocation(P, Size));
601  }
602 
603  /// getModRefInfo (for catchrets) - Return information about whether
604  /// a particular catchret modifies or reads the specified memory location.
605  ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
606 
607  /// getModRefInfo (for catchrets) - A convenience wrapper.
609  LocationSize Size) {
610  return getModRefInfo(I, MemoryLocation(P, Size));
611  }
612 
613  /// Check whether or not an instruction may read or write the optionally
614  /// specified memory location.
615  ///
616  ///
617  /// An instruction that doesn't read or write memory may be trivially LICM'd
618  /// for example.
619  ///
620  /// For function calls, this delegates to the alias-analysis specific
621  /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
622  /// helpers above.
624  const Optional<MemoryLocation> &OptLoc) {
625  AAQueryInfo AAQIP;
626  return getModRefInfo(I, OptLoc, AAQIP);
627  }
628 
629  /// A convenience wrapper for constructing the memory location.
631  LocationSize Size) {
632  return getModRefInfo(I, MemoryLocation(P, Size));
633  }
634 
635  /// Return information about whether a call and an instruction may refer to
636  /// the same memory locations.
637  ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);
638 
639  /// Return information about whether two call sites may refer to the same set
640  /// of memory locations. See the AA documentation for details:
641  /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
642  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);
643 
644  /// Return information about whether a particular call site modifies
645  /// or reads the specified memory location \p MemLoc before instruction \p I
646  /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
647  /// instruction ordering queries inside the BasicBlock containing \p I.
648  /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
649  /// set.
650  ModRefInfo callCapturesBefore(const Instruction *I,
651  const MemoryLocation &MemLoc, DominatorTree *DT,
652  OrderedBasicBlock *OBB = nullptr);
653 
654  /// A convenience wrapper to synthesize a memory location.
657  OrderedBasicBlock *OBB = nullptr) {
658  return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
659  }
660 
661  /// @}
662  //===--------------------------------------------------------------------===//
663  /// \name Higher level methods for querying mod/ref information.
664  /// @{
665 
666  /// Check if it is possible for execution of the specified basic block to
667  /// modify the location Loc.
668  bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
669 
670  /// A convenience wrapper synthesizing a memory location.
671  bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
672  LocationSize Size) {
673  return canBasicBlockModify(BB, MemoryLocation(P, Size));
674  }
675 
676  /// Check if it is possible for the execution of the specified instructions
677  /// to mod\ref (according to the mode) the location Loc.
678  ///
679  /// The instructions to consider are all of the instructions in the range of
680  /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
681  bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
682  const MemoryLocation &Loc,
683  const ModRefInfo Mode);
684 
685  /// A convenience wrapper synthesizing a memory location.
687  const Value *Ptr, LocationSize Size,
688  const ModRefInfo Mode) {
689  return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
690  }
691 
692 private:
693  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
694  AAQueryInfo &AAQI);
695  bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
696  bool OrLocal = false);
697  ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2,
698  AAQueryInfo &AAQIP);
699  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
700  AAQueryInfo &AAQI);
701  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
702  AAQueryInfo &AAQI);
703  ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
704  AAQueryInfo &AAQI);
705  ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
706  AAQueryInfo &AAQI);
707  ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
708  AAQueryInfo &AAQI);
709  ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
710  AAQueryInfo &AAQI);
711  ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
712  const MemoryLocation &Loc, AAQueryInfo &AAQI);
713  ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
714  AAQueryInfo &AAQI);
715  ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
716  AAQueryInfo &AAQI);
717  ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
718  AAQueryInfo &AAQI);
719  ModRefInfo getModRefInfo(const Instruction *I,
720  const Optional<MemoryLocation> &OptLoc,
721  AAQueryInfo &AAQIP) {
722  if (OptLoc == None) {
723  if (const auto *Call = dyn_cast<CallBase>(I)) {
724  return createModRefInfo(getModRefBehavior(Call));
725  }
726  }
727 
728  const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
729 
730  switch (I->getOpcode()) {
731  case Instruction::VAArg:
732  return getModRefInfo((const VAArgInst *)I, Loc, AAQIP);
733  case Instruction::Load:
734  return getModRefInfo((const LoadInst *)I, Loc, AAQIP);
735  case Instruction::Store:
736  return getModRefInfo((const StoreInst *)I, Loc, AAQIP);
737  case Instruction::Fence:
738  return getModRefInfo((const FenceInst *)I, Loc, AAQIP);
739  case Instruction::AtomicCmpXchg:
740  return getModRefInfo((const AtomicCmpXchgInst *)I, Loc, AAQIP);
741  case Instruction::AtomicRMW:
742  return getModRefInfo((const AtomicRMWInst *)I, Loc, AAQIP);
743  case Instruction::Call:
744  return getModRefInfo((const CallInst *)I, Loc, AAQIP);
745  case Instruction::Invoke:
746  return getModRefInfo((const InvokeInst *)I, Loc, AAQIP);
747  case Instruction::CatchPad:
748  return getModRefInfo((const CatchPadInst *)I, Loc, AAQIP);
749  case Instruction::CatchRet:
750  return getModRefInfo((const CatchReturnInst *)I, Loc, AAQIP);
751  default:
752  return ModRefInfo::NoModRef;
753  }
754  }
755 
756  class Concept;
757 
758  template <typename T> class Model;
759 
760  template <typename T> friend class AAResultBase;
761 
762  const TargetLibraryInfo &TLI;
763 
764  std::vector<std::unique_ptr<Concept>> AAs;
765 
766  std::vector<AnalysisKey *> AADeps;
767 
768  friend class BatchAAResults;
769 };
770 
771 /// This class is a wrapper over an AAResults, and it is intended to be used
772 /// only when there are no IR changes inbetween queries. BatchAAResults is
773 /// reusing the same `AAQueryInfo` to preserve the state across queries,
774 /// esentially making AA work in "batch mode". The internal state cannot be
775 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
776 /// or create a new BatchAAResults.
778  AAResults &AA;
779  AAQueryInfo AAQI;
780 
781 public:
782  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
783  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
784  return AA.alias(LocA, LocB, AAQI);
785  }
786  bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
787  return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
788  }
789  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
790  return AA.getModRefInfo(Call, Loc, AAQI);
791  }
792  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) {
793  return AA.getModRefInfo(Call1, Call2, AAQI);
794  }
796  const Optional<MemoryLocation> &OptLoc) {
797  return AA.getModRefInfo(I, OptLoc, AAQI);
798  }
800  return AA.getModRefInfo(I, Call2, AAQI);
801  }
802  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
803  return AA.getArgModRefInfo(Call, ArgIdx);
804  }
806  return AA.getModRefBehavior(Call);
807  }
808 };
809 
810 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
811 /// pointer or reference.
813 
814 /// A private abstract base class describing the concept of an individual alias
815 /// analysis implementation.
816 ///
817 /// This interface is implemented by any \c Model instantiation. It is also the
818 /// interface which a type used to instantiate the model must provide.
819 ///
820 /// All of these methods model methods by the same name in the \c
821 /// AAResults class. Only differences and specifics to how the
822 /// implementations are called are documented here.
824 public:
825  virtual ~Concept() = 0;
826 
827  /// An update API used internally by the AAResults to provide
828  /// a handle back to the top level aggregation.
829  virtual void setAAResults(AAResults *NewAAR) = 0;
830 
831  //===--------------------------------------------------------------------===//
832  /// \name Alias Queries
833  /// @{
834 
835  /// The main low level interface to the alias analysis implementation.
836  /// Returns an AliasResult indicating whether the two pointers are aliased to
837  /// each other. This is the interface that must be implemented by specific
838  /// alias analysis implementations.
839  virtual AliasResult alias(const MemoryLocation &LocA,
840  const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0;
841 
842  /// Checks whether the given location points to constant memory, or if
843  /// \p OrLocal is true whether it points to a local alloca.
844  virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
845  AAQueryInfo &AAQI, bool OrLocal) = 0;
846 
847  /// @}
848  //===--------------------------------------------------------------------===//
849  /// \name Simple mod/ref information
850  /// @{
851 
852  /// Get the ModRef info associated with a pointer argument of a callsite. The
853  /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
854  /// that these bits do not necessarily account for the overall behavior of
855  /// the function, but rather only provide additional per-argument
856  /// information.
857  virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
858  unsigned ArgIdx) = 0;
859 
860  /// Return the behavior of the given call site.
861  virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0;
862 
863  /// Return the behavior when calling the given function.
864  virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
865 
866  /// getModRefInfo (for call sites) - Return information about whether
867  /// a particular call site modifies or reads the specified memory location.
868  virtual ModRefInfo getModRefInfo(const CallBase *Call,
869  const MemoryLocation &Loc,
870  AAQueryInfo &AAQI) = 0;
871 
872  /// Return information about whether two call sites may refer to the same set
873  /// of memory locations. See the AA documentation for details:
874  /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
875  virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
876  AAQueryInfo &AAQI) = 0;
877 
878  /// @}
879 };
880 
881 /// A private class template which derives from \c Concept and wraps some other
882 /// type.
883 ///
884 /// This models the concept by directly forwarding each interface point to the
885 /// wrapped type which must implement a compatible interface. This provides
886 /// a type erased binding.
887 template <typename AAResultT> class AAResults::Model final : public Concept {
888  AAResultT &Result;
889 
890 public:
891  explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
892  Result.setAAResults(&AAR);
893  }
894  ~Model() override = default;
895 
896  void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
897 
898  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
899  AAQueryInfo &AAQI) override {
900  return Result.alias(LocA, LocB, AAQI);
901  }
902 
903  bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
904  bool OrLocal) override {
905  return Result.pointsToConstantMemory(Loc, AAQI, OrLocal);
906  }
907 
908  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
909  return Result.getArgModRefInfo(Call, ArgIdx);
910  }
911 
912  FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override {
913  return Result.getModRefBehavior(Call);
914  }
915 
916  FunctionModRefBehavior getModRefBehavior(const Function *F) override {
917  return Result.getModRefBehavior(F);
918  }
919 
920  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
921  AAQueryInfo &AAQI) override {
922  return Result.getModRefInfo(Call, Loc, AAQI);
923  }
924 
925  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
926  AAQueryInfo &AAQI) override {
927  return Result.getModRefInfo(Call1, Call2, AAQI);
928  }
929 };
930 
931 /// A CRTP-driven "mixin" base class to help implement the function alias
932 /// analysis results concept.
933 ///
934 /// Because of the nature of many alias analysis implementations, they often
935 /// only implement a subset of the interface. This base class will attempt to
936 /// implement the remaining portions of the interface in terms of simpler forms
937 /// of the interface where possible, and otherwise provide conservatively
938 /// correct fallback implementations.
939 ///
940 /// Implementors of an alias analysis should derive from this CRTP, and then
941 /// override specific methods that they wish to customize. There is no need to
942 /// use virtual anywhere, the CRTP base class does static dispatch to the
943 /// derived type passed into it.
944 template <typename DerivedT> class AAResultBase {
945  // Expose some parts of the interface only to the AAResults::Model
946  // for wrapping. Specifically, this allows the model to call our
947  // setAAResults method without exposing it as a fully public API.
948  friend class AAResults::Model<DerivedT>;
949 
950  /// A pointer to the AAResults object that this AAResult is
951  /// aggregated within. May be null if not aggregated.
952  AAResults *AAR = nullptr;
953 
954  /// Helper to dispatch calls back through the derived type.
955  DerivedT &derived() { return static_cast<DerivedT &>(*this); }
956 
957  /// A setter for the AAResults pointer, which is used to satisfy the
958  /// AAResults::Model contract.
959  void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
960 
961 protected:
962  /// This proxy class models a common pattern where we delegate to either the
963  /// top-level \c AAResults aggregation if one is registered, or to the
964  /// current result if none are registered.
966  AAResults *AAR;
967  DerivedT &CurrentResult;
968 
969  public:
970  AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
971  : AAR(AAR), CurrentResult(CurrentResult) {}
972 
973  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
974  AAQueryInfo &AAQI) {
975  return AAR ? AAR->alias(LocA, LocB, AAQI)
976  : CurrentResult.alias(LocA, LocB, AAQI);
977  }
978 
980  bool OrLocal) {
981  return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal)
982  : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal);
983  }
984 
985  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
986  return AAR ? AAR->getArgModRefInfo(Call, ArgIdx)
987  : CurrentResult.getArgModRefInfo(Call, ArgIdx);
988  }
989 
991  return AAR ? AAR->getModRefBehavior(Call)
992  : CurrentResult.getModRefBehavior(Call);
993  }
994 
996  return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
997  }
998 
1000  AAQueryInfo &AAQI) {
1001  return AAR ? AAR->getModRefInfo(Call, Loc, AAQI)
1002  : CurrentResult.getModRefInfo(Call, Loc, AAQI);
1003  }
1004 
1005  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1006  AAQueryInfo &AAQI) {
1007  return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI)
1008  : CurrentResult.getModRefInfo(Call1, Call2, AAQI);
1009  }
1010  };
1011 
1012  explicit AAResultBase() = default;
1013 
1014  // Provide all the copy and move constructors so that derived types aren't
1015  // constrained.
1018 
1019  /// Get a proxy for the best AA result set to query at this time.
1020  ///
1021  /// When this result is part of a larger aggregation, this will proxy to that
1022  /// aggregation. When this result is used in isolation, it will just delegate
1023  /// back to the derived class's implementation.
1024  ///
1025  /// Note that callers of this need to take considerable care to not cause
1026  /// performance problems when they use this routine, in the case of a large
1027  /// number of alias analyses being aggregated, it can be expensive to walk
1028  /// back across the chain.
1029  AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
1030 
1031 public:
1033  AAQueryInfo &AAQI) {
1034  return MayAlias;
1035  }
1036 
1038  bool OrLocal) {
1039  return false;
1040  }
1041 
1042  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
1043  return ModRefInfo::ModRef;
1044  }
1045 
1048  }
1049 
1052  }
1053 
1055  AAQueryInfo &AAQI) {
1056  return ModRefInfo::ModRef;
1057  }
1058 
1059  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1060  AAQueryInfo &AAQI) {
1061  return ModRefInfo::ModRef;
1062  }
1063 };
1064 
1065 /// Return true if this pointer is returned by a noalias function.
1066 bool isNoAliasCall(const Value *V);
1067 
1068 /// Return true if this is an argument with the noalias attribute.
1069 bool isNoAliasArgument(const Value *V);
1070 
1071 /// Return true if this pointer refers to a distinct and identifiable object.
1072 /// This returns true for:
1073 /// Global Variables and Functions (but not Global Aliases)
1074 /// Allocas
1075 /// ByVal and NoAlias Arguments
1076 /// NoAlias returns (e.g. calls to malloc)
1077 ///
1078 bool isIdentifiedObject(const Value *V);
1079 
1080 /// Return true if V is umabigously identified at the function-level.
1081 /// Different IdentifiedFunctionLocals can't alias.
1082 /// Further, an IdentifiedFunctionLocal can not alias with any function
1083 /// arguments other than itself, which is not necessarily true for
1084 /// IdentifiedObjects.
1085 bool isIdentifiedFunctionLocal(const Value *V);
1086 
1087 /// A manager for alias analyses.
1088 ///
1089 /// This class can have analyses registered with it and when run, it will run
1090 /// all of them and aggregate their results into single AA results interface
1091 /// that dispatches across all of the alias analysis results available.
1092 ///
1093 /// Note that the order in which analyses are registered is very significant.
1094 /// That is the order in which the results will be aggregated and queried.
1095 ///
1096 /// This manager effectively wraps the AnalysisManager for registering alias
1097 /// analyses. When you register your alias analysis with this manager, it will
1098 /// ensure the analysis itself is registered with its AnalysisManager.
1099 ///
1100 /// The result of this analysis is only invalidated if one of the particular
1101 /// aggregated AA results end up being invalidated. This removes the need to
1102 /// explicitly preserve the results of `AAManager`. Note that analyses should no
1103 /// longer be registered once the `AAManager` is run.
1104 class AAManager : public AnalysisInfoMixin<AAManager> {
1105 public:
1107 
1108  /// Register a specific AA result.
1109  template <typename AnalysisT> void registerFunctionAnalysis() {
1110  ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
1111  }
1112 
1113  /// Register a specific AA result.
1114  template <typename AnalysisT> void registerModuleAnalysis() {
1115  ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
1116  }
1117 
1120  for (auto &Getter : ResultGetters)
1121  (*Getter)(F, AM, R);
1122  return R;
1123  }
1124 
1125 private:
1127 
1128  static AnalysisKey Key;
1129 
1131  AAResults &AAResults),
1132  4> ResultGetters;
1133 
1134  template <typename AnalysisT>
1135  static void getFunctionAAResultImpl(Function &F,
1137  AAResults &AAResults) {
1138  AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1139  AAResults.addAADependencyID(AnalysisT::ID());
1140  }
1141 
1142  template <typename AnalysisT>
1143  static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
1144  AAResults &AAResults) {
1145  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1146  auto &MAM = MAMProxy.getManager();
1147  if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) {
1148  AAResults.addAAResult(*R);
1149  MAMProxy
1150  .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
1151  }
1152  }
1153 };
1154 
1155 /// A wrapper pass to provide the legacy pass manager access to a suitably
1156 /// prepared AAResults object.
1158  std::unique_ptr<AAResults> AAR;
1159 
1160 public:
1161  static char ID;
1162 
1164 
1165  AAResults &getAAResults() { return *AAR; }
1166  const AAResults &getAAResults() const { return *AAR; }
1167 
1168  bool runOnFunction(Function &F) override;
1169 
1170  void getAnalysisUsage(AnalysisUsage &AU) const override;
1171 };
1172 
1173 /// A wrapper pass for external alias analyses. This just squirrels away the
1174 /// callback used to run any analyses and register their results.
1176  using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
1177 
1179 
1180  static char ID;
1181 
1184  }
1185 
1187  : ImmutablePass(ID), CB(std::move(CB)) {
1189  }
1190 
1191  void getAnalysisUsage(AnalysisUsage &AU) const override {
1192  AU.setPreservesAll();
1193  }
1194 };
1195 
1197 
1198 /// A wrapper pass around a callback which can be used to populate the
1199 /// AAResults in the AAResultsWrapperPass from an external AA.
1200 ///
1201 /// The callback provided here will be used each time we prepare an AAResults
1202 /// object, and will receive a reference to the function wrapper pass, the
1203 /// function, and the AAResults object to populate. This should be used when
1204 /// setting up a custom pass pipeline to inject a hook into the AA results.
1206  std::function<void(Pass &, Function &, AAResults &)> Callback);
1207 
1208 /// A helper for the legacy pass manager to create a \c AAResults
1209 /// object populated to the best of our ability for a particular function when
1210 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
1211 ///
1212 /// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1213 /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1214 /// getAnalysisUsage.
1216 
1217 /// A helper for the legacy pass manager to populate \p AU to add uses to make
1218 /// sure the analyses required by \p createLegacyPMAAResults are available.
1220 
1221 } // end namespace llvm
1222 
1223 #endif // LLVM_ANALYSIS_ALIASANALYSIS_H
The access may reference and may modify the value stored in memory.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
LLVM_NODISCARD ModRefInfo unionModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, LocationSize Size)
getModRefInfo (for catchrets) - A convenience wrapper.
BatchAAResults(AAResults &AAR)
ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, LocationSize Size)
getModRefInfo (for atomicrmws) - A convenience wrapper.
static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from memory that ...
void addAAResult(AAResultT &AAResult)
Register a specific AA result.
The access neither references nor modifies the value stored in memory.
LLVM_NODISCARD ModRefInfo clearMust(const ModRefInfo MRI)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI)
SI Whole Quad Mode
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, LocationSize Size)
getModRefInfo (for catchpads) - A convenience wrapper.
Various leaf nodes.
Definition: ISDOpcodes.h:59
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
An instruction for ordering other memory operations.
Definition: Instructions.h:462
An instruction that atomically checks whether a specified value is in a memory location, and, if it is, stores a new value there.
Definition: Instructions.h:538
ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, LocationSize Size, DominatorTree *DT, OrderedBasicBlock *OBB=nullptr)
A convenience wrapper to synthesize a memory location.
ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, LocationSize Size)
getModRefInfo (for fences) - A convenience wrapper.
static constexpr LocationSize unknown()
ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, LocationSize Size)
getModRefInfo (for stores) - A convenience wrapper.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias. ...
std::function< void(Pass &, Function &, AAResults &)> CallbackT
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const Value *Ptr, LocationSize Size, const ModRefInfo Mode)
A convenience wrapper synthesizing a memory location.
This class stores info we want to provide to or retain within an alias query.
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:266
This class represents a function call, abstracting a target machine&#39;s calling convention.
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI)
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
bool doesNotAccessMemory(const Function *F)
Checks if the specified function is known to never read or write memory.
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
void registerModuleAnalysis()
Register a specific AA result.
const AAResults & getAAResults() const
This is the AA result object for the basic, local, and stateless alias analysis.
static LocationSize precise(uint64_t Value)
static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from memory that ...
bool pointsToConstantMemory(const Value *P, bool OrLocal=false)
A convenience wrapper around the primary pointsToConstantMemory interface.
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
An instruction for reading from memory.
Definition: Instructions.h:169
bool canBasicBlockModify(const BasicBlock &BB, const Value *P, LocationSize Size)
A convenience wrapper synthesizing a memory location.
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:701
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
void initializeExternalAAWrapperPassPass(PassRegistry &)
LLVM_NODISCARD bool isModAndRefSet(const ModRefInfo MRI)
Access to any memory.
ModRefInfo getModRefInfo(const Instruction *I, const Optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location...
This indicates that the function could not be classified into one of the behaviors above...
LLVM_NODISCARD ModRefInfo clearMod(const ModRefInfo MRI)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
ModRefInfo getModRefInfo(const CallBase *Call, const Value *P, LocationSize Size)
getModRefInfo (for call sites) - A convenience wrapper.
The only memory references in this function (if it has any) are references of memory that is otherwis...
Definition: BitVector.h:937
FunctionPass * createAAResultsWrapperPass()
ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, LocationSize Size)
getModRefInfo (for cmpxchges) - A convenience wrapper.
static bool doesNotReadMemory(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to only write memory (or not access memory ...
bool isNoAlias(const Value *V1, const Value *V2)
A convenience wrapper around the isNoAlias helper interface.
LLVM_NODISCARD ModRefInfo clearRef(const ModRefInfo MRI)
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Must is provided for completeness, but no routines will return only Must today.
The access may reference the value stored in memory, a mustAlias relation was found, and no mayAlias or partialAlias found.
The access may reference the value stored in memory.
The only memory references in this function (if it has any) are non-volatile loads from objects point...
AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR)
A helper for the legacy pass manager to create a AAResults object populated to the best of our abilit...
The function may perform non-volatile loads and stores of objects pointed to by its pointer-typed arg...
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
AliasResult alias(const Value *V1, const Value *V2)
A convenience wrapper around the primary alias interface.
LLVM_NODISCARD ModRefInfo setRef(const ModRefInfo MRI)
Key
PAL metadata keys.
LLVM_NODISCARD bool isMustSet(const ModRefInfo MRI)
ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, LocationSize Size)
getModRefInfo (for loads) - A convenience wrapper.
Access to memory via argument pointers.
The access may reference, modify or both the value stored in memory, a mustAlias relation was found...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
The access may modify the value stored in memory, a mustAlias relation was found, and no mayAlias or ...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
AAResultBase(AAResultBase &&Arg)
An instruction for storing to memory.
Definition: Instructions.h:325
void registerFunctionAnalysis()
Register a specific AA result.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
A private abstract base class describing the concept of an individual alias analysis implementation...
static bool onlyReadsMemory(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to only read from non-volatile memory (or n...
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)
A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
bool onlyReadsMemory(const Function *F)
Checks if the specified function is known to only read from non-volatile memory (or not access memory...
AAResultBase(const AAResultBase &Arg)
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, LocationSize V2Size)
A convenience wrapper around the primary alias interface.
A manager for alias analyses.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:389
ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, LocationSize Size)
getModRefInfo (for va_args) - A convenience wrapper.
Result run(Function &F, FunctionAnalysisManager &AM)
Represent the analysis usage information of a pass.
void addAADependencyID(AnalysisKey *ID)
Register a function analysis ID that the results aggregation depends on.
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
static bool doesAccessArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to potentially read or write from objects p...
IsCapturedCacheT IsCapturedCache
The only memory references in this function (if it has any) are non-volatile loads and stores from ob...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
std::pair< MemoryLocation, MemoryLocation > LocPair
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
This function does not perform any non-local loads or stores to memory.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
FunctionModRefLocation
The locations at which a function might access memory.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:255
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2)
Memory that is inaccessible via LLVM IR.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1160
LLVM_NODISCARD ModRefInfo setMod(const ModRefInfo MRI)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
The access may modify the value stored in memory.
bool isMustAlias(const Value *V1, const Value *V2)
A convenience wrapper around the isMustAlias helper interface.
This proxy class models a common pattern where we delegate to either the top-level AAResults aggregat...
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
ModRefInfo getModRefInfo(const Instruction *I, const Optional< MemoryLocation > &OptLoc)
AAResults(const TargetLibraryInfo &TLI)
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
Base case is no access to memory.
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
This file provides utility analysis objects describing memory locations.
static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to potentially read or write from memory th...
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
#define I(x, y, z)
Definition: MD5.cpp:58
AAResultsProxy getBestAAResults()
Get a proxy for the best AA result set to query at this time.
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:153
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:648
Analysis pass providing the TargetLibraryInfo.
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:73
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Invoke instruction.
A wrapper pass for external alias analyses.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
LLVM_NODISCARD ModRefInfo setModAndRef(const ModRefInfo MRI)
print Print MemDeps of function
FunctionModRefBehavior getModRefBehavior(const Function *F)
bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, LocationSize V2Size)
A convenience wrapper around the isNoAlias helper interface.
A container for analyses that lazily runs them and caches their results.
bool isNoAliasArgument(const Value *V)
Return true if this is an argument with the noalias attribute.
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
This header defines various interfaces for pass management in LLVM.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:88
ExternalAAWrapperPass(CallbackT CB)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
FunctionModRefBehavior getModRefBehavior(const Function *F)
AliasCacheT AliasCache
ModRefInfo getModRefInfo(const Instruction *I, const Value *P, LocationSize Size)
A convenience wrapper for constructing the memory location.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)