contrib/llvm/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/CFLAndersAliasAnalysis.h"
  30 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
  31 #include "llvm/Analysis/CaptureTracking.h"
  32 #include "llvm/Analysis/GlobalsModRef.h"
  33 #include "llvm/Analysis/MemoryLocation.h"
  34 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
  35 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  36 #include "llvm/Analysis/ScopedNoAliasAA.h"
  37 #include "llvm/Analysis/TargetLibraryInfo.h"
  38 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
  39 #include "llvm/Analysis/ValueTracking.h"
  40 #include "llvm/IR/Argument.h"
  41 #include "llvm/IR/Attributes.h"
  42 #include "llvm/IR/BasicBlock.h"
  43 #include "llvm/IR/CallSite.h"
  44 #include "llvm/IR/Instruction.h"
  45 #include "llvm/IR/Instructions.h"
  46 #include "llvm/IR/Module.h"
  47 #include "llvm/IR/Type.h"
  48 #include "llvm/IR/Value.h"
  49 #include "llvm/Pass.h"
  50 #include "llvm/Support/AtomicOrdering.h"
  51 #include "llvm/Support/Casting.h"
  52 #include "llvm/Support/CommandLine.h"
  53 #include <algorithm>
  54 #include <cassert>
  55 #include <functional>
  56 #include <iterator>
  57
  58 using namespace llvm;
  59
  60 /// Allow disabling BasicAA from the AA results. This is particularly useful
  61 /// when testing to isolate a single AA implementation.
  62 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
  63                                     cl::init(false));
  64
  65 AAResults::AAResults(AAResults &&Arg)
  66     : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
  67   for (auto &AA : AAs)
  68     AA->setAAResults(this);
  69 }
  70
  71 AAResults::~AAResults() {
  72 // FIXME; It would be nice to at least clear out the pointers back to this
  73 // aggregation here, but we end up with non-nesting lifetimes in the legacy
  74 // pass manager that prevent this from working. In the legacy pass manager
  75 // we'll end up with dangling references here in some cases.
  76 #if 0
  77   for (auto &AA : AAs)
  78     AA->setAAResults(nullptr);
  79 #endif
  80 }
  81
  82 bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
  83                            FunctionAnalysisManager::Invalidator &Inv) {
  84   // Check if the AA manager itself has been invalidated.
  85   auto PAC = PA.getChecker<AAManager>();
  86   if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
  87     return true; // The manager needs to be blown away, clear everything.
  88
  89   // Check all of the dependencies registered.
  90   for (AnalysisKey *ID : AADeps)
  91     if (Inv.invalidate(ID, F, PA))
  92       return true;
  93
  94   // Everything we depend on is still fine, so are we. Nothing to invalidate.
  95   return false;
  96 }
  97
  98 //===----------------------------------------------------------------------===//
  99 // Default chaining methods
 100 //===----------------------------------------------------------------------===//
 101
 102 AliasResult AAResults::alias(const MemoryLocation &LocA,
 103                              const MemoryLocation &LocB) {
 104   for (const auto &AA : AAs) {
 105     auto Result = AA->alias(LocA, LocB);
 106     if (Result != MayAlias)
 107       return Result;
 108   }
 109   return MayAlias;
 110 }
 111
 112 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
 113                                        bool OrLocal) {
 114   for (const auto &AA : AAs)
 115     if (AA->pointsToConstantMemory(Loc, OrLocal))
 116       return true;
 117
 118   return false;
 119 }
 120
 121 ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
 122   ModRefInfo Result = ModRefInfo::ModRef;
 123
 124   for (const auto &AA : AAs) {
 125     Result = intersectModRef(Result, AA->getArgModRefInfo(CS, ArgIdx));
 126
 127     // Early-exit the moment we reach the bottom of the lattice.
 128     if (isNoModRef(Result))
 129       return Result;
 130   }
 131
 132   return Result;
 133 }
 134
 135 ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
 136   // We may have two calls
 137   if (auto CS = ImmutableCallSite(I)) {
 138     // Check if the two calls modify the same memory
 139     return getModRefInfo(CS, Call);
 140   } else if (I->isFenceLike()) {
 141     // If this is a fence, just return ModRef.
 142     return ModRefInfo::ModRef;
 143   } else {
 144     // Otherwise, check if the call modifies or references the
 145     // location this memory access defines.  The best we can say
 146     // is that if the call references what this instruction
 147     // defines, it must be clobbered by this location.
 148     const MemoryLocation DefLoc = MemoryLocation::get(I);
 149     ModRefInfo MR = getModRefInfo(Call, DefLoc);
 150     if (isModOrRefSet(MR))
 151       return setModAndRef(MR);
 152   }
 153   return ModRefInfo::NoModRef;
 154 }
 155
 156 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS,
 157                                     const MemoryLocation &Loc) {
 158   ModRefInfo Result = ModRefInfo::ModRef;
 159
 160   for (const auto &AA : AAs) {
 161     Result = intersectModRef(Result, AA->getModRefInfo(CS, Loc));
 162
 163     // Early-exit the moment we reach the bottom of the lattice.
 164     if (isNoModRef(Result))
 165       return Result;
 166   }
 167
 168   // Try to refine the mod-ref info further using other API entry points to the
 169   // aggregate set of AA results.
 170   auto MRB = getModRefBehavior(CS);
 171   if (MRB == FMRB_DoesNotAccessMemory ||
 172       MRB == FMRB_OnlyAccessesInaccessibleMem)
 173     return ModRefInfo::NoModRef;
 174
 175   if (onlyReadsMemory(MRB))
 176     Result = clearMod(Result);
 177   else if (doesNotReadMemory(MRB))
 178     Result = clearRef(Result);
 179
 180   if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
 181     bool DoesAlias = false;
 182     ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
 183     if (doesAccessArgPointees(MRB)) {
 184       for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
 185         const Value *Arg = *AI;
 186         if (!Arg->getType()->isPointerTy())
 187           continue;
 188         unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
 189         MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
 190         AliasResult ArgAlias = alias(ArgLoc, Loc);
 191         if (ArgAlias != NoAlias) {
 192           ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
 193           DoesAlias = true;
 194           AllArgsMask = unionModRef(AllArgsMask, ArgMask);
 195         }
 196       }
 197     }
 198     // Return NoModRef if no alias found with any argument.
 199     if (!DoesAlias)
 200       return ModRefInfo::NoModRef;
 201     // Logical & between other AA analyses and argument analysis.
 202     Result = intersectModRef(Result, AllArgsMask);
 203   }
 204
 205   // If Loc is a constant memory location, the call definitely could not
 206   // modify the memory location.
 207   if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
 208     Result = clearMod(Result);
 209
 210   return Result;
 211 }
 212
 213 ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1,
 214                                     ImmutableCallSite CS2) {
 215   ModRefInfo Result = ModRefInfo::ModRef;
 216
 217   for (const auto &AA : AAs) {
 218     Result = intersectModRef(Result, AA->getModRefInfo(CS1, CS2));
 219
 220     // Early-exit the moment we reach the bottom of the lattice.
 221     if (isNoModRef(Result))
 222       return Result;
 223   }
 224
 225   // Try to refine the mod-ref info further using other API entry points to the
 226   // aggregate set of AA results.
 227
 228   // If CS1 or CS2 are readnone, they don't interact.
 229   auto CS1B = getModRefBehavior(CS1);
 230   if (CS1B == FMRB_DoesNotAccessMemory)
 231     return ModRefInfo::NoModRef;
 232
 233   auto CS2B = getModRefBehavior(CS2);
 234   if (CS2B == FMRB_DoesNotAccessMemory)
 235     return ModRefInfo::NoModRef;
 236
 237   // If they both only read from memory, there is no dependence.
 238   if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
 239     return ModRefInfo::NoModRef;
 240
 241   // If CS1 only reads memory, the only dependence on CS2 can be
 242   // from CS1 reading memory written by CS2.
 243   if (onlyReadsMemory(CS1B))
 244     Result = clearMod(Result);
 245   else if (doesNotReadMemory(CS1B))
 246     Result = clearRef(Result);
 247
 248   // If CS2 only access memory through arguments, accumulate the mod/ref
 249   // information from CS1's references to the memory referenced by
 250   // CS2's arguments.
 251   if (onlyAccessesArgPointees(CS2B)) {
 252     ModRefInfo R = ModRefInfo::NoModRef;
 253     if (doesAccessArgPointees(CS2B)) {
 254       for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
 255         const Value *Arg = *I;
 256         if (!Arg->getType()->isPointerTy())
 257           continue;
 258         unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
 259         auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
 260
 261         // ArgModRefCS2 indicates what CS2 might do to CS2ArgLoc, and the
 262         // dependence of CS1 on that location is the inverse:
 263         // - If CS2 modifies location, dependence exists if CS1 reads or writes.
 264         // - If CS2 only reads location, dependence exists if CS1 writes.
 265         ModRefInfo ArgModRefCS2 = getArgModRefInfo(CS2, CS2ArgIdx);
 266         ModRefInfo ArgMask = ModRefInfo::NoModRef;
 267         if (isModSet(ArgModRefCS2))
 268           ArgMask = ModRefInfo::ModRef;
 269         else if (isRefSet(ArgModRefCS2))
 270           ArgMask = ModRefInfo::Mod;
 271
 272         // ModRefCS1 indicates what CS1 might do to CS2ArgLoc, and we use
 273         // above ArgMask to update dependence info.
 274         ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc);
 275         ArgMask = intersectModRef(ArgMask, ModRefCS1);
 276
 277         R = intersectModRef(unionModRef(R, ArgMask), Result);
 278         if (R == Result)
 279           break;
 280       }
 281     }
 282     return R;
 283   }
 284
 285   // If CS1 only accesses memory through arguments, check if CS2 references
 286   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
 287   if (onlyAccessesArgPointees(CS1B)) {
 288     ModRefInfo R = ModRefInfo::NoModRef;
 289     if (doesAccessArgPointees(CS1B)) {
 290       for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
 291         const Value *Arg = *I;
 292         if (!Arg->getType()->isPointerTy())
 293           continue;
 294         unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
 295         auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
 296
 297         // ArgModRefCS1 indicates what CS1 might do to CS1ArgLoc; if CS1 might
 298         // Mod CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If
 299         // CS1 might Ref, then we care only about a Mod by CS2.
 300         ModRefInfo ArgModRefCS1 = getArgModRefInfo(CS1, CS1ArgIdx);
 301         ModRefInfo ModRefCS2 = getModRefInfo(CS2, CS1ArgLoc);
 302         if ((isModSet(ArgModRefCS1) && isModOrRefSet(ModRefCS2)) ||
 303             (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2)))
 304           R = intersectModRef(unionModRef(R, ArgModRefCS1), Result);
 305
 306         if (R == Result)
 307           break;
 308       }
 309     }
 310     return R;
 311   }
 312
 313   return Result;
 314 }
 315
 316 FunctionModRefBehavior AAResults::getModRefBehavior(ImmutableCallSite CS) {
 317   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 318
 319   for (const auto &AA : AAs) {
 320     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
 321
 322     // Early-exit the moment we reach the bottom of the lattice.
 323     if (Result == FMRB_DoesNotAccessMemory)
 324       return Result;
 325   }
 326
 327   return Result;
 328 }
 329
 330 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
 331   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 332
 333   for (const auto &AA : AAs) {
 334     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
 335
 336     // Early-exit the moment we reach the bottom of the lattice.
 337     if (Result == FMRB_DoesNotAccessMemory)
 338       return Result;
 339   }
 340
 341   return Result;
 342 }
 343
 344 //===----------------------------------------------------------------------===//
 345 // Helper method implementation
 346 //===----------------------------------------------------------------------===//
 347
 348 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
 349                                     const MemoryLocation &Loc) {
 350   // Be conservative in the face of atomic.
 351   if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
 352     return ModRefInfo::ModRef;
 353
 354   // If the load address doesn't alias the given address, it doesn't read
 355   // or write the specified memory.
 356   if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
 357     return ModRefInfo::NoModRef;
 358
 359   // Otherwise, a load just reads.
 360   return ModRefInfo::Ref;
 361 }
 362
 363 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
 364                                     const MemoryLocation &Loc) {
 365   // Be conservative in the face of atomic.
 366   if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
 367     return ModRefInfo::ModRef;
 368
 369   if (Loc.Ptr) {
 370     // If the store address cannot alias the pointer in question, then the
 371     // specified memory cannot be modified by the store.
 372     if (!alias(MemoryLocation::get(S), Loc))
 373       return ModRefInfo::NoModRef;
 374
 375     // If the pointer is a pointer to constant memory, then it could not have
 376     // been modified by this store.
 377     if (pointsToConstantMemory(Loc))
 378       return ModRefInfo::NoModRef;
 379   }
 380
 381   // Otherwise, a store just writes.
 382   return ModRefInfo::Mod;
 383 }
 384
 385 ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
 386   // If we know that the location is a constant memory location, the fence
 387   // cannot modify this location.
 388   if (Loc.Ptr && pointsToConstantMemory(Loc))
 389     return ModRefInfo::Ref;
 390   return ModRefInfo::ModRef;
 391 }
 392
 393 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
 394                                     const MemoryLocation &Loc) {
 395   if (Loc.Ptr) {
 396     // If the va_arg address cannot alias the pointer in question, then the
 397     // specified memory cannot be accessed by the va_arg.
 398     if (!alias(MemoryLocation::get(V), Loc))
 399       return ModRefInfo::NoModRef;
 400
 401     // If the pointer is a pointer to constant memory, then it could not have
 402     // been modified by this va_arg.
 403     if (pointsToConstantMemory(Loc))
 404       return ModRefInfo::NoModRef;
 405   }
 406
 407   // Otherwise, a va_arg reads and writes.
 408   return ModRefInfo::ModRef;
 409 }
 410
 411 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
 412                                     const MemoryLocation &Loc) {
 413   if (Loc.Ptr) {
 414     // If the pointer is a pointer to constant memory,
 415     // then it could not have been modified by this catchpad.
 416     if (pointsToConstantMemory(Loc))
 417       return ModRefInfo::NoModRef;
 418   }
 419
 420   // Otherwise, a catchpad reads and writes.
 421   return ModRefInfo::ModRef;
 422 }
 423
 424 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
 425                                     const MemoryLocation &Loc) {
 426   if (Loc.Ptr) {
 427     // If the pointer is a pointer to constant memory,
 428     // then it could not have been modified by this catchpad.
 429     if (pointsToConstantMemory(Loc))
 430       return ModRefInfo::NoModRef;
 431   }
 432
 433   // Otherwise, a catchret reads and writes.
 434   return ModRefInfo::ModRef;
 435 }
 436
 437 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
 438                                     const MemoryLocation &Loc) {
 439   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
 440   if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
 441     return ModRefInfo::ModRef;
 442
 443   // If the cmpxchg address does not alias the location, it does not access it.
 444   if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc))
 445     return ModRefInfo::NoModRef;
 446
 447   return ModRefInfo::ModRef;
 448 }
 449
 450 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
 451                                     const MemoryLocation &Loc) {
 452   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
 453   if (isStrongerThanMonotonic(RMW->getOrdering()))
 454     return ModRefInfo::ModRef;
 455
 456   // If the atomicrmw address does not alias the location, it does not access it.
 457   if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
 458     return ModRefInfo::NoModRef;
 459
 460   return ModRefInfo::ModRef;
 461 }
 462
 463 /// \brief Return information about whether a particular call site modifies
 464 /// or reads the specified memory location \p MemLoc before instruction \p I
 465 /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
 466 /// instruction-ordering queries inside the BasicBlock containing \p I.
 467 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
 468 /// BasicAA isn't willing to spend linear time determining whether an alloca
 469 /// was captured before or after this particular call, while we are. However,
 470 /// with a smarter AA in place, this test is just wasting compile time.
 471 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
 472                                          const MemoryLocation &MemLoc,
 473                                          DominatorTree *DT,
 474                                          OrderedBasicBlock *OBB) {
 475   if (!DT)
 476     return ModRefInfo::ModRef;
 477
 478   const Value *Object =
 479       GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
 480   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
 481       isa<Constant>(Object))
 482     return ModRefInfo::ModRef;
 483
 484   ImmutableCallSite CS(I);
 485   if (!CS.getInstruction() || CS.getInstruction() == Object)
 486     return ModRefInfo::ModRef;
 487
 488   if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
 489                                  /* StoreCaptures */ true, I, DT,
 490                                  /* include Object */ true,
 491                                  /* OrderedBasicBlock */ OBB))
 492     return ModRefInfo::ModRef;
 493
 494   unsigned ArgNo = 0;
 495   ModRefInfo R = ModRefInfo::NoModRef;
 496   for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
 497        CI != CE; ++CI, ++ArgNo) {
 498     // Only look at the no-capture or byval pointer arguments.  If this
 499     // pointer were passed to arguments that were neither of these, then it
 500     // couldn't be no-capture.
 501     if (!(*CI)->getType()->isPointerTy() ||
 502         (!CS.doesNotCapture(ArgNo) &&
 503          ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
 504       continue;
 505
 506     // If this is a no-capture pointer argument, see if we can tell that it
 507     // is impossible to alias the pointer we're checking.  If not, we have to
 508     // assume that the call could touch the pointer, even though it doesn't
 509     // escape.
 510     if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object)))
 511       continue;
 512     if (CS.doesNotAccessMemory(ArgNo))
 513       continue;
 514     if (CS.onlyReadsMemory(ArgNo)) {
 515       R = ModRefInfo::Ref;
 516       continue;
 517     }
 518     return ModRefInfo::ModRef;
 519   }
 520   return R;
 521 }
 522
 523 /// canBasicBlockModify - Return true if it is possible for execution of the
 524 /// specified basic block to modify the location Loc.
 525 ///
 526 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
 527                                     const MemoryLocation &Loc) {
 528   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
 529 }
 530
 531 /// canInstructionRangeModRef - Return true if it is possible for the
 532 /// execution of the specified instructions to mod\ref (according to the
 533 /// mode) the location Loc. The instructions to consider are all
 534 /// of the instructions in the range of [I1,I2] INCLUSIVE.
 535 /// I1 and I2 must be in the same basic block.
 536 bool AAResults::canInstructionRangeModRef(const Instruction &I1,
 537                                           const Instruction &I2,
 538                                           const MemoryLocation &Loc,
 539                                           const ModRefInfo Mode) {
 540   assert(I1.getParent() == I2.getParent() &&
 541          "Instructions not in same basic block!");
 542   BasicBlock::const_iterator I = I1.getIterator();
 543   BasicBlock::const_iterator E = I2.getIterator();
 544   ++E;  // Convert from inclusive to exclusive range.
 545
 546   for (; I != E; ++I) // Check every instruction in range
 547     if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
 548       return true;
 549   return false;
 550 }
 551
 552 // Provide a definition for the root virtual destructor.
 553 AAResults::Concept::~Concept() = default;
 554
 555 // Provide a definition for the static object used to identify passes.
 556 AnalysisKey AAManager::Key;
 557
 558 namespace {
 559
 560 /// A wrapper pass for external alias analyses. This just squirrels away the
 561 /// callback used to run any analyses and register their results.
 562 struct ExternalAAWrapperPass : ImmutablePass {
 563   using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
 564
 565   CallbackT CB;
 566
 567   static char ID;
 568
 569   ExternalAAWrapperPass() : ImmutablePass(ID) {
 570     initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
 571   }
 572
 573   explicit ExternalAAWrapperPass(CallbackT CB)
 574       : ImmutablePass(ID), CB(std::move(CB)) {
 575     initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
 576   }
 577
 578   void getAnalysisUsage(AnalysisUsage &AU) const override {
 579     AU.setPreservesAll();
 580   }
 581 };
 582
 583 } // end anonymous namespace
 584
 585 char ExternalAAWrapperPass::ID = 0;
 586
 587 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
 588                 false, true)
 589
 590 ImmutablePass *
 591 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
 592   return new ExternalAAWrapperPass(std::move(Callback));
 593 }
 594
 595 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
 596   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 597 }
 598
 599 char AAResultsWrapperPass::ID = 0;
 600
 601 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
 602                       "Function Alias Analysis Results", false, true)
 603 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 604 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
 605 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
 606 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 607 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 608 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
 609 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 610 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
 611 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 612 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
 613                     "Function Alias Analysis Results", false, true)
 614
 615 FunctionPass *llvm::createAAResultsWrapperPass() {
 616   return new AAResultsWrapperPass();
 617 }
 618
 619 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
 620 ///
 621 /// This is the legacy pass manager's interface to the new-style AA results
 622 /// aggregation object. Because this is somewhat shoe-horned into the legacy
 623 /// pass manager, we hard code all the specific alias analyses available into
 624 /// it. While the particular set enabled is configured via commandline flags,
 625 /// adding a new alias analysis to LLVM will require adding support for it to
 626 /// this list.
 627 bool AAResultsWrapperPass::runOnFunction(Function &F) {
 628   // NB! This *must* be reset before adding new AA results to the new
 629   // AAResults object because in the legacy pass manager, each instance
 630   // of these will refer to the *same* immutable analyses, registering and
 631   // unregistering themselves with them. We need to carefully tear down the
 632   // previous object first, in this case replacing it with an empty one, before
 633   // registering new results.
 634   AAR.reset(
 635       new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
 636
 637   // BasicAA is always available for function analyses. Also, we add it first
 638   // so that it can trump TBAA results when it proves MustAlias.
 639   // FIXME: TBAA should have an explicit mode to support this and then we
 640   // should reconsider the ordering here.
 641   if (!DisableBasicAA)
 642     AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
 643
 644   // Populate the results with the currently available AAs.
 645   if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
 646     AAR->addAAResult(WrapperPass->getResult());
 647   if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
 648     AAR->addAAResult(WrapperPass->getResult());
 649   if (auto *WrapperPass =
 650           getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
 651     AAR->addAAResult(WrapperPass->getResult());
 652   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
 653     AAR->addAAResult(WrapperPass->getResult());
 654   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
 655     AAR->addAAResult(WrapperPass->getResult());
 656   if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
 657     AAR->addAAResult(WrapperPass->getResult());
 658   if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
 659     AAR->addAAResult(WrapperPass->getResult());
 660
 661   // If available, run an external AA providing callback over the results as
 662   // well.
 663   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
 664     if (WrapperPass->CB)
 665       WrapperPass->CB(*this, F, *AAR);
 666
 667   // Analyses don't mutate the IR, so return false.
 668   return false;
 669 }
 670
 671 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 672   AU.setPreservesAll();
 673   AU.addRequired<BasicAAWrapperPass>();
 674   AU.addRequired<TargetLibraryInfoWrapperPass>();
 675
 676   // We also need to mark all the alias analysis passes we will potentially
 677   // probe in runOnFunction as used here to ensure the legacy pass manager
 678   // preserves them. This hard coding of lists of alias analyses is specific to
 679   // the legacy pass manager.
 680   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
 681   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
 682   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
 683   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
 684   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
 685   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
 686   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 687 }
 688
 689 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
 690                                         BasicAAResult &BAR) {
 691   AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
 692
 693   // Add in our explicitly constructed BasicAA results.
 694   if (!DisableBasicAA)
 695     AAR.addAAResult(BAR);
 696
 697   // Populate the results with the other currently available AAs.
 698   if (auto *WrapperPass =
 699           P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
 700     AAR.addAAResult(WrapperPass->getResult());
 701   if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
 702     AAR.addAAResult(WrapperPass->getResult());
 703   if (auto *WrapperPass =
 704           P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
 705     AAR.addAAResult(WrapperPass->getResult());
 706   if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
 707     AAR.addAAResult(WrapperPass->getResult());
 708   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
 709     AAR.addAAResult(WrapperPass->getResult());
 710   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
 711     AAR.addAAResult(WrapperPass->getResult());
 712
 713   return AAR;
 714 }
 715
 716 bool llvm::isNoAliasCall(const Value *V) {
 717   if (auto CS = ImmutableCallSite(V))
 718     return CS.hasRetAttr(Attribute::NoAlias);
 719   return false;
 720 }
 721
 722 bool llvm::isNoAliasArgument(const Value *V) {
 723   if (const Argument *A = dyn_cast<Argument>(V))
 724     return A->hasNoAliasAttr();
 725   return false;
 726 }
 727
 728 bool llvm::isIdentifiedObject(const Value *V) {
 729   if (isa<AllocaInst>(V))
 730     return true;
 731   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
 732     return true;
 733   if (isNoAliasCall(V))
 734     return true;
 735   if (const Argument *A = dyn_cast<Argument>(V))
 736     return A->hasNoAliasAttr() || A->hasByValAttr();
 737   return false;
 738 }
 739
 740 bool llvm::isIdentifiedFunctionLocal(const Value *V) {
 741   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
 742 }
 743
 744 void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
 745   // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
 746   // more alias analyses are added to llvm::createLegacyPMAAResults, they need
 747   // to be added here also.
 748   AU.addRequired<TargetLibraryInfoWrapperPass>();
 749   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
 750   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
 751   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
 752   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
 753   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
 754   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 755 }