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 
375 //===----------------------------------------------------------------------===//
376 // Helper method implementation
377 //===----------------------------------------------------------------------===//
378 
380  const MemoryLocation &Loc) {
381  // Be conservative in the face of atomic.
383  return ModRefInfo::ModRef;
384 
385  // If the load address doesn't alias the given address, it doesn't read
386  // or write the specified memory.
387  if (Loc.Ptr) {
388  AliasResult AR = alias(MemoryLocation::get(L), Loc);
389  if (AR == NoAlias)
390  return ModRefInfo::NoModRef;
391  if (AR == MustAlias)
392  return ModRefInfo::MustRef;
393  }
394  // Otherwise, a load just reads.
395  return ModRefInfo::Ref;
396 }
397 
399  const MemoryLocation &Loc) {
400  // Be conservative in the face of atomic.
402  return ModRefInfo::ModRef;
403 
404  if (Loc.Ptr) {
405  AliasResult AR = alias(MemoryLocation::get(S), Loc);
406  // If the store address cannot alias the pointer in question, then the
407  // specified memory cannot be modified by the store.
408  if (AR == NoAlias)
409  return ModRefInfo::NoModRef;
410 
411  // If the pointer is a pointer to constant memory, then it could not have
412  // been modified by this store.
413  if (pointsToConstantMemory(Loc))
414  return ModRefInfo::NoModRef;
415 
416  // If the store address aliases the pointer as must alias, set Must.
417  if (AR == MustAlias)
418  return ModRefInfo::MustMod;
419  }
420 
421  // Otherwise, a store just writes.
422  return ModRefInfo::Mod;
423 }
424 
426  // If we know that the location is a constant memory location, the fence
427  // cannot modify this location.
428  if (Loc.Ptr && pointsToConstantMemory(Loc))
429  return ModRefInfo::Ref;
430  return ModRefInfo::ModRef;
431 }
432 
434  const MemoryLocation &Loc) {
435  if (Loc.Ptr) {
436  AliasResult AR = alias(MemoryLocation::get(V), Loc);
437  // If the va_arg address cannot alias the pointer in question, then the
438  // specified memory cannot be accessed by the va_arg.
439  if (AR == NoAlias)
440  return ModRefInfo::NoModRef;
441 
442  // If the pointer is a pointer to constant memory, then it could not have
443  // been modified by this va_arg.
444  if (pointsToConstantMemory(Loc))
445  return ModRefInfo::NoModRef;
446 
447  // If the va_arg aliases the pointer as must alias, set Must.
448  if (AR == MustAlias)
449  return ModRefInfo::MustModRef;
450  }
451 
452  // Otherwise, a va_arg reads and writes.
453  return ModRefInfo::ModRef;
454 }
455 
457  const MemoryLocation &Loc) {
458  if (Loc.Ptr) {
459  // If the pointer is a pointer to constant memory,
460  // then it could not have been modified by this catchpad.
461  if (pointsToConstantMemory(Loc))
462  return ModRefInfo::NoModRef;
463  }
464 
465  // Otherwise, a catchpad reads and writes.
466  return ModRefInfo::ModRef;
467 }
468 
470  const MemoryLocation &Loc) {
471  if (Loc.Ptr) {
472  // If the pointer is a pointer to constant memory,
473  // then it could not have been modified by this catchpad.
474  if (pointsToConstantMemory(Loc))
475  return ModRefInfo::NoModRef;
476  }
477 
478  // Otherwise, a catchret reads and writes.
479  return ModRefInfo::ModRef;
480 }
481 
483  const MemoryLocation &Loc) {
484  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
486  return ModRefInfo::ModRef;
487 
488  if (Loc.Ptr) {
489  AliasResult AR = alias(MemoryLocation::get(CX), Loc);
490  // If the cmpxchg address does not alias the location, it does not access
491  // it.
492  if (AR == NoAlias)
493  return ModRefInfo::NoModRef;
494 
495  // If the cmpxchg address aliases the pointer as must alias, set Must.
496  if (AR == MustAlias)
497  return ModRefInfo::MustModRef;
498  }
499 
500  return ModRefInfo::ModRef;
501 }
502 
504  const MemoryLocation &Loc) {
505  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
507  return ModRefInfo::ModRef;
508 
509  if (Loc.Ptr) {
510  AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
511  // If the atomicrmw address does not alias the location, it does not access
512  // it.
513  if (AR == NoAlias)
514  return ModRefInfo::NoModRef;
515 
516  // If the atomicrmw address aliases the pointer as must alias, set Must.
517  if (AR == MustAlias)
518  return ModRefInfo::MustModRef;
519  }
520 
521  return ModRefInfo::ModRef;
522 }
523 
524 /// \brief Return information about whether a particular call site modifies
525 /// or reads the specified memory location \p MemLoc before instruction \p I
526 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
527 /// instruction-ordering queries inside the BasicBlock containing \p I.
528 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
529 /// BasicAA isn't willing to spend linear time determining whether an alloca
530 /// was captured before or after this particular call, while we are. However,
531 /// with a smarter AA in place, this test is just wasting compile time.
533  const MemoryLocation &MemLoc,
534  DominatorTree *DT,
535  OrderedBasicBlock *OBB) {
536  if (!DT)
537  return ModRefInfo::ModRef;
538 
539  const Value *Object =
541  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
542  isa<Constant>(Object))
543  return ModRefInfo::ModRef;
544 
545  ImmutableCallSite CS(I);
546  if (!CS.getInstruction() || CS.getInstruction() == Object)
547  return ModRefInfo::ModRef;
548 
549  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
550  /* StoreCaptures */ true, I, DT,
551  /* include Object */ true,
552  /* OrderedBasicBlock */ OBB))
553  return ModRefInfo::ModRef;
554 
555  unsigned ArgNo = 0;
557  bool MustAlias = true;
558  // Set flag only if no May found and all operands processed.
559  for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
560  CI != CE; ++CI, ++ArgNo) {
561  // Only look at the no-capture or byval pointer arguments. If this
562  // pointer were passed to arguments that were neither of these, then it
563  // couldn't be no-capture.
564  if (!(*CI)->getType()->isPointerTy() ||
565  (!CS.doesNotCapture(ArgNo) &&
566  ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
567  continue;
568 
569  AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
570  // If this is a no-capture pointer argument, see if we can tell that it
571  // is impossible to alias the pointer we're checking. If not, we have to
572  // assume that the call could touch the pointer, even though it doesn't
573  // escape.
574  if (AR != MustAlias)
575  MustAlias = false;
576  if (AR == NoAlias)
577  continue;
578  if (CS.doesNotAccessMemory(ArgNo))
579  continue;
580  if (CS.onlyReadsMemory(ArgNo)) {
581  R = ModRefInfo::Ref;
582  continue;
583  }
584  // Not returning MustModRef since we have not seen all the arguments.
585  return ModRefInfo::ModRef;
586  }
587  return MustAlias ? setMust(R) : clearMust(R);
588 }
589 
590 /// canBasicBlockModify - Return true if it is possible for execution of the
591 /// specified basic block to modify the location Loc.
592 ///
594  const MemoryLocation &Loc) {
595  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
596 }
597 
598 /// canInstructionRangeModRef - Return true if it is possible for the
599 /// execution of the specified instructions to mod\ref (according to the
600 /// mode) the location Loc. The instructions to consider are all
601 /// of the instructions in the range of [I1,I2] INCLUSIVE.
602 /// I1 and I2 must be in the same basic block.
604  const Instruction &I2,
605  const MemoryLocation &Loc,
606  const ModRefInfo Mode) {
607  assert(I1.getParent() == I2.getParent() &&
608  "Instructions not in same basic block!");
611  ++E; // Convert from inclusive to exclusive range.
612 
613  for (; I != E; ++I) // Check every instruction in range
614  if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
615  return true;
616  return false;
617 }
618 
619 // Provide a definition for the root virtual destructor.
620 AAResults::Concept::~Concept() = default;
621 
622 // Provide a definition for the static object used to identify passes.
623 AnalysisKey AAManager::Key;
624 
625 namespace {
626 
627 /// A wrapper pass for external alias analyses. This just squirrels away the
628 /// callback used to run any analyses and register their results.
629 struct ExternalAAWrapperPass : ImmutablePass {
630  using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
631 
632  CallbackT CB;
633 
634  static char ID;
635 
636  ExternalAAWrapperPass() : ImmutablePass(ID) {
638  }
639 
640  explicit ExternalAAWrapperPass(CallbackT CB)
641  : ImmutablePass(ID), CB(std::move(CB)) {
643  }
644 
645  void getAnalysisUsage(AnalysisUsage &AU) const override {
646  AU.setPreservesAll();
647  }
648 };
649 
650 } // end anonymous namespace
651 
653 
654 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
655  false, true)
656 
658 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
659  return new ExternalAAWrapperPass(std::move(Callback));
660 }
661 
664 }
665 
666 char AAResultsWrapperPass::ID = 0;
667 
669  "Function Alias Analysis Results", false, true)
673 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
675 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
680  "Function Alias Analysis Results", false, true)
681 
683  return new AAResultsWrapperPass();
684 }
685 
686 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
687 ///
688 /// This is the legacy pass manager's interface to the new-style AA results
689 /// aggregation object. Because this is somewhat shoe-horned into the legacy
690 /// pass manager, we hard code all the specific alias analyses available into
691 /// it. While the particular set enabled is configured via commandline flags,
692 /// adding a new alias analysis to LLVM will require adding support for it to
693 /// this list.
695  // NB! This *must* be reset before adding new AA results to the new
696  // AAResults object because in the legacy pass manager, each instance
697  // of these will refer to the *same* immutable analyses, registering and
698  // unregistering themselves with them. We need to carefully tear down the
699  // previous object first, in this case replacing it with an empty one, before
700  // registering new results.
701  AAR.reset(
702  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
703 
704  // BasicAA is always available for function analyses. Also, we add it first
705  // so that it can trump TBAA results when it proves MustAlias.
706  // FIXME: TBAA should have an explicit mode to support this and then we
707  // should reconsider the ordering here.
708  if (!DisableBasicAA)
709  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
710 
711  // Populate the results with the currently available AAs.
712  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
713  AAR->addAAResult(WrapperPass->getResult());
714  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
715  AAR->addAAResult(WrapperPass->getResult());
716  if (auto *WrapperPass =
717  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
718  AAR->addAAResult(WrapperPass->getResult());
719  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
720  AAR->addAAResult(WrapperPass->getResult());
721  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
722  AAR->addAAResult(WrapperPass->getResult());
723  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
724  AAR->addAAResult(WrapperPass->getResult());
725  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
726  AAR->addAAResult(WrapperPass->getResult());
727 
728  // If available, run an external AA providing callback over the results as
729  // well.
730  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
731  if (WrapperPass->CB)
732  WrapperPass->CB(*this, F, *AAR);
733 
734  // Analyses don't mutate the IR, so return false.
735  return false;
736 }
737 
739  AU.setPreservesAll();
742 
743  // We also need to mark all the alias analysis passes we will potentially
744  // probe in runOnFunction as used here to ensure the legacy pass manager
745  // preserves them. This hard coding of lists of alias analyses is specific to
746  // the legacy pass manager.
754 }
755 
757  BasicAAResult &BAR) {
759 
760  // Add in our explicitly constructed BasicAA results.
761  if (!DisableBasicAA)
762  AAR.addAAResult(BAR);
763 
764  // Populate the results with the other currently available AAs.
765  if (auto *WrapperPass =
767  AAR.addAAResult(WrapperPass->getResult());
768  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
769  AAR.addAAResult(WrapperPass->getResult());
770  if (auto *WrapperPass =
772  AAR.addAAResult(WrapperPass->getResult());
773  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
774  AAR.addAAResult(WrapperPass->getResult());
775  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
776  AAR.addAAResult(WrapperPass->getResult());
777  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
778  AAR.addAAResult(WrapperPass->getResult());
779 
780  return AAR;
781 }
782 
783 bool llvm::isNoAliasCall(const Value *V) {
784  if (auto CS = ImmutableCallSite(V))
785  return CS.hasRetAttr(Attribute::NoAlias);
786  return false;
787 }
788 
790  if (const Argument *A = dyn_cast<Argument>(V))
791  return A->hasNoAliasAttr();
792  return false;
793 }
794 
796  if (isa<AllocaInst>(V))
797  return true;
798  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
799  return true;
800  if (isNoAliasCall(V))
801  return true;
802  if (const Argument *A = dyn_cast<Argument>(V))
803  return A->hasNoAliasAttr() || A->hasByValAttr();
804  return false;
805 }
806 
808  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
809 }
810 
812  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
813  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
814  // to be added here also.
822 }
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:515
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
An instruction for ordering other memory operations.
Definition: Instructions.h:440
an instruction that atomically checks whether a specified value is in a memory location, and, if it is, stores a new value there.
Definition: Instructions.h:514
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:233
Function Alias Analysis Results
This is the AA result object for the basic, local, and stateless alias analysis.
bool onlyReadsMemory(ImmutableCallSite CS)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from memory that ...
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:164
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:677
void initializeExternalAAWrapperPassPass(PassRegistry &)
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:568
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:306
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
static cl::opt< bool > DisableBasicAA("disable-basicaa", cl::Hidden, cl::init(false))
Allow disabling BasicAA from the AA results.
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:406
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:221
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:757
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This file declares a simple ARC-aware AliasAnalysis using special knowledge of Objective C to enhance...
This function does not perform any non-local loads or stores to memory.
static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Return a location representing a particular argument of a call.
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
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: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...
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:358
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:713
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
#define I(x, y, z)
Definition: MD5.cpp:58
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:598
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
LLVM Value Representation.
Definition: Value.h:73
Legacy wrapper pass to provide the ObjCARCAAResult object.
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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...
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)