60 if (
const Argument *
A = dyn_cast<Argument>(V))
61 if (
A->hasByValAttr() ||
A->hasNoAliasAttr())
73 if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
89 bool RoundToAlign =
false) {
167 struct VariableGEPIndex {
172 bool operator==(
const VariableGEPIndex &Other)
const {
173 return V == Other.V && Extension == Other.Extension &&
174 Scale == Other.Scale;
177 bool operator!=(
const VariableGEPIndex &Other)
const {
205 if (
ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
206 switch (BOp->getOpcode()) {
214 case Instruction::Add:
217 Offset += RHSC->getValue();
219 case Instruction::Mul:
222 Offset *= RHSC->getValue();
223 Scale *= RHSC->getValue();
225 case Instruction::Shl:
228 Offset <<= RHSC->getValue().getLimitedValue();
238 if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
239 (isa<ZExtInst>(V) && Extension != EK_SignExt)) {
240 Value *CastOp = cast<CastInst>(V)->getOperand(0);
243 Scale = Scale.
trunc(SmallWidth);
244 Offset = Offset.
trunc(SmallWidth);
245 Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
249 Scale = Scale.
zext(OldWidth);
250 Offset = Offset.
zext(OldWidth);
278 unsigned MaxLookup = 6;
286 if (
const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
287 if (!GA->mayBeOverridden()) {
288 V = GA->getAliasee();
295 if (Op->
getOpcode() == Instruction::BitCast) {
306 if (
const Value *Simplified =
336 if (
StructType *STy = dyn_cast<StructType>(*GTI++)) {
338 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
339 if (FieldNo == 0)
continue;
346 if (
ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
347 if (CIdx->isZero())
continue;
359 Extension = EK_SignExt;
362 APInt IndexScale(Width, 0), IndexOffset(Width, 0);
369 Scale *= IndexScale.getSExtValue();
375 for (
unsigned i = 0, e = VarIndices.
size(); i != e; ++i) {
376 if (VarIndices[i].V == Index &&
377 VarIndices[i].Extension == Extension) {
378 Scale += VarIndices[i].Scale;
388 Scale = (int64_t)Scale >> ShiftBits;
392 VariableGEPIndex Entry = {Index, Extension,
393 static_cast<int64_t
>(Scale)};
400 }
while (--MaxLookup);
412 if (Src.
empty())
return;
414 for (
unsigned i = 0, e = Src.
size(); i != e; ++i) {
415 const Value *V = Src[i].V;
417 int64_t Scale = Src[i].Scale;
421 for (
unsigned j = 0, e = Dest.
size(); j != e; ++j) {
422 if (Dest[j].V != V || Dest[j].Extension != Extension)
continue;
426 if (Dest[j].Scale != Scale)
427 Dest[j].Scale -= Scale;
436 VariableGEPIndex Entry = { V, Extension, -Scale };
448 if (
const Instruction *inst = dyn_cast<Instruction>(V))
451 if (
const Argument *arg = dyn_cast<Argument>(V))
452 return arg->getParent();
462 return !F1 || !F2 || F1 == F2;
474 virtual void initializePass() {
475 InitializeAliasAnalysis(
this);
483 virtual AliasResult alias(
const Location &LocA,
484 const Location &LocB) {
485 assert(AliasCache.empty() &&
"AliasCache must be cleared after use!");
487 "BasicAliasAnalysis doesn't support interprocedural queries.");
488 AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag,
489 LocB.Ptr, LocB.Size, LocB.TBAATag);
494 AliasCache.shrink_and_clear();
499 const Location &Loc);
509 virtual bool pointsToConstantMemory(
const Location &Loc,
bool OrLocal);
523 virtual void *getAdjustedAnalysisPointer(
const void *
ID) {
531 typedef std::pair<Location, Location> LocPair;
533 AliasCacheTy AliasCache;
540 AliasResult aliasGEP(
const GEPOperator *V1, uint64_t V1Size,
542 const Value *
V2, uint64_t V2Size,
544 const Value *UnderlyingV1,
const Value *UnderlyingV2);
548 AliasResult aliasPHI(
const PHINode *PN, uint64_t PNSize,
550 const Value *
V2, uint64_t V2Size,
551 const MDNode *V2TBAAInfo);
554 AliasResult aliasSelect(
const SelectInst *SI, uint64_t SISize,
556 const Value *
V2, uint64_t V2Size,
557 const MDNode *V2TBAAInfo);
559 AliasResult aliasCheck(
const Value *V1, uint64_t V1Size,
561 const Value *
V2, uint64_t V2Size,
569 "Basic Alias Analysis (stateless AA impl)",
573 "Basic Alias
Analysis (stateless AA impl)",
578 return new BasicAliasAnalysis();
585 BasicAliasAnalysis::pointsToConstantMemory(
const Location &Loc,
bool OrLocal) {
586 assert(Visited.empty() &&
"Visited must be cleared after use!");
588 unsigned MaxLookup = 8;
593 if (!Visited.insert(V)) {
599 if (OrLocal && isa<AllocaInst>(V))
607 if (!GV->isConstant()) {
615 if (
const SelectInst *SI = dyn_cast<SelectInst>(V)) {
623 if (
const PHINode *PN = dyn_cast<PHINode>(V)) {
625 if (PN->getNumIncomingValues() > MaxLookup) {
629 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
630 Worklist.
push_back(PN->getIncomingValue(i));
638 }
while (!Worklist.
empty() && --MaxLookup);
641 return Worklist.
empty();
649 return DoesNotAccessMemory;
656 Min = OnlyReadsMemory;
665 BasicAliasAnalysis::getModRefBehavior(
const Function *
F) {
668 return DoesNotAccessMemory;
672 #define GET_INTRINSIC_MODREF_BEHAVIOR
673 #include "llvm/IR/Intrinsics.gen"
674 #undef GET_INTRINSIC_MODREF_BEHAVIOR
681 Min = OnlyReadsMemory;
693 const Location &Loc) {
695 "AliasAnalysis query involving multiple functions!");
704 if (isa<AllocaInst>(Object))
706 if (CI->isTailCall())
714 bool PassedAsArg =
false;
717 CI != CE; ++CI, ++ArgNo) {
721 if (!(*CI)->getType()->isPointerTy() ||
729 if (!isNoAlias(Location(*CI), Location(Object))) {
740 ModRefResult Min = ModRef;
749 uint64_t Len = UnknownSize;
751 Len = LenCI->getZExtValue();
755 if (isNoAlias(Location(Dest, Len), Loc)) {
756 if (isNoAlias(Location(Src, Len), Loc))
760 }
else if (isNoAlias(Location(Src, Len), Loc)) {
770 uint64_t Len = LenCI->getZExtValue();
772 if (isNoAlias(Location(Dest, Len), Loc))
835 uint64_t Len = UnknownSize;
837 Len = LenCI->getZExtValue();
841 if (isNoAlias(Location(Dest, Len), Loc)) {
843 if (isNoAlias(Location(Src, 16), Loc))
848 }
else if (isNoAlias(Location(Src, 16), Loc)) {
861 unsigned Size1 = Indices1.
size();
862 unsigned Size2 = Indices2.
size();
867 for (
unsigned I = 0;
I != Size1; ++
I)
868 if (Indices1[
I] != Indices2[
I])
880 BasicAliasAnalysis::aliasGEP(
const GEPOperator *GEP1, uint64_t V1Size,
882 const Value *
V2, uint64_t V2Size,
884 const Value *UnderlyingV1,
885 const Value *UnderlyingV2) {
886 int64_t GEP1BaseOffset;
892 if (
const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
894 AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
895 UnderlyingV2, UnknownSize, 0);
899 if ((BaseAlias == MayAlias) && V1Size == V2Size) {
901 AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
902 V1TBAAInfo, UnderlyingV2,
904 if (PreciseBaseAlias == NoAlias) {
907 int64_t GEP2BaseOffset;
909 const Value *GEP2BasePtr =
911 const Value *GEP1BasePtr =
915 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
917 "DecomposeGEPExpression and GetUnderlyingObject disagree!");
921 if (GEP1BaseOffset == GEP2BaseOffset &&
924 GEP1VariableIndices.
clear();
930 if (BaseAlias != MustAlias)
return BaseAlias;
935 const Value *GEP1BasePtr =
938 int64_t GEP2BaseOffset;
940 const Value *GEP2BasePtr =
945 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
947 "DecomposeGEPExpression and GetUnderlyingObject disagree!");
953 GEP1BaseOffset -= GEP2BaseOffset;
962 if (V1Size == UnknownSize && V2Size == UnknownSize)
965 AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0,
966 V2, V2Size, V2TBAAInfo);
975 const Value *GEP1BasePtr =
980 if (GEP1BasePtr != UnderlyingV1) {
982 "DecomposeGEPExpression and GetUnderlyingObject disagree!");
993 if (GEP1BaseOffset == 0 && GEP1VariableIndices.
empty())
1000 if (GEP1BaseOffset != 0 && GEP1VariableIndices.
empty()) {
1001 if (GEP1BaseOffset >= 0) {
1002 if (V2Size != UnknownSize) {
1003 if ((uint64_t)GEP1BaseOffset < V2Size)
1004 return PartialAlias;
1008 if (V1Size != UnknownSize) {
1009 if (-(uint64_t)GEP1BaseOffset < V1Size)
1010 return PartialAlias;
1018 if (!GEP1VariableIndices.
empty()) {
1019 uint64_t Modulo = 0;
1020 for (
unsigned i = 0, e = GEP1VariableIndices.
size(); i != e; ++i)
1021 Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
1022 Modulo = Modulo ^ (Modulo & (Modulo - 1));
1027 uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
1028 if (V1Size != UnknownSize && V2Size != UnknownSize &&
1029 ModOffset >= V2Size && V1Size <= Modulo - ModOffset)
1040 return PartialAlias;
1059 BasicAliasAnalysis::aliasSelect(
const SelectInst *SI, uint64_t SISize,
1060 const MDNode *SITBAAInfo,
1061 const Value *V2, uint64_t V2Size,
1062 const MDNode *V2TBAAInfo) {
1065 if (
const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1069 SI2->getTrueValue(), V2Size, V2TBAAInfo);
1070 if (Alias == MayAlias)
1072 AliasResult ThisAlias =
1074 SI2->getFalseValue(), V2Size, V2TBAAInfo);
1081 aliasCheck(V2, V2Size, V2TBAAInfo, SI->
getTrueValue(), SISize, SITBAAInfo);
1082 if (Alias == MayAlias)
1085 AliasResult ThisAlias =
1086 aliasCheck(V2, V2Size, V2TBAAInfo, SI->
getFalseValue(), SISize, SITBAAInfo);
1093 BasicAliasAnalysis::aliasPHI(
const PHINode *PN, uint64_t PNSize,
1094 const MDNode *PNTBAAInfo,
1095 const Value *V2, uint64_t V2Size,
1096 const MDNode *V2TBAAInfo) {
1100 if (
const PHINode *PN2 = dyn_cast<PHINode>(V2))
1101 if (PN2->getParent() == PN->
getParent()) {
1102 LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
1103 Location(V2, V2Size, V2TBAAInfo));
1113 AliasResult Alias = NoAlias;
1114 assert(AliasCache.count(Locs) &&
1115 "There must exist an entry for the phi node");
1116 AliasResult OrigAliasResult = AliasCache[Locs];
1117 AliasCache[Locs] = NoAlias;
1120 AliasResult ThisAlias =
1123 V2Size, V2TBAAInfo);
1125 if (Alias == MayAlias)
1130 if (Alias != NoAlias)
1131 AliasCache[Locs] = OrigAliasResult;
1140 if (isa<PHINode>(PV1))
1146 if (UniqueSrc.
insert(PV1))
1150 AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo,
1151 V1Srcs[0], PNSize, PNTBAAInfo);
1154 if (Alias == MayAlias)
1159 for (
unsigned i = 1, e = V1Srcs.
size(); i != e; ++i) {
1160 Value *V = V1Srcs[i];
1162 AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo,
1163 V, PNSize, PNTBAAInfo);
1165 if (Alias == MayAlias)
1176 BasicAliasAnalysis::aliasCheck(
const Value *V1, uint64_t V1Size,
1177 const MDNode *V1TBAAInfo,
1178 const Value *V2, uint64_t V2Size,
1179 const MDNode *V2TBAAInfo) {
1182 if (V1Size == 0 || V2Size == 0)
1190 if (V1 == V2)
return MustAlias;
1202 if (CPN->getType()->getAddressSpace() == 0)
1205 if (CPN->getType()->getAddressSpace() == 0)
1253 LocPair Locs(Location(V1, V1Size, V1TBAAInfo),
1254 Location(V2, V2Size, V2TBAAInfo));
1257 std::pair<AliasCacheTy::iterator, bool> Pair =
1258 AliasCache.insert(std::make_pair(Locs, MayAlias));
1260 return Pair.first->second;
1264 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
1270 if (
const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1271 AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
1272 if (Result != MayAlias)
return AliasCache[Locs] = Result;
1275 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
1280 if (
const PHINode *PN = dyn_cast<PHINode>(V1)) {
1281 AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo,
1282 V2, V2Size, V2TBAAInfo);
1283 if (Result != MayAlias)
return AliasCache[Locs] = Result;
1286 if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
1291 if (
const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
1292 AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo,
1293 V2, V2Size, V2TBAAInfo);
1294 if (Result != MayAlias)
return AliasCache[Locs] = Result;
1301 if ((V1Size != UnknownSize &&
isObjectSize(O1, V1Size, *TD, *TLI)) ||
1302 (V2Size != UnknownSize &&
isObjectSize(O2, V2Size, *TD, *TLI)))
1303 return AliasCache[Locs] = PartialAlias;
1305 AliasResult Result =
1307 Location(V2, V2Size, V2TBAAInfo));
1308 return AliasCache[Locs] = Result;
void push_back(const T &Elt)
Basic Alias Analysis(stateless AA impl)"
Pointers differ, but pointees overlap.
virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal=false)
static PassRegistry * getPassRegistry()
LLVM Argument representation.
ModRefResult getModRefInfo(const Instruction *I, const Location &Loc)
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
unsigned getNumParams() const
Intrinsic::ID getIntrinsicID() const
static const Value * DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, SmallVectorImpl< VariableGEPIndex > &VarIndices, const DataLayout *TD)
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD=0, unsigned Depth=0)
static bool isEscapeSource(const Value *V)
bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI=0)
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
MDNode - a tuple of other values.
bool isNoAliasCall(const Value *V)
ValTy * getArgument(unsigned ArgNo) const
Type * getPointerElementType() const
StringRef getName() const
Value * GetUnderlyingObject(Value *V, const DataLayout *TD=0, unsigned MaxLookup=6)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
const StructLayout * getStructLayout(StructType *Ty) const
bool has(LibFunc::Func F) const
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &TD, const TargetLibraryInfo &TLI)
static AliasAnalysis::AliasResult MergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B)
ID
LLVM Calling Convention Representation.
bool isIdentifiedObject(const Value *V)
static bool isIdentifiedFunctionLocal(const Value *V)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
ImmutablePass * createBasicAliasAnalysisPass()
INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis,"basicaa","Basic Alias Analysis (stateless AA impl)", false, true, false) INITIALIZE_AG_PASS_END(BasicAliasAnalysis
static bool areVarIndicesEqual(SmallVectorImpl< VariableGEPIndex > &Indices1, SmallVectorImpl< VariableGEPIndex > &Indices2)
bool doesNotAccessMemory() const
Determine if the function does not access memory.
unsigned getNumIncomingValues() const
uint64_t getElementOffset(unsigned Idx) const
void memset_pattern16(void *b, const void *pattern16, size_t len);
User::const_op_iterator arg_iterator
Type * getParamType(unsigned i) const
Parameter type accessors.
APInt LLVM_ATTRIBUTE_UNUSED_RESULT trunc(unsigned width) const
Truncate to new width.
InstrTy * getInstruction() const
unsigned getIntrinsicID() const LLVM_READONLY
virtual AliasResult alias(const Location &LocA, const Location &LocB)
const Value * getCondition() const
int64_t getSExtValue() const
Get sign extended value.
APInt Or(const APInt &LHS, const APInt &RHS)
Bitwise OR function for APInt.
BasicBlock * getIncomingBlock(unsigned i) const
unsigned getBitWidth() const
Return the number of bits in the APInt.
Value * getOperand(unsigned i) const
static void GetIndexDifference(SmallVectorImpl< VariableGEPIndex > &Dest, const SmallVectorImpl< VariableGEPIndex > &Src)
static bool isNonEscapingLocalObject(const Value *V)
iterator erase(iterator I)
Value * SimplifyInstruction(Instruction *I, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0, const DominatorTree *DT=0)
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
void initializeBasicAliasAnalysisPass(PassRegistry &)
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS)
getModRefBehavior - Return the behavior when calling the given call site.
const Value * getTrueValue() const
unsigned getIntegerBitWidth() const
Class for constant integers.
bool doesNotAccessMemory() const
Determine if the call does not access memory.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Value * getIncomingValue(unsigned i) const
uint64_t getTypeAllocSize(Type *Ty) const
MDNode * getMetadata(unsigned KindID) const
static Value * GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, ExtensionKind &Extension, const DataLayout &TD, unsigned Depth)
bool hasAllZeroIndices() const
Value * stripPointerCasts()
Strips off any unneeded pointer casts, all-zero GEPs and aliases from the specified value...
bool doesNotCapture(unsigned ArgNo) const
Determine whether this argument is not captured.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Value * getArgOperand(unsigned i) const
Class for arbitrary precision integers.
static bool notDifferentParent(const Value *O1, const Value *O2)
unsigned getOpcode() const
bool operator!=(uint64_t V1, const APInt &V2)
static bool isObjectSmallerThan(const Value *V, uint64_t Size, const DataLayout &TD, const TargetLibraryInfo &TLI)
ImmutableCallSite - establish a view to a call site for examination.
FunctionType * getFunctionType() const
unsigned getPointerSizeInBits(unsigned AS=0) const
unsigned getPointerAddressSpace() const
unsigned getPrimitiveSizeInBits() const
uint64_t getTypeStoreSize(Type *Ty) const
static uint64_t const UnknownSize
LLVM Value Representation.
static const Function * getParent(const Value *V)
#define INITIALIZE_AG_PASS_END(passName, agName, arg, n, cfg, analysis, def)
const Value * getFalseValue() const
APInt LLVM_ATTRIBUTE_UNUSED_RESULT zext(unsigned width) const
Zero extend to a new width.
bool isNoAliasArgument(const Value *V)
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, const TargetLibraryInfo *TLI, bool RoundToAlign=false)
Compute the size of the object pointed by Ptr. Returns true and the object size in Size if successful...
bool operator==(uint64_t V1, const APInt &V2)
const BasicBlock * getParent() const
INITIALIZE_PASS(GlobalMerge,"global-merge","Global Merge", false, false) bool GlobalMerge const DataLayout * TD
FunTy * getCalledFunction() const
gep_type_iterator gep_type_begin(const User *GEP)