Line data Source code
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 10527806 : 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 0 : 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 0 : 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 2867898 : switch (Value.getTag()) {
181 1403466 : case Invalid:
182 : return Value.cast<Invalid>();
183 2267648 : case Clobber:
184 : return Value.cast<Clobber>();
185 1266856 : case Def:
186 : return Value.cast<Def>();
187 : case Other:
188 : return nullptr;
189 : }
190 0 : 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 3625145 : : 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 0 : BasicBlock *getBB() const { return BB; }
225 :
226 15724 : void setResult(const MemDepResult &R) { Result = R; }
227 :
228 0 : const MemDepResult &getResult() const { return Result; }
229 :
230 0 : 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 1480185 : : Entry(bb, result), Address(address) {}
244 :
245 : // BB is the sort key, it can't be changed.
246 1378394 : 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 0 : 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 1769582 : 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 = LocationSize::unknown();
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 0 : 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 151206 : MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC,
369 : const TargetLibraryInfo &TLI,
370 : DominatorTree &DT, PhiValues &PV)
371 151206 : : 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 13572 : 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
|
