1 //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
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
7 //===----------------------------------------------------------------------===//
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.
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,
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
24 //===----------------------------------------------------------------------===//
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/BasicAliasAnalysis.h"
28 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
29 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
30 #include "llvm/Analysis/CaptureTracking.h"
31 #include "llvm/Analysis/GlobalsModRef.h"
32 #include "llvm/Analysis/MemoryLocation.h"
33 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
34 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
35 #include "llvm/Analysis/ScopedNoAliasAA.h"
36 #include "llvm/Analysis/TargetLibraryInfo.h"
37 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
38 #include "llvm/Analysis/ValueTracking.h"
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/InitializePasses.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/AtomicOrdering.h"
50 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/CommandLine.h"
59 /// Allow disabling BasicAA from the AA results. This is particularly useful
60 /// when testing to isolate a single AA implementation.
61 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
64 AAResults::AAResults(AAResults &&Arg)
65 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
67 AA->setAAResults(this);
70 AAResults::~AAResults() {
71 // FIXME; It would be nice to at least clear out the pointers back to this
72 // aggregation here, but we end up with non-nesting lifetimes in the legacy
73 // pass manager that prevent this from working. In the legacy pass manager
74 // we'll end up with dangling references here in some cases.
77 AA->setAAResults(nullptr);
81 bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
82 FunctionAnalysisManager::Invalidator &Inv) {
83 // AAResults preserves the AAManager by default, due to the stateless nature
84 // of AliasAnalysis. There is no need to check whether it has been preserved
85 // explicitly. Check if any module dependency was invalidated and caused the
86 // AAManager to be invalidated. Invalidate ourselves in that case.
87 auto PAC = PA.getChecker<AAManager>();
88 if (!PAC.preservedWhenStateless())
91 // Check if any of the function dependencies were invalidated, and invalidate
92 // ourselves in that case.
93 for (AnalysisKey *ID : AADeps)
94 if (Inv.invalidate(ID, F, PA))
97 // Everything we depend on is still fine, so are we. Nothing to invalidate.
101 //===----------------------------------------------------------------------===//
102 // Default chaining methods
103 //===----------------------------------------------------------------------===//
105 AliasResult AAResults::alias(const MemoryLocation &LocA,
106 const MemoryLocation &LocB) {
108 return alias(LocA, LocB, AAQIP);
111 AliasResult AAResults::alias(const MemoryLocation &LocA,
112 const MemoryLocation &LocB, AAQueryInfo &AAQI) {
113 for (const auto &AA : AAs) {
114 auto Result = AA->alias(LocA, LocB, AAQI);
115 if (Result != MayAlias)
121 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
124 return pointsToConstantMemory(Loc, AAQIP, OrLocal);
127 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
128 AAQueryInfo &AAQI, bool OrLocal) {
129 for (const auto &AA : AAs)
130 if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
136 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
137 ModRefInfo Result = ModRefInfo::ModRef;
139 for (const auto &AA : AAs) {
140 Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
142 // Early-exit the moment we reach the bottom of the lattice.
143 if (isNoModRef(Result))
144 return ModRefInfo::NoModRef;
150 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) {
152 return getModRefInfo(I, Call2, AAQIP);
155 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
157 // We may have two calls.
158 if (const auto *Call1 = dyn_cast<CallBase>(I)) {
159 // Check if the two calls modify the same memory.
160 return getModRefInfo(Call1, Call2, AAQI);
161 } else if (I->isFenceLike()) {
162 // If this is a fence, just return ModRef.
163 return ModRefInfo::ModRef;
165 // Otherwise, check if the call modifies or references the
166 // location this memory access defines. The best we can say
167 // is that if the call references what this instruction
168 // defines, it must be clobbered by this location.
169 const MemoryLocation DefLoc = MemoryLocation::get(I);
170 ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
171 if (isModOrRefSet(MR))
172 return setModAndRef(MR);
174 return ModRefInfo::NoModRef;
177 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
178 const MemoryLocation &Loc) {
180 return getModRefInfo(Call, Loc, AAQIP);
183 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
184 const MemoryLocation &Loc,
186 ModRefInfo Result = ModRefInfo::ModRef;
188 for (const auto &AA : AAs) {
189 Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc, AAQI));
191 // Early-exit the moment we reach the bottom of the lattice.
192 if (isNoModRef(Result))
193 return ModRefInfo::NoModRef;
196 // Try to refine the mod-ref info further using other API entry points to the
197 // aggregate set of AA results.
198 auto MRB = getModRefBehavior(Call);
199 if (MRB == FMRB_DoesNotAccessMemory ||
200 MRB == FMRB_OnlyAccessesInaccessibleMem)
201 return ModRefInfo::NoModRef;
203 if (onlyReadsMemory(MRB))
204 Result = clearMod(Result);
205 else if (doesNotReadMemory(MRB))
206 Result = clearRef(Result);
208 if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
209 bool IsMustAlias = true;
210 ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
211 if (doesAccessArgPointees(MRB)) {
212 for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
213 const Value *Arg = *AI;
214 if (!Arg->getType()->isPointerTy())
216 unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
217 MemoryLocation ArgLoc =
218 MemoryLocation::getForArgument(Call, ArgIdx, TLI);
219 AliasResult ArgAlias = alias(ArgLoc, Loc);
220 if (ArgAlias != NoAlias) {
221 ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
222 AllArgsMask = unionModRef(AllArgsMask, ArgMask);
224 // Conservatively clear IsMustAlias unless only MustAlias is found.
225 IsMustAlias &= (ArgAlias == MustAlias);
228 // Return NoModRef if no alias found with any argument.
229 if (isNoModRef(AllArgsMask))
230 return ModRefInfo::NoModRef;
231 // Logical & between other AA analyses and argument analysis.
232 Result = intersectModRef(Result, AllArgsMask);
233 // If only MustAlias found above, set Must bit.
234 Result = IsMustAlias ? setMust(Result) : clearMust(Result);
237 // If Loc is a constant memory location, the call definitely could not
238 // modify the memory location.
239 if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
240 Result = clearMod(Result);
245 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
246 const CallBase *Call2) {
248 return getModRefInfo(Call1, Call2, AAQIP);
251 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
252 const CallBase *Call2, AAQueryInfo &AAQI) {
253 ModRefInfo Result = ModRefInfo::ModRef;
255 for (const auto &AA : AAs) {
256 Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2, AAQI));
258 // Early-exit the moment we reach the bottom of the lattice.
259 if (isNoModRef(Result))
260 return ModRefInfo::NoModRef;
263 // Try to refine the mod-ref info further using other API entry points to the
264 // aggregate set of AA results.
266 // If Call1 or Call2 are readnone, they don't interact.
267 auto Call1B = getModRefBehavior(Call1);
268 if (Call1B == FMRB_DoesNotAccessMemory)
269 return ModRefInfo::NoModRef;
271 auto Call2B = getModRefBehavior(Call2);
272 if (Call2B == FMRB_DoesNotAccessMemory)
273 return ModRefInfo::NoModRef;
275 // If they both only read from memory, there is no dependence.
276 if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
277 return ModRefInfo::NoModRef;
279 // If Call1 only reads memory, the only dependence on Call2 can be
280 // from Call1 reading memory written by Call2.
281 if (onlyReadsMemory(Call1B))
282 Result = clearMod(Result);
283 else if (doesNotReadMemory(Call1B))
284 Result = clearRef(Result);
286 // If Call2 only access memory through arguments, accumulate the mod/ref
287 // information from Call1's references to the memory referenced by
288 // Call2's arguments.
289 if (onlyAccessesArgPointees(Call2B)) {
290 if (!doesAccessArgPointees(Call2B))
291 return ModRefInfo::NoModRef;
292 ModRefInfo R = ModRefInfo::NoModRef;
293 bool IsMustAlias = true;
294 for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
295 const Value *Arg = *I;
296 if (!Arg->getType()->isPointerTy())
298 unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
300 MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
302 // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
303 // dependence of Call1 on that location is the inverse:
304 // - If Call2 modifies location, dependence exists if Call1 reads or
306 // - If Call2 only reads location, dependence exists if Call1 writes.
307 ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
308 ModRefInfo ArgMask = ModRefInfo::NoModRef;
309 if (isModSet(ArgModRefC2))
310 ArgMask = ModRefInfo::ModRef;
311 else if (isRefSet(ArgModRefC2))
312 ArgMask = ModRefInfo::Mod;
314 // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
315 // above ArgMask to update dependence info.
316 ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
317 ArgMask = intersectModRef(ArgMask, ModRefC1);
319 // Conservatively clear IsMustAlias unless only MustAlias is found.
320 IsMustAlias &= isMustSet(ModRefC1);
322 R = intersectModRef(unionModRef(R, ArgMask), Result);
324 // On early exit, not all args were checked, cannot set Must.
332 return ModRefInfo::NoModRef;
334 // If MustAlias found above, set Must bit.
335 return IsMustAlias ? setMust(R) : clearMust(R);
338 // If Call1 only accesses memory through arguments, check if Call2 references
339 // any of the memory referenced by Call1's arguments. If not, return NoModRef.
340 if (onlyAccessesArgPointees(Call1B)) {
341 if (!doesAccessArgPointees(Call1B))
342 return ModRefInfo::NoModRef;
343 ModRefInfo R = ModRefInfo::NoModRef;
344 bool IsMustAlias = true;
345 for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
346 const Value *Arg = *I;
347 if (!Arg->getType()->isPointerTy())
349 unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
351 MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
353 // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
354 // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
355 // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
356 ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
357 ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
358 if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
359 (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
360 R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
362 // Conservatively clear IsMustAlias unless only MustAlias is found.
363 IsMustAlias &= isMustSet(ModRefC2);
366 // On early exit, not all args were checked, cannot set Must.
374 return ModRefInfo::NoModRef;
376 // If MustAlias found above, set Must bit.
377 return IsMustAlias ? setMust(R) : clearMust(R);
383 FunctionModRefBehavior AAResults::getModRefBehavior(const CallBase *Call) {
384 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
386 for (const auto &AA : AAs) {
387 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
389 // Early-exit the moment we reach the bottom of the lattice.
390 if (Result == FMRB_DoesNotAccessMemory)
397 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
398 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
400 for (const auto &AA : AAs) {
401 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
403 // Early-exit the moment we reach the bottom of the lattice.
404 if (Result == FMRB_DoesNotAccessMemory)
411 raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
423 OS << "PartialAlias";
429 //===----------------------------------------------------------------------===//
430 // Helper method implementation
431 //===----------------------------------------------------------------------===//
433 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
434 const MemoryLocation &Loc) {
436 return getModRefInfo(L, Loc, AAQIP);
438 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
439 const MemoryLocation &Loc,
441 // Be conservative in the face of atomic.
442 if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
443 return ModRefInfo::ModRef;
445 // If the load address doesn't alias the given address, it doesn't read
446 // or write the specified memory.
448 AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
450 return ModRefInfo::NoModRef;
452 return ModRefInfo::MustRef;
454 // Otherwise, a load just reads.
455 return ModRefInfo::Ref;
458 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
459 const MemoryLocation &Loc) {
461 return getModRefInfo(S, Loc, AAQIP);
463 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
464 const MemoryLocation &Loc,
466 // Be conservative in the face of atomic.
467 if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
468 return ModRefInfo::ModRef;
471 AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI);
472 // If the store address cannot alias the pointer in question, then the
473 // specified memory cannot be modified by the store.
475 return ModRefInfo::NoModRef;
477 // If the pointer is a pointer to constant memory, then it could not have
478 // been modified by this store.
479 if (pointsToConstantMemory(Loc, AAQI))
480 return ModRefInfo::NoModRef;
482 // If the store address aliases the pointer as must alias, set Must.
484 return ModRefInfo::MustMod;
487 // Otherwise, a store just writes.
488 return ModRefInfo::Mod;
491 ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
493 return getModRefInfo(S, Loc, AAQIP);
496 ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
497 const MemoryLocation &Loc,
499 // If we know that the location is a constant memory location, the fence
500 // cannot modify this location.
501 if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI))
502 return ModRefInfo::Ref;
503 return ModRefInfo::ModRef;
506 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
507 const MemoryLocation &Loc) {
509 return getModRefInfo(V, Loc, AAQIP);
512 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
513 const MemoryLocation &Loc,
516 AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
517 // If the va_arg address cannot alias the pointer in question, then the
518 // specified memory cannot be accessed by the va_arg.
520 return ModRefInfo::NoModRef;
522 // If the pointer is a pointer to constant memory, then it could not have
523 // been modified by this va_arg.
524 if (pointsToConstantMemory(Loc, AAQI))
525 return ModRefInfo::NoModRef;
527 // If the va_arg aliases the pointer as must alias, set Must.
529 return ModRefInfo::MustModRef;
532 // Otherwise, a va_arg reads and writes.
533 return ModRefInfo::ModRef;
536 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
537 const MemoryLocation &Loc) {
539 return getModRefInfo(CatchPad, Loc, AAQIP);
542 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
543 const MemoryLocation &Loc,
546 // If the pointer is a pointer to constant memory,
547 // then it could not have been modified by this catchpad.
548 if (pointsToConstantMemory(Loc, AAQI))
549 return ModRefInfo::NoModRef;
552 // Otherwise, a catchpad reads and writes.
553 return ModRefInfo::ModRef;
556 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
557 const MemoryLocation &Loc) {
559 return getModRefInfo(CatchRet, Loc, AAQIP);
562 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
563 const MemoryLocation &Loc,
566 // If the pointer is a pointer to constant memory,
567 // then it could not have been modified by this catchpad.
568 if (pointsToConstantMemory(Loc, AAQI))
569 return ModRefInfo::NoModRef;
572 // Otherwise, a catchret reads and writes.
573 return ModRefInfo::ModRef;
576 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
577 const MemoryLocation &Loc) {
579 return getModRefInfo(CX, Loc, AAQIP);
582 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
583 const MemoryLocation &Loc,
585 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
586 if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
587 return ModRefInfo::ModRef;
590 AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI);
591 // If the cmpxchg address does not alias the location, it does not access
594 return ModRefInfo::NoModRef;
596 // If the cmpxchg address aliases the pointer as must alias, set Must.
598 return ModRefInfo::MustModRef;
601 return ModRefInfo::ModRef;
604 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
605 const MemoryLocation &Loc) {
607 return getModRefInfo(RMW, Loc, AAQIP);
610 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
611 const MemoryLocation &Loc,
613 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
614 if (isStrongerThanMonotonic(RMW->getOrdering()))
615 return ModRefInfo::ModRef;
618 AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI);
619 // If the atomicrmw address does not alias the location, it does not access
622 return ModRefInfo::NoModRef;
624 // If the atomicrmw address aliases the pointer as must alias, set Must.
626 return ModRefInfo::MustModRef;
629 return ModRefInfo::ModRef;
632 /// Return information about whether a particular call site modifies
633 /// or reads the specified memory location \p MemLoc before instruction \p I
634 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
635 /// instruction-ordering queries inside the BasicBlock containing \p I.
636 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
637 /// BasicAA isn't willing to spend linear time determining whether an alloca
638 /// was captured before or after this particular call, while we are. However,
639 /// with a smarter AA in place, this test is just wasting compile time.
640 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
641 const MemoryLocation &MemLoc,
643 OrderedBasicBlock *OBB) {
645 return ModRefInfo::ModRef;
647 const Value *Object =
648 GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
649 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
650 isa<Constant>(Object))
651 return ModRefInfo::ModRef;
653 const auto *Call = dyn_cast<CallBase>(I);
654 if (!Call || Call == Object)
655 return ModRefInfo::ModRef;
657 if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
658 /* StoreCaptures */ true, I, DT,
659 /* include Object */ true,
660 /* OrderedBasicBlock */ OBB))
661 return ModRefInfo::ModRef;
664 ModRefInfo R = ModRefInfo::NoModRef;
665 bool IsMustAlias = true;
666 // Set flag only if no May found and all operands processed.
667 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
668 CI != CE; ++CI, ++ArgNo) {
669 // Only look at the no-capture or byval pointer arguments. If this
670 // pointer were passed to arguments that were neither of these, then it
671 // couldn't be no-capture.
672 if (!(*CI)->getType()->isPointerTy() ||
673 (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
674 !Call->isByValArgument(ArgNo)))
677 AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
678 // If this is a no-capture pointer argument, see if we can tell that it
679 // is impossible to alias the pointer we're checking. If not, we have to
680 // assume that the call could touch the pointer, even though it doesn't
686 if (Call->doesNotAccessMemory(ArgNo))
688 if (Call->onlyReadsMemory(ArgNo)) {
692 // Not returning MustModRef since we have not seen all the arguments.
693 return ModRefInfo::ModRef;
695 return IsMustAlias ? setMust(R) : clearMust(R);
698 /// canBasicBlockModify - Return true if it is possible for execution of the
699 /// specified basic block to modify the location Loc.
701 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
702 const MemoryLocation &Loc) {
703 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
706 /// canInstructionRangeModRef - Return true if it is possible for the
707 /// execution of the specified instructions to mod\ref (according to the
708 /// mode) the location Loc. The instructions to consider are all
709 /// of the instructions in the range of [I1,I2] INCLUSIVE.
710 /// I1 and I2 must be in the same basic block.
711 bool AAResults::canInstructionRangeModRef(const Instruction &I1,
712 const Instruction &I2,
713 const MemoryLocation &Loc,
714 const ModRefInfo Mode) {
715 assert(I1.getParent() == I2.getParent() &&
716 "Instructions not in same basic block!");
717 BasicBlock::const_iterator I = I1.getIterator();
718 BasicBlock::const_iterator E = I2.getIterator();
719 ++E; // Convert from inclusive to exclusive range.
721 for (; I != E; ++I) // Check every instruction in range
722 if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
727 // Provide a definition for the root virtual destructor.
728 AAResults::Concept::~Concept() = default;
730 // Provide a definition for the static object used to identify passes.
731 AnalysisKey AAManager::Key;
736 } // end anonymous namespace
738 ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {
739 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
742 ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB)
743 : ImmutablePass(ID), CB(std::move(CB)) {
744 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
747 char ExternalAAWrapperPass::ID = 0;
749 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
753 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
754 return new ExternalAAWrapperPass(std::move(Callback));
757 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
758 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
761 char AAResultsWrapperPass::ID = 0;
763 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
764 "Function Alias Analysis Results", false, true)
765 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
766 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
767 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
768 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
769 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
770 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
771 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
772 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
773 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
774 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
775 "Function Alias Analysis Results", false, true)
777 FunctionPass *llvm::createAAResultsWrapperPass() {
778 return new AAResultsWrapperPass();
781 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
783 /// This is the legacy pass manager's interface to the new-style AA results
784 /// aggregation object. Because this is somewhat shoe-horned into the legacy
785 /// pass manager, we hard code all the specific alias analyses available into
786 /// it. While the particular set enabled is configured via commandline flags,
787 /// adding a new alias analysis to LLVM will require adding support for it to
789 bool AAResultsWrapperPass::runOnFunction(Function &F) {
790 // NB! This *must* be reset before adding new AA results to the new
791 // AAResults object because in the legacy pass manager, each instance
792 // of these will refer to the *same* immutable analyses, registering and
793 // unregistering themselves with them. We need to carefully tear down the
794 // previous object first, in this case replacing it with an empty one, before
795 // registering new results.
797 new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
799 // BasicAA is always available for function analyses. Also, we add it first
800 // so that it can trump TBAA results when it proves MustAlias.
801 // FIXME: TBAA should have an explicit mode to support this and then we
802 // should reconsider the ordering here.
804 AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
806 // Populate the results with the currently available AAs.
807 if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
808 AAR->addAAResult(WrapperPass->getResult());
809 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
810 AAR->addAAResult(WrapperPass->getResult());
811 if (auto *WrapperPass =
812 getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
813 AAR->addAAResult(WrapperPass->getResult());
814 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
815 AAR->addAAResult(WrapperPass->getResult());
816 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
817 AAR->addAAResult(WrapperPass->getResult());
818 if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
819 AAR->addAAResult(WrapperPass->getResult());
820 if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
821 AAR->addAAResult(WrapperPass->getResult());
823 // If available, run an external AA providing callback over the results as
825 if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
827 WrapperPass->CB(*this, F, *AAR);
829 // Analyses don't mutate the IR, so return false.
833 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
834 AU.setPreservesAll();
835 AU.addRequired<BasicAAWrapperPass>();
836 AU.addRequired<TargetLibraryInfoWrapperPass>();
838 // We also need to mark all the alias analysis passes we will potentially
839 // probe in runOnFunction as used here to ensure the legacy pass manager
840 // preserves them. This hard coding of lists of alias analyses is specific to
841 // the legacy pass manager.
842 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
843 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
844 AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
845 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
846 AU.addUsedIfAvailable<SCEVAAWrapperPass>();
847 AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
848 AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
849 AU.addUsedIfAvailable<ExternalAAWrapperPass>();
852 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
853 BasicAAResult &BAR) {
854 AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F));
856 // Add in our explicitly constructed BasicAA results.
858 AAR.addAAResult(BAR);
860 // Populate the results with the other currently available AAs.
861 if (auto *WrapperPass =
862 P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
863 AAR.addAAResult(WrapperPass->getResult());
864 if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
865 AAR.addAAResult(WrapperPass->getResult());
866 if (auto *WrapperPass =
867 P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
868 AAR.addAAResult(WrapperPass->getResult());
869 if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
870 AAR.addAAResult(WrapperPass->getResult());
871 if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
872 AAR.addAAResult(WrapperPass->getResult());
873 if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
874 AAR.addAAResult(WrapperPass->getResult());
875 if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>())
877 WrapperPass->CB(P, F, AAR);
882 bool llvm::isNoAliasCall(const Value *V) {
883 if (const auto *Call = dyn_cast<CallBase>(V))
884 return Call->hasRetAttr(Attribute::NoAlias);
888 bool llvm::isNoAliasArgument(const Value *V) {
889 if (const Argument *A = dyn_cast<Argument>(V))
890 return A->hasNoAliasAttr();
894 bool llvm::isIdentifiedObject(const Value *V) {
895 if (isa<AllocaInst>(V))
897 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
899 if (isNoAliasCall(V))
901 if (const Argument *A = dyn_cast<Argument>(V))
902 return A->hasNoAliasAttr() || A->hasByValAttr();
906 bool llvm::isIdentifiedFunctionLocal(const Value *V) {
907 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
910 void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
911 // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
912 // more alias analyses are added to llvm::createLegacyPMAAResults, they need
913 // to be added here also.
914 AU.addRequired<TargetLibraryInfoWrapperPass>();
915 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
916 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
917 AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
918 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
919 AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
920 AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
921 AU.addUsedIfAvailable<ExternalAAWrapperPass>();