950 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the generic AliasAnalysis interface which is used as the10// common interface used by all clients and implementations of alias analysis.11//12// This file also implements the default version of the AliasAnalysis interface13// that is to be used when no other implementation is specified. This does some14// simple tests that detect obvious cases: two different global pointers cannot15// 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, but19// it is very fast, and makes a nice clean default implementation. Because it20// handles lots of little corner cases, other, more complex, alias analysis21// implementations may choose to rely on this pass to resolve these simple and22// 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/CaptureTracking.h"30#include "llvm/Analysis/GlobalsModRef.h"31#include "llvm/Analysis/MemoryLocation.h"32#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"33#include "llvm/Analysis/ScopedNoAliasAA.h"34#include "llvm/Analysis/TargetLibraryInfo.h"35#include "llvm/Analysis/TypeBasedAliasAnalysis.h"36#include "llvm/Analysis/ValueTracking.h"37#include "llvm/IR/Argument.h"38#include "llvm/IR/Attributes.h"39#include "llvm/IR/BasicBlock.h"40#include "llvm/IR/Instruction.h"41#include "llvm/IR/Instructions.h"42#include "llvm/IR/Type.h"43#include "llvm/IR/Value.h"44#include "llvm/InitializePasses.h"45#include "llvm/Pass.h"46#include "llvm/Support/AtomicOrdering.h"47#include "llvm/Support/Casting.h"48#include "llvm/Support/CommandLine.h"49#include <cassert>50#include <functional>51#include <iterator>52 53#define DEBUG_TYPE "aa"54 55using namespace llvm;56 57STATISTIC(NumNoAlias, "Number of NoAlias results");58STATISTIC(NumMayAlias, "Number of MayAlias results");59STATISTIC(NumMustAlias, "Number of MustAlias results");60 61/// Allow disabling BasicAA from the AA results. This is particularly useful62/// when testing to isolate a single AA implementation.63static cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden,64 cl::init(false));65 66#ifndef NDEBUG67/// Print a trace of alias analysis queries and their results.68static cl::opt<bool> EnableAATrace("aa-trace", cl::Hidden, cl::init(false));69#else70static const bool EnableAATrace = false;71#endif72 73AAResults::AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}74 75AAResults::AAResults(AAResults &&Arg)76 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {}77 78AAResults::~AAResults() = default;79 80bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,81 FunctionAnalysisManager::Invalidator &Inv) {82 // AAResults preserves the AAManager by default, due to the stateless nature83 // of AliasAnalysis. There is no need to check whether it has been preserved84 // explicitly. Check if any module dependency was invalidated and caused the85 // 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 invalidate91 // 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 methods102//===----------------------------------------------------------------------===//103 104AliasResult AAResults::alias(const MemoryLocation &LocA,105 const MemoryLocation &LocB) {106 SimpleAAQueryInfo AAQIP(*this);107 return alias(LocA, LocB, AAQIP, nullptr);108}109 110AliasResult AAResults::alias(const MemoryLocation &LocA,111 const MemoryLocation &LocB, AAQueryInfo &AAQI,112 const Instruction *CtxI) {113 assert(LocA.Ptr->getType()->isPointerTy() &&114 LocB.Ptr->getType()->isPointerTy() &&115 "Can only call alias() on pointers");116 AliasResult Result = AliasResult::MayAlias;117 118 if (EnableAATrace) {119 for (unsigned I = 0; I < AAQI.Depth; ++I)120 dbgs() << " ";121 dbgs() << "Start " << *LocA.Ptr << " @ " << LocA.Size << ", "122 << *LocB.Ptr << " @ " << LocB.Size << "\n";123 }124 125 AAQI.Depth++;126 for (const auto &AA : AAs) {127 Result = AA->alias(LocA, LocB, AAQI, CtxI);128 if (Result != AliasResult::MayAlias)129 break;130 }131 AAQI.Depth--;132 133 if (EnableAATrace) {134 for (unsigned I = 0; I < AAQI.Depth; ++I)135 dbgs() << " ";136 dbgs() << "End " << *LocA.Ptr << " @ " << LocA.Size << ", "137 << *LocB.Ptr << " @ " << LocB.Size << " = " << Result << "\n";138 }139 140 if (AAQI.Depth == 0) {141 if (Result == AliasResult::NoAlias)142 ++NumNoAlias;143 else if (Result == AliasResult::MustAlias)144 ++NumMustAlias;145 else146 ++NumMayAlias;147 }148 return Result;149}150 151AliasResult AAResults::aliasErrno(const MemoryLocation &Loc, const Module *M) {152 AliasResult Result = AliasResult::MayAlias;153 154 for (const auto &AA : AAs) {155 Result = AA->aliasErrno(Loc, M);156 if (Result != AliasResult::MayAlias)157 break;158 }159 160 return Result;161}162 163ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,164 bool IgnoreLocals) {165 SimpleAAQueryInfo AAQIP(*this);166 return getModRefInfoMask(Loc, AAQIP, IgnoreLocals);167}168 169ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,170 AAQueryInfo &AAQI, bool IgnoreLocals) {171 ModRefInfo Result = ModRefInfo::ModRef;172 173 for (const auto &AA : AAs) {174 Result &= AA->getModRefInfoMask(Loc, AAQI, IgnoreLocals);175 176 // Early-exit the moment we reach the bottom of the lattice.177 if (isNoModRef(Result))178 return ModRefInfo::NoModRef;179 }180 181 return Result;182}183 184ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {185 ModRefInfo Result = ModRefInfo::ModRef;186 187 for (const auto &AA : AAs) {188 Result &= AA->getArgModRefInfo(Call, ArgIdx);189 190 // Early-exit the moment we reach the bottom of the lattice.191 if (isNoModRef(Result))192 return ModRefInfo::NoModRef;193 }194 195 return Result;196}197 198ModRefInfo AAResults::getModRefInfo(const Instruction *I,199 const CallBase *Call2) {200 SimpleAAQueryInfo AAQIP(*this);201 return getModRefInfo(I, Call2, AAQIP);202}203 204ModRefInfo AAResults::getModRefInfo(const Instruction *I, const CallBase *Call2,205 AAQueryInfo &AAQI) {206 // We may have two calls.207 if (const auto *Call1 = dyn_cast<CallBase>(I)) {208 // Check if the two calls modify the same memory.209 return getModRefInfo(Call1, Call2, AAQI);210 }211 // If this is a fence, just return ModRef.212 if (I->isFenceLike())213 return ModRefInfo::ModRef;214 // Otherwise, check if the call modifies or references the215 // location this memory access defines. The best we can say216 // is that if the call references what this instruction217 // defines, it must be clobbered by this location.218 const MemoryLocation DefLoc = MemoryLocation::get(I);219 ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);220 if (isModOrRefSet(MR))221 return ModRefInfo::ModRef;222 return ModRefInfo::NoModRef;223}224 225ModRefInfo 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 &= 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 // Apply the ModRef mask. This ensures that if Loc is a constant memory239 // location, we take into account the fact that the call definitely could not240 // modify the memory location.241 if (!isNoModRef(Result))242 Result &= getModRefInfoMask(Loc);243 244 return Result;245}246 247ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,248 const CallBase *Call2, AAQueryInfo &AAQI) {249 ModRefInfo Result = ModRefInfo::ModRef;250 251 for (const auto &AA : AAs) {252 Result &= AA->getModRefInfo(Call1, Call2, AAQI);253 254 // Early-exit the moment we reach the bottom of the lattice.255 if (isNoModRef(Result))256 return ModRefInfo::NoModRef;257 }258 259 // Try to refine the mod-ref info further using other API entry points to the260 // aggregate set of AA results.261 262 // If Call1 or Call2 are readnone, they don't interact.263 auto Call1B = getMemoryEffects(Call1, AAQI);264 if (Call1B.doesNotAccessMemory())265 return ModRefInfo::NoModRef;266 267 auto Call2B = getMemoryEffects(Call2, AAQI);268 if (Call2B.doesNotAccessMemory())269 return ModRefInfo::NoModRef;270 271 // If they both only read from memory, there is no dependence.272 if (Call1B.onlyReadsMemory() && Call2B.onlyReadsMemory())273 return ModRefInfo::NoModRef;274 275 // If Call1 only reads memory, the only dependence on Call2 can be276 // from Call1 reading memory written by Call2.277 if (Call1B.onlyReadsMemory())278 Result &= ModRefInfo::Ref;279 else if (Call1B.onlyWritesMemory())280 Result &= ModRefInfo::Mod;281 282 // If Call2 only access memory through arguments, accumulate the mod/ref283 // information from Call1's references to the memory referenced by284 // Call2's arguments.285 if (Call2B.onlyAccessesArgPointees()) {286 if (!Call2B.doesAccessArgPointees())287 return ModRefInfo::NoModRef;288 ModRefInfo R = ModRefInfo::NoModRef;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 the298 // dependence of Call1 on that location is the inverse:299 // - If Call2 modifies location, dependence exists if Call1 reads or300 // 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 use310 // above ArgMask to update dependence info.311 ArgMask &= getModRefInfo(Call1, Call2ArgLoc, AAQI);312 313 R = (R | ArgMask) & Result;314 if (R == Result)315 break;316 }317 318 return R;319 }320 321 // If Call1 only accesses memory through arguments, check if Call2 references322 // any of the memory referenced by Call1's arguments. If not, return NoModRef.323 if (Call1B.onlyAccessesArgPointees()) {324 if (!Call1B.doesAccessArgPointees())325 return ModRefInfo::NoModRef;326 ModRefInfo R = ModRefInfo::NoModRef;327 for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {328 const Value *Arg = *I;329 if (!Arg->getType()->isPointerTy())330 continue;331 unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);332 auto Call1ArgLoc =333 MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);334 335 // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1336 // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by337 // Call2. If Call1 might Ref, then we care only about a Mod by Call2.338 ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);339 ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);340 if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||341 (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))342 R = (R | ArgModRefC1) & Result;343 344 if (R == Result)345 break;346 }347 348 return R;349 }350 351 return Result;352}353 354ModRefInfo AAResults::getModRefInfo(const Instruction *I1,355 const Instruction *I2) {356 SimpleAAQueryInfo AAQIP(*this);357 return getModRefInfo(I1, I2, AAQIP);358}359 360ModRefInfo AAResults::getModRefInfo(const Instruction *I1,361 const Instruction *I2, AAQueryInfo &AAQI) {362 // Early-exit if either instruction does not read or write memory.363 if (!I1->mayReadOrWriteMemory() || !I2->mayReadOrWriteMemory())364 return ModRefInfo::NoModRef;365 366 if (const auto *Call2 = dyn_cast<CallBase>(I2))367 return getModRefInfo(I1, Call2, AAQI);368 369 // FIXME: We can have a more precise result.370 ModRefInfo MR = getModRefInfo(I1, MemoryLocation::getOrNone(I2), AAQI);371 return isModOrRefSet(MR) ? ModRefInfo::ModRef : ModRefInfo::NoModRef;372}373 374MemoryEffects AAResults::getMemoryEffects(const CallBase *Call,375 AAQueryInfo &AAQI) {376 MemoryEffects Result = MemoryEffects::unknown();377 378 for (const auto &AA : AAs) {379 Result &= AA->getMemoryEffects(Call, AAQI);380 381 // Early-exit the moment we reach the bottom of the lattice.382 if (Result.doesNotAccessMemory())383 return Result;384 }385 386 return Result;387}388 389MemoryEffects AAResults::getMemoryEffects(const CallBase *Call) {390 SimpleAAQueryInfo AAQI(*this);391 return getMemoryEffects(Call, AAQI);392}393 394MemoryEffects AAResults::getMemoryEffects(const Function *F) {395 MemoryEffects Result = MemoryEffects::unknown();396 397 for (const auto &AA : AAs) {398 Result &= AA->getMemoryEffects(F);399 400 // Early-exit the moment we reach the bottom of the lattice.401 if (Result.doesNotAccessMemory())402 return Result;403 }404 405 return Result;406}407 408raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {409 switch (AR) {410 case AliasResult::NoAlias:411 OS << "NoAlias";412 break;413 case AliasResult::MustAlias:414 OS << "MustAlias";415 break;416 case AliasResult::MayAlias:417 OS << "MayAlias";418 break;419 case AliasResult::PartialAlias:420 OS << "PartialAlias";421 if (AR.hasOffset())422 OS << " (off " << AR.getOffset() << ")";423 break;424 }425 return OS;426}427 428//===----------------------------------------------------------------------===//429// Helper method implementation430//===----------------------------------------------------------------------===//431 432ModRefInfo AAResults::getModRefInfo(const LoadInst *L,433 const MemoryLocation &Loc,434 AAQueryInfo &AAQI) {435 // Be conservative in the face of atomic.436 if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))437 return ModRefInfo::ModRef;438 439 // If the load address doesn't alias the given address, it doesn't read440 // or write the specified memory.441 if (Loc.Ptr) {442 AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI, L);443 if (AR == AliasResult::NoAlias)444 return ModRefInfo::NoModRef;445 }446 // Otherwise, a load just reads.447 return ModRefInfo::Ref;448}449 450ModRefInfo AAResults::getModRefInfo(const StoreInst *S,451 const MemoryLocation &Loc,452 AAQueryInfo &AAQI) {453 // Be conservative in the face of atomic.454 if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))455 return ModRefInfo::ModRef;456 457 if (Loc.Ptr) {458 AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI, S);459 // If the store address cannot alias the pointer in question, then the460 // specified memory cannot be modified by the store.461 if (AR == AliasResult::NoAlias)462 return ModRefInfo::NoModRef;463 464 // Examine the ModRef mask. If Mod isn't present, then return NoModRef.465 // This ensures that if Loc is a constant memory location, we take into466 // account the fact that the store definitely could not modify the memory467 // location.468 if (!isModSet(getModRefInfoMask(Loc)))469 return ModRefInfo::NoModRef;470 }471 472 // Otherwise, a store just writes.473 return ModRefInfo::Mod;474}475 476ModRefInfo AAResults::getModRefInfo(const FenceInst *S,477 const MemoryLocation &Loc,478 AAQueryInfo &AAQI) {479 // All we know about a fence instruction is what we get from the ModRef480 // mask: if Loc is a constant memory location, the fence definitely could481 // not modify it.482 if (Loc.Ptr)483 return getModRefInfoMask(Loc);484 return ModRefInfo::ModRef;485}486 487ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,488 const MemoryLocation &Loc,489 AAQueryInfo &AAQI) {490 if (Loc.Ptr) {491 AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI, V);492 // If the va_arg address cannot alias the pointer in question, then the493 // specified memory cannot be accessed by the va_arg.494 if (AR == AliasResult::NoAlias)495 return ModRefInfo::NoModRef;496 497 // If the pointer is a pointer to invariant memory, then it could not have498 // been modified by this va_arg.499 return getModRefInfoMask(Loc, AAQI);500 }501 502 // Otherwise, a va_arg reads and writes.503 return ModRefInfo::ModRef;504}505 506ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,507 const MemoryLocation &Loc,508 AAQueryInfo &AAQI) {509 if (Loc.Ptr) {510 // If the pointer is a pointer to invariant memory,511 // then it could not have been modified by this catchpad.512 return getModRefInfoMask(Loc, AAQI);513 }514 515 // Otherwise, a catchpad reads and writes.516 return ModRefInfo::ModRef;517}518 519ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,520 const MemoryLocation &Loc,521 AAQueryInfo &AAQI) {522 if (Loc.Ptr) {523 // If the pointer is a pointer to invariant memory,524 // then it could not have been modified by this catchpad.525 return getModRefInfoMask(Loc, AAQI);526 }527 528 // Otherwise, a catchret reads and writes.529 return ModRefInfo::ModRef;530}531 532ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,533 const MemoryLocation &Loc,534 AAQueryInfo &AAQI) {535 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.536 if (isStrongerThanMonotonic(CX->getSuccessOrdering()))537 return ModRefInfo::ModRef;538 539 if (Loc.Ptr) {540 AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI, CX);541 // If the cmpxchg address does not alias the location, it does not access542 // it.543 if (AR == AliasResult::NoAlias)544 return ModRefInfo::NoModRef;545 }546 547 return ModRefInfo::ModRef;548}549 550ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,551 const MemoryLocation &Loc,552 AAQueryInfo &AAQI) {553 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.554 if (isStrongerThanMonotonic(RMW->getOrdering()))555 return ModRefInfo::ModRef;556 557 if (Loc.Ptr) {558 AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI, RMW);559 // If the atomicrmw address does not alias the location, it does not access560 // it.561 if (AR == AliasResult::NoAlias)562 return ModRefInfo::NoModRef;563 }564 565 return ModRefInfo::ModRef;566}567 568ModRefInfo AAResults::getModRefInfo(const Instruction *I,569 const std::optional<MemoryLocation> &OptLoc,570 AAQueryInfo &AAQIP) {571 if (OptLoc == std::nullopt) {572 if (const auto *Call = dyn_cast<CallBase>(I))573 return getMemoryEffects(Call, AAQIP).getModRef();574 }575 576 const MemoryLocation &Loc = OptLoc.value_or(MemoryLocation());577 578 switch (I->getOpcode()) {579 case Instruction::VAArg:580 return getModRefInfo((const VAArgInst *)I, Loc, AAQIP);581 case Instruction::Load:582 return getModRefInfo((const LoadInst *)I, Loc, AAQIP);583 case Instruction::Store:584 return getModRefInfo((const StoreInst *)I, Loc, AAQIP);585 case Instruction::Fence:586 return getModRefInfo((const FenceInst *)I, Loc, AAQIP);587 case Instruction::AtomicCmpXchg:588 return getModRefInfo((const AtomicCmpXchgInst *)I, Loc, AAQIP);589 case Instruction::AtomicRMW:590 return getModRefInfo((const AtomicRMWInst *)I, Loc, AAQIP);591 case Instruction::Call:592 case Instruction::CallBr:593 case Instruction::Invoke:594 return getModRefInfo((const CallBase *)I, Loc, AAQIP);595 case Instruction::CatchPad:596 return getModRefInfo((const CatchPadInst *)I, Loc, AAQIP);597 case Instruction::CatchRet:598 return getModRefInfo((const CatchReturnInst *)I, Loc, AAQIP);599 default:600 assert(!I->mayReadOrWriteMemory() &&601 "Unhandled memory access instruction!");602 return ModRefInfo::NoModRef;603 }604}605 606/// Return information about whether a particular call site modifies607/// or reads the specified memory location \p MemLoc before instruction \p I608/// in a BasicBlock.609/// FIXME: this is really just shoring-up a deficiency in alias analysis.610/// BasicAA isn't willing to spend linear time determining whether an alloca611/// was captured before or after this particular call, while we are. However,612/// with a smarter AA in place, this test is just wasting compile time.613ModRefInfo AAResults::callCapturesBefore(const Instruction *I,614 const MemoryLocation &MemLoc,615 DominatorTree *DT,616 AAQueryInfo &AAQI) {617 if (!DT)618 return ModRefInfo::ModRef;619 620 const Value *Object = getUnderlyingObject(MemLoc.Ptr);621 if (!isIdentifiedFunctionLocal(Object))622 return ModRefInfo::ModRef;623 624 const auto *Call = dyn_cast<CallBase>(I);625 if (!Call || Call == Object)626 return ModRefInfo::ModRef;627 628 if (capturesAnything(PointerMayBeCapturedBefore(629 Object, /* ReturnCaptures */ true, I, DT,630 /* include Object */ true, CaptureComponents::Provenance)))631 return ModRefInfo::ModRef;632 633 unsigned ArgNo = 0;634 ModRefInfo R = ModRefInfo::NoModRef;635 // Set flag only if no May found and all operands processed.636 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();637 CI != CE; ++CI, ++ArgNo) {638 // Only look at the no-capture or byval pointer arguments. If this639 // pointer were passed to arguments that were neither of these, then it640 // couldn't be no-capture.641 if (!(*CI)->getType()->isPointerTy())642 continue;643 644 // Make sure we still check captures(ret: address, provenance) and645 // captures(address) arguments, as these wouldn't be treated as a capture646 // at the call-site.647 CaptureInfo Captures = Call->getCaptureInfo(ArgNo);648 if (capturesAnyProvenance(Captures.getOtherComponents()))649 continue;650 651 AliasResult AR =652 alias(MemoryLocation::getBeforeOrAfter(*CI),653 MemoryLocation::getBeforeOrAfter(Object), AAQI, Call);654 // If this is a no-capture pointer argument, see if we can tell that it655 // is impossible to alias the pointer we're checking. If not, we have to656 // assume that the call could touch the pointer, even though it doesn't657 // escape.658 if (AR == AliasResult::NoAlias)659 continue;660 if (Call->doesNotAccessMemory(ArgNo))661 continue;662 if (Call->onlyReadsMemory(ArgNo)) {663 R = ModRefInfo::Ref;664 continue;665 }666 return ModRefInfo::ModRef;667 }668 return R;669}670 671/// canBasicBlockModify - Return true if it is possible for execution of the672/// specified basic block to modify the location Loc.673///674bool AAResults::canBasicBlockModify(const BasicBlock &BB,675 const MemoryLocation &Loc) {676 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);677}678 679/// canInstructionRangeModRef - Return true if it is possible for the680/// execution of the specified instructions to mod\ref (according to the681/// mode) the location Loc. The instructions to consider are all682/// of the instructions in the range of [I1,I2] INCLUSIVE.683/// I1 and I2 must be in the same basic block.684bool AAResults::canInstructionRangeModRef(const Instruction &I1,685 const Instruction &I2,686 const MemoryLocation &Loc,687 const ModRefInfo Mode) {688 assert(I1.getParent() == I2.getParent() &&689 "Instructions not in same basic block!");690 BasicBlock::const_iterator I = I1.getIterator();691 BasicBlock::const_iterator E = I2.getIterator();692 ++E; // Convert from inclusive to exclusive range.693 694 for (; I != E; ++I) // Check every instruction in range695 if (isModOrRefSet(getModRefInfo(&*I, Loc) & Mode))696 return true;697 return false;698}699 700// Provide a definition for the root virtual destructor.701AAResults::Concept::~Concept() = default;702 703// Provide a definition for the static object used to identify passes.704AnalysisKey AAManager::Key;705 706ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {}707 708ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB, bool RunEarly)709 : ImmutablePass(ID), CB(std::move(CB)), RunEarly(RunEarly) {}710 711char ExternalAAWrapperPass::ID = 0;712 713INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",714 false, true)715 716ImmutablePass *717llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {718 return new ExternalAAWrapperPass(std::move(Callback));719}720 721AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {}722 723char AAResultsWrapperPass::ID = 0;724 725INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",726 "Function Alias Analysis Results", false, true)727INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)728INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)729INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)730INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)731INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)732INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)733INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",734 "Function Alias Analysis Results", false, true)735 736/// Run the wrapper pass to rebuild an aggregation over known AA passes.737///738/// This is the legacy pass manager's interface to the new-style AA results739/// aggregation object. Because this is somewhat shoe-horned into the legacy740/// pass manager, we hard code all the specific alias analyses available into741/// it. While the particular set enabled is configured via commandline flags,742/// adding a new alias analysis to LLVM will require adding support for it to743/// this list.744bool AAResultsWrapperPass::runOnFunction(Function &F) {745 // NB! This *must* be reset before adding new AA results to the new746 // AAResults object because in the legacy pass manager, each instance747 // of these will refer to the *same* immutable analyses, registering and748 // unregistering themselves with them. We need to carefully tear down the749 // previous object first, in this case replacing it with an empty one, before750 // registering new results.751 AAR.reset(752 new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));753 754 // Add any target-specific alias analyses that should be run early.755 auto *ExtWrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>();756 if (ExtWrapperPass && ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {757 LLVM_DEBUG(dbgs() << "AAResults register Early ExternalAA: "758 << ExtWrapperPass->getPassName() << "\n");759 ExtWrapperPass->CB(*this, F, *AAR);760 }761 762 // BasicAA is always available for function analyses. Also, we add it first763 // so that it can trump TBAA results when it proves MustAlias.764 // FIXME: TBAA should have an explicit mode to support this and then we765 // should reconsider the ordering here.766 if (!DisableBasicAA) {767 LLVM_DEBUG(dbgs() << "AAResults register BasicAA\n");768 AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());769 }770 771 // Populate the results with the currently available AAs.772 if (auto *WrapperPass =773 getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>()) {774 LLVM_DEBUG(dbgs() << "AAResults register ScopedNoAliasAA\n");775 AAR->addAAResult(WrapperPass->getResult());776 }777 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>()) {778 LLVM_DEBUG(dbgs() << "AAResults register TypeBasedAA\n");779 AAR->addAAResult(WrapperPass->getResult());780 }781 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>()) {782 LLVM_DEBUG(dbgs() << "AAResults register GlobalsAA\n");783 AAR->addAAResult(WrapperPass->getResult());784 }785 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>()) {786 LLVM_DEBUG(dbgs() << "AAResults register SCEVAA\n");787 AAR->addAAResult(WrapperPass->getResult());788 }789 790 // If available, run an external AA providing callback over the results as791 // well.792 if (ExtWrapperPass && !ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {793 LLVM_DEBUG(dbgs() << "AAResults register Late ExternalAA: "794 << ExtWrapperPass->getPassName() << "\n");795 ExtWrapperPass->CB(*this, F, *AAR);796 }797 798 // Analyses don't mutate the IR, so return false.799 return false;800}801 802void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {803 AU.setPreservesAll();804 AU.addRequiredTransitive<BasicAAWrapperPass>();805 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();806 807 // We also need to mark all the alias analysis passes we will potentially808 // probe in runOnFunction as used here to ensure the legacy pass manager809 // preserves them. This hard coding of lists of alias analyses is specific to810 // the legacy pass manager.811 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();812 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();813 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();814 AU.addUsedIfAvailable<SCEVAAWrapperPass>();815 AU.addUsedIfAvailable<ExternalAAWrapperPass>();816}817 818AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) {819 Result R(AM.getResult<TargetLibraryAnalysis>(F));820 for (auto &Getter : ResultGetters)821 (*Getter)(F, AM, R);822 return R;823}824 825bool llvm::isNoAliasCall(const Value *V) {826 if (const auto *Call = dyn_cast<CallBase>(V))827 return Call->hasRetAttr(Attribute::NoAlias);828 return false;829}830 831static bool isNoAliasOrByValArgument(const Value *V) {832 if (const Argument *A = dyn_cast<Argument>(V))833 return A->hasNoAliasAttr() || A->hasByValAttr();834 return false;835}836 837bool llvm::isIdentifiedObject(const Value *V) {838 if (isa<AllocaInst>(V))839 return true;840 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))841 return true;842 if (isNoAliasCall(V))843 return true;844 if (isNoAliasOrByValArgument(V))845 return true;846 return false;847}848 849bool llvm::isIdentifiedFunctionLocal(const Value *V) {850 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);851}852 853bool llvm::isBaseOfObject(const Value *V) {854 // TODO: We can handle other cases here855 // 1) For GC languages, arguments to functions are often required to be856 // base pointers.857 // 2) Result of allocation routines are often base pointers. Leverage TLI.858 return (isa<AllocaInst>(V) || isa<GlobalVariable>(V));859}860 861bool llvm::isEscapeSource(const Value *V) {862 if (auto *CB = dyn_cast<CallBase>(V)) {863 if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(CB, true))864 return false;865 866 // The return value of a function with a captures(ret: address, provenance)867 // attribute is not necessarily an escape source. The return value may868 // alias with a non-escaping object.869 return !CB->hasArgumentWithAdditionalReturnCaptureComponents();870 }871 872 // The load case works because isNotCapturedBefore considers all873 // stores to be escapes (it passes true for the StoreCaptures argument874 // to PointerMayBeCaptured).875 if (isa<LoadInst>(V))876 return true;877 878 // The inttoptr case works because isNotCapturedBefore considers all879 // means of converting or equating a pointer to an int (ptrtoint, ptr store880 // which could be followed by an integer load, ptr<->int compare) as881 // escaping, and objects located at well-known addresses via platform-specific882 // means cannot be considered non-escaping local objects.883 if (isa<IntToPtrInst>(V))884 return true;885 886 // Capture tracking considers insertions into aggregates and vectors as887 // captures. As such, extractions from aggregates and vectors are escape888 // sources.889 if (isa<ExtractValueInst, ExtractElementInst>(V))890 return true;891 892 // Same for inttoptr constant expressions.893 if (auto *CE = dyn_cast<ConstantExpr>(V))894 if (CE->getOpcode() == Instruction::IntToPtr)895 return true;896 897 return false;898}899 900bool llvm::isNotVisibleOnUnwind(const Value *Object,901 bool &RequiresNoCaptureBeforeUnwind) {902 RequiresNoCaptureBeforeUnwind = false;903 904 // Alloca goes out of scope on unwind.905 if (isa<AllocaInst>(Object))906 return true;907 908 // Byval goes out of scope on unwind.909 if (auto *A = dyn_cast<Argument>(Object))910 return A->hasByValAttr() || A->hasAttribute(Attribute::DeadOnUnwind);911 912 // A noalias return is not accessible from any other code. If the pointer913 // does not escape prior to the unwind, then the caller cannot access the914 // memory either.915 if (isNoAliasCall(Object)) {916 RequiresNoCaptureBeforeUnwind = true;917 return true;918 }919 920 return false;921}922 923// We don't consider globals as writable: While the physical memory is writable,924// we may not have provenance to perform the write.925bool llvm::isWritableObject(const Value *Object,926 bool &ExplicitlyDereferenceableOnly) {927 ExplicitlyDereferenceableOnly = false;928 929 // TODO: Alloca might not be writable after its lifetime ends.930 // See https://github.com/llvm/llvm-project/issues/51838.931 if (isa<AllocaInst>(Object))932 return true;933 934 if (auto *A = dyn_cast<Argument>(Object)) {935 // Also require noalias, otherwise writability at function entry cannot be936 // generalized to writability at other program points, even if the pointer937 // does not escape.938 if (A->hasAttribute(Attribute::Writable) && A->hasNoAliasAttr()) {939 ExplicitlyDereferenceableOnly = true;940 return true;941 }942 943 return A->hasByValAttr();944 }945 946 // TODO: Noalias shouldn't imply writability, this should check for an947 // allocator function instead.948 return isNoAliasCall(Object);949}950