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