1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps ---*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the MemoryDependenceAnalysis analysis pass.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
14 #define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
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/AliasAnalysis.h"
23 #include "llvm/Analysis/MemoryLocation.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/IR/PassManager.h"
27 #include "llvm/IR/PredIteratorCache.h"
28 #include "llvm/IR/ValueHandle.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/ErrorHandling.h"
38 class AssumptionCache
;
44 class TargetLibraryInfo
;
48 /// A memory dependence query can return one of three different answers.
51 /// Clients of MemDep never see this.
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.
59 /// In a default-constructed MemDepResult object, the type will be Invalid
60 /// and the instruction pointer will be null.
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.
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.
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.
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.
94 /// This marker indicates that the query has no known dependency in the
97 /// More detailed state info is encoded in the upper part of the pair (i.e.
102 /// If DepType is "Other", the upper part of the sum type is an encoding of
103 /// the following more detailed type information.
105 /// This marker indicates that the query has no dependency in the specified
108 /// To find out more, the client should query other predecessor blocks.
110 /// This marker indicates that the query has no dependency in the specified
113 /// This marker indicates that the query dependency is unknown.
117 using ValueTy
= PointerSumType
<
118 DepType
, PointerSumTypeMember
<Invalid
, Instruction
*>,
119 PointerSumTypeMember
<Clobber
, Instruction
*>,
120 PointerSumTypeMember
<Def
, Instruction
*>,
121 PointerSumTypeMember
<Other
, PointerEmbeddedInt
<OtherType
, 3>>>;
124 explicit MemDepResult(ValueTy V
) : Value(V
) {}
127 MemDepResult() = default;
129 /// get methods: These are static ctor methods for creating various
130 /// MemDepResult kinds.
131 static MemDepResult
getDef(Instruction
*Inst
) {
132 assert(Inst
&& "Def requires inst");
133 return MemDepResult(ValueTy::create
<Def
>(Inst
));
135 static MemDepResult
getClobber(Instruction
*Inst
) {
136 assert(Inst
&& "Clobber requires inst");
137 return MemDepResult(ValueTy::create
<Clobber
>(Inst
));
139 static MemDepResult
getNonLocal() {
140 return MemDepResult(ValueTy::create
<Other
>(NonLocal
));
142 static MemDepResult
getNonFuncLocal() {
143 return MemDepResult(ValueTy::create
<Other
>(NonFuncLocal
));
145 static MemDepResult
getUnknown() {
146 return MemDepResult(ValueTy::create
<Other
>(Unknown
));
149 /// Tests if this MemDepResult represents a query that is an instruction
150 /// clobber dependency.
151 bool isClobber() const { return Value
.is
<Clobber
>(); }
153 /// Tests if this MemDepResult represents a query that is an instruction
154 /// definition dependency.
155 bool isDef() const { return Value
.is
<Def
>(); }
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
;
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
;
169 /// Tests if this MemDepResult represents a query which cannot and/or will
171 bool isUnknown() const {
172 return Value
.is
<Other
>() && Value
.cast
<Other
>() == Unknown
;
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()) {
180 return Value
.cast
<Invalid
>();
182 return Value
.cast
<Clobber
>();
184 return Value
.cast
<Def
>();
188 llvm_unreachable("Unknown discriminant!");
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
; }
197 friend class MemoryDependenceResults
;
199 /// Tests if this is a MemDepResult in its dirty/invalid. state.
200 bool isDirty() const { return Value
.is
<Invalid
>(); }
202 static MemDepResult
getDirty(Instruction
*Inst
) {
203 return MemDepResult(ValueTy::create
<Invalid
>(Inst
));
207 /// This is an entry in the NonLocalDepInfo cache.
209 /// For each BasicBlock (the BB entry) it keeps a MemDepResult.
210 class NonLocalDepEntry
{
215 NonLocalDepEntry(BasicBlock
*bb
, MemDepResult result
)
216 : BB(bb
), Result(result
) {}
218 // This is used for searches.
219 NonLocalDepEntry(BasicBlock
*bb
) : BB(bb
) {}
221 // BB is the sort key, it can't be changed.
222 BasicBlock
*getBB() const { return BB
; }
224 void setResult(const MemDepResult
&R
) { Result
= R
; }
226 const MemDepResult
&getResult() const { return Result
; }
228 bool operator<(const NonLocalDepEntry
&RHS
) const { return BB
< RHS
.BB
; }
231 /// This is a result from a NonLocal dependence query.
233 /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
234 /// (potentially phi translated) address that was live in the block.
235 class NonLocalDepResult
{
236 NonLocalDepEntry Entry
;
240 NonLocalDepResult(BasicBlock
*bb
, MemDepResult result
, Value
*address
)
241 : Entry(bb
, result
), Address(address
) {}
243 // BB is the sort key, it can't be changed.
244 BasicBlock
*getBB() const { return Entry
.getBB(); }
246 void setResult(const MemDepResult
&R
, Value
*Addr
) {
251 const MemDepResult
&getResult() const { return Entry
.getResult(); }
253 /// Returns the address of this pointer in this block.
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.
260 /// The address is always null for a non-local 'call' dependence.
261 Value
*getAddress() const { return Address
; }
264 /// Provides a lazy, caching interface for making common memory aliasing
265 /// information queries, backed by LLVM's alias analysis passes.
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.
276 class MemoryDependenceResults
{
277 // A map from instructions to their dependency.
278 using LocalDepMapType
= DenseMap
<Instruction
*, MemDepResult
>;
279 LocalDepMapType LocalDeps
;
282 using NonLocalDepInfo
= std::vector
<NonLocalDepEntry
>;
285 /// A pair<Value*, bool> where the bool is true if the dependence is a read
286 /// only dependence, false if read/write.
287 using ValueIsLoadPair
= PointerIntPair
<const Value
*, 1, bool>;
289 /// This pair is used when caching information for a block.
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.
294 using BBSkipFirstBlockPair
= PointerIntPair
<BasicBlock
*, 1, bool>;
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.
299 BBSkipFirstBlockPair Pair
;
300 /// The results of the query for each relevant block.
301 NonLocalDepInfo NonLocalDeps
;
302 /// The maximum size of the dereferences of the pointer.
304 /// May be UnknownSize if the sizes are unknown.
305 LocationSize Size
= LocationSize::unknown();
306 /// The AA tags associated with dereferences of the pointer.
308 /// The members may be null if there are no tags or conflicting tags.
311 NonLocalPointerInfo() = default;
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.
317 DenseMap
<AssertingVH
<const Value
>, NonLocalDepResult
> NonLocalDefsCache
;
318 using ReverseNonLocalDefsCacheTy
=
319 DenseMap
<Instruction
*, SmallPtrSet
<const Value
*, 4>>;
320 ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache
;
322 /// This map stores the cached results of doing a pointer lookup at the
323 /// bottom of a block.
325 /// The key of this map is the pointer+isload bit, the value is a list of
326 /// <bb->result> mappings.
327 using CachedNonLocalPointerInfo
=
328 DenseMap
<ValueIsLoadPair
, NonLocalPointerInfo
>;
329 CachedNonLocalPointerInfo NonLocalPointerDeps
;
331 // A map from instructions to their non-local pointer dependencies.
332 using ReverseNonLocalPtrDepTy
=
333 DenseMap
<Instruction
*, SmallPtrSet
<ValueIsLoadPair
, 4>>;
334 ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps
;
336 /// This is the instruction we keep for each cached access that we have for
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>;
343 // A map from instructions to their non-local dependencies.
344 using NonLocalDepMapType
= DenseMap
<Instruction
*, PerInstNLInfo
>;
346 NonLocalDepMapType NonLocalDeps
;
348 // A reverse mapping from dependencies to the dependees. This is
349 // used when removing instructions to keep the cache coherent.
350 using ReverseDepMapType
=
351 DenseMap
<Instruction
*, SmallPtrSet
<Instruction
*, 4>>;
352 ReverseDepMapType ReverseLocalDeps
;
354 // A reverse mapping from dependencies to the non-local dependees.
355 ReverseDepMapType ReverseNonLocalDeps
;
357 /// Current AA implementation, just a cache.
360 const TargetLibraryInfo
&TLI
;
363 PredIteratorCache PredCache
;
365 unsigned DefaultBlockScanLimit
;
368 MemoryDependenceResults(AliasAnalysis
&AA
, AssumptionCache
&AC
,
369 const TargetLibraryInfo
&TLI
, DominatorTree
&DT
,
370 PhiValues
&PV
, unsigned DefaultBlockScanLimit
)
371 : AA(AA
), AC(AC
), TLI(TLI
), DT(DT
), PV(PV
),
372 DefaultBlockScanLimit(DefaultBlockScanLimit
) {}
374 /// Handle invalidation in the new PM.
375 bool invalidate(Function
&F
, const PreservedAnalyses
&PA
,
376 FunctionAnalysisManager::Invalidator
&Inv
);
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;
383 /// Returns the instruction on which a memory operation depends.
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 OrderedBasicBlock
*OBB
= nullptr);
390 /// Perform a full dependency query for the specified call, returning the set
391 /// of blocks that the value is potentially live across.
393 /// The returned set of results will include a "NonLocal" result for all
394 /// blocks where the value is live across.
396 /// This method assumes the instruction returns a "NonLocal" dependency
397 /// within its own block.
399 /// This returns a reference to an internal data structure that may be
400 /// invalidated on the next non-local query or when an instruction is
401 /// removed. Clients must copy this data if they want it around longer than
403 const NonLocalDepInfo
&getNonLocalCallDependency(CallBase
*QueryCall
);
405 /// Perform a full dependency query for an access to the QueryInst's
406 /// specified memory location, returning the set of instructions that either
407 /// define or clobber the value.
409 /// Warning: For a volatile query instruction, the dependencies will be
410 /// accurate, and thus usable for reordering, but it is never legal to
411 /// remove the query instruction.
413 /// This method assumes the pointer has a "NonLocal" dependency within
414 /// QueryInst's parent basic block.
415 void getNonLocalPointerDependency(Instruction
*QueryInst
,
416 SmallVectorImpl
<NonLocalDepResult
> &Result
);
418 /// Removes an instruction from the dependence analysis, updating the
419 /// dependence of instructions that previously depended on it.
420 void removeInstruction(Instruction
*InstToRemove
);
422 /// Invalidates cached information about the specified pointer, because it
423 /// may be too conservative in memdep.
425 /// This is an optional call that can be used when the client detects an
426 /// equivalence between the pointer and some other value and replaces the
427 /// other value with ptr. This can make Ptr available in more places that
428 /// cached info does not necessarily keep.
429 void invalidateCachedPointerInfo(Value
*Ptr
);
431 /// Clears the PredIteratorCache info.
433 /// This needs to be done when the CFG changes, e.g., due to splitting
435 void invalidateCachedPredecessors();
437 /// Returns the instruction on which a memory location depends.
439 /// If isLoad is true, this routine ignores may-aliases with read-only
440 /// operations. If isLoad is false, this routine ignores may-aliases
441 /// with reads from read-only locations. If possible, pass the query
442 /// instruction as well; this function may take advantage of the metadata
443 /// annotated to the query instruction to refine the result. \p Limit
444 /// can be used to set the maximum number of instructions that will be
445 /// examined to find the pointer dependency. On return, it will be set to
446 /// the number of instructions left to examine. If a null pointer is passed
447 /// in, the limit will default to the value of -memdep-block-scan-limit.
449 /// Note that this is an uncached query, and thus may be inefficient.
450 MemDepResult
getPointerDependencyFrom(const MemoryLocation
&Loc
, bool isLoad
,
451 BasicBlock::iterator ScanIt
,
453 Instruction
*QueryInst
= nullptr,
454 unsigned *Limit
= nullptr,
455 OrderedBasicBlock
*OBB
= nullptr);
458 getSimplePointerDependencyFrom(const MemoryLocation
&MemLoc
, bool isLoad
,
459 BasicBlock::iterator ScanIt
, BasicBlock
*BB
,
460 Instruction
*QueryInst
, unsigned *Limit
,
461 OrderedBasicBlock
*OBB
);
463 /// This analysis looks for other loads and stores with invariant.group
464 /// metadata and the same pointer operand. Returns Unknown if it does not
465 /// find anything, and Def if it can be assumed that 2 instructions load or
466 /// store the same value and NonLocal which indicate that non-local Def was
467 /// found, which can be retrieved by calling getNonLocalPointerDependency
468 /// with the same queried instruction.
469 MemDepResult
getInvariantGroupPointerDependency(LoadInst
*LI
, BasicBlock
*BB
);
471 /// Looks at a memory location for a load (specified by MemLocBase, Offs, and
472 /// Size) and compares it against a load.
474 /// If the specified load could be safely widened to a larger integer load
475 /// that is 1) still efficient, 2) safe for the target, and 3) would provide
476 /// the specified memory location value, then this function returns the size
477 /// in bytes of the load width to use. If not, this returns zero.
478 static unsigned getLoadLoadClobberFullWidthSize(const Value
*MemLocBase
,
483 /// Release memory in caches.
484 void releaseMemory();
487 MemDepResult
getCallDependencyFrom(CallBase
*Call
, bool isReadOnlyCall
,
488 BasicBlock::iterator ScanIt
,
490 bool getNonLocalPointerDepFromBB(Instruction
*QueryInst
,
491 const PHITransAddr
&Pointer
,
492 const MemoryLocation
&Loc
, bool isLoad
,
494 SmallVectorImpl
<NonLocalDepResult
> &Result
,
495 DenseMap
<BasicBlock
*, Value
*> &Visited
,
496 bool SkipFirstBlock
= false);
497 MemDepResult
GetNonLocalInfoForBlock(Instruction
*QueryInst
,
498 const MemoryLocation
&Loc
, bool isLoad
,
499 BasicBlock
*BB
, NonLocalDepInfo
*Cache
,
500 unsigned NumSortedEntries
);
502 void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P
);
504 void verifyRemoved(Instruction
*Inst
) const;
507 /// An analysis that produces \c MemoryDependenceResults for a function.
509 /// This is essentially a no-op because the results are computed entirely
511 class MemoryDependenceAnalysis
512 : public AnalysisInfoMixin
<MemoryDependenceAnalysis
> {
513 friend AnalysisInfoMixin
<MemoryDependenceAnalysis
>;
515 static AnalysisKey Key
;
517 unsigned DefaultBlockScanLimit
;
520 using Result
= MemoryDependenceResults
;
522 MemoryDependenceAnalysis();
523 MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit
) : DefaultBlockScanLimit(DefaultBlockScanLimit
) { }
525 MemoryDependenceResults
run(Function
&F
, FunctionAnalysisManager
&AM
);
528 /// A wrapper analysis pass for the legacy pass manager that exposes a \c
529 /// MemoryDepnedenceResults instance.
530 class MemoryDependenceWrapperPass
: public FunctionPass
{
531 Optional
<MemoryDependenceResults
> MemDep
;
536 MemoryDependenceWrapperPass();
537 ~MemoryDependenceWrapperPass() override
;
539 /// Pass Implementation stuff. This doesn't do any analysis eagerly.
540 bool runOnFunction(Function
&) override
;
542 /// Clean up memory in between runs
543 void releaseMemory() override
;
545 /// Does not modify anything. It uses Value Numbering and Alias Analysis.
546 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
548 MemoryDependenceResults
&getMemDep() { return *MemDep
; }
551 } // end namespace llvm
553 #endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H