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