LLVM  9.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 
40 #include "llvm/IR/Argument.h"
41 #include "llvm/IR/Attributes.h"
42 #include "llvm/IR/BasicBlock.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/Module.h"
46 #include "llvm/IR/Type.h"
47 #include "llvm/IR/Value.h"
48 #include "llvm/Pass.h"
50 #include "llvm/Support/Casting.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <functional>
55 #include <iterator>
56 
57 using namespace llvm;
58 
59 /// Allow disabling BasicAA from the AA results. This is particularly useful
60 /// when testing to isolate a single AA implementation.
61 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
62  cl::init(false));
63 
65  : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
66  for (auto &AA : AAs)
67  AA->setAAResults(this);
68 }
69 
71 // FIXME; It would be nice to at least clear out the pointers back to this
72 // aggregation here, but we end up with non-nesting lifetimes in the legacy
73 // pass manager that prevent this from working. In the legacy pass manager
74 // we'll end up with dangling references here in some cases.
75 #if 0
76  for (auto &AA : AAs)
77  AA->setAAResults(nullptr);
78 #endif
79 }
80 
83  // Check if the AA manager itself has been invalidated.
84  auto PAC = PA.getChecker<AAManager>();
85  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
86  return true; // The manager needs to be blown away, clear everything.
87 
88  // Check all of the dependencies registered.
89  for (AnalysisKey *ID : AADeps)
90  if (Inv.invalidate(ID, F, PA))
91  return true;
92 
93  // Everything we depend on is still fine, so are we. Nothing to invalidate.
94  return false;
95 }
96 
97 //===----------------------------------------------------------------------===//
98 // Default chaining methods
99 //===----------------------------------------------------------------------===//
100 
102  const MemoryLocation &LocB) {
103  for (const auto &AA : AAs) {
104  auto Result = AA->alias(LocA, LocB);
105  if (Result != MayAlias)
106  return Result;
107  }
108  return MayAlias;
109 }
110 
112  bool OrLocal) {
113  for (const auto &AA : AAs)
114  if (AA->pointsToConstantMemory(Loc, OrLocal))
115  return true;
116 
117  return false;
118 }
119 
120 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
122 
123  for (const auto &AA : AAs) {
124  Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
125 
126  // Early-exit the moment we reach the bottom of the lattice.
127  if (isNoModRef(Result))
128  return ModRefInfo::NoModRef;
129  }
130 
131  return Result;
132 }
133 
135  // We may have two calls.
136  if (const auto *Call1 = dyn_cast<CallBase>(I)) {
137  // Check if the two calls modify the same memory.
138  return getModRefInfo(Call1, Call2);
139  } else if (I->isFenceLike()) {
140  // If this is a fence, just return ModRef.
141  return ModRefInfo::ModRef;
142  } else {
143  // Otherwise, check if the call modifies or references the
144  // location this memory access defines. The best we can say
145  // is that if the call references what this instruction
146  // defines, it must be clobbered by this location.
147  const MemoryLocation DefLoc = MemoryLocation::get(I);
148  ModRefInfo MR = getModRefInfo(Call2, DefLoc);
149  if (isModOrRefSet(MR))
150  return setModAndRef(MR);
151  }
152  return ModRefInfo::NoModRef;
153 }
154 
156  const MemoryLocation &Loc) {
158 
159  for (const auto &AA : AAs) {
160  Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc));
161 
162  // Early-exit the moment we reach the bottom of the lattice.
163  if (isNoModRef(Result))
164  return ModRefInfo::NoModRef;
165  }
166 
167  // Try to refine the mod-ref info further using other API entry points to the
168  // aggregate set of AA results.
169  auto MRB = getModRefBehavior(Call);
170  if (MRB == FMRB_DoesNotAccessMemory ||
172  return ModRefInfo::NoModRef;
173 
174  if (onlyReadsMemory(MRB))
175  Result = clearMod(Result);
176  else if (doesNotReadMemory(MRB))
177  Result = clearRef(Result);
178 
180  bool IsMustAlias = true;
181  ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
182  if (doesAccessArgPointees(MRB)) {
183  for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
184  const Value *Arg = *AI;
185  if (!Arg->getType()->isPointerTy())
186  continue;
187  unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
188  MemoryLocation ArgLoc =
189  MemoryLocation::getForArgument(Call, ArgIdx, TLI);
190  AliasResult ArgAlias = alias(ArgLoc, Loc);
191  if (ArgAlias != NoAlias) {
192  ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
193  AllArgsMask = unionModRef(AllArgsMask, ArgMask);
194  }
195  // Conservatively clear IsMustAlias unless only MustAlias is found.
196  IsMustAlias &= (ArgAlias == MustAlias);
197  }
198  }
199  // Return NoModRef if no alias found with any argument.
200  if (isNoModRef(AllArgsMask))
201  return ModRefInfo::NoModRef;
202  // Logical & between other AA analyses and argument analysis.
203  Result = intersectModRef(Result, AllArgsMask);
204  // If only MustAlias found above, set Must bit.
205  Result = IsMustAlias ? setMust(Result) : clearMust(Result);
206  }
207 
208  // If Loc is a constant memory location, the call definitely could not
209  // modify the memory location.
210  if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
211  Result = clearMod(Result);
212 
213  return Result;
214 }
215 
217  const CallBase *Call2) {
219 
220  for (const auto &AA : AAs) {
221  Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2));
222 
223  // Early-exit the moment we reach the bottom of the lattice.
224  if (isNoModRef(Result))
225  return ModRefInfo::NoModRef;
226  }
227 
228  // Try to refine the mod-ref info further using other API entry points to the
229  // aggregate set of AA results.
230 
231  // If Call1 or Call2 are readnone, they don't interact.
232  auto Call1B = getModRefBehavior(Call1);
233  if (Call1B == FMRB_DoesNotAccessMemory)
234  return ModRefInfo::NoModRef;
235 
236  auto Call2B = getModRefBehavior(Call2);
237  if (Call2B == FMRB_DoesNotAccessMemory)
238  return ModRefInfo::NoModRef;
239 
240  // If they both only read from memory, there is no dependence.
241  if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
242  return ModRefInfo::NoModRef;
243 
244  // If Call1 only reads memory, the only dependence on Call2 can be
245  // from Call1 reading memory written by Call2.
246  if (onlyReadsMemory(Call1B))
247  Result = clearMod(Result);
248  else if (doesNotReadMemory(Call1B))
249  Result = clearRef(Result);
250 
251  // If Call2 only access memory through arguments, accumulate the mod/ref
252  // information from Call1's references to the memory referenced by
253  // Call2's arguments.
254  if (onlyAccessesArgPointees(Call2B)) {
255  if (!doesAccessArgPointees(Call2B))
256  return ModRefInfo::NoModRef;
258  bool IsMustAlias = true;
259  for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
260  const Value *Arg = *I;
261  if (!Arg->getType()->isPointerTy())
262  continue;
263  unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
264  auto Call2ArgLoc =
265  MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
266 
267  // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
268  // dependence of Call1 on that location is the inverse:
269  // - If Call2 modifies location, dependence exists if Call1 reads or
270  // writes.
271  // - If Call2 only reads location, dependence exists if Call1 writes.
272  ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
274  if (isModSet(ArgModRefC2))
275  ArgMask = ModRefInfo::ModRef;
276  else if (isRefSet(ArgModRefC2))
277  ArgMask = ModRefInfo::Mod;
278 
279  // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
280  // above ArgMask to update dependence info.
281  ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
282  ArgMask = intersectModRef(ArgMask, ModRefC1);
283 
284  // Conservatively clear IsMustAlias unless only MustAlias is found.
285  IsMustAlias &= isMustSet(ModRefC1);
286 
287  R = intersectModRef(unionModRef(R, ArgMask), Result);
288  if (R == Result) {
289  // On early exit, not all args were checked, cannot set Must.
290  if (I + 1 != E)
291  IsMustAlias = false;
292  break;
293  }
294  }
295 
296  if (isNoModRef(R))
297  return ModRefInfo::NoModRef;
298 
299  // If MustAlias found above, set Must bit.
300  return IsMustAlias ? setMust(R) : clearMust(R);
301  }
302 
303  // If Call1 only accesses memory through arguments, check if Call2 references
304  // any of the memory referenced by Call1's arguments. If not, return NoModRef.
305  if (onlyAccessesArgPointees(Call1B)) {
306  if (!doesAccessArgPointees(Call1B))
307  return ModRefInfo::NoModRef;
309  bool IsMustAlias = true;
310  for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
311  const Value *Arg = *I;
312  if (!Arg->getType()->isPointerTy())
313  continue;
314  unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
315  auto Call1ArgLoc =
316  MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
317 
318  // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
319  // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
320  // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
321  ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
322  ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
323  if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
324  (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
325  R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
326 
327  // Conservatively clear IsMustAlias unless only MustAlias is found.
328  IsMustAlias &= isMustSet(ModRefC2);
329 
330  if (R == Result) {
331  // On early exit, not all args were checked, cannot set Must.
332  if (I + 1 != E)
333  IsMustAlias = false;
334  break;
335  }
336  }
337 
338  if (isNoModRef(R))
339  return ModRefInfo::NoModRef;
340 
341  // If MustAlias found above, set Must bit.
342  return IsMustAlias ? setMust(R) : clearMust(R);
343  }
344 
345  return Result;
346 }
347 
350 
351  for (const auto &AA : AAs) {
352  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
353 
354  // Early-exit the moment we reach the bottom of the lattice.
355  if (Result == FMRB_DoesNotAccessMemory)
356  return Result;
357  }
358 
359  return Result;
360 }
361 
364 
365  for (const auto &AA : AAs) {
366  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
367 
368  // Early-exit the moment we reach the bottom of the lattice.
369  if (Result == FMRB_DoesNotAccessMemory)
370  return Result;
371  }
372 
373  return Result;
374 }
375 
377  switch (AR) {
378  case NoAlias:
379  OS << "NoAlias";
380  break;
381  case MustAlias:
382  OS << "MustAlias";
383  break;
384  case MayAlias:
385  OS << "MayAlias";
386  break;
387  case PartialAlias:
388  OS << "PartialAlias";
389  break;
390  }
391  return OS;
392 }
393 
394 //===----------------------------------------------------------------------===//
395 // Helper method implementation
396 //===----------------------------------------------------------------------===//
397 
399  const MemoryLocation &Loc) {
400  // Be conservative in the face of atomic.
402  return ModRefInfo::ModRef;
403 
404  // If the load address doesn't alias the given address, it doesn't read
405  // or write the specified memory.
406  if (Loc.Ptr) {
407  AliasResult AR = alias(MemoryLocation::get(L), Loc);
408  if (AR == NoAlias)
409  return ModRefInfo::NoModRef;
410  if (AR == MustAlias)
411  return ModRefInfo::MustRef;
412  }
413  // Otherwise, a load just reads.
414  return ModRefInfo::Ref;
415 }
416 
418  const MemoryLocation &Loc) {
419  // Be conservative in the face of atomic.
421  return ModRefInfo::ModRef;
422 
423  if (Loc.Ptr) {
424  AliasResult AR = alias(MemoryLocation::get(S), Loc);
425  // If the store address cannot alias the pointer in question, then the
426  // specified memory cannot be modified by the store.
427  if (AR == NoAlias)
428  return ModRefInfo::NoModRef;
429 
430  // If the pointer is a pointer to constant memory, then it could not have
431  // been modified by this store.
432  if (pointsToConstantMemory(Loc))
433  return ModRefInfo::NoModRef;
434 
435  // If the store address aliases the pointer as must alias, set Must.
436  if (AR == MustAlias)
437  return ModRefInfo::MustMod;
438  }
439 
440  // Otherwise, a store just writes.
441  return ModRefInfo::Mod;
442 }
443 
445  // If we know that the location is a constant memory location, the fence
446  // cannot modify this location.
447  if (Loc.Ptr && pointsToConstantMemory(Loc))
448  return ModRefInfo::Ref;
449  return ModRefInfo::ModRef;
450 }
451 
453  const MemoryLocation &Loc) {
454  if (Loc.Ptr) {
455  AliasResult AR = alias(MemoryLocation::get(V), Loc);
456  // If the va_arg address cannot alias the pointer in question, then the
457  // specified memory cannot be accessed by the va_arg.
458  if (AR == NoAlias)
459  return ModRefInfo::NoModRef;
460 
461  // If the pointer is a pointer to constant memory, then it could not have
462  // been modified by this va_arg.
463  if (pointsToConstantMemory(Loc))
464  return ModRefInfo::NoModRef;
465 
466  // If the va_arg aliases the pointer as must alias, set Must.
467  if (AR == MustAlias)
468  return ModRefInfo::MustModRef;
469  }
470 
471  // Otherwise, a va_arg reads and writes.
472  return ModRefInfo::ModRef;
473 }
474 
476  const MemoryLocation &Loc) {
477  if (Loc.Ptr) {
478  // If the pointer is a pointer to constant memory,
479  // then it could not have been modified by this catchpad.
480  if (pointsToConstantMemory(Loc))
481  return ModRefInfo::NoModRef;
482  }
483 
484  // Otherwise, a catchpad reads and writes.
485  return ModRefInfo::ModRef;
486 }
487 
489  const MemoryLocation &Loc) {
490  if (Loc.Ptr) {
491  // If the pointer is a pointer to constant memory,
492  // then it could not have been modified by this catchpad.
493  if (pointsToConstantMemory(Loc))
494  return ModRefInfo::NoModRef;
495  }
496 
497  // Otherwise, a catchret reads and writes.
498  return ModRefInfo::ModRef;
499 }
500 
502  const MemoryLocation &Loc) {
503  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
505  return ModRefInfo::ModRef;
506 
507  if (Loc.Ptr) {
508  AliasResult AR = alias(MemoryLocation::get(CX), Loc);
509  // If the cmpxchg address does not alias the location, it does not access
510  // it.
511  if (AR == NoAlias)
512  return ModRefInfo::NoModRef;
513 
514  // If the cmpxchg address aliases the pointer as must alias, set Must.
515  if (AR == MustAlias)
516  return ModRefInfo::MustModRef;
517  }
518 
519  return ModRefInfo::ModRef;
520 }
521 
523  const MemoryLocation &Loc) {
524  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
526  return ModRefInfo::ModRef;
527 
528  if (Loc.Ptr) {
529  AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
530  // If the atomicrmw address does not alias the location, it does not access
531  // it.
532  if (AR == NoAlias)
533  return ModRefInfo::NoModRef;
534 
535  // If the atomicrmw address aliases the pointer as must alias, set Must.
536  if (AR == MustAlias)
537  return ModRefInfo::MustModRef;
538  }
539 
540  return ModRefInfo::ModRef;
541 }
542 
543 /// Return information about whether a particular call site modifies
544 /// or reads the specified memory location \p MemLoc before instruction \p I
545 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
546 /// instruction-ordering queries inside the BasicBlock containing \p I.
547 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
548 /// BasicAA isn't willing to spend linear time determining whether an alloca
549 /// was captured before or after this particular call, while we are. However,
550 /// with a smarter AA in place, this test is just wasting compile time.
552  const MemoryLocation &MemLoc,
553  DominatorTree *DT,
554  OrderedBasicBlock *OBB) {
555  if (!DT)
556  return ModRefInfo::ModRef;
557 
558  const Value *Object =
560  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
561  isa<Constant>(Object))
562  return ModRefInfo::ModRef;
563 
564  const auto *Call = dyn_cast<CallBase>(I);
565  if (!Call || Call == Object)
566  return ModRefInfo::ModRef;
567 
568  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
569  /* StoreCaptures */ true, I, DT,
570  /* include Object */ true,
571  /* OrderedBasicBlock */ OBB))
572  return ModRefInfo::ModRef;
573 
574  unsigned ArgNo = 0;
576  bool IsMustAlias = true;
577  // Set flag only if no May found and all operands processed.
578  for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
579  CI != CE; ++CI, ++ArgNo) {
580  // Only look at the no-capture or byval pointer arguments. If this
581  // pointer were passed to arguments that were neither of these, then it
582  // couldn't be no-capture.
583  if (!(*CI)->getType()->isPointerTy() ||
584  (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
585  !Call->isByValArgument(ArgNo)))
586  continue;
587 
588  AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
589  // If this is a no-capture pointer argument, see if we can tell that it
590  // is impossible to alias the pointer we're checking. If not, we have to
591  // assume that the call could touch the pointer, even though it doesn't
592  // escape.
593  if (AR != MustAlias)
594  IsMustAlias = false;
595  if (AR == NoAlias)
596  continue;
597  if (Call->doesNotAccessMemory(ArgNo))
598  continue;
599  if (Call->onlyReadsMemory(ArgNo)) {
600  R = ModRefInfo::Ref;
601  continue;
602  }
603  // Not returning MustModRef since we have not seen all the arguments.
604  return ModRefInfo::ModRef;
605  }
606  return IsMustAlias ? setMust(R) : clearMust(R);
607 }
608 
609 /// canBasicBlockModify - Return true if it is possible for execution of the
610 /// specified basic block to modify the location Loc.
611 ///
613  const MemoryLocation &Loc) {
614  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
615 }
616 
617 /// canInstructionRangeModRef - Return true if it is possible for the
618 /// execution of the specified instructions to mod\ref (according to the
619 /// mode) the location Loc. The instructions to consider are all
620 /// of the instructions in the range of [I1,I2] INCLUSIVE.
621 /// I1 and I2 must be in the same basic block.
623  const Instruction &I2,
624  const MemoryLocation &Loc,
625  const ModRefInfo Mode) {
626  assert(I1.getParent() == I2.getParent() &&
627  "Instructions not in same basic block!");
630  ++E; // Convert from inclusive to exclusive range.
631 
632  for (; I != E; ++I) // Check every instruction in range
633  if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
634  return true;
635  return false;
636 }
637 
638 // Provide a definition for the root virtual destructor.
639 AAResults::Concept::~Concept() = default;
640 
641 // Provide a definition for the static object used to identify passes.
642 AnalysisKey AAManager::Key;
643 
644 namespace {
645 
646 
647 } // end anonymous namespace
648 
650 
651 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
652  false, true)
653 
656  return new ExternalAAWrapperPass(std::move(Callback));
657 }
658 
661 }
662 
663 char AAResultsWrapperPass::ID = 0;
664 
666  "Function Alias Analysis Results", false, true)
672 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
677  "Function Alias Analysis Results", false, true)
678 
680  return new AAResultsWrapperPass();
681 }
682 
683 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
684 ///
685 /// This is the legacy pass manager's interface to the new-style AA results
686 /// aggregation object. Because this is somewhat shoe-horned into the legacy
687 /// pass manager, we hard code all the specific alias analyses available into
688 /// it. While the particular set enabled is configured via commandline flags,
689 /// adding a new alias analysis to LLVM will require adding support for it to
690 /// this list.
692  // NB! This *must* be reset before adding new AA results to the new
693  // AAResults object because in the legacy pass manager, each instance
694  // of these will refer to the *same* immutable analyses, registering and
695  // unregistering themselves with them. We need to carefully tear down the
696  // previous object first, in this case replacing it with an empty one, before
697  // registering new results.
698  AAR.reset(
699  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
700 
701  // BasicAA is always available for function analyses. Also, we add it first
702  // so that it can trump TBAA results when it proves MustAlias.
703  // FIXME: TBAA should have an explicit mode to support this and then we
704  // should reconsider the ordering here.
705  if (!DisableBasicAA)
706  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
707 
708  // Populate the results with the currently available AAs.
709  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
710  AAR->addAAResult(WrapperPass->getResult());
711  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
712  AAR->addAAResult(WrapperPass->getResult());
713  if (auto *WrapperPass =
714  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
715  AAR->addAAResult(WrapperPass->getResult());
716  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
717  AAR->addAAResult(WrapperPass->getResult());
718  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
719  AAR->addAAResult(WrapperPass->getResult());
720  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
721  AAR->addAAResult(WrapperPass->getResult());
722  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
723  AAR->addAAResult(WrapperPass->getResult());
724 
725  // If available, run an external AA providing callback over the results as
726  // well.
727  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
728  if (WrapperPass->CB)
729  WrapperPass->CB(*this, F, *AAR);
730 
731  // Analyses don't mutate the IR, so return false.
732  return false;
733 }
734 
736  AU.setPreservesAll();
739 
740  // We also need to mark all the alias analysis passes we will potentially
741  // probe in runOnFunction as used here to ensure the legacy pass manager
742  // preserves them. This hard coding of lists of alias analyses is specific to
743  // the legacy pass manager.
751 }
752 
754  BasicAAResult &BAR) {
756 
757  // Add in our explicitly constructed BasicAA results.
758  if (!DisableBasicAA)
759  AAR.addAAResult(BAR);
760 
761  // Populate the results with the other currently available AAs.
762  if (auto *WrapperPass =
764  AAR.addAAResult(WrapperPass->getResult());
765  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
766  AAR.addAAResult(WrapperPass->getResult());
767  if (auto *WrapperPass =
769  AAR.addAAResult(WrapperPass->getResult());
770  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
771  AAR.addAAResult(WrapperPass->getResult());
772  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
773  AAR.addAAResult(WrapperPass->getResult());
774  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
775  AAR.addAAResult(WrapperPass->getResult());
776 
777  return AAR;
778 }
779 
780 bool llvm::isNoAliasCall(const Value *V) {
781  if (const auto *Call = dyn_cast<CallBase>(V))
782  return Call->hasRetAttr(Attribute::NoAlias);
783  return false;
784 }
785 
787  if (const Argument *A = dyn_cast<Argument>(V))
788  return A->hasNoAliasAttr();
789  return false;
790 }
791 
793  if (isa<AllocaInst>(V))
794  return true;
795  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
796  return true;
797  if (isNoAliasCall(V))
798  return true;
799  if (const Argument *A = dyn_cast<Argument>(V))
800  return A->hasNoAliasAttr() || A->hasByValAttr();
801  return false;
802 }
803 
805  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
806 }
807 
809  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
810  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
811  // to be added here also.
819 }
Legacy wrapper pass to provide the GlobalsAAResult object.
The access may reference and may modify the value stored in memory.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
LLVM_NODISCARD ModRefInfo unionModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
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:660
The access neither references nor modifies the value stored in memory.
LLVM_NODISCARD ModRefInfo clearMust(const ModRefInfo MRI)
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
Atomic ordering constants.
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:541
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
This class represents lattice values for constants.
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:455
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:529
This is the interface for a metadata-based scoped no-alias analysis.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
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:248
Function Alias Analysis Results
This is the AA result object for the basic, local, and stateless alias analysis.
static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from memory that ...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1014
F(f)
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1106
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
block Block Frequency true
An instruction for reading from memory.
Definition: Instructions.h:168
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:692
This indicates that the function could not be classified into one of the behaviors above...
Legacy wrapper pass to provide the TypeBasedAAResult object.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:305
LLVM_NODISCARD ModRefInfo clearMod(const ModRefInfo MRI)
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:938
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:371
static bool doesNotReadMemory(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to only write memory (or not access memory ...
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.
LLVM_NODISCARD ModRefInfo clearRef(const ModRefInfo MRI)
The access may reference the value stored in memory, a mustAlias relation was found, and no mayAlias or partialAlias found.
The access may reference the value stored in memory.
This file contains the simple types necessary to represent the attributes associated with functions a...
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
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 &)
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
LLVM_NODISCARD bool isMustSet(const ModRefInfo MRI)
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:583
The access may reference, modify or both the value stored in memory, a mustAlias relation was found...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
The access may modify the value stored in memory, a mustAlias relation was found, and no mayAlias or ...
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:321
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
static cl::opt< bool > DisableBasicAA("disable-basicaa", cl::Hidden, cl::init(false))
Allow disabling BasicAA from the AA results.
bool isStrongerThanMonotonic(AtomicOrdering ao)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
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 ...
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:423
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
This is the interface for a metadata-based TBAA.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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)...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
const Instruction & front() const
Definition: BasicBlock.h:281
A manager for alias analyses.
Legacy wrapper pass to provide the CFLAndersAAResult object.
Represent the analysis usage information of a pass.
const Instruction & back() const
Definition: BasicBlock.h:283
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:285
self_iterator getIterator()
Definition: ilist_node.h:82
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
AtomicOrdering getOrdering() const
Returns the ordering constraint of this rmw instruction.
Definition: Instructions.h:774
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.
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
Iterator for intrusive lists based on ilist_node.
INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_END(AAResultsWrapperPass
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:256
Module.h This file contains the declarations for the Module class.
The access may modify the value stored in memory.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
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...
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
amdgpu Simplify well known AMD library false Value Value * Arg
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1100
AAResults(const TargetLibraryInfo &TLI)
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
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:373
This file provides utility analysis objects describing memory locations.
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2039
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:642
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:92
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 class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
A wrapper pass for external alias analyses.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
LLVM_NODISCARD ModRefInfo setModAndRef(const ModRefInfo MRI)
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.
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:88
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:71
const BasicBlock * getParent() const
Definition: Instruction.h:67
Legacy wrapper pass to provide the BasicAAResult object.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)