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