119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file defines the primary stateless implementation of the 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Alias Analysis interface that implements identities (two different 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// globals cannot alias, etc), but does no stateful analysis. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/AliasAnalysis.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/Passes.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/DerivedTypes.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/GlobalAlias.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/GlobalVariable.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/IntrinsicInst.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/LLVMContext.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Operator.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/CaptureTracking.h" 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/MemoryBuiltins.h" 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/InstructionSimplify.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/ValueTracking.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetData.h" 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetLibraryInfo.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallVector.h" 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/ErrorHandling.h" 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/GetElementPtrTypeIterator.h" 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <algorithm> 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Useful predicates 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isKnownNonNull - Return true if we know that the specified value is never 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// null. 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool isKnownNonNull(const Value *V) { 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Alloca never returns null, malloc might. 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<AllocaInst>(V)) return true; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A byval argument is never null. 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Argument *A = dyn_cast<Argument>(V)) 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return A->hasByValAttr(); 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Global values are not null unless extern weak. 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !GV->hasExternalWeakLinkage(); 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// object that never escapes from the function. 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool isNonEscapingLocalObject(const Value *V) { 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a local allocation, check to see if it escapes. 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<AllocaInst>(V) || isNoAliasCall(V)) 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Set StoreCaptures to True so that we can assume in our callers that the 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // pointer is not the result of a load instruction. Currently 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // PointerMayBeCaptured doesn't have any special analysis for the 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // StoreCaptures=false case; if it did, our callers could be refined to be 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // more precise. 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is an argument that corresponds to a byval or noalias argument, 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // then it has not escaped before entering the function. Check if it escapes 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // inside the function. 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Argument *A = dyn_cast<Argument>(V)) 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (A->hasByValAttr() || A->hasNoAliasAttr()) { 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't bother analyzing arguments already known not to escape. 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (A->hasNoCaptureAttr()) 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isEscapeSource - Return true if the pointer is one which would have 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// been considered an escape by isNonEscapingLocalObject. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool isEscapeSource(const Value *V) { 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The load case works because isNonEscapingLocalObject considers all 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // stores to be escapes (it passes true for the StoreCaptures argument 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to PointerMayBeCaptured). 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<LoadInst>(V)) 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// getObjectSize - Return the size of the object specified by V, or 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// UnknownSize if unknown. 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic uint64_t getObjectSize(const Value *V, const TargetData &TD) { 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *AccessTy; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GV->hasDefinitiveInitializer()) 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AccessTy = GV->getType()->getElementType(); 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!AI->isArrayAllocation()) 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AccessTy = AI->getType()->getElementType(); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (const CallInst* CI = extractMallocCall(V)) { 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isArrayMalloc(V, &TD)) 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The size is the argument to the malloc call. 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return C->getZExtValue(); 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (const Argument *A = dyn_cast<Argument>(V)) { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (A->hasByValAttr()) 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AccessTy = cast<PointerType>(A->getType())->getElementType(); 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AccessTy->isSized()) 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return TD.getTypeAllocSize(AccessTy); 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::UnknownSize; 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// isObjectSmallerThan - Return true if we can prove that the object specified 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// by V is smaller than Size. 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData &TD) { 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t ObjectSize = getObjectSize(V, TD); 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// isObjectSize - Return true if we can prove that the object specified 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// by V has size Size. 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool isObjectSize(const Value *V, uint64_t Size, 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData &TD) { 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t ObjectSize = getObjectSize(V, TD); 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// GetElementPtr Instruction Decomposition and Analysis 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum ExtensionKind { 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EK_NotExtended, 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EK_SignExt, 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EK_ZeroExt 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct VariableGEPIndex { 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V; 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtensionKind Extension; 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int64_t Scale; 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// GetLinearExpression - Analyze the specified value as a linear expression: 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// "A*V + B", where A and B are constant integers. Return the scale and offset 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// values as APInts and return V as a Value*, and return whether we looked 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// through any sign or zero extends. The incoming Value is known to have 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntegerType and it may already be sign or zero extended. 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Note that this looks through extends, so the high bits may not be 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// represented in the result. 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtensionKind &Extension, 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData &TD, unsigned Depth) { 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(V->getType()->isIntegerTy() && "Not an integer value"); 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Limit our recursion depth. 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Depth == 6) { 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = 1; 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = 0; 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman switch (BOp->getOpcode()) { 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman default: break; 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case Instruction::Or: 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // analyze it. 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FALL THROUGH. 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case Instruction::Add: 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TD, Depth+1); 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset += RHSC->getValue(); 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case Instruction::Mul: 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TD, Depth+1); 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset *= RHSC->getValue(); 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale *= RHSC->getValue(); 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case Instruction::Shl: 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TD, Depth+1); 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset <<= RHSC->getValue().getLimitedValue(); 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale <<= RHSC->getValue().getLimitedValue(); 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Since GEP indices are sign extended anyway, we don't care about the high 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // bits of a sign or zero extended value - just scales and offsets. The 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // extensions have to be consistent though. 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *CastOp = cast<CastInst>(V)->getOperand(0); 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OldWidth = Scale.getBitWidth(); 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = Scale.trunc(SmallWidth); 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = Offset.trunc(SmallWidth); 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TD, Depth+1); 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = Scale.zext(OldWidth); 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = Offset.zext(OldWidth); 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Result; 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = 1; 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = 0; 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// into a base pointer with a constant offset and a number of scaled symbolic 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// offsets. 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the VarIndices vector) are Value*'s that are known to be scaled by the 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// specified amount, but which may have other unrepresented high bits. As such, 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the gep cannot necessarily be reconstructed from its decomposed form. 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// When TargetData is around, this function is capable of analyzing everything 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// that GetUnderlyingObject can look through. When not, it just looks 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// through pointer casts. 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic const Value * 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVectorImpl<VariableGEPIndex> &VarIndices, 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData *TD) { 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Limit recursion depth to limit compile time in crazy cases. 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned MaxLookup = 6; 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BaseOffs = 0; 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman do { 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See if this is a bitcast or GEP. 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Operator *Op = dyn_cast<Operator>(V); 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Op == 0) { 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The only non-operator case we can handle are GlobalAliases. 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GA->mayBeOverridden()) { 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GA->getAliasee(); 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Op->getOpcode() == Instruction::BitCast) { 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Op->getOperand(0); 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GEPOp == 0) { 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it's not a GEP, hand it off to SimplifyInstruction to see if it 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // can come up with something. This matches what GetUnderlyingObject does. 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const Instruction *I = dyn_cast<Instruction>(V)) 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: Get a DominatorTree and use it here. 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const Value *Simplified = 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Simplified; 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't attempt to analyze GEPs over unsized objects. 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!cast<PointerType>(GEPOp->getOperand(0)->getType()) 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ->getElementType()->isSized()) 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we are lacking TargetData information, we can't compute the offets of 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // elements computed by GEPs. However, we can handle bitcast equivalent 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // GEPs. 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TD == 0) { 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GEPOp->hasAllZeroIndices()) 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GEPOp->getOperand(0); 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman gep_type_iterator GTI = gep_type_begin(GEPOp); 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (User::const_op_iterator I = GEPOp->op_begin()+1, 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = GEPOp->op_end(); I != E; ++I) { 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Index = *I; 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute the (potentially symbolic) offset in bytes for this index. 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For a struct, add the member offset. 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (FieldNo == 0) continue; 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For an array/pointer, add the element offset, explicitly scaled. 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CIdx->isZero()) continue; 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Scale = TD->getTypeAllocSize(*GTI); 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtensionKind Extension = EK_NotExtended; 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the integer type is smaller than the pointer size, it is implicitly 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // sign extended to pointer size. 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth(); 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TD->getPointerSizeInBits() > Width) 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Extension = EK_SignExt; 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman APInt IndexScale(Width, 0), IndexOffset(Width, 0); 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman *TD, 0); 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BaseOffs += IndexOffset.getSExtValue()*Scale; 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale *= IndexScale.getSExtValue(); 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we already had an occurrence of this index variable, merge this 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // scale into it. For example, we want to handle: 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A[x][x] -> x*16 + x*4 -> x*20 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This also ensures that 'x' only appears in the index list once. 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VarIndices[i].V == Index && 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VarIndices[i].Extension == Extension) { 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale += VarIndices[i].Scale; 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VarIndices.erase(VarIndices.begin()+i); 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure that we have a scale that makes sense for this target's 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // pointer size. 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) { 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale <<= ShiftBits; 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = (int64_t)Scale >> ShiftBits; 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Scale) { 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VariableGEPIndex Entry = {Index, Extension, 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static_cast<int64_t>(Scale)}; 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VarIndices.push_back(Entry); 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Analyze the base pointer next. 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GEPOp->getOperand(0); 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } while (--MaxLookup); 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the chain of expressions is too deep, just return early. 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return V; 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// GetIndexDifference - Dest and Src are the variable indices from two 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// difference between the two pointers. 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const SmallVectorImpl<VariableGEPIndex> &Src) { 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Src.empty()) return; 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Src.size(); i != e; ++i) { 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V = Src[i].V; 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtensionKind Extension = Src[i].Extension; 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int64_t Scale = Src[i].Scale; 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find V in Dest. This is N^2, but pointer indices almost never have more 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // than a few variable indexes. 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Dest[j].V != V || Dest[j].Extension != Extension) continue; 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we found it, subtract off Scale V's from the entry in Dest. If it 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // goes to zero, remove the entry. 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Dest[j].Scale != Scale) 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dest[j].Scale -= Scale; 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dest.erase(Dest.begin()+j); 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Scale = 0; 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we didn't consume this entry, add it to the end of the Dest list. 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Scale) { 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VariableGEPIndex Entry = { V, Extension, -Scale }; 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dest.push_back(Entry); 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// BasicAliasAnalysis Pass 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic const Function *getParent(const Value *V) { 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Instruction *inst = dyn_cast<Instruction>(V)) 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return inst->getParent()->getParent(); 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Argument *arg = dyn_cast<Argument>(V)) 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return arg->getParent(); 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NULL; 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool notDifferentParent(const Value *O1, const Value *O2) { 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Function *F1 = getParent(O1); 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Function *F2 = getParent(O2); 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !F1 || !F2 || F1 == F2; 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// BasicAliasAnalysis - This is the primary alias analysis implementation. 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Class identification, replacement for typeinfo 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicAliasAnalysis() : ImmutablePass(ID), 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // AliasCache rarely has more than 1 or 2 elements, 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // so start it off fairly small so that clear() 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // doesn't have to tromp through 64 (the default) 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // elements on each alias query. This really wants 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // something like a SmallDenseMap. 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasCache(8) { 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void initializePass() { 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InitializeAliasAnalysis(this); 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<AliasAnalysis>(); 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<TargetLibraryInfo>(); 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual AliasResult alias(const Location &LocA, 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Location &LocB) { 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "BasicAliasAnalysis doesn't support interprocedural queries."); 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 48119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LocB.Ptr, LocB.Size, LocB.TBAATag); 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasCache.clear(); 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Alias; 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Location &Loc); 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ImmutableCallSite CS2) { 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The AliasAnalysis base class has some smarts, lets use them. 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return AliasAnalysis::getModRefInfo(CS1, CS2); 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// pointsToConstantMemory - Chase pointers until we find a (constant 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// global) or not. 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getModRefBehavior - Return the behavior when calling the given 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// call site. 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getModRefBehavior - Return the behavior when calling the given function. 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// For use when the call site is not known. 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ModRefBehavior getModRefBehavior(const Function *F); 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getAdjustedAnalysisPointer - This method is used when a pass implements 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// an analysis interface through multiple inheritance. If needed, it 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// should override this to adjust the this pointer as needed for the 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// specified pass info. 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void *getAdjustedAnalysisPointer(const void *ID) { 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ID == &AliasAnalysis::ID) 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return (AliasAnalysis*)this; 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return this; 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // AliasCache - Track alias queries to guard against recursion. 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef std::pair<Location, Location> LocPair; 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef DenseMap<LocPair, AliasResult> AliasCacheTy; 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasCacheTy AliasCache; 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Visited - Track instructions visited by pointsToConstantMemory. 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<const Value*, 16> Visited; 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction against another. 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo, 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *UnderlyingV1, const Value *UnderlyingV2); 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction against another. 53519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *PNTBAAInfo, 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo); 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// aliasSelect - Disambiguate a Select instruction against another value. 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *SITBAAInfo, 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo); 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V1TBAATag, 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAATag); 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End of anonymous namespace 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Register this pass... 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar BasicAliasAnalysis::ID = 0; 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Basic Alias Analysis (stateless AA impl)", 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, true, false) 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Basic Alias Analysis (stateless AA impl)", 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, true, false) 56219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanImmutablePass *llvm::createBasicAliasAnalysisPass() { 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new BasicAliasAnalysis(); 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// pointsToConstantMemory - Returns whether the given pointer value 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// points to memory that is local to the function, with global constants being 57019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// considered local to all functions. 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool 57219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Visited.empty() && "Visited must be cleared after use!"); 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned MaxLookup = 8; 57619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<const Value *, 16> Worklist; 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Worklist.push_back(Loc.Ptr); 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman do { 57919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Visited.insert(V)) { 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Visited.clear(); 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 58419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // An alloca instruction defines local memory. 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OrLocal && isa<AllocaInst>(V)) 58719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A global constant counts as local memory for our purposes. 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Note: this doesn't require GV to be "ODR" because it isn't legal for a 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // global to be marked constant in some modules and non-constant in 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // others. GV may even be a declaration, not a definition. 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GV->isConstant()) { 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Visited.clear(); 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 60019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If both select values point to local memory, then so does the select. 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Worklist.push_back(SI->getTrueValue()); 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Worklist.push_back(SI->getFalseValue()); 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If all values incoming to a phi node point to local memory, then so does 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the phi. 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const PHINode *PN = dyn_cast<PHINode>(V)) { 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't bother inspecting phi nodes with many operands. 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PN->getNumIncomingValues() > MaxLookup) { 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Visited.clear(); 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Worklist.push_back(PN->getIncomingValue(i)); 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 62119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise be conservative. 62219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Visited.clear(); 62319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } while (!Worklist.empty() && --MaxLookup); 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Visited.clear(); 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Worklist.empty(); 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getModRefBehavior - Return the behavior when calling the given call site. 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::ModRefBehavior 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CS.doesNotAccessMemory()) 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Can't do better than this. 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DoesNotAccessMemory; 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ModRefBehavior Min = UnknownModRefBehavior; 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the callsite knows it only reads memory, don't return worse 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // than that. 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CS.onlyReadsMemory()) 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Min = OnlyReadsMemory; 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The AliasAnalysis base class has some smarts, lets use them. 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getModRefBehavior - Return the behavior when calling the given function. 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// For use when the call site is not known. 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::ModRefBehavior 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicAliasAnalysis::getModRefBehavior(const Function *F) { 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the function declares it doesn't access memory, we can't do better. 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (F->doesNotAccessMemory()) 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DoesNotAccessMemory; 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For intrinsics, we can check the table. 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unsigned iid = F->getIntrinsicID()) { 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define GET_INTRINSIC_MODREF_BEHAVIOR 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Intrinsics.gen" 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#undef GET_INTRINSIC_MODREF_BEHAVIOR 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModRefBehavior Min = UnknownModRefBehavior; 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the function declares it only reads memory, go with that. 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (F->onlyReadsMemory()) 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = OnlyReadsMemory; 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise be conservative. 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getModRefInfo - Check to see if the specified callsite can clobber the 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// specified memory object. Since we only look at local properties of this 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// function, we really can't say much about this query. We do, however, use 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// simple "address taken" analysis on local objects. 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::ModRefResult 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Location &Loc) { 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "AliasAnalysis query involving multiple functions!"); 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a tail call and Loc.Ptr points to a stack location, we know that 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the tail call cannot access or modify the local stack. 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We cannot exclude byval arguments here; these belong to the caller of 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the current function not to the current function, and a tail callee 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // may reference them. 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<AllocaInst>(Object)) 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CI->isTailCall()) 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the pointer is to a locally allocated object that does not escape, 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // then the call can not mod/ref the pointer unless the call takes the pointer 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // as an argument, and itself doesn't capture it. 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<Constant>(Object) && CS.getInstruction() != Object && 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isNonEscapingLocalObject(Object)) { 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool PassedAsArg = false; 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ArgNo = 0; 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CI != CE; ++CI, ++ArgNo) { 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Only look at the no-capture or byval pointer arguments. If this 70619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // pointer were passed to arguments that were neither of these, then it 70719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // couldn't be no-capture. 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(*CI)->getType()->isPointerTy() || 70919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (!CS.paramHasAttr(ArgNo+1, Attribute::NoCapture) && 71019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !CS.paramHasAttr(ArgNo+1, Attribute::ByVal))) 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 71319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a no-capture pointer argument, see if we can tell that it 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is impossible to alias the pointer we're checking. If not, we have to 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // assume that the call could touch the pointer, even though it doesn't 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // escape. 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isNoAlias(Location(*CI), Location(Object))) { 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PassedAsArg = true; 719894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!PassedAsArg) 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModRefResult Min = ModRef; 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 730894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Finally, handle specific knowledge of intrinsics. 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 732894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (II != 0) 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (II->getIntrinsicID()) { 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: break; 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::memcpy: 736894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::memmove: { 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Len = UnknownSize; 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Len = LenCI->getZExtValue(); 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Dest = II->getArgOperand(0); 741894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Src = II->getArgOperand(1); 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the source dest, then it doesn't modref the loc. 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(Dest, Len), Loc)) { 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(Src, Len), Loc)) 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the dest, then worst case it reads the loc. 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = Ref; 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (isNoAlias(Location(Src, Len), Loc)) { 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the source, then worst case it mutates the loc. 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = Mod; 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::memset: 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Since memset is 'accesses arguments' only, the AliasAnalysis base class 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will handle it for the variable length case. 757894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Len = LenCI->getZExtValue(); 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Dest = II->getArgOperand(0); 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(Dest, Len), Loc)) 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We know that memset doesn't load anything. 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = Mod; 765894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::lifetime_start: 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::lifetime_end: 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::invariant_start: { 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t PtrSize = 770894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(II->getArgOperand(1), 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PtrSize, 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman II->getMetadata(LLVMContext::MD_tbaa)), 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Loc)) 775894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 776894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 777894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 778894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Intrinsic::invariant_end: { 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t PtrSize = 780894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(II->getArgOperand(2), 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PtrSize, 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman II->getMetadata(LLVMContext::MD_tbaa)), 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Loc)) 785894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoModRef; 786894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 787894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //case Intrinsic::arm_neon_vld1: { 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // // LLVM's vld1 and vst1 intrinsics currently only support a single 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // // vector register. 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // uint64_t Size = 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 79319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // if (isNoAlias(Location(II->getArgOperand(0), Size, 79419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // II->getMetadata(LLVMContext::MD_tbaa)), 79519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Loc)) 79619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // return NoModRef; 79719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // break; 79819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //} 79919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //case Intrinsic::arm_neon_vst1: { 80019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // uint64_t Size = 80119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 80219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // if (isNoAlias(Location(II->getArgOperand(0), Size, 80319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // II->getMetadata(LLVMContext::MD_tbaa)), 80419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Loc)) 80519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // return NoModRef; 80619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // break; 80719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //} 808894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 809894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 81019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We can bound the aliasing properties of memset_pattern16 just as we can 81119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // for memcpy/memset. This is particularly important because the 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 81319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // whenever possible. 81419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (TLI.has(LibFunc::memset_pattern16) && 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CS.getCalledFunction() && 81619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CS.getCalledFunction()->getName() == "memset_pattern16") { 81719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Function *MS = CS.getCalledFunction(); 81819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FunctionType *MemsetType = MS->getFunctionType(); 81919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 82019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<PointerType>(MemsetType->getParamType(0)) && 82119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<PointerType>(MemsetType->getParamType(1)) && 82219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<IntegerType>(MemsetType->getParamType(2))) { 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Len = UnknownSize; 82419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 82519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Len = LenCI->getZExtValue(); 82619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *Dest = CS.getArgument(0); 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *Src = CS.getArgument(1); 82819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the source dest, then it doesn't modref the loc. 82919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(Dest, Len), Loc)) { 83019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Always reads 16 bytes of the source. 83119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isNoAlias(Location(Src, 16), Loc)) 83219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NoModRef; 83319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the dest, then worst case it reads the loc. 83419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = Ref; 83519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Always reads 16 bytes of the source. 83619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (isNoAlias(Location(Src, 16), Loc)) { 83719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it can't overlap the source, then worst case it mutates the loc. 83819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Min = Mod; 83919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 840894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 841894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 84219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 84319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The AliasAnalysis base class has some smarts, lets use them. 84419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 845894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 846894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 847894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 848894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// against another pointer. We know that V1 is a GEP, but we don't know 84919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 850894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// UnderlyingV2 is the same for V2. 851894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 852894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::AliasResult 85319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 85419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 85519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo, 856894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *UnderlyingV1, 857894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *UnderlyingV2) { 858894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t GEP1BaseOffset; 85919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 860894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 861894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we have two gep instructions with must-alias'ing base pointers, figure 862894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // out if the indexes to the GEP tell us anything about the derived pointer. 863894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 864894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do the base pointers alias? 86519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 86619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UnderlyingV2, UnknownSize, 0); 867894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 868894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we get a No or May, then return it immediately, no amount of analysis 869894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will improve this situation. 870894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BaseAlias != MustAlias) return BaseAlias; 871894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 872894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we have a MustAlias. Since the base pointers alias each other 873894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // exactly, see if the computed offset from the common pointer tells us 874894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // about the relation of the resulting pointer. 875894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *GEP1BasePtr = 876894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 877894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 878894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t GEP2BaseOffset; 87919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 880894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *GEP2BasePtr = 881894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 882894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 883894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If DecomposeGEPExpression isn't able to look all the way through the 884894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // addressing operation, we must not have TD and this is too complex for us 885894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to handle without it. 886894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 887894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(TD == 0 && 88819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 889894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 890894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 891894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 892894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Subtract the GEP2 pointer from the GEP1 pointer to find out their 893894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // symbolic difference. 894894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GEP1BaseOffset -= GEP2BaseOffset; 895894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 896894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 897894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 898894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if these two pointers are related by the getelementptr 899894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction. If one pointer is a GEP with a non-zero index of the other 900894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // pointer, we know they cannot alias. 901894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 902894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If both accesses are unknown size, we can't do anything useful here. 903894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1Size == UnknownSize && V2Size == UnknownSize) 904894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 905894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 90719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2, V2Size, V2TBAAInfo); 908894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (R != MustAlias) 909894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If V2 may alias GEP base pointer, conservatively returns MayAlias. 910894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If V2 is known not to alias GEP base pointer, then the two values 911894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // cannot alias per GEP semantics: "A pointer value formed from a 912894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getelementptr instruction is associated with the addresses associated 913894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // with the first operand of the getelementptr". 914894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return R; 915894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 916894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *GEP1BasePtr = 917894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 918894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 919894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If DecomposeGEPExpression isn't able to look all the way through the 920894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // addressing operation, we must not have TD and this is too complex for us 921894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to handle without it. 922894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (GEP1BasePtr != UnderlyingV1) { 923894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(TD == 0 && 92419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 925894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 926894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 927894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 928894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 929894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In the two GEP Case, if there is no difference in the offsets of the 930894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // computed pointers, the resultant pointers are a must alias. This 931894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // hapens when we have two lexically identical GEP's (for example). 932894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 933894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 934894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // must aliases the GEP, the end result is a must alias also. 935894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 936894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MustAlias; 937894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 93819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there is a constant difference between the pointers, but the difference 93919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // is less than the size of the associated memory object, then we know 94019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that the objects are partially overlapping. If the difference is 94119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // greater, we know they do not overlap. 94219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 94319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GEP1BaseOffset >= 0) { 94419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V2Size != UnknownSize) { 94519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((uint64_t)GEP1BaseOffset < V2Size) 94619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return PartialAlias; 94719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NoAlias; 94819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 94919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 95019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V1Size != UnknownSize) { 95119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (-(uint64_t)GEP1BaseOffset < V1Size) 95219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return PartialAlias; 95319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NoAlias; 95419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 95519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 95619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 95719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 95819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try to distinguish something like &A[i][1] against &A[42][0]. 95919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Grab the least significant bit set in any of the scales. 96019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GEP1VariableIndices.empty()) { 96119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Modulo = 0; 96219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 96319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 96419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Modulo = Modulo ^ (Modulo & (Modulo - 1)); 96519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We can compute the difference between the two addresses 96719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // mod Modulo. Check whether that difference guarantees that the 96819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // two locations do not alias. 96919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 97019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V1Size != UnknownSize && V2Size != UnknownSize && 97119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 972894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 973894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 97419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 97519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Statically, we can see that the base objects are the same, but the 97619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // pointers have dynamic offsets which we can't resolve. And none of our 97719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // little tricks above worked. 97819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 97919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 98019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // practical effect of this is protecting TBAA in the case of dynamic 98119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // indices into arrays of unions. An alternative way to solve this would 98219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // be to have clang emit extra metadata for unions and/or union accesses. 98319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A union-specific solution wouldn't handle the problem for malloc'd 98419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // memory however. 98519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return PartialAlias; 98619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 98719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 98819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic AliasAnalysis::AliasResult 98919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanMergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 99019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the results agree, take it. 99119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (A == B) 99219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return A; 99319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A mix of PartialAlias and MustAlias is PartialAlias. 99419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 99519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 99619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::PartialAlias; 99719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, we don't know anything. 99819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasAnalysis::MayAlias; 999894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1000894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1001894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 1002894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instruction against another. 1003894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::AliasResult 100419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 100519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *SITBAAInfo, 100619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 100719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo) { 1008894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the values are Selects with the same condition, we can do a more precise 1009894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // check: just check for aliases between the values on corresponding arms. 1010894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1011894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SI->getCondition() == SI2->getCondition()) { 1012894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult Alias = 101319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 101419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI2->getTrueValue(), V2Size, V2TBAAInfo); 1015894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Alias == MayAlias) 1016894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 1017894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult ThisAlias = 101819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 101919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI2->getFalseValue(), V2Size, V2TBAAInfo); 102019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MergeAliasResults(ThisAlias, Alias); 1021894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1022894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1023894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If both arms of the Select node NoAlias or MustAlias V2, then returns 1024894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // NoAlias / MustAlias. Otherwise, returns MayAlias. 1025894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult Alias = 102619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 1027894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Alias == MayAlias) 1028894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 1029894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1030894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult ThisAlias = 103119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 103219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MergeAliasResults(ThisAlias, Alias); 1033894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1034894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1035894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 1036894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// against another. 1037894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::AliasResult 103819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 103919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *PNTBAAInfo, 104019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 104119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo) { 1042894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the values are PHIs in the same block, we can do a more precise 1043894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // as well as efficient check: just check for aliases between the values 1044894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // on corresponding edges. 1045894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1046894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN2->getParent() == PN->getParent()) { 1047894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult Alias = 104819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo, 1049894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 105019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2Size, V2TBAAInfo); 1051894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Alias == MayAlias) 1052894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 1053894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 1054894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasResult ThisAlias = 105519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 1056894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 105719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2Size, V2TBAAInfo); 105819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Alias = MergeAliasResults(ThisAlias, Alias); 105919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Alias == MayAlias) 106019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 1061894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1062894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Alias; 1063894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1064894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1065894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<Value*, 4> UniqueSrc; 1066894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Value*, 4> V1Srcs; 1067894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1068894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *PV1 = PN->getIncomingValue(i); 1069894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(PV1)) 1070894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If any of the source itself is a PHI, return MayAlias conservatively 1071894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to avoid compile time explosion. The worst possible case is if both 1072894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1073894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and 'n' are the number of PHI sources. 1074894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 1075894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UniqueSrc.insert(PV1)) 1076894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V1Srcs.push_back(PV1); 1077894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1078894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 107919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 108019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V1Srcs[0], PNSize, PNTBAAInfo); 1081894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Early exit if the check of the first PHI source against V2 is MayAlias. 1082894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Other results are not possible. 1083894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Alias == MayAlias) 1084894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MayAlias; 1085894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1086894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1087894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // NoAlias / MustAlias. Otherwise, returns MayAlias. 1088894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1089894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = V1Srcs[i]; 1090894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 109219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V, PNSize, PNTBAAInfo); 109319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Alias = MergeAliasResults(ThisAlias, Alias); 109419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Alias == MayAlias) 109519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 1096894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1097894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1098894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Alias; 1099894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 1102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// such as array references. 1103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 1104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAliasAnalysis::AliasResult 110519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 110619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V1TBAAInfo, 110719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *V2, uint64_t V2Size, 110819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MDNode *V2TBAAInfo) { 1109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If either of the memory references is empty, it doesn't matter what the 1110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // pointer values are. 1111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1Size == 0 || V2Size == 0) 1112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Strip off any casts if they exist. 1115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V1 = V1->stripPointerCasts(); 1116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V2 = V2->stripPointerCasts(); 1117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Are we checking for alias of the same value? 1119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1 == V2) return MustAlias; 1120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; // Scalars cannot alias each other 1123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out what objects these things are pointing to if we can. 112519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *O1 = GetUnderlyingObject(V1, TD); 112619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Value *O2 = GetUnderlyingObject(V2, TD); 1127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Null values in the default address space don't point to any object, so they 1129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // don't alias any other pointer. 1130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CPN->getType()->getAddressSpace() == 0) 1132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CPN->getType()->getAddressSpace() == 0) 1135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (O1 != O2) { 1138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If V1/V2 point to two different objects we know that we have no alias. 1139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Constant pointers can't alias with non-const isIdentifiedObject objects. 1143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Arguments can't alias with local allocations or noalias calls 1148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // in the same function. 1149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 1150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) 1151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Most objects can't alias null. 1154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If one pointer is the result of a call/invoke or load and the other is a 1159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // non-escaping local object within the same function, then we know the 1160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // object couldn't escape to a point where the call could return it. 1161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 1162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that if the pointers are in different functions, there are a 1163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // variety of complications. A call with a nocapture argument may still 1164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // temporary store the nocapture argument's value in a temporary memory 1165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // location if that memory location doesn't escape. Or it may pass a 1166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // nocapture value to other functions as long as they don't capture it. 1167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the size of one access is larger than the entire object on the other 1174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // side, then we know such behavior is undefined and can assume no alias. 1175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TD) 1176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD)) || 1177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD))) 1178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NoAlias; 1179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Check the cache before climbing up use-def chains. This also terminates 118119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // otherwise infinitely recursive queries. 118219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 118319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Location(V2, V2Size, V2TBAAInfo)); 118419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V1 > V2) 118519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::swap(Locs.first, Locs.second); 118619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<AliasCacheTy::iterator, bool> Pair = 118719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasCache.insert(std::make_pair(Locs, MayAlias)); 118819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Pair.second) 118919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Pair.first->second; 119019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // GEP can't simplify, we don't even look at the PHI cases. 1193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1, V2); 1195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1Size, V2Size); 1196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(O1, O2); 1197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 119819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 119919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, V2TBAAInfo, O1, O2); 120019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Result != MayAlias) return AliasCache[Locs] = Result; 120119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 1202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1, V2); 1205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1Size, V2Size); 1206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 120719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 120819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 120919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2, V2Size, V2TBAAInfo); 121019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Result != MayAlias) return AliasCache[Locs] = Result; 121119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 1212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1, V2); 1215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1Size, V2Size); 1216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 121719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 121819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 121919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2, V2Size, V2TBAAInfo); 122019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Result != MayAlias) return AliasCache[Locs] = Result; 122119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 1222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If both pointers are pointing into the same object and one of them 122419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // accesses is accessing the entire object, then the accesses must 122519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // overlap in some way. 122619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TD && O1 == O2) 122719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD)) || 122819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD))) 122919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasCache[Locs] = PartialAlias; 123019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 123119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasResult Result = 123219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 123319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Location(V2, V2Size, V2TBAAInfo)); 123419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasCache[Locs] = Result; 1235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1236