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/CFG.h"
  29 #include "llvm/Analysis/CaptureTracking.h"
  30 #include "llvm/Analysis/TargetLibraryInfo.h"
  31 #include "llvm/Analysis/ValueTracking.h"
  32 #include "llvm/IR/BasicBlock.h"
  33 #include "llvm/IR/DataLayout.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/Instructions.h"
  37 #include "llvm/IR/IntrinsicInst.h"
  38 #include "llvm/IR/LLVMContext.h"
  39 #include "llvm/IR/Type.h"
  40 #include "llvm/Pass.h"
  41 using namespace llvm;
  42
  43 // Register the AliasAnalysis interface, providing a nice name to refer to.
  44 INITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA)
  45 char AliasAnalysis::ID = 0;
  46
  47 //===----------------------------------------------------------------------===//
  48 // Default chaining methods
  49 //===----------------------------------------------------------------------===//
  50
  51 AliasResult AliasAnalysis::alias(const MemoryLocation &LocA,
  52                                  const MemoryLocation &LocB) {
  53   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  54   return AA->alias(LocA, LocB);
  55 }
  56
  57 bool AliasAnalysis::pointsToConstantMemory(const MemoryLocation &Loc,
  58                                            bool OrLocal) {
  59   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  60   return AA->pointsToConstantMemory(Loc, OrLocal);
  61 }
  62
  63 AliasAnalysis::ModRefResult
  64 AliasAnalysis::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
  65   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  66   return AA->getArgModRefInfo(CS, ArgIdx);
  67 }
  68
  69 void AliasAnalysis::deleteValue(Value *V) {
  70   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  71   AA->deleteValue(V);
  72 }
  73
  74 AliasAnalysis::ModRefResult
  75 AliasAnalysis::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
  76   // We may have two calls
  77   if (auto CS = ImmutableCallSite(I)) {
  78     // Check if the two calls modify the same memory
  79     return getModRefInfo(Call, CS);
  80   } else {
  81     // Otherwise, check if the call modifies or references the
  82     // location this memory access defines.  The best we can say
  83     // is that if the call references what this instruction
  84     // defines, it must be clobbered by this location.
  85     const MemoryLocation DefLoc = MemoryLocation::get(I);
  86     if (getModRefInfo(Call, DefLoc) != AliasAnalysis::NoModRef)
  87       return AliasAnalysis::ModRef;
  88   }
  89   return AliasAnalysis::NoModRef;
  90 }
  91
  92 AliasAnalysis::ModRefResult
  93 AliasAnalysis::getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
  94   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  95
  96   ModRefBehavior MRB = getModRefBehavior(CS);
  97   if (MRB == DoesNotAccessMemory)
  98     return NoModRef;
  99
 100   ModRefResult Mask = ModRef;
 101   if (onlyReadsMemory(MRB))
 102     Mask = Ref;
 103
 104   if (onlyAccessesArgPointees(MRB)) {
 105     bool doesAlias = false;
 106     ModRefResult AllArgsMask = NoModRef;
 107     if (doesAccessArgPointees(MRB)) {
 108       for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
 109            AI != AE; ++AI) {
 110         const Value *Arg = *AI;
 111         if (!Arg->getType()->isPointerTy())
 112           continue;
 113         unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
 114         MemoryLocation ArgLoc =
 115             MemoryLocation::getForArgument(CS, ArgIdx, *TLI);
 116         if (!isNoAlias(ArgLoc, Loc)) {
 117           ModRefResult ArgMask = getArgModRefInfo(CS, ArgIdx);
 118           doesAlias = true;
 119           AllArgsMask = ModRefResult(AllArgsMask | ArgMask);
 120         }
 121       }
 122     }
 123     if (!doesAlias)
 124       return NoModRef;
 125     Mask = ModRefResult(Mask & AllArgsMask);
 126   }
 127
 128   // If Loc is a constant memory location, the call definitely could not
 129   // modify the memory location.
 130   if ((Mask & Mod) && pointsToConstantMemory(Loc))
 131     Mask = ModRefResult(Mask & ~Mod);
 132
 133   // If this is the end of the chain, don't forward.
 134   if (!AA) return Mask;
 135
 136   // Otherwise, fall back to the next AA in the chain. But we can merge
 137   // in any mask we've managed to compute.
 138   return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask);
 139 }
 140
 141 AliasAnalysis::ModRefResult
 142 AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
 143   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
 144
 145   // If CS1 or CS2 are readnone, they don't interact.
 146   ModRefBehavior CS1B = getModRefBehavior(CS1);
 147   if (CS1B == DoesNotAccessMemory) return NoModRef;
 148
 149   ModRefBehavior CS2B = getModRefBehavior(CS2);
 150   if (CS2B == DoesNotAccessMemory) return NoModRef;
 151
 152   // If they both only read from memory, there is no dependence.
 153   if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
 154     return NoModRef;
 155
 156   AliasAnalysis::ModRefResult Mask = ModRef;
 157
 158   // If CS1 only reads memory, the only dependence on CS2 can be
 159   // from CS1 reading memory written by CS2.
 160   if (onlyReadsMemory(CS1B))
 161     Mask = ModRefResult(Mask & Ref);
 162
 163   // If CS2 only access memory through arguments, accumulate the mod/ref
 164   // information from CS1's references to the memory referenced by
 165   // CS2's arguments.
 166   if (onlyAccessesArgPointees(CS2B)) {
 167     AliasAnalysis::ModRefResult R = NoModRef;
 168     if (doesAccessArgPointees(CS2B)) {
 169       for (ImmutableCallSite::arg_iterator
 170            I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
 171         const Value *Arg = *I;
 172         if (!Arg->getType()->isPointerTy())
 173           continue;
 174         unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
 175         auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, *TLI);
 176
 177         // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence of
 178         // CS1 on that location is the inverse.
 179         ModRefResult ArgMask = getArgModRefInfo(CS2, CS2ArgIdx);
 180         if (ArgMask == Mod)
 181           ArgMask = ModRef;
 182         else if (ArgMask == Ref)
 183           ArgMask = Mod;
 184
 185         R = ModRefResult((R | (getModRefInfo(CS1, CS2ArgLoc) & ArgMask)) & Mask);
 186         if (R == Mask)
 187           break;
 188       }
 189     }
 190     return R;
 191   }
 192
 193   // If CS1 only accesses memory through arguments, check if CS2 references
 194   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
 195   if (onlyAccessesArgPointees(CS1B)) {
 196     AliasAnalysis::ModRefResult R = NoModRef;
 197     if (doesAccessArgPointees(CS1B)) {
 198       for (ImmutableCallSite::arg_iterator
 199            I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
 200         const Value *Arg = *I;
 201         if (!Arg->getType()->isPointerTy())
 202           continue;
 203         unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
 204         auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, *TLI);
 205
 206         // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
 207         // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
 208         // might Ref, then we care only about a Mod by CS2.
 209         ModRefResult ArgMask = getArgModRefInfo(CS1, CS1ArgIdx);
 210         ModRefResult ArgR = getModRefInfo(CS2, CS1ArgLoc);
 211         if (((ArgMask & Mod) != NoModRef && (ArgR & ModRef) != NoModRef) ||
 212             ((ArgMask & Ref) != NoModRef && (ArgR & Mod)    != NoModRef))
 213           R = ModRefResult((R | ArgMask) & Mask);
 214
 215         if (R == Mask)
 216           break;
 217       }
 218     }
 219     return R;
 220   }
 221
 222   // If this is the end of the chain, don't forward.
 223   if (!AA) return Mask;
 224
 225   // Otherwise, fall back to the next AA in the chain. But we can merge
 226   // in any mask we've managed to compute.
 227   return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
 228 }
 229
 230 AliasAnalysis::ModRefBehavior
 231 AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
 232   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
 233
 234   ModRefBehavior Min = UnknownModRefBehavior;
 235
 236   // Call back into the alias analysis with the other form of getModRefBehavior
 237   // to see if it can give a better response.
 238   if (const Function *F = CS.getCalledFunction())
 239     Min = getModRefBehavior(F);
 240
 241   // If this is the end of the chain, don't forward.
 242   if (!AA) return Min;
 243
 244   // Otherwise, fall back to the next AA in the chain. But we can merge
 245   // in any result we've managed to compute.
 246   return ModRefBehavior(AA->getModRefBehavior(CS) & Min);
 247 }
 248
 249 AliasAnalysis::ModRefBehavior
 250 AliasAnalysis::getModRefBehavior(const Function *F) {
 251   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
 252   return AA->getModRefBehavior(F);
 253 }
 254
 255 //===----------------------------------------------------------------------===//
 256 // AliasAnalysis non-virtual helper method implementation
 257 //===----------------------------------------------------------------------===//
 258
 259 AliasAnalysis::ModRefResult
 260 AliasAnalysis::getModRefInfo(const LoadInst *L, const MemoryLocation &Loc) {
 261   // Be conservative in the face of volatile/atomic.
 262   if (!L->isUnordered())
 263     return ModRef;
 264
 265   // If the load address doesn't alias the given address, it doesn't read
 266   // or write the specified memory.
 267   if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
 268     return NoModRef;
 269
 270   // Otherwise, a load just reads.
 271   return Ref;
 272 }
 273
 274 AliasAnalysis::ModRefResult
 275 AliasAnalysis::getModRefInfo(const StoreInst *S, const MemoryLocation &Loc) {
 276   // Be conservative in the face of volatile/atomic.
 277   if (!S->isUnordered())
 278     return ModRef;
 279
 280   if (Loc.Ptr) {
 281     // If the store address cannot alias the pointer in question, then the
 282     // specified memory cannot be modified by the store.
 283     if (!alias(MemoryLocation::get(S), Loc))
 284       return NoModRef;
 285
 286     // If the pointer is a pointer to constant memory, then it could not have
 287     // been modified by this store.
 288     if (pointsToConstantMemory(Loc))
 289       return NoModRef;
 290
 291   }
 292
 293   // Otherwise, a store just writes.
 294   return Mod;
 295 }
 296
 297 AliasAnalysis::ModRefResult
 298 AliasAnalysis::getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc) {
 299
 300   if (Loc.Ptr) {
 301     // If the va_arg address cannot alias the pointer in question, then the
 302     // specified memory cannot be accessed by the va_arg.
 303     if (!alias(MemoryLocation::get(V), Loc))
 304       return NoModRef;
 305
 306     // If the pointer is a pointer to constant memory, then it could not have
 307     // been modified by this va_arg.
 308     if (pointsToConstantMemory(Loc))
 309       return NoModRef;
 310   }
 311
 312   // Otherwise, a va_arg reads and writes.
 313   return ModRef;
 314 }
 315
 316 AliasAnalysis::ModRefResult
 317 AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX,
 318                              const MemoryLocation &Loc) {
 319   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
 320   if (CX->getSuccessOrdering() > Monotonic)
 321     return ModRef;
 322
 323   // If the cmpxchg address does not alias the location, it does not access it.
 324   if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
 325     return NoModRef;
 326
 327   return ModRef;
 328 }
 329
 330 AliasAnalysis::ModRefResult
 331 AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW,
 332                              const MemoryLocation &Loc) {
 333   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
 334   if (RMW->getOrdering() > Monotonic)
 335     return ModRef;
 336
 337   // If the atomicrmw address does not alias the location, it does not access it.
 338   if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
 339     return NoModRef;
 340
 341   return ModRef;
 342 }
 343
 344 // FIXME: this is really just shoring-up a deficiency in alias analysis.
 345 // BasicAA isn't willing to spend linear time determining whether an alloca
 346 // was captured before or after this particular call, while we are. However,
 347 // with a smarter AA in place, this test is just wasting compile time.
 348 AliasAnalysis::ModRefResult AliasAnalysis::callCapturesBefore(
 349     const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT) {
 350   if (!DT)
 351     return AliasAnalysis::ModRef;
 352
 353   const Value *Object = GetUnderlyingObject(MemLoc.Ptr, *DL);
 354   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
 355       isa<Constant>(Object))
 356     return AliasAnalysis::ModRef;
 357
 358   ImmutableCallSite CS(I);
 359   if (!CS.getInstruction() || CS.getInstruction() == Object)
 360     return AliasAnalysis::ModRef;
 361
 362   if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
 363                                        /* StoreCaptures */ true, I, DT,
 364                                        /* include Object */ true))
 365     return AliasAnalysis::ModRef;
 366
 367   unsigned ArgNo = 0;
 368   AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef;
 369   for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
 370        CI != CE; ++CI, ++ArgNo) {
 371     // Only look at the no-capture or byval pointer arguments.  If this
 372     // pointer were passed to arguments that were neither of these, then it
 373     // couldn't be no-capture.
 374     if (!(*CI)->getType()->isPointerTy() ||
 375         (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
 376       continue;
 377
 378     // If this is a no-capture pointer argument, see if we can tell that it
 379     // is impossible to alias the pointer we're checking.  If not, we have to
 380     // assume that the call could touch the pointer, even though it doesn't
 381     // escape.
 382     if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
 383       continue;
 384     if (CS.doesNotAccessMemory(ArgNo))
 385       continue;
 386     if (CS.onlyReadsMemory(ArgNo)) {
 387       R = AliasAnalysis::Ref;
 388       continue;
 389     }
 390     return AliasAnalysis::ModRef;
 391   }
 392   return R;
 393 }
 394
 395 // AliasAnalysis destructor: DO NOT move this to the header file for
 396 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
 397 // the AliasAnalysis.o file in the current .a file, causing alias analysis
 398 // support to not be included in the tool correctly!
 399 //
 400 AliasAnalysis::~AliasAnalysis() {}
 401
 402 /// InitializeAliasAnalysis - Subclasses must call this method to initialize the
 403 /// AliasAnalysis interface before any other methods are called.
 404 ///
 405 void AliasAnalysis::InitializeAliasAnalysis(Pass *P, const DataLayout *NewDL) {
 406   DL = NewDL;
 407   auto *TLIP = P->getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
 408   TLI = TLIP ? &TLIP->getTLI() : nullptr;
 409   AA = &P->getAnalysis<AliasAnalysis>();
 410 }
 411
 412 // getAnalysisUsage - All alias analysis implementations should invoke this
 413 // directly (using AliasAnalysis::getAnalysisUsage(AU)).
 414 void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 415   AU.addRequired<AliasAnalysis>();         // All AA's chain
 416 }
 417
 418 /// getTypeStoreSize - Return the DataLayout store size for the given type,
 419 /// if known, or a conservative value otherwise.
 420 ///
 421 uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
 422   return DL ? DL->getTypeStoreSize(Ty) : MemoryLocation::UnknownSize;
 423 }
 424
 425 /// canBasicBlockModify - Return true if it is possible for execution of the
 426 /// specified basic block to modify the location Loc.
 427 ///
 428 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
 429                                         const MemoryLocation &Loc) {
 430   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod);
 431 }
 432
 433 /// canInstructionRangeModRef - Return true if it is possible for the
 434 /// execution of the specified instructions to mod\ref (according to the
 435 /// mode) the location Loc. The instructions to consider are all
 436 /// of the instructions in the range of [I1,I2] INCLUSIVE.
 437 /// I1 and I2 must be in the same basic block.
 438 bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1,
 439                                               const Instruction &I2,
 440                                               const MemoryLocation &Loc,
 441                                               const ModRefResult Mode) {
 442   assert(I1.getParent() == I2.getParent() &&
 443          "Instructions not in same basic block!");
 444   BasicBlock::const_iterator I = &I1;
 445   BasicBlock::const_iterator E = &I2;
 446   ++E;  // Convert from inclusive to exclusive range.
 447
 448   for (; I != E; ++I) // Check every instruction in range
 449     if (getModRefInfo(I, Loc) & Mode)
 450       return true;
 451   return false;
 452 }
 453
 454 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 455 /// function.
 456 bool llvm::isNoAliasCall(const Value *V) {
 457   if (isa<CallInst>(V) || isa<InvokeInst>(V))
 458     return ImmutableCallSite(cast<Instruction>(V))
 459       .paramHasAttr(0, Attribute::NoAlias);
 460   return false;
 461 }
 462
 463 /// isNoAliasArgument - Return true if this is an argument with the noalias
 464 /// attribute.
 465 bool llvm::isNoAliasArgument(const Value *V)
 466 {
 467   if (const Argument *A = dyn_cast<Argument>(V))
 468     return A->hasNoAliasAttr();
 469   return false;
 470 }
 471
 472 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
 473 /// identifiable object.  This returns true for:
 474 ///    Global Variables and Functions (but not Global Aliases)
 475 ///    Allocas and Mallocs
 476 ///    ByVal and NoAlias Arguments
 477 ///    NoAlias returns
 478 ///
 479 bool llvm::isIdentifiedObject(const Value *V) {
 480   if (isa<AllocaInst>(V))
 481     return true;
 482   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
 483     return true;
 484   if (isNoAliasCall(V))
 485     return true;
 486   if (const Argument *A = dyn_cast<Argument>(V))
 487     return A->hasNoAliasAttr() || A->hasByValAttr();
 488   return false;
 489 }
 490
 491 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
 492 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
 493 /// Further, an IdentifiedFunctionLocal can not alias with any function
 494 /// arguments other than itself, which is not necessarily true for
 495 /// IdentifiedObjects.
 496 bool llvm::isIdentifiedFunctionLocal(const Value *V)
 497 {
 498   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
 499 }