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