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