LLVM  7.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/CallSite.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/Module.h"
47 #include "llvm/IR/Type.h"
48 #include "llvm/IR/Value.h"
49 #include "llvm/Pass.h"
51 #include "llvm/Support/Casting.h"
53 #include <algorithm>
54 #include <cassert>
55 #include <functional>
56 #include <iterator>
57 
58 using namespace llvm;
59 
60 /// Allow disabling BasicAA from the AA results. This is particularly useful
61 /// when testing to isolate a single AA implementation.
62 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
63  cl::init(false));
64 
66  : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
67  for (auto &AA : AAs)
68  AA->setAAResults(this);
69 }
70 
72 // FIXME; It would be nice to at least clear out the pointers back to this
73 // aggregation here, but we end up with non-nesting lifetimes in the legacy
74 // pass manager that prevent this from working. In the legacy pass manager
75 // we'll end up with dangling references here in some cases.
76 #if 0
77  for (auto &AA : AAs)
78  AA->setAAResults(nullptr);
79 #endif
80 }
81 
84  // Check if the AA manager itself has been invalidated.
85  auto PAC = PA.getChecker<AAManager>();
86  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
87  return true; // The manager needs to be blown away, clear everything.
88 
89  // Check all of the dependencies registered.
90  for (AnalysisKey *ID : AADeps)
91  if (Inv.invalidate(ID, F, PA))
92  return true;
93 
94  // Everything we depend on is still fine, so are we. Nothing to invalidate.
95  return false;
96 }
97 
98 //===----------------------------------------------------------------------===//
99 // Default chaining methods
100 //===----------------------------------------------------------------------===//
101 
103  const MemoryLocation &LocB) {
104  for (const auto &AA : AAs) {
105  auto Result = AA->alias(LocA, LocB);
106  if (Result != MayAlias)
107  return Result;
108  }
109  return MayAlias;
110 }
111 
113  bool OrLocal) {
114  for (const auto &AA : AAs)
115  if (AA->pointsToConstantMemory(Loc, OrLocal))
116  return true;
117 
118  return false;
119 }
120 
123 
124  for (const auto &AA : AAs) {
125  Result = intersectModRef(Result, AA->getArgModRefInfo(CS, ArgIdx));
126 
127  // Early-exit the moment we reach the bottom of the lattice.
128  if (isNoModRef(Result))
129  return ModRefInfo::NoModRef;
130  }
131 
132  return Result;
133 }
134 
136  // We may have two calls.
137  if (auto CS = ImmutableCallSite(I)) {
138  // Check if the two calls modify the same memory.
139  return getModRefInfo(CS, Call);
140  } else if (I->isFenceLike()) {
141  // If this is a fence, just return ModRef.
142  return ModRefInfo::ModRef;
143  } else {
144  // Otherwise, check if the call modifies or references the
145  // location this memory access defines. The best we can say
146  // is that if the call references what this instruction
147  // defines, it must be clobbered by this location.
148  const MemoryLocation DefLoc = MemoryLocation::get(I);
149  ModRefInfo MR = getModRefInfo(Call, DefLoc);
150  if (isModOrRefSet(MR))
151  return setModAndRef(MR);
152  }
153  return ModRefInfo::NoModRef;
154 }
155 
157  const MemoryLocation &Loc) {
159 
160  for (const auto &AA : AAs) {
161  Result = intersectModRef(Result, AA->getModRefInfo(CS, Loc));
162 
163  // Early-exit the moment we reach the bottom of the lattice.
164  if (isNoModRef(Result))
165  return ModRefInfo::NoModRef;
166  }
167 
168  // Try to refine the mod-ref info further using other API entry points to the
169  // aggregate set of AA results.
170  auto MRB = getModRefBehavior(CS);
171  if (MRB == FMRB_DoesNotAccessMemory ||
173  return ModRefInfo::NoModRef;
174 
175  if (onlyReadsMemory(MRB))
176  Result = clearMod(Result);
177  else if (doesNotReadMemory(MRB))
178  Result = clearRef(Result);
179 
181  bool DoesAlias = false;
182  bool IsMustAlias = true;
183  ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
184  if (doesAccessArgPointees(MRB)) {
185  for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
186  const Value *Arg = *AI;
187  if (!Arg->getType()->isPointerTy())
188  continue;
189  unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
190  MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
191  AliasResult ArgAlias = alias(ArgLoc, Loc);
192  if (ArgAlias != NoAlias) {
193  ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
194  DoesAlias = true;
195  AllArgsMask = unionModRef(AllArgsMask, ArgMask);
196  }
197  // Conservatively clear IsMustAlias unless only MustAlias is found.
198  IsMustAlias &= (ArgAlias == MustAlias);
199  }
200  }
201  // Return NoModRef if no alias found with any argument.
202  if (!DoesAlias)
203  return ModRefInfo::NoModRef;
204  // Logical & between other AA analyses and argument analysis.
205  Result = intersectModRef(Result, AllArgsMask);
206  // If only MustAlias found above, set Must bit.
207  Result = IsMustAlias ? setMust(Result) : clearMust(Result);
208  }
209 
210  // If Loc is a constant memory location, the call definitely could not
211  // modify the memory location.
212  if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
213  Result = clearMod(Result);
214 
215  return Result;
216 }
217 
219  ImmutableCallSite CS2) {
221 
222  for (const auto &AA : AAs) {
223  Result = intersectModRef(Result, AA->getModRefInfo(CS1, CS2));
224 
225  // Early-exit the moment we reach the bottom of the lattice.
226  if (isNoModRef(Result))
227  return ModRefInfo::NoModRef;
228  }
229 
230  // Try to refine the mod-ref info further using other API entry points to the
231  // aggregate set of AA results.
232 
233  // If CS1 or CS2 are readnone, they don't interact.
234  auto CS1B = getModRefBehavior(CS1);
235  if (CS1B == FMRB_DoesNotAccessMemory)
236  return ModRefInfo::NoModRef;
237 
238  auto CS2B = getModRefBehavior(CS2);
239  if (CS2B == FMRB_DoesNotAccessMemory)
240  return ModRefInfo::NoModRef;
241 
242  // If they both only read from memory, there is no dependence.
243  if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
244  return ModRefInfo::NoModRef;
245 
246  // If CS1 only reads memory, the only dependence on CS2 can be
247  // from CS1 reading memory written by CS2.
248  if (onlyReadsMemory(CS1B))
249  Result = clearMod(Result);
250  else if (doesNotReadMemory(CS1B))
251  Result = clearRef(Result);
252 
253  // If CS2 only access memory through arguments, accumulate the mod/ref
254  // information from CS1's references to the memory referenced by
255  // CS2's arguments.
256  if (onlyAccessesArgPointees(CS2B)) {
257  if (!doesAccessArgPointees(CS2B))
258  return ModRefInfo::NoModRef;
260  bool IsMustAlias = true;
261  for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
262  const Value *Arg = *I;
263  if (!Arg->getType()->isPointerTy())
264  continue;
265  unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
266  auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
267 
268  // ArgModRefCS2 indicates what CS2 might do to CS2ArgLoc, and the
269  // dependence of CS1 on that location is the inverse:
270  // - If CS2 modifies location, dependence exists if CS1 reads or writes.
271  // - If CS2 only reads location, dependence exists if CS1 writes.
272  ModRefInfo ArgModRefCS2 = getArgModRefInfo(CS2, CS2ArgIdx);
274  if (isModSet(ArgModRefCS2))
275  ArgMask = ModRefInfo::ModRef;
276  else if (isRefSet(ArgModRefCS2))
277  ArgMask = ModRefInfo::Mod;
278 
279  // ModRefCS1 indicates what CS1 might do to CS2ArgLoc, and we use
280  // above ArgMask to update dependence info.
281  ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc);
282  ArgMask = intersectModRef(ArgMask, ModRefCS1);
283 
284  // Conservatively clear IsMustAlias unless only MustAlias is found.
285  IsMustAlias &= isMustSet(ModRefCS1);
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 CS1 only accesses memory through arguments, check if CS2 references
304  // any of the memory referenced by CS1's arguments. If not, return NoModRef.
305  if (onlyAccessesArgPointees(CS1B)) {
306  if (!doesAccessArgPointees(CS1B))
307  return ModRefInfo::NoModRef;
309  bool IsMustAlias = true;
310  for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
311  const Value *Arg = *I;
312  if (!Arg->getType()->isPointerTy())
313  continue;
314  unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
315  auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
316 
317  // ArgModRefCS1 indicates what CS1 might do to CS1ArgLoc; if CS1 might
318  // Mod CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If
319  // CS1 might Ref, then we care only about a Mod by CS2.
320  ModRefInfo ArgModRefCS1 = getArgModRefInfo(CS1, CS1ArgIdx);
321  ModRefInfo ModRefCS2 = getModRefInfo(CS2, CS1ArgLoc);
322  if ((isModSet(ArgModRefCS1) && isModOrRefSet(ModRefCS2)) ||
323  (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2)))
324  R = intersectModRef(unionModRef(R, ArgModRefCS1), Result);
325 
326  // Conservatively clear IsMustAlias unless only MustAlias is found.
327  IsMustAlias &= isMustSet(ModRefCS2);
328 
329  if (R == Result) {
330  // On early exit, not all args were checked, cannot set Must.
331  if (I + 1 != E)
332  IsMustAlias = false;
333  break;
334  }
335  }
336 
337  if (isNoModRef(R))
338  return ModRefInfo::NoModRef;
339 
340  // If MustAlias found above, set Must bit.
341  return IsMustAlias ? setMust(R) : clearMust(R);
342  }
343 
344  return Result;
345 }
346 
349 
350  for (const auto &AA : AAs) {
351  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
352 
353  // Early-exit the moment we reach the bottom of the lattice.
354  if (Result == FMRB_DoesNotAccessMemory)
355  return Result;
356  }
357 
358  return Result;
359 }
360 
363 
364  for (const auto &AA : AAs) {
365  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
366 
367  // Early-exit the moment we reach the bottom of the lattice.
368  if (Result == FMRB_DoesNotAccessMemory)
369  return Result;
370  }
371 
372  return Result;
373 }
374 
376  switch (AR) {
377  case NoAlias:
378  OS << "NoAlias";
379  break;
380  case MustAlias:
381  OS << "MustAlias";
382  break;
383  case MayAlias:
384  OS << "MayAlias";
385  break;
386  case PartialAlias:
387  OS << "PartialAlias";
388  break;
389  }
390  return OS;
391 }
392 
393 //===----------------------------------------------------------------------===//
394 // Helper method implementation
395 //===----------------------------------------------------------------------===//
396 
398  const MemoryLocation &Loc) {
399  // Be conservative in the face of atomic.
401  return ModRefInfo::ModRef;
402 
403  // If the load address doesn't alias the given address, it doesn't read
404  // or write the specified memory.
405  if (Loc.Ptr) {
406  AliasResult AR = alias(MemoryLocation::get(L), Loc);
407  if (AR == NoAlias)
408  return ModRefInfo::NoModRef;
409  if (AR == MustAlias)
410  return ModRefInfo::MustRef;
411  }
412  // Otherwise, a load just reads.
413  return ModRefInfo::Ref;
414 }
415 
417  const MemoryLocation &Loc) {
418  // Be conservative in the face of atomic.
420  return ModRefInfo::ModRef;
421 
422  if (Loc.Ptr) {
423  AliasResult AR = alias(MemoryLocation::get(S), Loc);
424  // If the store address cannot alias the pointer in question, then the
425  // specified memory cannot be modified by the store.
426  if (AR == NoAlias)
427  return ModRefInfo::NoModRef;
428 
429  // If the pointer is a pointer to constant memory, then it could not have
430  // been modified by this store.
431  if (pointsToConstantMemory(Loc))
432  return ModRefInfo::NoModRef;
433 
434  // If the store address aliases the pointer as must alias, set Must.
435  if (AR == MustAlias)
436  return ModRefInfo::MustMod;
437  }
438 
439  // Otherwise, a store just writes.
440  return ModRefInfo::Mod;
441 }
442 
444  // If we know that the location is a constant memory location, the fence
445  // cannot modify this location.
446  if (Loc.Ptr && pointsToConstantMemory(Loc))
447  return ModRefInfo::Ref;
448  return ModRefInfo::ModRef;
449 }
450 
452  const MemoryLocation &Loc) {
453  if (Loc.Ptr) {
454  AliasResult AR = alias(MemoryLocation::get(V), Loc);
455  // If the va_arg address cannot alias the pointer in question, then the
456  // specified memory cannot be accessed by the va_arg.
457  if (AR == NoAlias)
458  return ModRefInfo::NoModRef;
459 
460  // If the pointer is a pointer to constant memory, then it could not have
461  // been modified by this va_arg.
462  if (pointsToConstantMemory(Loc))
463  return ModRefInfo::NoModRef;
464 
465  // If the va_arg aliases the pointer as must alias, set Must.
466  if (AR == MustAlias)
467  return ModRefInfo::MustModRef;
468  }
469 
470  // Otherwise, a va_arg reads and writes.
471  return ModRefInfo::ModRef;
472 }
473 
475  const MemoryLocation &Loc) {
476  if (Loc.Ptr) {
477  // If the pointer is a pointer to constant memory,
478  // then it could not have been modified by this catchpad.
479  if (pointsToConstantMemory(Loc))
480  return ModRefInfo::NoModRef;
481  }
482 
483  // Otherwise, a catchpad reads and writes.
484  return ModRefInfo::ModRef;
485 }
486 
488  const MemoryLocation &Loc) {
489  if (Loc.Ptr) {
490  // If the pointer is a pointer to constant memory,
491  // then it could not have been modified by this catchpad.
492  if (pointsToConstantMemory(Loc))
493  return ModRefInfo::NoModRef;
494  }
495 
496  // Otherwise, a catchret reads and writes.
497  return ModRefInfo::ModRef;
498 }
499 
501  const MemoryLocation &Loc) {
502  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
504  return ModRefInfo::ModRef;
505 
506  if (Loc.Ptr) {
507  AliasResult AR = alias(MemoryLocation::get(CX), Loc);
508  // If the cmpxchg address does not alias the location, it does not access
509  // it.
510  if (AR == NoAlias)
511  return ModRefInfo::NoModRef;
512 
513  // If the cmpxchg address aliases the pointer as must alias, set Must.
514  if (AR == MustAlias)
515  return ModRefInfo::MustModRef;
516  }
517 
518  return ModRefInfo::ModRef;
519 }
520 
522  const MemoryLocation &Loc) {
523  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
525  return ModRefInfo::ModRef;
526 
527  if (Loc.Ptr) {
528  AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
529  // If the atomicrmw address does not alias the location, it does not access
530  // it.
531  if (AR == NoAlias)
532  return ModRefInfo::NoModRef;
533 
534  // If the atomicrmw address aliases the pointer as must alias, set Must.
535  if (AR == MustAlias)
536  return ModRefInfo::MustModRef;
537  }
538 
539  return ModRefInfo::ModRef;
540 }
541 
542 /// Return information about whether a particular call site modifies
543 /// or reads the specified memory location \p MemLoc before instruction \p I
544 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
545 /// instruction-ordering queries inside the BasicBlock containing \p I.
546 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
547 /// BasicAA isn't willing to spend linear time determining whether an alloca
548 /// was captured before or after this particular call, while we are. However,
549 /// with a smarter AA in place, this test is just wasting compile time.
551  const MemoryLocation &MemLoc,
552  DominatorTree *DT,
553  OrderedBasicBlock *OBB) {
554  if (!DT)
555  return ModRefInfo::ModRef;
556 
557  const Value *Object =
559  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
560  isa<Constant>(Object))
561  return ModRefInfo::ModRef;
562 
563  ImmutableCallSite CS(I);
564  if (!CS.getInstruction() || CS.getInstruction() == Object)
565  return ModRefInfo::ModRef;
566 
567  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
568  /* StoreCaptures */ true, I, DT,
569  /* include Object */ true,
570  /* OrderedBasicBlock */ OBB))
571  return ModRefInfo::ModRef;
572 
573  unsigned ArgNo = 0;
575  bool IsMustAlias = true;
576  // Set flag only if no May found and all operands processed.
577  for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
578  CI != CE; ++CI, ++ArgNo) {
579  // Only look at the no-capture or byval pointer arguments. If this
580  // pointer were passed to arguments that were neither of these, then it
581  // couldn't be no-capture.
582  if (!(*CI)->getType()->isPointerTy() ||
583  (!CS.doesNotCapture(ArgNo) &&
584  ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
585  continue;
586 
587  AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
588  // If this is a no-capture pointer argument, see if we can tell that it
589  // is impossible to alias the pointer we're checking. If not, we have to
590  // assume that the call could touch the pointer, even though it doesn't
591  // escape.
592  if (AR != MustAlias)
593  IsMustAlias = false;
594  if (AR == NoAlias)
595  continue;
596  if (CS.doesNotAccessMemory(ArgNo))
597  continue;
598  if (CS.onlyReadsMemory(ArgNo)) {
599  R = ModRefInfo::Ref;
600  continue;
601  }
602  // Not returning MustModRef since we have not seen all the arguments.
603  return ModRefInfo::ModRef;
604  }
605  return IsMustAlias ? setMust(R) : clearMust(R);
606 }
607 
608 /// canBasicBlockModify - Return true if it is possible for execution of the
609 /// specified basic block to modify the location Loc.
610 ///
612  const MemoryLocation &Loc) {
613  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
614 }
615 
616 /// canInstructionRangeModRef - Return true if it is possible for the
617 /// execution of the specified instructions to mod\ref (according to the
618 /// mode) the location Loc. The instructions to consider are all
619 /// of the instructions in the range of [I1,I2] INCLUSIVE.
620 /// I1 and I2 must be in the same basic block.
622  const Instruction &I2,
623  const MemoryLocation &Loc,
624  const ModRefInfo Mode) {
625  assert(I1.getParent() == I2.getParent() &&
626  "Instructions not in same basic block!");
629  ++E; // Convert from inclusive to exclusive range.
630 
631  for (; I != E; ++I) // Check every instruction in range
632  if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
633  return true;
634  return false;
635 }
636 
637 // Provide a definition for the root virtual destructor.
638 AAResults::Concept::~Concept() = default;
639 
640 // Provide a definition for the static object used to identify passes.
641 AnalysisKey AAManager::Key;
642 
643 namespace {
644 
645 /// A wrapper pass for external alias analyses. This just squirrels away the
646 /// callback used to run any analyses and register their results.
647 struct ExternalAAWrapperPass : ImmutablePass {
648  using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
649 
650  CallbackT CB;
651 
652  static char ID;
653 
654  ExternalAAWrapperPass() : ImmutablePass(ID) {
656  }
657 
658  explicit ExternalAAWrapperPass(CallbackT CB)
659  : ImmutablePass(ID), CB(std::move(CB)) {
661  }
662 
663  void getAnalysisUsage(AnalysisUsage &AU) const override {
664  AU.setPreservesAll();
665  }
666 };
667 
668 } // end anonymous namespace
669 
671 
672 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
673  false, true)
674 
676 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
677  return new ExternalAAWrapperPass(std::move(Callback));
678 }
679 
682 }
683 
684 char AAResultsWrapperPass::ID = 0;
685 
687  "Function Alias Analysis Results", false, true)
691 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
693 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
698  "Function Alias Analysis Results", false, true)
699 
701  return new AAResultsWrapperPass();
702 }
703 
704 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
705 ///
706 /// This is the legacy pass manager's interface to the new-style AA results
707 /// aggregation object. Because this is somewhat shoe-horned into the legacy
708 /// pass manager, we hard code all the specific alias analyses available into
709 /// it. While the particular set enabled is configured via commandline flags,
710 /// adding a new alias analysis to LLVM will require adding support for it to
711 /// this list.
713  // NB! This *must* be reset before adding new AA results to the new
714  // AAResults object because in the legacy pass manager, each instance
715  // of these will refer to the *same* immutable analyses, registering and
716  // unregistering themselves with them. We need to carefully tear down the
717  // previous object first, in this case replacing it with an empty one, before
718  // registering new results.
719  AAR.reset(
720  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
721 
722  // BasicAA is always available for function analyses. Also, we add it first
723  // so that it can trump TBAA results when it proves MustAlias.
724  // FIXME: TBAA should have an explicit mode to support this and then we
725  // should reconsider the ordering here.
726  if (!DisableBasicAA)
727  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
728 
729  // Populate the results with the currently available AAs.
730  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
731  AAR->addAAResult(WrapperPass->getResult());
732  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
733  AAR->addAAResult(WrapperPass->getResult());
734  if (auto *WrapperPass =
735  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
736  AAR->addAAResult(WrapperPass->getResult());
737  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
738  AAR->addAAResult(WrapperPass->getResult());
739  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
740  AAR->addAAResult(WrapperPass->getResult());
741  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
742  AAR->addAAResult(WrapperPass->getResult());
743  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
744  AAR->addAAResult(WrapperPass->getResult());
745 
746  // If available, run an external AA providing callback over the results as
747  // well.
748  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
749  if (WrapperPass->CB)
750  WrapperPass->CB(*this, F, *AAR);
751 
752  // Analyses don't mutate the IR, so return false.
753  return false;
754 }
755 
757  AU.setPreservesAll();
760 
761  // We also need to mark all the alias analysis passes we will potentially
762  // probe in runOnFunction as used here to ensure the legacy pass manager
763  // preserves them. This hard coding of lists of alias analyses is specific to
764  // the legacy pass manager.
772 }
773 
775  BasicAAResult &BAR) {
777 
778  // Add in our explicitly constructed BasicAA results.
779  if (!DisableBasicAA)
780  AAR.addAAResult(BAR);
781 
782  // Populate the results with the other currently available AAs.
783  if (auto *WrapperPass =
785  AAR.addAAResult(WrapperPass->getResult());
786  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
787  AAR.addAAResult(WrapperPass->getResult());
788  if (auto *WrapperPass =
790  AAR.addAAResult(WrapperPass->getResult());
791  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
792  AAR.addAAResult(WrapperPass->getResult());
793  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
794  AAR.addAAResult(WrapperPass->getResult());
795  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
796  AAR.addAAResult(WrapperPass->getResult());
797 
798  return AAR;
799 }
800 
801 bool llvm::isNoAliasCall(const Value *V) {
802  if (auto CS = ImmutableCallSite(V))
803  return CS.hasRetAttr(Attribute::NoAlias);
804  return false;
805 }
806 
808  if (const Argument *A = dyn_cast<Argument>(V))
809  return A->hasNoAliasAttr();
810  return false;
811 }
812 
814  if (isa<AllocaInst>(V))
815  return true;
816  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
817  return true;
818  if (isNoAliasCall(V))
819  return true;
820  if (const Argument *A = dyn_cast<Argument>(V))
821  return A->hasNoAliasAttr() || A->hasByValAttr();
822  return false;
823 }
824 
826  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
827 }
828 
830  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
831  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
832  // to be added here also.
840 }
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:577
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:520
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:444
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:518
This is the interface for a metadata-based scoped no-alias analysis.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
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:237
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 ...
F(f)
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:168
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:681
void initializeExternalAAWrapperPassPass(PassRegistry &)
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:454
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
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:921
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 ...
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)
IterTy arg_end() const
Definition: CallSite.h:575
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...
InstrTy * getInstruction() const
Definition: CallSite.h:92
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 &)
LLVM_NODISCARD bool isMustSet(const ModRefInfo MRI)
IterTy data_operands_end() const
Definition: CallSite.h:249
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:572
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:310
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.
bool isStrongerThanMonotonic(AtomicOrdering ao)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
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:410
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
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)...
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:276
A manager for alias analyses.
Legacy wrapper pass to provide the CFLAndersAAResult object.
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:278
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 doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:593
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
unsigned getNumArgOperands() const
Definition: CallSite.h:293
AtomicOrdering getOrdering() const
Returns the ordering constraint of this rmw instruction.
Definition: Instructions.h:761
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.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
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:91
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
IterTy arg_begin() const
Definition: CallSite.h:571
Module.h This file contains the declarations for the Module class.
IterTy data_operands_begin() const
data_operands_begin/data_operands_end - Return iterators iterating over the call / invoke argument li...
Definition: CallSite.h:245
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...
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.
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:446
amdgpu Simplify well known AMD library false Value Value * Arg
AAResults(const TargetLibraryInfo &TLI)
Basic Alias true
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:362
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:714
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
#define I(x, y, z)
Definition: MD5.cpp:58
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2032
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:598
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
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 class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
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...
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:89
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:67
Legacy wrapper pass to provide the BasicAAResult object.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)