BasicAliasAnalysis.cpp revision 263508
1264790Sbapt//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 2264790Sbapt// 3272955Srodrigc// The LLVM Compiler Infrastructure 4264790Sbapt// 5264790Sbapt// This file is distributed under the University of Illinois Open Source 6264790Sbapt// License. See LICENSE.TXT for details. 7264790Sbapt// 8264790Sbapt//===----------------------------------------------------------------------===// 9264790Sbapt// 10264790Sbapt// This file defines the primary stateless implementation of the 11264790Sbapt// Alias Analysis interface that implements identities (two different 12264790Sbapt// globals cannot alias, etc), but does no stateful analysis. 13264790Sbapt// 14264790Sbapt//===----------------------------------------------------------------------===// 15264790Sbapt 16264790Sbapt#include "llvm/Analysis/Passes.h" 17264790Sbapt#include "llvm/ADT/SmallPtrSet.h" 18264790Sbapt#include "llvm/ADT/SmallVector.h" 19264790Sbapt#include "llvm/Analysis/AliasAnalysis.h" 20264790Sbapt#include "llvm/Analysis/CaptureTracking.h" 21264790Sbapt#include "llvm/Analysis/InstructionSimplify.h" 22264790Sbapt#include "llvm/Analysis/MemoryBuiltins.h" 23264790Sbapt#include "llvm/Analysis/ValueTracking.h" 24264790Sbapt#include "llvm/IR/Constants.h" 25264790Sbapt#include "llvm/IR/DataLayout.h" 26264790Sbapt#include "llvm/IR/DerivedTypes.h" 27264790Sbapt#include "llvm/IR/Function.h" 28264790Sbapt#include "llvm/IR/GlobalAlias.h" 29264790Sbapt#include "llvm/IR/GlobalVariable.h" 30264790Sbapt#include "llvm/IR/Instructions.h" 31264790Sbapt#include "llvm/IR/IntrinsicInst.h" 32264790Sbapt#include "llvm/IR/LLVMContext.h" 33264790Sbapt#include "llvm/IR/Operator.h" 34264790Sbapt#include "llvm/Pass.h" 35264790Sbapt#include "llvm/Support/ErrorHandling.h" 36264790Sbapt#include "llvm/Support/GetElementPtrTypeIterator.h" 37264790Sbapt#include "llvm/Target/TargetLibraryInfo.h" 38264790Sbapt#include <algorithm> 39264790Sbaptusing namespace llvm; 40264790Sbapt 41264790Sbapt//===----------------------------------------------------------------------===// 42264790Sbapt// Useful predicates 43264790Sbapt//===----------------------------------------------------------------------===// 44264790Sbapt 45264790Sbapt/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 46264790Sbapt/// object that never escapes from the function. 47264790Sbaptstatic bool isNonEscapingLocalObject(const Value *V) { 48264790Sbapt // If this is a local allocation, check to see if it escapes. 49264790Sbapt if (isa<AllocaInst>(V) || isNoAliasCall(V)) 50264790Sbapt // Set StoreCaptures to True so that we can assume in our callers that the 51264790Sbapt // pointer is not the result of a load instruction. Currently 52264790Sbapt // PointerMayBeCaptured doesn't have any special analysis for the 53264790Sbapt // StoreCaptures=false case; if it did, our callers could be refined to be 54264790Sbapt // more precise. 55264790Sbapt return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 56264790Sbapt 57264790Sbapt // If this is an argument that corresponds to a byval or noalias argument, 58264790Sbapt // then it has not escaped before entering the function. Check if it escapes 59264790Sbapt // inside the function. 60264790Sbapt if (const Argument *A = dyn_cast<Argument>(V)) 61264790Sbapt if (A->hasByValAttr() || A->hasNoAliasAttr()) 62264790Sbapt // Note even if the argument is marked nocapture we still need to check 63264790Sbapt // for copies made inside the function. The nocapture attribute only 64264790Sbapt // specifies that there are no copies made that outlive the function. 65264790Sbapt return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 66264790Sbapt 67264790Sbapt return false; 68264790Sbapt} 69264790Sbapt 70264790Sbapt/// isEscapeSource - Return true if the pointer is one which would have 71264790Sbapt/// been considered an escape by isNonEscapingLocalObject. 72264790Sbaptstatic bool isEscapeSource(const Value *V) { 73264790Sbapt if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 74264790Sbapt return true; 75264790Sbapt 76264790Sbapt // The load case works because isNonEscapingLocalObject considers all 77264790Sbapt // stores to be escapes (it passes true for the StoreCaptures argument 78264790Sbapt // to PointerMayBeCaptured). 79264790Sbapt if (isa<LoadInst>(V)) 80264790Sbapt return true; 81264790Sbapt 82264790Sbapt return false; 83264790Sbapt} 84264790Sbapt 85264790Sbapt/// getObjectSize - Return the size of the object specified by V, or 86264790Sbapt/// UnknownSize if unknown. 87264790Sbaptstatic uint64_t getObjectSize(const Value *V, const DataLayout &TD, 88264790Sbapt const TargetLibraryInfo &TLI, 89264790Sbapt bool RoundToAlign = false) { 90264790Sbapt uint64_t Size; 91264790Sbapt if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) 92264790Sbapt return Size; 93264790Sbapt return AliasAnalysis::UnknownSize; 94264790Sbapt} 95264790Sbapt 96264790Sbapt/// isObjectSmallerThan - Return true if we can prove that the object specified 97264790Sbapt/// by V is smaller than Size. 98264790Sbaptstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 99264790Sbapt const DataLayout &TD, 100264790Sbapt const TargetLibraryInfo &TLI) { 101264790Sbapt // Note that the meanings of the "object" are slightly different in the 102264790Sbapt // following contexts: 103264790Sbapt // c1: llvm::getObjectSize() 104264790Sbapt // c2: llvm.objectsize() intrinsic 105264790Sbapt // c3: isObjectSmallerThan() 106264790Sbapt // c1 and c2 share the same meaning; however, the meaning of "object" in c3 107264790Sbapt // refers to the "entire object". 108264790Sbapt // 109264790Sbapt // Consider this example: 110264790Sbapt // char *p = (char*)malloc(100) 111264790Sbapt // char *q = p+80; 112264790Sbapt // 113264790Sbapt // In the context of c1 and c2, the "object" pointed by q refers to the 114264790Sbapt // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. 115264790Sbapt // 116264790Sbapt // However, in the context of c3, the "object" refers to the chunk of memory 117264790Sbapt // being allocated. So, the "object" has 100 bytes, and q points to the middle 118264790Sbapt // the "object". In case q is passed to isObjectSmallerThan() as the 1st 119264790Sbapt // parameter, before the llvm::getObjectSize() is called to get the size of 120264790Sbapt // entire object, we should: 121264790Sbapt // - either rewind the pointer q to the base-address of the object in 122264790Sbapt // question (in this case rewind to p), or 123264790Sbapt // - just give up. It is up to caller to make sure the pointer is pointing 124264790Sbapt // to the base address the object. 125264790Sbapt // 126264790Sbapt // We go for 2nd option for simplicity. 127264790Sbapt if (!isIdentifiedObject(V)) 128264790Sbapt return false; 129264790Sbapt 130264790Sbapt // This function needs to use the aligned object size because we allow 131264790Sbapt // reads a bit past the end given sufficient alignment. 132264790Sbapt uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); 133264790Sbapt 134264790Sbapt return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 135264790Sbapt} 136264790Sbapt 137264790Sbapt/// isObjectSize - Return true if we can prove that the object specified 138264790Sbapt/// by V has size Size. 139264790Sbaptstatic bool isObjectSize(const Value *V, uint64_t Size, 140264790Sbapt const DataLayout &TD, const TargetLibraryInfo &TLI) { 141264790Sbapt uint64_t ObjectSize = getObjectSize(V, TD, TLI); 142264790Sbapt return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 143264790Sbapt} 144264790Sbapt 145264790Sbapt/// isIdentifiedFunctionLocal - Return true if V is umabigously identified 146264790Sbapt/// at the function-level. Different IdentifiedFunctionLocals can't alias. 147264790Sbapt/// Further, an IdentifiedFunctionLocal can not alias with any function 148264790Sbapt/// arguments other than itself, which is not neccessarily true for 149264790Sbapt/// IdentifiedObjects. 150264790Sbaptstatic bool isIdentifiedFunctionLocal(const Value *V) 151264790Sbapt{ 152264790Sbapt return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V); 153264790Sbapt} 154264790Sbapt 155264790Sbapt 156264790Sbapt//===----------------------------------------------------------------------===// 157264790Sbapt// GetElementPtr Instruction Decomposition and Analysis 158264790Sbapt//===----------------------------------------------------------------------===// 159264790Sbapt 160264790Sbaptnamespace { 161264790Sbapt enum ExtensionKind { 162264790Sbapt EK_NotExtended, 163264790Sbapt EK_SignExt, 164264790Sbapt EK_ZeroExt 165264790Sbapt }; 166264790Sbapt 167264790Sbapt struct VariableGEPIndex { 168264790Sbapt const Value *V; 169264790Sbapt ExtensionKind Extension; 170264790Sbapt int64_t Scale; 171264790Sbapt 172264790Sbapt bool operator==(const VariableGEPIndex &Other) const { 173264790Sbapt return V == Other.V && Extension == Other.Extension && 174264790Sbapt Scale == Other.Scale; 175264790Sbapt } 176264790Sbapt 177264790Sbapt bool operator!=(const VariableGEPIndex &Other) const { 178264790Sbapt return !operator==(Other); 179264790Sbapt } 180264790Sbapt }; 181264790Sbapt} 182264790Sbapt 183264790Sbapt 184264790Sbapt/// GetLinearExpression - Analyze the specified value as a linear expression: 185264790Sbapt/// "A*V + B", where A and B are constant integers. Return the scale and offset 186264790Sbapt/// values as APInts and return V as a Value*, and return whether we looked 187264790Sbapt/// through any sign or zero extends. The incoming Value is known to have 188264790Sbapt/// IntegerType and it may already be sign or zero extended. 189264790Sbapt/// 190264790Sbapt/// Note that this looks through extends, so the high bits may not be 191264790Sbapt/// represented in the result. 192264790Sbaptstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 193264790Sbapt ExtensionKind &Extension, 194264790Sbapt const DataLayout &TD, unsigned Depth) { 195264790Sbapt assert(V->getType()->isIntegerTy() && "Not an integer value"); 196264790Sbapt 197264790Sbapt // Limit our recursion depth. 198264790Sbapt if (Depth == 6) { 199264790Sbapt Scale = 1; 200264790Sbapt Offset = 0; 201264790Sbapt return V; 202264790Sbapt } 203264790Sbapt 204264790Sbapt if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 205264790Sbapt if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 206264790Sbapt switch (BOp->getOpcode()) { 207264790Sbapt default: break; 208264790Sbapt case Instruction::Or: 209264790Sbapt // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 210264790Sbapt // analyze it. 211264790Sbapt if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 212264790Sbapt break; 213264790Sbapt // FALL THROUGH. 214264790Sbapt case Instruction::Add: 215264790Sbapt V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 216264790Sbapt TD, Depth+1); 217264790Sbapt Offset += RHSC->getValue(); 218264790Sbapt return V; 219264790Sbapt case Instruction::Mul: 220264790Sbapt V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 221264790Sbapt TD, Depth+1); 222264790Sbapt Offset *= RHSC->getValue(); 223264790Sbapt Scale *= RHSC->getValue(); 224264790Sbapt return V; 225264790Sbapt case Instruction::Shl: 226264790Sbapt V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 227264790Sbapt TD, Depth+1); 228264790Sbapt Offset <<= RHSC->getValue().getLimitedValue(); 229264790Sbapt Scale <<= RHSC->getValue().getLimitedValue(); 230264790Sbapt return V; 231264790Sbapt } 232264790Sbapt } 233264790Sbapt } 234264790Sbapt 235264790Sbapt // Since GEP indices are sign extended anyway, we don't care about the high 236264790Sbapt // bits of a sign or zero extended value - just scales and offsets. The 237264790Sbapt // extensions have to be consistent though. 238264790Sbapt if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 239264790Sbapt (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 240264790Sbapt Value *CastOp = cast<CastInst>(V)->getOperand(0); 241264790Sbapt unsigned OldWidth = Scale.getBitWidth(); 242264790Sbapt unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 243264790Sbapt Scale = Scale.trunc(SmallWidth); 244264790Sbapt Offset = Offset.trunc(SmallWidth); 245264790Sbapt Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 246264790Sbapt 247264790Sbapt Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 248264790Sbapt TD, Depth+1); 249264790Sbapt Scale = Scale.zext(OldWidth); 250264790Sbapt Offset = Offset.zext(OldWidth); 251264790Sbapt 252264790Sbapt return Result; 253264790Sbapt } 254264790Sbapt 255264790Sbapt Scale = 1; 256264790Sbapt Offset = 0; 257264790Sbapt return V; 258264790Sbapt} 259264790Sbapt 260264790Sbapt/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 261264790Sbapt/// into a base pointer with a constant offset and a number of scaled symbolic 262264790Sbapt/// offsets. 263264790Sbapt/// 264264790Sbapt/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 265264790Sbapt/// the VarIndices vector) are Value*'s that are known to be scaled by the 266264790Sbapt/// specified amount, but which may have other unrepresented high bits. As such, 267264790Sbapt/// the gep cannot necessarily be reconstructed from its decomposed form. 268264790Sbapt/// 269264790Sbapt/// When DataLayout is around, this function is capable of analyzing everything 270264790Sbapt/// that GetUnderlyingObject can look through. When not, it just looks 271264790Sbapt/// through pointer casts. 272264790Sbapt/// 273264790Sbaptstatic const Value * 274264790SbaptDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 275264790Sbapt SmallVectorImpl<VariableGEPIndex> &VarIndices, 276264790Sbapt const DataLayout *TD) { 277264790Sbapt // Limit recursion depth to limit compile time in crazy cases. 278264790Sbapt unsigned MaxLookup = 6; 279264790Sbapt 280264790Sbapt BaseOffs = 0; 281264790Sbapt do { 282264790Sbapt // See if this is a bitcast or GEP. 283264790Sbapt const Operator *Op = dyn_cast<Operator>(V); 284264790Sbapt if (Op == 0) { 285264790Sbapt // The only non-operator case we can handle are GlobalAliases. 286264790Sbapt if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 287264790Sbapt if (!GA->mayBeOverridden()) { 288264790Sbapt V = GA->getAliasee(); 289272955Srodrigc continue; 290272955Srodrigc } 291272955Srodrigc } 292272955Srodrigc return V; 293272955Srodrigc } 294272955Srodrigc 295272955Srodrigc if (Op->getOpcode() == Instruction::BitCast) { 296272955Srodrigc V = Op->getOperand(0); 297272955Srodrigc continue; 298272955Srodrigc } 299272955Srodrigc 300272955Srodrigc const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 301272955Srodrigc if (GEPOp == 0) { 302272955Srodrigc // If it's not a GEP, hand it off to SimplifyInstruction to see if it 303272955Srodrigc // can come up with something. This matches what GetUnderlyingObject does. 304272955Srodrigc if (const Instruction *I = dyn_cast<Instruction>(V)) 305272955Srodrigc // TODO: Get a DominatorTree and use it here. 306272955Srodrigc if (const Value *Simplified = 307272955Srodrigc SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 308272955Srodrigc V = Simplified; 309272955Srodrigc continue; 310272955Srodrigc } 311272955Srodrigc 312272955Srodrigc return V; 313272955Srodrigc } 314272955Srodrigc 315272955Srodrigc // Don't attempt to analyze GEPs over unsized objects. 316272955Srodrigc if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized()) 317272955Srodrigc return V; 318272955Srodrigc 319264790Sbapt // If we are lacking DataLayout information, we can't compute the offets of 320264790Sbapt // elements computed by GEPs. However, we can handle bitcast equivalent 321264790Sbapt // GEPs. 322264790Sbapt if (TD == 0) { 323264790Sbapt if (!GEPOp->hasAllZeroIndices()) 324264790Sbapt return V; 325264790Sbapt V = GEPOp->getOperand(0); 326264790Sbapt continue; 327264790Sbapt } 328264790Sbapt 329264790Sbapt unsigned AS = GEPOp->getPointerAddressSpace(); 330264790Sbapt // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 331264790Sbapt gep_type_iterator GTI = gep_type_begin(GEPOp); 332264790Sbapt for (User::const_op_iterator I = GEPOp->op_begin()+1, 333264790Sbapt E = GEPOp->op_end(); I != E; ++I) { 334264790Sbapt Value *Index = *I; 335264790Sbapt // Compute the (potentially symbolic) offset in bytes for this index. 336264790Sbapt if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 337264790Sbapt // For a struct, add the member offset. 338264790Sbapt unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 339264790Sbapt if (FieldNo == 0) continue; 340264790Sbapt 341264790Sbapt BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 342264790Sbapt continue; 343264790Sbapt } 344264790Sbapt 345264790Sbapt // For an array/pointer, add the element offset, explicitly scaled. 346264790Sbapt if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 347264790Sbapt if (CIdx->isZero()) continue; 348264790Sbapt BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 349264790Sbapt continue; 350264790Sbapt } 351264790Sbapt 352264790Sbapt uint64_t Scale = TD->getTypeAllocSize(*GTI); 353264790Sbapt ExtensionKind Extension = EK_NotExtended; 354264790Sbapt 355264790Sbapt // If the integer type is smaller than the pointer size, it is implicitly 356264790Sbapt // sign extended to pointer size. 357264790Sbapt unsigned Width = Index->getType()->getIntegerBitWidth(); 358264790Sbapt if (TD->getPointerSizeInBits(AS) > Width) 359264790Sbapt Extension = EK_SignExt; 360264790Sbapt 361264790Sbapt // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 362264790Sbapt APInt IndexScale(Width, 0), IndexOffset(Width, 0); 363264790Sbapt Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 364264790Sbapt *TD, 0); 365264790Sbapt 366264790Sbapt // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 367264790Sbapt // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 368264790Sbapt BaseOffs += IndexOffset.getSExtValue()*Scale; 369264790Sbapt Scale *= IndexScale.getSExtValue(); 370264790Sbapt 371264790Sbapt // If we already had an occurrence of this index variable, merge this 372264790Sbapt // scale into it. For example, we want to handle: 373264790Sbapt // A[x][x] -> x*16 + x*4 -> x*20 374264790Sbapt // This also ensures that 'x' only appears in the index list once. 375264790Sbapt for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 376264790Sbapt if (VarIndices[i].V == Index && 377264790Sbapt VarIndices[i].Extension == Extension) { 378264790Sbapt Scale += VarIndices[i].Scale; 379264790Sbapt VarIndices.erase(VarIndices.begin()+i); 380264790Sbapt break; 381264790Sbapt } 382264790Sbapt } 383264790Sbapt 384264790Sbapt // Make sure that we have a scale that makes sense for this target's 385264790Sbapt // pointer size. 386264790Sbapt if (unsigned ShiftBits = 64 - TD->getPointerSizeInBits(AS)) { 387264790Sbapt Scale <<= ShiftBits; 388264790Sbapt Scale = (int64_t)Scale >> ShiftBits; 389264790Sbapt } 390264790Sbapt 391264790Sbapt if (Scale) { 392264790Sbapt VariableGEPIndex Entry = {Index, Extension, 393264790Sbapt static_cast<int64_t>(Scale)}; 394264790Sbapt VarIndices.push_back(Entry); 395264790Sbapt } 396264790Sbapt } 397264790Sbapt 398264790Sbapt // Analyze the base pointer next. 399264790Sbapt V = GEPOp->getOperand(0); 400264790Sbapt } while (--MaxLookup); 401264790Sbapt 402264790Sbapt // If the chain of expressions is too deep, just return early. 403264790Sbapt return V; 404264790Sbapt} 405264790Sbapt 406264790Sbapt/// GetIndexDifference - Dest and Src are the variable indices from two 407264790Sbapt/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 408264790Sbapt/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 409264790Sbapt/// difference between the two pointers. 410264790Sbaptstatic void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 411264790Sbapt const SmallVectorImpl<VariableGEPIndex> &Src) { 412264790Sbapt if (Src.empty()) return; 413264790Sbapt 414264790Sbapt for (unsigned i = 0, e = Src.size(); i != e; ++i) { 415264790Sbapt const Value *V = Src[i].V; 416264790Sbapt ExtensionKind Extension = Src[i].Extension; 417264790Sbapt int64_t Scale = Src[i].Scale; 418264790Sbapt 419264790Sbapt // Find V in Dest. This is N^2, but pointer indices almost never have more 420264790Sbapt // than a few variable indexes. 421264790Sbapt for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 422264790Sbapt if (Dest[j].V != V || Dest[j].Extension != Extension) continue; 423264790Sbapt 424264790Sbapt // If we found it, subtract off Scale V's from the entry in Dest. If it 425264790Sbapt // goes to zero, remove the entry. 426264790Sbapt if (Dest[j].Scale != Scale) 427264790Sbapt Dest[j].Scale -= Scale; 428264790Sbapt else 429264790Sbapt Dest.erase(Dest.begin()+j); 430264790Sbapt Scale = 0; 431264790Sbapt break; 432264790Sbapt } 433264790Sbapt 434264790Sbapt // If we didn't consume this entry, add it to the end of the Dest list. 435264790Sbapt if (Scale) { 436264790Sbapt VariableGEPIndex Entry = { V, Extension, -Scale }; 437264790Sbapt Dest.push_back(Entry); 438264790Sbapt } 439264790Sbapt } 440264790Sbapt} 441264790Sbapt 442264790Sbapt//===----------------------------------------------------------------------===// 443264790Sbapt// BasicAliasAnalysis Pass 444264790Sbapt//===----------------------------------------------------------------------===// 445264790Sbapt 446264790Sbapt#ifndef NDEBUG 447264790Sbaptstatic const Function *getParent(const Value *V) { 448264790Sbapt if (const Instruction *inst = dyn_cast<Instruction>(V)) 449264790Sbapt return inst->getParent()->getParent(); 450264790Sbapt 451264790Sbapt if (const Argument *arg = dyn_cast<Argument>(V)) 452264790Sbapt return arg->getParent(); 453264790Sbapt 454264790Sbapt return NULL; 455264790Sbapt} 456264790Sbapt 457264790Sbaptstatic bool notDifferentParent(const Value *O1, const Value *O2) { 458264790Sbapt 459264790Sbapt const Function *F1 = getParent(O1); 460264790Sbapt const Function *F2 = getParent(O2); 461264790Sbapt 462264790Sbapt return !F1 || !F2 || F1 == F2; 463264790Sbapt} 464264790Sbapt#endif 465264790Sbapt 466264790Sbaptnamespace { 467264790Sbapt /// BasicAliasAnalysis - This is the primary alias analysis implementation. 468264790Sbapt struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 469264790Sbapt static char ID; // Class identification, replacement for typeinfo 470264790Sbapt BasicAliasAnalysis() : ImmutablePass(ID) { 471264790Sbapt initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 472264790Sbapt } 473264790Sbapt 474264790Sbapt virtual void initializePass() { 475264790Sbapt InitializeAliasAnalysis(this); 476264790Sbapt } 477264790Sbapt 478264790Sbapt virtual void getAnalysisUsage(AnalysisUsage &AU) const { 479264790Sbapt AU.addRequired<AliasAnalysis>(); 480264790Sbapt AU.addRequired<TargetLibraryInfo>(); 481264790Sbapt } 482264790Sbapt 483264790Sbapt virtual AliasResult alias(const Location &LocA, 484264790Sbapt const Location &LocB) { 485264790Sbapt assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 486264790Sbapt assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 487264790Sbapt "BasicAliasAnalysis doesn't support interprocedural queries."); 488264790Sbapt AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 489264790Sbapt LocB.Ptr, LocB.Size, LocB.TBAATag); 490264790Sbapt // AliasCache rarely has more than 1 or 2 elements, always use 491264790Sbapt // shrink_and_clear so it quickly returns to the inline capacity of the 492264790Sbapt // SmallDenseMap if it ever grows larger. 493264790Sbapt // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 494264790Sbapt AliasCache.shrink_and_clear(); 495264790Sbapt return Alias; 496264790Sbapt } 497264790Sbapt 498264790Sbapt virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 499264790Sbapt const Location &Loc); 500264790Sbapt 501264790Sbapt virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 502264790Sbapt ImmutableCallSite CS2) { 503264790Sbapt // The AliasAnalysis base class has some smarts, lets use them. 504264790Sbapt return AliasAnalysis::getModRefInfo(CS1, CS2); 505264790Sbapt } 506264790Sbapt 507264790Sbapt /// pointsToConstantMemory - Chase pointers until we find a (constant 508264790Sbapt /// global) or not. 509264790Sbapt virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 510264790Sbapt 511264790Sbapt /// getModRefBehavior - Return the behavior when calling the given 512264790Sbapt /// call site. 513264790Sbapt virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 514264790Sbapt 515264790Sbapt /// getModRefBehavior - Return the behavior when calling the given function. 516264790Sbapt /// For use when the call site is not known. 517264790Sbapt virtual ModRefBehavior getModRefBehavior(const Function *F); 518264790Sbapt 519264790Sbapt /// getAdjustedAnalysisPointer - This method is used when a pass implements 520264790Sbapt /// an analysis interface through multiple inheritance. If needed, it 521264790Sbapt /// should override this to adjust the this pointer as needed for the 522264790Sbapt /// specified pass info. 523264790Sbapt virtual void *getAdjustedAnalysisPointer(const void *ID) { 524264790Sbapt if (ID == &AliasAnalysis::ID) 525264790Sbapt return (AliasAnalysis*)this; 526264790Sbapt return this; 527264790Sbapt } 528264790Sbapt 529272955Srodrigc private: 530264790Sbapt // AliasCache - Track alias queries to guard against recursion. 531264790Sbapt typedef std::pair<Location, Location> LocPair; 532264790Sbapt typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; 533264790Sbapt AliasCacheTy AliasCache; 534264790Sbapt 535264790Sbapt // Visited - Track instructions visited by pointsToConstantMemory. 536264790Sbapt SmallPtrSet<const Value*, 16> Visited; 537264790Sbapt 538272955Srodrigc // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 539264790Sbapt // instruction against another. 540264790Sbapt AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 541272955Srodrigc const MDNode *V1TBAAInfo, 542272955Srodrigc const Value *V2, uint64_t V2Size, 543264790Sbapt const MDNode *V2TBAAInfo, 544264790Sbapt const Value *UnderlyingV1, const Value *UnderlyingV2); 545264790Sbapt 546264790Sbapt // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 547264790Sbapt // instruction against another. 548264790Sbapt AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 549264790Sbapt const MDNode *PNTBAAInfo, 550264790Sbapt const Value *V2, uint64_t V2Size, 551264790Sbapt const MDNode *V2TBAAInfo); 552264790Sbapt 553264790Sbapt /// aliasSelect - Disambiguate a Select instruction against another value. 554264790Sbapt AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 555264790Sbapt const MDNode *SITBAAInfo, 556264790Sbapt const Value *V2, uint64_t V2Size, 557264790Sbapt const MDNode *V2TBAAInfo); 558264790Sbapt 559264790Sbapt AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 560264790Sbapt const MDNode *V1TBAATag, 561264790Sbapt const Value *V2, uint64_t V2Size, 562264790Sbapt const MDNode *V2TBAATag); 563264790Sbapt }; 564264790Sbapt} // End of anonymous namespace 565264790Sbapt 566264790Sbapt// Register this pass... 567264790Sbaptchar BasicAliasAnalysis::ID = 0; 568264790SbaptINITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 569264790Sbapt "Basic Alias Analysis (stateless AA impl)", 570264790Sbapt false, true, false) 571264790SbaptINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 572264790SbaptINITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 573264790Sbapt "Basic Alias Analysis (stateless AA impl)", 574264790Sbapt false, true, false) 575264790Sbapt 576264790Sbapt 577264790SbaptImmutablePass *llvm::createBasicAliasAnalysisPass() { 578264790Sbapt return new BasicAliasAnalysis(); 579264790Sbapt} 580264790Sbapt 581264790Sbapt/// pointsToConstantMemory - Returns whether the given pointer value 582264790Sbapt/// points to memory that is local to the function, with global constants being 583264790Sbapt/// considered local to all functions. 584264790Sbaptbool 585264790SbaptBasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 586264790Sbapt assert(Visited.empty() && "Visited must be cleared after use!"); 587264790Sbapt 588264790Sbapt unsigned MaxLookup = 8; 589264790Sbapt SmallVector<const Value *, 16> Worklist; 590264790Sbapt Worklist.push_back(Loc.Ptr); 591264790Sbapt do { 592264790Sbapt const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 593264790Sbapt if (!Visited.insert(V)) { 594264790Sbapt Visited.clear(); 595264790Sbapt return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 596264790Sbapt } 597264790Sbapt 598264790Sbapt // An alloca instruction defines local memory. 599264790Sbapt if (OrLocal && isa<AllocaInst>(V)) 600264790Sbapt continue; 601264790Sbapt 602264790Sbapt // A global constant counts as local memory for our purposes. 603264790Sbapt if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 604264790Sbapt // Note: this doesn't require GV to be "ODR" because it isn't legal for a 605264790Sbapt // global to be marked constant in some modules and non-constant in 606264790Sbapt // others. GV may even be a declaration, not a definition. 607264790Sbapt if (!GV->isConstant()) { 608264790Sbapt Visited.clear(); 609264790Sbapt return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 610264790Sbapt } 611264790Sbapt continue; 612264790Sbapt } 613264790Sbapt 614264790Sbapt // If both select values point to local memory, then so does the select. 615264790Sbapt if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 616264790Sbapt Worklist.push_back(SI->getTrueValue()); 617264790Sbapt Worklist.push_back(SI->getFalseValue()); 618264790Sbapt continue; 619264790Sbapt } 620264790Sbapt 621264790Sbapt // If all values incoming to a phi node point to local memory, then so does 622264790Sbapt // the phi. 623264790Sbapt if (const PHINode *PN = dyn_cast<PHINode>(V)) { 624264790Sbapt // Don't bother inspecting phi nodes with many operands. 625264790Sbapt if (PN->getNumIncomingValues() > MaxLookup) { 626264790Sbapt Visited.clear(); 627264790Sbapt return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 628264790Sbapt } 629264790Sbapt for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 630264790Sbapt Worklist.push_back(PN->getIncomingValue(i)); 631264790Sbapt continue; 632264790Sbapt } 633264790Sbapt 634264790Sbapt // Otherwise be conservative. 635264790Sbapt Visited.clear(); 636264790Sbapt return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 637264790Sbapt 638264790Sbapt } while (!Worklist.empty() && --MaxLookup); 639264790Sbapt 640264790Sbapt Visited.clear(); 641264790Sbapt return Worklist.empty(); 642264790Sbapt} 643264790Sbapt 644264790Sbapt/// getModRefBehavior - Return the behavior when calling the given call site. 645264790SbaptAliasAnalysis::ModRefBehavior 646264790SbaptBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 647264790Sbapt if (CS.doesNotAccessMemory()) 648264790Sbapt // Can't do better than this. 649264790Sbapt return DoesNotAccessMemory; 650264790Sbapt 651264790Sbapt ModRefBehavior Min = UnknownModRefBehavior; 652264790Sbapt 653264790Sbapt // If the callsite knows it only reads memory, don't return worse 654264790Sbapt // than that. 655264790Sbapt if (CS.onlyReadsMemory()) 656264790Sbapt Min = OnlyReadsMemory; 657264790Sbapt 658264790Sbapt // The AliasAnalysis base class has some smarts, lets use them. 659264790Sbapt return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 660264790Sbapt} 661264790Sbapt 662264790Sbapt/// getModRefBehavior - Return the behavior when calling the given function. 663264790Sbapt/// For use when the call site is not known. 664264790SbaptAliasAnalysis::ModRefBehavior 665264790SbaptBasicAliasAnalysis::getModRefBehavior(const Function *F) { 666264790Sbapt // If the function declares it doesn't access memory, we can't do better. 667264790Sbapt if (F->doesNotAccessMemory()) 668264790Sbapt return DoesNotAccessMemory; 669264790Sbapt 670264790Sbapt // For intrinsics, we can check the table. 671264790Sbapt if (unsigned iid = F->getIntrinsicID()) { 672264790Sbapt#define GET_INTRINSIC_MODREF_BEHAVIOR 673264790Sbapt#include "llvm/IR/Intrinsics.gen" 674264790Sbapt#undef GET_INTRINSIC_MODREF_BEHAVIOR 675264790Sbapt } 676264790Sbapt 677264790Sbapt ModRefBehavior Min = UnknownModRefBehavior; 678264790Sbapt 679264790Sbapt // If the function declares it only reads memory, go with that. 680264790Sbapt if (F->onlyReadsMemory()) 681264790Sbapt Min = OnlyReadsMemory; 682264790Sbapt 683264790Sbapt // Otherwise be conservative. 684264790Sbapt return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 685264790Sbapt} 686264790Sbapt 687264790Sbapt/// getModRefInfo - Check to see if the specified callsite can clobber the 688264790Sbapt/// specified memory object. Since we only look at local properties of this 689264790Sbapt/// function, we really can't say much about this query. We do, however, use 690264790Sbapt/// simple "address taken" analysis on local objects. 691264790SbaptAliasAnalysis::ModRefResult 692264790SbaptBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 693264790Sbapt const Location &Loc) { 694264790Sbapt assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 695264790Sbapt "AliasAnalysis query involving multiple functions!"); 696264790Sbapt 697264790Sbapt const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 698264790Sbapt 699264790Sbapt // If this is a tail call and Loc.Ptr points to a stack location, we know that 700264790Sbapt // the tail call cannot access or modify the local stack. 701264790Sbapt // We cannot exclude byval arguments here; these belong to the caller of 702264790Sbapt // the current function not to the current function, and a tail callee 703264790Sbapt // may reference them. 704264790Sbapt if (isa<AllocaInst>(Object)) 705264790Sbapt if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 706264790Sbapt if (CI->isTailCall()) 707264790Sbapt return NoModRef; 708264790Sbapt 709264790Sbapt // If the pointer is to a locally allocated object that does not escape, 710264790Sbapt // then the call can not mod/ref the pointer unless the call takes the pointer 711264790Sbapt // as an argument, and itself doesn't capture it. 712264790Sbapt if (!isa<Constant>(Object) && CS.getInstruction() != Object && 713264790Sbapt isNonEscapingLocalObject(Object)) { 714264790Sbapt bool PassedAsArg = false; 715264790Sbapt unsigned ArgNo = 0; 716264790Sbapt for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 717264790Sbapt CI != CE; ++CI, ++ArgNo) { 718264790Sbapt // Only look at the no-capture or byval pointer arguments. If this 719264790Sbapt // pointer were passed to arguments that were neither of these, then it 720264790Sbapt // couldn't be no-capture. 721264790Sbapt if (!(*CI)->getType()->isPointerTy() || 722264790Sbapt (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 723264790Sbapt continue; 724264790Sbapt 725264790Sbapt // If this is a no-capture pointer argument, see if we can tell that it 726272955Srodrigc // is impossible to alias the pointer we're checking. If not, we have to 727272955Srodrigc // assume that the call could touch the pointer, even though it doesn't 728264790Sbapt // escape. 729264790Sbapt if (!isNoAlias(Location(*CI), Location(Object))) { 730264790Sbapt PassedAsArg = true; 731264790Sbapt break; 732264790Sbapt } 733264790Sbapt } 734264790Sbapt 735264790Sbapt if (!PassedAsArg) 736264790Sbapt return NoModRef; 737264790Sbapt } 738264790Sbapt 739264790Sbapt const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 740264790Sbapt ModRefResult Min = ModRef; 741264790Sbapt 742264790Sbapt // Finally, handle specific knowledge of intrinsics. 743264790Sbapt const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 744264790Sbapt if (II != 0) 745264790Sbapt switch (II->getIntrinsicID()) { 746264790Sbapt default: break; 747264790Sbapt case Intrinsic::memcpy: 748264790Sbapt case Intrinsic::memmove: { 749264790Sbapt uint64_t Len = UnknownSize; 750264790Sbapt if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 751264790Sbapt Len = LenCI->getZExtValue(); 752264790Sbapt Value *Dest = II->getArgOperand(0); 753264790Sbapt Value *Src = II->getArgOperand(1); 754264790Sbapt // If it can't overlap the source dest, then it doesn't modref the loc. 755264790Sbapt if (isNoAlias(Location(Dest, Len), Loc)) { 756264790Sbapt if (isNoAlias(Location(Src, Len), Loc)) 757264790Sbapt return NoModRef; 758264790Sbapt // If it can't overlap the dest, then worst case it reads the loc. 759264790Sbapt Min = Ref; 760264790Sbapt } else if (isNoAlias(Location(Src, Len), Loc)) { 761264790Sbapt // If it can't overlap the source, then worst case it mutates the loc. 762264790Sbapt Min = Mod; 763264790Sbapt } 764264790Sbapt break; 765264790Sbapt } 766264790Sbapt case Intrinsic::memset: 767264790Sbapt // Since memset is 'accesses arguments' only, the AliasAnalysis base class 768264790Sbapt // will handle it for the variable length case. 769264790Sbapt if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 770264790Sbapt uint64_t Len = LenCI->getZExtValue(); 771264790Sbapt Value *Dest = II->getArgOperand(0); 772264790Sbapt if (isNoAlias(Location(Dest, Len), Loc)) 773264790Sbapt return NoModRef; 774264790Sbapt } 775264790Sbapt // We know that memset doesn't load anything. 776264790Sbapt Min = Mod; 777264790Sbapt break; 778264790Sbapt case Intrinsic::lifetime_start: 779264790Sbapt case Intrinsic::lifetime_end: 780264790Sbapt case Intrinsic::invariant_start: { 781264790Sbapt uint64_t PtrSize = 782264790Sbapt cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 783264790Sbapt if (isNoAlias(Location(II->getArgOperand(1), 784264790Sbapt PtrSize, 785264790Sbapt II->getMetadata(LLVMContext::MD_tbaa)), 786264790Sbapt Loc)) 787264790Sbapt return NoModRef; 788264790Sbapt break; 789264790Sbapt } 790264790Sbapt case Intrinsic::invariant_end: { 791264790Sbapt uint64_t PtrSize = 792264790Sbapt cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 793264790Sbapt if (isNoAlias(Location(II->getArgOperand(2), 794264790Sbapt PtrSize, 795264790Sbapt II->getMetadata(LLVMContext::MD_tbaa)), 796264790Sbapt Loc)) 797264790Sbapt return NoModRef; 798264790Sbapt break; 799264790Sbapt } 800264790Sbapt case Intrinsic::arm_neon_vld1: { 801264790Sbapt // LLVM's vld1 and vst1 intrinsics currently only support a single 802264790Sbapt // vector register. 803264790Sbapt uint64_t Size = 804264790Sbapt TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 805264790Sbapt if (isNoAlias(Location(II->getArgOperand(0), Size, 806264790Sbapt II->getMetadata(LLVMContext::MD_tbaa)), 807264790Sbapt Loc)) 808264790Sbapt return NoModRef; 809264790Sbapt break; 810264790Sbapt } 811264790Sbapt case Intrinsic::arm_neon_vst1: { 812264790Sbapt uint64_t Size = 813264790Sbapt TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 814264790Sbapt if (isNoAlias(Location(II->getArgOperand(0), Size, 815264790Sbapt II->getMetadata(LLVMContext::MD_tbaa)), 816264790Sbapt Loc)) 817264790Sbapt return NoModRef; 818264790Sbapt break; 819264790Sbapt } 820264790Sbapt } 821264790Sbapt 822264790Sbapt // We can bound the aliasing properties of memset_pattern16 just as we can 823272955Srodrigc // for memcpy/memset. This is particularly important because the 824264790Sbapt // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 825272955Srodrigc // whenever possible. 826264790Sbapt else if (TLI.has(LibFunc::memset_pattern16) && 827264790Sbapt CS.getCalledFunction() && 828272955Srodrigc CS.getCalledFunction()->getName() == "memset_pattern16") { 829264790Sbapt const Function *MS = CS.getCalledFunction(); 830264790Sbapt FunctionType *MemsetType = MS->getFunctionType(); 831264790Sbapt if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 832264790Sbapt isa<PointerType>(MemsetType->getParamType(0)) && 833264790Sbapt isa<PointerType>(MemsetType->getParamType(1)) && 834264790Sbapt isa<IntegerType>(MemsetType->getParamType(2))) { 835264790Sbapt uint64_t Len = UnknownSize; 836264790Sbapt if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 837264790Sbapt Len = LenCI->getZExtValue(); 838264790Sbapt const Value *Dest = CS.getArgument(0); 839264790Sbapt const Value *Src = CS.getArgument(1); 840264790Sbapt // If it can't overlap the source dest, then it doesn't modref the loc. 841264790Sbapt if (isNoAlias(Location(Dest, Len), Loc)) { 842264790Sbapt // Always reads 16 bytes of the source. 843264790Sbapt if (isNoAlias(Location(Src, 16), Loc)) 844264790Sbapt return NoModRef; 845264790Sbapt // If it can't overlap the dest, then worst case it reads the loc. 846264790Sbapt Min = Ref; 847264790Sbapt // Always reads 16 bytes of the source. 848264790Sbapt } else if (isNoAlias(Location(Src, 16), Loc)) { 849264790Sbapt // If it can't overlap the source, then worst case it mutates the loc. 850264790Sbapt Min = Mod; 851264790Sbapt } 852264790Sbapt } 853264790Sbapt } 854264790Sbapt 855264790Sbapt // The AliasAnalysis base class has some smarts, lets use them. 856264790Sbapt return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 857264790Sbapt} 858264790Sbapt 859264790Sbaptstatic bool areVarIndicesEqual(SmallVectorImpl<VariableGEPIndex> &Indices1, 860264790Sbapt SmallVectorImpl<VariableGEPIndex> &Indices2) { 861264790Sbapt unsigned Size1 = Indices1.size(); 862264790Sbapt unsigned Size2 = Indices2.size(); 863264790Sbapt 864264790Sbapt if (Size1 != Size2) 865264790Sbapt return false; 866264790Sbapt 867264790Sbapt for (unsigned I = 0; I != Size1; ++I) 868264790Sbapt if (Indices1[I] != Indices2[I]) 869264790Sbapt return false; 870264790Sbapt 871264790Sbapt return true; 872264790Sbapt} 873264790Sbapt 874264790Sbapt/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 875264790Sbapt/// against another pointer. We know that V1 is a GEP, but we don't know 876264790Sbapt/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 877264790Sbapt/// UnderlyingV2 is the same for V2. 878264790Sbapt/// 879264790SbaptAliasAnalysis::AliasResult 880264790SbaptBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 881264790Sbapt const MDNode *V1TBAAInfo, 882264790Sbapt const Value *V2, uint64_t V2Size, 883272955Srodrigc const MDNode *V2TBAAInfo, 884264790Sbapt const Value *UnderlyingV1, 885264790Sbapt const Value *UnderlyingV2) { 886264790Sbapt int64_t GEP1BaseOffset; 887264790Sbapt SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 888264790Sbapt 889264790Sbapt // If we have two gep instructions with must-alias or not-alias'ing base 890264790Sbapt // pointers, figure out if the indexes to the GEP tell us anything about the 891264790Sbapt // derived pointer. 892264790Sbapt if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 893264790Sbapt // Do the base pointers alias? 894264790Sbapt AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 895264790Sbapt UnderlyingV2, UnknownSize, 0); 896264790Sbapt 897264790Sbapt // Check for geps of non-aliasing underlying pointers where the offsets are 898264790Sbapt // identical. 899264790Sbapt if ((BaseAlias == MayAlias) && V1Size == V2Size) { 900264790Sbapt // Do the base pointers alias assuming type and size. 901264790Sbapt AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, 902264790Sbapt V1TBAAInfo, UnderlyingV2, 903264790Sbapt V2Size, V2TBAAInfo); 904264790Sbapt if (PreciseBaseAlias == NoAlias) { 905264790Sbapt // See if the computed offset from the common pointer tells us about the 906264790Sbapt // relation of the resulting pointer. 907264790Sbapt int64_t GEP2BaseOffset; 908264790Sbapt SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 909264790Sbapt const Value *GEP2BasePtr = 910264790Sbapt DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 911264790Sbapt const Value *GEP1BasePtr = 912264790Sbapt DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 913264790Sbapt // DecomposeGEPExpression and GetUnderlyingObject should return the 914264790Sbapt // same result except when DecomposeGEPExpression has no DataLayout. 915264790Sbapt if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 916264790Sbapt assert(TD == 0 && 917264790Sbapt "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 918264790Sbapt return MayAlias; 919264790Sbapt } 920264790Sbapt // Same offsets. 921264790Sbapt if (GEP1BaseOffset == GEP2BaseOffset && 922264790Sbapt areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) 923264790Sbapt return NoAlias; 924264790Sbapt GEP1VariableIndices.clear(); 925264790Sbapt } 926264790Sbapt } 927264790Sbapt 928264790Sbapt // If we get a No or May, then return it immediately, no amount of analysis 929264790Sbapt // will improve this situation. 930264790Sbapt if (BaseAlias != MustAlias) return BaseAlias; 931264790Sbapt 932264790Sbapt // Otherwise, we have a MustAlias. Since the base pointers alias each other 933264790Sbapt // exactly, see if the computed offset from the common pointer tells us 934264790Sbapt // about the relation of the resulting pointer. 935264790Sbapt const Value *GEP1BasePtr = 936264790Sbapt DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 937264790Sbapt 938264790Sbapt int64_t GEP2BaseOffset; 939264790Sbapt SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 940264790Sbapt const Value *GEP2BasePtr = 941264790Sbapt DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 942264790Sbapt 943264790Sbapt // DecomposeGEPExpression and GetUnderlyingObject should return the 944264790Sbapt // same result except when DecomposeGEPExpression has no DataLayout. 945264790Sbapt if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 946264790Sbapt assert(TD == 0 && 947264790Sbapt "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 948264790Sbapt return MayAlias; 949264790Sbapt } 950264790Sbapt 951264790Sbapt // Subtract the GEP2 pointer from the GEP1 pointer to find out their 952264790Sbapt // symbolic difference. 953264790Sbapt GEP1BaseOffset -= GEP2BaseOffset; 954264790Sbapt GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 955264790Sbapt 956264790Sbapt } else { 957264790Sbapt // Check to see if these two pointers are related by the getelementptr 958264790Sbapt // instruction. If one pointer is a GEP with a non-zero index of the other 959264790Sbapt // pointer, we know they cannot alias. 960264790Sbapt 961264790Sbapt // If both accesses are unknown size, we can't do anything useful here. 962264790Sbapt if (V1Size == UnknownSize && V2Size == UnknownSize) 963264790Sbapt return MayAlias; 964264790Sbapt 965264790Sbapt AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 966264790Sbapt V2, V2Size, V2TBAAInfo); 967264790Sbapt if (R != MustAlias) 968264790Sbapt // If V2 may alias GEP base pointer, conservatively returns MayAlias. 969264790Sbapt // If V2 is known not to alias GEP base pointer, then the two values 970264790Sbapt // cannot alias per GEP semantics: "A pointer value formed from a 971264790Sbapt // getelementptr instruction is associated with the addresses associated 972264790Sbapt // with the first operand of the getelementptr". 973264790Sbapt return R; 974264790Sbapt 975264790Sbapt const Value *GEP1BasePtr = 976264790Sbapt DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 977272955Srodrigc 978264790Sbapt // DecomposeGEPExpression and GetUnderlyingObject should return the 979272955Srodrigc // same result except when DecomposeGEPExpression has no DataLayout. 980264790Sbapt if (GEP1BasePtr != UnderlyingV1) { 981264790Sbapt assert(TD == 0 && 982272955Srodrigc "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 983264790Sbapt return MayAlias; 984272955Srodrigc } 985264790Sbapt } 986264790Sbapt 987264790Sbapt // In the two GEP Case, if there is no difference in the offsets of the 988264790Sbapt // computed pointers, the resultant pointers are a must alias. This 989264790Sbapt // hapens when we have two lexically identical GEP's (for example). 990264790Sbapt // 991264790Sbapt // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 992264790Sbapt // must aliases the GEP, the end result is a must alias also. 993272955Srodrigc if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 994264790Sbapt return MustAlias; 995272955Srodrigc 996264790Sbapt // If there is a constant difference between the pointers, but the difference 997264790Sbapt // is less than the size of the associated memory object, then we know 998272955Srodrigc // that the objects are partially overlapping. If the difference is 999264790Sbapt // greater, we know they do not overlap. 1000264790Sbapt if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 1001264790Sbapt if (GEP1BaseOffset >= 0) { 1002264790Sbapt if (V2Size != UnknownSize) { 1003264790Sbapt if ((uint64_t)GEP1BaseOffset < V2Size) 1004264790Sbapt return PartialAlias; 1005264790Sbapt return NoAlias; 1006264790Sbapt } 1007264790Sbapt } else { 1008264790Sbapt if (V1Size != UnknownSize) { 1009264790Sbapt if (-(uint64_t)GEP1BaseOffset < V1Size) 1010264790Sbapt return PartialAlias; 1011264790Sbapt return NoAlias; 1012264790Sbapt } 1013264790Sbapt } 1014264790Sbapt } 1015264790Sbapt 1016264790Sbapt // Try to distinguish something like &A[i][1] against &A[42][0]. 1017264790Sbapt // Grab the least significant bit set in any of the scales. 1018264790Sbapt if (!GEP1VariableIndices.empty()) { 1019264790Sbapt uint64_t Modulo = 0; 1020264790Sbapt for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 1021264790Sbapt Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 1022264790Sbapt Modulo = Modulo ^ (Modulo & (Modulo - 1)); 1023264790Sbapt 1024264790Sbapt // We can compute the difference between the two addresses 1025264790Sbapt // mod Modulo. Check whether that difference guarantees that the 1026264790Sbapt // two locations do not alias. 1027264790Sbapt uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 1028272955Srodrigc if (V1Size != UnknownSize && V2Size != UnknownSize && 1029264790Sbapt ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 1030272955Srodrigc return NoAlias; 1031264790Sbapt } 1032264790Sbapt 1033272955Srodrigc // Statically, we can see that the base objects are the same, but the 1034264790Sbapt // pointers have dynamic offsets which we can't resolve. And none of our 1035264790Sbapt // little tricks above worked. 1036264790Sbapt // 1037264790Sbapt // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 1038264790Sbapt // practical effect of this is protecting TBAA in the case of dynamic 1039264790Sbapt // indices into arrays of unions or malloc'd memory. 1040264790Sbapt return PartialAlias; 1041264790Sbapt} 1042264790Sbapt 1043264790Sbaptstatic AliasAnalysis::AliasResult 1044264790SbaptMergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 1045264790Sbapt // If the results agree, take it. 1046264790Sbapt if (A == B) 1047264790Sbapt return A; 1048264790Sbapt // A mix of PartialAlias and MustAlias is PartialAlias. 1049264790Sbapt if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 1050264790Sbapt (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 1051264790Sbapt return AliasAnalysis::PartialAlias; 1052264790Sbapt // Otherwise, we don't know anything. 1053264790Sbapt return AliasAnalysis::MayAlias; 1054264790Sbapt} 1055264790Sbapt 1056264790Sbapt/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 1057264790Sbapt/// instruction against another. 1058264790SbaptAliasAnalysis::AliasResult 1059264790SbaptBasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 1060264790Sbapt const MDNode *SITBAAInfo, 1061264790Sbapt const Value *V2, uint64_t V2Size, 1062264790Sbapt const MDNode *V2TBAAInfo) { 1063264790Sbapt // If the values are Selects with the same condition, we can do a more precise 1064264790Sbapt // check: just check for aliases between the values on corresponding arms. 1065264790Sbapt if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1066264790Sbapt if (SI->getCondition() == SI2->getCondition()) { 1067264790Sbapt AliasResult Alias = 1068264790Sbapt aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 1069264790Sbapt SI2->getTrueValue(), V2Size, V2TBAAInfo); 1070264790Sbapt if (Alias == MayAlias) 1071264790Sbapt return MayAlias; 1072264790Sbapt AliasResult ThisAlias = 1073264790Sbapt aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 1074264790Sbapt SI2->getFalseValue(), V2Size, V2TBAAInfo); 1075264790Sbapt return MergeAliasResults(ThisAlias, Alias); 1076264790Sbapt } 1077264790Sbapt 1078264790Sbapt // If both arms of the Select node NoAlias or MustAlias V2, then returns 1079264790Sbapt // NoAlias / MustAlias. Otherwise, returns MayAlias. 1080264790Sbapt AliasResult Alias = 1081264790Sbapt aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 1082264790Sbapt if (Alias == MayAlias) 1083264790Sbapt return MayAlias; 1084264790Sbapt 1085264790Sbapt AliasResult ThisAlias = 1086264790Sbapt aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 1087264790Sbapt return MergeAliasResults(ThisAlias, Alias); 1088264790Sbapt} 1089264790Sbapt 1090264790Sbapt// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 1091264790Sbapt// against another. 1092264790SbaptAliasAnalysis::AliasResult 1093264790SbaptBasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 1094264790Sbapt const MDNode *PNTBAAInfo, 1095264790Sbapt const Value *V2, uint64_t V2Size, 1096264790Sbapt const MDNode *V2TBAAInfo) { 1097264790Sbapt // If the values are PHIs in the same block, we can do a more precise 1098264790Sbapt // as well as efficient check: just check for aliases between the values 1099264790Sbapt // on corresponding edges. 1100264790Sbapt if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1101264790Sbapt if (PN2->getParent() == PN->getParent()) { 1102264790Sbapt LocPair Locs(Location(PN, PNSize, PNTBAAInfo), 1103264790Sbapt Location(V2, V2Size, V2TBAAInfo)); 1104264790Sbapt if (PN > V2) 1105264790Sbapt std::swap(Locs.first, Locs.second); 1106264790Sbapt // Analyse the PHIs' inputs under the assumption that the PHIs are 1107264790Sbapt // NoAlias. 1108264790Sbapt // If the PHIs are May/MustAlias there must be (recursively) an input 1109264790Sbapt // operand from outside the PHIs' cycle that is MayAlias/MustAlias or 1110264790Sbapt // there must be an operation on the PHIs within the PHIs' value cycle 1111264790Sbapt // that causes a MayAlias. 1112264790Sbapt // Pretend the phis do not alias. 1113264790Sbapt AliasResult Alias = NoAlias; 1114264790Sbapt assert(AliasCache.count(Locs) && 1115264790Sbapt "There must exist an entry for the phi node"); 1116264790Sbapt AliasResult OrigAliasResult = AliasCache[Locs]; 1117264790Sbapt AliasCache[Locs] = NoAlias; 1118264790Sbapt 1119264790Sbapt for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1120264790Sbapt AliasResult ThisAlias = 1121264790Sbapt aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 1122264790Sbapt PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 1123264790Sbapt V2Size, V2TBAAInfo); 1124264790Sbapt Alias = MergeAliasResults(ThisAlias, Alias); 1125264790Sbapt if (Alias == MayAlias) 1126264790Sbapt break; 1127264790Sbapt } 1128264790Sbapt 1129264790Sbapt // Reset if speculation failed. 1130264790Sbapt if (Alias != NoAlias) 1131264790Sbapt AliasCache[Locs] = OrigAliasResult; 1132264790Sbapt 1133264790Sbapt return Alias; 1134264790Sbapt } 1135264790Sbapt 1136264790Sbapt SmallPtrSet<Value*, 4> UniqueSrc; 1137264790Sbapt SmallVector<Value*, 4> V1Srcs; 1138264790Sbapt for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1139264790Sbapt Value *PV1 = PN->getIncomingValue(i); 1140264790Sbapt if (isa<PHINode>(PV1)) 1141264790Sbapt // If any of the source itself is a PHI, return MayAlias conservatively 1142264790Sbapt // to avoid compile time explosion. The worst possible case is if both 1143264790Sbapt // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1144264790Sbapt // and 'n' are the number of PHI sources. 1145264790Sbapt return MayAlias; 1146264790Sbapt if (UniqueSrc.insert(PV1)) 1147264790Sbapt V1Srcs.push_back(PV1); 1148264790Sbapt } 1149264790Sbapt 1150264790Sbapt AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 1151264790Sbapt V1Srcs[0], PNSize, PNTBAAInfo); 1152264790Sbapt // Early exit if the check of the first PHI source against V2 is MayAlias. 1153264790Sbapt // Other results are not possible. 1154264790Sbapt if (Alias == MayAlias) 1155264790Sbapt return MayAlias; 1156264790Sbapt 1157264790Sbapt // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1158264790Sbapt // NoAlias / MustAlias. Otherwise, returns MayAlias. 1159264790Sbapt for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1160264790Sbapt Value *V = V1Srcs[i]; 1161264790Sbapt 1162264790Sbapt AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 1163264790Sbapt V, PNSize, PNTBAAInfo); 1164264790Sbapt Alias = MergeAliasResults(ThisAlias, Alias); 1165264790Sbapt if (Alias == MayAlias) 1166264790Sbapt break; 1167264790Sbapt } 1168264790Sbapt 1169264790Sbapt return Alias; 1170264790Sbapt} 1171264790Sbapt 1172264790Sbapt// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 1173264790Sbapt// such as array references. 1174264790Sbapt// 1175264790SbaptAliasAnalysis::AliasResult 1176264790SbaptBasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 1177264790Sbapt const MDNode *V1TBAAInfo, 1178264790Sbapt const Value *V2, uint64_t V2Size, 1179264790Sbapt const MDNode *V2TBAAInfo) { 1180264790Sbapt // If either of the memory references is empty, it doesn't matter what the 1181264790Sbapt // pointer values are. 1182264790Sbapt if (V1Size == 0 || V2Size == 0) 1183264790Sbapt return NoAlias; 1184264790Sbapt 1185264790Sbapt // Strip off any casts if they exist. 1186264790Sbapt V1 = V1->stripPointerCasts(); 1187264790Sbapt V2 = V2->stripPointerCasts(); 1188264790Sbapt 1189264790Sbapt // Are we checking for alias of the same value? 1190264790Sbapt if (V1 == V2) return MustAlias; 1191264790Sbapt 1192264790Sbapt if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1193264790Sbapt return NoAlias; // Scalars cannot alias each other 1194264790Sbapt 1195264790Sbapt // Figure out what objects these things are pointing to if we can. 1196264790Sbapt const Value *O1 = GetUnderlyingObject(V1, TD); 1197264790Sbapt const Value *O2 = GetUnderlyingObject(V2, TD); 1198264790Sbapt 1199264790Sbapt // Null values in the default address space don't point to any object, so they 1200264790Sbapt // don't alias any other pointer. 1201264790Sbapt if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1202264790Sbapt if (CPN->getType()->getAddressSpace() == 0) 1203264790Sbapt return NoAlias; 1204264790Sbapt if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1205264790Sbapt if (CPN->getType()->getAddressSpace() == 0) 1206264790Sbapt return NoAlias; 1207264790Sbapt 1208264790Sbapt if (O1 != O2) { 1209264790Sbapt // If V1/V2 point to two different objects we know that we have no alias. 1210264790Sbapt if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1211264790Sbapt return NoAlias; 1212264790Sbapt 1213264790Sbapt // Constant pointers can't alias with non-const isIdentifiedObject objects. 1214264790Sbapt if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1215264790Sbapt (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1216264790Sbapt return NoAlias; 1217264790Sbapt 1218264790Sbapt // Function arguments can't alias with things that are known to be 1219264790Sbapt // unambigously identified at the function level. 1220264790Sbapt if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || 1221264790Sbapt (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) 1222264790Sbapt return NoAlias; 1223264790Sbapt 1224264790Sbapt // Most objects can't alias null. 1225264790Sbapt if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1226264790Sbapt (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1227264790Sbapt return NoAlias; 1228264790Sbapt 1229264790Sbapt // If one pointer is the result of a call/invoke or load and the other is a 1230264790Sbapt // non-escaping local object within the same function, then we know the 1231264790Sbapt // object couldn't escape to a point where the call could return it. 1232264790Sbapt // 1233264790Sbapt // Note that if the pointers are in different functions, there are a 1234264790Sbapt // variety of complications. A call with a nocapture argument may still 1235264790Sbapt // temporary store the nocapture argument's value in a temporary memory 1236264790Sbapt // location if that memory location doesn't escape. Or it may pass a 1237264790Sbapt // nocapture value to other functions as long as they don't capture it. 1238264790Sbapt if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1239264790Sbapt return NoAlias; 1240264790Sbapt if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1241264790Sbapt return NoAlias; 1242264790Sbapt } 1243264790Sbapt 1244264790Sbapt // If the size of one access is larger than the entire object on the other 1245264790Sbapt // side, then we know such behavior is undefined and can assume no alias. 1246272955Srodrigc if (TD) 1247264790Sbapt if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || 1248264790Sbapt (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) 1249264790Sbapt return NoAlias; 1250264790Sbapt 1251264790Sbapt // Check the cache before climbing up use-def chains. This also terminates 1252264790Sbapt // otherwise infinitely recursive queries. 1253264790Sbapt LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 1254264790Sbapt Location(V2, V2Size, V2TBAAInfo)); 1255264790Sbapt if (V1 > V2) 1256264790Sbapt std::swap(Locs.first, Locs.second); 1257264790Sbapt std::pair<AliasCacheTy::iterator, bool> Pair = 1258264790Sbapt AliasCache.insert(std::make_pair(Locs, MayAlias)); 1259264790Sbapt if (!Pair.second) 1260264790Sbapt return Pair.first->second; 1261264790Sbapt 1262264790Sbapt // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1263264790Sbapt // GEP can't simplify, we don't even look at the PHI cases. 1264264790Sbapt if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1265264790Sbapt std::swap(V1, V2); 1266264790Sbapt std::swap(V1Size, V2Size); 1267264790Sbapt std::swap(O1, O2); 1268264790Sbapt std::swap(V1TBAAInfo, V2TBAAInfo); 1269264790Sbapt } 1270264790Sbapt if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1271264790Sbapt AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); 1272264790Sbapt if (Result != MayAlias) return AliasCache[Locs] = Result; 1273264790Sbapt } 1274264790Sbapt 1275264790Sbapt if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1276264790Sbapt std::swap(V1, V2); 1277264790Sbapt std::swap(V1Size, V2Size); 1278264790Sbapt std::swap(V1TBAAInfo, V2TBAAInfo); 1279264790Sbapt } 1280264790Sbapt if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 1281264790Sbapt AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 1282264790Sbapt V2, V2Size, V2TBAAInfo); 1283264790Sbapt if (Result != MayAlias) return AliasCache[Locs] = Result; 1284264790Sbapt } 1285264790Sbapt 1286264790Sbapt if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1287264790Sbapt std::swap(V1, V2); 1288264790Sbapt std::swap(V1Size, V2Size); 1289264790Sbapt std::swap(V1TBAAInfo, V2TBAAInfo); 1290264790Sbapt } 1291264790Sbapt if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 1292264790Sbapt AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 1293264790Sbapt V2, V2Size, V2TBAAInfo); 1294264790Sbapt if (Result != MayAlias) return AliasCache[Locs] = Result; 1295264790Sbapt } 1296264790Sbapt 1297272955Srodrigc // If both pointers are pointing into the same object and one of them 1298272955Srodrigc // accesses is accessing the entire object, then the accesses must 1299264790Sbapt // overlap in some way. 1300264790Sbapt if (TD && O1 == O2) 1301264790Sbapt if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || 1302264790Sbapt (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) 1303264790Sbapt return AliasCache[Locs] = PartialAlias; 1304264790Sbapt 1305264790Sbapt AliasResult Result = 1306264790Sbapt AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 1307264790Sbapt Location(V2, V2Size, V2TBAAInfo)); 1308264790Sbapt return AliasCache[Locs] = Result; 1309264790Sbapt} 1310264790Sbapt