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