LLVM  16.0.0git
MemoryDependenceAnalysis.h
Go to the documentation of this file.
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"
21 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/IR/PassManager.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Pass.h"
27 #include <optional>
28 
29 namespace llvm {
30 
31 class AAResults;
32 class AssumptionCache;
33 class BatchAAResults;
34 class DominatorTree;
35 class PHITransAddr;
36 class PhiValues;
37 
38 /// A memory dependence query can return one of three different answers.
39 class MemDepResult {
40  enum DepType {
41  /// Clients of MemDep never see this.
42  ///
43  /// Entries with this marker occur in a LocalDeps map or NonLocalDeps map
44  /// when the instruction they previously referenced was removed from
45  /// MemDep. In either case, the entry may include an instruction pointer.
46  /// If so, the pointer is an instruction in the block where scanning can
47  /// start from, saving some work.
48  ///
49  /// In a default-constructed MemDepResult object, the type will be Invalid
50  /// and the instruction pointer will be null.
51  Invalid = 0,
52 
53  /// This is a dependence on the specified instruction which clobbers the
54  /// desired value. The pointer member of the MemDepResult pair holds the
55  /// instruction that clobbers the memory. For example, this occurs when we
56  /// see a may-aliased store to the memory location we care about.
57  ///
58  /// There are several cases that may be interesting here:
59  /// 1. Loads are clobbered by may-alias stores.
60  /// 2. Loads are considered clobbered by partially-aliased loads. The
61  /// client may choose to analyze deeper into these cases.
62  Clobber,
63 
64  /// This is a dependence on the specified instruction which defines or
65  /// produces the desired memory location. The pointer member of the
66  /// MemDepResult pair holds the instruction that defines the memory.
67  ///
68  /// Cases of interest:
69  /// 1. This could be a load or store for dependence queries on
70  /// load/store. The value loaded or stored is the produced value.
71  /// Note that the pointer operand may be different than that of the
72  /// queried pointer due to must aliases and phi translation. Note
73  /// that the def may not be the same type as the query, the pointers
74  /// may just be must aliases.
75  /// 2. For loads and stores, this could be an allocation instruction. In
76  /// this case, the load is loading an undef value or a store is the
77  /// first store to (that part of) the allocation.
78  /// 3. Dependence queries on calls return Def only when they are readonly
79  /// calls or memory use intrinsics with identical callees and no
80  /// intervening clobbers. No validation is done that the operands to
81  /// the calls are the same.
82  Def,
83 
84  /// This marker indicates that the query has no known dependency in the
85  /// specified block.
86  ///
87  /// More detailed state info is encoded in the upper part of the pair (i.e.
88  /// the Instruction*)
89  Other
90  };
91 
92  /// If DepType is "Other", the upper part of the sum type is an encoding of
93  /// the following more detailed type information.
94  enum OtherType {
95  /// This marker indicates that the query has no dependency in the specified
96  /// block.
97  ///
98  /// To find out more, the client should query other predecessor blocks.
99  NonLocal = 1,
100  /// This marker indicates that the query has no dependency in the specified
101  /// function.
102  NonFuncLocal,
103  /// This marker indicates that the query dependency is unknown.
104  Unknown
105  };
106 
107  using ValueTy = PointerSumType<
112  ValueTy Value;
113 
114  explicit MemDepResult(ValueTy V) : Value(V) {}
115 
116 public:
117  MemDepResult() = default;
118 
119  /// get methods: These are static ctor methods for creating various
120  /// MemDepResult kinds.
122  assert(Inst && "Def requires inst");
123  return MemDepResult(ValueTy::create<Def>(Inst));
124  }
126  assert(Inst && "Clobber requires inst");
127  return MemDepResult(ValueTy::create<Clobber>(Inst));
128  }
130  return MemDepResult(ValueTy::create<Other>(NonLocal));
131  }
133  return MemDepResult(ValueTy::create<Other>(NonFuncLocal));
134  }
136  return MemDepResult(ValueTy::create<Other>(Unknown));
137  }
138 
139  /// Tests if this MemDepResult represents a query that is an instruction
140  /// clobber dependency.
141  bool isClobber() const { return Value.is<Clobber>(); }
142 
143  /// Tests if this MemDepResult represents a query that is an instruction
144  /// definition dependency.
145  bool isDef() const { return Value.is<Def>(); }
146 
147  /// Tests if this MemDepResult represents a query that is transparent to the
148  /// start of the block, but where a non-local hasn't been done.
149  bool isNonLocal() const {
150  return Value.is<Other>() && Value.cast<Other>() == NonLocal;
151  }
152 
153  /// Tests if this MemDepResult represents a query that is transparent to the
154  /// start of the function.
155  bool isNonFuncLocal() const {
156  return Value.is<Other>() && Value.cast<Other>() == NonFuncLocal;
157  }
158 
159  /// Tests if this MemDepResult represents a query which cannot and/or will
160  /// not be computed.
161  bool isUnknown() const {
162  return Value.is<Other>() && Value.cast<Other>() == Unknown;
163  }
164 
165  /// If this is a normal dependency, returns the instruction that is depended
166  /// on. Otherwise, returns null.
167  Instruction *getInst() const {
168  switch (Value.getTag()) {
169  case Invalid:
170  return Value.cast<Invalid>();
171  case Clobber:
172  return Value.cast<Clobber>();
173  case Def:
174  return Value.cast<Def>();
175  case Other:
176  return nullptr;
177  }
178  llvm_unreachable("Unknown discriminant!");
179  }
180 
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  bool operator>(const MemDepResult &M) const { return Value > M.Value; }
185 
186 private:
188 
189  /// Tests if this is a MemDepResult in its dirty/invalid. state.
190  bool isDirty() const { return Value.is<Invalid>(); }
191 
192  static MemDepResult getDirty(Instruction *Inst) {
193  return MemDepResult(ValueTy::create<Invalid>(Inst));
194  }
195 };
196 
197 /// This is an entry in the NonLocalDepInfo cache.
198 ///
199 /// For each BasicBlock (the BB entry) it keeps a MemDepResult.
201  BasicBlock *BB;
202  MemDepResult Result;
203 
204 public:
206  : BB(bb), Result(result) {}
207 
208  // This is used for searches.
210 
211  // BB is the sort key, it can't be changed.
212  BasicBlock *getBB() const { return BB; }
213 
214  void setResult(const MemDepResult &R) { Result = R; }
215 
216  const MemDepResult &getResult() const { return Result; }
217 
218  bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; }
219 };
220 
221 /// This is a result from a NonLocal dependence query.
222 ///
223 /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
224 /// (potentially phi translated) address that was live in the block.
226  NonLocalDepEntry Entry;
227  Value *Address;
228 
229 public:
231  : Entry(bb, result), Address(address) {}
232 
233  // BB is the sort key, it can't be changed.
234  BasicBlock *getBB() const { return Entry.getBB(); }
235 
236  void setResult(const MemDepResult &R, Value *Addr) {
237  Entry.setResult(R);
238  Address = Addr;
239  }
240 
241  const MemDepResult &getResult() const { return Entry.getResult(); }
242 
243  /// Returns the address of this pointer in this block.
244  ///
245  /// This can be different than the address queried for the non-local result
246  /// because of phi translation. This returns null if the address was not
247  /// available in a block (i.e. because phi translation failed) or if this is
248  /// a cached result and that address was deleted.
249  ///
250  /// The address is always null for a non-local 'call' dependence.
251  Value *getAddress() const { return Address; }
252 };
253 
254 /// Provides a lazy, caching interface for making common memory aliasing
255 /// information queries, backed by LLVM's alias analysis passes.
256 ///
257 /// The dependency information returned is somewhat unusual, but is pragmatic.
258 /// If queried about a store or call that might modify memory, the analysis
259 /// will return the instruction[s] that may either load from that memory or
260 /// store to it. If queried with a load or call that can never modify memory,
261 /// the analysis will return calls and stores that might modify the pointer,
262 /// but generally does not return loads unless a) they are volatile, or
263 /// b) they load from *must-aliased* pointers. Returning a dependence on
264 /// must-alias'd pointers instead of all pointers interacts well with the
265 /// internal caching mechanism.
267  // A map from instructions to their dependency.
269  LocalDepMapType LocalDeps;
270 
271 public:
272  using NonLocalDepInfo = std::vector<NonLocalDepEntry>;
273 
274 private:
275  /// A pair<Value*, bool> where the bool is true if the dependence is a read
276  /// only dependence, false if read/write.
278 
279  /// This pair is used when caching information for a block.
280  ///
281  /// If the pointer is null, the cache value is not a full query that starts
282  /// at the specified block. If non-null, the bool indicates whether or not
283  /// the contents of the block was skipped.
285 
286  /// This record is the information kept for each (value, is load) pair.
287  struct NonLocalPointerInfo {
288  /// The pair of the block and the skip-first-block flag.
290  /// The results of the query for each relevant block.
291  NonLocalDepInfo NonLocalDeps;
292  /// The maximum size of the dereferences of the pointer.
293  ///
294  /// May be UnknownSize if the sizes are unknown.
296  /// The AA tags associated with dereferences of the pointer.
297  ///
298  /// The members may be null if there are no tags or conflicting tags.
299  AAMDNodes AATags;
300 
301  NonLocalPointerInfo() = default;
302  };
303 
304  /// Cache storing single nonlocal def for the instruction.
305  /// It is set when nonlocal def would be found in function returning only
306  /// local dependencies.
308  using ReverseNonLocalDefsCacheTy =
310  ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache;
311 
312  /// This map stores the cached results of doing a pointer lookup at the
313  /// bottom of a block.
314  ///
315  /// The key of this map is the pointer+isload bit, the value is a list of
316  /// <bb->result> mappings.
317  using CachedNonLocalPointerInfo =
319  CachedNonLocalPointerInfo NonLocalPointerDeps;
320 
321  // A map from instructions to their non-local pointer dependencies.
322  using ReverseNonLocalPtrDepTy =
324  ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
325 
326  /// This is the instruction we keep for each cached access that we have for
327  /// an instruction.
328  ///
329  /// The pointer is an owning pointer and the bool indicates whether we have
330  /// any dirty bits in the set.
331  using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>;
332 
333  // A map from instructions to their non-local dependencies.
334  using NonLocalDepMapType = DenseMap<Instruction *, PerInstNLInfo>;
335 
336  NonLocalDepMapType NonLocalDepsMap;
337 
338  // A reverse mapping from dependencies to the dependees. This is
339  // used when removing instructions to keep the cache coherent.
340  using ReverseDepMapType =
342  ReverseDepMapType ReverseLocalDeps;
343 
344  // A reverse mapping from dependencies to the non-local dependees.
345  ReverseDepMapType ReverseNonLocalDeps;
346 
347  /// Current AA implementation, just a cache.
348  AAResults &AA;
349  AssumptionCache &AC;
350  const TargetLibraryInfo &TLI;
351  DominatorTree &DT;
352  PhiValues &PV;
353  PredIteratorCache PredCache;
354 
355  unsigned DefaultBlockScanLimit;
356 
357  /// Offsets to dependant clobber loads.
358  using ClobberOffsetsMapType = DenseMap<LoadInst *, int32_t>;
359  ClobberOffsetsMapType ClobberOffsets;
360 
361 public:
363  const TargetLibraryInfo &TLI, DominatorTree &DT,
364  PhiValues &PV, unsigned DefaultBlockScanLimit)
365  : AA(AA), AC(AC), TLI(TLI), DT(DT), PV(PV),
366  DefaultBlockScanLimit(DefaultBlockScanLimit) {}
367 
368  /// Handle invalidation in the new PM.
369  bool invalidate(Function &F, const PreservedAnalyses &PA,
371 
372  /// Some methods limit the number of instructions they will examine.
373  /// The return value of this method is the default limit that will be
374  /// used if no limit is explicitly passed in.
375  unsigned getDefaultBlockScanLimit() const;
376 
377  /// Returns the instruction on which a memory operation depends.
378  ///
379  /// See the class comment for more details. It is illegal to call this on
380  /// non-memory instructions.
382 
383  /// Perform a full dependency query for the specified call, returning the set
384  /// of blocks that the value is potentially live across.
385  ///
386  /// The returned set of results will include a "NonLocal" result for all
387  /// blocks where the value is live across.
388  ///
389  /// This method assumes the instruction returns a "NonLocal" dependency
390  /// within its own block.
391  ///
392  /// This returns a reference to an internal data structure that may be
393  /// invalidated on the next non-local query or when an instruction is
394  /// removed. Clients must copy this data if they want it around longer than
395  /// that.
397 
398  /// Perform a full dependency query for an access to the QueryInst's
399  /// specified memory location, returning the set of instructions that either
400  /// define or clobber the value.
401  ///
402  /// Warning: For a volatile query instruction, the dependencies will be
403  /// accurate, and thus usable for reordering, but it is never legal to
404  /// remove the query instruction.
405  ///
406  /// This method assumes the pointer has a "NonLocal" dependency within
407  /// QueryInst's parent basic block.
410 
411  /// Removes an instruction from the dependence analysis, updating the
412  /// dependence of instructions that previously depended on it.
413  void removeInstruction(Instruction *InstToRemove);
414 
415  /// Invalidates cached information about the specified pointer, because it
416  /// may be too conservative in memdep.
417  ///
418  /// This is an optional call that can be used when the client detects an
419  /// equivalence between the pointer and some other value and replaces the
420  /// other value with ptr. This can make Ptr available in more places that
421  /// cached info does not necessarily keep.
423 
424  /// Clears the PredIteratorCache info.
425  ///
426  /// This needs to be done when the CFG changes, e.g., due to splitting
427  /// critical edges.
429 
430  /// Returns the instruction on which a memory location depends.
431  ///
432  /// If isLoad is true, this routine ignores may-aliases with read-only
433  /// operations. If isLoad is false, this routine ignores may-aliases
434  /// with reads from read-only locations. If possible, pass the query
435  /// instruction as well; this function may take advantage of the metadata
436  /// annotated to the query instruction to refine the result. \p Limit
437  /// can be used to set the maximum number of instructions that will be
438  /// examined to find the pointer dependency. On return, it will be set to
439  /// the number of instructions left to examine. If a null pointer is passed
440  /// in, the limit will default to the value of -memdep-block-scan-limit.
441  ///
442  /// Note that this is an uncached query, and thus may be inefficient.
444  BasicBlock::iterator ScanIt,
445  BasicBlock *BB,
446  Instruction *QueryInst = nullptr,
447  unsigned *Limit = nullptr);
448 
450  BasicBlock::iterator ScanIt,
451  BasicBlock *BB,
452  Instruction *QueryInst,
453  unsigned *Limit,
454  BatchAAResults &BatchAA);
455 
459  Instruction *QueryInst, unsigned *Limit,
460  BatchAAResults &BatchAA);
461 
462  /// This analysis looks for other loads and stores with invariant.group
463  /// metadata and the same pointer operand. Returns Unknown if it does not
464  /// find anything, and Def if it can be assumed that 2 instructions load or
465  /// store the same value and NonLocal which indicate that non-local Def was
466  /// found, which can be retrieved by calling getNonLocalPointerDependency
467  /// with the same queried instruction.
469 
470  /// Release memory in caches.
471  void releaseMemory();
472 
473  /// Return the clobber offset to dependent instruction.
474  std::optional<int32_t> getClobberOffset(LoadInst *DepInst) const {
475  const auto Off = ClobberOffsets.find(DepInst);
476  if (Off != ClobberOffsets.end())
477  return Off->getSecond();
478  return None;
479  }
480 
481 private:
482  MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall,
483  BasicBlock::iterator ScanIt,
484  BasicBlock *BB);
485  bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
486  const PHITransAddr &Pointer,
487  const MemoryLocation &Loc, bool isLoad,
488  BasicBlock *BB,
491  bool SkipFirstBlock = false,
492  bool IsIncomplete = false);
493  MemDepResult getNonLocalInfoForBlock(Instruction *QueryInst,
494  const MemoryLocation &Loc, bool isLoad,
495  BasicBlock *BB, NonLocalDepInfo *Cache,
496  unsigned NumSortedEntries,
497  BatchAAResults &BatchAA);
498 
499  void removeCachedNonLocalPointerDependencies(ValueIsLoadPair P);
500 
501  void verifyRemoved(Instruction *Inst) const;
502 };
503 
504 /// An analysis that produces \c MemoryDependenceResults for a function.
505 ///
506 /// This is essentially a no-op because the results are computed entirely
507 /// lazily.
509  : public AnalysisInfoMixin<MemoryDependenceAnalysis> {
511 
512  static AnalysisKey Key;
513 
514  unsigned DefaultBlockScanLimit;
515 
516 public:
518 
520  MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit) : DefaultBlockScanLimit(DefaultBlockScanLimit) { }
521 
523 };
524 
525 /// A wrapper analysis pass for the legacy pass manager that exposes a \c
526 /// MemoryDepnedenceResults instance.
528  std::optional<MemoryDependenceResults> MemDep;
529 
530 public:
531  static char ID;
532 
534  ~MemoryDependenceWrapperPass() override;
535 
536  /// Pass Implementation stuff. This doesn't do any analysis eagerly.
537  bool runOnFunction(Function &) override;
538 
539  /// Clean up memory in between runs
540  void releaseMemory() override;
541 
542  /// Does not modify anything. It uses Value Numbering and Alias Analysis.
543  void getAnalysisUsage(AnalysisUsage &AU) const override;
544 
545  MemoryDependenceResults &getMemDep() { return *MemDep; }
546 };
547 
548 } // end namespace llvm
549 
550 #endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::MemoryDependenceResults::removeInstruction
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
Definition: MemoryDependenceAnalysis.cpp:1504
llvm::BatchAAResults
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Definition: AliasAnalysis.h:609
llvm::NonLocalDepResult::NonLocalDepResult
NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
Definition: MemoryDependenceAnalysis.h:230
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::NonLocalDepEntry
This is an entry in the NonLocalDepInfo cache.
Definition: MemoryDependenceAnalysis.h:200
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
Optional.h
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:124
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::PHITransAddr
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:35
llvm::MemoryDependenceWrapperPass::getMemDep
MemoryDependenceResults & getMemDep()
Definition: MemoryDependenceAnalysis.h:545
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::PredIteratorCache
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
Definition: PredIteratorCache.h:27
Pass.h
llvm::MemoryDependenceWrapperPass::MemoryDependenceWrapperPass
MemoryDependenceWrapperPass()
Definition: MemoryDependenceAnalysis.cpp:1747
llvm::NonLocalDepEntry::NonLocalDepEntry
NonLocalDepEntry(BasicBlock *bb, MemDepResult result)
Definition: MemoryDependenceAnalysis.h:205
llvm::MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass
~MemoryDependenceWrapperPass() override
llvm::MemoryDependenceWrapperPass::runOnFunction
bool runOnFunction(Function &) override
Pass Implementation stuff. This doesn't do any analysis eagerly.
Definition: MemoryDependenceAnalysis.cpp:1789
llvm::MemoryDependenceAnalysis::MemoryDependenceAnalysis
MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit)
Definition: MemoryDependenceAnalysis.h:520
llvm::MemoryDependenceResults::invalidateCachedPredecessors
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
Definition: MemoryDependenceAnalysis.cpp:1500
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::NonLocalDepEntry::getResult
const MemDepResult & getResult() const
Definition: MemoryDependenceAnalysis.h:216
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
DenseMap.h
PointerEmbeddedInt.h
llvm::MemDepResult::operator>
bool operator>(const MemDepResult &M) const
Definition: MemoryDependenceAnalysis.h:184
llvm::MemDepResult
A memory dependence query can return one of three different answers.
Definition: MemoryDependenceAnalysis.h:39
llvm::NonLocalDepEntry::NonLocalDepEntry
NonLocalDepEntry(BasicBlock *bb)
Definition: MemoryDependenceAnalysis.h:209
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::MemoryDependenceResults::releaseMemory
void releaseMemory()
Release memory in caches.
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MemoryDependenceResults::MemoryDependenceResults
MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, const TargetLibraryInfo &TLI, DominatorTree &DT, PhiValues &PV, unsigned DefaultBlockScanLimit)
Definition: MemoryDependenceAnalysis.h:362
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
PointerIntPair.h
llvm::MemoryDependenceAnalysis::run
MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)
Definition: MemoryDependenceAnalysis.cpp:1726
bb
< i1 > br i1 label label bb bb
Definition: README.txt:978
llvm::NonLocalDepEntry::operator<
bool operator<(const NonLocalDepEntry &RHS) const
Definition: MemoryDependenceAnalysis.h:218
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::NonLocalDepResult::getAddress
Value * getAddress() const
Returns the address of this pointer in this block.
Definition: MemoryDependenceAnalysis.h:251
llvm::LocationSize
Definition: MemoryLocation.h:66
llvm::MemoryDependenceResults::invalidateCachedPointerInfo
void invalidateCachedPointerInfo(Value *Ptr)
Invalidates cached information about the specified pointer, because it may be too conservative in mem...
Definition: MemoryDependenceAnalysis.cpp:1488
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MemoryDependenceResults::getInvariantGroupPointerDependency
MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)
This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...
Definition: MemoryDependenceAnalysis.cpp:278
llvm::Instruction
Definition: Instruction.h:42
llvm::NonLocalDepResult::getBB
BasicBlock * getBB() const
Definition: MemoryDependenceAnalysis.h:234
SmallPtrSet.h
llvm::MemoryDependenceResults::getDefaultBlockScanLimit
unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
Definition: MemoryDependenceAnalysis.cpp:1785
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::NonLocalDepResult
This is a result from a NonLocal dependence query.
Definition: MemoryDependenceAnalysis.h:225
llvm::MemDepResult::isNonFuncLocal
bool isNonFuncLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the function.
Definition: MemoryDependenceAnalysis.h:155
llvm::NonLocalDepResult::setResult
void setResult(const MemDepResult &R, Value *Addr)
Definition: MemoryDependenceAnalysis.h:236
llvm::MemDepResult::getInst
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
Definition: MemoryDependenceAnalysis.h:167
llvm::PointerSumTypeMember
A compile time pair of an integer tag and the pointer-like type which it indexes within a sum type.
Definition: PointerSumType.h:27
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::MemDepResult::getDef
static MemDepResult getDef(Instruction *Inst)
get methods: These are static ctor methods for creating various MemDepResult kinds.
Definition: MemoryDependenceAnalysis.h:121
MemoryLocation.h
llvm::DenseMap< Instruction *, MemDepResult >
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::MemDepResult::isClobber
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
Definition: MemoryDependenceAnalysis.h:141
PredIteratorCache.h
llvm::MemoryDependenceResults::getNonLocalCallDependency
const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
Definition: MemoryDependenceAnalysis.cpp:709
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::MemoryDependenceWrapperPass::releaseMemory
void releaseMemory() override
Clean up memory in between runs.
Definition: MemoryDependenceAnalysis.cpp:1753
llvm::PointerSumType
A sum type over pointer-like types.
Definition: PointerSumType.h:70
isLoad
static bool isLoad(int Opcode)
Definition: ARCInstrInfo.cpp:53
llvm::MemDepResult::MemDepResult
MemDepResult()=default
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::MemoryDependenceResults::getDependency
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
Definition: MemoryDependenceAnalysis.cpp:638
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::MemDepResult::getClobber
static MemDepResult getClobber(Instruction *Inst)
Definition: MemoryDependenceAnalysis.h:125
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::MemoryDependenceResults::getPointerDependencyFrom
MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)
Returns the instruction on which a memory location depends.
Definition: MemoryDependenceAnalysis.cpp:269
llvm::MemDepResult::getNonFuncLocal
static MemDepResult getNonFuncLocal()
Definition: MemoryDependenceAnalysis.h:132
llvm::MemoryDependenceResults::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation in the new PM.
Definition: MemoryDependenceAnalysis.cpp:1766
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:266
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::MemoryDependenceWrapperPass
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Definition: MemoryDependenceAnalysis.h:527
llvm::MemoryDependenceResults::getClobberOffset
std::optional< int32_t > getClobberOffset(LoadInst *DepInst) const
Return the clobber offset to dependent instruction.
Definition: MemoryDependenceAnalysis.h:474
llvm::MemoryDependenceResults::getNonLocalPointerDependency
void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)
Perform a full dependency query for an access to the QueryInst's specified memory location,...
Definition: MemoryDependenceAnalysis.cpp:833
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::MemDepResult::operator<
bool operator<(const MemDepResult &M) const
Definition: MemoryDependenceAnalysis.h:183
llvm::NonLocalDepEntry::getBB
BasicBlock * getBB() const
Definition: MemoryDependenceAnalysis.h:212
llvm::MemoryDependenceAnalysis::MemoryDependenceAnalysis
MemoryDependenceAnalysis()
Definition: MemoryDependenceAnalysis.cpp:1722
Invalid
@ Invalid
Definition: AArch64ISelLowering.cpp:9722
llvm::PointerIntPair< const Value *, 1, bool >
llvm::PhiValues
Class for calculating and caching the underlying values of phis in a function.
Definition: PhiValues.h:40
llvm::MemoryDependenceWrapperPass::ID
static char ID
Definition: MemoryDependenceAnalysis.h:531
llvm::MemoryDependenceResults::NonLocalDepInfo
std::vector< NonLocalDepEntry > NonLocalDepInfo
Definition: MemoryDependenceAnalysis.h:272
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::MemDepResult::getNonLocal
static MemDepResult getNonLocal()
Definition: MemoryDependenceAnalysis.h:129
llvm::MemoryDependenceWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
Does not modify anything. It uses Value Numbering and Alias Analysis.
Definition: MemoryDependenceAnalysis.cpp:1757
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::NonLocalDepResult::getResult
const MemDepResult & getResult() const
Definition: MemoryDependenceAnalysis.h:241
llvm::MemoryDependenceResults::getSimplePointerDependencyFrom
MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)
Definition: MemoryDependenceAnalysis.cpp:364
llvm::MemDepResult::isUnknown
bool isUnknown() const
Tests if this MemDepResult represents a query which cannot and/or will not be computed.
Definition: MemoryDependenceAnalysis.h:161
llvm::MemDepResult::operator!=
bool operator!=(const MemDepResult &M) const
Definition: MemoryDependenceAnalysis.h:182
PointerSumType.h
llvm::MemDepResult::getUnknown
static MemDepResult getUnknown()
Definition: MemoryDependenceAnalysis.h:135
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MemDepResult::operator==
bool operator==(const MemDepResult &M) const
Definition: MemoryDependenceAnalysis.h:181
llvm::MemDepResult::isNonLocal
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
Definition: MemoryDependenceAnalysis.h:149
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::NonLocalDepEntry::setResult
void setResult(const MemDepResult &R)
Definition: MemoryDependenceAnalysis.h:214
llvm::MemoryDependenceAnalysis
An analysis that produces MemoryDependenceResults for a function.
Definition: MemoryDependenceAnalysis.h:508
llvm::MemDepResult::isDef
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
Definition: MemoryDependenceAnalysis.h:145