LLVM  6.0.0svn
AliasAnalysis.cpp
Go to the documentation of this file.
1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the generic AliasAnalysis interface which is used as the
11 // common interface used by all clients and implementations of alias analysis.
12 //
13 // This file also implements the default version of the AliasAnalysis interface
14 // that is to be used when no other implementation is specified. This does some
15 // simple tests that detect obvious cases: two different global pointers cannot
16 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
17 // etc.
18 //
19 // This alias analysis implementation really isn't very good for anything, but
20 // it is very fast, and makes a nice clean default implementation. Because it
21 // handles lots of little corner cases, other, more complex, alias analysis
22 // implementations may choose to rely on this pass to resolve these simple and
23 // easy cases.
24 //
25 //===----------------------------------------------------------------------===//
26 
29 #include "llvm/Analysis/CFG.h"
40 #include "llvm/IR/BasicBlock.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/LLVMContext.h"
47 #include "llvm/IR/Type.h"
48 #include "llvm/Pass.h"
49 using namespace llvm;
50 
51 /// Allow disabling BasicAA from the AA results. This is particularly useful
52 /// when testing to isolate a single AA implementation.
53 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
54  cl::init(false));
55 
57  : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
58  for (auto &AA : AAs)
59  AA->setAAResults(this);
60 }
61 
63 // FIXME; It would be nice to at least clear out the pointers back to this
64 // aggregation here, but we end up with non-nesting lifetimes in the legacy
65 // pass manager that prevent this from working. In the legacy pass manager
66 // we'll end up with dangling references here in some cases.
67 #if 0
68  for (auto &AA : AAs)
69  AA->setAAResults(nullptr);
70 #endif
71 }
72 
75  // Check if the AA manager itself has been invalidated.
76  auto PAC = PA.getChecker<AAManager>();
77  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
78  return true; // The manager needs to be blown away, clear everything.
79 
80  // Check all of the dependencies registered.
81  for (AnalysisKey *ID : AADeps)
82  if (Inv.invalidate(ID, F, PA))
83  return true;
84 
85  // Everything we depend on is still fine, so are we. Nothing to invalidate.
86  return false;
87 }
88 
89 //===----------------------------------------------------------------------===//
90 // Default chaining methods
91 //===----------------------------------------------------------------------===//
92 
94  const MemoryLocation &LocB) {
95  for (const auto &AA : AAs) {
96  auto Result = AA->alias(LocA, LocB);
97  if (Result != MayAlias)
98  return Result;
99  }
100  return MayAlias;
101 }
102 
104  bool OrLocal) {
105  for (const auto &AA : AAs)
106  if (AA->pointsToConstantMemory(Loc, OrLocal))
107  return true;
108 
109  return false;
110 }
111 
113  ModRefInfo Result = MRI_ModRef;
114 
115  for (const auto &AA : AAs) {
116  Result = ModRefInfo(Result & AA->getArgModRefInfo(CS, ArgIdx));
117 
118  // Early-exit the moment we reach the bottom of the lattice.
119  if (Result == MRI_NoModRef)
120  return Result;
121  }
122 
123  return Result;
124 }
125 
127  // We may have two calls
128  if (auto CS = ImmutableCallSite(I)) {
129  // Check if the two calls modify the same memory
130  return getModRefInfo(CS, Call);
131  } else if (I->isFenceLike()) {
132  // If this is a fence, just return MRI_ModRef.
133  return MRI_ModRef;
134  } else {
135  // Otherwise, check if the call modifies or references the
136  // location this memory access defines. The best we can say
137  // is that if the call references what this instruction
138  // defines, it must be clobbered by this location.
139  const MemoryLocation DefLoc = MemoryLocation::get(I);
140  if (getModRefInfo(Call, DefLoc) != MRI_NoModRef)
141  return MRI_ModRef;
142  }
143  return MRI_NoModRef;
144 }
145 
147  const MemoryLocation &Loc) {
148  ModRefInfo Result = MRI_ModRef;
149 
150  for (const auto &AA : AAs) {
151  Result = ModRefInfo(Result & AA->getModRefInfo(CS, Loc));
152 
153  // Early-exit the moment we reach the bottom of the lattice.
154  if (Result == MRI_NoModRef)
155  return Result;
156  }
157 
158  // Try to refine the mod-ref info further using other API entry points to the
159  // aggregate set of AA results.
160  auto MRB = getModRefBehavior(CS);
161  if (MRB == FMRB_DoesNotAccessMemory ||
163  return MRI_NoModRef;
164 
165  if (onlyReadsMemory(MRB))
166  Result = ModRefInfo(Result & MRI_Ref);
167  else if (doesNotReadMemory(MRB))
168  Result = ModRefInfo(Result & MRI_Mod);
169 
171  bool DoesAlias = false;
172  ModRefInfo AllArgsMask = MRI_NoModRef;
173  if (doesAccessArgPointees(MRB)) {
174  for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
175  const Value *Arg = *AI;
176  if (!Arg->getType()->isPointerTy())
177  continue;
178  unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
179  MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
180  AliasResult ArgAlias = alias(ArgLoc, Loc);
181  if (ArgAlias != NoAlias) {
182  ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
183  DoesAlias = true;
184  AllArgsMask = ModRefInfo(AllArgsMask | ArgMask);
185  }
186  }
187  }
188  if (!DoesAlias)
189  return MRI_NoModRef;
190  Result = ModRefInfo(Result & AllArgsMask);
191  }
192 
193  // If Loc is a constant memory location, the call definitely could not
194  // modify the memory location.
195  if ((Result & MRI_Mod) &&
196  pointsToConstantMemory(Loc, /*OrLocal*/ false))
197  Result = ModRefInfo(Result & ~MRI_Mod);
198 
199  return Result;
200 }
201 
203  ImmutableCallSite CS2) {
204  ModRefInfo Result = MRI_ModRef;
205 
206  for (const auto &AA : AAs) {
207  Result = ModRefInfo(Result & AA->getModRefInfo(CS1, CS2));
208 
209  // Early-exit the moment we reach the bottom of the lattice.
210  if (Result == MRI_NoModRef)
211  return Result;
212  }
213 
214  // Try to refine the mod-ref info further using other API entry points to the
215  // aggregate set of AA results.
216 
217  // If CS1 or CS2 are readnone, they don't interact.
218  auto CS1B = getModRefBehavior(CS1);
219  if (CS1B == FMRB_DoesNotAccessMemory)
220  return MRI_NoModRef;
221 
222  auto CS2B = getModRefBehavior(CS2);
223  if (CS2B == FMRB_DoesNotAccessMemory)
224  return MRI_NoModRef;
225 
226  // If they both only read from memory, there is no dependence.
227  if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
228  return MRI_NoModRef;
229 
230  // If CS1 only reads memory, the only dependence on CS2 can be
231  // from CS1 reading memory written by CS2.
232  if (onlyReadsMemory(CS1B))
233  Result = ModRefInfo(Result & MRI_Ref);
234  else if (doesNotReadMemory(CS1B))
235  Result = ModRefInfo(Result & MRI_Mod);
236 
237  // If CS2 only access memory through arguments, accumulate the mod/ref
238  // information from CS1's references to the memory referenced by
239  // CS2's arguments.
240  if (onlyAccessesArgPointees(CS2B)) {
242  if (doesAccessArgPointees(CS2B)) {
243  for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
244  const Value *Arg = *I;
245  if (!Arg->getType()->isPointerTy())
246  continue;
247  unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
248  auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
249 
250  // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence
251  // of CS1 on that location is the inverse.
252  ModRefInfo ArgMask = getArgModRefInfo(CS2, CS2ArgIdx);
253  if (ArgMask == MRI_Mod)
254  ArgMask = MRI_ModRef;
255  else if (ArgMask == MRI_Ref)
256  ArgMask = MRI_Mod;
257 
258  ArgMask = ModRefInfo(ArgMask & getModRefInfo(CS1, CS2ArgLoc));
259 
260  R = ModRefInfo((R | ArgMask) & Result);
261  if (R == Result)
262  break;
263  }
264  }
265  return R;
266  }
267 
268  // If CS1 only accesses memory through arguments, check if CS2 references
269  // any of the memory referenced by CS1's arguments. If not, return NoModRef.
270  if (onlyAccessesArgPointees(CS1B)) {
272  if (doesAccessArgPointees(CS1B)) {
273  for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
274  const Value *Arg = *I;
275  if (!Arg->getType()->isPointerTy())
276  continue;
277  unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
278  auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
279 
280  // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
281  // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
282  // might Ref, then we care only about a Mod by CS2.
283  ModRefInfo ArgMask = getArgModRefInfo(CS1, CS1ArgIdx);
284  ModRefInfo ArgR = getModRefInfo(CS2, CS1ArgLoc);
285  if (((ArgMask & MRI_Mod) != MRI_NoModRef &&
286  (ArgR & MRI_ModRef) != MRI_NoModRef) ||
287  ((ArgMask & MRI_Ref) != MRI_NoModRef &&
288  (ArgR & MRI_Mod) != MRI_NoModRef))
289  R = ModRefInfo((R | ArgMask) & Result);
290 
291  if (R == Result)
292  break;
293  }
294  }
295  return R;
296  }
297 
298  return Result;
299 }
300 
303 
304  for (const auto &AA : AAs) {
305  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
306 
307  // Early-exit the moment we reach the bottom of the lattice.
308  if (Result == FMRB_DoesNotAccessMemory)
309  return Result;
310  }
311 
312  return Result;
313 }
314 
317 
318  for (const auto &AA : AAs) {
319  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
320 
321  // Early-exit the moment we reach the bottom of the lattice.
322  if (Result == FMRB_DoesNotAccessMemory)
323  return Result;
324  }
325 
326  return Result;
327 }
328 
329 //===----------------------------------------------------------------------===//
330 // Helper method implementation
331 //===----------------------------------------------------------------------===//
332 
334  const MemoryLocation &Loc) {
335  // Be conservative in the face of atomic.
337  return MRI_ModRef;
338 
339  // If the load address doesn't alias the given address, it doesn't read
340  // or write the specified memory.
341  if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
342  return MRI_NoModRef;
343 
344  // Otherwise, a load just reads.
345  return MRI_Ref;
346 }
347 
349  const MemoryLocation &Loc) {
350  // Be conservative in the face of atomic.
352  return MRI_ModRef;
353 
354  if (Loc.Ptr) {
355  // If the store address cannot alias the pointer in question, then the
356  // specified memory cannot be modified by the store.
357  if (!alias(MemoryLocation::get(S), Loc))
358  return MRI_NoModRef;
359 
360  // If the pointer is a pointer to constant memory, then it could not have
361  // been modified by this store.
362  if (pointsToConstantMemory(Loc))
363  return MRI_NoModRef;
364  }
365 
366  // Otherwise, a store just writes.
367  return MRI_Mod;
368 }
369 
371  // If we know that the location is a constant memory location, the fence
372  // cannot modify this location.
373  if (Loc.Ptr && pointsToConstantMemory(Loc))
374  return MRI_Ref;
375  return MRI_ModRef;
376 }
377 
379  const MemoryLocation &Loc) {
380 
381  if (Loc.Ptr) {
382  // If the va_arg address cannot alias the pointer in question, then the
383  // specified memory cannot be accessed by the va_arg.
384  if (!alias(MemoryLocation::get(V), Loc))
385  return MRI_NoModRef;
386 
387  // If the pointer is a pointer to constant memory, then it could not have
388  // been modified by this va_arg.
389  if (pointsToConstantMemory(Loc))
390  return MRI_NoModRef;
391  }
392 
393  // Otherwise, a va_arg reads and writes.
394  return MRI_ModRef;
395 }
396 
398  const MemoryLocation &Loc) {
399  if (Loc.Ptr) {
400  // If the pointer is a pointer to constant memory,
401  // then it could not have been modified by this catchpad.
402  if (pointsToConstantMemory(Loc))
403  return MRI_NoModRef;
404  }
405 
406  // Otherwise, a catchpad reads and writes.
407  return MRI_ModRef;
408 }
409 
411  const MemoryLocation &Loc) {
412  if (Loc.Ptr) {
413  // If the pointer is a pointer to constant memory,
414  // then it could not have been modified by this catchpad.
415  if (pointsToConstantMemory(Loc))
416  return MRI_NoModRef;
417  }
418 
419  // Otherwise, a catchret reads and writes.
420  return MRI_ModRef;
421 }
422 
424  const MemoryLocation &Loc) {
425  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
427  return MRI_ModRef;
428 
429  // If the cmpxchg address does not alias the location, it does not access it.
430  if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
431  return MRI_NoModRef;
432 
433  return MRI_ModRef;
434 }
435 
437  const MemoryLocation &Loc) {
438  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
440  return MRI_ModRef;
441 
442  // If the atomicrmw address does not alias the location, it does not access it.
443  if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
444  return MRI_NoModRef;
445 
446  return MRI_ModRef;
447 }
448 
449 /// \brief Return information about whether a particular call site modifies
450 /// or reads the specified memory location \p MemLoc before instruction \p I
451 /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
452 /// instruction-ordering queries inside the BasicBlock containing \p I.
453 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
454 /// BasicAA isn't willing to spend linear time determining whether an alloca
455 /// was captured before or after this particular call, while we are. However,
456 /// with a smarter AA in place, this test is just wasting compile time.
458  const MemoryLocation &MemLoc,
459  DominatorTree *DT,
460  OrderedBasicBlock *OBB) {
461  if (!DT)
462  return MRI_ModRef;
463 
464  const Value *Object =
466  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
467  isa<Constant>(Object))
468  return MRI_ModRef;
469 
470  ImmutableCallSite CS(I);
471  if (!CS.getInstruction() || CS.getInstruction() == Object)
472  return MRI_ModRef;
473 
474  if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
475  /* StoreCaptures */ true, I, DT,
476  /* include Object */ true,
477  /* OrderedBasicBlock */ OBB))
478  return MRI_ModRef;
479 
480  unsigned ArgNo = 0;
482  for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
483  CI != CE; ++CI, ++ArgNo) {
484  // Only look at the no-capture or byval pointer arguments. If this
485  // pointer were passed to arguments that were neither of these, then it
486  // couldn't be no-capture.
487  if (!(*CI)->getType()->isPointerTy() ||
488  (!CS.doesNotCapture(ArgNo) &&
489  ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
490  continue;
491 
492  // If this is a no-capture pointer argument, see if we can tell that it
493  // is impossible to alias the pointer we're checking. If not, we have to
494  // assume that the call could touch the pointer, even though it doesn't
495  // escape.
496  if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
497  continue;
498  if (CS.doesNotAccessMemory(ArgNo))
499  continue;
500  if (CS.onlyReadsMemory(ArgNo)) {
501  R = MRI_Ref;
502  continue;
503  }
504  return MRI_ModRef;
505  }
506  return R;
507 }
508 
509 /// canBasicBlockModify - Return true if it is possible for execution of the
510 /// specified basic block to modify the location Loc.
511 ///
513  const MemoryLocation &Loc) {
514  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, MRI_Mod);
515 }
516 
517 /// canInstructionRangeModRef - Return true if it is possible for the
518 /// execution of the specified instructions to mod\ref (according to the
519 /// mode) the location Loc. The instructions to consider are all
520 /// of the instructions in the range of [I1,I2] INCLUSIVE.
521 /// I1 and I2 must be in the same basic block.
523  const Instruction &I2,
524  const MemoryLocation &Loc,
525  const ModRefInfo Mode) {
526  assert(I1.getParent() == I2.getParent() &&
527  "Instructions not in same basic block!");
530  ++E; // Convert from inclusive to exclusive range.
531 
532  for (; I != E; ++I) // Check every instruction in range
533  if (getModRefInfo(&*I, Loc) & Mode)
534  return true;
535  return false;
536 }
537 
538 // Provide a definition for the root virtual destructor.
540 
541 // Provide a definition for the static object used to identify passes.
542 AnalysisKey AAManager::Key;
543 
544 namespace {
545 /// A wrapper pass for external alias analyses. This just squirrels away the
546 /// callback used to run any analyses and register their results.
547 struct ExternalAAWrapperPass : ImmutablePass {
548  typedef std::function<void(Pass &, Function &, AAResults &)> CallbackT;
549 
550  CallbackT CB;
551 
552  static char ID;
553 
554  ExternalAAWrapperPass() : ImmutablePass(ID) {
556  }
557  explicit ExternalAAWrapperPass(CallbackT CB)
558  : ImmutablePass(ID), CB(std::move(CB)) {
560  }
561 
562  void getAnalysisUsage(AnalysisUsage &AU) const override {
563  AU.setPreservesAll();
564  }
565 };
566 }
567 
569 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
570  false, true)
571 
573 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
574  return new ExternalAAWrapperPass(std::move(Callback));
575 }
576 
579 }
580 
581 char AAResultsWrapperPass::ID = 0;
582 
584  "Function Alias Analysis Results", false, true)
588 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
590 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
595  "Function Alias Analysis Results", false, true)
596 
598  return new AAResultsWrapperPass();
599 }
600 
601 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
602 ///
603 /// This is the legacy pass manager's interface to the new-style AA results
604 /// aggregation object. Because this is somewhat shoe-horned into the legacy
605 /// pass manager, we hard code all the specific alias analyses available into
606 /// it. While the particular set enabled is configured via commandline flags,
607 /// adding a new alias analysis to LLVM will require adding support for it to
608 /// this list.
610  // NB! This *must* be reset before adding new AA results to the new
611  // AAResults object because in the legacy pass manager, each instance
612  // of these will refer to the *same* immutable analyses, registering and
613  // unregistering themselves with them. We need to carefully tear down the
614  // previous object first, in this case replacing it with an empty one, before
615  // registering new results.
616  AAR.reset(
617  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
618 
619  // BasicAA is always available for function analyses. Also, we add it first
620  // so that it can trump TBAA results when it proves MustAlias.
621  // FIXME: TBAA should have an explicit mode to support this and then we
622  // should reconsider the ordering here.
623  if (!DisableBasicAA)
624  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
625 
626  // Populate the results with the currently available AAs.
627  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
628  AAR->addAAResult(WrapperPass->getResult());
629  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
630  AAR->addAAResult(WrapperPass->getResult());
631  if (auto *WrapperPass =
632  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
633  AAR->addAAResult(WrapperPass->getResult());
634  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
635  AAR->addAAResult(WrapperPass->getResult());
636  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
637  AAR->addAAResult(WrapperPass->getResult());
638  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
639  AAR->addAAResult(WrapperPass->getResult());
640  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
641  AAR->addAAResult(WrapperPass->getResult());
642 
643  // If available, run an external AA providing callback over the results as
644  // well.
645  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
646  if (WrapperPass->CB)
647  WrapperPass->CB(*this, F, *AAR);
648 
649  // Analyses don't mutate the IR, so return false.
650  return false;
651 }
652 
654  AU.setPreservesAll();
657 
658  // We also need to mark all the alias analysis passes we will potentially
659  // probe in runOnFunction as used here to ensure the legacy pass manager
660  // preserves them. This hard coding of lists of alias analyses is specific to
661  // the legacy pass manager.
669 }
670 
672  BasicAAResult &BAR) {
674 
675  // Add in our explicitly constructed BasicAA results.
676  if (!DisableBasicAA)
677  AAR.addAAResult(BAR);
678 
679  // Populate the results with the other currently available AAs.
680  if (auto *WrapperPass =
682  AAR.addAAResult(WrapperPass->getResult());
683  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
684  AAR.addAAResult(WrapperPass->getResult());
685  if (auto *WrapperPass =
687  AAR.addAAResult(WrapperPass->getResult());
688  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
689  AAR.addAAResult(WrapperPass->getResult());
690  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
691  AAR.addAAResult(WrapperPass->getResult());
692  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
693  AAR.addAAResult(WrapperPass->getResult());
694 
695  return AAR;
696 }
697 
698 bool llvm::isNoAliasCall(const Value *V) {
699  if (auto CS = ImmutableCallSite(V))
700  return CS.hasRetAttr(Attribute::NoAlias);
701  return false;
702 }
703 
705  if (const Argument *A = dyn_cast<Argument>(V))
706  return A->hasNoAliasAttr();
707  return false;
708 }
709 
711  if (isa<AllocaInst>(V))
712  return true;
713  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
714  return true;
715  if (isNoAliasCall(V))
716  return true;
717  if (const Argument *A = dyn_cast<Argument>(V))
718  return A->hasNoAliasAttr() || A->hasByValAttr();
719  return false;
720 }
721 
723  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
724 }
725 
727  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
728  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
729  // to be added here also.
737 }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
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:577
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
SI Whole Quad Mode
bool isFenceLike() const
Return true if this instruction behaves like a memory fence: it can load or store to memory location ...
Definition: Instruction.h:479
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
An instruction for ordering other memory operations.
Definition: Instructions.h:440
an instruction that atomically checks whether a specified value is in a memory location, and, if it is, stores a new value there.
Definition: Instructions.h:514
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias. ...
This is the interface for a metadata-based scoped no-alias analysis.
INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis", false, true) ImmutablePass *llvm
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:233
Function Alias Analysis Results
This is the AA result object for the basic, local, and stateless alias analysis.
bool onlyReadsMemory(ImmutableCallSite CS)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from memory that ...
The two locations do not alias at all.
Definition: AliasAnalysis.h:79
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
An instruction for reading from memory.
Definition: Instructions.h:164
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:677
void initializeExternalAAWrapperPassPass(PassRegistry &)
static bool isStrongerThan(AtomicOrdering ao, AtomicOrdering other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice, which is based on C++&#39;s definition.
The access modifies the value stored in memory.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:81
This indicates that the function could not be classified into one of the behaviors above...
Legacy wrapper pass to provide the TypeBasedAAResult object.
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:446
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AnalysisUsage & addRequired()
The only memory references in this function (if it has any) are references of memory that is otherwis...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Definition: BitVector.h:920
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:94
This is the interface for a SCEV-based alias analysis.
FunctionPass * createAAResultsWrapperPass()
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
static bool doesNotReadMemory(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to only write memory (or not access memory ...
IterTy arg_end() const
Definition: CallSite.h:549
InstrTy * getInstruction() const
Definition: CallSite.h:89
The access references the value stored in memory.
Definition: AliasAnalysis.h:98
AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR)
A helper for the legacy pass manager to create a AAResults object populated to the best of our abilit...
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
void initializeAAResultsWrapperPassPass(PassRegistry &)
IterTy data_operands_end() const
Definition: CallSite.h:246
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
AtomicOrdering getSuccessOrdering() const
Returns the success ordering constraint of this cmpxchg instruction.
Definition: Instructions.h:568
FunctionModRefBehavior
Summary of how a function affects memory in the program.
bool runOnFunction(Function &F) override
Run the wrapper pass to rebuild an aggregation over known AA passes.
Legacy wrapper pass to provide the CFLSteensAAResult object.
An instruction for storing to memory.
Definition: Instructions.h:306
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
static cl::opt< bool > DisableBasicAA("disable-basicaa", cl::Hidden, cl::init(false))
Allow disabling BasicAA from the AA results.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
The access neither references nor modifies the value stored in memory.
Definition: AliasAnalysis.h:96
ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)
A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
This is the interface for LLVM&#39;s unification-based alias analysis implemented with CFL graph reachabi...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
This is the interface for a metadata-based TBAA.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)
Check if it is possible for the execution of the specified instructions to mod(according to the mode)...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
const Instruction & front() const
Definition: BasicBlock.h:264
A manager for alias analyses.
#define A
Definition: LargeTest.cpp:12
Legacy wrapper pass to provide the CFLAndersAAResult object.
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:73
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Return the behavior of the given call site.
Represent the analysis usage information of a pass.
const Instruction & back() const
Definition: BasicBlock.h:266
static bool doesAccessArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to potentially read or write from objects p...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
self_iterator getIterator()
Definition: ilist_node.h:82
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:567
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
unsigned getNumArgOperands() const
Definition: CallSite.h:290
AtomicOrdering getOrdering() const
Returns the ordering constraint of this rmw instruction.
Definition: Instructions.h:757
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This file declares a simple ARC-aware AliasAnalysis using special knowledge of Objective C to enhance...
This function does not perform any non-local loads or stores to memory.
static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Return a location representing a particular argument of a call.
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
Iterator for intrusive lists based on ilist_node.
INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_END(AAResultsWrapperPass
#define E
Definition: LargeTest.cpp:27
Legacy wrapper pass to provide the SCEVAAResult object.
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:266
static bool isStrongerThanMonotonic(AtomicOrdering ao)
IterTy arg_begin() const
Definition: CallSite.h:545
IterTy data_operands_begin() const
data_operands_begin/data_operands_end - Return iterators iterating over the call / invoke argument li...
Definition: CallSite.h:242
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT, OrderedBasicBlock *OBB=nullptr)
Return information about whether a particular call site modifies or reads the specified memory locati...
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:438
AAResults(const TargetLibraryInfo &TLI)
Basic Alias true
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
block Block Frequency Analysis
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Definition: Instructions.h:358
Establish a view to a call site for examination.
Definition: CallSite.h:687
The access both references and modifies the value stored in memory.
#define I(x, y, z)
Definition: MD5.cpp:58
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:572
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
LLVM Value Representation.
Definition: Value.h:73
Legacy wrapper pass to provide the ObjCARCAAResult object.
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
bool isNoAliasArgument(const Value *V)
Return true if this is an argument with the noalias attribute.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a callsite.
const BasicBlock * getParent() const
Definition: Instruction.h:66
Legacy wrapper pass to provide the BasicAAResult object.