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