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
28namespace llvm {
29class Function;
30class FunctionPass;
31class Instruction;
32class CallSite;
33class AssumptionCache;
34class MemoryDependenceResults;
35class PredIteratorCache;
36class DominatorTree;
37class PHITransAddr;
38
39/// A memory dependence query can return one of three different answers.
40class 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
117public:
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
187private:
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.
201class NonLocalDepEntry {
202  BasicBlock *BB;
203  MemDepResult Result;
204
205public:
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.
226class NonLocalDepResult {
227  NonLocalDepEntry Entry;
228  Value *Address;
229
230public:
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.
267class MemoryDependenceResults {
268  // A map from instructions to their dependency.
269  typedef DenseMap<Instruction *, MemDepResult> LocalDepMapType;
270  LocalDepMapType LocalDeps;
271
272public:
273  typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
274
275private:
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
347public:
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
449private:
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.
474class MemoryDependenceAnalysis
475    : public AnalysisInfoMixin<MemoryDependenceAnalysis> {
476  friend AnalysisInfoMixin<MemoryDependenceAnalysis>;
477  static char PassID;
478
479public:
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.
487class MemoryDependenceWrapperPass : public FunctionPass {
488  Optional<MemoryDependenceResults> MemDep;
489public:
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
509