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