Index: lib/Analysis/AssumptionCache.cpp =================================================================== --- lib/Analysis/AssumptionCache.cpp +++ lib/Analysis/AssumptionCache.cpp @@ -110,6 +110,20 @@ } } + // TODO:FIXME: The expression (inside) __builtin_assume(x > 0 && x < 16) + // would get transformed into: + // %x.off = add i16 %x, -1 + // %0 = icmp ult i16 %x.off, 15 + // The following pattern is needed to add %x to the AC. + // + // Unclear what this means for the 'in-sync with ValueTracking' comment in + // the beginning of this function. As an observation LazyValueInfo has code + // for this exact pattern but without the AddAffected here it will never find + // those in the AC. + if (match(Cond, m_ICmp(Pred, m_Add(m_Value(A), m_Value()), m_Value()))) { + AddAffected(A); + } + for (auto &AV : Affected) { auto &AVV = getOrInsertAffectedValues(AV); if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end()) Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -33,6 +33,7 @@ #include "llvm/IR/Attributes.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" +#include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" @@ -48,6 +49,7 @@ #include "llvm/IR/Intrinsics.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" @@ -64,6 +66,7 @@ #define DEBUG_TYPE "basicaa" using namespace llvm; +using namespace llvm::PatternMatch; /// Enable analysis of recursive PHI nodes. static cl::opt EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, @@ -998,25 +1001,65 @@ return AAResultBase::getModRefInfo(CS1, CS2); } +// TODO:FIXME: This could be handled LazyValueInfo but unfortunately there are +// some issues enabling that analysis (it asserts complaining about +// deconstructing without releaseMemory begin called). It would also requires +// the fix in AssumptionCache.cpp. +// +// Basically given a value V find out what its range is (if known otherwise +// return full-set). +static ConstantRange getValueRange(const Value *V, + const Instruction *RefI, + AssumptionCache *AC, + DominatorTree *DT) { + + Value *X; + unsigned BitWidth = V->getType()->getIntegerBitWidth(); + ConstantInt *C; + + if (match(V, m_Shl(m_Value(X), m_ConstantInt(C)))) { + ConstantRange CR = getValueRange(X, RefI, AC, DT); + return CR.shl(APInt(BitWidth, C->getZExtValue())); + } else if (match(V, m_Mul(m_Value(X), m_ConstantInt(C)))) { + ConstantRange CR = getValueRange(X, RefI, AC, DT); + return CR.multiply(APInt(BitWidth, C->getZExtValue())); + } else { + for (auto &AssumeVH : AC->assumptionsFor(V)) { + CallInst *I = cast(AssumeVH); + + if (!isValidAssumeForContext(I, RefI, DT)) + continue; + + Value *Arg = I->getArgOperand(0); + + CmpInst::Predicate Pred; + ConstantInt *Offset, *Upper; + + if (match(Arg, m_c_ICmp(Pred, m_Add(m_Specific(V), m_ConstantInt(Offset)), m_ConstantInt(Upper))) && + Pred == ICmpInst::ICMP_ULT) { + return ConstantRange(APInt(BitWidth, -Offset->getSExtValue()), + APInt(BitWidth, Upper->getSExtValue() - Offset->getSExtValue())); + } + } + } + // Unknown return full range + return ConstantRange(BitWidth, true); +} + /// Provide ad-hoc rules to disambiguate accesses through two GEP operators, /// both having the exact same pointer operand. static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, LocationSize MaybeV1Size, const GEPOperator *GEP2, LocationSize MaybeV2Size, - const DataLayout &DL) { + const DataLayout &DL, + AssumptionCache *AC, + DominatorTree *DT) { assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType() && "Expected GEPs with the same pointer operand"); - // Try to determine whether GEP1 and GEP2 index through arrays, into structs, - // such that the struct field accesses provably cannot alias. - // We also need at least two indices (the pointer, and the struct field). - if (GEP1->getNumIndices() != GEP2->getNumIndices() || - GEP1->getNumIndices() < 2) - return MayAlias; - // If we don't know the size of the accesses through both GEPs, we can't // determine whether the struct fields accessed can't alias. if (MaybeV1Size == LocationSize::unknown() || @@ -1026,6 +1069,55 @@ const uint64_t V1Size = MaybeV1Size.getValue(); const uint64_t V2Size = MaybeV2Size.getValue(); + // The situation is: + // %I1 = shl/mul i16 %X, C1 + // %I2 = shl/mul i16 %X, C2 + // %G1 = getelementptr i16, i16* %baseptr, i16 %I1 + // %G2 = getelementptr i16, i16* %baseptr, i16 %I2 + // Given that we have value range information on %I1 and %I2 we can determine + // if there is alias by comparing the lower bounds of those ranges (since %X + // is used in both) + if (GEP1->getNumIndices() == GEP2->getNumIndices() && + GEP1->getNumIndices() == 1) { + const BinaryOperator *I1 = dyn_cast(GEP1->getOperand(1)); + const BinaryOperator *I2 = dyn_cast(GEP2->getOperand(1)); + if (I1 && I2 && I1->getOperand(0) == I2->getOperand(0)) { + + ConstantRange R1 = getValueRange(I1, I1, AC, DT); + ConstantRange R2 = getValueRange(I2, I2, AC, DT); + + const unsigned BitWidth = I1->getType()->getIntegerBitWidth(); + // The idea behind SafeRange is to have a range, to compare against, that + // would guarantee that %X was not zero and did not cause an overflow. + const ConstantRange SafeRange(APInt(BitWidth, 1), + APInt(BitWidth, (1U << BitWidth) - 1)); + + if (SafeRange.contains(R1) && SafeRange.contains(R2)) { + unsigned Ty1Size = DL.getTypeStoreSize(GEP1->getSourceElementType()); + unsigned Ty2Size = DL.getTypeStoreSize(GEP2->getSourceElementType()); + const uint64_t R1Lower = R1.getLower().getZExtValue() * Ty1Size; + const uint64_t R2Lower = R2.getLower().getZExtValue() * Ty2Size; + + // Since %X is the same in both we can now pick a value for it that + // corresponds to the lower bounds and compare those with the sizes. + if (R1Lower < R2Lower) { + if (R1Lower + V1Size <= R2Lower) + return NoAlias; + } else { + if (R2Lower + V2Size <= R1Lower) + return NoAlias; + } + } + } + } + + // Try to determine whether GEP1 and GEP2 index through arrays, into structs, + // such that the struct field accesses provably cannot alias. + // We also need at least two indices (the pointer, and the struct field). + if (GEP1->getNumIndices() != GEP2->getNumIndices() || + GEP1->getNumIndices() < 2) + return MayAlias; + ConstantInt *C1 = dyn_cast(GEP1->getOperand(GEP1->getNumOperands() - 1)); ConstantInt *C2 = @@ -1223,6 +1315,22 @@ const AAMDNodes &V1AAInfo, const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, const Value *UnderlyingV1, const Value *UnderlyingV2) { + // If %G1 = getelementptr i16, i16* %P, i16 %I1 + // Then try to determine if %G1 and %P alias by looking at the value range of + // %I1 and comparing it to the size of the %P access. + if (UnderlyingV1 == V2 && GEP1->getNumIndices() == 1) { + if (const Instruction *I1 = dyn_cast(GEP1->getOperand(1))) { + ConstantRange R1 = getValueRange(I1, I1, &AC, DT); + const unsigned BitWidth = I1->getType()->getIntegerBitWidth(); + const ConstantRange SafeRange(APInt(BitWidth, 1), + APInt(BitWidth, (1U << BitWidth) - 1)); + unsigned Ty1Size = DL.getTypeStoreSize(GEP1->getSourceElementType()); + if (SafeRange.contains(R1) && + V2Size.getValue() <= R1.getLower().getZExtValue() * Ty1Size) + return NoAlias; + } + } + DecomposedGEP DecompGEP1, DecompGEP2; bool GEP1MaxLookupReached = DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT); @@ -1292,7 +1400,7 @@ if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() == GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() && GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) { - AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL); + AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL, &AC, DT); // If we couldn't find anything interesting, don't abandon just yet. if (R != MayAlias) return R;