contrib/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

   1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- 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 MemoryDependenceAnalysis analysis pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
  15 #define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
  16
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/PointerSumType.h"
  19 #include "llvm/ADT/PointerEmbeddedInt.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/IR/BasicBlock.h"
  23 #include "llvm/IR/PassManager.h"
  24 #include "llvm/IR/PredIteratorCache.h"
  25 #include "llvm/IR/ValueHandle.h"
  26 #include "llvm/Pass.h"
  27
  28 namespace llvm {
  29 class Function;
  30 class FunctionPass;
  31 class Instruction;
  32 class CallSite;
  33 class AssumptionCache;
  34 class MemoryDependenceResults;
  35 class PredIteratorCache;
  36 class DominatorTree;
  37 class PHITransAddr;
  38
  39 /// A memory dependence query can return one of three different answers.
  40 class MemDepResult {
  41   enum DepType {
  42     /// Clients of MemDep never see this.
  43     ///
  44     /// Entries with this marker occur in a LocalDeps map or NonLocalDeps map
  45     /// when the instruction they previously referenced was removed from
  46     /// MemDep.  In either case, the entry may include an instruction pointer.
  47     /// If so, the pointer is an instruction in the block where scanning can
  48     /// start from, saving some work.
  49     ///
  50     /// In a default-constructed MemDepResult object, the type will be Invalid
  51     /// and the instruction pointer will be null.
  52     Invalid = 0,
  53
  54     /// This is a dependence on the specified instruction which clobbers the
  55     /// desired value.  The pointer member of the MemDepResult pair holds the
  56     /// instruction that clobbers the memory.  For example, this occurs when we
  57     /// see a may-aliased store to the memory location we care about.
  58     ///
  59     /// There are several cases that may be interesting here:
  60     ///   1. Loads are clobbered by may-alias stores.
  61     ///   2. Loads are considered clobbered by partially-aliased loads.  The
  62     ///      client may choose to analyze deeper into these cases.
  63     Clobber,
  64
  65     /// This is a dependence on the specified instruction which defines or
  66     /// produces the desired memory location.  The pointer member of the
  67     /// MemDepResult pair holds the instruction that defines the memory.
  68     ///
  69     /// Cases of interest:
  70     ///   1. This could be a load or store for dependence queries on
  71     ///      load/store.  The value loaded or stored is the produced value.
  72     ///      Note that the pointer operand may be different than that of the
  73     ///      queried pointer due to must aliases and phi translation.  Note
  74     ///      that the def may not be the same type as the query, the pointers
  75     ///      may just be must aliases.
  76     ///   2. For loads and stores, this could be an allocation instruction. In
  77     ///      this case, the load is loading an undef value or a store is the
  78     ///      first store to (that part of) the allocation.
  79     ///   3. Dependence queries on calls return Def only when they are readonly
  80     ///      calls or memory use intrinsics with identical callees and no
  81     ///      intervening clobbers.  No validation is done that the operands to
  82     ///      the calls are the same.
  83     Def,
  84
  85     /// This marker indicates that the query has no known dependency in the
  86     /// specified block.
  87     ///
  88     /// More detailed state info is encoded in the upper part of the pair (i.e.
  89     /// the Instruction*)
  90     Other
  91   };
  92
  93   /// If DepType is "Other", the upper part of the sum type is an encoding of
  94   /// the following more detailed type information.
  95   enum OtherType {
  96     /// This marker indicates that the query has no dependency in the specified
  97     /// block.
  98     ///
  99     /// To find out more, the client should query other predecessor blocks.
 100     NonLocal = 1,
 101     /// This marker indicates that the query has no dependency in the specified
 102     /// function.
 103     NonFuncLocal,
 104     /// This marker indicates that the query dependency is unknown.
 105     Unknown
 106   };
 107
 108   typedef PointerSumType<
 109       DepType, PointerSumTypeMember<Invalid, Instruction *>,
 110       PointerSumTypeMember<Clobber, Instruction *>,
 111       PointerSumTypeMember<Def, Instruction *>,
 112       PointerSumTypeMember<Other, PointerEmbeddedInt<OtherType, 3>>>
 113       ValueTy;
 114   ValueTy Value;
 115   explicit MemDepResult(ValueTy V) : Value(V) {}
 116
 117 public:
 118   MemDepResult() : Value() {}
 119
 120   /// get methods: These are static ctor methods for creating various
 121   /// MemDepResult kinds.
 122   static MemDepResult getDef(Instruction *Inst) {
 123     assert(Inst && "Def requires inst");
 124     return MemDepResult(ValueTy::create<Def>(Inst));
 125   }
 126   static MemDepResult getClobber(Instruction *Inst) {
 127     assert(Inst && "Clobber requires inst");
 128     return MemDepResult(ValueTy::create<Clobber>(Inst));
 129   }
 130   static MemDepResult getNonLocal() {
 131     return MemDepResult(ValueTy::create<Other>(NonLocal));
 132   }
 133   static MemDepResult getNonFuncLocal() {
 134     return MemDepResult(ValueTy::create<Other>(NonFuncLocal));
 135   }
 136   static MemDepResult getUnknown() {
 137     return MemDepResult(ValueTy::create<Other>(Unknown));
 138   }
 139
 140   /// Tests if this MemDepResult represents a query that is an instruction
 141   /// clobber dependency.
 142   bool isClobber() const { return Value.is<Clobber>(); }
 143
 144   /// Tests if this MemDepResult represents a query that is an instruction
 145   /// definition dependency.
 146   bool isDef() const { return Value.is<Def>(); }
 147
 148   /// Tests if this MemDepResult represents a query that is transparent to the
 149   /// start of the block, but where a non-local hasn't been done.
 150   bool isNonLocal() const {
 151     return Value.is<Other>() && Value.cast<Other>() == NonLocal;
 152   }
 153
 154   /// Tests if this MemDepResult represents a query that is transparent to the
 155   /// start of the function.
 156   bool isNonFuncLocal() const {
 157     return Value.is<Other>() && Value.cast<Other>() == NonFuncLocal;
 158   }
 159
 160   /// Tests if this MemDepResult represents a query which cannot and/or will
 161   /// not be computed.
 162   bool isUnknown() const {
 163     return Value.is<Other>() && Value.cast<Other>() == Unknown;
 164   }
 165
 166   /// If this is a normal dependency, returns the instruction that is depended
 167   /// on.  Otherwise, returns null.
 168   Instruction *getInst() const {
 169     switch (Value.getTag()) {
 170     case Invalid:
 171       return Value.cast<Invalid>();
 172     case Clobber:
 173       return Value.cast<Clobber>();
 174     case Def:
 175       return Value.cast<Def>();
 176     case Other:
 177       return nullptr;
 178     }
 179     llvm_unreachable("Unknown discriminant!");
 180   }
 181
 182   bool operator==(const MemDepResult &M) const { return Value == M.Value; }
 183   bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
 184   bool operator<(const MemDepResult &M) const { return Value < M.Value; }
 185   bool operator>(const MemDepResult &M) const { return Value > M.Value; }
 186
 187 private:
 188   friend class MemoryDependenceResults;
 189
 190   /// Tests if this is a MemDepResult in its dirty/invalid. state.
 191   bool isDirty() const { return Value.is<Invalid>(); }
 192
 193   static MemDepResult getDirty(Instruction *Inst) {
 194     return MemDepResult(ValueTy::create<Invalid>(Inst));
 195   }
 196 };
 197
 198 /// This is an entry in the NonLocalDepInfo cache.
 199 ///
 200 /// For each BasicBlock (the BB entry) it keeps a MemDepResult.
 201 class NonLocalDepEntry {
 202   BasicBlock *BB;
 203   MemDepResult Result;
 204
 205 public:
 206   NonLocalDepEntry(BasicBlock *bb, MemDepResult result)
 207       : BB(bb), Result(result) {}
 208
 209   // This is used for searches.
 210   NonLocalDepEntry(BasicBlock *bb) : BB(bb) {}
 211
 212   // BB is the sort key, it can't be changed.
 213   BasicBlock *getBB() const { return BB; }
 214
 215   void setResult(const MemDepResult &R) { Result = R; }
 216
 217   const MemDepResult &getResult() const { return Result; }
 218
 219   bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; }
 220 };
 221
 222 /// This is a result from a NonLocal dependence query.
 223 ///
 224 /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
 225 /// (potentially phi translated) address that was live in the block.
 226 class NonLocalDepResult {
 227   NonLocalDepEntry Entry;
 228   Value *Address;
 229
 230 public:
 231   NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
 232       : Entry(bb, result), Address(address) {}
 233
 234   // BB is the sort key, it can't be changed.
 235   BasicBlock *getBB() const { return Entry.getBB(); }
 236
 237   void setResult(const MemDepResult &R, Value *Addr) {
 238     Entry.setResult(R);
 239     Address = Addr;
 240   }
 241
 242   const MemDepResult &getResult() const { return Entry.getResult(); }
 243
 244   /// Returns the address of this pointer in this block.
 245   ///
 246   /// This can be different than the address queried for the non-local result
 247   /// because of phi translation.  This returns null if the address was not
 248   /// available in a block (i.e. because phi translation failed) or if this is
 249   /// a cached result and that address was deleted.
 250   ///
 251   /// The address is always null for a non-local 'call' dependence.
 252   Value *getAddress() const { return Address; }
 253 };
 254
 255 /// Provides a lazy, caching interface for making common memory aliasing
 256 /// information queries, backed by LLVM's alias analysis passes.
 257 ///
 258 /// The dependency information returned is somewhat unusual, but is pragmatic.
 259 /// If queried about a store or call that might modify memory, the analysis
 260 /// will return the instruction[s] that may either load from that memory or
 261 /// store to it.  If queried with a load or call that can never modify memory,
 262 /// the analysis will return calls and stores that might modify the pointer,
 263 /// but generally does not return loads unless a) they are volatile, or
 264 /// b) they load from *must-aliased* pointers.  Returning a dependence on
 265 /// must-alias'd pointers instead of all pointers interacts well with the
 266 /// internal caching mechanism.
 267 class MemoryDependenceResults {
 268   // A map from instructions to their dependency.
 269   typedef DenseMap<Instruction *, MemDepResult> LocalDepMapType;
 270   LocalDepMapType LocalDeps;
 271
 272 public:
 273   typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
 274
 275 private:
 276   /// A pair<Value*, bool> where the bool is true if the dependence is a read
 277   /// only dependence, false if read/write.
 278   typedef PointerIntPair<const Value *, 1, bool> ValueIsLoadPair;
 279
 280   /// This pair is used when caching information for a block.
 281   ///
 282   /// If the pointer is null, the cache value is not a full query that starts
 283   /// at the specified block.  If non-null, the bool indicates whether or not
 284   /// the contents of the block was skipped.
 285   typedef PointerIntPair<BasicBlock *, 1, bool> BBSkipFirstBlockPair;
 286
 287   /// This record is the information kept for each (value, is load) pair.
 288   struct NonLocalPointerInfo {
 289     /// The pair of the block and the skip-first-block flag.
 290     BBSkipFirstBlockPair Pair;
 291     /// The results of the query for each relevant block.
 292     NonLocalDepInfo NonLocalDeps;
 293     /// The maximum size of the dereferences of the pointer.
 294     ///
 295     /// May be UnknownSize if the sizes are unknown.
 296     uint64_t Size;
 297     /// The AA tags associated with dereferences of the pointer.
 298     ///
 299     /// The members may be null if there are no tags or conflicting tags.
 300     AAMDNodes AATags;
 301
 302     NonLocalPointerInfo() : Size(MemoryLocation::UnknownSize) {}
 303   };
 304
 305   /// This map stores the cached results of doing a pointer lookup at the
 306   /// bottom of a block.
 307   ///
 308   /// The key of this map is the pointer+isload bit, the value is a list of
 309   /// <bb->result> mappings.
 310   typedef DenseMap<ValueIsLoadPair, NonLocalPointerInfo>
 311       CachedNonLocalPointerInfo;
 312   CachedNonLocalPointerInfo NonLocalPointerDeps;
 313
 314   // A map from instructions to their non-local pointer dependencies.
 315   typedef DenseMap<Instruction *, SmallPtrSet<ValueIsLoadPair, 4>>
 316       ReverseNonLocalPtrDepTy;
 317   ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
 318
 319   /// This is the instruction we keep for each cached access that we have for
 320   /// an instruction.
 321   ///
 322   /// The pointer is an owning pointer and the bool indicates whether we have
 323   /// any dirty bits in the set.
 324   typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo;
 325
 326   // A map from instructions to their non-local dependencies.
 327   typedef DenseMap<Instruction *, PerInstNLInfo> NonLocalDepMapType;
 328
 329   NonLocalDepMapType NonLocalDeps;
 330
 331   // A reverse mapping from dependencies to the dependees.  This is
 332   // used when removing instructions to keep the cache coherent.
 333   typedef DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>>
 334       ReverseDepMapType;
 335   ReverseDepMapType ReverseLocalDeps;
 336
 337   // A reverse mapping from dependencies to the non-local dependees.
 338   ReverseDepMapType ReverseNonLocalDeps;
 339
 340   /// Current AA implementation, just a cache.
 341   AliasAnalysis &AA;
 342   AssumptionCache &AC;
 343   const TargetLibraryInfo &TLI;
 344   DominatorTree &DT;
 345   PredIteratorCache PredCache;
 346
 347 public:
 348   MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC,
 349                           const TargetLibraryInfo &TLI,
 350                           DominatorTree &DT)
 351       : AA(AA), AC(AC), TLI(TLI), DT(DT) {}
 352
 353   /// Returns the instruction on which a memory operation depends.
 354   ///
 355   /// See the class comment for more details.  It is illegal to call this on
 356   /// non-memory instructions.
 357   MemDepResult getDependency(Instruction *QueryInst);
 358
 359   /// Perform a full dependency query for the specified call, returning the set
 360   /// of blocks that the value is potentially live across.
 361   ///
 362   /// The returned set of results will include a "NonLocal" result for all
 363   /// blocks where the value is live across.
 364   ///
 365   /// This method assumes the instruction returns a "NonLocal" dependency
 366   /// within its own block.
 367   ///
 368   /// This returns a reference to an internal data structure that may be
 369   /// invalidated on the next non-local query or when an instruction is
 370   /// removed.  Clients must copy this data if they want it around longer than
 371   /// that.
 372   const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
 373
 374   /// Perform a full dependency query for an access to the QueryInst's
 375   /// specified memory location, returning the set of instructions that either
 376   /// define or clobber the value.
 377   ///
 378   /// Warning: For a volatile query instruction, the dependencies will be
 379   /// accurate, and thus usable for reordering, but it is never legal to
 380   /// remove the query instruction.
 381   ///
 382   /// This method assumes the pointer has a "NonLocal" dependency within
 383   /// QueryInst's parent basic block.
 384   void getNonLocalPointerDependency(Instruction *QueryInst,
 385                                     SmallVectorImpl<NonLocalDepResult> &Result);
 386
 387   /// Removes an instruction from the dependence analysis, updating the
 388   /// dependence of instructions that previously depended on it.
 389   void removeInstruction(Instruction *InstToRemove);
 390
 391   /// Invalidates cached information about the specified pointer, because it
 392   /// may be too conservative in memdep.
 393   ///
 394   /// This is an optional call that can be used when the client detects an
 395   /// equivalence between the pointer and some other value and replaces the
 396   /// other value with ptr. This can make Ptr available in more places that
 397   /// cached info does not necessarily keep.
 398   void invalidateCachedPointerInfo(Value *Ptr);
 399
 400   /// Clears the PredIteratorCache info.
 401   ///
 402   /// This needs to be done when the CFG changes, e.g., due to splitting
 403   /// critical edges.
 404   void invalidateCachedPredecessors();
 405
 406   /// Returns the instruction on which a memory location depends.
 407   ///
 408   /// If isLoad is true, this routine ignores may-aliases with read-only
 409   /// operations.  If isLoad is false, this routine ignores may-aliases
 410   /// with reads from read-only locations. If possible, pass the query
 411   /// instruction as well; this function may take advantage of the metadata
 412   /// annotated to the query instruction to refine the result.
 413   ///
 414   /// Note that this is an uncached query, and thus may be inefficient.
 415   MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad,
 416                                         BasicBlock::iterator ScanIt,
 417                                         BasicBlock *BB,
 418                                         Instruction *QueryInst = nullptr);
 419
 420   MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc,
 421                                               bool isLoad,
 422                                               BasicBlock::iterator ScanIt,
 423                                               BasicBlock *BB,
 424                                               Instruction *QueryInst);
 425
 426   /// This analysis looks for other loads and stores with invariant.group
 427   /// metadata and the same pointer operand. Returns Unknown if it does not
 428   /// find anything, and Def if it can be assumed that 2 instructions load or
 429   /// store the same value.
 430   /// FIXME: This analysis works only on single block because of restrictions
 431   /// at the call site.
 432   MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);
 433
 434   /// Looks at a memory location for a load (specified by MemLocBase, Offs, and
 435   /// Size) and compares it against a load.
 436   ///
 437   /// If the specified load could be safely widened to a larger integer load
 438   /// that is 1) still efficient, 2) safe for the target, and 3) would provide
 439   /// the specified memory location value, then this function returns the size
 440   /// in bytes of the load width to use.  If not, this returns zero.
 441   static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase,
 442                                                   int64_t MemLocOffs,
 443                                                   unsigned MemLocSize,
 444                                                   const LoadInst *LI);
 445
 446   /// Release memory in caches.
 447   void releaseMemory();
 448
 449 private:
 450   MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
 451                                          BasicBlock::iterator ScanIt,
 452                                          BasicBlock *BB);
 453   bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
 454                                    const PHITransAddr &Pointer,
 455                                    const MemoryLocation &Loc, bool isLoad,
 456                                    BasicBlock *BB,
 457                                    SmallVectorImpl<NonLocalDepResult> &Result,
 458                                    DenseMap<BasicBlock *, Value *> &Visited,
 459                                    bool SkipFirstBlock = false);
 460   MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst,
 461                                        const MemoryLocation &Loc, bool isLoad,
 462                                        BasicBlock *BB, NonLocalDepInfo *Cache,
 463                                        unsigned NumSortedEntries);
 464
 465   void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
 466
 467   void verifyRemoved(Instruction *Inst) const;
 468 };
 469
 470 /// An analysis that produces \c MemoryDependenceResults for a function.
 471 ///
 472 /// This is essentially a no-op because the results are computed entirely
 473 /// lazily.
 474 class MemoryDependenceAnalysis
 475     : public AnalysisInfoMixin<MemoryDependenceAnalysis> {
 476   friend AnalysisInfoMixin<MemoryDependenceAnalysis>;
 477   static char PassID;
 478
 479 public:
 480   typedef MemoryDependenceResults Result;
 481
 482   MemoryDependenceResults run(Function &F, AnalysisManager<Function> &AM);
 483 };
 484
 485 /// A wrapper analysis pass for the legacy pass manager that exposes a \c
 486 /// MemoryDepnedenceResults instance.
 487 class MemoryDependenceWrapperPass : public FunctionPass {
 488   Optional<MemoryDependenceResults> MemDep;
 489 public:
 490   MemoryDependenceWrapperPass();
 491   ~MemoryDependenceWrapperPass() override;
 492   static char ID;
 493
 494   /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
 495   bool runOnFunction(Function &) override;
 496
 497   /// Clean up memory in between runs
 498   void releaseMemory() override;
 499
 500   /// Does not modify anything.  It uses Value Numbering and Alias Analysis.
 501   void getAnalysisUsage(AnalysisUsage &AU) const override;
 502
 503   MemoryDependenceResults &getMemDep() { return *MemDep; }
 504 };
 505
 506 } // End llvm namespace
 507
 508 #endif