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

source code of llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h