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