LLVM  15.0.0git
MemoryDependenceAnalysis.cpp
Go to the documentation of this file.
1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
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 implements an analysis that determines, for a given memory
10 // operation, what preceding memory operations it depends on. It builds on
11 // alias analysis information, and tries to provide a lazy, caching interface to
12 // a common kind of alias information query.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/InstrTypes.h"
34 #include "llvm/IR/Instruction.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/LLVMContext.h"
38 #include "llvm/IR/Metadata.h"
39 #include "llvm/IR/Module.h"
41 #include "llvm/IR/Type.h"
42 #include "llvm/IR/Use.h"
43 #include "llvm/IR/Value.h"
44 #include "llvm/InitializePasses.h"
45 #include "llvm/Pass.h"
47 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/Compiler.h"
50 #include "llvm/Support/Debug.h"
51 #include <algorithm>
52 #include <cassert>
53 #include <iterator>
54 #include <utility>
55 
56 using namespace llvm;
57 
58 #define DEBUG_TYPE "memdep"
59 
60 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
61 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
62 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
63 
64 STATISTIC(NumCacheNonLocalPtr,
65  "Number of fully cached non-local ptr responses");
66 STATISTIC(NumCacheDirtyNonLocalPtr,
67  "Number of cached, but dirty, non-local ptr responses");
68 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
69 STATISTIC(NumCacheCompleteNonLocalPtr,
70  "Number of block queries that were completely cached");
71 
72 // Limit for the number of instructions to scan in a block.
73 
75  "memdep-block-scan-limit", cl::Hidden, cl::init(100),
76  cl::desc("The number of instructions to scan in a block in memory "
77  "dependency analysis (default = 100)"));
78 
79 static cl::opt<unsigned>
80  BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
81  cl::desc("The number of blocks to scan during memory "
82  "dependency analysis (default = 1000)"));
83 
84 // Limit on the number of memdep results to process.
85 static const unsigned int NumResultsLimit = 100;
86 
87 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
88 ///
89 /// If the set becomes empty, remove Inst's entry.
90 template <typename KeyTy>
91 static void
93  Instruction *Inst, KeyTy Val) {
94  typename DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>>::iterator InstIt =
95  ReverseMap.find(Inst);
96  assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
97  bool Found = InstIt->second.erase(Val);
98  assert(Found && "Invalid reverse map!");
99  (void)Found;
100  if (InstIt->second.empty())
101  ReverseMap.erase(InstIt);
102 }
103 
104 /// If the given instruction references a specific memory location, fill in Loc
105 /// with the details, otherwise set Loc.Ptr to null.
106 ///
107 /// Returns a ModRefInfo value describing the general behavior of the
108 /// instruction.
110  const TargetLibraryInfo &TLI) {
111  if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
112  if (LI->isUnordered()) {
113  Loc = MemoryLocation::get(LI);
114  return ModRefInfo::Ref;
115  }
116  if (LI->getOrdering() == AtomicOrdering::Monotonic) {
117  Loc = MemoryLocation::get(LI);
118  return ModRefInfo::ModRef;
119  }
120  Loc = MemoryLocation();
121  return ModRefInfo::ModRef;
122  }
123 
124  if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
125  if (SI->isUnordered()) {
126  Loc = MemoryLocation::get(SI);
127  return ModRefInfo::Mod;
128  }
129  if (SI->getOrdering() == AtomicOrdering::Monotonic) {
130  Loc = MemoryLocation::get(SI);
131  return ModRefInfo::ModRef;
132  }
133  Loc = MemoryLocation();
134  return ModRefInfo::ModRef;
135  }
136 
137  if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
138  Loc = MemoryLocation::get(V);
139  return ModRefInfo::ModRef;
140  }
141 
142  if (const CallInst *CI = isFreeCall(Inst, &TLI)) {
143  // calls to free() deallocate the entire structure
144  Loc = MemoryLocation::getAfter(CI->getArgOperand(0));
145  return ModRefInfo::Mod;
146  }
147 
148  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
149  switch (II->getIntrinsicID()) {
150  case Intrinsic::lifetime_start:
151  case Intrinsic::lifetime_end:
152  case Intrinsic::invariant_start:
153  Loc = MemoryLocation::getForArgument(II, 1, TLI);
154  // These intrinsics don't really modify the memory, but returning Mod
155  // will allow them to be handled conservatively.
156  return ModRefInfo::Mod;
157  case Intrinsic::invariant_end:
158  Loc = MemoryLocation::getForArgument(II, 2, TLI);
159  // These intrinsics don't really modify the memory, but returning Mod
160  // will allow them to be handled conservatively.
161  return ModRefInfo::Mod;
162  case Intrinsic::masked_load:
163  Loc = MemoryLocation::getForArgument(II, 0, TLI);
164  return ModRefInfo::Ref;
165  case Intrinsic::masked_store:
166  Loc = MemoryLocation::getForArgument(II, 1, TLI);
167  return ModRefInfo::Mod;
168  default:
169  break;
170  }
171  }
172 
173  // Otherwise, just do the coarse-grained thing that always works.
174  if (Inst->mayWriteToMemory())
175  return ModRefInfo::ModRef;
176  if (Inst->mayReadFromMemory())
177  return ModRefInfo::Ref;
178  return ModRefInfo::NoModRef;
179 }
180 
181 /// Private helper for finding the local dependencies of a call site.
182 MemDepResult MemoryDependenceResults::getCallDependencyFrom(
183  CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
184  BasicBlock *BB) {
185  unsigned Limit = getDefaultBlockScanLimit();
186 
187  // Walk backwards through the block, looking for dependencies.
188  while (ScanIt != BB->begin()) {
189  Instruction *Inst = &*--ScanIt;
190  // Debug intrinsics don't cause dependences and should not affect Limit
191  if (isa<DbgInfoIntrinsic>(Inst))
192  continue;
193 
194  // Limit the amount of scanning we do so we don't end up with quadratic
195  // running time on extreme testcases.
196  --Limit;
197  if (!Limit)
198  return MemDepResult::getUnknown();
199 
200  // If this inst is a memory op, get the pointer it accessed
201  MemoryLocation Loc;
202  ModRefInfo MR = GetLocation(Inst, Loc, TLI);
203  if (Loc.Ptr) {
204  // A simple instruction.
205  if (isModOrRefSet(AA.getModRefInfo(Call, Loc)))
206  return MemDepResult::getClobber(Inst);
207  continue;
208  }
209 
210  if (auto *CallB = dyn_cast<CallBase>(Inst)) {
211  // If these two calls do not interfere, look past it.
212  if (isNoModRef(AA.getModRefInfo(Call, CallB))) {
213  // If the two calls are the same, return Inst as a Def, so that
214  // Call can be found redundant and eliminated.
215  if (isReadOnlyCall && !isModSet(MR) &&
216  Call->isIdenticalToWhenDefined(CallB))
217  return MemDepResult::getDef(Inst);
218 
219  // Otherwise if the two calls don't interact (e.g. CallB is readnone)
220  // keep scanning.
221  continue;
222  } else
223  return MemDepResult::getClobber(Inst);
224  }
225 
226  // If we could not obtain a pointer for the instruction and the instruction
227  // touches memory then assume that this is a dependency.
228  if (isModOrRefSet(MR))
229  return MemDepResult::getClobber(Inst);
230  }
231 
232  // No dependence found. If this is the entry block of the function, it is
233  // unknown, otherwise it is non-local.
234  if (BB != &BB->getParent()->getEntryBlock())
235  return MemDepResult::getNonLocal();
237 }
238 
240  const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
241  BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
242  BatchAAResults &BatchAA) {
243  MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
244  if (QueryInst != nullptr) {
245  if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
246  InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
247 
248  if (InvariantGroupDependency.isDef())
249  return InvariantGroupDependency;
250  }
251  }
253  MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, BatchAA);
254  if (SimpleDep.isDef())
255  return SimpleDep;
256  // Non-local invariant group dependency indicates there is non local Def
257  // (it only returns nonLocal if it finds nonLocal def), which is better than
258  // local clobber and everything else.
259  if (InvariantGroupDependency.isNonLocal())
260  return InvariantGroupDependency;
261 
262  assert(InvariantGroupDependency.isUnknown() &&
263  "InvariantGroupDependency should be only unknown at this point");
264  return SimpleDep;
265 }
266 
268  const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
269  BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
270  BatchAAResults BatchAA(AA);
271  return getPointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst, Limit,
272  BatchAA);
273 }
274 
277  BasicBlock *BB) {
278 
279  if (!LI->hasMetadata(LLVMContext::MD_invariant_group))
280  return MemDepResult::getUnknown();
281 
282  // Take the ptr operand after all casts and geps 0. This way we can search
283  // cast graph down only.
284  Value *LoadOperand = LI->getPointerOperand()->stripPointerCasts();
285 
286  // It's is not safe to walk the use list of global value, because function
287  // passes aren't allowed to look outside their functions.
288  // FIXME: this could be fixed by filtering instructions from outside
289  // of current function.
290  if (isa<GlobalValue>(LoadOperand))
291  return MemDepResult::getUnknown();
292 
293  // Queue to process all pointers that are equivalent to load operand.
294  SmallVector<const Value *, 8> LoadOperandsQueue;
295  LoadOperandsQueue.push_back(LoadOperand);
296 
297  Instruction *ClosestDependency = nullptr;
298  // Order of instructions in uses list is unpredictible. In order to always
299  // get the same result, we will look for the closest dominance.
300  auto GetClosestDependency = [this](Instruction *Best, Instruction *Other) {
301  assert(Other && "Must call it with not null instruction");
302  if (Best == nullptr || DT.dominates(Best, Other))
303  return Other;
304  return Best;
305  };
306 
307  // FIXME: This loop is O(N^2) because dominates can be O(n) and in worst case
308  // we will see all the instructions. This should be fixed in MSSA.
309  while (!LoadOperandsQueue.empty()) {
310  const Value *Ptr = LoadOperandsQueue.pop_back_val();
311  assert(Ptr && !isa<GlobalValue>(Ptr) &&
312  "Null or GlobalValue should not be inserted");
313 
314  for (const Use &Us : Ptr->uses()) {
315  auto *U = dyn_cast<Instruction>(Us.getUser());
316  if (!U || U == LI || !DT.dominates(U, LI))
317  continue;
318 
319  // Bitcast or gep with zeros are using Ptr. Add to queue to check it's
320  // users. U = bitcast Ptr
321  if (isa<BitCastInst>(U)) {
322  LoadOperandsQueue.push_back(U);
323  continue;
324  }
325  // Gep with zeros is equivalent to bitcast.
326  // FIXME: we are not sure if some bitcast should be canonicalized to gep 0
327  // or gep 0 to bitcast because of SROA, so there are 2 forms. When
328  // typeless pointers will be ready then both cases will be gone
329  // (and this BFS also won't be needed).
330  if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
331  if (GEP->hasAllZeroIndices()) {
332  LoadOperandsQueue.push_back(U);
333  continue;
334  }
335 
336  // If we hit load/store with the same invariant.group metadata (and the
337  // same pointer operand) we can assume that value pointed by pointer
338  // operand didn't change.
339  if ((isa<LoadInst>(U) ||
340  (isa<StoreInst>(U) &&
341  cast<StoreInst>(U)->getPointerOperand() == Ptr)) &&
342  U->hasMetadata(LLVMContext::MD_invariant_group))
343  ClosestDependency = GetClosestDependency(ClosestDependency, U);
344  }
345  }
346 
347  if (!ClosestDependency)
348  return MemDepResult::getUnknown();
349  if (ClosestDependency->getParent() == BB)
350  return MemDepResult::getDef(ClosestDependency);
351  // Def(U) can't be returned here because it is non-local. If local
352  // dependency won't be found then return nonLocal counting that the
353  // user will call getNonLocalPointerDependency, which will return cached
354  // result.
355  NonLocalDefsCache.try_emplace(
356  LI, NonLocalDepResult(ClosestDependency->getParent(),
357  MemDepResult::getDef(ClosestDependency), nullptr));
358  ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
359  return MemDepResult::getNonLocal();
360 }
361 
363  const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
364  BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
365  BatchAAResults &BatchAA) {
366  bool isInvariantLoad = false;
367 
368  unsigned DefaultLimit = getDefaultBlockScanLimit();
369  if (!Limit)
370  Limit = &DefaultLimit;
371 
372  // We must be careful with atomic accesses, as they may allow another thread
373  // to touch this location, clobbering it. We are conservative: if the
374  // QueryInst is not a simple (non-atomic) memory access, we automatically
375  // return getClobber.
376  // If it is simple, we know based on the results of
377  // "Compiler testing via a theory of sound optimisations in the C11/C++11
378  // memory model" in PLDI 2013, that a non-atomic location can only be
379  // clobbered between a pair of a release and an acquire action, with no
380  // access to the location in between.
381  // Here is an example for giving the general intuition behind this rule.
382  // In the following code:
383  // store x 0;
384  // release action; [1]
385  // acquire action; [4]
386  // %val = load x;
387  // It is unsafe to replace %val by 0 because another thread may be running:
388  // acquire action; [2]
389  // store x 42;
390  // release action; [3]
391  // with synchronization from 1 to 2 and from 3 to 4, resulting in %val
392  // being 42. A key property of this program however is that if either
393  // 1 or 4 were missing, there would be a race between the store of 42
394  // either the store of 0 or the load (making the whole program racy).
395  // The paper mentioned above shows that the same property is respected
396  // by every program that can detect any optimization of that kind: either
397  // it is racy (undefined) or there is a release followed by an acquire
398  // between the pair of accesses under consideration.
399 
400  // If the load is invariant, we "know" that it doesn't alias *any* write. We
401  // do want to respect mustalias results since defs are useful for value
402  // forwarding, but any mayalias write can be assumed to be noalias.
403  // Arguably, this logic should be pushed inside AliasAnalysis itself.
404  if (isLoad && QueryInst) {
405  LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
406  if (LI && LI->hasMetadata(LLVMContext::MD_invariant_load))
407  isInvariantLoad = true;
408  }
409 
410  // True for volatile instruction.
411  // For Load/Store return true if atomic ordering is stronger than AO,
412  // for other instruction just true if it can read or write to memory.
413  auto isComplexForReordering = [](Instruction * I, AtomicOrdering AO)->bool {
414  if (I->isVolatile())
415  return true;
416  if (auto *LI = dyn_cast<LoadInst>(I))
417  return isStrongerThan(LI->getOrdering(), AO);
418  if (auto *SI = dyn_cast<StoreInst>(I))
419  return isStrongerThan(SI->getOrdering(), AO);
420  return I->mayReadOrWriteMemory();
421  };
422 
423  // Walk backwards through the basic block, looking for dependencies.
424  while (ScanIt != BB->begin()) {
425  Instruction *Inst = &*--ScanIt;
426 
427  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
428  // Debug intrinsics don't (and can't) cause dependencies.
429  if (isa<DbgInfoIntrinsic>(II))
430  continue;
431 
432  // Limit the amount of scanning we do so we don't end up with quadratic
433  // running time on extreme testcases.
434  --*Limit;
435  if (!*Limit)
436  return MemDepResult::getUnknown();
437 
438  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
439  // If we reach a lifetime begin or end marker, then the query ends here
440  // because the value is undefined.
441  Intrinsic::ID ID = II->getIntrinsicID();
442  switch (ID) {
443  case Intrinsic::lifetime_start: {
444  // FIXME: This only considers queries directly on the invariant-tagged
445  // pointer, not on query pointers that are indexed off of them. It'd
446  // be nice to handle that at some point (the right approach is to use
447  // GetPointerBaseWithConstantOffset).
448  MemoryLocation ArgLoc = MemoryLocation::getAfter(II->getArgOperand(1));
449  if (BatchAA.isMustAlias(ArgLoc, MemLoc))
450  return MemDepResult::getDef(II);
451  continue;
452  }
453  case Intrinsic::masked_load:
454  case Intrinsic::masked_store: {
455  MemoryLocation Loc;
456  /*ModRefInfo MR =*/ GetLocation(II, Loc, TLI);
457  AliasResult R = BatchAA.alias(Loc, MemLoc);
458  if (R == AliasResult::NoAlias)
459  continue;
460  if (R == AliasResult::MustAlias)
461  return MemDepResult::getDef(II);
462  if (ID == Intrinsic::masked_load)
463  continue;
464  return MemDepResult::getClobber(II);
465  }
466  }
467  }
468 
469  // Values depend on loads if the pointers are must aliased. This means
470  // that a load depends on another must aliased load from the same value.
471  // One exception is atomic loads: a value can depend on an atomic load that
472  // it does not alias with when this atomic load indicates that another
473  // thread may be accessing the location.
474  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
475  // While volatile access cannot be eliminated, they do not have to clobber
476  // non-aliasing locations, as normal accesses, for example, can be safely
477  // reordered with volatile accesses.
478  if (LI->isVolatile()) {
479  if (!QueryInst)
480  // Original QueryInst *may* be volatile
481  return MemDepResult::getClobber(LI);
482  if (QueryInst->isVolatile())
483  // Ordering required if QueryInst is itself volatile
484  return MemDepResult::getClobber(LI);
485  // Otherwise, volatile doesn't imply any special ordering
486  }
487 
488  // Atomic loads have complications involved.
489  // A Monotonic (or higher) load is OK if the query inst is itself not
490  // atomic.
491  // FIXME: This is overly conservative.
492  if (LI->isAtomic() && isStrongerThanUnordered(LI->getOrdering())) {
493  if (!QueryInst ||
494  isComplexForReordering(QueryInst, AtomicOrdering::NotAtomic))
495  return MemDepResult::getClobber(LI);
496  if (LI->getOrdering() != AtomicOrdering::Monotonic)
497  return MemDepResult::getClobber(LI);
498  }
499 
500  MemoryLocation LoadLoc = MemoryLocation::get(LI);
501 
502  // If we found a pointer, check if it could be the same as our pointer.
503  AliasResult R = BatchAA.alias(LoadLoc, MemLoc);
504 
505  if (isLoad) {
506  if (R == AliasResult::NoAlias)
507  continue;
508 
509  // Must aliased loads are defs of each other.
510  if (R == AliasResult::MustAlias)
511  return MemDepResult::getDef(Inst);
512 
513  // If we have a partial alias, then return this as a clobber for the
514  // client to handle.
515  if (R == AliasResult::PartialAlias && R.hasOffset()) {
516  ClobberOffsets[LI] = R.getOffset();
517  return MemDepResult::getClobber(Inst);
518  }
519 
520  // Random may-alias loads don't depend on each other without a
521  // dependence.
522  continue;
523  }
524 
525  // Stores don't depend on other no-aliased accesses.
526  if (R == AliasResult::NoAlias)
527  continue;
528 
529  // Stores don't alias loads from read-only memory.
530  if (BatchAA.pointsToConstantMemory(LoadLoc))
531  continue;
532 
533  // Stores depend on may/must aliased loads.
534  return MemDepResult::getDef(Inst);
535  }
536 
537  if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
538  // Atomic stores have complications involved.
539  // A Monotonic store is OK if the query inst is itself not atomic.
540  // FIXME: This is overly conservative.
541  if (!SI->isUnordered() && SI->isAtomic()) {
542  if (!QueryInst ||
543  isComplexForReordering(QueryInst, AtomicOrdering::Unordered))
545  // Ok, if we are here the guard above guarantee us that
546  // QueryInst is a non-atomic or unordered load/store.
547  // SI is atomic with monotonic or release semantic (seq_cst for store
548  // is actually a release semantic plus total order over other seq_cst
549  // instructions, as soon as QueryInst is not seq_cst we can consider it
550  // as simple release semantic).
551  // Monotonic and Release semantic allows re-ordering before store
552  // so we are safe to go further and check the aliasing. It will prohibit
553  // re-ordering in case locations are may or must alias.
554  }
555 
556  // While volatile access cannot be eliminated, they do not have to clobber
557  // non-aliasing locations, as normal accesses can for example be reordered
558  // with volatile accesses.
559  if (SI->isVolatile())
560  if (!QueryInst || QueryInst->isVolatile())
562 
563  // If alias analysis can tell that this store is guaranteed to not modify
564  // the query pointer, ignore it. Use getModRefInfo to handle cases where
565  // the query pointer points to constant memory etc.
566  if (!isModOrRefSet(BatchAA.getModRefInfo(SI, MemLoc)))
567  continue;
568 
569  // Ok, this store might clobber the query pointer. Check to see if it is
570  // a must alias: in this case, we want to return this as a def.
571  // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above.
573 
574  // If we found a pointer, check if it could be the same as our pointer.
575  AliasResult R = BatchAA.alias(StoreLoc, MemLoc);
576 
577  if (R == AliasResult::NoAlias)
578  continue;
579  if (R == AliasResult::MustAlias)
580  return MemDepResult::getDef(Inst);
581  if (isInvariantLoad)
582  continue;
583  return MemDepResult::getClobber(Inst);
584  }
585 
586  // If this is an allocation, and if we know that the accessed pointer is to
587  // the allocation, return Def. This means that there is no dependence and
588  // the access can be optimized based on that. For example, a load could
589  // turn into undef. Note that we can bypass the allocation itself when
590  // looking for a clobber in many cases; that's an alias property and is
591  // handled by BasicAA.
592  if (isa<AllocaInst>(Inst) || isNoAliasCall(Inst)) {
593  const Value *AccessPtr = getUnderlyingObject(MemLoc.Ptr);
594  if (AccessPtr == Inst || BatchAA.isMustAlias(Inst, AccessPtr))
595  return MemDepResult::getDef(Inst);
596  }
597 
598  if (isInvariantLoad)
599  continue;
600 
601  // A release fence requires that all stores complete before it, but does
602  // not prevent the reordering of following loads or stores 'before' the
603  // fence. As a result, we look past it when finding a dependency for
604  // loads. DSE uses this to find preceding stores to delete and thus we
605  // can't bypass the fence if the query instruction is a store.
606  if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
607  if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
608  continue;
609 
610  // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
611  ModRefInfo MR = BatchAA.getModRefInfo(Inst, MemLoc);
612  // If necessary, perform additional analysis.
613  if (isModAndRefSet(MR))
614  MR = BatchAA.callCapturesBefore(Inst, MemLoc, &DT);
615  switch (clearMust(MR)) {
617  // If the call has no effect on the queried pointer, just ignore it.
618  continue;
619  case ModRefInfo::Mod:
620  return MemDepResult::getClobber(Inst);
621  case ModRefInfo::Ref:
622  // If the call is known to never store to the pointer, and if this is a
623  // load query, we can safely ignore it (scan past it).
624  if (isLoad)
625  continue;
627  default:
628  // Otherwise, there is a potential dependence. Return a clobber.
629  return MemDepResult::getClobber(Inst);
630  }
631  }
632 
633  // No dependence found. If this is the entry block of the function, it is
634  // unknown, otherwise it is non-local.
635  if (BB != &BB->getParent()->getEntryBlock())
636  return MemDepResult::getNonLocal();
638 }
639 
641  ClobberOffsets.clear();
642  Instruction *ScanPos = QueryInst;
643 
644  // Check for a cached result
645  MemDepResult &LocalCache = LocalDeps[QueryInst];
646 
647  // If the cached entry is non-dirty, just return it. Note that this depends
648  // on MemDepResult's default constructing to 'dirty'.
649  if (!LocalCache.isDirty())
650  return LocalCache;
651 
652  // Otherwise, if we have a dirty entry, we know we can start the scan at that
653  // instruction, which may save us some work.
654  if (Instruction *Inst = LocalCache.getInst()) {
655  ScanPos = Inst;
656 
657  RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
658  }
659 
660  BasicBlock *QueryParent = QueryInst->getParent();
661 
662  // Do the scan.
663  if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
664  // No dependence found. If this is the entry block of the function, it is
665  // unknown, otherwise it is non-local.
666  if (QueryParent != &QueryParent->getParent()->getEntryBlock())
667  LocalCache = MemDepResult::getNonLocal();
668  else
669  LocalCache = MemDepResult::getNonFuncLocal();
670  } else {
671  MemoryLocation MemLoc;
672  ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI);
673  if (MemLoc.Ptr) {
674  // If we can do a pointer scan, make it happen.
675  bool isLoad = !isModSet(MR);
676  if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
677  isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
678 
679  LocalCache =
680  getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
681  QueryParent, QueryInst, nullptr);
682  } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
683  bool isReadOnly = AA.onlyReadsMemory(QueryCall);
684  LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
685  ScanPos->getIterator(), QueryParent);
686  } else
687  // Non-memory instruction.
688  LocalCache = MemDepResult::getUnknown();
689  }
690 
691  // Remember the result!
692  if (Instruction *I = LocalCache.getInst())
693  ReverseLocalDeps[I].insert(QueryInst);
694 
695  return LocalCache;
696 }
697 
698 #ifndef NDEBUG
699 /// This method is used when -debug is specified to verify that cache arrays
700 /// are properly kept sorted.
702  int Count = -1) {
703  if (Count == -1)
704  Count = Cache.size();
705  assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
706  "Cache isn't sorted!");
707 }
708 #endif
709 
712  assert(getDependency(QueryCall).isNonLocal() &&
713  "getNonLocalCallDependency should only be used on calls with "
714  "non-local deps!");
715  PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];
716  NonLocalDepInfo &Cache = CacheP.first;
717 
718  // This is the set of blocks that need to be recomputed. In the cached case,
719  // this can happen due to instructions being deleted etc. In the uncached
720  // case, this starts out as the set of predecessors we care about.
721  SmallVector<BasicBlock *, 32> DirtyBlocks;
722 
723  if (!Cache.empty()) {
724  // Okay, we have a cache entry. If we know it is not dirty, just return it
725  // with no computation.
726  if (!CacheP.second) {
727  ++NumCacheNonLocal;
728  return Cache;
729  }
730 
731  // If we already have a partially computed set of results, scan them to
732  // determine what is dirty, seeding our initial DirtyBlocks worklist.
733  for (auto &Entry : Cache)
734  if (Entry.getResult().isDirty())
735  DirtyBlocks.push_back(Entry.getBB());
736 
737  // Sort the cache so that we can do fast binary search lookups below.
738  llvm::sort(Cache);
739 
740  ++NumCacheDirtyNonLocal;
741  // cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
742  // << Cache.size() << " cached: " << *QueryInst;
743  } else {
744  // Seed DirtyBlocks with each of the preds of QueryInst's block.
745  BasicBlock *QueryBB = QueryCall->getParent();
746  append_range(DirtyBlocks, PredCache.get(QueryBB));
747  ++NumUncacheNonLocal;
748  }
749 
750  // isReadonlyCall - If this is a read-only call, we can be more aggressive.
751  bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
752 
754 
755  unsigned NumSortedEntries = Cache.size();
756  LLVM_DEBUG(AssertSorted(Cache));
757 
758  // Iterate while we still have blocks to update.
759  while (!DirtyBlocks.empty()) {
760  BasicBlock *DirtyBB = DirtyBlocks.pop_back_val();
761 
762  // Already processed this block?
763  if (!Visited.insert(DirtyBB).second)
764  continue;
765 
766  // Do a binary search to see if we already have an entry for this block in
767  // the cache set. If so, find it.
768  LLVM_DEBUG(AssertSorted(Cache, NumSortedEntries));
769  NonLocalDepInfo::iterator Entry =
770  std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
771  NonLocalDepEntry(DirtyBB));
772  if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
773  --Entry;
774 
775  NonLocalDepEntry *ExistingResult = nullptr;
776  if (Entry != Cache.begin() + NumSortedEntries &&
777  Entry->getBB() == DirtyBB) {
778  // If we already have an entry, and if it isn't already dirty, the block
779  // is done.
780  if (!Entry->getResult().isDirty())
781  continue;
782 
783  // Otherwise, remember this slot so we can update the value.
784  ExistingResult = &*Entry;
785  }
786 
787  // If the dirty entry has a pointer, start scanning from it so we don't have
788  // to rescan the entire block.
789  BasicBlock::iterator ScanPos = DirtyBB->end();
790  if (ExistingResult) {
791  if (Instruction *Inst = ExistingResult->getResult().getInst()) {
792  ScanPos = Inst->getIterator();
793  // We're removing QueryInst's use of Inst.
794  RemoveFromReverseMap<Instruction *>(ReverseNonLocalDeps, Inst,
795  QueryCall);
796  }
797  }
798 
799  // Find out if this block has a local dependency for QueryInst.
800  MemDepResult Dep;
801 
802  if (ScanPos != DirtyBB->begin()) {
803  Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
804  } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
805  // No dependence found. If this is the entry block of the function, it is
806  // a clobber, otherwise it is unknown.
808  } else {
810  }
811 
812  // If we had a dirty entry for the block, update it. Otherwise, just add
813  // a new entry.
814  if (ExistingResult)
815  ExistingResult->setResult(Dep);
816  else
817  Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
818 
819  // If the block has a dependency (i.e. it isn't completely transparent to
820  // the value), remember the association!
821  if (!Dep.isNonLocal()) {
822  // Keep the ReverseNonLocalDeps map up to date so we can efficiently
823  // update this when we remove instructions.
824  if (Instruction *Inst = Dep.getInst())
825  ReverseNonLocalDeps[Inst].insert(QueryCall);
826  } else {
827 
828  // If the block *is* completely transparent to the load, we need to check
829  // the predecessors of this block. Add them to our worklist.
830  append_range(DirtyBlocks, PredCache.get(DirtyBB));
831  }
832  }
833 
834  return Cache;
835 }
836 
838  Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
839  const MemoryLocation Loc = MemoryLocation::get(QueryInst);
840  bool isLoad = isa<LoadInst>(QueryInst);
841  BasicBlock *FromBB = QueryInst->getParent();
842  assert(FromBB);
843 
844  assert(Loc.Ptr->getType()->isPointerTy() &&
845  "Can't get pointer deps of a non-pointer!");
846  Result.clear();
847  {
848  // Check if there is cached Def with invariant.group.
849  auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
850  if (NonLocalDefIt != NonLocalDefsCache.end()) {
851  Result.push_back(NonLocalDefIt->second);
852  ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
853  .erase(QueryInst);
854  NonLocalDefsCache.erase(NonLocalDefIt);
855  return;
856  }
857  }
858  // This routine does not expect to deal with volatile instructions.
859  // Doing so would require piping through the QueryInst all the way through.
860  // TODO: volatiles can't be elided, but they can be reordered with other
861  // non-volatile accesses.
862 
863  // We currently give up on any instruction which is ordered, but we do handle
864  // atomic instructions which are unordered.
865  // TODO: Handle ordered instructions
866  auto isOrdered = [](Instruction *Inst) {
867  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
868  return !LI->isUnordered();
869  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
870  return !SI->isUnordered();
871  }
872  return false;
873  };
874  if (QueryInst->isVolatile() || isOrdered(QueryInst)) {
875  Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
876  const_cast<Value *>(Loc.Ptr)));
877  return;
878  }
879  const DataLayout &DL = FromBB->getModule()->getDataLayout();
880  PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, &AC);
881 
882  // This is the set of blocks we've inspected, and the pointer we consider in
883  // each block. Because of critical edges, we currently bail out if querying
884  // a block with multiple different pointers. This can happen during PHI
885  // translation.
887  if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
888  Result, Visited, true))
889  return;
890  Result.clear();
891  Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
892  const_cast<Value *>(Loc.Ptr)));
893 }
894 
895 /// Compute the memdep value for BB with Pointer/PointeeSize using either
896 /// cached information in Cache or by doing a lookup (which may use dirty cache
897 /// info if available).
898 ///
899 /// If we do a lookup, add the result to the cache.
900 MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
901  Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
902  BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries,
903  BatchAAResults &BatchAA) {
904 
905  bool isInvariantLoad = false;
906 
907  if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
908  isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
909 
910  // Do a binary search to see if we already have an entry for this block in
911  // the cache set. If so, find it.
912  NonLocalDepInfo::iterator Entry = std::upper_bound(
913  Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));
914  if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
915  --Entry;
916 
917  NonLocalDepEntry *ExistingResult = nullptr;
918  if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
919  ExistingResult = &*Entry;
920 
921  // Use cached result for invariant load only if there is no dependency for non
922  // invariant load. In this case invariant load can not have any dependency as
923  // well.
924  if (ExistingResult && isInvariantLoad &&
925  !ExistingResult->getResult().isNonFuncLocal())
926  ExistingResult = nullptr;
927 
928  // If we have a cached entry, and it is non-dirty, use it as the value for
929  // this dependency.
930  if (ExistingResult && !ExistingResult->getResult().isDirty()) {
931  ++NumCacheNonLocalPtr;
932  return ExistingResult->getResult();
933  }
934 
935  // Otherwise, we have to scan for the value. If we have a dirty cache
936  // entry, start scanning from its position, otherwise we scan from the end
937  // of the block.
938  BasicBlock::iterator ScanPos = BB->end();
939  if (ExistingResult && ExistingResult->getResult().getInst()) {
940  assert(ExistingResult->getResult().getInst()->getParent() == BB &&
941  "Instruction invalidated?");
942  ++NumCacheDirtyNonLocalPtr;
943  ScanPos = ExistingResult->getResult().getInst()->getIterator();
944 
945  // Eliminating the dirty entry from 'Cache', so update the reverse info.
946  ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
947  RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
948  } else {
949  ++NumUncacheNonLocalPtr;
950  }
951 
952  // Scan the block for the dependency.
953  MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB,
954  QueryInst, nullptr, BatchAA);
955 
956  // Don't cache results for invariant load.
957  if (isInvariantLoad)
958  return Dep;
959 
960  // If we had a dirty entry for the block, update it. Otherwise, just add
961  // a new entry.
962  if (ExistingResult)
963  ExistingResult->setResult(Dep);
964  else
965  Cache->push_back(NonLocalDepEntry(BB, Dep));
966 
967  // If the block has a dependency (i.e. it isn't completely transparent to
968  // the value), remember the reverse association because we just added it
969  // to Cache!
970  if (!Dep.isDef() && !Dep.isClobber())
971  return Dep;
972 
973  // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
974  // update MemDep when we remove instructions.
975  Instruction *Inst = Dep.getInst();
976  assert(Inst && "Didn't depend on anything?");
977  ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
978  ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
979  return Dep;
980 }
981 
982 /// Sort the NonLocalDepInfo cache, given a certain number of elements in the
983 /// array that are already properly ordered.
984 ///
985 /// This is optimized for the case when only a few entries are added.
986 static void
988  unsigned NumSortedEntries) {
989  switch (Cache.size() - NumSortedEntries) {
990  case 0:
991  // done, no new entries.
992  break;
993  case 2: {
994  // Two new entries, insert the last one into place.
995  NonLocalDepEntry Val = Cache.back();
996  Cache.pop_back();
997  MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
998  std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
999  Cache.insert(Entry, Val);
1001  }
1002  case 1:
1003  // One new entry, Just insert the new value at the appropriate position.
1004  if (Cache.size() != 1) {
1005  NonLocalDepEntry Val = Cache.back();
1006  Cache.pop_back();
1007  MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1008  llvm::upper_bound(Cache, Val);
1009  Cache.insert(Entry, Val);
1010  }
1011  break;
1012  default:
1013  // Added many values, do a full scale sort.
1014  llvm::sort(Cache);
1015  break;
1016  }
1017 }
1018 
1019 /// Perform a dependency query based on pointer/pointeesize starting at the end
1020 /// of StartBB.
1021 ///
1022 /// Add any clobber/def results to the results vector and keep track of which
1023 /// blocks are visited in 'Visited'.
1024 ///
1025 /// This has special behavior for the first block queries (when SkipFirstBlock
1026 /// is true). In this special case, it ignores the contents of the specified
1027 /// block and starts returning dependence info for its predecessors.
1028 ///
1029 /// This function returns true on success, or false to indicate that it could
1030 /// not compute dependence information for some reason. This should be treated
1031 /// as a clobber dependence on the first instruction in the predecessor block.
1032 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1033  Instruction *QueryInst, const PHITransAddr &Pointer,
1034  const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
1036  DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
1037  bool IsIncomplete) {
1038  // Look up the cached info for Pointer.
1039  ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
1040 
1041  // Set up a temporary NLPI value. If the map doesn't yet have an entry for
1042  // CacheKey, this value will be inserted as the associated value. Otherwise,
1043  // it'll be ignored, and we'll have to check to see if the cached size and
1044  // aa tags are consistent with the current query.
1045  NonLocalPointerInfo InitialNLPI;
1046  InitialNLPI.Size = Loc.Size;
1047  InitialNLPI.AATags = Loc.AATags;
1048 
1049  bool isInvariantLoad = false;
1050  if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
1051  isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
1052 
1053  // Get the NLPI for CacheKey, inserting one into the map if it doesn't
1054  // already have one.
1055  std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1056  NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1057  NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1058 
1059  // If we already have a cache entry for this CacheKey, we may need to do some
1060  // work to reconcile the cache entry and the current query.
1061  // Invariant loads don't participate in caching. Thus no need to reconcile.
1062  if (!isInvariantLoad && !Pair.second) {
1063  if (CacheInfo->Size != Loc.Size) {
1064  bool ThrowOutEverything;
1065  if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) {
1066  // FIXME: We may be able to do better in the face of results with mixed
1067  // precision. We don't appear to get them in practice, though, so just
1068  // be conservative.
1069  ThrowOutEverything =
1070  CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() ||
1071  CacheInfo->Size.getValue() < Loc.Size.getValue();
1072  } else {
1073  // For our purposes, unknown size > all others.
1074  ThrowOutEverything = !Loc.Size.hasValue();
1075  }
1076 
1077  if (ThrowOutEverything) {
1078  // The query's Size is greater than the cached one. Throw out the
1079  // cached data and proceed with the query at the greater size.
1080  CacheInfo->Pair = BBSkipFirstBlockPair();
1081  CacheInfo->Size = Loc.Size;
1082  for (auto &Entry : CacheInfo->NonLocalDeps)
1083  if (Instruction *Inst = Entry.getResult().getInst())
1084  RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1085  CacheInfo->NonLocalDeps.clear();
1086  // The cache is cleared (in the above line) so we will have lost
1087  // information about blocks we have already visited. We therefore must
1088  // assume that the cache information is incomplete.
1089  IsIncomplete = true;
1090  } else {
1091  // This query's Size is less than the cached one. Conservatively restart
1092  // the query using the greater size.
1093  return getNonLocalPointerDepFromBB(
1094  QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
1095  StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
1096  }
1097  }
1098 
1099  // If the query's AATags are inconsistent with the cached one,
1100  // conservatively throw out the cached data and restart the query with
1101  // no tag if needed.
1102  if (CacheInfo->AATags != Loc.AATags) {
1103  if (CacheInfo->AATags) {
1104  CacheInfo->Pair = BBSkipFirstBlockPair();
1105  CacheInfo->AATags = AAMDNodes();
1106  for (auto &Entry : CacheInfo->NonLocalDeps)
1107  if (Instruction *Inst = Entry.getResult().getInst())
1108  RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1109  CacheInfo->NonLocalDeps.clear();
1110  // The cache is cleared (in the above line) so we will have lost
1111  // information about blocks we have already visited. We therefore must
1112  // assume that the cache information is incomplete.
1113  IsIncomplete = true;
1114  }
1115  if (Loc.AATags)
1116  return getNonLocalPointerDepFromBB(
1117  QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
1118  Visited, SkipFirstBlock, IsIncomplete);
1119  }
1120  }
1121 
1122  NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1123 
1124  // If we have valid cached information for exactly the block we are
1125  // investigating, just return it with no recomputation.
1126  // Don't use cached information for invariant loads since it is valid for
1127  // non-invariant loads only.
1128  if (!IsIncomplete && !isInvariantLoad &&
1129  CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1130  // We have a fully cached result for this query then we can just return the
1131  // cached results and populate the visited set. However, we have to verify
1132  // that we don't already have conflicting results for these blocks. Check
1133  // to ensure that if a block in the results set is in the visited set that
1134  // it was for the same pointer query.
1135  if (!Visited.empty()) {
1136  for (auto &Entry : *Cache) {
1138  Visited.find(Entry.getBB());
1139  if (VI == Visited.end() || VI->second == Pointer.getAddr())
1140  continue;
1141 
1142  // We have a pointer mismatch in a block. Just return false, saying
1143  // that something was clobbered in this result. We could also do a
1144  // non-fully cached query, but there is little point in doing this.
1145  return false;
1146  }
1147  }
1148 
1149  Value *Addr = Pointer.getAddr();
1150  for (auto &Entry : *Cache) {
1151  Visited.insert(std::make_pair(Entry.getBB(), Addr));
1152  if (Entry.getResult().isNonLocal()) {
1153  continue;
1154  }
1155 
1156  if (DT.isReachableFromEntry(Entry.getBB())) {
1157  Result.push_back(
1158  NonLocalDepResult(Entry.getBB(), Entry.getResult(), Addr));
1159  }
1160  }
1161  ++NumCacheCompleteNonLocalPtr;
1162  return true;
1163  }
1164 
1165  // Otherwise, either this is a new block, a block with an invalid cache
1166  // pointer or one that we're about to invalidate by putting more info into
1167  // it than its valid cache info. If empty and not explicitly indicated as
1168  // incomplete, the result will be valid cache info, otherwise it isn't.
1169  //
1170  // Invariant loads don't affect cache in any way thus no need to update
1171  // CacheInfo as well.
1172  if (!isInvariantLoad) {
1173  if (!IsIncomplete && Cache->empty())
1174  CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1175  else
1176  CacheInfo->Pair = BBSkipFirstBlockPair();
1177  }
1178 
1180  Worklist.push_back(StartBB);
1181 
1182  // PredList used inside loop.
1184 
1185  // Keep track of the entries that we know are sorted. Previously cached
1186  // entries will all be sorted. The entries we add we only sort on demand (we
1187  // don't insert every element into its sorted position). We know that we
1188  // won't get any reuse from currently inserted values, because we don't
1189  // revisit blocks after we insert info for them.
1190  unsigned NumSortedEntries = Cache->size();
1191  unsigned WorklistEntries = BlockNumberLimit;
1192  bool GotWorklistLimit = false;
1193  LLVM_DEBUG(AssertSorted(*Cache));
1194 
1195  BatchAAResults BatchAA(AA);
1196  while (!Worklist.empty()) {
1197  BasicBlock *BB = Worklist.pop_back_val();
1198 
1199  // If we do process a large number of blocks it becomes very expensive and
1200  // likely it isn't worth worrying about
1201  if (Result.size() > NumResultsLimit) {
1202  Worklist.clear();
1203  // Sort it now (if needed) so that recursive invocations of
1204  // getNonLocalPointerDepFromBB and other routines that could reuse the
1205  // cache value will only see properly sorted cache arrays.
1206  if (Cache && NumSortedEntries != Cache->size()) {
1207  SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1208  }
1209  // Since we bail out, the "Cache" set won't contain all of the
1210  // results for the query. This is ok (we can still use it to accelerate
1211  // specific block queries) but we can't do the fastpath "return all
1212  // results from the set". Clear out the indicator for this.
1213  CacheInfo->Pair = BBSkipFirstBlockPair();
1214  return false;
1215  }
1216 
1217  // Skip the first block if we have it.
1218  if (!SkipFirstBlock) {
1219  // Analyze the dependency of *Pointer in FromBB. See if we already have
1220  // been here.
1221  assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
1222 
1223  // Get the dependency info for Pointer in BB. If we have cached
1224  // information, we will use it, otherwise we compute it.
1225  LLVM_DEBUG(AssertSorted(*Cache, NumSortedEntries));
1226  MemDepResult Dep = getNonLocalInfoForBlock(
1227  QueryInst, Loc, isLoad, BB, Cache, NumSortedEntries, BatchAA);
1228 
1229  // If we got a Def or Clobber, add this to the list of results.
1230  if (!Dep.isNonLocal()) {
1231  if (DT.isReachableFromEntry(BB)) {
1232  Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1233  continue;
1234  }
1235  }
1236  }
1237 
1238  // If 'Pointer' is an instruction defined in this block, then we need to do
1239  // phi translation to change it into a value live in the predecessor block.
1240  // If not, we just add the predecessors to the worklist and scan them with
1241  // the same Pointer.
1242  if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1243  SkipFirstBlock = false;
1245  for (BasicBlock *Pred : PredCache.get(BB)) {
1246  // Verify that we haven't looked at this block yet.
1247  std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1248  Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
1249  if (InsertRes.second) {
1250  // First time we've looked at *PI.
1251  NewBlocks.push_back(Pred);
1252  continue;
1253  }
1254 
1255  // If we have seen this block before, but it was with a different
1256  // pointer then we have a phi translation failure and we have to treat
1257  // this as a clobber.
1258  if (InsertRes.first->second != Pointer.getAddr()) {
1259  // Make sure to clean up the Visited map before continuing on to
1260  // PredTranslationFailure.
1261  for (unsigned i = 0; i < NewBlocks.size(); i++)
1262  Visited.erase(NewBlocks[i]);
1263  goto PredTranslationFailure;
1264  }
1265  }
1266  if (NewBlocks.size() > WorklistEntries) {
1267  // Make sure to clean up the Visited map before continuing on to
1268  // PredTranslationFailure.
1269  for (unsigned i = 0; i < NewBlocks.size(); i++)
1270  Visited.erase(NewBlocks[i]);
1271  GotWorklistLimit = true;
1272  goto PredTranslationFailure;
1273  }
1274  WorklistEntries -= NewBlocks.size();
1275  Worklist.append(NewBlocks.begin(), NewBlocks.end());
1276  continue;
1277  }
1278 
1279  // We do need to do phi translation, if we know ahead of time we can't phi
1280  // translate this value, don't even try.
1281  if (!Pointer.IsPotentiallyPHITranslatable())
1282  goto PredTranslationFailure;
1283 
1284  // We may have added values to the cache list before this PHI translation.
1285  // If so, we haven't done anything to ensure that the cache remains sorted.
1286  // Sort it now (if needed) so that recursive invocations of
1287  // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1288  // value will only see properly sorted cache arrays.
1289  if (Cache && NumSortedEntries != Cache->size()) {
1290  SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1291  NumSortedEntries = Cache->size();
1292  }
1293  Cache = nullptr;
1294 
1295  PredList.clear();
1296  for (BasicBlock *Pred : PredCache.get(BB)) {
1297  PredList.push_back(std::make_pair(Pred, Pointer));
1298 
1299  // Get the PHI translated pointer in this predecessor. This can fail if
1300  // not translatable, in which case the getAddr() returns null.
1301  PHITransAddr &PredPointer = PredList.back().second;
1302  PredPointer.PHITranslateValue(BB, Pred, &DT, /*MustDominate=*/false);
1303  Value *PredPtrVal = PredPointer.getAddr();
1304 
1305  // Check to see if we have already visited this pred block with another
1306  // pointer. If so, we can't do this lookup. This failure can occur
1307  // with PHI translation when a critical edge exists and the PHI node in
1308  // the successor translates to a pointer value different than the
1309  // pointer the block was first analyzed with.
1310  std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1311  Visited.insert(std::make_pair(Pred, PredPtrVal));
1312 
1313  if (!InsertRes.second) {
1314  // We found the pred; take it off the list of preds to visit.
1315  PredList.pop_back();
1316 
1317  // If the predecessor was visited with PredPtr, then we already did
1318  // the analysis and can ignore it.
1319  if (InsertRes.first->second == PredPtrVal)
1320  continue;
1321 
1322  // Otherwise, the block was previously analyzed with a different
1323  // pointer. We can't represent the result of this case, so we just
1324  // treat this as a phi translation failure.
1325 
1326  // Make sure to clean up the Visited map before continuing on to
1327  // PredTranslationFailure.
1328  for (unsigned i = 0, n = PredList.size(); i < n; ++i)
1329  Visited.erase(PredList[i].first);
1330 
1331  goto PredTranslationFailure;
1332  }
1333  }
1334 
1335  // Actually process results here; this need to be a separate loop to avoid
1336  // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1337  // any results for. (getNonLocalPointerDepFromBB will modify our
1338  // datastructures in ways the code after the PredTranslationFailure label
1339  // doesn't expect.)
1340  for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
1341  BasicBlock *Pred = PredList[i].first;
1342  PHITransAddr &PredPointer = PredList[i].second;
1343  Value *PredPtrVal = PredPointer.getAddr();
1344 
1345  bool CanTranslate = true;
1346  // If PHI translation was unable to find an available pointer in this
1347  // predecessor, then we have to assume that the pointer is clobbered in
1348  // that predecessor. We can still do PRE of the load, which would insert
1349  // a computation of the pointer in this predecessor.
1350  if (!PredPtrVal)
1351  CanTranslate = false;
1352 
1353  // FIXME: it is entirely possible that PHI translating will end up with
1354  // the same value. Consider PHI translating something like:
1355  // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need*
1356  // to recurse here, pedantically speaking.
1357 
1358  // If getNonLocalPointerDepFromBB fails here, that means the cached
1359  // result conflicted with the Visited list; we have to conservatively
1360  // assume it is unknown, but this also does not block PRE of the load.
1361  if (!CanTranslate ||
1362  !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1363  Loc.getWithNewPtr(PredPtrVal), isLoad,
1364  Pred, Result, Visited)) {
1365  // Add the entry to the Result list.
1366  NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1367  Result.push_back(Entry);
1368 
1369  // Since we had a phi translation failure, the cache for CacheKey won't
1370  // include all of the entries that we need to immediately satisfy future
1371  // queries. Mark this in NonLocalPointerDeps by setting the
1372  // BBSkipFirstBlockPair pointer to null. This requires reuse of the
1373  // cached value to do more work but not miss the phi trans failure.
1374  NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1375  NLPI.Pair = BBSkipFirstBlockPair();
1376  continue;
1377  }
1378  }
1379 
1380  // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1381  CacheInfo = &NonLocalPointerDeps[CacheKey];
1382  Cache = &CacheInfo->NonLocalDeps;
1383  NumSortedEntries = Cache->size();
1384 
1385  // Since we did phi translation, the "Cache" set won't contain all of the
1386  // results for the query. This is ok (we can still use it to accelerate
1387  // specific block queries) but we can't do the fastpath "return all
1388  // results from the set" Clear out the indicator for this.
1389  CacheInfo->Pair = BBSkipFirstBlockPair();
1390  SkipFirstBlock = false;
1391  continue;
1392 
1393  PredTranslationFailure:
1394  // The following code is "failure"; we can't produce a sane translation
1395  // for the given block. It assumes that we haven't modified any of
1396  // our datastructures while processing the current block.
1397 
1398  if (!Cache) {
1399  // Refresh the CacheInfo/Cache pointer if it got invalidated.
1400  CacheInfo = &NonLocalPointerDeps[CacheKey];
1401  Cache = &CacheInfo->NonLocalDeps;
1402  NumSortedEntries = Cache->size();
1403  }
1404 
1405  // Since we failed phi translation, the "Cache" set won't contain all of the
1406  // results for the query. This is ok (we can still use it to accelerate
1407  // specific block queries) but we can't do the fastpath "return all
1408  // results from the set". Clear out the indicator for this.
1409  CacheInfo->Pair = BBSkipFirstBlockPair();
1410 
1411  // If *nothing* works, mark the pointer as unknown.
1412  //
1413  // If this is the magic first block, return this as a clobber of the whole
1414  // incoming value. Since we can't phi translate to one of the predecessors,
1415  // we have to bail out.
1416  if (SkipFirstBlock)
1417  return false;
1418 
1419  // Results of invariant loads are not cached thus no need to update cached
1420  // information.
1421  if (!isInvariantLoad) {
1422  for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
1423  if (I.getBB() != BB)
1424  continue;
1425 
1426  assert((GotWorklistLimit || I.getResult().isNonLocal() ||
1427  !DT.isReachableFromEntry(BB)) &&
1428  "Should only be here with transparent block");
1429 
1430  I.setResult(MemDepResult::getUnknown());
1431 
1432 
1433  break;
1434  }
1435  }
1436  (void)GotWorklistLimit;
1437  // Go ahead and report unknown dependence.
1438  Result.push_back(
1440  }
1441 
1442  // Okay, we're done now. If we added new values to the cache, re-sort it.
1443  SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1444  LLVM_DEBUG(AssertSorted(*Cache));
1445  return true;
1446 }
1447 
1448 /// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
1449 void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
1450  ValueIsLoadPair P) {
1451 
1452  // Most of the time this cache is empty.
1453  if (!NonLocalDefsCache.empty()) {
1454  auto it = NonLocalDefsCache.find(P.getPointer());
1455  if (it != NonLocalDefsCache.end()) {
1456  RemoveFromReverseMap(ReverseNonLocalDefsCache,
1457  it->second.getResult().getInst(), P.getPointer());
1458  NonLocalDefsCache.erase(it);
1459  }
1460 
1461  if (auto *I = dyn_cast<Instruction>(P.getPointer())) {
1462  auto toRemoveIt = ReverseNonLocalDefsCache.find(I);
1463  if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1464  for (const auto *entry : toRemoveIt->second)
1465  NonLocalDefsCache.erase(entry);
1466  ReverseNonLocalDefsCache.erase(toRemoveIt);
1467  }
1468  }
1469  }
1470 
1471  CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P);
1472  if (It == NonLocalPointerDeps.end())
1473  return;
1474 
1475  // Remove all of the entries in the BB->val map. This involves removing
1476  // instructions from the reverse map.
1477  NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1478 
1479  for (const NonLocalDepEntry &DE : PInfo) {
1480  Instruction *Target = DE.getResult().getInst();
1481  if (!Target)
1482  continue; // Ignore non-local dep results.
1483  assert(Target->getParent() == DE.getBB());
1484 
1485  // Eliminating the dirty entry from 'Cache', so update the reverse info.
1486  RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1487  }
1488 
1489  // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1490  NonLocalPointerDeps.erase(It);
1491 }
1492 
1494  // If Ptr isn't really a pointer, just ignore it.
1495  if (!Ptr->getType()->isPointerTy())
1496  return;
1497  // Flush store info for the pointer.
1498  removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1499  // Flush load info for the pointer.
1500  removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1501  // Invalidate phis that use the pointer.
1502  PV.invalidateValue(Ptr);
1503 }
1504 
1506  PredCache.clear();
1507 }
1508 
1510  // Walk through the Non-local dependencies, removing this one as the value
1511  // for any cached queries.
1512  NonLocalDepMapType::iterator NLDI = NonLocalDepsMap.find(RemInst);
1513  if (NLDI != NonLocalDepsMap.end()) {
1514  NonLocalDepInfo &BlockMap = NLDI->second.first;
1515  for (auto &Entry : BlockMap)
1516  if (Instruction *Inst = Entry.getResult().getInst())
1517  RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1518  NonLocalDepsMap.erase(NLDI);
1519  }
1520 
1521  // If we have a cached local dependence query for this instruction, remove it.
1522  LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1523  if (LocalDepEntry != LocalDeps.end()) {
1524  // Remove us from DepInst's reverse set now that the local dep info is gone.
1525  if (Instruction *Inst = LocalDepEntry->second.getInst())
1526  RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1527 
1528  // Remove this local dependency info.
1529  LocalDeps.erase(LocalDepEntry);
1530  }
1531 
1532  // If we have any cached dependencies on this instruction, remove
1533  // them.
1534 
1535  // If the instruction is a pointer, remove it from both the load info and the
1536  // store info.
1537  if (RemInst->getType()->isPointerTy()) {
1538  removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1539  removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1540  } else {
1541  // Otherwise, if the instructions is in the map directly, it must be a load.
1542  // Remove it.
1543  auto toRemoveIt = NonLocalDefsCache.find(RemInst);
1544  if (toRemoveIt != NonLocalDefsCache.end()) {
1545  assert(isa<LoadInst>(RemInst) &&
1546  "only load instructions should be added directly");
1547  const Instruction *DepV = toRemoveIt->second.getResult().getInst();
1548  ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);
1549  NonLocalDefsCache.erase(toRemoveIt);
1550  }
1551  }
1552 
1553  // Loop over all of the things that depend on the instruction we're removing.
1555 
1556  // If we find RemInst as a clobber or Def in any of the maps for other values,
1557  // we need to replace its entry with a dirty version of the instruction after
1558  // it. If RemInst is a terminator, we use a null dirty value.
1559  //
1560  // Using a dirty version of the instruction after RemInst saves having to scan
1561  // the entire block to get to this point.
1562  MemDepResult NewDirtyVal;
1563  if (!RemInst->isTerminator())
1564  NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator());
1565 
1566  ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1567  if (ReverseDepIt != ReverseLocalDeps.end()) {
1568  // RemInst can't be the terminator if it has local stuff depending on it.
1569  assert(!ReverseDepIt->second.empty() && !RemInst->isTerminator() &&
1570  "Nothing can locally depend on a terminator");
1571 
1572  for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1573  assert(InstDependingOnRemInst != RemInst &&
1574  "Already removed our local dep info");
1575 
1576  LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1577 
1578  // Make sure to remember that new things depend on NewDepInst.
1579  assert(NewDirtyVal.getInst() &&
1580  "There is no way something else can have "
1581  "a local dep on this if it is a terminator!");
1582  ReverseDepsToAdd.push_back(
1583  std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));
1584  }
1585 
1586  ReverseLocalDeps.erase(ReverseDepIt);
1587 
1588  // Add new reverse deps after scanning the set, to avoid invalidating the
1589  // 'ReverseDeps' reference.
1590  while (!ReverseDepsToAdd.empty()) {
1591  ReverseLocalDeps[ReverseDepsToAdd.back().first].insert(
1592  ReverseDepsToAdd.back().second);
1593  ReverseDepsToAdd.pop_back();
1594  }
1595  }
1596 
1597  ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1598  if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1599  for (Instruction *I : ReverseDepIt->second) {
1600  assert(I != RemInst && "Already removed NonLocalDep info for RemInst");
1601 
1602  PerInstNLInfo &INLD = NonLocalDepsMap[I];
1603  // The information is now dirty!
1604  INLD.second = true;
1605 
1606  for (auto &Entry : INLD.first) {
1607  if (Entry.getResult().getInst() != RemInst)
1608  continue;
1609 
1610  // Convert to a dirty entry for the subsequent instruction.
1611  Entry.setResult(NewDirtyVal);
1612 
1613  if (Instruction *NextI = NewDirtyVal.getInst())
1614  ReverseDepsToAdd.push_back(std::make_pair(NextI, I));
1615  }
1616  }
1617 
1618  ReverseNonLocalDeps.erase(ReverseDepIt);
1619 
1620  // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1621  while (!ReverseDepsToAdd.empty()) {
1622  ReverseNonLocalDeps[ReverseDepsToAdd.back().first].insert(
1623  ReverseDepsToAdd.back().second);
1624  ReverseDepsToAdd.pop_back();
1625  }
1626  }
1627 
1628  // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1629  // value in the NonLocalPointerDeps info.
1630  ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1631  ReverseNonLocalPtrDeps.find(RemInst);
1632  if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1634  ReversePtrDepsToAdd;
1635 
1636  for (ValueIsLoadPair P : ReversePtrDepIt->second) {
1637  assert(P.getPointer() != RemInst &&
1638  "Already removed NonLocalPointerDeps info for RemInst");
1639 
1640  NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1641 
1642  // The cache is not valid for any specific block anymore.
1643  NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1644 
1645  // Update any entries for RemInst to use the instruction after it.
1646  for (auto &Entry : NLPDI) {
1647  if (Entry.getResult().getInst() != RemInst)
1648  continue;
1649 
1650  // Convert to a dirty entry for the subsequent instruction.
1651  Entry.setResult(NewDirtyVal);
1652 
1653  if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1654  ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1655  }
1656 
1657  // Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1658  // subsequent value may invalidate the sortedness.
1659  llvm::sort(NLPDI);
1660  }
1661 
1662  ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1663 
1664  while (!ReversePtrDepsToAdd.empty()) {
1665  ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
1666  ReversePtrDepsToAdd.back().second);
1667  ReversePtrDepsToAdd.pop_back();
1668  }
1669  }
1670 
1671  // Invalidate phis that use the removed instruction.
1672  PV.invalidateValue(RemInst);
1673 
1674  assert(!NonLocalDepsMap.count(RemInst) && "RemInst got reinserted?");
1675  LLVM_DEBUG(verifyRemoved(RemInst));
1676 }
1677 
1678 /// Verify that the specified instruction does not occur in our internal data
1679 /// structures.
1680 ///
1681 /// This function verifies by asserting in debug builds.
1682 void MemoryDependenceResults::verifyRemoved(Instruction *D) const {
1683 #ifndef NDEBUG
1684  for (const auto &DepKV : LocalDeps) {
1685  assert(DepKV.first != D && "Inst occurs in data structures");
1686  assert(DepKV.second.getInst() != D && "Inst occurs in data structures");
1687  }
1688 
1689  for (const auto &DepKV : NonLocalPointerDeps) {
1690  assert(DepKV.first.getPointer() != D && "Inst occurs in NLPD map key");
1691  for (const auto &Entry : DepKV.second.NonLocalDeps)
1692  assert(Entry.getResult().getInst() != D && "Inst occurs as NLPD value");
1693  }
1694 
1695  for (const auto &DepKV : NonLocalDepsMap) {
1696  assert(DepKV.first != D && "Inst occurs in data structures");
1697  const PerInstNLInfo &INLD = DepKV.second;
1698  for (const auto &Entry : INLD.first)
1699  assert(Entry.getResult().getInst() != D &&
1700  "Inst occurs in data structures");
1701  }
1702 
1703  for (const auto &DepKV : ReverseLocalDeps) {
1704  assert(DepKV.first != D && "Inst occurs in data structures");
1705  for (Instruction *Inst : DepKV.second)
1706  assert(Inst != D && "Inst occurs in data structures");
1707  }
1708 
1709  for (const auto &DepKV : ReverseNonLocalDeps) {
1710  assert(DepKV.first != D && "Inst occurs in data structures");
1711  for (Instruction *Inst : DepKV.second)
1712  assert(Inst != D && "Inst occurs in data structures");
1713  }
1714 
1715  for (const auto &DepKV : ReverseNonLocalPtrDeps) {
1716  assert(DepKV.first != D && "Inst occurs in rev NLPD map");
1717 
1718  for (ValueIsLoadPair P : DepKV.second)
1719  assert(P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) &&
1720  "Inst occurs in ReverseNonLocalPtrDeps map");
1721  }
1722 #endif
1723 }
1724 
1725 AnalysisKey MemoryDependenceAnalysis::Key;
1726 
1728  : DefaultBlockScanLimit(BlockScanLimit) {}
1729 
1732  auto &AA = AM.getResult<AAManager>(F);
1733  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1734  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1735  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1736  auto &PV = AM.getResult<PhiValuesAnalysis>(F);
1737  return MemoryDependenceResults(AA, AC, TLI, DT, PV, DefaultBlockScanLimit);
1738 }
1739 
1741 
1743  "Memory Dependence Analysis", false, true)
1750  "Memory Dependence Analysis", false, true)
1751 
1754 }
1755 
1757 
1759  MemDep.reset();
1760 }
1761 
1763  AU.setPreservesAll();
1769 }
1770 
1773  // Check whether our analysis is preserved.
1774  auto PAC = PA.getChecker<MemoryDependenceAnalysis>();
1775  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
1776  // If not, give up now.
1777  return true;
1778 
1779  // Check whether the analyses we depend on became invalid for any reason.
1780  if (Inv.invalidate<AAManager>(F, PA) ||
1781  Inv.invalidate<AssumptionAnalysis>(F, PA) ||
1782  Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
1783  Inv.invalidate<PhiValuesAnalysis>(F, PA))
1784  return true;
1785 
1786  // Otherwise this analysis result remains valid.
1787  return false;
1788 }
1789 
1791  return DefaultBlockScanLimit;
1792 }
1793 
1795  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1796  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1797  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1798  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1799  auto &PV = getAnalysis<PhiValuesWrapperPass>().getResult();
1800  MemDep.emplace(AA, AC, TLI, DT, PV, BlockScanLimit);
1801  return false;
1802 }
isOrdered
static bool isOrdered(const Instruction *I)
Definition: MemorySSA.cpp:1763
i
i
Definition: README.txt:29
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:1509
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::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
llvm::ModRefInfo::NoModRef
@ NoModRef
The access neither references nor modifies the value stored in memory.
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1299
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:299
llvm::AliasResult::PartialAlias
@ PartialAlias
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:104
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
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
memdep
memdep
Definition: MemoryDependenceAnalysis.cpp:1749
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1739
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1832
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::isModAndRefSet
LLVM_NODISCARD bool isModAndRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:192
Metadata.h
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::isModOrRefSet
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:189
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:218
AtomicOrdering.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
llvm::Function
Definition: Function.h:60
llvm::AnalysisManager::Invalidator::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:685
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
Pass.h
llvm::Instruction::isVolatile
bool isVolatile() const
Return true if this instruction has a volatile memory access.
Definition: Instruction.cpp:655
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:140
llvm::MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass
~MemoryDependenceWrapperPass() override
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::MemoryDependenceWrapperPass::runOnFunction
bool runOnFunction(Function &) override
Pass Implementation stuff. This doesn't do any analysis eagerly.
Definition: MemoryDependenceAnalysis.cpp:1794
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:709
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::MemoryLocation::getWithNewSize
MemoryLocation getWithNewSize(LocationSize NewSize) const
Definition: MemoryLocation.h:300
llvm::MemoryDependenceResults::invalidateCachedPredecessors
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
Definition: MemoryDependenceAnalysis.cpp:1505
ValueTracking.h
llvm::Dependence
Dependence - This class represents a dependence between two memory memory references in a function.
Definition: DependenceAnalysis.h:71
llvm::NonLocalDepEntry::getResult
const MemDepResult & getResult() const
Definition: MemoryDependenceAnalysis.h:215
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::PhiValuesWrapperPass
Wrapper pass for the legacy pass manager.
Definition: PhiValues.h:138
llvm::BatchAAResults::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Definition: AliasAnalysis.h:963
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:227
DenseMap.h
Module.h
MemoryBuiltins.h
BlockScanLimit
static cl::opt< unsigned > BlockScanLimit("memdep-block-scan-limit", cl::Hidden, cl::init(100), cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)"))
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:445
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::MemDepResult
A memory dependence query can return one of three different answers.
Definition: MemoryDependenceAnalysis.h:38
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
MemoryDependenceAnalysis.h
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:268
llvm::LocationSize::isPrecise
bool isPrecise() const
Definition: MemoryLocation.h:166
llvm::codeview::PointerMode::Pointer
@ Pointer
llvm::BatchAAResults::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
Definition: AliasAnalysis.h:966
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::AtomicOrdering::Monotonic
@ Monotonic
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
PHITransAddr.h
Instruction.h
CommandLine.h
llvm::MemoryLocation::AATags
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
Definition: MemoryLocation.h:231
llvm::MemoryDependenceAnalysis::run
MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)
Definition: MemoryDependenceAnalysis.cpp:1731
llvm::isNoAliasCall
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
Definition: AliasAnalysis.cpp:962
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
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:1493
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:159
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
TargetLibraryInfo.h
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
false
Definition: StackSlotColoring.cpp:141
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::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4362
SmallPtrSet.h
llvm::MemoryDependenceResults::getDefaultBlockScanLimit
unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
Definition: MemoryDependenceAnalysis.cpp:1790
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:147
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::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep", "Memory Dependence Analysis", false, true) INITIALIZE_PASS_END(MemoryDependenceWrapperPass
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:596
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
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::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
AssertSorted
static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache, int Count=-1)
This method is used when -debug is specified to verify that cache arrays are properly kept sorted.
Definition: MemoryDependenceAnalysis.cpp:701
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::clearMust
LLVM_NODISCARD ModRefInfo clearMust(const ModRefInfo MRI)
Definition: AliasAnalysis.h:228
llvm::AtomicOrdering
AtomicOrdering
Atomic ordering for LLVM's memory model.
Definition: AtomicOrdering.h:56
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::MemDepResult::getInst
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
Definition: MemoryDependenceAnalysis.h:166
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
llvm::isNoModRef
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:185
llvm::isStrongerThanUnordered
bool isStrongerThanUnordered(AtomicOrdering AO)
Definition: AtomicOrdering.h:120
VI
@ VI
Definition: SIInstrInfo.cpp:7842
llvm::BatchAAResults::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Definition: AliasAnalysis.h:960
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:112
llvm::getPointerOperand
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Definition: Instructions.h:5344
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:156
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
NumResultsLimit
static const unsigned int NumResultsLimit
Definition: MemoryDependenceAnalysis.cpp:85
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
Definition: DenseMap.h:716
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::initializeMemoryDependenceWrapperPassPass
void initializeMemoryDependenceWrapperPassPass(PassRegistry &)
llvm::AtomicOrdering::Unordered
@ Unordered
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:711
BlockNumberLimit
static cl::opt< unsigned > BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 1000)"))
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::PhiValuesAnalysis
The analysis pass which yields a PhiValues.
Definition: PhiValues.h:115
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Instruction::hasMetadata
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:261
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
Definition: MemoryLocation.cpp:158
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::PHITransAddr::PHITranslateValue
bool PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
PHITranslateValue - PHI translate the current address up the CFG from CurBB to Pred,...
Definition: PHITransAddr.cpp:313
llvm::MemoryDependenceWrapperPass::releaseMemory
void releaseMemory() override
Clean up memory in between runs.
Definition: MemoryDependenceAnalysis.cpp:1758
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::sys::Memory
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
isLoad
static bool isLoad(int Opcode)
Definition: ARCInstrInfo.cpp:53
llvm::MemoryDependenceResults::getDependency
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
Definition: MemoryDependenceAnalysis.cpp:640
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1813
llvm::ModRefInfo::Mod
@ Mod
The access may modify the value stored in memory.
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:576
llvm::MemDepResult::getClobber
static MemDepResult getClobber(Instruction *Inst)
Definition: MemoryDependenceAnalysis.h:124
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:280
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:176
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
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::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:682
llvm::MemDepResult::getNonFuncLocal
static MemDepResult getNonFuncLocal()
Definition: MemoryDependenceAnalysis.h:131
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:98
llvm::MemoryDependenceResults::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation in the new PM.
Definition: MemoryDependenceAnalysis.cpp:1771
llvm::AtomicOrdering::Release
@ Release
PhiValues.h
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:265
llvm::PHITransAddr::getAddr
Value * getAddr() const
Definition: PHITransAddr.h:59
llvm::BatchAAResults::isMustAlias
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Definition: AliasAnalysis.h:985
llvm::MemoryLocation::getWithoutAATags
MemoryLocation getWithoutAATags() const
Definition: MemoryLocation.h:306
llvm::PredIteratorCache::clear
void clear()
clear - Remove all information.
Definition: PredIteratorCache.h:71
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::MemoryDependenceWrapperPass
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Definition: MemoryDependenceAnalysis.h:526
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
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:837
Casting.h
Function.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:101
llvm::PhiValues::invalidateValue
void invalidateValue(const Value *V)
Notify PhiValues that the cached information using V is no longer valid.
Definition: PhiValues.cpp:137
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1552
llvm::is_sorted
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1687
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
SortNonLocalDepInfoCache
static void SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries)
Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already prop...
Definition: MemoryDependenceAnalysis.cpp:987
llvm::MemoryLocation::getWithNewPtr
MemoryLocation getWithNewPtr(const Value *NewPtr) const
Definition: MemoryLocation.h:294
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::isStrongerThan
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
Definition: AtomicOrdering.h:90
AA
llvm::MemoryDependenceAnalysis::MemoryDependenceAnalysis
MemoryDependenceAnalysis()
Definition: MemoryDependenceAnalysis.cpp:1727
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Instructions.h
llvm::DenseMapBase< DenseMap< ValueIsLoadPair, NonLocalPointerInfo, DenseMapInfo< ValueIsLoadPair >, llvm::detail::DenseMapPair< ValueIsLoadPair, NonLocalPointerInfo > >, ValueIsLoadPair, NonLocalPointerInfo, DenseMapInfo< ValueIsLoadPair >, llvm::detail::DenseMapPair< ValueIsLoadPair, NonLocalPointerInfo > >::iterator
DenseMapIterator< ValueIsLoadPair, NonLocalPointerInfo, DenseMapInfo< ValueIsLoadPair >, llvm::detail::DenseMapPair< ValueIsLoadPair, NonLocalPointerInfo > > iterator
Definition: DenseMap.h:71
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
SmallVector.h
llvm::MemoryDependenceWrapperPass::ID
static char ID
Definition: MemoryDependenceAnalysis.h:530
Dominators.h
llvm::MemoryLocation::getAfter
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
Definition: MemoryLocation.h:270
llvm::MemoryDependenceResults::NonLocalDepInfo
std::vector< NonLocalDepEntry > NonLocalDepInfo
Definition: MemoryDependenceAnalysis.h:271
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
RemoveFromReverseMap
static void RemoveFromReverseMap(DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 >> &ReverseMap, Instruction *Inst, KeyTy Val)
This is a helper function that removes Val from 'Inst's set in ReverseMap.
Definition: MemoryDependenceAnalysis.cpp:92
llvm::BatchAAResults::callCapturesBefore
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Definition: AliasAnalysis.h:993
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::PredIteratorCache::get
ArrayRef< BasicBlock * > get(BasicBlock *BB)
Definition: PredIteratorCache.h:66
llvm::MemoryDependenceWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
Does not modify anything. It uses Value Numbering and Alias Analysis.
Definition: MemoryDependenceAnalysis.cpp:1762
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
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
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
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::cl::desc
Definition: CommandLine.h:405
GetLocation
static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc, const TargetLibraryInfo &TLI)
If the given instruction references a specific memory location, fill in Loc with the details,...
Definition: MemoryDependenceAnalysis.cpp:109
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::MemDepResult::getUnknown
static MemDepResult getUnknown()
Definition: MemoryDependenceAnalysis.h:134
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
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
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:336
llvm::AtomicOrdering::NotAtomic
@ NotAtomic
llvm::ModRefInfo::ModRef
@ ModRef
The access may reference and may modify the value stored in memory.
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::isFreeCall
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
Definition: MemoryBuiltins.cpp:531
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236
llvm::NonLocalDepEntry::setResult
void setResult(const MemDepResult &R)
Definition: MemoryDependenceAnalysis.h:213
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::MemoryDependenceAnalysis
An analysis that produces MemoryDependenceResults for a function.
Definition: MemoryDependenceAnalysis.h:507
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::MemDepResult::isDef
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
Definition: MemoryDependenceAnalysis.h:144