lib/Analysis/AliasAnalysis.cpp

   1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  12 //
  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,
  17 // etc.
  18 //
  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
  23 // easy cases.
  24 //
  25 //===----------------------------------------------------------------------===//
  26
  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"
  48 using namespace llvm;
  49
  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,
  53                                     cl::init(false));
  54
  55 AAResults::AAResults(AAResults &&Arg) : AAs(std::move(Arg.AAs)) {
  56   for (auto &AA : AAs)
  57     AA->setAAResults(this);
  58 }
  59
  60 AAResults &AAResults::operator=(AAResults &&Arg) {
  61   AAs = std::move(Arg.AAs);
  62   for (auto &AA : AAs)
  63     AA->setAAResults(this);
  64   return *this;
  65 }
  66
  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.
  72 #if 0
  73   for (auto &AA : AAs)
  74     AA->setAAResults(nullptr);
  75 #endif
  76 }
  77
  78 //===----------------------------------------------------------------------===//
  79 // Default chaining methods
  80 //===----------------------------------------------------------------------===//
  81
  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)
  87       return Result;
  88   }
  89   return MayAlias;
  90 }
  91
  92 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
  93                                        bool OrLocal) {
  94   for (const auto &AA : AAs)
  95     if (AA->pointsToConstantMemory(Loc, OrLocal))
  96       return true;
  97
  98   return false;
  99 }
 100
 101 ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
 102   ModRefInfo Result = MRI_ModRef;
 103
 104   for (const auto &AA : AAs) {
 105     Result = ModRefInfo(Result & AA->getArgModRefInfo(CS, ArgIdx));
 106
 107     // Early-exit the moment we reach the bottom of the lattice.
 108     if (Result == MRI_NoModRef)
 109       return Result;
 110   }
 111
 112   return Result;
 113 }
 114
 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);
 120   } else {
 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)
 127       return MRI_ModRef;
 128   }
 129   return MRI_NoModRef;
 130 }
 131
 132 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS,
 133                                     const MemoryLocation &Loc) {
 134   ModRefInfo Result = MRI_ModRef;
 135
 136   for (const auto &AA : AAs) {
 137     Result = ModRefInfo(Result & AA->getModRefInfo(CS, Loc));
 138
 139     // Early-exit the moment we reach the bottom of the lattice.
 140     if (Result == MRI_NoModRef)
 141       return Result;
 142   }
 143
 144   return Result;
 145 }
 146
 147 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1,
 148                                     ImmutableCallSite CS2) {
 149   ModRefInfo Result = MRI_ModRef;
 150
 151   for (const auto &AA : AAs) {
 152     Result = ModRefInfo(Result & AA->getModRefInfo(CS1, CS2));
 153
 154     // Early-exit the moment we reach the bottom of the lattice.
 155     if (Result == MRI_NoModRef)
 156       return Result;
 157   }
 158
 159   return Result;
 160 }
 161
 162 FunctionModRefBehavior AAResults::getModRefBehavior(ImmutableCallSite CS) {
 163   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 164
 165   for (const auto &AA : AAs) {
 166     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
 167
 168     // Early-exit the moment we reach the bottom of the lattice.
 169     if (Result == FMRB_DoesNotAccessMemory)
 170       return Result;
 171   }
 172
 173   return Result;
 174 }
 175
 176 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
 177   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 178
 179   for (const auto &AA : AAs) {
 180     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
 181
 182     // Early-exit the moment we reach the bottom of the lattice.
 183     if (Result == FMRB_DoesNotAccessMemory)
 184       return Result;
 185   }
 186
 187   return Result;
 188 }
 189
 190 //===----------------------------------------------------------------------===//
 191 // Helper method implementation
 192 //===----------------------------------------------------------------------===//
 193
 194 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
 195                                     const MemoryLocation &Loc) {
 196   // Be conservative in the face of volatile/atomic.
 197   if (!L->isUnordered())
 198     return MRI_ModRef;
 199
 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))
 203     return MRI_NoModRef;
 204
 205   // Otherwise, a load just reads.
 206   return MRI_Ref;
 207 }
 208
 209 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
 210                                     const MemoryLocation &Loc) {
 211   // Be conservative in the face of volatile/atomic.
 212   if (!S->isUnordered())
 213     return MRI_ModRef;
 214
 215   if (Loc.Ptr) {
 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))
 219       return MRI_NoModRef;
 220
 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))
 224       return MRI_NoModRef;
 225   }
 226
 227   // Otherwise, a store just writes.
 228   return MRI_Mod;
 229 }
 230
 231 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
 232                                     const MemoryLocation &Loc) {
 233
 234   if (Loc.Ptr) {
 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))
 238       return MRI_NoModRef;
 239
 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))
 243       return MRI_NoModRef;
 244   }
 245
 246   // Otherwise, a va_arg reads and writes.
 247   return MRI_ModRef;
 248 }
 249
 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)
 254     return MRI_ModRef;
 255
 256   // If the cmpxchg address does not alias the location, it does not access it.
 257   if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
 258     return MRI_NoModRef;
 259
 260   return MRI_ModRef;
 261 }
 262
 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)
 267     return MRI_ModRef;
 268
 269   // If the atomicrmw address does not alias the location, it does not access it.
 270   if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
 271     return MRI_NoModRef;
 272
 273   return MRI_ModRef;
 274 }
 275
 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,
 286                                          DominatorTree *DT,
 287                                          OrderedBasicBlock *OBB) {
 288   if (!DT)
 289     return MRI_ModRef;
 290
 291   const Value *Object =
 292       GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
 293   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
 294       isa<Constant>(Object))
 295     return MRI_ModRef;
 296
 297   ImmutableCallSite CS(I);
 298   if (!CS.getInstruction() || CS.getInstruction() == Object)
 299     return MRI_ModRef;
 300
 301   if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
 302                                        /* StoreCaptures */ true, I, DT,
 303                                        /* include Object */ true,
 304                                        /* OrderedBasicBlock */ OBB))
 305     return MRI_ModRef;
 306
 307   unsigned ArgNo = 0;
 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)))
 316       continue;
 317
 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
 321     // escape.
 322     if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
 323       continue;
 324     if (CS.doesNotAccessMemory(ArgNo))
 325       continue;
 326     if (CS.onlyReadsMemory(ArgNo)) {
 327       R = MRI_Ref;
 328       continue;
 329     }
 330     return MRI_ModRef;
 331   }
 332   return R;
 333 }
 334
 335 /// canBasicBlockModify - Return true if it is possible for execution of the
 336 /// specified basic block to modify the location Loc.
 337 ///
 338 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
 339                                     const MemoryLocation &Loc) {
 340   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, MRI_Mod);
 341 }
 342
 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.
 357
 358   for (; I != E; ++I) // Check every instruction in range
 359     if (getModRefInfo(I, Loc) & Mode)
 360       return true;
 361   return false;
 362 }
 363
 364 // Provide a definition for the root virtual destructor.
 365 AAResults::Concept::~Concept() {}
 366
 367 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
 368   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 369 }
 370
 371 char AAResultsWrapperPass::ID = 0;
 372
 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)
 384
 385 FunctionPass *llvm::createAAResultsWrapperPass() {
 386   return new AAResultsWrapperPass();
 387 }
 388
 389 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
 390 ///
 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
 396 /// this list.
 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());
 405
 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.
 410   if (!DisableBasicAA)
 411     AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
 412
 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());
 427
 428   // Analyses don't mutate the IR, so return false.
 429   return false;
 430 }
 431
 432 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 433   AU.setPreservesAll();
 434   AU.addRequired<BasicAAWrapperPass>();
 435
 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>();
 446 }
 447
 448 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
 449                                         BasicAAResult &BAR) {
 450   AAResults AAR;
 451
 452   // Add in our explicitly constructed BasicAA results.
 453   if (!DisableBasicAA)
 454     AAR.addAAResult(BAR);
 455
 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());
 471
 472   return AAR;
 473 }
 474
 475 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 476 /// function.
 477 bool llvm::isNoAliasCall(const Value *V) {
 478   if (auto CS = ImmutableCallSite(V))
 479     return CS.paramHasAttr(0, Attribute::NoAlias);
 480   return false;
 481 }
 482
 483 /// isNoAliasArgument - Return true if this is an argument with the noalias
 484 /// attribute.
 485 bool llvm::isNoAliasArgument(const Value *V)
 486 {
 487   if (const Argument *A = dyn_cast<Argument>(V))
 488     return A->hasNoAliasAttr();
 489   return false;
 490 }
 491
 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
 497 ///    NoAlias returns
 498 ///
 499 bool llvm::isIdentifiedObject(const Value *V) {
 500   if (isa<AllocaInst>(V))
 501     return true;
 502   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
 503     return true;
 504   if (isNoAliasCall(V))
 505     return true;
 506   if (const Argument *A = dyn_cast<Argument>(V))
 507     return A->hasNoAliasAttr() || A->hasByValAttr();
 508   return false;
 509 }
 510
 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)
 517 {
 518   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
 519 }