1//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 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 defines the primary stateless implementation of the 11// Alias Analysis interface that implements identities (two different 12// globals cannot alias, etc), but does no stateful analysis. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/Passes.h" 17#include "llvm/ADT/SmallPtrSet.h" 18#include "llvm/ADT/SmallVector.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/Analysis/CaptureTracking.h" 21#include "llvm/Analysis/CFG.h" 22#include "llvm/Analysis/Dominators.h" 23#include "llvm/Analysis/InstructionSimplify.h" 24#include "llvm/Analysis/LoopInfo.h" 25#include "llvm/Analysis/MemoryBuiltins.h" 26#include "llvm/Analysis/ValueTracking.h" 27#include "llvm/IR/Constants.h" 28#include "llvm/IR/DataLayout.h" 29#include "llvm/IR/DerivedTypes.h" 30#include "llvm/IR/Function.h" 31#include "llvm/IR/GlobalAlias.h" 32#include "llvm/IR/GlobalVariable.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/LLVMContext.h" 36#include "llvm/IR/Operator.h" 37#include "llvm/Pass.h" 38#include "llvm/Support/ErrorHandling.h" 39#include "llvm/Support/GetElementPtrTypeIterator.h" 40#include "llvm/Target/TargetLibraryInfo.h" 41#include <algorithm> 42using namespace llvm; 43 44/// Cutoff after which to stop analysing a set of phi nodes potentially involved 45/// in a cycle. Because we are analysing 'through' phi nodes we need to be 46/// careful with value equivalence. We use reachability to make sure a value 47/// cannot be involved in a cycle. 48const unsigned MaxNumPhiBBsValueReachabilityCheck = 20; 49 50//===----------------------------------------------------------------------===// 51// Useful predicates 52//===----------------------------------------------------------------------===// 53 54/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 55/// object that never escapes from the function. 56static bool isNonEscapingLocalObject(const Value *V) { 57 // If this is a local allocation, check to see if it escapes. 58 if (isa<AllocaInst>(V) || isNoAliasCall(V)) 59 // Set StoreCaptures to True so that we can assume in our callers that the 60 // pointer is not the result of a load instruction. Currently 61 // PointerMayBeCaptured doesn't have any special analysis for the 62 // StoreCaptures=false case; if it did, our callers could be refined to be 63 // more precise. 64 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 65 66 // If this is an argument that corresponds to a byval or noalias argument, 67 // then it has not escaped before entering the function. Check if it escapes 68 // inside the function. 69 if (const Argument *A = dyn_cast<Argument>(V)) 70 if (A->hasByValAttr() || A->hasNoAliasAttr()) 71 // Note even if the argument is marked nocapture we still need to check 72 // for copies made inside the function. The nocapture attribute only 73 // specifies that there are no copies made that outlive the function. 74 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 75 76 return false; 77} 78 79/// isEscapeSource - Return true if the pointer is one which would have 80/// been considered an escape by isNonEscapingLocalObject. 81static bool isEscapeSource(const Value *V) { 82 if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 83 return true; 84 85 // The load case works because isNonEscapingLocalObject considers all 86 // stores to be escapes (it passes true for the StoreCaptures argument 87 // to PointerMayBeCaptured). 88 if (isa<LoadInst>(V)) 89 return true; 90 91 return false; 92} 93 94/// getObjectSize - Return the size of the object specified by V, or 95/// UnknownSize if unknown. 96static uint64_t getObjectSize(const Value *V, const DataLayout &TD, 97 const TargetLibraryInfo &TLI, 98 bool RoundToAlign = false) { 99 uint64_t Size; 100 if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) 101 return Size; 102 return AliasAnalysis::UnknownSize; 103} 104 105/// isObjectSmallerThan - Return true if we can prove that the object specified 106/// by V is smaller than Size. 107static bool isObjectSmallerThan(const Value *V, uint64_t Size, 108 const DataLayout &TD, 109 const TargetLibraryInfo &TLI) { 110 // Note that the meanings of the "object" are slightly different in the 111 // following contexts: 112 // c1: llvm::getObjectSize() 113 // c2: llvm.objectsize() intrinsic 114 // c3: isObjectSmallerThan() 115 // c1 and c2 share the same meaning; however, the meaning of "object" in c3 116 // refers to the "entire object". 117 // 118 // Consider this example: 119 // char *p = (char*)malloc(100) 120 // char *q = p+80; 121 // 122 // In the context of c1 and c2, the "object" pointed by q refers to the 123 // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. 124 // 125 // However, in the context of c3, the "object" refers to the chunk of memory 126 // being allocated. So, the "object" has 100 bytes, and q points to the middle 127 // the "object". In case q is passed to isObjectSmallerThan() as the 1st 128 // parameter, before the llvm::getObjectSize() is called to get the size of 129 // entire object, we should: 130 // - either rewind the pointer q to the base-address of the object in 131 // question (in this case rewind to p), or 132 // - just give up. It is up to caller to make sure the pointer is pointing 133 // to the base address the object. 134 // 135 // We go for 2nd option for simplicity. 136 if (!isIdentifiedObject(V)) 137 return false; 138 139 // This function needs to use the aligned object size because we allow 140 // reads a bit past the end given sufficient alignment. 141 uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); 142 143 return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 144} 145 146/// isObjectSize - Return true if we can prove that the object specified 147/// by V has size Size. 148static bool isObjectSize(const Value *V, uint64_t Size, 149 const DataLayout &TD, const TargetLibraryInfo &TLI) { 150 uint64_t ObjectSize = getObjectSize(V, TD, TLI); 151 return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 152} 153 154/// isIdentifiedFunctionLocal - Return true if V is umabigously identified 155/// at the function-level. Different IdentifiedFunctionLocals can't alias. 156/// Further, an IdentifiedFunctionLocal can not alias with any function 157/// arguments other than itself, which is not neccessarily true for 158/// IdentifiedObjects. 159static bool isIdentifiedFunctionLocal(const Value *V) 160{ 161 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V); 162} 163 164 165//===----------------------------------------------------------------------===// 166// GetElementPtr Instruction Decomposition and Analysis 167//===----------------------------------------------------------------------===// 168 169namespace { 170 enum ExtensionKind { 171 EK_NotExtended, 172 EK_SignExt, 173 EK_ZeroExt 174 }; 175 176 struct VariableGEPIndex { 177 const Value *V; 178 ExtensionKind Extension; 179 int64_t Scale; 180 181 bool operator==(const VariableGEPIndex &Other) const { 182 return V == Other.V && Extension == Other.Extension && 183 Scale == Other.Scale; 184 } 185 186 bool operator!=(const VariableGEPIndex &Other) const { 187 return !operator==(Other); 188 } 189 }; 190} 191 192 193/// GetLinearExpression - Analyze the specified value as a linear expression: 194/// "A*V + B", where A and B are constant integers. Return the scale and offset 195/// values as APInts and return V as a Value*, and return whether we looked 196/// through any sign or zero extends. The incoming Value is known to have 197/// IntegerType and it may already be sign or zero extended. 198/// 199/// Note that this looks through extends, so the high bits may not be 200/// represented in the result. 201static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 202 ExtensionKind &Extension, 203 const DataLayout &TD, unsigned Depth) { 204 assert(V->getType()->isIntegerTy() && "Not an integer value"); 205 206 // Limit our recursion depth. 207 if (Depth == 6) { 208 Scale = 1; 209 Offset = 0; 210 return V; 211 } 212 213 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 214 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 215 switch (BOp->getOpcode()) { 216 default: break; 217 case Instruction::Or: 218 // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 219 // analyze it. 220 if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 221 break; 222 // FALL THROUGH. 223 case Instruction::Add: 224 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 225 TD, Depth+1); 226 Offset += RHSC->getValue(); 227 return V; 228 case Instruction::Mul: 229 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 230 TD, Depth+1); 231 Offset *= RHSC->getValue(); 232 Scale *= RHSC->getValue(); 233 return V; 234 case Instruction::Shl: 235 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 236 TD, Depth+1); 237 Offset <<= RHSC->getValue().getLimitedValue(); 238 Scale <<= RHSC->getValue().getLimitedValue(); 239 return V; 240 } 241 } 242 } 243 244 // Since GEP indices are sign extended anyway, we don't care about the high 245 // bits of a sign or zero extended value - just scales and offsets. The 246 // extensions have to be consistent though. 247 if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 248 (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 249 Value *CastOp = cast<CastInst>(V)->getOperand(0); 250 unsigned OldWidth = Scale.getBitWidth(); 251 unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 252 Scale = Scale.trunc(SmallWidth); 253 Offset = Offset.trunc(SmallWidth); 254 Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 255 256 Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 257 TD, Depth+1); 258 Scale = Scale.zext(OldWidth); 259 Offset = Offset.zext(OldWidth); 260 261 return Result; 262 } 263 264 Scale = 1; 265 Offset = 0; 266 return V; 267} 268 269/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 270/// into a base pointer with a constant offset and a number of scaled symbolic 271/// offsets. 272/// 273/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 274/// the VarIndices vector) are Value*'s that are known to be scaled by the 275/// specified amount, but which may have other unrepresented high bits. As such, 276/// the gep cannot necessarily be reconstructed from its decomposed form. 277/// 278/// When DataLayout is around, this function is capable of analyzing everything 279/// that GetUnderlyingObject can look through. When not, it just looks 280/// through pointer casts. 281/// 282static const Value * 283DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 284 SmallVectorImpl<VariableGEPIndex> &VarIndices, 285 const DataLayout *TD) { 286 // Limit recursion depth to limit compile time in crazy cases. 287 unsigned MaxLookup = 6; 288 289 BaseOffs = 0; 290 do { 291 // See if this is a bitcast or GEP. 292 const Operator *Op = dyn_cast<Operator>(V); 293 if (Op == 0) { 294 // The only non-operator case we can handle are GlobalAliases. 295 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 296 if (!GA->mayBeOverridden()) { 297 V = GA->getAliasee(); 298 continue; 299 } 300 } 301 return V; 302 } 303 304 if (Op->getOpcode() == Instruction::BitCast) { 305 V = Op->getOperand(0); 306 continue; 307 } 308 309 const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 310 if (GEPOp == 0) { 311 // If it's not a GEP, hand it off to SimplifyInstruction to see if it 312 // can come up with something. This matches what GetUnderlyingObject does. 313 if (const Instruction *I = dyn_cast<Instruction>(V)) 314 // TODO: Get a DominatorTree and use it here. 315 if (const Value *Simplified = 316 SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 317 V = Simplified; 318 continue; 319 } 320 321 return V; 322 } 323 324 // Don't attempt to analyze GEPs over unsized objects. 325 if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized()) 326 return V; 327 328 // If we are lacking DataLayout information, we can't compute the offets of 329 // elements computed by GEPs. However, we can handle bitcast equivalent 330 // GEPs. 331 if (TD == 0) { 332 if (!GEPOp->hasAllZeroIndices()) 333 return V; 334 V = GEPOp->getOperand(0); 335 continue; 336 } 337 338 unsigned AS = GEPOp->getPointerAddressSpace(); 339 // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 340 gep_type_iterator GTI = gep_type_begin(GEPOp); 341 for (User::const_op_iterator I = GEPOp->op_begin()+1, 342 E = GEPOp->op_end(); I != E; ++I) { 343 Value *Index = *I; 344 // Compute the (potentially symbolic) offset in bytes for this index. 345 if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 346 // For a struct, add the member offset. 347 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 348 if (FieldNo == 0) continue; 349 350 BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 351 continue; 352 } 353 354 // For an array/pointer, add the element offset, explicitly scaled. 355 if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 356 if (CIdx->isZero()) continue; 357 BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 358 continue; 359 } 360 361 uint64_t Scale = TD->getTypeAllocSize(*GTI); 362 ExtensionKind Extension = EK_NotExtended; 363 364 // If the integer type is smaller than the pointer size, it is implicitly 365 // sign extended to pointer size. 366 unsigned Width = Index->getType()->getIntegerBitWidth(); 367 if (TD->getPointerSizeInBits(AS) > Width) 368 Extension = EK_SignExt; 369 370 // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 371 APInt IndexScale(Width, 0), IndexOffset(Width, 0); 372 Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 373 *TD, 0); 374 375 // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 376 // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 377 BaseOffs += IndexOffset.getSExtValue()*Scale; 378 Scale *= IndexScale.getSExtValue(); 379 380 // If we already had an occurrence of this index variable, merge this 381 // scale into it. For example, we want to handle: 382 // A[x][x] -> x*16 + x*4 -> x*20 383 // This also ensures that 'x' only appears in the index list once. 384 for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 385 if (VarIndices[i].V == Index && 386 VarIndices[i].Extension == Extension) { 387 Scale += VarIndices[i].Scale; 388 VarIndices.erase(VarIndices.begin()+i); 389 break; 390 } 391 } 392 393 // Make sure that we have a scale that makes sense for this target's 394 // pointer size. 395 if (unsigned ShiftBits = 64 - TD->getPointerSizeInBits(AS)) { 396 Scale <<= ShiftBits; 397 Scale = (int64_t)Scale >> ShiftBits; 398 } 399 400 if (Scale) { 401 VariableGEPIndex Entry = {Index, Extension, 402 static_cast<int64_t>(Scale)}; 403 VarIndices.push_back(Entry); 404 } 405 } 406 407 // Analyze the base pointer next. 408 V = GEPOp->getOperand(0); 409 } while (--MaxLookup); 410 411 // If the chain of expressions is too deep, just return early. 412 return V; 413} 414 415//===----------------------------------------------------------------------===// 416// BasicAliasAnalysis Pass 417//===----------------------------------------------------------------------===// 418 419#ifndef NDEBUG 420static const Function *getParent(const Value *V) { 421 if (const Instruction *inst = dyn_cast<Instruction>(V)) 422 return inst->getParent()->getParent(); 423 424 if (const Argument *arg = dyn_cast<Argument>(V)) 425 return arg->getParent(); 426 427 return NULL; 428} 429 430static bool notDifferentParent(const Value *O1, const Value *O2) { 431 432 const Function *F1 = getParent(O1); 433 const Function *F2 = getParent(O2); 434 435 return !F1 || !F2 || F1 == F2; 436} 437#endif 438 439namespace { 440 /// BasicAliasAnalysis - This is the primary alias analysis implementation. 441 struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 442 static char ID; // Class identification, replacement for typeinfo 443 BasicAliasAnalysis() : ImmutablePass(ID) { 444 initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 445 } 446 447 virtual void initializePass() { 448 InitializeAliasAnalysis(this); 449 } 450 451 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 452 AU.addRequired<AliasAnalysis>(); 453 AU.addRequired<TargetLibraryInfo>(); 454 } 455 456 virtual AliasResult alias(const Location &LocA, 457 const Location &LocB) { 458 assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 459 assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 460 "BasicAliasAnalysis doesn't support interprocedural queries."); 461 AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 462 LocB.Ptr, LocB.Size, LocB.TBAATag); 463 // AliasCache rarely has more than 1 or 2 elements, always use 464 // shrink_and_clear so it quickly returns to the inline capacity of the 465 // SmallDenseMap if it ever grows larger. 466 // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 467 AliasCache.shrink_and_clear(); 468 VisitedPhiBBs.clear(); 469 return Alias; 470 } 471 472 virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 473 const Location &Loc); 474 475 virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 476 ImmutableCallSite CS2) { 477 // The AliasAnalysis base class has some smarts, lets use them. 478 return AliasAnalysis::getModRefInfo(CS1, CS2); 479 } 480 481 /// pointsToConstantMemory - Chase pointers until we find a (constant 482 /// global) or not. 483 virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 484 485 /// getModRefBehavior - Return the behavior when calling the given 486 /// call site. 487 virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 488 489 /// getModRefBehavior - Return the behavior when calling the given function. 490 /// For use when the call site is not known. 491 virtual ModRefBehavior getModRefBehavior(const Function *F); 492 493 /// getAdjustedAnalysisPointer - This method is used when a pass implements 494 /// an analysis interface through multiple inheritance. If needed, it 495 /// should override this to adjust the this pointer as needed for the 496 /// specified pass info. 497 virtual void *getAdjustedAnalysisPointer(const void *ID) { 498 if (ID == &AliasAnalysis::ID) 499 return (AliasAnalysis*)this; 500 return this; 501 } 502 503 private: 504 // AliasCache - Track alias queries to guard against recursion. 505 typedef std::pair<Location, Location> LocPair; 506 typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; 507 AliasCacheTy AliasCache; 508 509 /// \brief Track phi nodes we have visited. When interpret "Value" pointer 510 /// equality as value equality we need to make sure that the "Value" is not 511 /// part of a cycle. Otherwise, two uses could come from different 512 /// "iterations" of a cycle and see different values for the same "Value" 513 /// pointer. 514 /// The following example shows the problem: 515 /// %p = phi(%alloca1, %addr2) 516 /// %l = load %ptr 517 /// %addr1 = gep, %alloca2, 0, %l 518 /// %addr2 = gep %alloca2, 0, (%l + 1) 519 /// alias(%p, %addr1) -> MayAlias ! 520 /// store %l, ... 521 SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs; 522 523 // Visited - Track instructions visited by pointsToConstantMemory. 524 SmallPtrSet<const Value*, 16> Visited; 525 526 /// \brief Check whether two Values can be considered equivalent. 527 /// 528 /// In addition to pointer equivalence of \p V1 and \p V2 this checks 529 /// whether they can not be part of a cycle in the value graph by looking at 530 /// all visited phi nodes an making sure that the phis cannot reach the 531 /// value. We have to do this because we are looking through phi nodes (That 532 /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). 533 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); 534 535 /// \brief Dest and Src are the variable indices from two decomposed 536 /// GetElementPtr instructions GEP1 and GEP2 which have common base 537 /// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 538 /// difference between the two pointers. 539 void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 540 const SmallVectorImpl<VariableGEPIndex> &Src); 541 542 // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 543 // instruction against another. 544 AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 545 const MDNode *V1TBAAInfo, 546 const Value *V2, uint64_t V2Size, 547 const MDNode *V2TBAAInfo, 548 const Value *UnderlyingV1, const Value *UnderlyingV2); 549 550 // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 551 // instruction against another. 552 AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 553 const MDNode *PNTBAAInfo, 554 const Value *V2, uint64_t V2Size, 555 const MDNode *V2TBAAInfo); 556 557 /// aliasSelect - Disambiguate a Select instruction against another value. 558 AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 559 const MDNode *SITBAAInfo, 560 const Value *V2, uint64_t V2Size, 561 const MDNode *V2TBAAInfo); 562 563 AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 564 const MDNode *V1TBAATag, 565 const Value *V2, uint64_t V2Size, 566 const MDNode *V2TBAATag); 567 }; 568} // End of anonymous namespace 569 570// Register this pass... 571char BasicAliasAnalysis::ID = 0; 572INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 573 "Basic Alias Analysis (stateless AA impl)", 574 false, true, false) 575INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 576INITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 577 "Basic Alias Analysis (stateless AA impl)", 578 false, true, false) 579 580 581ImmutablePass *llvm::createBasicAliasAnalysisPass() { 582 return new BasicAliasAnalysis(); 583} 584 585/// pointsToConstantMemory - Returns whether the given pointer value 586/// points to memory that is local to the function, with global constants being 587/// considered local to all functions. 588bool 589BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 590 assert(Visited.empty() && "Visited must be cleared after use!"); 591 592 unsigned MaxLookup = 8; 593 SmallVector<const Value *, 16> Worklist; 594 Worklist.push_back(Loc.Ptr); 595 do { 596 const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 597 if (!Visited.insert(V)) { 598 Visited.clear(); 599 return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 600 } 601 602 // An alloca instruction defines local memory. 603 if (OrLocal && isa<AllocaInst>(V)) 604 continue; 605 606 // A global constant counts as local memory for our purposes. 607 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 608 // Note: this doesn't require GV to be "ODR" because it isn't legal for a 609 // global to be marked constant in some modules and non-constant in 610 // others. GV may even be a declaration, not a definition. 611 if (!GV->isConstant()) { 612 Visited.clear(); 613 return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 614 } 615 continue; 616 } 617 618 // If both select values point to local memory, then so does the select. 619 if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 620 Worklist.push_back(SI->getTrueValue()); 621 Worklist.push_back(SI->getFalseValue()); 622 continue; 623 } 624 625 // If all values incoming to a phi node point to local memory, then so does 626 // the phi. 627 if (const PHINode *PN = dyn_cast<PHINode>(V)) { 628 // Don't bother inspecting phi nodes with many operands. 629 if (PN->getNumIncomingValues() > MaxLookup) { 630 Visited.clear(); 631 return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 632 } 633 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 634 Worklist.push_back(PN->getIncomingValue(i)); 635 continue; 636 } 637 638 // Otherwise be conservative. 639 Visited.clear(); 640 return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 641 642 } while (!Worklist.empty() && --MaxLookup); 643 644 Visited.clear(); 645 return Worklist.empty(); 646} 647 648/// getModRefBehavior - Return the behavior when calling the given call site. 649AliasAnalysis::ModRefBehavior 650BasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 651 if (CS.doesNotAccessMemory()) 652 // Can't do better than this. 653 return DoesNotAccessMemory; 654 655 ModRefBehavior Min = UnknownModRefBehavior; 656 657 // If the callsite knows it only reads memory, don't return worse 658 // than that. 659 if (CS.onlyReadsMemory()) 660 Min = OnlyReadsMemory; 661 662 // The AliasAnalysis base class has some smarts, lets use them. 663 return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 664} 665 666/// getModRefBehavior - Return the behavior when calling the given function. 667/// For use when the call site is not known. 668AliasAnalysis::ModRefBehavior 669BasicAliasAnalysis::getModRefBehavior(const Function *F) { 670 // If the function declares it doesn't access memory, we can't do better. 671 if (F->doesNotAccessMemory()) 672 return DoesNotAccessMemory; 673 674 // For intrinsics, we can check the table. 675 if (unsigned iid = F->getIntrinsicID()) { 676#define GET_INTRINSIC_MODREF_BEHAVIOR 677#include "llvm/IR/Intrinsics.gen" 678#undef GET_INTRINSIC_MODREF_BEHAVIOR 679 } 680 681 ModRefBehavior Min = UnknownModRefBehavior; 682 683 // If the function declares it only reads memory, go with that. 684 if (F->onlyReadsMemory()) 685 Min = OnlyReadsMemory; 686 687 // Otherwise be conservative. 688 return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 689} 690 691/// getModRefInfo - Check to see if the specified callsite can clobber the 692/// specified memory object. Since we only look at local properties of this 693/// function, we really can't say much about this query. We do, however, use 694/// simple "address taken" analysis on local objects. 695AliasAnalysis::ModRefResult 696BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 697 const Location &Loc) { 698 assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 699 "AliasAnalysis query involving multiple functions!"); 700 701 const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 702 703 // If this is a tail call and Loc.Ptr points to a stack location, we know that 704 // the tail call cannot access or modify the local stack. 705 // We cannot exclude byval arguments here; these belong to the caller of 706 // the current function not to the current function, and a tail callee 707 // may reference them. 708 if (isa<AllocaInst>(Object)) 709 if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 710 if (CI->isTailCall()) 711 return NoModRef; 712 713 // If the pointer is to a locally allocated object that does not escape, 714 // then the call can not mod/ref the pointer unless the call takes the pointer 715 // as an argument, and itself doesn't capture it. 716 if (!isa<Constant>(Object) && CS.getInstruction() != Object && 717 isNonEscapingLocalObject(Object)) { 718 bool PassedAsArg = false; 719 unsigned ArgNo = 0; 720 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 721 CI != CE; ++CI, ++ArgNo) { 722 // Only look at the no-capture or byval pointer arguments. If this 723 // pointer were passed to arguments that were neither of these, then it 724 // couldn't be no-capture. 725 if (!(*CI)->getType()->isPointerTy() || 726 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 727 continue; 728 729 // If this is a no-capture pointer argument, see if we can tell that it 730 // is impossible to alias the pointer we're checking. If not, we have to 731 // assume that the call could touch the pointer, even though it doesn't 732 // escape. 733 if (!isNoAlias(Location(*CI), Location(Object))) { 734 PassedAsArg = true; 735 break; 736 } 737 } 738 739 if (!PassedAsArg) 740 return NoModRef; 741 } 742 743 const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 744 ModRefResult Min = ModRef; 745 746 // Finally, handle specific knowledge of intrinsics. 747 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 748 if (II != 0) 749 switch (II->getIntrinsicID()) { 750 default: break; 751 case Intrinsic::memcpy: 752 case Intrinsic::memmove: { 753 uint64_t Len = UnknownSize; 754 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 755 Len = LenCI->getZExtValue(); 756 Value *Dest = II->getArgOperand(0); 757 Value *Src = II->getArgOperand(1); 758 // If it can't overlap the source dest, then it doesn't modref the loc. 759 if (isNoAlias(Location(Dest, Len), Loc)) { 760 if (isNoAlias(Location(Src, Len), Loc)) 761 return NoModRef; 762 // If it can't overlap the dest, then worst case it reads the loc. 763 Min = Ref; 764 } else if (isNoAlias(Location(Src, Len), Loc)) { 765 // If it can't overlap the source, then worst case it mutates the loc. 766 Min = Mod; 767 } 768 break; 769 } 770 case Intrinsic::memset: 771 // Since memset is 'accesses arguments' only, the AliasAnalysis base class 772 // will handle it for the variable length case. 773 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 774 uint64_t Len = LenCI->getZExtValue(); 775 Value *Dest = II->getArgOperand(0); 776 if (isNoAlias(Location(Dest, Len), Loc)) 777 return NoModRef; 778 } 779 // We know that memset doesn't load anything. 780 Min = Mod; 781 break; 782 case Intrinsic::lifetime_start: 783 case Intrinsic::lifetime_end: 784 case Intrinsic::invariant_start: { 785 uint64_t PtrSize = 786 cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 787 if (isNoAlias(Location(II->getArgOperand(1), 788 PtrSize, 789 II->getMetadata(LLVMContext::MD_tbaa)), 790 Loc)) 791 return NoModRef; 792 break; 793 } 794 case Intrinsic::invariant_end: { 795 uint64_t PtrSize = 796 cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 797 if (isNoAlias(Location(II->getArgOperand(2), 798 PtrSize, 799 II->getMetadata(LLVMContext::MD_tbaa)), 800 Loc)) 801 return NoModRef; 802 break; 803 } 804 case Intrinsic::arm_neon_vld1: { 805 // LLVM's vld1 and vst1 intrinsics currently only support a single 806 // vector register. 807 uint64_t Size = 808 TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 809 if (isNoAlias(Location(II->getArgOperand(0), Size, 810 II->getMetadata(LLVMContext::MD_tbaa)), 811 Loc)) 812 return NoModRef; 813 break; 814 } 815 case Intrinsic::arm_neon_vst1: { 816 uint64_t Size = 817 TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 818 if (isNoAlias(Location(II->getArgOperand(0), Size, 819 II->getMetadata(LLVMContext::MD_tbaa)), 820 Loc)) 821 return NoModRef; 822 break; 823 } 824 } 825 826 // We can bound the aliasing properties of memset_pattern16 just as we can 827 // for memcpy/memset. This is particularly important because the 828 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 829 // whenever possible. 830 else if (TLI.has(LibFunc::memset_pattern16) && 831 CS.getCalledFunction() && 832 CS.getCalledFunction()->getName() == "memset_pattern16") { 833 const Function *MS = CS.getCalledFunction(); 834 FunctionType *MemsetType = MS->getFunctionType(); 835 if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 836 isa<PointerType>(MemsetType->getParamType(0)) && 837 isa<PointerType>(MemsetType->getParamType(1)) && 838 isa<IntegerType>(MemsetType->getParamType(2))) { 839 uint64_t Len = UnknownSize; 840 if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 841 Len = LenCI->getZExtValue(); 842 const Value *Dest = CS.getArgument(0); 843 const Value *Src = CS.getArgument(1); 844 // If it can't overlap the source dest, then it doesn't modref the loc. 845 if (isNoAlias(Location(Dest, Len), Loc)) { 846 // Always reads 16 bytes of the source. 847 if (isNoAlias(Location(Src, 16), Loc)) 848 return NoModRef; 849 // If it can't overlap the dest, then worst case it reads the loc. 850 Min = Ref; 851 // Always reads 16 bytes of the source. 852 } else if (isNoAlias(Location(Src, 16), Loc)) { 853 // If it can't overlap the source, then worst case it mutates the loc. 854 Min = Mod; 855 } 856 } 857 } 858 859 // The AliasAnalysis base class has some smarts, lets use them. 860 return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 861} 862 863static bool areVarIndicesEqual(SmallVectorImpl<VariableGEPIndex> &Indices1, 864 SmallVectorImpl<VariableGEPIndex> &Indices2) { 865 unsigned Size1 = Indices1.size(); 866 unsigned Size2 = Indices2.size(); 867 868 if (Size1 != Size2) 869 return false; 870 871 for (unsigned I = 0; I != Size1; ++I) 872 if (Indices1[I] != Indices2[I]) 873 return false; 874 875 return true; 876} 877 878/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 879/// against another pointer. We know that V1 is a GEP, but we don't know 880/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 881/// UnderlyingV2 is the same for V2. 882/// 883AliasAnalysis::AliasResult 884BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 885 const MDNode *V1TBAAInfo, 886 const Value *V2, uint64_t V2Size, 887 const MDNode *V2TBAAInfo, 888 const Value *UnderlyingV1, 889 const Value *UnderlyingV2) { 890 int64_t GEP1BaseOffset; 891 SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 892 893 // If we have two gep instructions with must-alias or not-alias'ing base 894 // pointers, figure out if the indexes to the GEP tell us anything about the 895 // derived pointer. 896 if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 897 // Do the base pointers alias? 898 AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 899 UnderlyingV2, UnknownSize, 0); 900 901 // Check for geps of non-aliasing underlying pointers where the offsets are 902 // identical. 903 if ((BaseAlias == MayAlias) && V1Size == V2Size) { 904 // Do the base pointers alias assuming type and size. 905 AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, 906 V1TBAAInfo, UnderlyingV2, 907 V2Size, V2TBAAInfo); 908 if (PreciseBaseAlias == NoAlias) { 909 // See if the computed offset from the common pointer tells us about the 910 // relation of the resulting pointer. 911 int64_t GEP2BaseOffset; 912 SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 913 const Value *GEP2BasePtr = 914 DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 915 const Value *GEP1BasePtr = 916 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 917 // DecomposeGEPExpression and GetUnderlyingObject should return the 918 // same result except when DecomposeGEPExpression has no DataLayout. 919 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 920 assert(TD == 0 && 921 "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 922 return MayAlias; 923 } 924 // Same offsets. 925 if (GEP1BaseOffset == GEP2BaseOffset && 926 areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) 927 return NoAlias; 928 GEP1VariableIndices.clear(); 929 } 930 } 931 932 // If we get a No or May, then return it immediately, no amount of analysis 933 // will improve this situation. 934 if (BaseAlias != MustAlias) return BaseAlias; 935 936 // Otherwise, we have a MustAlias. Since the base pointers alias each other 937 // exactly, see if the computed offset from the common pointer tells us 938 // about the relation of the resulting pointer. 939 const Value *GEP1BasePtr = 940 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 941 942 int64_t GEP2BaseOffset; 943 SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 944 const Value *GEP2BasePtr = 945 DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 946 947 // DecomposeGEPExpression and GetUnderlyingObject should return the 948 // same result except when DecomposeGEPExpression has no DataLayout. 949 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 950 assert(TD == 0 && 951 "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 952 return MayAlias; 953 } 954 955 // Subtract the GEP2 pointer from the GEP1 pointer to find out their 956 // symbolic difference. 957 GEP1BaseOffset -= GEP2BaseOffset; 958 GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 959 960 } else { 961 // Check to see if these two pointers are related by the getelementptr 962 // instruction. If one pointer is a GEP with a non-zero index of the other 963 // pointer, we know they cannot alias. 964 965 // If both accesses are unknown size, we can't do anything useful here. 966 if (V1Size == UnknownSize && V2Size == UnknownSize) 967 return MayAlias; 968 969 AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 970 V2, V2Size, V2TBAAInfo); 971 if (R != MustAlias) 972 // If V2 may alias GEP base pointer, conservatively returns MayAlias. 973 // If V2 is known not to alias GEP base pointer, then the two values 974 // cannot alias per GEP semantics: "A pointer value formed from a 975 // getelementptr instruction is associated with the addresses associated 976 // with the first operand of the getelementptr". 977 return R; 978 979 const Value *GEP1BasePtr = 980 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 981 982 // DecomposeGEPExpression and GetUnderlyingObject should return the 983 // same result except when DecomposeGEPExpression has no DataLayout. 984 if (GEP1BasePtr != UnderlyingV1) { 985 assert(TD == 0 && 986 "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 987 return MayAlias; 988 } 989 } 990 991 // In the two GEP Case, if there is no difference in the offsets of the 992 // computed pointers, the resultant pointers are a must alias. This 993 // hapens when we have two lexically identical GEP's (for example). 994 // 995 // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 996 // must aliases the GEP, the end result is a must alias also. 997 if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 998 return MustAlias; 999 1000 // If there is a constant difference between the pointers, but the difference 1001 // is less than the size of the associated memory object, then we know 1002 // that the objects are partially overlapping. If the difference is 1003 // greater, we know they do not overlap. 1004 if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 1005 if (GEP1BaseOffset >= 0) { 1006 if (V2Size != UnknownSize) { 1007 if ((uint64_t)GEP1BaseOffset < V2Size) 1008 return PartialAlias; 1009 return NoAlias; 1010 } 1011 } else { 1012 // We have the situation where: 1013 // + + 1014 // | BaseOffset | 1015 // ---------------->| 1016 // |-->V1Size |-------> V2Size 1017 // GEP1 V2 1018 // We need to know that V2Size is not unknown, otherwise we might have 1019 // stripped a gep with negative index ('gep <ptr>, -1, ...). 1020 if (V1Size != UnknownSize && V2Size != UnknownSize) { 1021 if (-(uint64_t)GEP1BaseOffset < V1Size) 1022 return PartialAlias; 1023 return NoAlias; 1024 } 1025 } 1026 } 1027 1028 // Try to distinguish something like &A[i][1] against &A[42][0]. 1029 // Grab the least significant bit set in any of the scales. 1030 if (!GEP1VariableIndices.empty()) { 1031 uint64_t Modulo = 0; 1032 for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 1033 Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 1034 Modulo = Modulo ^ (Modulo & (Modulo - 1)); 1035 1036 // We can compute the difference between the two addresses 1037 // mod Modulo. Check whether that difference guarantees that the 1038 // two locations do not alias. 1039 uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 1040 if (V1Size != UnknownSize && V2Size != UnknownSize && 1041 ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 1042 return NoAlias; 1043 } 1044 1045 // Statically, we can see that the base objects are the same, but the 1046 // pointers have dynamic offsets which we can't resolve. And none of our 1047 // little tricks above worked. 1048 // 1049 // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 1050 // practical effect of this is protecting TBAA in the case of dynamic 1051 // indices into arrays of unions or malloc'd memory. 1052 return PartialAlias; 1053} 1054 1055static AliasAnalysis::AliasResult 1056MergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 1057 // If the results agree, take it. 1058 if (A == B) 1059 return A; 1060 // A mix of PartialAlias and MustAlias is PartialAlias. 1061 if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 1062 (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 1063 return AliasAnalysis::PartialAlias; 1064 // Otherwise, we don't know anything. 1065 return AliasAnalysis::MayAlias; 1066} 1067 1068/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 1069/// instruction against another. 1070AliasAnalysis::AliasResult 1071BasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 1072 const MDNode *SITBAAInfo, 1073 const Value *V2, uint64_t V2Size, 1074 const MDNode *V2TBAAInfo) { 1075 // If the values are Selects with the same condition, we can do a more precise 1076 // check: just check for aliases between the values on corresponding arms. 1077 if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1078 if (SI->getCondition() == SI2->getCondition()) { 1079 AliasResult Alias = 1080 aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 1081 SI2->getTrueValue(), V2Size, V2TBAAInfo); 1082 if (Alias == MayAlias) 1083 return MayAlias; 1084 AliasResult ThisAlias = 1085 aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 1086 SI2->getFalseValue(), V2Size, V2TBAAInfo); 1087 return MergeAliasResults(ThisAlias, Alias); 1088 } 1089 1090 // If both arms of the Select node NoAlias or MustAlias V2, then returns 1091 // NoAlias / MustAlias. Otherwise, returns MayAlias. 1092 AliasResult Alias = 1093 aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 1094 if (Alias == MayAlias) 1095 return MayAlias; 1096 1097 AliasResult ThisAlias = 1098 aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 1099 return MergeAliasResults(ThisAlias, Alias); 1100} 1101 1102// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 1103// against another. 1104AliasAnalysis::AliasResult 1105BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 1106 const MDNode *PNTBAAInfo, 1107 const Value *V2, uint64_t V2Size, 1108 const MDNode *V2TBAAInfo) { 1109 // Track phi nodes we have visited. We use this information when we determine 1110 // value equivalence. 1111 VisitedPhiBBs.insert(PN->getParent()); 1112 1113 // If the values are PHIs in the same block, we can do a more precise 1114 // as well as efficient check: just check for aliases between the values 1115 // on corresponding edges. 1116 if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1117 if (PN2->getParent() == PN->getParent()) { 1118 LocPair Locs(Location(PN, PNSize, PNTBAAInfo), 1119 Location(V2, V2Size, V2TBAAInfo)); 1120 if (PN > V2) 1121 std::swap(Locs.first, Locs.second); 1122 // Analyse the PHIs' inputs under the assumption that the PHIs are 1123 // NoAlias. 1124 // If the PHIs are May/MustAlias there must be (recursively) an input 1125 // operand from outside the PHIs' cycle that is MayAlias/MustAlias or 1126 // there must be an operation on the PHIs within the PHIs' value cycle 1127 // that causes a MayAlias. 1128 // Pretend the phis do not alias. 1129 AliasResult Alias = NoAlias; 1130 assert(AliasCache.count(Locs) && 1131 "There must exist an entry for the phi node"); 1132 AliasResult OrigAliasResult = AliasCache[Locs]; 1133 AliasCache[Locs] = NoAlias; 1134 1135 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1136 AliasResult ThisAlias = 1137 aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 1138 PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 1139 V2Size, V2TBAAInfo); 1140 Alias = MergeAliasResults(ThisAlias, Alias); 1141 if (Alias == MayAlias) 1142 break; 1143 } 1144 1145 // Reset if speculation failed. 1146 if (Alias != NoAlias) 1147 AliasCache[Locs] = OrigAliasResult; 1148 1149 return Alias; 1150 } 1151 1152 SmallPtrSet<Value*, 4> UniqueSrc; 1153 SmallVector<Value*, 4> V1Srcs; 1154 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1155 Value *PV1 = PN->getIncomingValue(i); 1156 if (isa<PHINode>(PV1)) 1157 // If any of the source itself is a PHI, return MayAlias conservatively 1158 // to avoid compile time explosion. The worst possible case is if both 1159 // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1160 // and 'n' are the number of PHI sources. 1161 return MayAlias; 1162 if (UniqueSrc.insert(PV1)) 1163 V1Srcs.push_back(PV1); 1164 } 1165 1166 AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 1167 V1Srcs[0], PNSize, PNTBAAInfo); 1168 // Early exit if the check of the first PHI source against V2 is MayAlias. 1169 // Other results are not possible. 1170 if (Alias == MayAlias) 1171 return MayAlias; 1172 1173 // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1174 // NoAlias / MustAlias. Otherwise, returns MayAlias. 1175 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1176 Value *V = V1Srcs[i]; 1177 1178 AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 1179 V, PNSize, PNTBAAInfo); 1180 Alias = MergeAliasResults(ThisAlias, Alias); 1181 if (Alias == MayAlias) 1182 break; 1183 } 1184 1185 return Alias; 1186} 1187 1188// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 1189// such as array references. 1190// 1191AliasAnalysis::AliasResult 1192BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 1193 const MDNode *V1TBAAInfo, 1194 const Value *V2, uint64_t V2Size, 1195 const MDNode *V2TBAAInfo) { 1196 // If either of the memory references is empty, it doesn't matter what the 1197 // pointer values are. 1198 if (V1Size == 0 || V2Size == 0) 1199 return NoAlias; 1200 1201 // Strip off any casts if they exist. 1202 V1 = V1->stripPointerCasts(); 1203 V2 = V2->stripPointerCasts(); 1204 1205 // Are we checking for alias of the same value? 1206 // Because we look 'through' phi nodes we could look at "Value" pointers from 1207 // different iterations. We must therefore make sure that this is not the 1208 // case. The function isValueEqualInPotentialCycles ensures that this cannot 1209 // happen by looking at the visited phi nodes and making sure they cannot 1210 // reach the value. 1211 if (isValueEqualInPotentialCycles(V1, V2)) 1212 return MustAlias; 1213 1214 if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1215 return NoAlias; // Scalars cannot alias each other 1216 1217 // Figure out what objects these things are pointing to if we can. 1218 const Value *O1 = GetUnderlyingObject(V1, TD); 1219 const Value *O2 = GetUnderlyingObject(V2, TD); 1220 1221 // Null values in the default address space don't point to any object, so they 1222 // don't alias any other pointer. 1223 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1224 if (CPN->getType()->getAddressSpace() == 0) 1225 return NoAlias; 1226 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1227 if (CPN->getType()->getAddressSpace() == 0) 1228 return NoAlias; 1229 1230 if (O1 != O2) { 1231 // If V1/V2 point to two different objects we know that we have no alias. 1232 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1233 return NoAlias; 1234 1235 // Constant pointers can't alias with non-const isIdentifiedObject objects. 1236 if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1237 (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1238 return NoAlias; 1239 1240 // Function arguments can't alias with things that are known to be 1241 // unambigously identified at the function level. 1242 if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || 1243 (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) 1244 return NoAlias; 1245 1246 // Most objects can't alias null. 1247 if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1248 (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1249 return NoAlias; 1250 1251 // If one pointer is the result of a call/invoke or load and the other is a 1252 // non-escaping local object within the same function, then we know the 1253 // object couldn't escape to a point where the call could return it. 1254 // 1255 // Note that if the pointers are in different functions, there are a 1256 // variety of complications. A call with a nocapture argument may still 1257 // temporary store the nocapture argument's value in a temporary memory 1258 // location if that memory location doesn't escape. Or it may pass a 1259 // nocapture value to other functions as long as they don't capture it. 1260 if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1261 return NoAlias; 1262 if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1263 return NoAlias; 1264 } 1265 1266 // If the size of one access is larger than the entire object on the other 1267 // side, then we know such behavior is undefined and can assume no alias. 1268 if (TD) 1269 if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || 1270 (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) 1271 return NoAlias; 1272 1273 // Check the cache before climbing up use-def chains. This also terminates 1274 // otherwise infinitely recursive queries. 1275 LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 1276 Location(V2, V2Size, V2TBAAInfo)); 1277 if (V1 > V2) 1278 std::swap(Locs.first, Locs.second); 1279 std::pair<AliasCacheTy::iterator, bool> Pair = 1280 AliasCache.insert(std::make_pair(Locs, MayAlias)); 1281 if (!Pair.second) 1282 return Pair.first->second; 1283 1284 // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1285 // GEP can't simplify, we don't even look at the PHI cases. 1286 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1287 std::swap(V1, V2); 1288 std::swap(V1Size, V2Size); 1289 std::swap(O1, O2); 1290 std::swap(V1TBAAInfo, V2TBAAInfo); 1291 } 1292 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1293 AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); 1294 if (Result != MayAlias) return AliasCache[Locs] = Result; 1295 } 1296 1297 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1298 std::swap(V1, V2); 1299 std::swap(V1Size, V2Size); 1300 std::swap(V1TBAAInfo, V2TBAAInfo); 1301 } 1302 if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 1303 AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 1304 V2, V2Size, V2TBAAInfo); 1305 if (Result != MayAlias) return AliasCache[Locs] = Result; 1306 } 1307 1308 if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1309 std::swap(V1, V2); 1310 std::swap(V1Size, V2Size); 1311 std::swap(V1TBAAInfo, V2TBAAInfo); 1312 } 1313 if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 1314 AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 1315 V2, V2Size, V2TBAAInfo); 1316 if (Result != MayAlias) return AliasCache[Locs] = Result; 1317 } 1318 1319 // If both pointers are pointing into the same object and one of them 1320 // accesses is accessing the entire object, then the accesses must 1321 // overlap in some way. 1322 if (TD && O1 == O2) 1323 if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || 1324 (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) 1325 return AliasCache[Locs] = PartialAlias; 1326 1327 AliasResult Result = 1328 AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 1329 Location(V2, V2Size, V2TBAAInfo)); 1330 return AliasCache[Locs] = Result; 1331} 1332 1333bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V, 1334 const Value *V2) { 1335 if (V != V2) 1336 return false; 1337 1338 const Instruction *Inst = dyn_cast<Instruction>(V); 1339 if (!Inst) 1340 return true; 1341 1342 if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) 1343 return false; 1344 1345 // Use dominance or loop info if available. 1346 DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); 1347 LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>(); 1348 1349 // Make sure that the visited phis cannot reach the Value. This ensures that 1350 // the Values cannot come from different iterations of a potential cycle the 1351 // phi nodes could be involved in. 1352 for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(), 1353 PE = VisitedPhiBBs.end(); 1354 PI != PE; ++PI) 1355 if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI)) 1356 return false; 1357 1358 return true; 1359} 1360 1361/// GetIndexDifference - Dest and Src are the variable indices from two 1362/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 1363/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 1364/// difference between the two pointers. 1365void BasicAliasAnalysis::GetIndexDifference( 1366 SmallVectorImpl<VariableGEPIndex> &Dest, 1367 const SmallVectorImpl<VariableGEPIndex> &Src) { 1368 if (Src.empty()) 1369 return; 1370 1371 for (unsigned i = 0, e = Src.size(); i != e; ++i) { 1372 const Value *V = Src[i].V; 1373 ExtensionKind Extension = Src[i].Extension; 1374 int64_t Scale = Src[i].Scale; 1375 1376 // Find V in Dest. This is N^2, but pointer indices almost never have more 1377 // than a few variable indexes. 1378 for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 1379 if (!isValueEqualInPotentialCycles(Dest[j].V, V) || 1380 Dest[j].Extension != Extension) 1381 continue; 1382 1383 // If we found it, subtract off Scale V's from the entry in Dest. If it 1384 // goes to zero, remove the entry. 1385 if (Dest[j].Scale != Scale) 1386 Dest[j].Scale -= Scale; 1387 else 1388 Dest.erase(Dest.begin() + j); 1389 Scale = 0; 1390 break; 1391 } 1392 1393 // If we didn't consume this entry, add it to the end of the Dest list. 1394 if (Scale) { 1395 VariableGEPIndex Entry = { V, Extension, -Scale }; 1396 Dest.push_back(Entry); 1397 } 1398 } 1399} 1400