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