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

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