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