LLVM  8.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 IsMustAlias = true;
182  ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
183  if (doesAccessArgPointees(MRB)) {
184  for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
185  const Value *Arg = *AI;
186  if (!Arg->getType()->isPointerTy())
187  continue;
188  unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
189  MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
190  AliasResult ArgAlias = alias(ArgLoc, Loc);
191  if (ArgAlias != NoAlias) {
192  ModRefInfo ArgMask = getArgModRefInfo(CS, 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  ImmutableCallSite CS2) {
219 
220  for (const auto &AA : AAs) {
221  Result = intersectModRef(Result, AA->getModRefInfo(CS1, CS2));
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 CS1 or CS2 are readnone, they don't interact.
232  auto CS1B = getModRefBehavior(CS1);
233  if (CS1B == FMRB_DoesNotAccessMemory)
234  return ModRefInfo::NoModRef;
235 
236  auto CS2B = getModRefBehavior(CS2);
237  if (CS2B == FMRB_DoesNotAccessMemory)
238  return ModRefInfo::NoModRef;
239 
240  // If they both only read from memory, there is no dependence.
241  if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
242  return ModRefInfo::NoModRef;
243 
244  // If CS1 only reads memory, the only dependence on CS2 can be
245  // from CS1 reading memory written by CS2.
246  if (onlyReadsMemory(CS1B))
247  Result = clearMod(Result);
248  else if (doesNotReadMemory(CS1B))
249  Result = clearRef(Result);
250 
251  // If CS2 only access memory through arguments, accumulate the mod/ref
252  // information from CS1's references to the memory referenced by
253  // CS2's arguments.
254  if (onlyAccessesArgPointees(CS2B)) {
255  if (!doesAccessArgPointees(CS2B))
256  return ModRefInfo::NoModRef;
258  bool IsMustAlias = true;
259  for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
260  const Value *Arg = *I;
261  if (!Arg->getType()->isPointerTy())
262  continue;
263  unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
264  auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
265 
266  // ArgModRefCS2 indicates what CS2 might do to CS2ArgLoc, and the
267  // dependence of CS1 on that location is the inverse:
268  // - If CS2 modifies location, dependence exists if CS1 reads or writes.
269  // - If CS2 only reads location, dependence exists if CS1 writes.
270  ModRefInfo ArgModRefCS2 = getArgModRefInfo(CS2, CS2ArgIdx);
272  if (isModSet(ArgModRefCS2))
273  ArgMask = ModRefInfo::ModRef;
274  else if (isRefSet(ArgModRefCS2))
275  ArgMask = ModRefInfo::Mod;
276 
277  // ModRefCS1 indicates what CS1 might do to CS2ArgLoc, and we use
278  // above ArgMask to update dependence info.
279  ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc);
280  ArgMask = intersectModRef(ArgMask, ModRefCS1);
281 
282  // Conservatively clear IsMustAlias unless only MustAlias is found.
283  IsMustAlias &= isMustSet(ModRefCS1);
284 
285  R = intersectModRef(unionModRef(R, ArgMask), Result);
286  if (R == Result) {
287  // On early exit, not all args were checked, cannot set Must.
288  if (I + 1 != E)
289  IsMustAlias = false;
290  break;
291  }
292  }
293 
294  if (isNoModRef(R))
295  return ModRefInfo::NoModRef;
296 
297  // If MustAlias found above, set Must bit.
298  return IsMustAlias ? setMust(R) : clearMust(R);
299  }
300 
301  // If CS1 only accesses memory through arguments, check if CS2 references
302  // any of the memory referenced by CS1's arguments. If not, return NoModRef.
303  if (onlyAccessesArgPointees(CS1B)) {
304  if (!doesAccessArgPointees(CS1B))
305  return ModRefInfo::NoModRef;
307  bool IsMustAlias = true;
308  for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
309  const Value *Arg = *I;
310  if (!Arg->getType()->isPointerTy())
311  continue;
312  unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
313  auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
314 
315  // ArgModRefCS1 indicates what CS1 might do to CS1ArgLoc; if CS1 might
316  // Mod CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If
317  // CS1 might Ref, then we care only about a Mod by CS2.
318  ModRefInfo ArgModRefCS1 = getArgModRefInfo(CS1, CS1ArgIdx);
319  ModRefInfo ModRefCS2 = getModRefInfo(CS2, CS1ArgLoc);
320  if ((isModSet(ArgModRefCS1) && isModOrRefSet(ModRefCS2)) ||
321  (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2)))
322  R = intersectModRef(unionModRef(R, ArgModRefCS1), Result);
323 
324  // Conservatively clear IsMustAlias unless only MustAlias is found.
325  IsMustAlias &= isMustSet(ModRefCS2);
326 
327  if (R == Result) {
328  // On early exit, not all args were checked, cannot set Must.
329  if (I + 1 != E)
330  IsMustAlias = false;
331  break;
332  }
333  }
334 
335  if (isNoModRef(R))
336  return ModRefInfo::NoModRef;
337 
338  // If MustAlias found above, set Must bit.
339  return IsMustAlias ? setMust(R) : clearMust(R);
340  }
341 
342  return Result;
343 }
344 
347 
348  for (const auto &AA : AAs) {
349  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
350 
351  // Early-exit the moment we reach the bottom of the lattice.
352  if (Result == FMRB_DoesNotAccessMemory)
353  return Result;
354  }
355 
356  return Result;
357 }
358 
361 
362  for (const auto &AA : AAs) {
363  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
364 
365  // Early-exit the moment we reach the bottom of the lattice.
366  if (Result == FMRB_DoesNotAccessMemory)
367  return Result;
368  }
369 
370  return Result;
371 }
372 
374  switch (AR) {
375  case NoAlias:
376  OS << "NoAlias";
377  break;
378  case MustAlias:
379  OS << "MustAlias";
380  break;
381  case MayAlias:
382  OS << "MayAlias";
383  break;
384  case PartialAlias:
385  OS << "PartialAlias";
386  break;
387  }
388  return OS;
389 }
390 
391 //===----------------------------------------------------------------------===//
392 // Helper method implementation
393 //===----------------------------------------------------------------------===//
394 
396  const MemoryLocation &Loc) {
397  // Be conservative in the face of atomic.
399  return ModRefInfo::ModRef;
400 
401  // If the load address doesn't alias the given address, it doesn't read
402  // or write the specified memory.
403  if (Loc.Ptr) {
404  AliasResult AR = alias(MemoryLocation::get(L), Loc);
405  if (AR == NoAlias)
406  return ModRefInfo::NoModRef;
407  if (AR == MustAlias)
408  return ModRefInfo::MustRef;
409  }
410  // Otherwise, a load just reads.
411  return ModRefInfo::Ref;
412 }
413 
415  const MemoryLocation &Loc) {
416  // Be conservative in the face of atomic.
418  return ModRefInfo::ModRef;
419 
420  if (Loc.Ptr) {
421  AliasResult AR = alias(MemoryLocation::get(S), Loc);
422  // If the store address cannot alias the pointer in question, then the
423  // specified memory cannot be modified by the store.
424  if (AR == NoAlias)
425  return ModRefInfo::NoModRef;
426 
427  // If the pointer is a pointer to constant memory, then it could not have
428  // been modified by this store.
429  if (pointsToConstantMemory(Loc))
430  return ModRefInfo::NoModRef;
431 
432  // If the store address aliases the pointer as must alias, set Must.
433  if (AR == MustAlias)
434  return ModRefInfo::MustMod;
435  }
436 
437  // Otherwise, a store just writes.
438  return ModRefInfo::Mod;
439 }
440 
442  // If we know that the location is a constant memory location, the fence
443  // cannot modify this location.
444  if (Loc.Ptr && pointsToConstantMemory(Loc))
445  return ModRefInfo::Ref;
446  return ModRefInfo::ModRef;
447 }
448 
450  const MemoryLocation &Loc) {
451  if (Loc.Ptr) {
452  AliasResult AR = alias(MemoryLocation::get(V), Loc);
453  // If the va_arg address cannot alias the pointer in question, then the
454  // specified memory cannot be accessed by the va_arg.
455  if (AR == NoAlias)
456  return ModRefInfo::NoModRef;
457 
458  // If the pointer is a pointer to constant memory, then it could not have
459  // been modified by this va_arg.
460  if (pointsToConstantMemory(Loc))
461  return ModRefInfo::NoModRef;
462 
463  // If the va_arg aliases the pointer as must alias, set Must.
464  if (AR == MustAlias)
465  return ModRefInfo::MustModRef;
466  }
467 
468  // Otherwise, a va_arg reads and writes.
469  return ModRefInfo::ModRef;
470 }
471 
473  const MemoryLocation &Loc) {
474  if (Loc.Ptr) {
475  // If the pointer is a pointer to constant memory,
476  // then it could not have been modified by this catchpad.
477  if (pointsToConstantMemory(Loc))
478  return ModRefInfo::NoModRef;
479  }
480 
481  // Otherwise, a catchpad reads and writes.
482  return ModRefInfo::ModRef;
483 }
484 
486  const MemoryLocation &Loc) {
487  if (Loc.Ptr) {
488  // If the pointer is a pointer to constant memory,
489  // then it could not have been modified by this catchpad.
490  if (pointsToConstantMemory(Loc))
491  return ModRefInfo::NoModRef;
492  }
493 
494  // Otherwise, a catchret reads and writes.
495  return ModRefInfo::ModRef;
496 }
497 
499  const MemoryLocation &Loc) {
500  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
502  return ModRefInfo::ModRef;
503 
504  if (Loc.Ptr) {
505  AliasResult AR = alias(MemoryLocation::get(CX), Loc);
506  // If the cmpxchg address does not alias the location, it does not access
507  // it.
508  if (AR == NoAlias)
509  return ModRefInfo::NoModRef;
510 
511  // If the cmpxchg address aliases the pointer as must alias, set Must.
512  if (AR == MustAlias)
513  return ModRefInfo::MustModRef;
514  }
515 
516  return ModRefInfo::ModRef;
517 }
518 
520  const MemoryLocation &Loc) {
521  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
523  return ModRefInfo::ModRef;
524 
525  if (Loc.Ptr) {
526  AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
527  // If the atomicrmw address does not alias the location, it does not access
528  // it.
529  if (AR == NoAlias)
530  return ModRefInfo::NoModRef;
531 
532  // If the atomicrmw address aliases the pointer as must alias, set Must.
533  if (AR == MustAlias)
534  return ModRefInfo::MustModRef;
535  }
536 
537  return ModRefInfo::ModRef;
538 }
539 
540 /// Return information about whether a particular call site modifies
541 /// or reads the specified memory location \p MemLoc before instruction \p I
542 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
543 /// instruction-ordering queries inside the BasicBlock containing \p I.
544 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
545 /// BasicAA isn't willing to spend linear time determining whether an alloca
546 /// was captured before or after this particular call, while we are. However,
547 /// with a smarter AA in place, this test is just wasting compile time.
549  const MemoryLocation &MemLoc,
550  DominatorTree *DT,
551  OrderedBasicBlock *OBB) {
552  if (!DT)
553  return ModRefInfo::ModRef;
554 
555  const Value *Object =
557  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
558  isa<Constant>(Object))
559  return ModRefInfo::ModRef;
560 
561  ImmutableCallSite CS(I);
562  if (!CS.getInstruction() || CS.getInstruction() == Object)
563  return ModRefInfo::ModRef;
564 
565  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
566  /* StoreCaptures */ true, I, DT,
567  /* include Object */ true,
568  /* OrderedBasicBlock */ OBB))
569  return ModRefInfo::ModRef;
570 
571  unsigned ArgNo = 0;
573  bool IsMustAlias = true;
574  // Set flag only if no May found and all operands processed.
575  for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
576  CI != CE; ++CI, ++ArgNo) {
577  // Only look at the no-capture or byval pointer arguments. If this
578  // pointer were passed to arguments that were neither of these, then it
579  // couldn't be no-capture.
580  if (!(*CI)->getType()->isPointerTy() ||
581  (!CS.doesNotCapture(ArgNo) &&
582  ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
583  continue;
584 
585  AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
586  // If this is a no-capture pointer argument, see if we can tell that it
587  // is impossible to alias the pointer we're checking. If not, we have to
588  // assume that the call could touch the pointer, even though it doesn't
589  // escape.
590  if (AR != MustAlias)
591  IsMustAlias = false;
592  if (AR == NoAlias)
593  continue;
594  if (CS.doesNotAccessMemory(ArgNo))
595  continue;
596  if (CS.onlyReadsMemory(ArgNo)) {
597  R = ModRefInfo::Ref;
598  continue;
599  }
600  // Not returning MustModRef since we have not seen all the arguments.
601  return ModRefInfo::ModRef;
602  }
603  return IsMustAlias ? setMust(R) : clearMust(R);
604 }
605 
606 /// canBasicBlockModify - Return true if it is possible for execution of the
607 /// specified basic block to modify the location Loc.
608 ///
610  const MemoryLocation &Loc) {
611  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
612 }
613 
614 /// canInstructionRangeModRef - Return true if it is possible for the
615 /// execution of the specified instructions to mod\ref (according to the
616 /// mode) the location Loc. The instructions to consider are all
617 /// of the instructions in the range of [I1,I2] INCLUSIVE.
618 /// I1 and I2 must be in the same basic block.
620  const Instruction &I2,
621  const MemoryLocation &Loc,
622  const ModRefInfo Mode) {
623  assert(I1.getParent() == I2.getParent() &&
624  "Instructions not in same basic block!");
627  ++E; // Convert from inclusive to exclusive range.
628 
629  for (; I != E; ++I) // Check every instruction in range
630  if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
631  return true;
632  return false;
633 }
634 
635 // Provide a definition for the root virtual destructor.
636 AAResults::Concept::~Concept() = default;
637 
638 // Provide a definition for the static object used to identify passes.
639 AnalysisKey AAManager::Key;
640 
641 namespace {
642 
643 /// A wrapper pass for external alias analyses. This just squirrels away the
644 /// callback used to run any analyses and register their results.
645 struct ExternalAAWrapperPass : ImmutablePass {
646  using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
647 
648  CallbackT CB;
649 
650  static char ID;
651 
652  ExternalAAWrapperPass() : ImmutablePass(ID) {
654  }
655 
656  explicit ExternalAAWrapperPass(CallbackT CB)
657  : ImmutablePass(ID), CB(std::move(CB)) {
659  }
660 
661  void getAnalysisUsage(AnalysisUsage &AU) const override {
662  AU.setPreservesAll();
663  }
664 };
665 
666 } // end anonymous namespace
667 
669 
670 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
671  false, true)
672 
674 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
675  return new ExternalAAWrapperPass(std::move(Callback));
676 }
677 
680 }
681 
682 char AAResultsWrapperPass::ID = 0;
683 
685  "Function Alias Analysis Results", false, true)
689 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
691 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
696  "Function Alias Analysis Results", false, true)
697 
699  return new AAResultsWrapperPass();
700 }
701 
702 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
703 ///
704 /// This is the legacy pass manager's interface to the new-style AA results
705 /// aggregation object. Because this is somewhat shoe-horned into the legacy
706 /// pass manager, we hard code all the specific alias analyses available into
707 /// it. While the particular set enabled is configured via commandline flags,
708 /// adding a new alias analysis to LLVM will require adding support for it to
709 /// this list.
711  // NB! This *must* be reset before adding new AA results to the new
712  // AAResults object because in the legacy pass manager, each instance
713  // of these will refer to the *same* immutable analyses, registering and
714  // unregistering themselves with them. We need to carefully tear down the
715  // previous object first, in this case replacing it with an empty one, before
716  // registering new results.
717  AAR.reset(
718  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
719 
720  // BasicAA is always available for function analyses. Also, we add it first
721  // so that it can trump TBAA results when it proves MustAlias.
722  // FIXME: TBAA should have an explicit mode to support this and then we
723  // should reconsider the ordering here.
724  if (!DisableBasicAA)
725  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
726 
727  // Populate the results with the currently available AAs.
728  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
729  AAR->addAAResult(WrapperPass->getResult());
730  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
731  AAR->addAAResult(WrapperPass->getResult());
732  if (auto *WrapperPass =
733  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
734  AAR->addAAResult(WrapperPass->getResult());
735  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
736  AAR->addAAResult(WrapperPass->getResult());
737  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
738  AAR->addAAResult(WrapperPass->getResult());
739  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
740  AAR->addAAResult(WrapperPass->getResult());
741  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
742  AAR->addAAResult(WrapperPass->getResult());
743 
744  // If available, run an external AA providing callback over the results as
745  // well.
746  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
747  if (WrapperPass->CB)
748  WrapperPass->CB(*this, F, *AAR);
749 
750  // Analyses don't mutate the IR, so return false.
751  return false;
752 }
753 
755  AU.setPreservesAll();
758 
759  // We also need to mark all the alias analysis passes we will potentially
760  // probe in runOnFunction as used here to ensure the legacy pass manager
761  // preserves them. This hard coding of lists of alias analyses is specific to
762  // the legacy pass manager.
770 }
771 
773  BasicAAResult &BAR) {
775 
776  // Add in our explicitly constructed BasicAA results.
777  if (!DisableBasicAA)
778  AAR.addAAResult(BAR);
779 
780  // Populate the results with the other currently available AAs.
781  if (auto *WrapperPass =
783  AAR.addAAResult(WrapperPass->getResult());
784  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
785  AAR.addAAResult(WrapperPass->getResult());
786  if (auto *WrapperPass =
788  AAR.addAAResult(WrapperPass->getResult());
789  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
790  AAR.addAAResult(WrapperPass->getResult());
791  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
792  AAR.addAAResult(WrapperPass->getResult());
793  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
794  AAR.addAAResult(WrapperPass->getResult());
795 
796  return AAR;
797 }
798 
799 bool llvm::isNoAliasCall(const Value *V) {
800  if (auto CS = ImmutableCallSite(V))
801  return CS.hasRetAttr(Attribute::NoAlias);
802  return false;
803 }
804 
806  if (const Argument *A = dyn_cast<Argument>(V))
807  return A->hasNoAliasAttr();
808  return false;
809 }
810 
812  if (isa<AllocaInst>(V))
813  return true;
814  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
815  return true;
816  if (isNoAliasCall(V))
817  return true;
818  if (const Argument *A = dyn_cast<Argument>(V))
819  return A->hasNoAliasAttr() || A->hasByValAttr();
820  return false;
821 }
822 
824  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
825 }
826 
828  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
829  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
830  // to be added here also.
838 }
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:537
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.
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: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: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:364
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
static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
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:145
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: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:275
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:277
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:763
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: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)
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:2033
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:642
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
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:71
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)