LLVM  mainline
AliasAnalysis.cpp
Go to the documentation of this file.
00001 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the generic AliasAnalysis interface which is used as the
00011 // common interface used by all clients and implementations of alias analysis.
00012 //
00013 // This file also implements the default version of the AliasAnalysis interface
00014 // that is to be used when no other implementation is specified.  This does some
00015 // simple tests that detect obvious cases: two different global pointers cannot
00016 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
00017 // etc.
00018 //
00019 // This alias analysis implementation really isn't very good for anything, but
00020 // it is very fast, and makes a nice clean default implementation.  Because it
00021 // handles lots of little corner cases, other, more complex, alias analysis
00022 // implementations may choose to rely on this pass to resolve these simple and
00023 // easy cases.
00024 //
00025 //===----------------------------------------------------------------------===//
00026 
00027 #include "llvm/Analysis/AliasAnalysis.h"
00028 #include "llvm/Analysis/CFG.h"
00029 #include "llvm/Analysis/CaptureTracking.h"
00030 #include "llvm/Analysis/TargetLibraryInfo.h"
00031 #include "llvm/Analysis/ValueTracking.h"
00032 #include "llvm/IR/BasicBlock.h"
00033 #include "llvm/IR/DataLayout.h"
00034 #include "llvm/IR/Dominators.h"
00035 #include "llvm/IR/Function.h"
00036 #include "llvm/IR/Instructions.h"
00037 #include "llvm/IR/IntrinsicInst.h"
00038 #include "llvm/IR/LLVMContext.h"
00039 #include "llvm/IR/Type.h"
00040 #include "llvm/Pass.h"
00041 using namespace llvm;
00042 
00043 // Register the AliasAnalysis interface, providing a nice name to refer to.
00044 INITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA)
00045 char AliasAnalysis::ID = 0;
00046 
00047 //===----------------------------------------------------------------------===//
00048 // Default chaining methods
00049 //===----------------------------------------------------------------------===//
00050 
00051 AliasResult AliasAnalysis::alias(const MemoryLocation &LocA,
00052                                  const MemoryLocation &LocB) {
00053   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00054   return AA->alias(LocA, LocB);
00055 }
00056 
00057 bool AliasAnalysis::pointsToConstantMemory(const MemoryLocation &Loc,
00058                                            bool OrLocal) {
00059   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00060   return AA->pointsToConstantMemory(Loc, OrLocal);
00061 }
00062 
00063 AliasAnalysis::ModRefResult
00064 AliasAnalysis::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
00065   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00066   return AA->getArgModRefInfo(CS, ArgIdx);
00067 }
00068 
00069 void AliasAnalysis::deleteValue(Value *V) {
00070   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00071   AA->deleteValue(V);
00072 }
00073 
00074 void AliasAnalysis::copyValue(Value *From, Value *To) {
00075   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00076   AA->copyValue(From, To);
00077 }
00078 
00079 void AliasAnalysis::addEscapingUse(Use &U) {
00080   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00081   AA->addEscapingUse(U);
00082 }
00083 
00084 AliasAnalysis::ModRefResult
00085 AliasAnalysis::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
00086   // We may have two calls
00087   if (auto CS = ImmutableCallSite(I)) {
00088     // Check if the two calls modify the same memory
00089     return getModRefInfo(Call, CS);
00090   } else {
00091     // Otherwise, check if the call modifies or references the
00092     // location this memory access defines.  The best we can say
00093     // is that if the call references what this instruction
00094     // defines, it must be clobbered by this location.
00095     const MemoryLocation DefLoc = MemoryLocation::get(I);
00096     if (getModRefInfo(Call, DefLoc) != AliasAnalysis::NoModRef)
00097       return AliasAnalysis::ModRef;
00098   }
00099   return AliasAnalysis::NoModRef;
00100 }
00101 
00102 AliasAnalysis::ModRefResult
00103 AliasAnalysis::getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
00104   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00105 
00106   ModRefBehavior MRB = getModRefBehavior(CS);
00107   if (MRB == DoesNotAccessMemory)
00108     return NoModRef;
00109 
00110   ModRefResult Mask = ModRef;
00111   if (onlyReadsMemory(MRB))
00112     Mask = Ref;
00113 
00114   if (onlyAccessesArgPointees(MRB)) {
00115     bool doesAlias = false;
00116     ModRefResult AllArgsMask = NoModRef;
00117     if (doesAccessArgPointees(MRB)) {
00118       for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
00119            AI != AE; ++AI) {
00120         const Value *Arg = *AI;
00121         if (!Arg->getType()->isPointerTy())
00122           continue;
00123         unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
00124         MemoryLocation ArgLoc =
00125             MemoryLocation::getForArgument(CS, ArgIdx, *TLI);
00126         if (!isNoAlias(ArgLoc, Loc)) {
00127           ModRefResult ArgMask = getArgModRefInfo(CS, ArgIdx);
00128           doesAlias = true;
00129           AllArgsMask = ModRefResult(AllArgsMask | ArgMask);
00130         }
00131       }
00132     }
00133     if (!doesAlias)
00134       return NoModRef;
00135     Mask = ModRefResult(Mask & AllArgsMask);
00136   }
00137 
00138   // If Loc is a constant memory location, the call definitely could not
00139   // modify the memory location.
00140   if ((Mask & Mod) && pointsToConstantMemory(Loc))
00141     Mask = ModRefResult(Mask & ~Mod);
00142 
00143   // If this is the end of the chain, don't forward.
00144   if (!AA) return Mask;
00145 
00146   // Otherwise, fall back to the next AA in the chain. But we can merge
00147   // in any mask we've managed to compute.
00148   return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask);
00149 }
00150 
00151 AliasAnalysis::ModRefResult
00152 AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
00153   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00154 
00155   // If CS1 or CS2 are readnone, they don't interact.
00156   ModRefBehavior CS1B = getModRefBehavior(CS1);
00157   if (CS1B == DoesNotAccessMemory) return NoModRef;
00158 
00159   ModRefBehavior CS2B = getModRefBehavior(CS2);
00160   if (CS2B == DoesNotAccessMemory) return NoModRef;
00161 
00162   // If they both only read from memory, there is no dependence.
00163   if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
00164     return NoModRef;
00165 
00166   AliasAnalysis::ModRefResult Mask = ModRef;
00167 
00168   // If CS1 only reads memory, the only dependence on CS2 can be
00169   // from CS1 reading memory written by CS2.
00170   if (onlyReadsMemory(CS1B))
00171     Mask = ModRefResult(Mask & Ref);
00172 
00173   // If CS2 only access memory through arguments, accumulate the mod/ref
00174   // information from CS1's references to the memory referenced by
00175   // CS2's arguments.
00176   if (onlyAccessesArgPointees(CS2B)) {
00177     AliasAnalysis::ModRefResult R = NoModRef;
00178     if (doesAccessArgPointees(CS2B)) {
00179       for (ImmutableCallSite::arg_iterator
00180            I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
00181         const Value *Arg = *I;
00182         if (!Arg->getType()->isPointerTy())
00183           continue;
00184         unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
00185         auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, *TLI);
00186 
00187         // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence of
00188         // CS1 on that location is the inverse.
00189         ModRefResult ArgMask = getArgModRefInfo(CS2, CS2ArgIdx);
00190         if (ArgMask == Mod)
00191           ArgMask = ModRef;
00192         else if (ArgMask == Ref)
00193           ArgMask = Mod;
00194 
00195         R = ModRefResult((R | (getModRefInfo(CS1, CS2ArgLoc) & ArgMask)) & Mask);
00196         if (R == Mask)
00197           break;
00198       }
00199     }
00200     return R;
00201   }
00202 
00203   // If CS1 only accesses memory through arguments, check if CS2 references
00204   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
00205   if (onlyAccessesArgPointees(CS1B)) {
00206     AliasAnalysis::ModRefResult R = NoModRef;
00207     if (doesAccessArgPointees(CS1B)) {
00208       for (ImmutableCallSite::arg_iterator
00209            I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
00210         const Value *Arg = *I;
00211         if (!Arg->getType()->isPointerTy())
00212           continue;
00213         unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
00214         auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, *TLI);
00215 
00216         // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
00217         // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
00218         // might Ref, then we care only about a Mod by CS2.
00219         ModRefResult ArgMask = getArgModRefInfo(CS1, CS1ArgIdx);
00220         ModRefResult ArgR = getModRefInfo(CS2, CS1ArgLoc);
00221         if (((ArgMask & Mod) != NoModRef && (ArgR & ModRef) != NoModRef) ||
00222             ((ArgMask & Ref) != NoModRef && (ArgR & Mod)    != NoModRef))
00223           R = ModRefResult((R | ArgMask) & Mask);
00224 
00225         if (R == Mask)
00226           break;
00227       }
00228     }
00229     return R;
00230   }
00231 
00232   // If this is the end of the chain, don't forward.
00233   if (!AA) return Mask;
00234 
00235   // Otherwise, fall back to the next AA in the chain. But we can merge
00236   // in any mask we've managed to compute.
00237   return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
00238 }
00239 
00240 AliasAnalysis::ModRefBehavior
00241 AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
00242   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00243 
00244   ModRefBehavior Min = UnknownModRefBehavior;
00245 
00246   // Call back into the alias analysis with the other form of getModRefBehavior
00247   // to see if it can give a better response.
00248   if (const Function *F = CS.getCalledFunction())
00249     Min = getModRefBehavior(F);
00250 
00251   // If this is the end of the chain, don't forward.
00252   if (!AA) return Min;
00253 
00254   // Otherwise, fall back to the next AA in the chain. But we can merge
00255   // in any result we've managed to compute.
00256   return ModRefBehavior(AA->getModRefBehavior(CS) & Min);
00257 }
00258 
00259 AliasAnalysis::ModRefBehavior
00260 AliasAnalysis::getModRefBehavior(const Function *F) {
00261   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
00262   return AA->getModRefBehavior(F);
00263 }
00264 
00265 //===----------------------------------------------------------------------===//
00266 // AliasAnalysis non-virtual helper method implementation
00267 //===----------------------------------------------------------------------===//
00268 
00269 AliasAnalysis::ModRefResult
00270 AliasAnalysis::getModRefInfo(const LoadInst *L, const MemoryLocation &Loc) {
00271   // Be conservative in the face of volatile/atomic.
00272   if (!L->isUnordered())
00273     return ModRef;
00274 
00275   // If the load address doesn't alias the given address, it doesn't read
00276   // or write the specified memory.
00277   if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
00278     return NoModRef;
00279 
00280   // Otherwise, a load just reads.
00281   return Ref;
00282 }
00283 
00284 AliasAnalysis::ModRefResult
00285 AliasAnalysis::getModRefInfo(const StoreInst *S, const MemoryLocation &Loc) {
00286   // Be conservative in the face of volatile/atomic.
00287   if (!S->isUnordered())
00288     return ModRef;
00289 
00290   if (Loc.Ptr) {
00291     // If the store address cannot alias the pointer in question, then the
00292     // specified memory cannot be modified by the store.
00293     if (!alias(MemoryLocation::get(S), Loc))
00294       return NoModRef;
00295 
00296     // If the pointer is a pointer to constant memory, then it could not have
00297     // been modified by this store.
00298     if (pointsToConstantMemory(Loc))
00299       return NoModRef;
00300 
00301   }
00302 
00303   // Otherwise, a store just writes.
00304   return Mod;
00305 }
00306 
00307 AliasAnalysis::ModRefResult
00308 AliasAnalysis::getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc) {
00309 
00310   if (Loc.Ptr) {
00311     // If the va_arg address cannot alias the pointer in question, then the
00312     // specified memory cannot be accessed by the va_arg.
00313     if (!alias(MemoryLocation::get(V), Loc))
00314       return NoModRef;
00315 
00316     // If the pointer is a pointer to constant memory, then it could not have
00317     // been modified by this va_arg.
00318     if (pointsToConstantMemory(Loc))
00319       return NoModRef;
00320   }
00321 
00322   // Otherwise, a va_arg reads and writes.
00323   return ModRef;
00324 }
00325 
00326 AliasAnalysis::ModRefResult
00327 AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX,
00328                              const MemoryLocation &Loc) {
00329   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
00330   if (CX->getSuccessOrdering() > Monotonic)
00331     return ModRef;
00332 
00333   // If the cmpxchg address does not alias the location, it does not access it.
00334   if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
00335     return NoModRef;
00336 
00337   return ModRef;
00338 }
00339 
00340 AliasAnalysis::ModRefResult
00341 AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW,
00342                              const MemoryLocation &Loc) {
00343   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
00344   if (RMW->getOrdering() > Monotonic)
00345     return ModRef;
00346 
00347   // If the atomicrmw address does not alias the location, it does not access it.
00348   if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
00349     return NoModRef;
00350 
00351   return ModRef;
00352 }
00353 
00354 // FIXME: this is really just shoring-up a deficiency in alias analysis.
00355 // BasicAA isn't willing to spend linear time determining whether an alloca
00356 // was captured before or after this particular call, while we are. However,
00357 // with a smarter AA in place, this test is just wasting compile time.
00358 AliasAnalysis::ModRefResult AliasAnalysis::callCapturesBefore(
00359     const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT) {
00360   if (!DT)
00361     return AliasAnalysis::ModRef;
00362 
00363   const Value *Object = GetUnderlyingObject(MemLoc.Ptr, *DL);
00364   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
00365       isa<Constant>(Object))
00366     return AliasAnalysis::ModRef;
00367 
00368   ImmutableCallSite CS(I);
00369   if (!CS.getInstruction() || CS.getInstruction() == Object)
00370     return AliasAnalysis::ModRef;
00371 
00372   if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
00373                                        /* StoreCaptures */ true, I, DT,
00374                                        /* include Object */ true))
00375     return AliasAnalysis::ModRef;
00376 
00377   unsigned ArgNo = 0;
00378   AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef;
00379   for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
00380        CI != CE; ++CI, ++ArgNo) {
00381     // Only look at the no-capture or byval pointer arguments.  If this
00382     // pointer were passed to arguments that were neither of these, then it
00383     // couldn't be no-capture.
00384     if (!(*CI)->getType()->isPointerTy() ||
00385         (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
00386       continue;
00387 
00388     // If this is a no-capture pointer argument, see if we can tell that it
00389     // is impossible to alias the pointer we're checking.  If not, we have to
00390     // assume that the call could touch the pointer, even though it doesn't
00391     // escape.
00392     if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
00393       continue;
00394     if (CS.doesNotAccessMemory(ArgNo))
00395       continue;
00396     if (CS.onlyReadsMemory(ArgNo)) {
00397       R = AliasAnalysis::Ref;
00398       continue;
00399     }
00400     return AliasAnalysis::ModRef;
00401   }
00402   return R;
00403 }
00404 
00405 // AliasAnalysis destructor: DO NOT move this to the header file for
00406 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
00407 // the AliasAnalysis.o file in the current .a file, causing alias analysis
00408 // support to not be included in the tool correctly!
00409 //
00410 AliasAnalysis::~AliasAnalysis() {}
00411 
00412 /// InitializeAliasAnalysis - Subclasses must call this method to initialize the
00413 /// AliasAnalysis interface before any other methods are called.
00414 ///
00415 void AliasAnalysis::InitializeAliasAnalysis(Pass *P, const DataLayout *NewDL) {
00416   DL = NewDL;
00417   auto *TLIP = P->getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
00418   TLI = TLIP ? &TLIP->getTLI() : nullptr;
00419   AA = &P->getAnalysis<AliasAnalysis>();
00420 }
00421 
00422 // getAnalysisUsage - All alias analysis implementations should invoke this
00423 // directly (using AliasAnalysis::getAnalysisUsage(AU)).
00424 void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
00425   AU.addRequired<AliasAnalysis>();         // All AA's chain
00426 }
00427 
00428 /// getTypeStoreSize - Return the DataLayout store size for the given type,
00429 /// if known, or a conservative value otherwise.
00430 ///
00431 uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
00432   return DL ? DL->getTypeStoreSize(Ty) : MemoryLocation::UnknownSize;
00433 }
00434 
00435 /// canBasicBlockModify - Return true if it is possible for execution of the
00436 /// specified basic block to modify the location Loc.
00437 ///
00438 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
00439                                         const MemoryLocation &Loc) {
00440   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod);
00441 }
00442 
00443 /// canInstructionRangeModRef - Return true if it is possible for the
00444 /// execution of the specified instructions to mod\ref (according to the
00445 /// mode) the location Loc. The instructions to consider are all
00446 /// of the instructions in the range of [I1,I2] INCLUSIVE.
00447 /// I1 and I2 must be in the same basic block.
00448 bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1,
00449                                               const Instruction &I2,
00450                                               const MemoryLocation &Loc,
00451                                               const ModRefResult Mode) {
00452   assert(I1.getParent() == I2.getParent() &&
00453          "Instructions not in same basic block!");
00454   BasicBlock::const_iterator I = &I1;
00455   BasicBlock::const_iterator E = &I2;
00456   ++E;  // Convert from inclusive to exclusive range.
00457 
00458   for (; I != E; ++I) // Check every instruction in range
00459     if (getModRefInfo(I, Loc) & Mode)
00460       return true;
00461   return false;
00462 }
00463 
00464 /// isNoAliasCall - Return true if this pointer is returned by a noalias
00465 /// function.
00466 bool llvm::isNoAliasCall(const Value *V) {
00467   if (isa<CallInst>(V) || isa<InvokeInst>(V))
00468     return ImmutableCallSite(cast<Instruction>(V))
00469       .paramHasAttr(0, Attribute::NoAlias);
00470   return false;
00471 }
00472 
00473 /// isNoAliasArgument - Return true if this is an argument with the noalias
00474 /// attribute.
00475 bool llvm::isNoAliasArgument(const Value *V)
00476 {
00477   if (const Argument *A = dyn_cast<Argument>(V))
00478     return A->hasNoAliasAttr();
00479   return false;
00480 }
00481 
00482 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
00483 /// identifiable object.  This returns true for:
00484 ///    Global Variables and Functions (but not Global Aliases)
00485 ///    Allocas and Mallocs
00486 ///    ByVal and NoAlias Arguments
00487 ///    NoAlias returns
00488 ///
00489 bool llvm::isIdentifiedObject(const Value *V) {
00490   if (isa<AllocaInst>(V))
00491     return true;
00492   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
00493     return true;
00494   if (isNoAliasCall(V))
00495     return true;
00496   if (const Argument *A = dyn_cast<Argument>(V))
00497     return A->hasNoAliasAttr() || A->hasByValAttr();
00498   return false;
00499 }
00500 
00501 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
00502 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
00503 /// Further, an IdentifiedFunctionLocal can not alias with any function
00504 /// arguments other than itself, which is not necessarily true for
00505 /// IdentifiedObjects.
00506 bool llvm::isIdentifiedFunctionLocal(const Value *V)
00507 {
00508   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
00509 }