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