BasicAliasAnalysis.cpp [plain text]
#include "llvm/Analysis/Passes.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/Pass.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>
using namespace llvm;
const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
static bool isNonEscapingLocalObject(const Value *V) {
if (isa<AllocaInst>(V) || isNoAliasCall(V))
return !PointerMayBeCaptured(V, false, true);
if (const Argument *A = dyn_cast<Argument>(V))
if (A->hasByValAttr() || A->hasNoAliasAttr())
return !PointerMayBeCaptured(V, false, true);
return false;
}
static bool isEscapeSource(const Value *V) {
if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
return true;
if (isa<LoadInst>(V))
return true;
return false;
}
static uint64_t getObjectSize(const Value *V, const DataLayout &TD,
const TargetLibraryInfo &TLI,
bool RoundToAlign = false) {
uint64_t Size;
if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign))
return Size;
return AliasAnalysis::UnknownSize;
}
static bool isObjectSmallerThan(const Value *V, uint64_t Size,
const DataLayout &TD,
const TargetLibraryInfo &TLI) {
if (!isIdentifiedObject(V))
return false;
uint64_t ObjectSize = getObjectSize(V, TD, TLI, true);
return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size;
}
static bool isObjectSize(const Value *V, uint64_t Size,
const DataLayout &TD, const TargetLibraryInfo &TLI) {
uint64_t ObjectSize = getObjectSize(V, TD, TLI);
return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size;
}
static bool isIdentifiedFunctionLocal(const Value *V)
{
return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
}
namespace {
enum ExtensionKind {
EK_NotExtended,
EK_SignExt,
EK_ZeroExt
};
struct VariableGEPIndex {
const Value *V;
ExtensionKind Extension;
int64_t Scale;
bool operator==(const VariableGEPIndex &Other) const {
return V == Other.V && Extension == Other.Extension &&
Scale == Other.Scale;
}
bool operator!=(const VariableGEPIndex &Other) const {
return !operator==(Other);
}
};
}
static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
ExtensionKind &Extension,
const DataLayout &TD, unsigned Depth) {
assert(V->getType()->isIntegerTy() && "Not an integer value");
if (Depth == 6) {
Scale = 1;
Offset = 0;
return V;
}
if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
switch (BOp->getOpcode()) {
default: break;
case Instruction::Or:
if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD))
break;
case Instruction::Add:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
TD, Depth+1);
Offset += RHSC->getValue();
return V;
case Instruction::Mul:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
TD, Depth+1);
Offset *= RHSC->getValue();
Scale *= RHSC->getValue();
return V;
case Instruction::Shl:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
TD, Depth+1);
Offset <<= RHSC->getValue().getLimitedValue();
Scale <<= RHSC->getValue().getLimitedValue();
return V;
}
}
}
if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
(isa<ZExtInst>(V) && Extension != EK_SignExt)) {
Value *CastOp = cast<CastInst>(V)->getOperand(0);
unsigned OldWidth = Scale.getBitWidth();
unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
Scale = Scale.trunc(SmallWidth);
Offset = Offset.trunc(SmallWidth);
Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension,
TD, Depth+1);
Scale = Scale.zext(OldWidth);
Offset = Offset.zext(OldWidth);
return Result;
}
Scale = 1;
Offset = 0;
return V;
}
static const Value *
DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
SmallVectorImpl<VariableGEPIndex> &VarIndices,
const DataLayout *TD) {
unsigned MaxLookup = 6;
BaseOffs = 0;
do {
const Operator *Op = dyn_cast<Operator>(V);
if (Op == 0) {
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (!GA->mayBeOverridden()) {
V = GA->getAliasee();
continue;
}
}
return V;
}
if (Op->getOpcode() == Instruction::BitCast) {
V = Op->getOperand(0);
continue;
}
const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
if (GEPOp == 0) {
if (const Instruction *I = dyn_cast<Instruction>(V))
if (const Value *Simplified =
SimplifyInstruction(const_cast<Instruction *>(I), TD)) {
V = Simplified;
continue;
}
return V;
}
if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
return V;
if (TD == 0) {
if (!GEPOp->hasAllZeroIndices())
return V;
V = GEPOp->getOperand(0);
continue;
}
unsigned AS = GEPOp->getPointerAddressSpace();
gep_type_iterator GTI = gep_type_begin(GEPOp);
for (User::const_op_iterator I = GEPOp->op_begin()+1,
E = GEPOp->op_end(); I != E; ++I) {
Value *Index = *I;
if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
if (FieldNo == 0) continue;
BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo);
continue;
}
if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
if (CIdx->isZero()) continue;
BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue();
continue;
}
uint64_t Scale = TD->getTypeAllocSize(*GTI);
ExtensionKind Extension = EK_NotExtended;
unsigned Width = Index->getType()->getIntegerBitWidth();
if (TD->getPointerSizeInBits(AS) > Width)
Extension = EK_SignExt;
APInt IndexScale(Width, 0), IndexOffset(Width, 0);
Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension,
*TD, 0);
BaseOffs += IndexOffset.getSExtValue()*Scale;
Scale *= IndexScale.getSExtValue();
for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
if (VarIndices[i].V == Index &&
VarIndices[i].Extension == Extension) {
Scale += VarIndices[i].Scale;
VarIndices.erase(VarIndices.begin()+i);
break;
}
}
if (unsigned ShiftBits = 64 - TD->getPointerSizeInBits(AS)) {
Scale <<= ShiftBits;
Scale = (int64_t)Scale >> ShiftBits;
}
if (Scale) {
VariableGEPIndex Entry = {Index, Extension,
static_cast<int64_t>(Scale)};
VarIndices.push_back(Entry);
}
}
V = GEPOp->getOperand(0);
} while (--MaxLookup);
return V;
}
#ifndef NDEBUG
static const Function *getParent(const Value *V) {
if (const Instruction *inst = dyn_cast<Instruction>(V))
return inst->getParent()->getParent();
if (const Argument *arg = dyn_cast<Argument>(V))
return arg->getParent();
return NULL;
}
static bool notDifferentParent(const Value *O1, const Value *O2) {
const Function *F1 = getParent(O1);
const Function *F2 = getParent(O2);
return !F1 || !F2 || F1 == F2;
}
#endif
namespace {
struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
static char ID; BasicAliasAnalysis() : ImmutablePass(ID) {
initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry());
}
virtual void initializePass() {
InitializeAliasAnalysis(this);
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AliasAnalysis>();
AU.addRequired<TargetLibraryInfo>();
}
virtual AliasResult alias(const Location &LocA,
const Location &LocB) {
assert(AliasCache.empty() && "AliasCache must be cleared after use!");
assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
"BasicAliasAnalysis doesn't support interprocedural queries.");
AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag,
LocB.Ptr, LocB.Size, LocB.TBAATag);
AliasCache.shrink_and_clear();
VisitedPhiBBs.clear();
return Alias;
}
virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
const Location &Loc);
virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
ImmutableCallSite CS2) {
return AliasAnalysis::getModRefInfo(CS1, CS2);
}
virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
virtual ModRefBehavior getModRefBehavior(const Function *F);
virtual void *getAdjustedAnalysisPointer(const void *ID) {
if (ID == &AliasAnalysis::ID)
return (AliasAnalysis*)this;
return this;
}
private:
typedef std::pair<Location, Location> LocPair;
typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
AliasCacheTy AliasCache;
SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs;
SmallPtrSet<const Value*, 16> Visited;
bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
const SmallVectorImpl<VariableGEPIndex> &Src);
AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
const MDNode *V1TBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo,
const Value *UnderlyingV1, const Value *UnderlyingV2);
AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
const MDNode *PNTBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo);
AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
const MDNode *SITBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo);
AliasResult aliasCheck(const Value *V1, uint64_t V1Size,
const MDNode *V1TBAATag,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAATag);
};
}
char BasicAliasAnalysis::ID = 0;
INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa",
"Basic Alias Analysis (stateless AA impl)",
false, true, false)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa",
"Basic Alias Analysis (stateless AA impl)",
false, true, false)
ImmutablePass *llvm::createBasicAliasAnalysisPass() {
return new BasicAliasAnalysis();
}
bool
BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) {
assert(Visited.empty() && "Visited must be cleared after use!");
unsigned MaxLookup = 8;
SmallVector<const Value *, 16> Worklist;
Worklist.push_back(Loc.Ptr);
do {
const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD);
if (!Visited.insert(V)) {
Visited.clear();
return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
}
if (OrLocal && isa<AllocaInst>(V))
continue;
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
if (!GV->isConstant()) {
Visited.clear();
return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
}
continue;
}
if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
Worklist.push_back(SI->getTrueValue());
Worklist.push_back(SI->getFalseValue());
continue;
}
if (const PHINode *PN = dyn_cast<PHINode>(V)) {
if (PN->getNumIncomingValues() > MaxLookup) {
Visited.clear();
return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
}
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
Worklist.push_back(PN->getIncomingValue(i));
continue;
}
Visited.clear();
return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
} while (!Worklist.empty() && --MaxLookup);
Visited.clear();
return Worklist.empty();
}
AliasAnalysis::ModRefBehavior
BasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
if (CS.doesNotAccessMemory())
return DoesNotAccessMemory;
ModRefBehavior Min = UnknownModRefBehavior;
if (CS.onlyReadsMemory())
Min = OnlyReadsMemory;
return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
}
AliasAnalysis::ModRefBehavior
BasicAliasAnalysis::getModRefBehavior(const Function *F) {
if (F->doesNotAccessMemory())
return DoesNotAccessMemory;
if (unsigned iid = F->getIntrinsicID()) {
#define GET_INTRINSIC_MODREF_BEHAVIOR
#include "llvm/IR/Intrinsics.gen"
#undef GET_INTRINSIC_MODREF_BEHAVIOR
}
ModRefBehavior Min = UnknownModRefBehavior;
if (F->onlyReadsMemory())
Min = OnlyReadsMemory;
return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
}
AliasAnalysis::ModRefResult
BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
const Location &Loc) {
assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
"AliasAnalysis query involving multiple functions!");
const Value *Object = GetUnderlyingObject(Loc.Ptr, TD);
if (isa<AllocaInst>(Object))
if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
if (CI->isTailCall())
return NoModRef;
if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
isNonEscapingLocalObject(Object)) {
bool PassedAsArg = false;
unsigned ArgNo = 0;
for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
CI != CE; ++CI, ++ArgNo) {
if (!(*CI)->getType()->isPointerTy() ||
(!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
continue;
if (!isNoAlias(Location(*CI), Location(Object))) {
PassedAsArg = true;
break;
}
}
if (!PassedAsArg)
return NoModRef;
}
const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>();
ModRefResult Min = ModRef;
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
if (II != 0)
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::memcpy:
case Intrinsic::memmove: {
uint64_t Len = UnknownSize;
if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2)))
Len = LenCI->getZExtValue();
Value *Dest = II->getArgOperand(0);
Value *Src = II->getArgOperand(1);
if (isNoAlias(Location(Dest, Len), Loc)) {
if (isNoAlias(Location(Src, Len), Loc))
return NoModRef;
Min = Ref;
} else if (isNoAlias(Location(Src, Len), Loc)) {
Min = Mod;
}
break;
}
case Intrinsic::memset:
if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) {
uint64_t Len = LenCI->getZExtValue();
Value *Dest = II->getArgOperand(0);
if (isNoAlias(Location(Dest, Len), Loc))
return NoModRef;
}
Min = Mod;
break;
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::invariant_start: {
uint64_t PtrSize =
cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
if (isNoAlias(Location(II->getArgOperand(1),
PtrSize,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
return NoModRef;
break;
}
case Intrinsic::invariant_end: {
uint64_t PtrSize =
cast<ConstantInt>(II->getArgOperand(1))->getZExtValue();
if (isNoAlias(Location(II->getArgOperand(2),
PtrSize,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
return NoModRef;
break;
}
case Intrinsic::arm_neon_vld1: {
uint64_t Size =
TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize;
if (isNoAlias(Location(II->getArgOperand(0), Size,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
return NoModRef;
break;
}
case Intrinsic::arm_neon_vst1: {
uint64_t Size =
TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize;
if (isNoAlias(Location(II->getArgOperand(0), Size,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
return NoModRef;
break;
}
}
else if (TLI.has(LibFunc::memset_pattern16) &&
CS.getCalledFunction() &&
CS.getCalledFunction()->getName() == "memset_pattern16") {
const Function *MS = CS.getCalledFunction();
FunctionType *MemsetType = MS->getFunctionType();
if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 &&
isa<PointerType>(MemsetType->getParamType(0)) &&
isa<PointerType>(MemsetType->getParamType(1)) &&
isa<IntegerType>(MemsetType->getParamType(2))) {
uint64_t Len = UnknownSize;
if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2)))
Len = LenCI->getZExtValue();
const Value *Dest = CS.getArgument(0);
const Value *Src = CS.getArgument(1);
if (isNoAlias(Location(Dest, Len), Loc)) {
if (isNoAlias(Location(Src, 16), Loc))
return NoModRef;
Min = Ref;
} else if (isNoAlias(Location(Src, 16), Loc)) {
Min = Mod;
}
}
}
return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min);
}
static bool areVarIndicesEqual(SmallVectorImpl<VariableGEPIndex> &Indices1,
SmallVectorImpl<VariableGEPIndex> &Indices2) {
unsigned Size1 = Indices1.size();
unsigned Size2 = Indices2.size();
if (Size1 != Size2)
return false;
for (unsigned I = 0; I != Size1; ++I)
if (Indices1[I] != Indices2[I])
return false;
return true;
}
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
const MDNode *V1TBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo,
const Value *UnderlyingV1,
const Value *UnderlyingV2) {
int64_t GEP1BaseOffset;
SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
UnderlyingV2, UnknownSize, 0);
if ((BaseAlias == MayAlias) && V1Size == V2Size) {
AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
V1TBAAInfo, UnderlyingV2,
V2Size, V2TBAAInfo);
if (PreciseBaseAlias == NoAlias) {
int64_t GEP2BaseOffset;
SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
if (GEP1BaseOffset == GEP2BaseOffset &&
areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices))
return NoAlias;
GEP1VariableIndices.clear();
}
}
if (BaseAlias != MustAlias) return BaseAlias;
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
int64_t GEP2BaseOffset;
SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
GEP1BaseOffset -= GEP2BaseOffset;
GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);
} else {
if (V1Size == UnknownSize && V2Size == UnknownSize)
return MayAlias;
AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0,
V2, V2Size, V2TBAAInfo);
if (R != MustAlias)
return R;
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
if (GEP1BasePtr != UnderlyingV1) {
assert(TD == 0 &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
}
if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty())
return MustAlias;
if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
if (GEP1BaseOffset >= 0) {
if (V2Size != UnknownSize) {
if ((uint64_t)GEP1BaseOffset < V2Size)
return PartialAlias;
return NoAlias;
}
} else {
if (V1Size != UnknownSize && V2Size != UnknownSize) {
if (-(uint64_t)GEP1BaseOffset < V1Size)
return PartialAlias;
return NoAlias;
}
}
}
if (!GEP1VariableIndices.empty()) {
uint64_t Modulo = 0;
for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i)
Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
Modulo = Modulo ^ (Modulo & (Modulo - 1));
uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
if (V1Size != UnknownSize && V2Size != UnknownSize &&
ModOffset >= V2Size && V1Size <= Modulo - ModOffset)
return NoAlias;
}
return PartialAlias;
}
static AliasAnalysis::AliasResult
MergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) {
if (A == B)
return A;
if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) ||
(B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias))
return AliasAnalysis::PartialAlias;
return AliasAnalysis::MayAlias;
}
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize,
const MDNode *SITBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo) {
if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
if (SI->getCondition() == SI2->getCondition()) {
AliasResult Alias =
aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo,
SI2->getTrueValue(), V2Size, V2TBAAInfo);
if (Alias == MayAlias)
return MayAlias;
AliasResult ThisAlias =
aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo,
SI2->getFalseValue(), V2Size, V2TBAAInfo);
return MergeAliasResults(ThisAlias, Alias);
}
AliasResult Alias =
aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo);
if (Alias == MayAlias)
return MayAlias;
AliasResult ThisAlias =
aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo);
return MergeAliasResults(ThisAlias, Alias);
}
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
const MDNode *PNTBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo) {
VisitedPhiBBs.insert(PN->getParent());
if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
if (PN2->getParent() == PN->getParent()) {
LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
Location(V2, V2Size, V2TBAAInfo));
if (PN > V2)
std::swap(Locs.first, Locs.second);
AliasResult Alias = NoAlias;
assert(AliasCache.count(Locs) &&
"There must exist an entry for the phi node");
AliasResult OrigAliasResult = AliasCache[Locs];
AliasCache[Locs] = NoAlias;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
AliasResult ThisAlias =
aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
V2Size, V2TBAAInfo);
Alias = MergeAliasResults(ThisAlias, Alias);
if (Alias == MayAlias)
break;
}
if (Alias != NoAlias)
AliasCache[Locs] = OrigAliasResult;
return Alias;
}
SmallPtrSet<Value*, 4> UniqueSrc;
SmallVector<Value*, 4> V1Srcs;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *PV1 = PN->getIncomingValue(i);
if (isa<PHINode>(PV1))
return MayAlias;
if (UniqueSrc.insert(PV1))
V1Srcs.push_back(PV1);
}
AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo,
V1Srcs[0], PNSize, PNTBAAInfo);
if (Alias == MayAlias)
return MayAlias;
for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
Value *V = V1Srcs[i];
AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo,
V, PNSize, PNTBAAInfo);
Alias = MergeAliasResults(ThisAlias, Alias);
if (Alias == MayAlias)
break;
}
return Alias;
}
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
const MDNode *V1TBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo) {
if (V1Size == 0 || V2Size == 0)
return NoAlias;
V1 = V1->stripPointerCasts();
V2 = V2->stripPointerCasts();
if (isValueEqualInPotentialCycles(V1, V2))
return MustAlias;
if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
return NoAlias;
const Value *O1 = GetUnderlyingObject(V1, TD);
const Value *O2 = GetUnderlyingObject(V2, TD);
if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
if (CPN->getType()->getAddressSpace() == 0)
return NoAlias;
if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
if (CPN->getType()->getAddressSpace() == 0)
return NoAlias;
if (O1 != O2) {
if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
return NoAlias;
if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
(isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
return NoAlias;
if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
(isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
return NoAlias;
if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
(isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
return NoAlias;
if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
return NoAlias;
if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
return NoAlias;
}
if (TD)
if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) ||
(V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI)))
return NoAlias;
LocPair Locs(Location(V1, V1Size, V1TBAAInfo),
Location(V2, V2Size, V2TBAAInfo));
if (V1 > V2)
std::swap(Locs.first, Locs.second);
std::pair<AliasCacheTy::iterator, bool> Pair =
AliasCache.insert(std::make_pair(Locs, MayAlias));
if (!Pair.second)
return Pair.first->second;
if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
std::swap(O1, O2);
std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
if (Result != MayAlias) return AliasCache[Locs] = Result;
}
if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo,
V2, V2Size, V2TBAAInfo);
if (Result != MayAlias) return AliasCache[Locs] = Result;
}
if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo,
V2, V2Size, V2TBAAInfo);
if (Result != MayAlias) return AliasCache[Locs] = Result;
}
if (TD && O1 == O2)
if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) ||
(V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI)))
return AliasCache[Locs] = PartialAlias;
AliasResult Result =
AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo),
Location(V2, V2Size, V2TBAAInfo));
return AliasCache[Locs] = Result;
}
bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V,
const Value *V2) {
if (V != V2)
return false;
const Instruction *Inst = dyn_cast<Instruction>(V);
if (!Inst)
return true;
if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
return false;
DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>();
DominatorTree *DT = DTWP ? &DTWP->getDomTree() : 0;
LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>();
for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(),
PE = VisitedPhiBBs.end();
PI != PE; ++PI)
if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI))
return false;
return true;
}
void BasicAliasAnalysis::GetIndexDifference(
SmallVectorImpl<VariableGEPIndex> &Dest,
const SmallVectorImpl<VariableGEPIndex> &Src) {
if (Src.empty())
return;
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
const Value *V = Src[i].V;
ExtensionKind Extension = Src[i].Extension;
int64_t Scale = Src[i].Scale;
for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
Dest[j].Extension != Extension)
continue;
if (Dest[j].Scale != Scale)
Dest[j].Scale -= Scale;
else
Dest.erase(Dest.begin() + j);
Scale = 0;
break;
}
if (Scale) {
VariableGEPIndex Entry = { V, Extension, -Scale };
Dest.push_back(Entry);
}
}
}