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