1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the generic AliasAnalysis interface which is used as the
11 // common interface used by all clients and implementations of alias analysis.
13 // This file also implements the default version of the AliasAnalysis interface
14 // that is to be used when no other implementation is specified. This does some
15 // simple tests that detect obvious cases: two different global pointers cannot
16 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
19 // This alias analysis implementation really isn't very good for anything, but
20 // it is very fast, and makes a nice clean default implementation. Because it
21 // handles lots of little corner cases, other, more complex, alias analysis
22 // implementations may choose to rely on this pass to resolve these simple and
25 //===----------------------------------------------------------------------===//
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/BasicAliasAnalysis.h"
29 #include "llvm/Analysis/CFG.h"
30 #include "llvm/Analysis/CFLAliasAnalysis.h"
31 #include "llvm/Analysis/CaptureTracking.h"
32 #include "llvm/Analysis/GlobalsModRef.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/BasicBlock.h"
40 #include "llvm/IR/DataLayout.h"
41 #include "llvm/IR/Dominators.h"
42 #include "llvm/IR/Function.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/IntrinsicInst.h"
45 #include "llvm/IR/LLVMContext.h"
46 #include "llvm/IR/Type.h"
47 #include "llvm/Pass.h"
50 /// Allow disabling BasicAA from the AA results. This is particularly useful
51 /// when testing to isolate a single AA implementation.
52 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
55 AAResults::AAResults(AAResults &&Arg) : AAs(std::move(Arg.AAs)) {
57 AA->setAAResults(this);
60 AAResults &AAResults::operator=(AAResults &&Arg) {
61 AAs = std::move(Arg.AAs);
63 AA->setAAResults(this);
67 AAResults::~AAResults() {
68 // FIXME; It would be nice to at least clear out the pointers back to this
69 // aggregation here, but we end up with non-nesting lifetimes in the legacy
70 // pass manager that prevent this from working. In the legacy pass manager
71 // we'll end up with dangling references here in some cases.
74 AA->setAAResults(nullptr);
78 //===----------------------------------------------------------------------===//
79 // Default chaining methods
80 //===----------------------------------------------------------------------===//
82 AliasResult AAResults::alias(const MemoryLocation &LocA,
83 const MemoryLocation &LocB) {
84 for (const auto &AA : AAs) {
85 auto Result = AA->alias(LocA, LocB);
86 if (Result != MayAlias)
92 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
94 for (const auto &AA : AAs)
95 if (AA->pointsToConstantMemory(Loc, OrLocal))
101 ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
102 ModRefInfo Result = MRI_ModRef;
104 for (const auto &AA : AAs) {
105 Result = ModRefInfo(Result & AA->getArgModRefInfo(CS, ArgIdx));
107 // Early-exit the moment we reach the bottom of the lattice.
108 if (Result == MRI_NoModRef)
115 ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
116 // We may have two calls
117 if (auto CS = ImmutableCallSite(I)) {
118 // Check if the two calls modify the same memory
119 return getModRefInfo(Call, CS);
121 // Otherwise, check if the call modifies or references the
122 // location this memory access defines. The best we can say
123 // is that if the call references what this instruction
124 // defines, it must be clobbered by this location.
125 const MemoryLocation DefLoc = MemoryLocation::get(I);
126 if (getModRefInfo(Call, DefLoc) != MRI_NoModRef)
132 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS,
133 const MemoryLocation &Loc) {
134 ModRefInfo Result = MRI_ModRef;
136 for (const auto &AA : AAs) {
137 Result = ModRefInfo(Result & AA->getModRefInfo(CS, Loc));
139 // Early-exit the moment we reach the bottom of the lattice.
140 if (Result == MRI_NoModRef)
147 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1,
148 ImmutableCallSite CS2) {
149 ModRefInfo Result = MRI_ModRef;
151 for (const auto &AA : AAs) {
152 Result = ModRefInfo(Result & AA->getModRefInfo(CS1, CS2));
154 // Early-exit the moment we reach the bottom of the lattice.
155 if (Result == MRI_NoModRef)
162 FunctionModRefBehavior AAResults::getModRefBehavior(ImmutableCallSite CS) {
163 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
165 for (const auto &AA : AAs) {
166 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
168 // Early-exit the moment we reach the bottom of the lattice.
169 if (Result == FMRB_DoesNotAccessMemory)
176 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
177 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
179 for (const auto &AA : AAs) {
180 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
182 // Early-exit the moment we reach the bottom of the lattice.
183 if (Result == FMRB_DoesNotAccessMemory)
190 //===----------------------------------------------------------------------===//
191 // Helper method implementation
192 //===----------------------------------------------------------------------===//
194 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
195 const MemoryLocation &Loc) {
196 // Be conservative in the face of volatile/atomic.
197 if (!L->isUnordered())
200 // If the load address doesn't alias the given address, it doesn't read
201 // or write the specified memory.
202 if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
205 // Otherwise, a load just reads.
209 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
210 const MemoryLocation &Loc) {
211 // Be conservative in the face of volatile/atomic.
212 if (!S->isUnordered())
216 // If the store address cannot alias the pointer in question, then the
217 // specified memory cannot be modified by the store.
218 if (!alias(MemoryLocation::get(S), Loc))
221 // If the pointer is a pointer to constant memory, then it could not have
222 // been modified by this store.
223 if (pointsToConstantMemory(Loc))
227 // Otherwise, a store just writes.
231 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
232 const MemoryLocation &Loc) {
235 // If the va_arg address cannot alias the pointer in question, then the
236 // specified memory cannot be accessed by the va_arg.
237 if (!alias(MemoryLocation::get(V), Loc))
240 // If the pointer is a pointer to constant memory, then it could not have
241 // been modified by this va_arg.
242 if (pointsToConstantMemory(Loc))
246 // Otherwise, a va_arg reads and writes.
250 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
251 const MemoryLocation &Loc) {
252 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
253 if (CX->getSuccessOrdering() > Monotonic)
256 // If the cmpxchg address does not alias the location, it does not access it.
257 if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
263 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
264 const MemoryLocation &Loc) {
265 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
266 if (RMW->getOrdering() > Monotonic)
269 // If the atomicrmw address does not alias the location, it does not access it.
270 if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
276 /// \brief Return information about whether a particular call site modifies
277 /// or reads the specified memory location \p MemLoc before instruction \p I
278 /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
279 /// instruction-ordering queries inside the BasicBlock containing \p I.
280 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
281 /// BasicAA isn't willing to spend linear time determining whether an alloca
282 /// was captured before or after this particular call, while we are. However,
283 /// with a smarter AA in place, this test is just wasting compile time.
284 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
285 const MemoryLocation &MemLoc,
287 OrderedBasicBlock *OBB) {
291 const Value *Object =
292 GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
293 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
294 isa<Constant>(Object))
297 ImmutableCallSite CS(I);
298 if (!CS.getInstruction() || CS.getInstruction() == Object)
301 if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
302 /* StoreCaptures */ true, I, DT,
303 /* include Object */ true,
304 /* OrderedBasicBlock */ OBB))
308 ModRefInfo R = MRI_NoModRef;
309 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
310 CI != CE; ++CI, ++ArgNo) {
311 // Only look at the no-capture or byval pointer arguments. If this
312 // pointer were passed to arguments that were neither of these, then it
313 // couldn't be no-capture.
314 if (!(*CI)->getType()->isPointerTy() ||
315 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
318 // If this is a no-capture pointer argument, see if we can tell that it
319 // is impossible to alias the pointer we're checking. If not, we have to
320 // assume that the call could touch the pointer, even though it doesn't
322 if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
324 if (CS.doesNotAccessMemory(ArgNo))
326 if (CS.onlyReadsMemory(ArgNo)) {
335 /// canBasicBlockModify - Return true if it is possible for execution of the
336 /// specified basic block to modify the location Loc.
338 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
339 const MemoryLocation &Loc) {
340 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, MRI_Mod);
343 /// canInstructionRangeModRef - Return true if it is possible for the
344 /// execution of the specified instructions to mod\ref (according to the
345 /// mode) the location Loc. The instructions to consider are all
346 /// of the instructions in the range of [I1,I2] INCLUSIVE.
347 /// I1 and I2 must be in the same basic block.
348 bool AAResults::canInstructionRangeModRef(const Instruction &I1,
349 const Instruction &I2,
350 const MemoryLocation &Loc,
351 const ModRefInfo Mode) {
352 assert(I1.getParent() == I2.getParent() &&
353 "Instructions not in same basic block!");
354 BasicBlock::const_iterator I = &I1;
355 BasicBlock::const_iterator E = &I2;
356 ++E; // Convert from inclusive to exclusive range.
358 for (; I != E; ++I) // Check every instruction in range
359 if (getModRefInfo(I, Loc) & Mode)
364 // Provide a definition for the root virtual destructor.
365 AAResults::Concept::~Concept() {}
367 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
368 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
371 char AAResultsWrapperPass::ID = 0;
373 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
374 "Function Alias Analysis Results", false, true)
375 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
376 INITIALIZE_PASS_DEPENDENCY(CFLAAWrapperPass)
377 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
378 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
379 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
380 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
381 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
382 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
383 "Function Alias Analysis Results", false, true)
385 FunctionPass *llvm::createAAResultsWrapperPass() {
386 return new AAResultsWrapperPass();
389 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
391 /// This is the legacy pass manager's interface to the new-style AA results
392 /// aggregation object. Because this is somewhat shoe-horned into the legacy
393 /// pass manager, we hard code all the specific alias analyses available into
394 /// it. While the particular set enabled is configured via commandline flags,
395 /// adding a new alias analysis to LLVM will require adding support for it to
397 bool AAResultsWrapperPass::runOnFunction(Function &F) {
398 // NB! This *must* be reset before adding new AA results to the new
399 // AAResults object because in the legacy pass manager, each instance
400 // of these will refer to the *same* immutable analyses, registering and
401 // unregistering themselves with them. We need to carefully tear down the
402 // previous object first, in this case replacing it with an empty one, before
403 // registering new results.
404 AAR.reset(new AAResults());
406 // BasicAA is always available for function analyses. Also, we add it first
407 // so that it can trump TBAA results when it proves MustAlias.
408 // FIXME: TBAA should have an explicit mode to support this and then we
409 // should reconsider the ordering here.
411 AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
413 // Populate the results with the currently available AAs.
414 if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
415 AAR->addAAResult(WrapperPass->getResult());
416 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
417 AAR->addAAResult(WrapperPass->getResult());
418 if (auto *WrapperPass =
419 getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
420 AAR->addAAResult(WrapperPass->getResult());
421 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
422 AAR->addAAResult(WrapperPass->getResult());
423 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
424 AAR->addAAResult(WrapperPass->getResult());
425 if (auto *WrapperPass = getAnalysisIfAvailable<CFLAAWrapperPass>())
426 AAR->addAAResult(WrapperPass->getResult());
428 // Analyses don't mutate the IR, so return false.
432 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
433 AU.setPreservesAll();
434 AU.addRequired<BasicAAWrapperPass>();
436 // We also need to mark all the alias analysis passes we will potentially
437 // probe in runOnFunction as used here to ensure the legacy pass manager
438 // preserves them. This hard coding of lists of alias analyses is specific to
439 // the legacy pass manager.
440 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
441 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
442 AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
443 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
444 AU.addUsedIfAvailable<SCEVAAWrapperPass>();
445 AU.addUsedIfAvailable<CFLAAWrapperPass>();
448 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
449 BasicAAResult &BAR) {
452 // Add in our explicitly constructed BasicAA results.
454 AAR.addAAResult(BAR);
456 // Populate the results with the other currently available AAs.
457 if (auto *WrapperPass =
458 P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
459 AAR.addAAResult(WrapperPass->getResult());
460 if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
461 AAR.addAAResult(WrapperPass->getResult());
462 if (auto *WrapperPass =
463 P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
464 AAR.addAAResult(WrapperPass->getResult());
465 if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
466 AAR.addAAResult(WrapperPass->getResult());
467 if (auto *WrapperPass = P.getAnalysisIfAvailable<SCEVAAWrapperPass>())
468 AAR.addAAResult(WrapperPass->getResult());
469 if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAAWrapperPass>())
470 AAR.addAAResult(WrapperPass->getResult());
475 /// isNoAliasCall - Return true if this pointer is returned by a noalias
477 bool llvm::isNoAliasCall(const Value *V) {
478 if (auto CS = ImmutableCallSite(V))
479 return CS.paramHasAttr(0, Attribute::NoAlias);
483 /// isNoAliasArgument - Return true if this is an argument with the noalias
485 bool llvm::isNoAliasArgument(const Value *V)
487 if (const Argument *A = dyn_cast<Argument>(V))
488 return A->hasNoAliasAttr();
492 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
493 /// identifiable object. This returns true for:
494 /// Global Variables and Functions (but not Global Aliases)
495 /// Allocas and Mallocs
496 /// ByVal and NoAlias Arguments
499 bool llvm::isIdentifiedObject(const Value *V) {
500 if (isa<AllocaInst>(V))
502 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
504 if (isNoAliasCall(V))
506 if (const Argument *A = dyn_cast<Argument>(V))
507 return A->hasNoAliasAttr() || A->hasByValAttr();
511 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
512 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
513 /// Further, an IdentifiedFunctionLocal can not alias with any function
514 /// arguments other than itself, which is not necessarily true for
515 /// IdentifiedObjects.
516 bool llvm::isIdentifiedFunctionLocal(const Value *V)
518 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);