contrib/llvm/include/llvm/Analysis/AliasAnalysis.h

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