1218893Sdim//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10218893Sdim// This file defines the primary stateless implementation of the 11218893Sdim// Alias Analysis interface that implements identities (two different 12218893Sdim// globals cannot alias, etc), but does no stateful analysis. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16249423Sdim#include "llvm/Analysis/Passes.h" 17249423Sdim#include "llvm/ADT/SmallPtrSet.h" 18249423Sdim#include "llvm/ADT/SmallVector.h" 19193323Sed#include "llvm/Analysis/AliasAnalysis.h" 20199989Srdivacky#include "llvm/Analysis/CaptureTracking.h" 21266715Sdim#include "llvm/Analysis/CFG.h" 22266715Sdim#include "llvm/Analysis/Dominators.h" 23249423Sdim#include "llvm/Analysis/InstructionSimplify.h" 24266715Sdim#include "llvm/Analysis/LoopInfo.h" 25199989Srdivacky#include "llvm/Analysis/MemoryBuiltins.h" 26199989Srdivacky#include "llvm/Analysis/ValueTracking.h" 27249423Sdim#include "llvm/IR/Constants.h" 28249423Sdim#include "llvm/IR/DataLayout.h" 29249423Sdim#include "llvm/IR/DerivedTypes.h" 30249423Sdim#include "llvm/IR/Function.h" 31249423Sdim#include "llvm/IR/GlobalAlias.h" 32249423Sdim#include "llvm/IR/GlobalVariable.h" 33249423Sdim#include "llvm/IR/Instructions.h" 34249423Sdim#include "llvm/IR/IntrinsicInst.h" 35249423Sdim#include "llvm/IR/LLVMContext.h" 36249423Sdim#include "llvm/IR/Operator.h" 37249423Sdim#include "llvm/Pass.h" 38198090Srdivacky#include "llvm/Support/ErrorHandling.h" 39212904Sdim#include "llvm/Support/GetElementPtrTypeIterator.h" 40249423Sdim#include "llvm/Target/TargetLibraryInfo.h" 41193323Sed#include <algorithm> 42193323Sedusing namespace llvm; 43193323Sed 44266715Sdim/// Cutoff after which to stop analysing a set of phi nodes potentially involved 45266715Sdim/// in a cycle. Because we are analysing 'through' phi nodes we need to be 46266715Sdim/// careful with value equivalence. We use reachability to make sure a value 47266715Sdim/// cannot be involved in a cycle. 48266715Sdimconst unsigned MaxNumPhiBBsValueReachabilityCheck = 20; 49266715Sdim 50193323Sed//===----------------------------------------------------------------------===// 51193323Sed// Useful predicates 52193323Sed//===----------------------------------------------------------------------===// 53193323Sed 54193323Sed/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 55193323Sed/// object that never escapes from the function. 56193323Sedstatic bool isNonEscapingLocalObject(const Value *V) { 57193323Sed // If this is a local allocation, check to see if it escapes. 58198892Srdivacky if (isa<AllocaInst>(V) || isNoAliasCall(V)) 59199989Srdivacky // Set StoreCaptures to True so that we can assume in our callers that the 60199989Srdivacky // pointer is not the result of a load instruction. Currently 61199989Srdivacky // PointerMayBeCaptured doesn't have any special analysis for the 62199989Srdivacky // StoreCaptures=false case; if it did, our callers could be refined to be 63199989Srdivacky // more precise. 64199989Srdivacky return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 65193323Sed 66193323Sed // If this is an argument that corresponds to a byval or noalias argument, 67193323Sed // then it has not escaped before entering the function. Check if it escapes 68193323Sed // inside the function. 69193323Sed if (const Argument *A = dyn_cast<Argument>(V)) 70243830Sdim if (A->hasByValAttr() || A->hasNoAliasAttr()) 71243830Sdim // Note even if the argument is marked nocapture we still need to check 72243830Sdim // for copies made inside the function. The nocapture attribute only 73243830Sdim // specifies that there are no copies made that outlive the function. 74199989Srdivacky return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 75243830Sdim 76193323Sed return false; 77193323Sed} 78193323Sed 79210299Sed/// isEscapeSource - Return true if the pointer is one which would have 80210299Sed/// been considered an escape by isNonEscapingLocalObject. 81210299Sedstatic bool isEscapeSource(const Value *V) { 82210299Sed if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 83210299Sed return true; 84193323Sed 85210299Sed // The load case works because isNonEscapingLocalObject considers all 86210299Sed // stores to be escapes (it passes true for the StoreCaptures argument 87210299Sed // to PointerMayBeCaptured). 88210299Sed if (isa<LoadInst>(V)) 89210299Sed return true; 90210299Sed 91210299Sed return false; 92210299Sed} 93210299Sed 94218893Sdim/// getObjectSize - Return the size of the object specified by V, or 95218893Sdim/// UnknownSize if unknown. 96243830Sdimstatic uint64_t getObjectSize(const Value *V, const DataLayout &TD, 97243830Sdim const TargetLibraryInfo &TLI, 98234353Sdim bool RoundToAlign = false) { 99239462Sdim uint64_t Size; 100251662Sdim if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) 101239462Sdim return Size; 102239462Sdim return AliasAnalysis::UnknownSize; 103193323Sed} 104193323Sed 105218893Sdim/// isObjectSmallerThan - Return true if we can prove that the object specified 106218893Sdim/// by V is smaller than Size. 107218893Sdimstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 108243830Sdim const DataLayout &TD, 109243830Sdim const TargetLibraryInfo &TLI) { 110251662Sdim // Note that the meanings of the "object" are slightly different in the 111251662Sdim // following contexts: 112251662Sdim // c1: llvm::getObjectSize() 113251662Sdim // c2: llvm.objectsize() intrinsic 114251662Sdim // c3: isObjectSmallerThan() 115251662Sdim // c1 and c2 share the same meaning; however, the meaning of "object" in c3 116251662Sdim // refers to the "entire object". 117251662Sdim // 118251662Sdim // Consider this example: 119251662Sdim // char *p = (char*)malloc(100) 120251662Sdim // char *q = p+80; 121251662Sdim // 122251662Sdim // In the context of c1 and c2, the "object" pointed by q refers to the 123251662Sdim // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. 124251662Sdim // 125251662Sdim // However, in the context of c3, the "object" refers to the chunk of memory 126251662Sdim // being allocated. So, the "object" has 100 bytes, and q points to the middle 127251662Sdim // the "object". In case q is passed to isObjectSmallerThan() as the 1st 128251662Sdim // parameter, before the llvm::getObjectSize() is called to get the size of 129251662Sdim // entire object, we should: 130251662Sdim // - either rewind the pointer q to the base-address of the object in 131251662Sdim // question (in this case rewind to p), or 132251662Sdim // - just give up. It is up to caller to make sure the pointer is pointing 133251662Sdim // to the base address the object. 134263508Sdim // 135251662Sdim // We go for 2nd option for simplicity. 136251662Sdim if (!isIdentifiedObject(V)) 137251662Sdim return false; 138251662Sdim 139234353Sdim // This function needs to use the aligned object size because we allow 140234353Sdim // reads a bit past the end given sufficient alignment. 141243830Sdim uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); 142263508Sdim 143218893Sdim return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 144218893Sdim} 145193323Sed 146218893Sdim/// isObjectSize - Return true if we can prove that the object specified 147218893Sdim/// by V has size Size. 148218893Sdimstatic bool isObjectSize(const Value *V, uint64_t Size, 149243830Sdim const DataLayout &TD, const TargetLibraryInfo &TLI) { 150243830Sdim uint64_t ObjectSize = getObjectSize(V, TD, TLI); 151218893Sdim return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 152218893Sdim} 153193323Sed 154263508Sdim/// isIdentifiedFunctionLocal - Return true if V is umabigously identified 155263508Sdim/// at the function-level. Different IdentifiedFunctionLocals can't alias. 156263508Sdim/// Further, an IdentifiedFunctionLocal can not alias with any function 157263508Sdim/// arguments other than itself, which is not neccessarily true for 158263508Sdim/// IdentifiedObjects. 159263508Sdimstatic bool isIdentifiedFunctionLocal(const Value *V) 160263508Sdim{ 161263508Sdim return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V); 162263508Sdim} 163263508Sdim 164263508Sdim 165193323Sed//===----------------------------------------------------------------------===// 166212904Sdim// GetElementPtr Instruction Decomposition and Analysis 167212904Sdim//===----------------------------------------------------------------------===// 168212904Sdim 169212904Sdimnamespace { 170212904Sdim enum ExtensionKind { 171212904Sdim EK_NotExtended, 172212904Sdim EK_SignExt, 173212904Sdim EK_ZeroExt 174212904Sdim }; 175263508Sdim 176212904Sdim struct VariableGEPIndex { 177212904Sdim const Value *V; 178212904Sdim ExtensionKind Extension; 179212904Sdim int64_t Scale; 180243830Sdim 181243830Sdim bool operator==(const VariableGEPIndex &Other) const { 182243830Sdim return V == Other.V && Extension == Other.Extension && 183243830Sdim Scale == Other.Scale; 184243830Sdim } 185243830Sdim 186243830Sdim bool operator!=(const VariableGEPIndex &Other) const { 187243830Sdim return !operator==(Other); 188243830Sdim } 189212904Sdim }; 190212904Sdim} 191212904Sdim 192212904Sdim 193212904Sdim/// GetLinearExpression - Analyze the specified value as a linear expression: 194212904Sdim/// "A*V + B", where A and B are constant integers. Return the scale and offset 195212904Sdim/// values as APInts and return V as a Value*, and return whether we looked 196212904Sdim/// through any sign or zero extends. The incoming Value is known to have 197212904Sdim/// IntegerType and it may already be sign or zero extended. 198212904Sdim/// 199212904Sdim/// Note that this looks through extends, so the high bits may not be 200212904Sdim/// represented in the result. 201212904Sdimstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 202212904Sdim ExtensionKind &Extension, 203243830Sdim const DataLayout &TD, unsigned Depth) { 204212904Sdim assert(V->getType()->isIntegerTy() && "Not an integer value"); 205212904Sdim 206212904Sdim // Limit our recursion depth. 207212904Sdim if (Depth == 6) { 208212904Sdim Scale = 1; 209212904Sdim Offset = 0; 210212904Sdim return V; 211212904Sdim } 212263508Sdim 213212904Sdim if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 214212904Sdim if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 215212904Sdim switch (BOp->getOpcode()) { 216212904Sdim default: break; 217212904Sdim case Instruction::Or: 218212904Sdim // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 219212904Sdim // analyze it. 220212904Sdim if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 221212904Sdim break; 222212904Sdim // FALL THROUGH. 223212904Sdim case Instruction::Add: 224212904Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 225212904Sdim TD, Depth+1); 226212904Sdim Offset += RHSC->getValue(); 227212904Sdim return V; 228212904Sdim case Instruction::Mul: 229212904Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 230212904Sdim TD, Depth+1); 231212904Sdim Offset *= RHSC->getValue(); 232212904Sdim Scale *= RHSC->getValue(); 233212904Sdim return V; 234212904Sdim case Instruction::Shl: 235212904Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 236212904Sdim TD, Depth+1); 237212904Sdim Offset <<= RHSC->getValue().getLimitedValue(); 238212904Sdim Scale <<= RHSC->getValue().getLimitedValue(); 239212904Sdim return V; 240212904Sdim } 241212904Sdim } 242212904Sdim } 243263508Sdim 244212904Sdim // Since GEP indices are sign extended anyway, we don't care about the high 245212904Sdim // bits of a sign or zero extended value - just scales and offsets. The 246212904Sdim // extensions have to be consistent though. 247212904Sdim if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 248212904Sdim (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 249212904Sdim Value *CastOp = cast<CastInst>(V)->getOperand(0); 250212904Sdim unsigned OldWidth = Scale.getBitWidth(); 251212904Sdim unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 252218893Sdim Scale = Scale.trunc(SmallWidth); 253218893Sdim Offset = Offset.trunc(SmallWidth); 254212904Sdim Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 255212904Sdim 256212904Sdim Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 257212904Sdim TD, Depth+1); 258218893Sdim Scale = Scale.zext(OldWidth); 259218893Sdim Offset = Offset.zext(OldWidth); 260263508Sdim 261212904Sdim return Result; 262212904Sdim } 263263508Sdim 264212904Sdim Scale = 1; 265212904Sdim Offset = 0; 266212904Sdim return V; 267212904Sdim} 268212904Sdim 269212904Sdim/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 270212904Sdim/// into a base pointer with a constant offset and a number of scaled symbolic 271212904Sdim/// offsets. 272212904Sdim/// 273212904Sdim/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 274212904Sdim/// the VarIndices vector) are Value*'s that are known to be scaled by the 275212904Sdim/// specified amount, but which may have other unrepresented high bits. As such, 276212904Sdim/// the gep cannot necessarily be reconstructed from its decomposed form. 277212904Sdim/// 278243830Sdim/// When DataLayout is around, this function is capable of analyzing everything 279218893Sdim/// that GetUnderlyingObject can look through. When not, it just looks 280212904Sdim/// through pointer casts. 281212904Sdim/// 282212904Sdimstatic const Value * 283212904SdimDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 284212904Sdim SmallVectorImpl<VariableGEPIndex> &VarIndices, 285243830Sdim const DataLayout *TD) { 286212904Sdim // Limit recursion depth to limit compile time in crazy cases. 287212904Sdim unsigned MaxLookup = 6; 288263508Sdim 289212904Sdim BaseOffs = 0; 290212904Sdim do { 291212904Sdim // See if this is a bitcast or GEP. 292212904Sdim const Operator *Op = dyn_cast<Operator>(V); 293212904Sdim if (Op == 0) { 294212904Sdim // The only non-operator case we can handle are GlobalAliases. 295212904Sdim if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 296212904Sdim if (!GA->mayBeOverridden()) { 297212904Sdim V = GA->getAliasee(); 298212904Sdim continue; 299212904Sdim } 300212904Sdim } 301212904Sdim return V; 302212904Sdim } 303263508Sdim 304212904Sdim if (Op->getOpcode() == Instruction::BitCast) { 305212904Sdim V = Op->getOperand(0); 306212904Sdim continue; 307212904Sdim } 308218893Sdim 309223017Sdim const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 310223017Sdim if (GEPOp == 0) { 311223017Sdim // If it's not a GEP, hand it off to SimplifyInstruction to see if it 312223017Sdim // can come up with something. This matches what GetUnderlyingObject does. 313223017Sdim if (const Instruction *I = dyn_cast<Instruction>(V)) 314223017Sdim // TODO: Get a DominatorTree and use it here. 315223017Sdim if (const Value *Simplified = 316223017Sdim SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 317223017Sdim V = Simplified; 318223017Sdim continue; 319223017Sdim } 320263508Sdim 321212904Sdim return V; 322223017Sdim } 323263508Sdim 324212904Sdim // Don't attempt to analyze GEPs over unsized objects. 325263508Sdim if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized()) 326212904Sdim return V; 327263508Sdim 328243830Sdim // If we are lacking DataLayout information, we can't compute the offets of 329212904Sdim // elements computed by GEPs. However, we can handle bitcast equivalent 330212904Sdim // GEPs. 331212904Sdim if (TD == 0) { 332212904Sdim if (!GEPOp->hasAllZeroIndices()) 333212904Sdim return V; 334212904Sdim V = GEPOp->getOperand(0); 335212904Sdim continue; 336212904Sdim } 337263508Sdim 338263508Sdim unsigned AS = GEPOp->getPointerAddressSpace(); 339212904Sdim // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 340212904Sdim gep_type_iterator GTI = gep_type_begin(GEPOp); 341212904Sdim for (User::const_op_iterator I = GEPOp->op_begin()+1, 342212904Sdim E = GEPOp->op_end(); I != E; ++I) { 343212904Sdim Value *Index = *I; 344212904Sdim // Compute the (potentially symbolic) offset in bytes for this index. 345226633Sdim if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 346212904Sdim // For a struct, add the member offset. 347212904Sdim unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 348212904Sdim if (FieldNo == 0) continue; 349263508Sdim 350212904Sdim BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 351212904Sdim continue; 352212904Sdim } 353263508Sdim 354212904Sdim // For an array/pointer, add the element offset, explicitly scaled. 355212904Sdim if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 356212904Sdim if (CIdx->isZero()) continue; 357212904Sdim BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 358212904Sdim continue; 359212904Sdim } 360263508Sdim 361212904Sdim uint64_t Scale = TD->getTypeAllocSize(*GTI); 362212904Sdim ExtensionKind Extension = EK_NotExtended; 363263508Sdim 364212904Sdim // If the integer type is smaller than the pointer size, it is implicitly 365212904Sdim // sign extended to pointer size. 366263508Sdim unsigned Width = Index->getType()->getIntegerBitWidth(); 367263508Sdim if (TD->getPointerSizeInBits(AS) > Width) 368212904Sdim Extension = EK_SignExt; 369263508Sdim 370212904Sdim // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 371212904Sdim APInt IndexScale(Width, 0), IndexOffset(Width, 0); 372212904Sdim Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 373212904Sdim *TD, 0); 374263508Sdim 375212904Sdim // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 376212904Sdim // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 377218893Sdim BaseOffs += IndexOffset.getSExtValue()*Scale; 378218893Sdim Scale *= IndexScale.getSExtValue(); 379263508Sdim 380221345Sdim // If we already had an occurrence of this index variable, merge this 381212904Sdim // scale into it. For example, we want to handle: 382212904Sdim // A[x][x] -> x*16 + x*4 -> x*20 383212904Sdim // This also ensures that 'x' only appears in the index list once. 384212904Sdim for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 385212904Sdim if (VarIndices[i].V == Index && 386212904Sdim VarIndices[i].Extension == Extension) { 387212904Sdim Scale += VarIndices[i].Scale; 388212904Sdim VarIndices.erase(VarIndices.begin()+i); 389212904Sdim break; 390212904Sdim } 391212904Sdim } 392263508Sdim 393212904Sdim // Make sure that we have a scale that makes sense for this target's 394212904Sdim // pointer size. 395263508Sdim if (unsigned ShiftBits = 64 - TD->getPointerSizeInBits(AS)) { 396212904Sdim Scale <<= ShiftBits; 397218893Sdim Scale = (int64_t)Scale >> ShiftBits; 398212904Sdim } 399263508Sdim 400212904Sdim if (Scale) { 401226633Sdim VariableGEPIndex Entry = {Index, Extension, 402226633Sdim static_cast<int64_t>(Scale)}; 403212904Sdim VarIndices.push_back(Entry); 404212904Sdim } 405212904Sdim } 406263508Sdim 407212904Sdim // Analyze the base pointer next. 408212904Sdim V = GEPOp->getOperand(0); 409212904Sdim } while (--MaxLookup); 410263508Sdim 411212904Sdim // If the chain of expressions is too deep, just return early. 412212904Sdim return V; 413212904Sdim} 414212904Sdim 415212904Sdim//===----------------------------------------------------------------------===// 416210299Sed// BasicAliasAnalysis Pass 417193323Sed//===----------------------------------------------------------------------===// 418193323Sed 419210299Sed#ifndef NDEBUG 420210299Sedstatic const Function *getParent(const Value *V) { 421210299Sed if (const Instruction *inst = dyn_cast<Instruction>(V)) 422210299Sed return inst->getParent()->getParent(); 423210299Sed 424210299Sed if (const Argument *arg = dyn_cast<Argument>(V)) 425210299Sed return arg->getParent(); 426210299Sed 427210299Sed return NULL; 428210299Sed} 429210299Sed 430210299Sedstatic bool notDifferentParent(const Value *O1, const Value *O2) { 431210299Sed 432210299Sed const Function *F1 = getParent(O1); 433210299Sed const Function *F2 = getParent(O2); 434210299Sed 435210299Sed return !F1 || !F2 || F1 == F2; 436210299Sed} 437210299Sed#endif 438210299Sed 439193323Sednamespace { 440218893Sdim /// BasicAliasAnalysis - This is the primary alias analysis implementation. 441218893Sdim struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 442193323Sed static char ID; // Class identification, replacement for typeinfo 443243830Sdim BasicAliasAnalysis() : ImmutablePass(ID) { 444218893Sdim initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 445218893Sdim } 446210299Sed 447218893Sdim virtual void initializePass() { 448218893Sdim InitializeAliasAnalysis(this); 449218893Sdim } 450218893Sdim 451218893Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 452218893Sdim AU.addRequired<AliasAnalysis>(); 453226633Sdim AU.addRequired<TargetLibraryInfo>(); 454218893Sdim } 455218893Sdim 456218893Sdim virtual AliasResult alias(const Location &LocA, 457218893Sdim const Location &LocB) { 458223017Sdim assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 459218893Sdim assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 460210299Sed "BasicAliasAnalysis doesn't support interprocedural queries."); 461218893Sdim AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 462218893Sdim LocB.Ptr, LocB.Size, LocB.TBAATag); 463243830Sdim // AliasCache rarely has more than 1 or 2 elements, always use 464243830Sdim // shrink_and_clear so it quickly returns to the inline capacity of the 465243830Sdim // SmallDenseMap if it ever grows larger. 466243830Sdim // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 467243830Sdim AliasCache.shrink_and_clear(); 468266715Sdim VisitedPhiBBs.clear(); 469198090Srdivacky return Alias; 470198090Srdivacky } 471193323Sed 472212904Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 473218893Sdim const Location &Loc); 474193323Sed 475212904Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 476212904Sdim ImmutableCallSite CS2) { 477212904Sdim // The AliasAnalysis base class has some smarts, lets use them. 478212904Sdim return AliasAnalysis::getModRefInfo(CS1, CS2); 479212904Sdim } 480212904Sdim 481193323Sed /// pointsToConstantMemory - Chase pointers until we find a (constant 482193323Sed /// global) or not. 483218893Sdim virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 484193323Sed 485212904Sdim /// getModRefBehavior - Return the behavior when calling the given 486212904Sdim /// call site. 487212904Sdim virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 488212904Sdim 489212904Sdim /// getModRefBehavior - Return the behavior when calling the given function. 490212904Sdim /// For use when the call site is not known. 491212904Sdim virtual ModRefBehavior getModRefBehavior(const Function *F); 492212904Sdim 493202878Srdivacky /// getAdjustedAnalysisPointer - This method is used when a pass implements 494212904Sdim /// an analysis interface through multiple inheritance. If needed, it 495212904Sdim /// should override this to adjust the this pointer as needed for the 496212904Sdim /// specified pass info. 497212904Sdim virtual void *getAdjustedAnalysisPointer(const void *ID) { 498212904Sdim if (ID == &AliasAnalysis::ID) 499202878Srdivacky return (AliasAnalysis*)this; 500202878Srdivacky return this; 501202878Srdivacky } 502263508Sdim 503193323Sed private: 504223017Sdim // AliasCache - Track alias queries to guard against recursion. 505223017Sdim typedef std::pair<Location, Location> LocPair; 506243830Sdim typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; 507223017Sdim AliasCacheTy AliasCache; 508223017Sdim 509266715Sdim /// \brief Track phi nodes we have visited. When interpret "Value" pointer 510266715Sdim /// equality as value equality we need to make sure that the "Value" is not 511266715Sdim /// part of a cycle. Otherwise, two uses could come from different 512266715Sdim /// "iterations" of a cycle and see different values for the same "Value" 513266715Sdim /// pointer. 514266715Sdim /// The following example shows the problem: 515266715Sdim /// %p = phi(%alloca1, %addr2) 516266715Sdim /// %l = load %ptr 517266715Sdim /// %addr1 = gep, %alloca2, 0, %l 518266715Sdim /// %addr2 = gep %alloca2, 0, (%l + 1) 519266715Sdim /// alias(%p, %addr1) -> MayAlias ! 520266715Sdim /// store %l, ... 521266715Sdim SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs; 522266715Sdim 523223017Sdim // Visited - Track instructions visited by pointsToConstantMemory. 524210299Sed SmallPtrSet<const Value*, 16> Visited; 525198090Srdivacky 526266715Sdim /// \brief Check whether two Values can be considered equivalent. 527266715Sdim /// 528266715Sdim /// In addition to pointer equivalence of \p V1 and \p V2 this checks 529266715Sdim /// whether they can not be part of a cycle in the value graph by looking at 530266715Sdim /// all visited phi nodes an making sure that the phis cannot reach the 531266715Sdim /// value. We have to do this because we are looking through phi nodes (That 532266715Sdim /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). 533266715Sdim bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); 534266715Sdim 535266715Sdim /// \brief Dest and Src are the variable indices from two decomposed 536266715Sdim /// GetElementPtr instructions GEP1 and GEP2 which have common base 537266715Sdim /// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 538266715Sdim /// difference between the two pointers. 539266715Sdim void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 540266715Sdim const SmallVectorImpl<VariableGEPIndex> &Src); 541266715Sdim 542199989Srdivacky // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 543199989Srdivacky // instruction against another. 544218893Sdim AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 545243830Sdim const MDNode *V1TBAAInfo, 546218893Sdim const Value *V2, uint64_t V2Size, 547218893Sdim const MDNode *V2TBAAInfo, 548199989Srdivacky const Value *UnderlyingV1, const Value *UnderlyingV2); 549198090Srdivacky 550199989Srdivacky // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 551199989Srdivacky // instruction against another. 552218893Sdim AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 553218893Sdim const MDNode *PNTBAAInfo, 554218893Sdim const Value *V2, uint64_t V2Size, 555218893Sdim const MDNode *V2TBAAInfo); 556198090Srdivacky 557198892Srdivacky /// aliasSelect - Disambiguate a Select instruction against another value. 558218893Sdim AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 559218893Sdim const MDNode *SITBAAInfo, 560218893Sdim const Value *V2, uint64_t V2Size, 561218893Sdim const MDNode *V2TBAAInfo); 562198892Srdivacky 563218893Sdim AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 564218893Sdim const MDNode *V1TBAATag, 565218893Sdim const Value *V2, uint64_t V2Size, 566218893Sdim const MDNode *V2TBAATag); 567193323Sed }; 568193323Sed} // End of anonymous namespace 569193323Sed 570193323Sed// Register this pass... 571193323Sedchar BasicAliasAnalysis::ID = 0; 572226633SdimINITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 573218893Sdim "Basic Alias Analysis (stateless AA impl)", 574218893Sdim false, true, false) 575226633SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 576226633SdimINITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 577226633Sdim "Basic Alias Analysis (stateless AA impl)", 578226633Sdim false, true, false) 579193323Sed 580226633Sdim 581193323SedImmutablePass *llvm::createBasicAliasAnalysisPass() { 582193323Sed return new BasicAliasAnalysis(); 583193323Sed} 584193323Sed 585218893Sdim/// pointsToConstantMemory - Returns whether the given pointer value 586218893Sdim/// points to memory that is local to the function, with global constants being 587218893Sdim/// considered local to all functions. 588218893Sdimbool 589218893SdimBasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 590218893Sdim assert(Visited.empty() && "Visited must be cleared after use!"); 591193323Sed 592218893Sdim unsigned MaxLookup = 8; 593218893Sdim SmallVector<const Value *, 16> Worklist; 594218893Sdim Worklist.push_back(Loc.Ptr); 595218893Sdim do { 596218893Sdim const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 597218893Sdim if (!Visited.insert(V)) { 598218893Sdim Visited.clear(); 599218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 600218893Sdim } 601212904Sdim 602218893Sdim // An alloca instruction defines local memory. 603218893Sdim if (OrLocal && isa<AllocaInst>(V)) 604218893Sdim continue; 605218893Sdim 606218893Sdim // A global constant counts as local memory for our purposes. 607218893Sdim if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 608218893Sdim // Note: this doesn't require GV to be "ODR" because it isn't legal for a 609218893Sdim // global to be marked constant in some modules and non-constant in 610218893Sdim // others. GV may even be a declaration, not a definition. 611218893Sdim if (!GV->isConstant()) { 612218893Sdim Visited.clear(); 613218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 614218893Sdim } 615218893Sdim continue; 616218893Sdim } 617218893Sdim 618218893Sdim // If both select values point to local memory, then so does the select. 619218893Sdim if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 620218893Sdim Worklist.push_back(SI->getTrueValue()); 621218893Sdim Worklist.push_back(SI->getFalseValue()); 622218893Sdim continue; 623218893Sdim } 624218893Sdim 625218893Sdim // If all values incoming to a phi node point to local memory, then so does 626218893Sdim // the phi. 627218893Sdim if (const PHINode *PN = dyn_cast<PHINode>(V)) { 628218893Sdim // Don't bother inspecting phi nodes with many operands. 629218893Sdim if (PN->getNumIncomingValues() > MaxLookup) { 630218893Sdim Visited.clear(); 631218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 632218893Sdim } 633218893Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 634218893Sdim Worklist.push_back(PN->getIncomingValue(i)); 635218893Sdim continue; 636218893Sdim } 637218893Sdim 638218893Sdim // Otherwise be conservative. 639218893Sdim Visited.clear(); 640218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 641218893Sdim 642218893Sdim } while (!Worklist.empty() && --MaxLookup); 643218893Sdim 644218893Sdim Visited.clear(); 645218893Sdim return Worklist.empty(); 646193323Sed} 647193323Sed 648212904Sdim/// getModRefBehavior - Return the behavior when calling the given call site. 649212904SdimAliasAnalysis::ModRefBehavior 650212904SdimBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 651212904Sdim if (CS.doesNotAccessMemory()) 652212904Sdim // Can't do better than this. 653212904Sdim return DoesNotAccessMemory; 654193323Sed 655212904Sdim ModRefBehavior Min = UnknownModRefBehavior; 656212904Sdim 657212904Sdim // If the callsite knows it only reads memory, don't return worse 658212904Sdim // than that. 659212904Sdim if (CS.onlyReadsMemory()) 660212904Sdim Min = OnlyReadsMemory; 661212904Sdim 662212904Sdim // The AliasAnalysis base class has some smarts, lets use them. 663218893Sdim return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 664212904Sdim} 665212904Sdim 666212904Sdim/// getModRefBehavior - Return the behavior when calling the given function. 667212904Sdim/// For use when the call site is not known. 668212904SdimAliasAnalysis::ModRefBehavior 669212904SdimBasicAliasAnalysis::getModRefBehavior(const Function *F) { 670218893Sdim // If the function declares it doesn't access memory, we can't do better. 671212904Sdim if (F->doesNotAccessMemory()) 672212904Sdim return DoesNotAccessMemory; 673218893Sdim 674218893Sdim // For intrinsics, we can check the table. 675218893Sdim if (unsigned iid = F->getIntrinsicID()) { 676218893Sdim#define GET_INTRINSIC_MODREF_BEHAVIOR 677249423Sdim#include "llvm/IR/Intrinsics.gen" 678218893Sdim#undef GET_INTRINSIC_MODREF_BEHAVIOR 679218893Sdim } 680218893Sdim 681218893Sdim ModRefBehavior Min = UnknownModRefBehavior; 682218893Sdim 683218893Sdim // If the function declares it only reads memory, go with that. 684212904Sdim if (F->onlyReadsMemory()) 685218893Sdim Min = OnlyReadsMemory; 686212904Sdim 687218893Sdim // Otherwise be conservative. 688218893Sdim return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 689212904Sdim} 690212904Sdim 691199989Srdivacky/// getModRefInfo - Check to see if the specified callsite can clobber the 692199989Srdivacky/// specified memory object. Since we only look at local properties of this 693199989Srdivacky/// function, we really can't say much about this query. We do, however, use 694199989Srdivacky/// simple "address taken" analysis on local objects. 695193323SedAliasAnalysis::ModRefResult 696212904SdimBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 697218893Sdim const Location &Loc) { 698218893Sdim assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 699210299Sed "AliasAnalysis query involving multiple functions!"); 700210299Sed 701218893Sdim const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 702263508Sdim 703218893Sdim // If this is a tail call and Loc.Ptr points to a stack location, we know that 704199989Srdivacky // the tail call cannot access or modify the local stack. 705199989Srdivacky // We cannot exclude byval arguments here; these belong to the caller of 706199989Srdivacky // the current function not to the current function, and a tail callee 707199989Srdivacky // may reference them. 708199989Srdivacky if (isa<AllocaInst>(Object)) 709212904Sdim if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 710199989Srdivacky if (CI->isTailCall()) 711199989Srdivacky return NoModRef; 712263508Sdim 713199989Srdivacky // If the pointer is to a locally allocated object that does not escape, 714199989Srdivacky // then the call can not mod/ref the pointer unless the call takes the pointer 715199989Srdivacky // as an argument, and itself doesn't capture it. 716199989Srdivacky if (!isa<Constant>(Object) && CS.getInstruction() != Object && 717199989Srdivacky isNonEscapingLocalObject(Object)) { 718199989Srdivacky bool PassedAsArg = false; 719199989Srdivacky unsigned ArgNo = 0; 720212904Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 721199989Srdivacky CI != CE; ++CI, ++ArgNo) { 722223017Sdim // Only look at the no-capture or byval pointer arguments. If this 723223017Sdim // pointer were passed to arguments that were neither of these, then it 724223017Sdim // couldn't be no-capture. 725204642Srdivacky if (!(*CI)->getType()->isPointerTy() || 726234353Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 727199989Srdivacky continue; 728263508Sdim 729218893Sdim // If this is a no-capture pointer argument, see if we can tell that it 730199989Srdivacky // is impossible to alias the pointer we're checking. If not, we have to 731199989Srdivacky // assume that the call could touch the pointer, even though it doesn't 732199989Srdivacky // escape. 733226633Sdim if (!isNoAlias(Location(*CI), Location(Object))) { 734199989Srdivacky PassedAsArg = true; 735198113Srdivacky break; 736198090Srdivacky } 737198090Srdivacky } 738263508Sdim 739199989Srdivacky if (!PassedAsArg) 740199989Srdivacky return NoModRef; 741193323Sed } 742193323Sed 743226633Sdim const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 744218893Sdim ModRefResult Min = ModRef; 745218893Sdim 746199989Srdivacky // Finally, handle specific knowledge of intrinsics. 747212904Sdim const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 748212904Sdim if (II != 0) 749212904Sdim switch (II->getIntrinsicID()) { 750212904Sdim default: break; 751212904Sdim case Intrinsic::memcpy: 752212904Sdim case Intrinsic::memmove: { 753218893Sdim uint64_t Len = UnknownSize; 754212904Sdim if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 755212904Sdim Len = LenCI->getZExtValue(); 756212904Sdim Value *Dest = II->getArgOperand(0); 757212904Sdim Value *Src = II->getArgOperand(1); 758218893Sdim // If it can't overlap the source dest, then it doesn't modref the loc. 759218893Sdim if (isNoAlias(Location(Dest, Len), Loc)) { 760218893Sdim if (isNoAlias(Location(Src, Len), Loc)) 761212904Sdim return NoModRef; 762218893Sdim // If it can't overlap the dest, then worst case it reads the loc. 763218893Sdim Min = Ref; 764218893Sdim } else if (isNoAlias(Location(Src, Len), Loc)) { 765218893Sdim // If it can't overlap the source, then worst case it mutates the loc. 766218893Sdim Min = Mod; 767212904Sdim } 768212904Sdim break; 769199989Srdivacky } 770212904Sdim case Intrinsic::memset: 771212904Sdim // Since memset is 'accesses arguments' only, the AliasAnalysis base class 772212904Sdim // will handle it for the variable length case. 773212904Sdim if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 774218893Sdim uint64_t Len = LenCI->getZExtValue(); 775212904Sdim Value *Dest = II->getArgOperand(0); 776218893Sdim if (isNoAlias(Location(Dest, Len), Loc)) 777212904Sdim return NoModRef; 778212904Sdim } 779218893Sdim // We know that memset doesn't load anything. 780218893Sdim Min = Mod; 781212904Sdim break; 782212904Sdim case Intrinsic::lifetime_start: 783212904Sdim case Intrinsic::lifetime_end: 784212904Sdim case Intrinsic::invariant_start: { 785218893Sdim uint64_t PtrSize = 786212904Sdim cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 787218893Sdim if (isNoAlias(Location(II->getArgOperand(1), 788218893Sdim PtrSize, 789218893Sdim II->getMetadata(LLVMContext::MD_tbaa)), 790218893Sdim Loc)) 791199989Srdivacky return NoModRef; 792212904Sdim break; 793199989Srdivacky } 794212904Sdim case Intrinsic::invariant_end: { 795218893Sdim uint64_t PtrSize = 796212904Sdim cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 797218893Sdim if (isNoAlias(Location(II->getArgOperand(2), 798218893Sdim PtrSize, 799218893Sdim II->getMetadata(LLVMContext::MD_tbaa)), 800218893Sdim Loc)) 801199989Srdivacky return NoModRef; 802212904Sdim break; 803199989Srdivacky } 804221345Sdim case Intrinsic::arm_neon_vld1: { 805221345Sdim // LLVM's vld1 and vst1 intrinsics currently only support a single 806221345Sdim // vector register. 807221345Sdim uint64_t Size = 808221345Sdim TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 809221345Sdim if (isNoAlias(Location(II->getArgOperand(0), Size, 810221345Sdim II->getMetadata(LLVMContext::MD_tbaa)), 811221345Sdim Loc)) 812221345Sdim return NoModRef; 813221345Sdim break; 814212904Sdim } 815221345Sdim case Intrinsic::arm_neon_vst1: { 816221345Sdim uint64_t Size = 817221345Sdim TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 818221345Sdim if (isNoAlias(Location(II->getArgOperand(0), Size, 819221345Sdim II->getMetadata(LLVMContext::MD_tbaa)), 820221345Sdim Loc)) 821221345Sdim return NoModRef; 822221345Sdim break; 823221345Sdim } 824221345Sdim } 825199989Srdivacky 826226633Sdim // We can bound the aliasing properties of memset_pattern16 just as we can 827263508Sdim // for memcpy/memset. This is particularly important because the 828226633Sdim // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 829226633Sdim // whenever possible. 830226633Sdim else if (TLI.has(LibFunc::memset_pattern16) && 831226633Sdim CS.getCalledFunction() && 832226633Sdim CS.getCalledFunction()->getName() == "memset_pattern16") { 833226633Sdim const Function *MS = CS.getCalledFunction(); 834226633Sdim FunctionType *MemsetType = MS->getFunctionType(); 835226633Sdim if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 836226633Sdim isa<PointerType>(MemsetType->getParamType(0)) && 837226633Sdim isa<PointerType>(MemsetType->getParamType(1)) && 838226633Sdim isa<IntegerType>(MemsetType->getParamType(2))) { 839226633Sdim uint64_t Len = UnknownSize; 840226633Sdim if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 841226633Sdim Len = LenCI->getZExtValue(); 842226633Sdim const Value *Dest = CS.getArgument(0); 843226633Sdim const Value *Src = CS.getArgument(1); 844226633Sdim // If it can't overlap the source dest, then it doesn't modref the loc. 845226633Sdim if (isNoAlias(Location(Dest, Len), Loc)) { 846226633Sdim // Always reads 16 bytes of the source. 847226633Sdim if (isNoAlias(Location(Src, 16), Loc)) 848226633Sdim return NoModRef; 849226633Sdim // If it can't overlap the dest, then worst case it reads the loc. 850226633Sdim Min = Ref; 851226633Sdim // Always reads 16 bytes of the source. 852226633Sdim } else if (isNoAlias(Location(Src, 16), Loc)) { 853226633Sdim // If it can't overlap the source, then worst case it mutates the loc. 854226633Sdim Min = Mod; 855226633Sdim } 856226633Sdim } 857226633Sdim } 858226633Sdim 859193323Sed // The AliasAnalysis base class has some smarts, lets use them. 860218893Sdim return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 861193323Sed} 862193323Sed 863263508Sdimstatic bool areVarIndicesEqual(SmallVectorImpl<VariableGEPIndex> &Indices1, 864263508Sdim SmallVectorImpl<VariableGEPIndex> &Indices2) { 865243830Sdim unsigned Size1 = Indices1.size(); 866243830Sdim unsigned Size2 = Indices2.size(); 867243830Sdim 868243830Sdim if (Size1 != Size2) 869243830Sdim return false; 870243830Sdim 871243830Sdim for (unsigned I = 0; I != Size1; ++I) 872243830Sdim if (Indices1[I] != Indices2[I]) 873243830Sdim return false; 874243830Sdim 875243830Sdim return true; 876243830Sdim} 877243830Sdim 878199989Srdivacky/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 879199989Srdivacky/// against another pointer. We know that V1 is a GEP, but we don't know 880218893Sdim/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 881199989Srdivacky/// UnderlyingV2 is the same for V2. 882199989Srdivacky/// 883193323SedAliasAnalysis::AliasResult 884218893SdimBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 885243830Sdim const MDNode *V1TBAAInfo, 886218893Sdim const Value *V2, uint64_t V2Size, 887218893Sdim const MDNode *V2TBAAInfo, 888199989Srdivacky const Value *UnderlyingV1, 889199989Srdivacky const Value *UnderlyingV2) { 890199989Srdivacky int64_t GEP1BaseOffset; 891212904Sdim SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 892199989Srdivacky 893243830Sdim // If we have two gep instructions with must-alias or not-alias'ing base 894243830Sdim // pointers, figure out if the indexes to the GEP tell us anything about the 895243830Sdim // derived pointer. 896199989Srdivacky if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 897249423Sdim // Do the base pointers alias? 898249423Sdim AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 899249423Sdim UnderlyingV2, UnknownSize, 0); 900249423Sdim 901243830Sdim // Check for geps of non-aliasing underlying pointers where the offsets are 902243830Sdim // identical. 903249423Sdim if ((BaseAlias == MayAlias) && V1Size == V2Size) { 904243830Sdim // Do the base pointers alias assuming type and size. 905243830Sdim AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, 906243830Sdim V1TBAAInfo, UnderlyingV2, 907243830Sdim V2Size, V2TBAAInfo); 908243830Sdim if (PreciseBaseAlias == NoAlias) { 909243830Sdim // See if the computed offset from the common pointer tells us about the 910243830Sdim // relation of the resulting pointer. 911243830Sdim int64_t GEP2BaseOffset; 912243830Sdim SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 913243830Sdim const Value *GEP2BasePtr = 914243830Sdim DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 915243830Sdim const Value *GEP1BasePtr = 916243830Sdim DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 917243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 918243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 919243830Sdim if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 920243830Sdim assert(TD == 0 && 921243830Sdim "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 922243830Sdim return MayAlias; 923243830Sdim } 924243830Sdim // Same offsets. 925243830Sdim if (GEP1BaseOffset == GEP2BaseOffset && 926243830Sdim areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) 927243830Sdim return NoAlias; 928243830Sdim GEP1VariableIndices.clear(); 929243830Sdim } 930243830Sdim } 931263508Sdim 932199989Srdivacky // If we get a No or May, then return it immediately, no amount of analysis 933199989Srdivacky // will improve this situation. 934199989Srdivacky if (BaseAlias != MustAlias) return BaseAlias; 935263508Sdim 936199989Srdivacky // Otherwise, we have a MustAlias. Since the base pointers alias each other 937199989Srdivacky // exactly, see if the computed offset from the common pointer tells us 938199989Srdivacky // about the relation of the resulting pointer. 939199989Srdivacky const Value *GEP1BasePtr = 940199989Srdivacky DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 941263508Sdim 942199989Srdivacky int64_t GEP2BaseOffset; 943212904Sdim SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 944199989Srdivacky const Value *GEP2BasePtr = 945199989Srdivacky DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 946263508Sdim 947243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 948243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 949199989Srdivacky if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 950199989Srdivacky assert(TD == 0 && 951218893Sdim "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 952199989Srdivacky return MayAlias; 953199989Srdivacky } 954263508Sdim 955199989Srdivacky // Subtract the GEP2 pointer from the GEP1 pointer to find out their 956199989Srdivacky // symbolic difference. 957199989Srdivacky GEP1BaseOffset -= GEP2BaseOffset; 958212904Sdim GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 959263508Sdim 960199989Srdivacky } else { 961199989Srdivacky // Check to see if these two pointers are related by the getelementptr 962199989Srdivacky // instruction. If one pointer is a GEP with a non-zero index of the other 963199989Srdivacky // pointer, we know they cannot alias. 964193323Sed 965199989Srdivacky // If both accesses are unknown size, we can't do anything useful here. 966212904Sdim if (V1Size == UnknownSize && V2Size == UnknownSize) 967199989Srdivacky return MayAlias; 968193323Sed 969218893Sdim AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 970218893Sdim V2, V2Size, V2TBAAInfo); 971199989Srdivacky if (R != MustAlias) 972199989Srdivacky // If V2 may alias GEP base pointer, conservatively returns MayAlias. 973199989Srdivacky // If V2 is known not to alias GEP base pointer, then the two values 974199989Srdivacky // cannot alias per GEP semantics: "A pointer value formed from a 975199989Srdivacky // getelementptr instruction is associated with the addresses associated 976199989Srdivacky // with the first operand of the getelementptr". 977199989Srdivacky return R; 978193323Sed 979199989Srdivacky const Value *GEP1BasePtr = 980199989Srdivacky DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 981263508Sdim 982243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 983243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 984199989Srdivacky if (GEP1BasePtr != UnderlyingV1) { 985199989Srdivacky assert(TD == 0 && 986218893Sdim "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 987199989Srdivacky return MayAlias; 988193323Sed } 989193323Sed } 990263508Sdim 991199989Srdivacky // In the two GEP Case, if there is no difference in the offsets of the 992199989Srdivacky // computed pointers, the resultant pointers are a must alias. This 993199989Srdivacky // hapens when we have two lexically identical GEP's (for example). 994193323Sed // 995199989Srdivacky // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 996199989Srdivacky // must aliases the GEP, the end result is a must alias also. 997199989Srdivacky if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 998198090Srdivacky return MustAlias; 999193323Sed 1000226633Sdim // If there is a constant difference between the pointers, but the difference 1001226633Sdim // is less than the size of the associated memory object, then we know 1002226633Sdim // that the objects are partially overlapping. If the difference is 1003226633Sdim // greater, we know they do not overlap. 1004218893Sdim if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 1005226633Sdim if (GEP1BaseOffset >= 0) { 1006226633Sdim if (V2Size != UnknownSize) { 1007226633Sdim if ((uint64_t)GEP1BaseOffset < V2Size) 1008226633Sdim return PartialAlias; 1009226633Sdim return NoAlias; 1010226633Sdim } 1011226633Sdim } else { 1012266715Sdim // We have the situation where: 1013266715Sdim // + + 1014266715Sdim // | BaseOffset | 1015266715Sdim // ---------------->| 1016266715Sdim // |-->V1Size |-------> V2Size 1017266715Sdim // GEP1 V2 1018266715Sdim // We need to know that V2Size is not unknown, otherwise we might have 1019266715Sdim // stripped a gep with negative index ('gep <ptr>, -1, ...). 1020266715Sdim if (V1Size != UnknownSize && V2Size != UnknownSize) { 1021226633Sdim if (-(uint64_t)GEP1BaseOffset < V1Size) 1022226633Sdim return PartialAlias; 1023226633Sdim return NoAlias; 1024226633Sdim } 1025226633Sdim } 1026218893Sdim } 1027218893Sdim 1028226633Sdim // Try to distinguish something like &A[i][1] against &A[42][0]. 1029226633Sdim // Grab the least significant bit set in any of the scales. 1030226633Sdim if (!GEP1VariableIndices.empty()) { 1031226633Sdim uint64_t Modulo = 0; 1032226633Sdim for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 1033226633Sdim Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 1034226633Sdim Modulo = Modulo ^ (Modulo & (Modulo - 1)); 1035226633Sdim 1036226633Sdim // We can compute the difference between the two addresses 1037226633Sdim // mod Modulo. Check whether that difference guarantees that the 1038226633Sdim // two locations do not alias. 1039226633Sdim uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 1040226633Sdim if (V1Size != UnknownSize && V2Size != UnknownSize && 1041226633Sdim ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 1042198090Srdivacky return NoAlias; 1043198090Srdivacky } 1044226633Sdim 1045223017Sdim // Statically, we can see that the base objects are the same, but the 1046223017Sdim // pointers have dynamic offsets which we can't resolve. And none of our 1047223017Sdim // little tricks above worked. 1048223017Sdim // 1049223017Sdim // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 1050223017Sdim // practical effect of this is protecting TBAA in the case of dynamic 1051234353Sdim // indices into arrays of unions or malloc'd memory. 1052223017Sdim return PartialAlias; 1053193323Sed} 1054193323Sed 1055223017Sdimstatic AliasAnalysis::AliasResult 1056223017SdimMergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 1057223017Sdim // If the results agree, take it. 1058223017Sdim if (A == B) 1059223017Sdim return A; 1060223017Sdim // A mix of PartialAlias and MustAlias is PartialAlias. 1061223017Sdim if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 1062223017Sdim (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 1063223017Sdim return AliasAnalysis::PartialAlias; 1064223017Sdim // Otherwise, we don't know anything. 1065223017Sdim return AliasAnalysis::MayAlias; 1066223017Sdim} 1067223017Sdim 1068199989Srdivacky/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 1069199989Srdivacky/// instruction against another. 1070198892SrdivackyAliasAnalysis::AliasResult 1071218893SdimBasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 1072218893Sdim const MDNode *SITBAAInfo, 1073218893Sdim const Value *V2, uint64_t V2Size, 1074218893Sdim const MDNode *V2TBAAInfo) { 1075198892Srdivacky // If the values are Selects with the same condition, we can do a more precise 1076198892Srdivacky // check: just check for aliases between the values on corresponding arms. 1077198892Srdivacky if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1078198892Srdivacky if (SI->getCondition() == SI2->getCondition()) { 1079198892Srdivacky AliasResult Alias = 1080218893Sdim aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 1081218893Sdim SI2->getTrueValue(), V2Size, V2TBAAInfo); 1082198892Srdivacky if (Alias == MayAlias) 1083198892Srdivacky return MayAlias; 1084198892Srdivacky AliasResult ThisAlias = 1085218893Sdim aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 1086218893Sdim SI2->getFalseValue(), V2Size, V2TBAAInfo); 1087223017Sdim return MergeAliasResults(ThisAlias, Alias); 1088198892Srdivacky } 1089198892Srdivacky 1090198892Srdivacky // If both arms of the Select node NoAlias or MustAlias V2, then returns 1091198892Srdivacky // NoAlias / MustAlias. Otherwise, returns MayAlias. 1092198892Srdivacky AliasResult Alias = 1093218893Sdim aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 1094198892Srdivacky if (Alias == MayAlias) 1095198892Srdivacky return MayAlias; 1096210299Sed 1097198892Srdivacky AliasResult ThisAlias = 1098218893Sdim aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 1099223017Sdim return MergeAliasResults(ThisAlias, Alias); 1100198892Srdivacky} 1101198892Srdivacky 1102198090Srdivacky// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 1103198090Srdivacky// against another. 1104198090SrdivackyAliasAnalysis::AliasResult 1105218893SdimBasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 1106218893Sdim const MDNode *PNTBAAInfo, 1107218893Sdim const Value *V2, uint64_t V2Size, 1108218893Sdim const MDNode *V2TBAAInfo) { 1109266715Sdim // Track phi nodes we have visited. We use this information when we determine 1110266715Sdim // value equivalence. 1111266715Sdim VisitedPhiBBs.insert(PN->getParent()); 1112266715Sdim 1113198892Srdivacky // If the values are PHIs in the same block, we can do a more precise 1114198892Srdivacky // as well as efficient check: just check for aliases between the values 1115198892Srdivacky // on corresponding edges. 1116198892Srdivacky if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1117198892Srdivacky if (PN2->getParent() == PN->getParent()) { 1118243830Sdim LocPair Locs(Location(PN, PNSize, PNTBAAInfo), 1119243830Sdim Location(V2, V2Size, V2TBAAInfo)); 1120243830Sdim if (PN > V2) 1121243830Sdim std::swap(Locs.first, Locs.second); 1122249423Sdim // Analyse the PHIs' inputs under the assumption that the PHIs are 1123249423Sdim // NoAlias. 1124249423Sdim // If the PHIs are May/MustAlias there must be (recursively) an input 1125249423Sdim // operand from outside the PHIs' cycle that is MayAlias/MustAlias or 1126249423Sdim // there must be an operation on the PHIs within the PHIs' value cycle 1127249423Sdim // that causes a MayAlias. 1128249423Sdim // Pretend the phis do not alias. 1129249423Sdim AliasResult Alias = NoAlias; 1130249423Sdim assert(AliasCache.count(Locs) && 1131249423Sdim "There must exist an entry for the phi node"); 1132249423Sdim AliasResult OrigAliasResult = AliasCache[Locs]; 1133249423Sdim AliasCache[Locs] = NoAlias; 1134243830Sdim 1135249423Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1136198892Srdivacky AliasResult ThisAlias = 1137218893Sdim aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 1138198892Srdivacky PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 1139218893Sdim V2Size, V2TBAAInfo); 1140223017Sdim Alias = MergeAliasResults(ThisAlias, Alias); 1141223017Sdim if (Alias == MayAlias) 1142223017Sdim break; 1143198892Srdivacky } 1144243830Sdim 1145243830Sdim // Reset if speculation failed. 1146249423Sdim if (Alias != NoAlias) 1147243830Sdim AliasCache[Locs] = OrigAliasResult; 1148243830Sdim 1149198892Srdivacky return Alias; 1150198892Srdivacky } 1151198892Srdivacky 1152198396Srdivacky SmallPtrSet<Value*, 4> UniqueSrc; 1153198090Srdivacky SmallVector<Value*, 4> V1Srcs; 1154198090Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1155198090Srdivacky Value *PV1 = PN->getIncomingValue(i); 1156198090Srdivacky if (isa<PHINode>(PV1)) 1157198090Srdivacky // If any of the source itself is a PHI, return MayAlias conservatively 1158198090Srdivacky // to avoid compile time explosion. The worst possible case is if both 1159198090Srdivacky // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1160198090Srdivacky // and 'n' are the number of PHI sources. 1161198090Srdivacky return MayAlias; 1162198090Srdivacky if (UniqueSrc.insert(PV1)) 1163198090Srdivacky V1Srcs.push_back(PV1); 1164198090Srdivacky } 1165198090Srdivacky 1166218893Sdim AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 1167218893Sdim V1Srcs[0], PNSize, PNTBAAInfo); 1168198090Srdivacky // Early exit if the check of the first PHI source against V2 is MayAlias. 1169198090Srdivacky // Other results are not possible. 1170198090Srdivacky if (Alias == MayAlias) 1171198090Srdivacky return MayAlias; 1172198090Srdivacky 1173198090Srdivacky // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1174198090Srdivacky // NoAlias / MustAlias. Otherwise, returns MayAlias. 1175198090Srdivacky for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1176198090Srdivacky Value *V = V1Srcs[i]; 1177198892Srdivacky 1178218893Sdim AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 1179218893Sdim V, PNSize, PNTBAAInfo); 1180223017Sdim Alias = MergeAliasResults(ThisAlias, Alias); 1181223017Sdim if (Alias == MayAlias) 1182223017Sdim break; 1183198090Srdivacky } 1184198090Srdivacky 1185198090Srdivacky return Alias; 1186198090Srdivacky} 1187198090Srdivacky 1188198090Srdivacky// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 1189198090Srdivacky// such as array references. 1190198090Srdivacky// 1191198090SrdivackyAliasAnalysis::AliasResult 1192218893SdimBasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 1193218893Sdim const MDNode *V1TBAAInfo, 1194218893Sdim const Value *V2, uint64_t V2Size, 1195218893Sdim const MDNode *V2TBAAInfo) { 1196207618Srdivacky // If either of the memory references is empty, it doesn't matter what the 1197207618Srdivacky // pointer values are. 1198207618Srdivacky if (V1Size == 0 || V2Size == 0) 1199207618Srdivacky return NoAlias; 1200207618Srdivacky 1201198090Srdivacky // Strip off any casts if they exist. 1202198090Srdivacky V1 = V1->stripPointerCasts(); 1203198090Srdivacky V2 = V2->stripPointerCasts(); 1204198090Srdivacky 1205198090Srdivacky // Are we checking for alias of the same value? 1206266715Sdim // Because we look 'through' phi nodes we could look at "Value" pointers from 1207266715Sdim // different iterations. We must therefore make sure that this is not the 1208266715Sdim // case. The function isValueEqualInPotentialCycles ensures that this cannot 1209266715Sdim // happen by looking at the visited phi nodes and making sure they cannot 1210266715Sdim // reach the value. 1211266715Sdim if (isValueEqualInPotentialCycles(V1, V2)) 1212266715Sdim return MustAlias; 1213198090Srdivacky 1214204642Srdivacky if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1215198090Srdivacky return NoAlias; // Scalars cannot alias each other 1216198090Srdivacky 1217198090Srdivacky // Figure out what objects these things are pointing to if we can. 1218218893Sdim const Value *O1 = GetUnderlyingObject(V1, TD); 1219218893Sdim const Value *O2 = GetUnderlyingObject(V2, TD); 1220198090Srdivacky 1221199481Srdivacky // Null values in the default address space don't point to any object, so they 1222199481Srdivacky // don't alias any other pointer. 1223199481Srdivacky if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1224199481Srdivacky if (CPN->getType()->getAddressSpace() == 0) 1225199481Srdivacky return NoAlias; 1226199481Srdivacky if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1227199481Srdivacky if (CPN->getType()->getAddressSpace() == 0) 1228199481Srdivacky return NoAlias; 1229199481Srdivacky 1230198090Srdivacky if (O1 != O2) { 1231198090Srdivacky // If V1/V2 point to two different objects we know that we have no alias. 1232198090Srdivacky if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1233198090Srdivacky return NoAlias; 1234199481Srdivacky 1235199481Srdivacky // Constant pointers can't alias with non-const isIdentifiedObject objects. 1236199481Srdivacky if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1237199481Srdivacky (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1238199481Srdivacky return NoAlias; 1239199481Srdivacky 1240263508Sdim // Function arguments can't alias with things that are known to be 1241263508Sdim // unambigously identified at the function level. 1242263508Sdim if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || 1243263508Sdim (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) 1244198090Srdivacky return NoAlias; 1245198090Srdivacky 1246198090Srdivacky // Most objects can't alias null. 1247210299Sed if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1248210299Sed (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1249198090Srdivacky return NoAlias; 1250263508Sdim 1251210299Sed // If one pointer is the result of a call/invoke or load and the other is a 1252210299Sed // non-escaping local object within the same function, then we know the 1253210299Sed // object couldn't escape to a point where the call could return it. 1254210299Sed // 1255210299Sed // Note that if the pointers are in different functions, there are a 1256210299Sed // variety of complications. A call with a nocapture argument may still 1257210299Sed // temporary store the nocapture argument's value in a temporary memory 1258210299Sed // location if that memory location doesn't escape. Or it may pass a 1259210299Sed // nocapture value to other functions as long as they don't capture it. 1260210299Sed if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1261210299Sed return NoAlias; 1262210299Sed if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1263210299Sed return NoAlias; 1264198090Srdivacky } 1265210299Sed 1266198090Srdivacky // If the size of one access is larger than the entire object on the other 1267198090Srdivacky // side, then we know such behavior is undefined and can assume no alias. 1268198090Srdivacky if (TD) 1269243830Sdim if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || 1270243830Sdim (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) 1271198090Srdivacky return NoAlias; 1272263508Sdim 1273223017Sdim // Check the cache before climbing up use-def chains. This also terminates 1274223017Sdim // otherwise infinitely recursive queries. 1275223017Sdim LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 1276223017Sdim Location(V2, V2Size, V2TBAAInfo)); 1277223017Sdim if (V1 > V2) 1278223017Sdim std::swap(Locs.first, Locs.second); 1279223017Sdim std::pair<AliasCacheTy::iterator, bool> Pair = 1280223017Sdim AliasCache.insert(std::make_pair(Locs, MayAlias)); 1281223017Sdim if (!Pair.second) 1282223017Sdim return Pair.first->second; 1283223017Sdim 1284199989Srdivacky // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1285199989Srdivacky // GEP can't simplify, we don't even look at the PHI cases. 1286198396Srdivacky if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1287198090Srdivacky std::swap(V1, V2); 1288198090Srdivacky std::swap(V1Size, V2Size); 1289199989Srdivacky std::swap(O1, O2); 1290243830Sdim std::swap(V1TBAAInfo, V2TBAAInfo); 1291198090Srdivacky } 1292218893Sdim if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1293243830Sdim AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); 1294223017Sdim if (Result != MayAlias) return AliasCache[Locs] = Result; 1295218893Sdim } 1296198090Srdivacky 1297198090Srdivacky if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1298198090Srdivacky std::swap(V1, V2); 1299198090Srdivacky std::swap(V1Size, V2Size); 1300243830Sdim std::swap(V1TBAAInfo, V2TBAAInfo); 1301198090Srdivacky } 1302218893Sdim if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 1303218893Sdim AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 1304218893Sdim V2, V2Size, V2TBAAInfo); 1305223017Sdim if (Result != MayAlias) return AliasCache[Locs] = Result; 1306218893Sdim } 1307198090Srdivacky 1308198892Srdivacky if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1309198892Srdivacky std::swap(V1, V2); 1310198892Srdivacky std::swap(V1Size, V2Size); 1311243830Sdim std::swap(V1TBAAInfo, V2TBAAInfo); 1312198892Srdivacky } 1313218893Sdim if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 1314218893Sdim AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 1315218893Sdim V2, V2Size, V2TBAAInfo); 1316223017Sdim if (Result != MayAlias) return AliasCache[Locs] = Result; 1317218893Sdim } 1318198892Srdivacky 1319218893Sdim // If both pointers are pointing into the same object and one of them 1320218893Sdim // accesses is accessing the entire object, then the accesses must 1321218893Sdim // overlap in some way. 1322218893Sdim if (TD && O1 == O2) 1323243830Sdim if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || 1324243830Sdim (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) 1325223017Sdim return AliasCache[Locs] = PartialAlias; 1326218893Sdim 1327223017Sdim AliasResult Result = 1328223017Sdim AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 1329223017Sdim Location(V2, V2Size, V2TBAAInfo)); 1330223017Sdim return AliasCache[Locs] = Result; 1331198090Srdivacky} 1332266715Sdim 1333266715Sdimbool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V, 1334266715Sdim const Value *V2) { 1335266715Sdim if (V != V2) 1336266715Sdim return false; 1337266715Sdim 1338266715Sdim const Instruction *Inst = dyn_cast<Instruction>(V); 1339266715Sdim if (!Inst) 1340266715Sdim return true; 1341266715Sdim 1342266715Sdim if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) 1343266715Sdim return false; 1344266715Sdim 1345266715Sdim // Use dominance or loop info if available. 1346266715Sdim DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); 1347266715Sdim LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>(); 1348266715Sdim 1349266715Sdim // Make sure that the visited phis cannot reach the Value. This ensures that 1350266715Sdim // the Values cannot come from different iterations of a potential cycle the 1351266715Sdim // phi nodes could be involved in. 1352266715Sdim for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(), 1353266715Sdim PE = VisitedPhiBBs.end(); 1354266715Sdim PI != PE; ++PI) 1355266715Sdim if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI)) 1356266715Sdim return false; 1357266715Sdim 1358266715Sdim return true; 1359266715Sdim} 1360266715Sdim 1361266715Sdim/// GetIndexDifference - Dest and Src are the variable indices from two 1362266715Sdim/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 1363266715Sdim/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 1364266715Sdim/// difference between the two pointers. 1365266715Sdimvoid BasicAliasAnalysis::GetIndexDifference( 1366266715Sdim SmallVectorImpl<VariableGEPIndex> &Dest, 1367266715Sdim const SmallVectorImpl<VariableGEPIndex> &Src) { 1368266715Sdim if (Src.empty()) 1369266715Sdim return; 1370266715Sdim 1371266715Sdim for (unsigned i = 0, e = Src.size(); i != e; ++i) { 1372266715Sdim const Value *V = Src[i].V; 1373266715Sdim ExtensionKind Extension = Src[i].Extension; 1374266715Sdim int64_t Scale = Src[i].Scale; 1375266715Sdim 1376266715Sdim // Find V in Dest. This is N^2, but pointer indices almost never have more 1377266715Sdim // than a few variable indexes. 1378266715Sdim for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 1379266715Sdim if (!isValueEqualInPotentialCycles(Dest[j].V, V) || 1380266715Sdim Dest[j].Extension != Extension) 1381266715Sdim continue; 1382266715Sdim 1383266715Sdim // If we found it, subtract off Scale V's from the entry in Dest. If it 1384266715Sdim // goes to zero, remove the entry. 1385266715Sdim if (Dest[j].Scale != Scale) 1386266715Sdim Dest[j].Scale -= Scale; 1387266715Sdim else 1388266715Sdim Dest.erase(Dest.begin() + j); 1389266715Sdim Scale = 0; 1390266715Sdim break; 1391266715Sdim } 1392266715Sdim 1393266715Sdim // If we didn't consume this entry, add it to the end of the Dest list. 1394266715Sdim if (Scale) { 1395266715Sdim VariableGEPIndex Entry = { V, Extension, -Scale }; 1396266715Sdim Dest.push_back(Entry); 1397266715Sdim } 1398266715Sdim } 1399266715Sdim} 1400