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