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