LLVM  9.0.0svn
AliasAnalysis.cpp
Go to the documentation of this file.
1 //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the generic AliasAnalysis interface which is used as the
10 // common interface used by all clients and implementations of alias analysis.
11 //
12 // This file also implements the default version of the AliasAnalysis interface
13 // that is to be used when no other implementation is specified. This does some
14 // simple tests that detect obvious cases: two different global pointers cannot
15 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
16 // etc.
17 //
18 // This alias analysis implementation really isn't very good for anything, but
19 // it is very fast, and makes a nice clean default implementation. Because it
20 // handles lots of little corner cases, other, more complex, alias analysis
21 // implementations may choose to rely on this pass to resolve these simple and
22 // easy cases.
23 //
24 //===----------------------------------------------------------------------===//
25 
39 #include "llvm/IR/Argument.h"
40 #include "llvm/IR/Attributes.h"
41 #include "llvm/IR/BasicBlock.h"
42 #include "llvm/IR/Instruction.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/Pass.h"
49 #include "llvm/Support/Casting.h"
51 #include <algorithm>
52 #include <cassert>
53 #include <functional>
54 #include <iterator>
55 
56 using namespace llvm;
57 
58 /// Allow disabling BasicAA from the AA results. This is particularly useful
59 /// when testing to isolate a single AA implementation.
60 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
61  cl::init(false));
62 
64  : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
65  for (auto &AA : AAs)
66  AA->setAAResults(this);
67 }
68 
70 // FIXME; It would be nice to at least clear out the pointers back to this
71 // aggregation here, but we end up with non-nesting lifetimes in the legacy
72 // pass manager that prevent this from working. In the legacy pass manager
73 // we'll end up with dangling references here in some cases.
74 #if 0
75  for (auto &AA : AAs)
76  AA->setAAResults(nullptr);
77 #endif
78 }
79 
82  // Check if the AA manager itself has been invalidated.
83  auto PAC = PA.getChecker<AAManager>();
84  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
85  return true; // The manager needs to be blown away, clear everything.
86 
87  // Check all of the dependencies registered.
88  for (AnalysisKey *ID : AADeps)
89  if (Inv.invalidate(ID, F, PA))
90  return true;
91 
92  // Everything we depend on is still fine, so are we. Nothing to invalidate.
93  return false;
94 }
95 
96 //===----------------------------------------------------------------------===//
97 // Default chaining methods
98 //===----------------------------------------------------------------------===//
99 
101  const MemoryLocation &LocB) {
102  for (const auto &AA : AAs) {
103  auto Result = AA->alias(LocA, LocB);
104  if (Result != MayAlias)
105  return Result;
106  }
107  return MayAlias;
108 }
109 
111  bool OrLocal) {
112  for (const auto &AA : AAs)
113  if (AA->pointsToConstantMemory(Loc, OrLocal))
114  return true;
115 
116  return false;
117 }
118 
119 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
121 
122  for (const auto &AA : AAs) {
123  Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
124 
125  // Early-exit the moment we reach the bottom of the lattice.
126  if (isNoModRef(Result))
127  return ModRefInfo::NoModRef;
128  }
129 
130  return Result;
131 }
132 
134  // We may have two calls.
135  if (const auto *Call1 = dyn_cast<CallBase>(I)) {
136  // Check if the two calls modify the same memory.
137  return getModRefInfo(Call1, Call2);
138  } else if (I->isFenceLike()) {
139  // If this is a fence, just return ModRef.
140  return ModRefInfo::ModRef;
141  } else {
142  // Otherwise, check if the call modifies or references the
143  // location this memory access defines. The best we can say
144  // is that if the call references what this instruction
145  // defines, it must be clobbered by this location.
146  const MemoryLocation DefLoc = MemoryLocation::get(I);
147  ModRefInfo MR = getModRefInfo(Call2, DefLoc);
148  if (isModOrRefSet(MR))
149  return setModAndRef(MR);
150  }
151  return ModRefInfo::NoModRef;
152 }
153 
155  const MemoryLocation &Loc) {
157 
158  for (const auto &AA : AAs) {
159  Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc));
160 
161  // Early-exit the moment we reach the bottom of the lattice.
162  if (isNoModRef(Result))
163  return ModRefInfo::NoModRef;
164  }
165 
166  // Try to refine the mod-ref info further using other API entry points to the
167  // aggregate set of AA results.
168  auto MRB = getModRefBehavior(Call);
169  if (MRB == FMRB_DoesNotAccessMemory ||
171  return ModRefInfo::NoModRef;
172 
173  if (onlyReadsMemory(MRB))
174  Result = clearMod(Result);
175  else if (doesNotReadMemory(MRB))
176  Result = clearRef(Result);
177 
179  bool IsMustAlias = true;
180  ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
181  if (doesAccessArgPointees(MRB)) {
182  for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
183  const Value *Arg = *AI;
184  if (!Arg->getType()->isPointerTy())
185  continue;
186  unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
187  MemoryLocation ArgLoc =
188  MemoryLocation::getForArgument(Call, ArgIdx, TLI);
189  AliasResult ArgAlias = alias(ArgLoc, Loc);
190  if (ArgAlias != NoAlias) {
191  ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
192  AllArgsMask = unionModRef(AllArgsMask, ArgMask);
193  }
194  // Conservatively clear IsMustAlias unless only MustAlias is found.
195  IsMustAlias &= (ArgAlias == MustAlias);
196  }
197  }
198  // Return NoModRef if no alias found with any argument.
199  if (isNoModRef(AllArgsMask))
200  return ModRefInfo::NoModRef;
201  // Logical & between other AA analyses and argument analysis.
202  Result = intersectModRef(Result, AllArgsMask);
203  // If only MustAlias found above, set Must bit.
204  Result = IsMustAlias ? setMust(Result) : clearMust(Result);
205  }
206 
207  // If Loc is a constant memory location, the call definitely could not
208  // modify the memory location.
209  if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
210  Result = clearMod(Result);
211 
212  return Result;
213 }
214 
216  const CallBase *Call2) {
218 
219  for (const auto &AA : AAs) {
220  Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2));
221 
222  // Early-exit the moment we reach the bottom of the lattice.
223  if (isNoModRef(Result))
224  return ModRefInfo::NoModRef;
225  }
226 
227  // Try to refine the mod-ref info further using other API entry points to the
228  // aggregate set of AA results.
229 
230  // If Call1 or Call2 are readnone, they don't interact.
231  auto Call1B = getModRefBehavior(Call1);
232  if (Call1B == FMRB_DoesNotAccessMemory)
233  return ModRefInfo::NoModRef;
234 
235  auto Call2B = getModRefBehavior(Call2);
236  if (Call2B == FMRB_DoesNotAccessMemory)
237  return ModRefInfo::NoModRef;
238 
239  // If they both only read from memory, there is no dependence.
240  if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
241  return ModRefInfo::NoModRef;
242 
243  // If Call1 only reads memory, the only dependence on Call2 can be
244  // from Call1 reading memory written by Call2.
245  if (onlyReadsMemory(Call1B))
246  Result = clearMod(Result);
247  else if (doesNotReadMemory(Call1B))
248  Result = clearRef(Result);
249 
250  // If Call2 only access memory through arguments, accumulate the mod/ref
251  // information from Call1's references to the memory referenced by
252  // Call2's arguments.
253  if (onlyAccessesArgPointees(Call2B)) {
254  if (!doesAccessArgPointees(Call2B))
255  return ModRefInfo::NoModRef;
257  bool IsMustAlias = true;
258  for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
259  const Value *Arg = *I;
260  if (!Arg->getType()->isPointerTy())
261  continue;
262  unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
263  auto Call2ArgLoc =
264  MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
265 
266  // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
267  // dependence of Call1 on that location is the inverse:
268  // - If Call2 modifies location, dependence exists if Call1 reads or
269  // writes.
270  // - If Call2 only reads location, dependence exists if Call1 writes.
271  ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
273  if (isModSet(ArgModRefC2))
274  ArgMask = ModRefInfo::ModRef;
275  else if (isRefSet(ArgModRefC2))
276  ArgMask = ModRefInfo::Mod;
277 
278  // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
279  // above ArgMask to update dependence info.
280  ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
281  ArgMask = intersectModRef(ArgMask, ModRefC1);
282 
283  // Conservatively clear IsMustAlias unless only MustAlias is found.
284  IsMustAlias &= isMustSet(ModRefC1);
285 
286  R = intersectModRef(unionModRef(R, ArgMask), Result);
287  if (R == Result) {
288  // On early exit, not all args were checked, cannot set Must.
289  if (I + 1 != E)
290  IsMustAlias = false;
291  break;
292  }
293  }
294 
295  if (isNoModRef(R))
296  return ModRefInfo::NoModRef;
297 
298  // If MustAlias found above, set Must bit.
299  return IsMustAlias ? setMust(R) : clearMust(R);
300  }
301 
302  // If Call1 only accesses memory through arguments, check if Call2 references
303  // any of the memory referenced by Call1's arguments. If not, return NoModRef.
304  if (onlyAccessesArgPointees(Call1B)) {
305  if (!doesAccessArgPointees(Call1B))
306  return ModRefInfo::NoModRef;
308  bool IsMustAlias = true;
309  for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
310  const Value *Arg = *I;
311  if (!Arg->getType()->isPointerTy())
312  continue;
313  unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
314  auto Call1ArgLoc =
315  MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
316 
317  // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
318  // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
319  // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
320  ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
321  ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
322  if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
323  (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
324  R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
325 
326  // Conservatively clear IsMustAlias unless only MustAlias is found.
327  IsMustAlias &= isMustSet(ModRefC2);
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(Call));
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  const auto *Call = dyn_cast<CallBase>(I);
564  if (!Call || Call == 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 = Call->data_operands_begin(), CE = Call->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  (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
584  !Call->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 (Call->doesNotAccessMemory(ArgNo))
597  continue;
598  if (Call->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 
646 } // end anonymous namespace
647 
649 
650 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
651  false, true)
652 
655  return new ExternalAAWrapperPass(std::move(Callback));
656 }
657 
660 }
661 
662 char AAResultsWrapperPass::ID = 0;
663 
665  "Function Alias Analysis Results", false, true)
671 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
676  "Function Alias Analysis Results", false, true)
677 
679  return new AAResultsWrapperPass();
680 }
681 
682 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
683 ///
684 /// This is the legacy pass manager's interface to the new-style AA results
685 /// aggregation object. Because this is somewhat shoe-horned into the legacy
686 /// pass manager, we hard code all the specific alias analyses available into
687 /// it. While the particular set enabled is configured via commandline flags,
688 /// adding a new alias analysis to LLVM will require adding support for it to
689 /// this list.
691  // NB! This *must* be reset before adding new AA results to the new
692  // AAResults object because in the legacy pass manager, each instance
693  // of these will refer to the *same* immutable analyses, registering and
694  // unregistering themselves with them. We need to carefully tear down the
695  // previous object first, in this case replacing it with an empty one, before
696  // registering new results.
697  AAR.reset(
698  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
699 
700  // BasicAA is always available for function analyses. Also, we add it first
701  // so that it can trump TBAA results when it proves MustAlias.
702  // FIXME: TBAA should have an explicit mode to support this and then we
703  // should reconsider the ordering here.
704  if (!DisableBasicAA)
705  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
706 
707  // Populate the results with the currently available AAs.
708  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
709  AAR->addAAResult(WrapperPass->getResult());
710  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
711  AAR->addAAResult(WrapperPass->getResult());
712  if (auto *WrapperPass =
713  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
714  AAR->addAAResult(WrapperPass->getResult());
715  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
716  AAR->addAAResult(WrapperPass->getResult());
717  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
718  AAR->addAAResult(WrapperPass->getResult());
719  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
720  AAR->addAAResult(WrapperPass->getResult());
721  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
722  AAR->addAAResult(WrapperPass->getResult());
723 
724  // If available, run an external AA providing callback over the results as
725  // well.
726  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
727  if (WrapperPass->CB)
728  WrapperPass->CB(*this, F, *AAR);
729 
730  // Analyses don't mutate the IR, so return false.
731  return false;
732 }
733 
735  AU.setPreservesAll();
738 
739  // We also need to mark all the alias analysis passes we will potentially
740  // probe in runOnFunction as used here to ensure the legacy pass manager
741  // preserves them. This hard coding of lists of alias analyses is specific to
742  // the legacy pass manager.
750 }
751 
753  BasicAAResult &BAR) {
755 
756  // Add in our explicitly constructed BasicAA results.
757  if (!DisableBasicAA)
758  AAR.addAAResult(BAR);
759 
760  // Populate the results with the other currently available AAs.
761  if (auto *WrapperPass =
763  AAR.addAAResult(WrapperPass->getResult());
764  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
765  AAR.addAAResult(WrapperPass->getResult());
766  if (auto *WrapperPass =
768  AAR.addAAResult(WrapperPass->getResult());
769  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
770  AAR.addAAResult(WrapperPass->getResult());
771  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
772  AAR.addAAResult(WrapperPass->getResult());
773  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
774  AAR.addAAResult(WrapperPass->getResult());
775 
776  return AAR;
777 }
778 
779 bool llvm::isNoAliasCall(const Value *V) {
780  if (const auto *Call = dyn_cast<CallBase>(V))
781  return Call->hasRetAttr(Attribute::NoAlias);
782  return false;
783 }
784 
786  if (const Argument *A = dyn_cast<Argument>(V))
787  return A->hasNoAliasAttr();
788  return false;
789 }
790 
792  if (isa<AllocaInst>(V))
793  return true;
794  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
795  return true;
796  if (isNoAliasCall(V))
797  return true;
798  if (const Argument *A = dyn_cast<Argument>(V))
799  return A->hasNoAliasAttr() || A->hasByValAttr();
800  return false;
801 }
802 
804  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
805 }
806 
808  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
809  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
810  // to be added here also.
818 }
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:80
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:659
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:29
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:554
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:23
This is the interface for a simple mod/ref and alias analysis over globals.
An instruction for ordering other memory operations.
Definition: Instructions.h:454
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:528
This is the interface for a metadata-based scoped no-alias analysis.
The two locations do not alias at all.
Definition: AliasAnalysis.h:83
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:247
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:1126
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:167
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:691
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: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:50
Definition: BitVector.h:937
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:369
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:244
AtomicOrdering getSuccessOrdering() const
Returns the success ordering constraint of this cmpxchg instruction.
Definition: Instructions.h:582
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:320
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:144
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:77
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:422
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:57
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:223
const Instruction & front() const
Definition: BasicBlock.h:280
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:282
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:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
self_iterator getIterator()
Definition: ilist_node.h:81
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:789
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:85
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:89
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:255
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:55
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)
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1120
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:372
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:322
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
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:91
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
LLVM Value Representation.
Definition: Value.h:72
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:45
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:87
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
const BasicBlock * getParent() const
Definition: Instruction.h:66
Legacy wrapper pass to provide the BasicAAResult object.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)