llvm/lib/Analysis/AliasAnalysis.cpp

   1 //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the generic AliasAnalysis interface which is used as the
  10 // common interface used by all clients and implementations of alias analysis.
  11 //
  12 // This file also implements the default version of the AliasAnalysis interface
  13 // that is to be used when no other implementation is specified.  This does some
  14 // simple tests that detect obvious cases: two different global pointers cannot
  15 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
  16 // etc.
  17 //
  18 // This alias analysis implementation really isn't very good for anything, but
  19 // it is very fast, and makes a nice clean default implementation.  Because it
  20 // handles lots of little corner cases, other, more complex, alias analysis
  21 // implementations may choose to rely on this pass to resolve these simple and
  22 // easy cases.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #include "llvm/Analysis/AliasAnalysis.h"
  27 #include "llvm/ADT/Statistic.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/Instruction.h"
  44 #include "llvm/IR/Instructions.h"
  45 #include "llvm/IR/Module.h"
  46 #include "llvm/IR/Type.h"
  47 #include "llvm/IR/Value.h"
  48 #include "llvm/InitializePasses.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 #define DEBUG_TYPE "aa"
  59
  60 using namespace llvm;
  61
  62 STATISTIC(NumNoAlias,   "Number of NoAlias results");
  63 STATISTIC(NumMayAlias,  "Number of MayAlias results");
  64 STATISTIC(NumMustAlias, "Number of MustAlias results");
  65
  66 namespace llvm {
  67 /// Allow disabling BasicAA from the AA results. This is particularly useful
  68 /// when testing to isolate a single AA implementation.
  69 cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(false));
  70 } // namespace llvm
  71
  72 #ifndef NDEBUG
  73 /// Print a trace of alias analysis queries and their results.
  74 static cl::opt<bool> EnableAATrace("aa-trace", cl::Hidden, cl::init(false));
  75 #else
  76 static const bool EnableAATrace = false;
  77 #endif
  78
  79 AAResults::AAResults(AAResults &&Arg)
  80     : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
  81   for (auto &AA : AAs)
  82     AA->setAAResults(this);
  83 }
  84
  85 AAResults::~AAResults() {
  86 // FIXME; It would be nice to at least clear out the pointers back to this
  87 // aggregation here, but we end up with non-nesting lifetimes in the legacy
  88 // pass manager that prevent this from working. In the legacy pass manager
  89 // we'll end up with dangling references here in some cases.
  90 #if 0
  91   for (auto &AA : AAs)
  92     AA->setAAResults(nullptr);
  93 #endif
  94 }
  95
  96 bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
  97                            FunctionAnalysisManager::Invalidator &Inv) {
  98   // AAResults preserves the AAManager by default, due to the stateless nature
  99   // of AliasAnalysis. There is no need to check whether it has been preserved
 100   // explicitly. Check if any module dependency was invalidated and caused the
 101   // AAManager to be invalidated. Invalidate ourselves in that case.
 102   auto PAC = PA.getChecker<AAManager>();
 103   if (!PAC.preservedWhenStateless())
 104     return true;
 105
 106   // Check if any of the function dependencies were invalidated, and invalidate
 107   // ourselves in that case.
 108   for (AnalysisKey *ID : AADeps)
 109     if (Inv.invalidate(ID, F, PA))
 110       return true;
 111
 112   // Everything we depend on is still fine, so are we. Nothing to invalidate.
 113   return false;
 114 }
 115
 116 //===----------------------------------------------------------------------===//
 117 // Default chaining methods
 118 //===----------------------------------------------------------------------===//
 119
 120 AliasResult AAResults::alias(const MemoryLocation &LocA,
 121                              const MemoryLocation &LocB) {
 122   AAQueryInfo AAQIP;
 123   return alias(LocA, LocB, AAQIP);
 124 }
 125
 126 AliasResult AAResults::alias(const MemoryLocation &LocA,
 127                              const MemoryLocation &LocB, AAQueryInfo &AAQI) {
 128   AliasResult Result = AliasResult::MayAlias;
 129
 130   if (EnableAATrace) {
 131     for (unsigned I = 0; I < AAQI.Depth; ++I)
 132       dbgs() << "  ";
 133     dbgs() << "Start " << *LocA.Ptr << " @ " << LocA.Size << ", "
 134            << *LocB.Ptr << " @ " << LocB.Size << "\n";
 135   }
 136
 137   AAQI.Depth++;
 138   for (const auto &AA : AAs) {
 139     Result = AA->alias(LocA, LocB, AAQI);
 140     if (Result != AliasResult::MayAlias)
 141       break;
 142   }
 143   AAQI.Depth--;
 144
 145   if (EnableAATrace) {
 146     for (unsigned I = 0; I < AAQI.Depth; ++I)
 147       dbgs() << "  ";
 148     dbgs() << "End " << *LocA.Ptr << " @ " << LocA.Size << ", "
 149            << *LocB.Ptr << " @ " << LocB.Size << " = " << Result << "\n";
 150   }
 151
 152   if (AAQI.Depth == 0) {
 153     if (Result == AliasResult::NoAlias)
 154       ++NumNoAlias;
 155     else if (Result == AliasResult::MustAlias)
 156       ++NumMustAlias;
 157     else
 158       ++NumMayAlias;
 159   }
 160   return Result;
 161 }
 162
 163 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
 164                                        bool OrLocal) {
 165   AAQueryInfo AAQIP;
 166   return pointsToConstantMemory(Loc, AAQIP, OrLocal);
 167 }
 168
 169 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
 170                                        AAQueryInfo &AAQI, bool OrLocal) {
 171   for (const auto &AA : AAs)
 172     if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
 173       return true;
 174
 175   return false;
 176 }
 177
 178 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
 179   ModRefInfo Result = ModRefInfo::ModRef;
 180
 181   for (const auto &AA : AAs) {
 182     Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
 183
 184     // Early-exit the moment we reach the bottom of the lattice.
 185     if (isNoModRef(Result))
 186       return ModRefInfo::NoModRef;
 187   }
 188
 189   return Result;
 190 }
 191
 192 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) {
 193   AAQueryInfo AAQIP;
 194   return getModRefInfo(I, Call2, AAQIP);
 195 }
 196
 197 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
 198                                     AAQueryInfo &AAQI) {
 199   // We may have two calls.
 200   if (const auto *Call1 = dyn_cast<CallBase>(I)) {
 201     // Check if the two calls modify the same memory.
 202     return getModRefInfo(Call1, Call2, AAQI);
 203   } else if (I->isFenceLike()) {
 204     // If this is a fence, just return ModRef.
 205     return ModRefInfo::ModRef;
 206   } else {
 207     // Otherwise, check if the call modifies or references the
 208     // location this memory access defines.  The best we can say
 209     // is that if the call references what this instruction
 210     // defines, it must be clobbered by this location.
 211     const MemoryLocation DefLoc = MemoryLocation::get(I);
 212     ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
 213     if (isModOrRefSet(MR))
 214       return setModAndRef(MR);
 215   }
 216   return ModRefInfo::NoModRef;
 217 }
 218
 219 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
 220                                     const MemoryLocation &Loc) {
 221   AAQueryInfo AAQIP;
 222   return getModRefInfo(Call, Loc, AAQIP);
 223 }
 224
 225 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
 226                                     const MemoryLocation &Loc,
 227                                     AAQueryInfo &AAQI) {
 228   ModRefInfo Result = ModRefInfo::ModRef;
 229
 230   for (const auto &AA : AAs) {
 231     Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc, AAQI));
 232
 233     // Early-exit the moment we reach the bottom of the lattice.
 234     if (isNoModRef(Result))
 235       return ModRefInfo::NoModRef;
 236   }
 237
 238   // Try to refine the mod-ref info further using other API entry points to the
 239   // aggregate set of AA results.
 240   auto MRB = getModRefBehavior(Call);
 241   if (onlyAccessesInaccessibleMem(MRB))
 242     return ModRefInfo::NoModRef;
 243
 244   if (onlyReadsMemory(MRB))
 245     Result = clearMod(Result);
 246   else if (doesNotReadMemory(MRB))
 247     Result = clearRef(Result);
 248
 249   if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
 250     bool IsMustAlias = true;
 251     ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
 252     if (doesAccessArgPointees(MRB)) {
 253       for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
 254         const Value *Arg = *AI;
 255         if (!Arg->getType()->isPointerTy())
 256           continue;
 257         unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
 258         MemoryLocation ArgLoc =
 259             MemoryLocation::getForArgument(Call, ArgIdx, TLI);
 260         AliasResult ArgAlias = alias(ArgLoc, Loc, AAQI);
 261         if (ArgAlias != AliasResult::NoAlias) {
 262           ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
 263           AllArgsMask = unionModRef(AllArgsMask, ArgMask);
 264         }
 265         // Conservatively clear IsMustAlias unless only MustAlias is found.
 266         IsMustAlias &= (ArgAlias == AliasResult::MustAlias);
 267       }
 268     }
 269     // Return NoModRef if no alias found with any argument.
 270     if (isNoModRef(AllArgsMask))
 271       return ModRefInfo::NoModRef;
 272     // Logical & between other AA analyses and argument analysis.
 273     Result = intersectModRef(Result, AllArgsMask);
 274     // If only MustAlias found above, set Must bit.
 275     Result = IsMustAlias ? setMust(Result) : clearMust(Result);
 276   }
 277
 278   // If Loc is a constant memory location, the call definitely could not
 279   // modify the memory location.
 280   if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false))
 281     Result = clearMod(Result);
 282
 283   return Result;
 284 }
 285
 286 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
 287                                     const CallBase *Call2) {
 288   AAQueryInfo AAQIP;
 289   return getModRefInfo(Call1, Call2, AAQIP);
 290 }
 291
 292 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
 293                                     const CallBase *Call2, AAQueryInfo &AAQI) {
 294   ModRefInfo Result = ModRefInfo::ModRef;
 295
 296   for (const auto &AA : AAs) {
 297     Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2, AAQI));
 298
 299     // Early-exit the moment we reach the bottom of the lattice.
 300     if (isNoModRef(Result))
 301       return ModRefInfo::NoModRef;
 302   }
 303
 304   // Try to refine the mod-ref info further using other API entry points to the
 305   // aggregate set of AA results.
 306
 307   // If Call1 or Call2 are readnone, they don't interact.
 308   auto Call1B = getModRefBehavior(Call1);
 309   if (Call1B == FMRB_DoesNotAccessMemory)
 310     return ModRefInfo::NoModRef;
 311
 312   auto Call2B = getModRefBehavior(Call2);
 313   if (Call2B == FMRB_DoesNotAccessMemory)
 314     return ModRefInfo::NoModRef;
 315
 316   // If they both only read from memory, there is no dependence.
 317   if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
 318     return ModRefInfo::NoModRef;
 319
 320   // If Call1 only reads memory, the only dependence on Call2 can be
 321   // from Call1 reading memory written by Call2.
 322   if (onlyReadsMemory(Call1B))
 323     Result = clearMod(Result);
 324   else if (doesNotReadMemory(Call1B))
 325     Result = clearRef(Result);
 326
 327   // If Call2 only access memory through arguments, accumulate the mod/ref
 328   // information from Call1's references to the memory referenced by
 329   // Call2's arguments.
 330   if (onlyAccessesArgPointees(Call2B)) {
 331     if (!doesAccessArgPointees(Call2B))
 332       return ModRefInfo::NoModRef;
 333     ModRefInfo R = ModRefInfo::NoModRef;
 334     bool IsMustAlias = true;
 335     for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
 336       const Value *Arg = *I;
 337       if (!Arg->getType()->isPointerTy())
 338         continue;
 339       unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
 340       auto Call2ArgLoc =
 341           MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
 342
 343       // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
 344       // dependence of Call1 on that location is the inverse:
 345       // - If Call2 modifies location, dependence exists if Call1 reads or
 346       //   writes.
 347       // - If Call2 only reads location, dependence exists if Call1 writes.
 348       ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
 349       ModRefInfo ArgMask = ModRefInfo::NoModRef;
 350       if (isModSet(ArgModRefC2))
 351         ArgMask = ModRefInfo::ModRef;
 352       else if (isRefSet(ArgModRefC2))
 353         ArgMask = ModRefInfo::Mod;
 354
 355       // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
 356       // above ArgMask to update dependence info.
 357       ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc, AAQI);
 358       ArgMask = intersectModRef(ArgMask, ModRefC1);
 359
 360       // Conservatively clear IsMustAlias unless only MustAlias is found.
 361       IsMustAlias &= isMustSet(ModRefC1);
 362
 363       R = intersectModRef(unionModRef(R, ArgMask), Result);
 364       if (R == Result) {
 365         // On early exit, not all args were checked, cannot set Must.
 366         if (I + 1 != E)
 367           IsMustAlias = false;
 368         break;
 369       }
 370     }
 371
 372     if (isNoModRef(R))
 373       return ModRefInfo::NoModRef;
 374
 375     // If MustAlias found above, set Must bit.
 376     return IsMustAlias ? setMust(R) : clearMust(R);
 377   }
 378
 379   // If Call1 only accesses memory through arguments, check if Call2 references
 380   // any of the memory referenced by Call1's arguments. If not, return NoModRef.
 381   if (onlyAccessesArgPointees(Call1B)) {
 382     if (!doesAccessArgPointees(Call1B))
 383       return ModRefInfo::NoModRef;
 384     ModRefInfo R = ModRefInfo::NoModRef;
 385     bool IsMustAlias = true;
 386     for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
 387       const Value *Arg = *I;
 388       if (!Arg->getType()->isPointerTy())
 389         continue;
 390       unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
 391       auto Call1ArgLoc =
 392           MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
 393
 394       // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
 395       // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
 396       // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
 397       ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
 398       ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);
 399       if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
 400           (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
 401         R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
 402
 403       // Conservatively clear IsMustAlias unless only MustAlias is found.
 404       IsMustAlias &= isMustSet(ModRefC2);
 405
 406       if (R == Result) {
 407         // On early exit, not all args were checked, cannot set Must.
 408         if (I + 1 != E)
 409           IsMustAlias = false;
 410         break;
 411       }
 412     }
 413
 414     if (isNoModRef(R))
 415       return ModRefInfo::NoModRef;
 416
 417     // If MustAlias found above, set Must bit.
 418     return IsMustAlias ? setMust(R) : clearMust(R);
 419   }
 420
 421   return Result;
 422 }
 423
 424 FunctionModRefBehavior AAResults::getModRefBehavior(const CallBase *Call) {
 425   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 426
 427   for (const auto &AA : AAs) {
 428     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
 429
 430     // Early-exit the moment we reach the bottom of the lattice.
 431     if (Result == FMRB_DoesNotAccessMemory)
 432       return Result;
 433   }
 434
 435   return Result;
 436 }
 437
 438 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
 439   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
 440
 441   for (const auto &AA : AAs) {
 442     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
 443
 444     // Early-exit the moment we reach the bottom of the lattice.
 445     if (Result == FMRB_DoesNotAccessMemory)
 446       return Result;
 447   }
 448
 449   return Result;
 450 }
 451
 452 raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
 453   switch (AR) {
 454   case AliasResult::NoAlias:
 455     OS << "NoAlias";
 456     break;
 457   case AliasResult::MustAlias:
 458     OS << "MustAlias";
 459     break;
 460   case AliasResult::MayAlias:
 461     OS << "MayAlias";
 462     break;
 463   case AliasResult::PartialAlias:
 464     OS << "PartialAlias";
 465     if (AR.hasOffset())
 466       OS << " (off " << AR.getOffset() << ")";
 467     break;
 468   }
 469   return OS;
 470 }
 471
 472 //===----------------------------------------------------------------------===//
 473 // Helper method implementation
 474 //===----------------------------------------------------------------------===//
 475
 476 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
 477                                     const MemoryLocation &Loc) {
 478   AAQueryInfo AAQIP;
 479   return getModRefInfo(L, Loc, AAQIP);
 480 }
 481 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
 482                                     const MemoryLocation &Loc,
 483                                     AAQueryInfo &AAQI) {
 484   // Be conservative in the face of atomic.
 485   if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
 486     return ModRefInfo::ModRef;
 487
 488   // If the load address doesn't alias the given address, it doesn't read
 489   // or write the specified memory.
 490   if (Loc.Ptr) {
 491     AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
 492     if (AR == AliasResult::NoAlias)
 493       return ModRefInfo::NoModRef;
 494     if (AR == AliasResult::MustAlias)
 495       return ModRefInfo::MustRef;
 496   }
 497   // Otherwise, a load just reads.
 498   return ModRefInfo::Ref;
 499 }
 500
 501 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
 502                                     const MemoryLocation &Loc) {
 503   AAQueryInfo AAQIP;
 504   return getModRefInfo(S, Loc, AAQIP);
 505 }
 506 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
 507                                     const MemoryLocation &Loc,
 508                                     AAQueryInfo &AAQI) {
 509   // Be conservative in the face of atomic.
 510   if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
 511     return ModRefInfo::ModRef;
 512
 513   if (Loc.Ptr) {
 514     AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI);
 515     // If the store address cannot alias the pointer in question, then the
 516     // specified memory cannot be modified by the store.
 517     if (AR == AliasResult::NoAlias)
 518       return ModRefInfo::NoModRef;
 519
 520     // If the pointer is a pointer to constant memory, then it could not have
 521     // been modified by this store.
 522     if (pointsToConstantMemory(Loc, AAQI))
 523       return ModRefInfo::NoModRef;
 524
 525     // If the store address aliases the pointer as must alias, set Must.
 526     if (AR == AliasResult::MustAlias)
 527       return ModRefInfo::MustMod;
 528   }
 529
 530   // Otherwise, a store just writes.
 531   return ModRefInfo::Mod;
 532 }
 533
 534 ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
 535   AAQueryInfo AAQIP;
 536   return getModRefInfo(S, Loc, AAQIP);
 537 }
 538
 539 ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
 540                                     const MemoryLocation &Loc,
 541                                     AAQueryInfo &AAQI) {
 542   // If we know that the location is a constant memory location, the fence
 543   // cannot modify this location.
 544   if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI))
 545     return ModRefInfo::Ref;
 546   return ModRefInfo::ModRef;
 547 }
 548
 549 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
 550                                     const MemoryLocation &Loc) {
 551   AAQueryInfo AAQIP;
 552   return getModRefInfo(V, Loc, AAQIP);
 553 }
 554
 555 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
 556                                     const MemoryLocation &Loc,
 557                                     AAQueryInfo &AAQI) {
 558   if (Loc.Ptr) {
 559     AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
 560     // If the va_arg address cannot alias the pointer in question, then the
 561     // specified memory cannot be accessed by the va_arg.
 562     if (AR == AliasResult::NoAlias)
 563       return ModRefInfo::NoModRef;
 564
 565     // If the pointer is a pointer to constant memory, then it could not have
 566     // been modified by this va_arg.
 567     if (pointsToConstantMemory(Loc, AAQI))
 568       return ModRefInfo::NoModRef;
 569
 570     // If the va_arg aliases the pointer as must alias, set Must.
 571     if (AR == AliasResult::MustAlias)
 572       return ModRefInfo::MustModRef;
 573   }
 574
 575   // Otherwise, a va_arg reads and writes.
 576   return ModRefInfo::ModRef;
 577 }
 578
 579 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
 580                                     const MemoryLocation &Loc) {
 581   AAQueryInfo AAQIP;
 582   return getModRefInfo(CatchPad, Loc, AAQIP);
 583 }
 584
 585 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
 586                                     const MemoryLocation &Loc,
 587                                     AAQueryInfo &AAQI) {
 588   if (Loc.Ptr) {
 589     // If the pointer is a pointer to constant memory,
 590     // then it could not have been modified by this catchpad.
 591     if (pointsToConstantMemory(Loc, AAQI))
 592       return ModRefInfo::NoModRef;
 593   }
 594
 595   // Otherwise, a catchpad reads and writes.
 596   return ModRefInfo::ModRef;
 597 }
 598
 599 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
 600                                     const MemoryLocation &Loc) {
 601   AAQueryInfo AAQIP;
 602   return getModRefInfo(CatchRet, Loc, AAQIP);
 603 }
 604
 605 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
 606                                     const MemoryLocation &Loc,
 607                                     AAQueryInfo &AAQI) {
 608   if (Loc.Ptr) {
 609     // If the pointer is a pointer to constant memory,
 610     // then it could not have been modified by this catchpad.
 611     if (pointsToConstantMemory(Loc, AAQI))
 612       return ModRefInfo::NoModRef;
 613   }
 614
 615   // Otherwise, a catchret reads and writes.
 616   return ModRefInfo::ModRef;
 617 }
 618
 619 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
 620                                     const MemoryLocation &Loc) {
 621   AAQueryInfo AAQIP;
 622   return getModRefInfo(CX, Loc, AAQIP);
 623 }
 624
 625 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
 626                                     const MemoryLocation &Loc,
 627                                     AAQueryInfo &AAQI) {
 628   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
 629   if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
 630     return ModRefInfo::ModRef;
 631
 632   if (Loc.Ptr) {
 633     AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI);
 634     // If the cmpxchg address does not alias the location, it does not access
 635     // it.
 636     if (AR == AliasResult::NoAlias)
 637       return ModRefInfo::NoModRef;
 638
 639     // If the cmpxchg address aliases the pointer as must alias, set Must.
 640     if (AR == AliasResult::MustAlias)
 641       return ModRefInfo::MustModRef;
 642   }
 643
 644   return ModRefInfo::ModRef;
 645 }
 646
 647 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
 648                                     const MemoryLocation &Loc) {
 649   AAQueryInfo AAQIP;
 650   return getModRefInfo(RMW, Loc, AAQIP);
 651 }
 652
 653 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
 654                                     const MemoryLocation &Loc,
 655                                     AAQueryInfo &AAQI) {
 656   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
 657   if (isStrongerThanMonotonic(RMW->getOrdering()))
 658     return ModRefInfo::ModRef;
 659
 660   if (Loc.Ptr) {
 661     AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI);
 662     // If the atomicrmw address does not alias the location, it does not access
 663     // it.
 664     if (AR == AliasResult::NoAlias)
 665       return ModRefInfo::NoModRef;
 666
 667     // If the atomicrmw address aliases the pointer as must alias, set Must.
 668     if (AR == AliasResult::MustAlias)
 669       return ModRefInfo::MustModRef;
 670   }
 671
 672   return ModRefInfo::ModRef;
 673 }
 674
 675 ModRefInfo AAResults::getModRefInfo(const Instruction *I,
 676                                     const Optional<MemoryLocation> &OptLoc,
 677                                     AAQueryInfo &AAQIP) {
 678   if (OptLoc == None) {
 679     if (const auto *Call = dyn_cast<CallBase>(I)) {
 680       return createModRefInfo(getModRefBehavior(Call));
 681     }
 682   }
 683
 684   const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
 685
 686   switch (I->getOpcode()) {
 687   case Instruction::VAArg:
 688     return getModRefInfo((const VAArgInst *)I, Loc, AAQIP);
 689   case Instruction::Load:
 690     return getModRefInfo((const LoadInst *)I, Loc, AAQIP);
 691   case Instruction::Store:
 692     return getModRefInfo((const StoreInst *)I, Loc, AAQIP);
 693   case Instruction::Fence:
 694     return getModRefInfo((const FenceInst *)I, Loc, AAQIP);
 695   case Instruction::AtomicCmpXchg:
 696     return getModRefInfo((const AtomicCmpXchgInst *)I, Loc, AAQIP);
 697   case Instruction::AtomicRMW:
 698     return getModRefInfo((const AtomicRMWInst *)I, Loc, AAQIP);
 699   case Instruction::Call:
 700     return getModRefInfo((const CallInst *)I, Loc, AAQIP);
 701   case Instruction::Invoke:
 702     return getModRefInfo((const InvokeInst *)I, Loc, AAQIP);
 703   case Instruction::CatchPad:
 704     return getModRefInfo((const CatchPadInst *)I, Loc, AAQIP);
 705   case Instruction::CatchRet:
 706     return getModRefInfo((const CatchReturnInst *)I, Loc, AAQIP);
 707   default:
 708     return ModRefInfo::NoModRef;
 709   }
 710 }
 711
 712 /// Return information about whether a particular call site modifies
 713 /// or reads the specified memory location \p MemLoc before instruction \p I
 714 /// in a BasicBlock.
 715 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
 716 /// BasicAA isn't willing to spend linear time determining whether an alloca
 717 /// was captured before or after this particular call, while we are. However,
 718 /// with a smarter AA in place, this test is just wasting compile time.
 719 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
 720                                          const MemoryLocation &MemLoc,
 721                                          DominatorTree *DT,
 722                                          AAQueryInfo &AAQI) {
 723   if (!DT)
 724     return ModRefInfo::ModRef;
 725
 726   const Value *Object = getUnderlyingObject(MemLoc.Ptr);
 727   if (!isIdentifiedFunctionLocal(Object))
 728     return ModRefInfo::ModRef;
 729
 730   const auto *Call = dyn_cast<CallBase>(I);
 731   if (!Call || Call == Object)
 732     return ModRefInfo::ModRef;
 733
 734   if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
 735                                  /* StoreCaptures */ true, I, DT,
 736                                  /* include Object */ true))
 737     return ModRefInfo::ModRef;
 738
 739   unsigned ArgNo = 0;
 740   ModRefInfo R = ModRefInfo::NoModRef;
 741   bool IsMustAlias = true;
 742   // Set flag only if no May found and all operands processed.
 743   for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
 744        CI != CE; ++CI, ++ArgNo) {
 745     // Only look at the no-capture or byval pointer arguments.  If this
 746     // pointer were passed to arguments that were neither of these, then it
 747     // couldn't be no-capture.
 748     if (!(*CI)->getType()->isPointerTy() ||
 749         (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
 750          !Call->isByValArgument(ArgNo)))
 751       continue;
 752
 753     AliasResult AR = alias(
 754         MemoryLocation::getBeforeOrAfter(*CI),
 755         MemoryLocation::getBeforeOrAfter(Object), AAQI);
 756     // If this is a no-capture pointer argument, see if we can tell that it
 757     // is impossible to alias the pointer we're checking.  If not, we have to
 758     // assume that the call could touch the pointer, even though it doesn't
 759     // escape.
 760     if (AR != AliasResult::MustAlias)
 761       IsMustAlias = false;
 762     if (AR == AliasResult::NoAlias)
 763       continue;
 764     if (Call->doesNotAccessMemory(ArgNo))
 765       continue;
 766     if (Call->onlyReadsMemory(ArgNo)) {
 767       R = ModRefInfo::Ref;
 768       continue;
 769     }
 770     // Not returning MustModRef since we have not seen all the arguments.
 771     return ModRefInfo::ModRef;
 772   }
 773   return IsMustAlias ? setMust(R) : clearMust(R);
 774 }
 775
 776 /// canBasicBlockModify - Return true if it is possible for execution of the
 777 /// specified basic block to modify the location Loc.
 778 ///
 779 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
 780                                     const MemoryLocation &Loc) {
 781   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
 782 }
 783
 784 /// canInstructionRangeModRef - Return true if it is possible for the
 785 /// execution of the specified instructions to mod\ref (according to the
 786 /// mode) the location Loc. The instructions to consider are all
 787 /// of the instructions in the range of [I1,I2] INCLUSIVE.
 788 /// I1 and I2 must be in the same basic block.
 789 bool AAResults::canInstructionRangeModRef(const Instruction &I1,
 790                                           const Instruction &I2,
 791                                           const MemoryLocation &Loc,
 792                                           const ModRefInfo Mode) {
 793   assert(I1.getParent() == I2.getParent() &&
 794          "Instructions not in same basic block!");
 795   BasicBlock::const_iterator I = I1.getIterator();
 796   BasicBlock::const_iterator E = I2.getIterator();
 797   ++E;  // Convert from inclusive to exclusive range.
 798
 799   for (; I != E; ++I) // Check every instruction in range
 800     if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
 801       return true;
 802   return false;
 803 }
 804
 805 // Provide a definition for the root virtual destructor.
 806 AAResults::Concept::~Concept() = default;
 807
 808 // Provide a definition for the static object used to identify passes.
 809 AnalysisKey AAManager::Key;
 810
 811 namespace {
 812
 813
 814 } // end anonymous namespace
 815
 816 ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {
 817   initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
 818 }
 819
 820 ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB)
 821     : ImmutablePass(ID), CB(std::move(CB)) {
 822   initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
 823 }
 824
 825 char ExternalAAWrapperPass::ID = 0;
 826
 827 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
 828                 false, true)
 829
 830 ImmutablePass *
 831 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
 832   return new ExternalAAWrapperPass(std::move(Callback));
 833 }
 834
 835 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
 836   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 837 }
 838
 839 char AAResultsWrapperPass::ID = 0;
 840
 841 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
 842                       "Function Alias Analysis Results", false, true)
 843 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 844 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
 845 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
 846 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 847 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 848 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
 849 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 850 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
 851 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 852 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
 853                     "Function Alias Analysis Results", false, true)
 854
 855 FunctionPass *llvm::createAAResultsWrapperPass() {
 856   return new AAResultsWrapperPass();
 857 }
 858
 859 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
 860 ///
 861 /// This is the legacy pass manager's interface to the new-style AA results
 862 /// aggregation object. Because this is somewhat shoe-horned into the legacy
 863 /// pass manager, we hard code all the specific alias analyses available into
 864 /// it. While the particular set enabled is configured via commandline flags,
 865 /// adding a new alias analysis to LLVM will require adding support for it to
 866 /// this list.
 867 bool AAResultsWrapperPass::runOnFunction(Function &F) {
 868   // NB! This *must* be reset before adding new AA results to the new
 869   // AAResults object because in the legacy pass manager, each instance
 870   // of these will refer to the *same* immutable analyses, registering and
 871   // unregistering themselves with them. We need to carefully tear down the
 872   // previous object first, in this case replacing it with an empty one, before
 873   // registering new results.
 874   AAR.reset(
 875       new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
 876
 877   // BasicAA is always available for function analyses. Also, we add it first
 878   // so that it can trump TBAA results when it proves MustAlias.
 879   // FIXME: TBAA should have an explicit mode to support this and then we
 880   // should reconsider the ordering here.
 881   if (!DisableBasicAA)
 882     AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
 883
 884   // Populate the results with the currently available AAs.
 885   if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
 886     AAR->addAAResult(WrapperPass->getResult());
 887   if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
 888     AAR->addAAResult(WrapperPass->getResult());
 889   if (auto *WrapperPass =
 890           getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
 891     AAR->addAAResult(WrapperPass->getResult());
 892   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
 893     AAR->addAAResult(WrapperPass->getResult());
 894   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
 895     AAR->addAAResult(WrapperPass->getResult());
 896   if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
 897     AAR->addAAResult(WrapperPass->getResult());
 898   if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
 899     AAR->addAAResult(WrapperPass->getResult());
 900
 901   // If available, run an external AA providing callback over the results as
 902   // well.
 903   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
 904     if (WrapperPass->CB)
 905       WrapperPass->CB(*this, F, *AAR);
 906
 907   // Analyses don't mutate the IR, so return false.
 908   return false;
 909 }
 910
 911 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 912   AU.setPreservesAll();
 913   AU.addRequiredTransitive<BasicAAWrapperPass>();
 914   AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
 915
 916   // We also need to mark all the alias analysis passes we will potentially
 917   // probe in runOnFunction as used here to ensure the legacy pass manager
 918   // preserves them. This hard coding of lists of alias analyses is specific to
 919   // the legacy pass manager.
 920   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
 921   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
 922   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
 923   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
 924   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
 925   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
 926   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 927   AU.addUsedIfAvailable<ExternalAAWrapperPass>();
 928 }
 929
 930 AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) {
 931   Result R(AM.getResult<TargetLibraryAnalysis>(F));
 932   for (auto &Getter : ResultGetters)
 933     (*Getter)(F, AM, R);
 934   return R;
 935 }
 936
 937 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
 938                                         BasicAAResult &BAR) {
 939   AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F));
 940
 941   // Add in our explicitly constructed BasicAA results.
 942   if (!DisableBasicAA)
 943     AAR.addAAResult(BAR);
 944
 945   // Populate the results with the other currently available AAs.
 946   if (auto *WrapperPass =
 947           P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
 948     AAR.addAAResult(WrapperPass->getResult());
 949   if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
 950     AAR.addAAResult(WrapperPass->getResult());
 951   if (auto *WrapperPass =
 952           P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
 953     AAR.addAAResult(WrapperPass->getResult());
 954   if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
 955     AAR.addAAResult(WrapperPass->getResult());
 956   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
 957     AAR.addAAResult(WrapperPass->getResult());
 958   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
 959     AAR.addAAResult(WrapperPass->getResult());
 960   if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>())
 961     if (WrapperPass->CB)
 962       WrapperPass->CB(P, F, AAR);
 963
 964   return AAR;
 965 }
 966
 967 bool llvm::isNoAliasCall(const Value *V) {
 968   if (const auto *Call = dyn_cast<CallBase>(V))
 969     return Call->hasRetAttr(Attribute::NoAlias);
 970   return false;
 971 }
 972
 973 static bool isNoAliasOrByValArgument(const Value *V) {
 974   if (const Argument *A = dyn_cast<Argument>(V))
 975     return A->hasNoAliasAttr() || A->hasByValAttr();
 976   return false;
 977 }
 978
 979 bool llvm::isIdentifiedObject(const Value *V) {
 980   if (isa<AllocaInst>(V))
 981     return true;
 982   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
 983     return true;
 984   if (isNoAliasCall(V))
 985     return true;
 986   if (isNoAliasOrByValArgument(V))
 987     return true;
 988   return false;
 989 }
 990
 991 bool llvm::isIdentifiedFunctionLocal(const Value *V) {
 992   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);
 993 }
 994
 995 void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
 996   // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
 997   // more alias analyses are added to llvm::createLegacyPMAAResults, they need
 998   // to be added here also.
 999   AU.addRequired<TargetLibraryInfoWrapperPass>();
1000   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
1001   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
1002   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
1003   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
1004   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
1005   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
1006   AU.addUsedIfAvailable<ExternalAAWrapperPass>();
1007 }