Index: include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- include/llvm/Analysis/BasicAliasAnalysis.h +++ include/llvm/Analysis/BasicAliasAnalysis.h @@ -39,6 +39,7 @@ class DominatorTree; class Function; class GEPOperator; +class LazyValueInfo; class LoopInfo; class PHINode; class SelectInst; @@ -62,13 +63,14 @@ DominatorTree *DT; LoopInfo *LI; PhiValues *PV; + LazyValueInfo *LVI; public: BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - PhiValues *PV = nullptr) - : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) + PhiValues *PV = nullptr, LazyValueInfo *LVI = nullptr) + : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV), LVI(LVI) {} BasicAAResult(const BasicAAResult &Arg) Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -88,6 +88,9 @@ /// on integer-typed Values. ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); + ConstantRange getConstantRange(const Value *V, const BasicBlock *BB, + const Instruction *CxtI = nullptr); + /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, @@ -149,7 +152,13 @@ initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry()); } ~LazyValueInfoWrapperPass() override { +#if 0 + // TODO:FIXME: There appears to be a problem with pass scheduling where LVI + // is called (via AA) after it has been freed. See --debug-pass=Executions + // for details with gdb breakpoints in releaseMemory and getImpl. + assert(!Info.PImpl && "releaseMemory not called"); +#endif } LazyValueInfo &getLVI(); 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 @@ -23,6 +23,7 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" @@ -33,6 +34,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" @@ -1004,19 +1006,13 @@ LocationSize MaybeV1Size, const GEPOperator *GEP2, LocationSize MaybeV2Size, - const DataLayout &DL) { + const DataLayout &DL, + LazyValueInfo *LVI) { 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 +1022,61 @@ 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() == 1 && GEP2->getNumIndices() == 1 && LVI) { + const BinaryOperator *I1 = dyn_cast(GEP1->getOperand(1)); + const BinaryOperator *I2 = dyn_cast(GEP2->getOperand(1)); + + auto isSupported = [] (const BinaryOperator *I) { + return (I && dyn_cast(I->getOperand(1)) && + (I->getOpcode() == Instruction::Mul || + I->getOpcode() == Instruction::Shl)); + }; + + if (isSupported(I1) && isSupported(I2) && + I1->getOperand(0) == I2->getOperand(0)) { + ConstantRange R1 = LVI->getConstantRange(I1, I1->getParent(), I1); + ConstantRange R2 = LVI->getConstantRange(I2, I2->getParent(), I1); + + 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 +1274,25 @@ 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 && LVI) { + const BinaryOperator *I1 = dyn_cast(GEP1->getOperand(1)); + if (I1 && dyn_cast(I1->getOperand(1)) && + (I1->getOpcode() == Instruction::Mul || + I1->getOpcode() == Instruction::Shl)) { + ConstantRange R1 = LVI->getConstantRange(I1, I1->getParent(), I1); + 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 +1362,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, LVI); // If we couldn't find anything interesting, don't abandon just yet. if (R != MayAlias) return R; @@ -1943,6 +2013,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa", "Basic Alias Analysis (stateless AA impl)", false, true) @@ -1956,11 +2027,13 @@ auto &DTWP = getAnalysis(); auto *LIWP = getAnalysisIfAvailable(); auto *PVWP = getAnalysisIfAvailable(); + auto *LVIP = &getAnalysis(); Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, TLIWP.getTLI(), ACT.getAssumptionCache(F), &DTWP.getDomTree(), LIWP ? &LIWP->getLoopInfo() : nullptr, - PVWP ? &PVWP->getResult() : nullptr)); + PVWP ? &PVWP->getResult() : nullptr, + LVIP ? &LVIP->getLVI() : nullptr)); return false; } @@ -1969,6 +2042,7 @@ AU.setPreservesAll(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addUsedIfAvailable(); } Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -1567,6 +1567,12 @@ return nullptr; } +ConstantRange LazyValueInfo::getConstantRange(const Value *V, const BasicBlock *BB, + const Instruction *CxtI) { + return getConstantRange(const_cast(V), const_cast(BB), + const_cast(CxtI)); +} + ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI) { assert(V->getType()->isIntegerTy());