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  AAQueryInfo AAQIP;
103  return alias(LocA, LocB, AAQIP);
104 }
105 
107  const MemoryLocation &LocB, AAQueryInfo &AAQI) {
108  for (const auto &AA : AAs) {
109  auto Result = AA->alias(LocA, LocB, AAQI);
110  if (Result != MayAlias)
111  return Result;
112  }
113  return MayAlias;
114 }
115 
117  bool OrLocal) {
118  AAQueryInfo AAQIP;
119  return pointsToConstantMemory(Loc, AAQIP, OrLocal);
120 }
121 
123  AAQueryInfo &AAQI, bool OrLocal) {
124  for (const auto &AA : AAs)
125  if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
126  return true;
127 
128  return false;
129 }
130 
131 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
133 
134  for (const auto &AA : AAs) {
135  Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
136 
137  // Early-exit the moment we reach the bottom of the lattice.
138  if (isNoModRef(Result))
139  return ModRefInfo::NoModRef;
140  }
141 
142  return Result;
143 }
144 
146  AAQueryInfo AAQIP;
147  return getModRefInfo(I, Call2, AAQIP);
148 }
149 
151  AAQueryInfo &AAQI) {
152  // We may have two calls.
153  if (const auto *Call1 = dyn_cast<CallBase>(I)) {
154  // Check if the two calls modify the same memory.
155  return getModRefInfo(Call1, Call2, AAQI);
156  } else if (I->isFenceLike()) {
157  // If this is a fence, just return ModRef.
158  return ModRefInfo::ModRef;
159  } else {
160  // Otherwise, check if the call modifies or references the
161  // location this memory access defines. The best we can say
162  // is that if the call references what this instruction
163  // defines, it must be clobbered by this location.
164  const MemoryLocation DefLoc = MemoryLocation::get(I);
165  ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
166  if (isModOrRefSet(MR))
167  return setModAndRef(MR);
168  }
169  return ModRefInfo::NoModRef;
170 }
171 
173  const MemoryLocation &Loc) {
174  AAQueryInfo AAQIP;
175  return getModRefInfo(Call, Loc, AAQIP);
176 }
177 
179  const MemoryLocation &Loc,
180  AAQueryInfo &AAQI) {
182 
183  for (const auto &AA : AAs) {
184  Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc, AAQI));
185 
186  // Early-exit the moment we reach the bottom of the lattice.
187  if (isNoModRef(Result))
188  return ModRefInfo::NoModRef;
189  }
190 
191  // Try to refine the mod-ref info further using other API entry points to the
192  // aggregate set of AA results.
193  auto MRB = getModRefBehavior(Call);
194  if (MRB == FMRB_DoesNotAccessMemory ||
196  return ModRefInfo::NoModRef;
197 
198  if (onlyReadsMemory(MRB))
199  Result = clearMod(Result);
200  else if (doesNotReadMemory(MRB))
201  Result = clearRef(Result);
202 
204  bool IsMustAlias = true;
205  ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
206  if (doesAccessArgPointees(MRB)) {
207  for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
208  const Value *Arg = *AI;
209  if (!Arg->getType()->isPointerTy())
210  continue;
211  unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
212  MemoryLocation ArgLoc =
213  MemoryLocation::getForArgument(Call, ArgIdx, TLI);
214  AliasResult ArgAlias = alias(ArgLoc, Loc);
215  if (ArgAlias != NoAlias) {
216  ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
217  AllArgsMask = unionModRef(AllArgsMask, ArgMask);
218  }
219  // Conservatively clear IsMustAlias unless only MustAlias is found.
220  IsMustAlias &= (ArgAlias == MustAlias);
221  }
222  }
223  // Return NoModRef if no alias found with any argument.
224  if (isNoModRef(AllArgsMask))
225  return ModRefInfo::NoModRef;
226  // Logical & between other AA analyses and argument analysis.
227  Result = intersectModRef(Result, AllArgsMask);
228  // If only MustAlias found above, set Must bit.
229  Result = IsMustAlias ? setMust(Result) : clearMust(Result);
230  }
231 
232  // If Loc is a constant memory location, the call definitely could not
233  // modify the memory location.
234  if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
235  Result = clearMod(Result);
236 
237  return Result;
238 }
239 
241  const CallBase *Call2) {
242  AAQueryInfo AAQIP;
243  return getModRefInfo(Call1, Call2, AAQIP);
244 }
245 
247  const CallBase *Call2, AAQueryInfo &AAQI) {
249 
250  for (const auto &AA : AAs) {
251  Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2, AAQI));
252 
253  // Early-exit the moment we reach the bottom of the lattice.
254  if (isNoModRef(Result))
255  return ModRefInfo::NoModRef;
256  }
257 
258  // Try to refine the mod-ref info further using other API entry points to the
259  // aggregate set of AA results.
260 
261  // If Call1 or Call2 are readnone, they don't interact.
262  auto Call1B = getModRefBehavior(Call1);
263  if (Call1B == FMRB_DoesNotAccessMemory)
264  return ModRefInfo::NoModRef;
265 
266  auto Call2B = getModRefBehavior(Call2);
267  if (Call2B == FMRB_DoesNotAccessMemory)
268  return ModRefInfo::NoModRef;
269 
270  // If they both only read from memory, there is no dependence.
271  if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
272  return ModRefInfo::NoModRef;
273 
274  // If Call1 only reads memory, the only dependence on Call2 can be
275  // from Call1 reading memory written by Call2.
276  if (onlyReadsMemory(Call1B))
277  Result = clearMod(Result);
278  else if (doesNotReadMemory(Call1B))
279  Result = clearRef(Result);
280 
281  // If Call2 only access memory through arguments, accumulate the mod/ref
282  // information from Call1's references to the memory referenced by
283  // Call2's arguments.
284  if (onlyAccessesArgPointees(Call2B)) {
285  if (!doesAccessArgPointees(Call2B))
286  return ModRefInfo::NoModRef;
288  bool IsMustAlias = true;
289  for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
290  const Value *Arg = *I;
291  if (!Arg->getType()->isPointerTy())
292  continue;
293  unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
294  auto Call2ArgLoc =
295  MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
296 
297  // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
298  // dependence of Call1 on that location is the inverse:
299  // - If Call2 modifies location, dependence exists if Call1 reads or
300  // writes.
301  // - If Call2 only reads location, dependence exists if Call1 writes.
302  ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
304  if (isModSet(ArgModRefC2))
305  ArgMask = ModRefInfo::ModRef;
306  else if (isRefSet(ArgModRefC2))
307  ArgMask = ModRefInfo::Mod;
308 
309  // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
310  // above ArgMask to update dependence info.
311  ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
312  ArgMask = intersectModRef(ArgMask, ModRefC1);
313 
314  // Conservatively clear IsMustAlias unless only MustAlias is found.
315  IsMustAlias &= isMustSet(ModRefC1);
316 
317  R = intersectModRef(unionModRef(R, ArgMask), Result);
318  if (R == Result) {
319  // On early exit, not all args were checked, cannot set Must.
320  if (I + 1 != E)
321  IsMustAlias = false;
322  break;
323  }
324  }
325 
326  if (isNoModRef(R))
327  return ModRefInfo::NoModRef;
328 
329  // If MustAlias found above, set Must bit.
330  return IsMustAlias ? setMust(R) : clearMust(R);
331  }
332 
333  // If Call1 only accesses memory through arguments, check if Call2 references
334  // any of the memory referenced by Call1's arguments. If not, return NoModRef.
335  if (onlyAccessesArgPointees(Call1B)) {
336  if (!doesAccessArgPointees(Call1B))
337  return ModRefInfo::NoModRef;
339  bool IsMustAlias = true;
340  for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
341  const Value *Arg = *I;
342  if (!Arg->getType()->isPointerTy())
343  continue;
344  unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
345  auto Call1ArgLoc =
346  MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
347 
348  // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
349  // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
350  // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
351  ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
352  ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
353  if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
354  (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
355  R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
356 
357  // Conservatively clear IsMustAlias unless only MustAlias is found.
358  IsMustAlias &= isMustSet(ModRefC2);
359 
360  if (R == Result) {
361  // On early exit, not all args were checked, cannot set Must.
362  if (I + 1 != E)
363  IsMustAlias = false;
364  break;
365  }
366  }
367 
368  if (isNoModRef(R))
369  return ModRefInfo::NoModRef;
370 
371  // If MustAlias found above, set Must bit.
372  return IsMustAlias ? setMust(R) : clearMust(R);
373  }
374 
375  return Result;
376 }
377 
380 
381  for (const auto &AA : AAs) {
382  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
383 
384  // Early-exit the moment we reach the bottom of the lattice.
385  if (Result == FMRB_DoesNotAccessMemory)
386  return Result;
387  }
388 
389  return Result;
390 }
391 
394 
395  for (const auto &AA : AAs) {
396  Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
397 
398  // Early-exit the moment we reach the bottom of the lattice.
399  if (Result == FMRB_DoesNotAccessMemory)
400  return Result;
401  }
402 
403  return Result;
404 }
405 
407  switch (AR) {
408  case NoAlias:
409  OS << "NoAlias";
410  break;
411  case MustAlias:
412  OS << "MustAlias";
413  break;
414  case MayAlias:
415  OS << "MayAlias";
416  break;
417  case PartialAlias:
418  OS << "PartialAlias";
419  break;
420  }
421  return OS;
422 }
423 
424 //===----------------------------------------------------------------------===//
425 // Helper method implementation
426 //===----------------------------------------------------------------------===//
427 
429  const MemoryLocation &Loc) {
430  AAQueryInfo AAQIP;
431  return getModRefInfo(L, Loc, AAQIP);
432 }
434  const MemoryLocation &Loc,
435  AAQueryInfo &AAQI) {
436  // Be conservative in the face of atomic.
438  return ModRefInfo::ModRef;
439 
440  // If the load address doesn't alias the given address, it doesn't read
441  // or write the specified memory.
442  if (Loc.Ptr) {
443  AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
444  if (AR == NoAlias)
445  return ModRefInfo::NoModRef;
446  if (AR == MustAlias)
447  return ModRefInfo::MustRef;
448  }
449  // Otherwise, a load just reads.
450  return ModRefInfo::Ref;
451 }
452 
454  const MemoryLocation &Loc) {
455  AAQueryInfo AAQIP;
456  return getModRefInfo(S, Loc, AAQIP);
457 }
459  const MemoryLocation &Loc,
460  AAQueryInfo &AAQI) {
461  // Be conservative in the face of atomic.
463  return ModRefInfo::ModRef;
464 
465  if (Loc.Ptr) {
466  AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI);
467  // If the store address cannot alias the pointer in question, then the
468  // specified memory cannot be modified by the store.
469  if (AR == NoAlias)
470  return ModRefInfo::NoModRef;
471 
472  // If the pointer is a pointer to constant memory, then it could not have
473  // been modified by this store.
474  if (pointsToConstantMemory(Loc, AAQI))
475  return ModRefInfo::NoModRef;
476 
477  // If the store address aliases the pointer as must alias, set Must.
478  if (AR == MustAlias)
479  return ModRefInfo::MustMod;
480  }
481 
482  // Otherwise, a store just writes.
483  return ModRefInfo::Mod;
484 }
485 
487  AAQueryInfo AAQIP;
488  return getModRefInfo(S, Loc, AAQIP);
489 }
490 
492  const MemoryLocation &Loc,
493  AAQueryInfo &AAQI) {
494  // If we know that the location is a constant memory location, the fence
495  // cannot modify this location.
496  if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI))
497  return ModRefInfo::Ref;
498  return ModRefInfo::ModRef;
499 }
500 
502  const MemoryLocation &Loc) {
503  AAQueryInfo AAQIP;
504  return getModRefInfo(V, Loc, AAQIP);
505 }
506 
508  const MemoryLocation &Loc,
509  AAQueryInfo &AAQI) {
510  if (Loc.Ptr) {
511  AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
512  // If the va_arg address cannot alias the pointer in question, then the
513  // specified memory cannot be accessed by the va_arg.
514  if (AR == NoAlias)
515  return ModRefInfo::NoModRef;
516 
517  // If the pointer is a pointer to constant memory, then it could not have
518  // been modified by this va_arg.
519  if (pointsToConstantMemory(Loc, AAQI))
520  return ModRefInfo::NoModRef;
521 
522  // If the va_arg aliases the pointer as must alias, set Must.
523  if (AR == MustAlias)
524  return ModRefInfo::MustModRef;
525  }
526 
527  // Otherwise, a va_arg reads and writes.
528  return ModRefInfo::ModRef;
529 }
530 
532  const MemoryLocation &Loc) {
533  AAQueryInfo AAQIP;
534  return getModRefInfo(CatchPad, Loc, AAQIP);
535 }
536 
538  const MemoryLocation &Loc,
539  AAQueryInfo &AAQI) {
540  if (Loc.Ptr) {
541  // If the pointer is a pointer to constant memory,
542  // then it could not have been modified by this catchpad.
543  if (pointsToConstantMemory(Loc, AAQI))
544  return ModRefInfo::NoModRef;
545  }
546 
547  // Otherwise, a catchpad reads and writes.
548  return ModRefInfo::ModRef;
549 }
550 
552  const MemoryLocation &Loc) {
553  AAQueryInfo AAQIP;
554  return getModRefInfo(CatchRet, Loc, AAQIP);
555 }
556 
558  const MemoryLocation &Loc,
559  AAQueryInfo &AAQI) {
560  if (Loc.Ptr) {
561  // If the pointer is a pointer to constant memory,
562  // then it could not have been modified by this catchpad.
563  if (pointsToConstantMemory(Loc, AAQI))
564  return ModRefInfo::NoModRef;
565  }
566 
567  // Otherwise, a catchret reads and writes.
568  return ModRefInfo::ModRef;
569 }
570 
572  const MemoryLocation &Loc) {
573  AAQueryInfo AAQIP;
574  return getModRefInfo(CX, Loc, AAQIP);
575 }
576 
578  const MemoryLocation &Loc,
579  AAQueryInfo &AAQI) {
580  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
582  return ModRefInfo::ModRef;
583 
584  if (Loc.Ptr) {
585  AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI);
586  // If the cmpxchg address does not alias the location, it does not access
587  // it.
588  if (AR == NoAlias)
589  return ModRefInfo::NoModRef;
590 
591  // If the cmpxchg address aliases the pointer as must alias, set Must.
592  if (AR == MustAlias)
593  return ModRefInfo::MustModRef;
594  }
595 
596  return ModRefInfo::ModRef;
597 }
598 
600  const MemoryLocation &Loc) {
601  AAQueryInfo AAQIP;
602  return getModRefInfo(RMW, Loc, AAQIP);
603 }
604 
606  const MemoryLocation &Loc,
607  AAQueryInfo &AAQI) {
608  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
610  return ModRefInfo::ModRef;
611 
612  if (Loc.Ptr) {
613  AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI);
614  // If the atomicrmw address does not alias the location, it does not access
615  // it.
616  if (AR == NoAlias)
617  return ModRefInfo::NoModRef;
618 
619  // If the atomicrmw address aliases the pointer as must alias, set Must.
620  if (AR == MustAlias)
621  return ModRefInfo::MustModRef;
622  }
623 
624  return ModRefInfo::ModRef;
625 }
626 
627 /// Return information about whether a particular call site modifies
628 /// or reads the specified memory location \p MemLoc before instruction \p I
629 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
630 /// instruction-ordering queries inside the BasicBlock containing \p I.
631 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
632 /// BasicAA isn't willing to spend linear time determining whether an alloca
633 /// was captured before or after this particular call, while we are. However,
634 /// with a smarter AA in place, this test is just wasting compile time.
636  const MemoryLocation &MemLoc,
637  DominatorTree *DT,
638  OrderedBasicBlock *OBB) {
639  if (!DT)
640  return ModRefInfo::ModRef;
641 
642  const Value *Object =
644  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
645  isa<Constant>(Object))
646  return ModRefInfo::ModRef;
647 
648  const auto *Call = dyn_cast<CallBase>(I);
649  if (!Call || Call == Object)
650  return ModRefInfo::ModRef;
651 
652  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
653  /* StoreCaptures */ true, I, DT,
654  /* include Object */ true,
655  /* OrderedBasicBlock */ OBB))
656  return ModRefInfo::ModRef;
657 
658  unsigned ArgNo = 0;
660  bool IsMustAlias = true;
661  // Set flag only if no May found and all operands processed.
662  for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
663  CI != CE; ++CI, ++ArgNo) {
664  // Only look at the no-capture or byval pointer arguments. If this
665  // pointer were passed to arguments that were neither of these, then it
666  // couldn't be no-capture.
667  if (!(*CI)->getType()->isPointerTy() ||
668  (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
669  !Call->isByValArgument(ArgNo)))
670  continue;
671 
672  AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
673  // If this is a no-capture pointer argument, see if we can tell that it
674  // is impossible to alias the pointer we're checking. If not, we have to
675  // assume that the call could touch the pointer, even though it doesn't
676  // escape.
677  if (AR != MustAlias)
678  IsMustAlias = false;
679  if (AR == NoAlias)
680  continue;
681  if (Call->doesNotAccessMemory(ArgNo))
682  continue;
683  if (Call->onlyReadsMemory(ArgNo)) {
684  R = ModRefInfo::Ref;
685  continue;
686  }
687  // Not returning MustModRef since we have not seen all the arguments.
688  return ModRefInfo::ModRef;
689  }
690  return IsMustAlias ? setMust(R) : clearMust(R);
691 }
692 
693 /// canBasicBlockModify - Return true if it is possible for execution of the
694 /// specified basic block to modify the location Loc.
695 ///
697  const MemoryLocation &Loc) {
698  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
699 }
700 
701 /// canInstructionRangeModRef - Return true if it is possible for the
702 /// execution of the specified instructions to mod\ref (according to the
703 /// mode) the location Loc. The instructions to consider are all
704 /// of the instructions in the range of [I1,I2] INCLUSIVE.
705 /// I1 and I2 must be in the same basic block.
707  const Instruction &I2,
708  const MemoryLocation &Loc,
709  const ModRefInfo Mode) {
710  assert(I1.getParent() == I2.getParent() &&
711  "Instructions not in same basic block!");
714  ++E; // Convert from inclusive to exclusive range.
715 
716  for (; I != E; ++I) // Check every instruction in range
717  if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
718  return true;
719  return false;
720 }
721 
722 // Provide a definition for the root virtual destructor.
723 AAResults::Concept::~Concept() = default;
724 
725 // Provide a definition for the static object used to identify passes.
726 AnalysisKey AAManager::Key;
727 
728 namespace {
729 
730 
731 } // end anonymous namespace
732 
734 
735 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
736  false, true)
737 
740  return new ExternalAAWrapperPass(std::move(Callback));
741 }
742 
745 }
746 
747 char AAResultsWrapperPass::ID = 0;
748 
750  "Function Alias Analysis Results", false, true)
756 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
761  "Function Alias Analysis Results", false, true)
762 
764  return new AAResultsWrapperPass();
765 }
766 
767 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
768 ///
769 /// This is the legacy pass manager's interface to the new-style AA results
770 /// aggregation object. Because this is somewhat shoe-horned into the legacy
771 /// pass manager, we hard code all the specific alias analyses available into
772 /// it. While the particular set enabled is configured via commandline flags,
773 /// adding a new alias analysis to LLVM will require adding support for it to
774 /// this list.
776  // NB! This *must* be reset before adding new AA results to the new
777  // AAResults object because in the legacy pass manager, each instance
778  // of these will refer to the *same* immutable analyses, registering and
779  // unregistering themselves with them. We need to carefully tear down the
780  // previous object first, in this case replacing it with an empty one, before
781  // registering new results.
782  AAR.reset(
783  new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
784 
785  // BasicAA is always available for function analyses. Also, we add it first
786  // so that it can trump TBAA results when it proves MustAlias.
787  // FIXME: TBAA should have an explicit mode to support this and then we
788  // should reconsider the ordering here.
789  if (!DisableBasicAA)
790  AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
791 
792  // Populate the results with the currently available AAs.
793  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
794  AAR->addAAResult(WrapperPass->getResult());
795  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
796  AAR->addAAResult(WrapperPass->getResult());
797  if (auto *WrapperPass =
798  getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
799  AAR->addAAResult(WrapperPass->getResult());
800  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
801  AAR->addAAResult(WrapperPass->getResult());
802  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
803  AAR->addAAResult(WrapperPass->getResult());
804  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
805  AAR->addAAResult(WrapperPass->getResult());
806  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
807  AAR->addAAResult(WrapperPass->getResult());
808 
809  // If available, run an external AA providing callback over the results as
810  // well.
811  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
812  if (WrapperPass->CB)
813  WrapperPass->CB(*this, F, *AAR);
814 
815  // Analyses don't mutate the IR, so return false.
816  return false;
817 }
818 
820  AU.setPreservesAll();
823 
824  // We also need to mark all the alias analysis passes we will potentially
825  // probe in runOnFunction as used here to ensure the legacy pass manager
826  // preserves them. This hard coding of lists of alias analyses is specific to
827  // the legacy pass manager.
835 }
836 
838  BasicAAResult &BAR) {
840 
841  // Add in our explicitly constructed BasicAA results.
842  if (!DisableBasicAA)
843  AAR.addAAResult(BAR);
844 
845  // Populate the results with the other currently available AAs.
846  if (auto *WrapperPass =
848  AAR.addAAResult(WrapperPass->getResult());
849  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
850  AAR.addAAResult(WrapperPass->getResult());
851  if (auto *WrapperPass =
853  AAR.addAAResult(WrapperPass->getResult());
854  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
855  AAR.addAAResult(WrapperPass->getResult());
856  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
857  AAR.addAAResult(WrapperPass->getResult());
858  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
859  AAR.addAAResult(WrapperPass->getResult());
860 
861  return AAR;
862 }
863 
864 bool llvm::isNoAliasCall(const Value *V) {
865  if (const auto *Call = dyn_cast<CallBase>(V))
866  return Call->hasRetAttr(Attribute::NoAlias);
867  return false;
868 }
869 
871  if (const Argument *A = dyn_cast<Argument>(V))
872  return A->hasNoAliasAttr();
873  return false;
874 }
875 
877  if (isa<AllocaInst>(V))
878  return true;
879  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
880  return true;
881  if (isNoAliasCall(V))
882  return true;
883  if (const Argument *A = dyn_cast<Argument>(V))
884  return A->hasNoAliasAttr() || A->hasByValAttr();
885  return false;
886 }
887 
889  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
890 }
891 
893  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
894  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
895  // to be added here also.
903 }
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)
User::op_iterator data_operands_end()
Definition: InstrTypes.h:1076
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
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1465
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 class stores info we want to provide to or retain within an alias query.
This is the interface for a metadata-based scoped no-alias analysis.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis", false, true) ImmutablePass *llvm
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h: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
User::op_iterator data_operands_begin()
data_operands_begin/data_operands_end - Return iterators iterating over the call / invoke argument li...
Definition: InstrTypes.h:1072
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.
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: InstrTypes.h:1437
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:78
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)
A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
This is the interface for LLVM&#39;s unification-based alias analysis implemented with CFL graph reachabi...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h: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 isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: InstrTypes.h:1442
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
Iterator for intrusive lists based on ilist_node.
INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_END(AAResultsWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h: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...
unsigned getNumArgOperands() const
Definition: InstrTypes.h:1153
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)
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1471
#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:88
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
const BasicBlock * getParent() const
Definition: Instruction.h:66
Legacy wrapper pass to provide the BasicAAResult object.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)