X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=06dbde58c1084488ae087b9efbc0633394c0c11e;hb=93710f07f02b3961556d2344e1baab1f53e4b45e;hp=b8a49f590f0cb318e7632b3b23dfee85b9b9a2cd;hpb=f255eb964370acb26813504a4cb680040ffae517;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index b8a49f590f0..06dbde58c10 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1201,6 +1201,23 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, return getTruncateOrSignExtend(X, Ty); } + // sext(C1 + (C2 * x)) --> C1 + sext(C2 * x) if C1 < C2 + if (auto SA = dyn_cast(Op)) { + if (SA->getNumOperands() == 2) { + auto SC1 = dyn_cast(SA->getOperand(0)); + auto SMul = dyn_cast(SA->getOperand(1)); + if (SMul && SC1) { + if (auto SC2 = dyn_cast(SMul->getOperand(0))) { + const APInt &C1 = SC1->getValue()->getValue(); + const APInt &C2 = SC2->getValue()->getValue(); + if (C1.isStrictlyPositive() && C2.isStrictlyPositive() && + C2.ugt(C1) && C2.isPowerOf2()) + return getAddExpr(getSignExtendExpr(SC1, Ty), + getSignExtendExpr(SMul, Ty)); + } + } + } + } // If the input value is a chrec scev, and we can prove that the value // did not overflow the old, smaller, value, we can sign extend all of the // operands (often constants). This allows analysis of something like @@ -1292,6 +1309,22 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, L, AR->getNoWrapFlags()); } } + // If Start and Step are constants, check if we can apply this + // transformation: + // sext{C1,+,C2} --> C1 + sext{0,+,C2} if C1 < C2 + auto SC1 = dyn_cast(Start); + auto SC2 = dyn_cast(Step); + if (SC1 && SC2) { + const APInt &C1 = SC1->getValue()->getValue(); + const APInt &C2 = SC2->getValue()->getValue(); + if (C1.isStrictlyPositive() && C2.isStrictlyPositive() && C2.ugt(C1) && + C2.isPowerOf2()) { + Start = getSignExtendExpr(Start, Ty); + const SCEV *NewAR = getAddRecExpr(getConstant(AR->getType(), 0), Step, + L, AR->getNoWrapFlags()); + return getAddExpr(Start, getSignExtendExpr(NewAR, Ty)); + } + } } // The cast wasn't folded; create an explicit cast node. @@ -3362,7 +3395,7 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { // For a SCEVUnknown, ask ValueTracking. unsigned BitWidth = getTypeSizeInBits(U->getType()); APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); - ComputeMaskedBits(U->getValue(), Zeros, Ones); + computeKnownBits(U->getValue(), Zeros, Ones); return Zeros.countTrailingOnes(); } @@ -3501,7 +3534,7 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { if (const SCEVUnknown *U = dyn_cast(S)) { // For a SCEVUnknown, ask ValueTracking. APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); - ComputeMaskedBits(U->getValue(), Zeros, Ones, DL); + computeKnownBits(U->getValue(), Zeros, Ones, DL); if (Ones == ~Zeros + 1) return setUnsignedRange(U, ConservativeResult); return setUnsignedRange(U, @@ -3754,13 +3787,13 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // Instcombine's ShrinkDemandedConstant may strip bits out of // constants, obscuring what would otherwise be a low-bits mask. - // Use ComputeMaskedBits to compute what ShrinkDemandedConstant + // Use computeKnownBits to compute what ShrinkDemandedConstant // knew about to reconstruct a low-bits mask value. unsigned LZ = A.countLeadingZeros(); unsigned TZ = A.countTrailingZeros(); unsigned BitWidth = A.getBitWidth(); APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); - ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, DL); + computeKnownBits(U->getOperand(0), KnownZero, KnownOne, DL); APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ); @@ -4409,38 +4442,63 @@ ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) { SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); - // Examine all exits and pick the most conservative values. - const SCEV *MaxBECount = getCouldNotCompute(); + SmallVector, 4> ExitCounts; bool CouldComputeBECount = true; BasicBlock *Latch = L->getLoopLatch(); // may be NULL. - const SCEV *LatchMaxCount = nullptr; - SmallVector, 4> ExitCounts; + const SCEV *MustExitMaxBECount = nullptr; + const SCEV *MayExitMaxBECount = nullptr; + + // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts + // and compute maxBECount. for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { - ExitLimit EL = ComputeExitLimit(L, ExitingBlocks[i]); + BasicBlock *ExitBB = ExitingBlocks[i]; + ExitLimit EL = ComputeExitLimit(L, ExitBB); + + // 1. For each exit that can be computed, add an entry to ExitCounts. + // CouldComputeBECount is true only if all exits can be computed. if (EL.Exact == getCouldNotCompute()) // We couldn't compute an exact value for this exit, so // we won't be able to compute an exact value for the loop. CouldComputeBECount = false; else - ExitCounts.push_back(std::make_pair(ExitingBlocks[i], EL.Exact)); - - if (MaxBECount == getCouldNotCompute()) - MaxBECount = EL.Max; - else if (EL.Max != getCouldNotCompute()) { - // We cannot take the "min" MaxBECount, because non-unit stride loops may - // skip some loop tests. Taking the max over the exits is sufficiently - // conservative. TODO: We could do better taking into consideration - // non-latch exits that dominate the latch. - if (EL.MustExit && ExitingBlocks[i] == Latch) - LatchMaxCount = EL.Max; - else - MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, EL.Max); + ExitCounts.push_back(std::make_pair(ExitBB, EL.Exact)); + + // 2. Derive the loop's MaxBECount from each exit's max number of + // non-exiting iterations. Partition the loop exits into two kinds: + // LoopMustExits and LoopMayExits. + // + // A LoopMustExit meets two requirements: + // + // (a) Its ExitLimit.MustExit flag must be set which indicates that the exit + // test condition cannot be skipped (the tested variable has unit stride or + // the test is less-than or greater-than, rather than a strict inequality). + // + // (b) It must dominate the loop latch, hence must be tested on every loop + // iteration. + // + // If any computable LoopMustExit is found, then MaxBECount is the minimum + // EL.Max of computable LoopMustExits. Otherwise, MaxBECount is + // conservatively the maximum EL.Max, where CouldNotCompute is considered + // greater than any computable EL.Max. + if (EL.MustExit && EL.Max != getCouldNotCompute() && Latch && + DT->dominates(ExitBB, Latch)) { + if (!MustExitMaxBECount) + MustExitMaxBECount = EL.Max; + else { + MustExitMaxBECount = + getUMinFromMismatchedTypes(MustExitMaxBECount, EL.Max); + } + } else if (MayExitMaxBECount != getCouldNotCompute()) { + if (!MayExitMaxBECount || EL.Max == getCouldNotCompute()) + MayExitMaxBECount = EL.Max; + else { + MayExitMaxBECount = + getUMaxFromMismatchedTypes(MayExitMaxBECount, EL.Max); + } } } - // Be more precise in the easy case of a loop latch that must exit. - if (LatchMaxCount) { - MaxBECount = getUMinFromMismatchedTypes(MaxBECount, LatchMaxCount); - } + const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : + (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute()); return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount); } @@ -6137,18 +6195,30 @@ bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred, // If LHS or RHS is an addrec, check to see if the condition is true in // every iteration of the loop. - if (const SCEVAddRecExpr *AR = dyn_cast(LHS)) - if (isLoopEntryGuardedByCond( - AR->getLoop(), Pred, AR->getStart(), RHS) && - isLoopBackedgeGuardedByCond( - AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS)) - return true; - if (const SCEVAddRecExpr *AR = dyn_cast(RHS)) - if (isLoopEntryGuardedByCond( - AR->getLoop(), Pred, LHS, AR->getStart()) && - isLoopBackedgeGuardedByCond( - AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this))) - return true; + // If LHS and RHS are both addrec, both conditions must be true in + // every iteration of the loop. + const SCEVAddRecExpr *LAR = dyn_cast(LHS); + const SCEVAddRecExpr *RAR = dyn_cast(RHS); + bool LeftGuarded = false; + bool RightGuarded = false; + if (LAR) { + const Loop *L = LAR->getLoop(); + if (isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) && + isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) { + if (!RAR) return true; + LeftGuarded = true; + } + } + if (RAR) { + const Loop *L = RAR->getLoop(); + if (isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) && + isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) { + if (!LAR) return true; + RightGuarded = true; + } + } + if (LeftGuarded && RightGuarded) + return true; // Otherwise see what can be done with known constant ranges. return isKnownPredicateWithRanges(Pred, LHS, RHS); @@ -6874,7 +6944,7 @@ struct SCEVCollectTerms { : Terms(T) {} bool follow(const SCEV *S) { - if (isa(S) || isa(S) || isa(S)) { + if (isa(S) || isa(S)) { if (!containsUndefs(S)) Terms.push_back(S); @@ -6987,7 +7057,7 @@ public: return; } - if (Numerator == D.Zero) { + if (Numerator->isZero()) { *Quotient = D.Zero; *Remainder = D.Zero; return; @@ -7003,7 +7073,7 @@ public: // Bail out when the Numerator is not divisible by one of the terms of // the Denominator. - if (R != D.Zero) { + if (!R->isZero()) { *Quotient = D.Zero; *Remainder = Numerator; return; @@ -7061,9 +7131,19 @@ public: void visitAddExpr(const SCEVAddExpr *Numerator) { SmallVector Qs, Rs; + Type *Ty = Denominator->getType(); + for (const SCEV *Op : Numerator->operands()) { const SCEV *Q, *R; divide(SE, Op, Denominator, &Q, &R); + + // Bail out if types do not match. + if (Ty != Q->getType() || Ty != R->getType()) { + Quotient = Zero; + Remainder = Numerator; + return; + } + Qs.push_back(Q); Rs.push_back(R); } @@ -7080,9 +7160,17 @@ public: void visitMulExpr(const SCEVMulExpr *Numerator) { SmallVector Qs; + Type *Ty = Denominator->getType(); bool FoundDenominatorTerm = false; for (const SCEV *Op : Numerator->operands()) { + // Bail out if types do not match. + if (Ty != Op->getType()) { + Quotient = Zero; + Remainder = Numerator; + return; + } + if (FoundDenominatorTerm) { Qs.push_back(Op); continue; @@ -7091,10 +7179,18 @@ public: // Check whether Denominator divides one of the product operands. const SCEV *Q, *R; divide(SE, Op, Denominator, &Q, &R); - if (R != Zero) { + if (!R->isZero()) { Qs.push_back(Op); continue; } + + // Bail out if types do not match. + if (Ty != Q->getType()) { + Quotient = Zero; + Remainder = Numerator; + return; + } + FoundDenominatorTerm = true; Qs.push_back(Q); } @@ -7120,6 +7216,15 @@ public: cast(Zero)->getValue(); Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true); + if (Remainder->isZero()) { + // The Quotient is obtained by replacing Denominator by 1 in Numerator. + RewriteMap[cast(Denominator)->getValue()] = + cast(One)->getValue(); + Quotient = + SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true); + return; + } + // Quotient is (Numerator - Remainder) divided by Denominator. const SCEV *Q, *R; const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder); @@ -7141,86 +7246,37 @@ private: }; } -// Find the Greatest Common Divisor of A and B. -static const SCEV * -findGCD(ScalarEvolution &SE, const SCEV *A, const SCEV *B) { - - if (const SCEVConstant *CA = dyn_cast(A)) - if (const SCEVConstant *CB = dyn_cast(B)) - return SE.getConstant(gcd(CA, CB)); - - const SCEV *One = SE.getConstant(A->getType(), 1); - if (isa(A) && isa(B)) - return One; - if (isa(A) && isa(B)) - return One; - - const SCEV *Q, *R; - if (const SCEVMulExpr *M = dyn_cast(A)) { - SmallVector Qs; - for (const SCEV *Op : M->operands()) - Qs.push_back(findGCD(SE, Op, B)); - return SE.getMulExpr(Qs); - } - if (const SCEVMulExpr *M = dyn_cast(B)) { - SmallVector Qs; - for (const SCEV *Op : M->operands()) - Qs.push_back(findGCD(SE, A, Op)); - return SE.getMulExpr(Qs); - } - - const SCEV *Zero = SE.getConstant(A->getType(), 0); - SCEVDivision::divide(SE, A, B, &Q, &R); - if (R == Zero) - return B; - - SCEVDivision::divide(SE, B, A, &Q, &R); - if (R == Zero) - return A; - - return One; -} - -// Find the Greatest Common Divisor of all the SCEVs in Terms. -static const SCEV * -findGCD(ScalarEvolution &SE, SmallVectorImpl &Terms) { - assert(Terms.size() > 0 && "Terms vector is empty"); - - const SCEV *GCD = Terms[0]; - for (const SCEV *T : Terms) - GCD = findGCD(SE, GCD, T); - - return GCD; -} - -static void findArrayDimensionsRec(ScalarEvolution &SE, +static bool findArrayDimensionsRec(ScalarEvolution &SE, SmallVectorImpl &Terms, - SmallVectorImpl &Sizes, - const SCEV *Zero, const SCEV *One) { - // The GCD of all Terms is the dimension of the innermost dimension. - const SCEV *GCD = findGCD(SE, Terms); + SmallVectorImpl &Sizes) { + int Last = Terms.size() - 1; + const SCEV *Step = Terms[Last]; // End of recursion. - if (Terms.size() == 1) { - if (const SCEVMulExpr *M = dyn_cast(GCD)) { + if (Last == 0) { + if (const SCEVMulExpr *M = dyn_cast(Step)) { SmallVector Qs; for (const SCEV *Op : M->operands()) if (!isa(Op)) Qs.push_back(Op); - GCD = SE.getMulExpr(Qs); + Step = SE.getMulExpr(Qs); } - Sizes.push_back(GCD); - return; + Sizes.push_back(Step); + return true; } - for (unsigned I = 0; I < Terms.size(); ++I) { + for (const SCEV *&Term : Terms) { // Normalize the terms before the next call to findArrayDimensionsRec. const SCEV *Q, *R; - SCEVDivision::divide(SE, Terms[I], GCD, &Q, &R); - assert(R == Zero && "GCD does not evenly divide one of the terms"); - Terms[I] = Q; + SCEVDivision::divide(SE, Term, Step, &Q, &R); + + // Bail out when GCD does not evenly divide one of the terms. + if (!R->isZero()) + return false; + + Term = Q; } // Remove all SCEVConstants. @@ -7230,8 +7286,11 @@ static void findArrayDimensionsRec(ScalarEvolution &SE, Terms.end()); if (Terms.size() > 0) - findArrayDimensionsRec(SE, Terms, Sizes, Zero, One); - Sizes.push_back(GCD); + if (!findArrayDimensionsRec(SE, Terms, Sizes)) + return false; + + Sizes.push_back(Step); + return true; } namespace { @@ -7281,13 +7340,46 @@ static inline int numberOfTerms(const SCEV *S) { return 1; } +static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) { + if (isa(T)) + return nullptr; + + if (isa(T)) + return T; + + if (const SCEVMulExpr *M = dyn_cast(T)) { + SmallVector Factors; + for (const SCEV *Op : M->operands()) + if (!isa(Op)) + Factors.push_back(Op); + + return SE.getMulExpr(Factors); + } + + return T; +} + +/// Return the size of an element read or written by Inst. +const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { + Type *Ty; + if (StoreInst *Store = dyn_cast(Inst)) + Ty = Store->getValueOperand()->getType(); + else if (LoadInst *Load = dyn_cast(Inst)) + Ty = Load->getType(); + else + return nullptr; + + Type *ETy = getEffectiveSCEVType(PointerType::getUnqual(Ty)); + return getSizeOfExpr(ETy, Ty); +} + /// Second step of delinearization: compute the array dimensions Sizes from the /// set of Terms extracted from the memory access function of this SCEVAddRec. -void SCEVAddRecExpr::findArrayDimensions( - ScalarEvolution &SE, SmallVectorImpl &Terms, - SmallVectorImpl &Sizes) const { +void ScalarEvolution::findArrayDimensions(SmallVectorImpl &Terms, + SmallVectorImpl &Sizes, + const SCEV *ElementSize) const { - if (Terms.size() < 2) + if (Terms.size() < 1 || !ElementSize) return; // Early return when Terms do not contain parameters: we do not delinearize @@ -7310,15 +7402,36 @@ void SCEVAddRecExpr::findArrayDimensions( return numberOfTerms(LHS) > numberOfTerms(RHS); }); + ScalarEvolution &SE = *const_cast(this); + + // Divide all terms by the element size. + for (const SCEV *&Term : Terms) { + const SCEV *Q, *R; + SCEVDivision::divide(SE, Term, ElementSize, &Q, &R); + Term = Q; + } + + SmallVector NewTerms; + + // Remove constant factors. + for (const SCEV *T : Terms) + if (const SCEV *NewT = removeConstantFactors(SE, T)) + NewTerms.push_back(NewT); + DEBUG({ dbgs() << "Terms after sorting:\n"; - for (const SCEV *T : Terms) + for (const SCEV *T : NewTerms) dbgs() << *T << "\n"; }); - const SCEV *Zero = SE.getConstant(this->getType(), 0); - const SCEV *One = SE.getConstant(this->getType(), 1); - findArrayDimensionsRec(SE, Terms, Sizes, Zero, One); + if (NewTerms.empty() || + !findArrayDimensionsRec(SE, NewTerms, Sizes)) { + Sizes.clear(); + return; + } + + // The last element to be pushed into Sizes is the size of an element. + Sizes.push_back(ElementSize); DEBUG({ dbgs() << "Sizes:\n"; @@ -7329,15 +7442,15 @@ void SCEVAddRecExpr::findArrayDimensions( /// Third step of delinearization: compute the access functions for the /// Subscripts based on the dimensions in Sizes. -const SCEV *SCEVAddRecExpr::computeAccessFunctions( +void SCEVAddRecExpr::computeAccessFunctions( ScalarEvolution &SE, SmallVectorImpl &Subscripts, SmallVectorImpl &Sizes) const { + // Early exit in case this SCEV is not an affine multivariate function. - const SCEV *Zero = SE.getConstant(this->getType(), 0); - if (!this->isAffine()) - return Zero; + if (Sizes.empty() || !this->isAffine()) + return; - const SCEV *Res = this, *Remainder = Zero; + const SCEV *Res = this; int Last = Sizes.size() - 1; for (int i = Last; i >= 0; i--) { const SCEV *Q, *R; @@ -7353,10 +7466,17 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions( Res = Q; + // Do not record the last subscript corresponding to the size of elements in + // the array. if (i == Last) { - // Do not record the last subscript corresponding to the size of elements - // in the array. - Remainder = R; + + // Bail out if the remainder is too complex. + if (isa(R)) { + Subscripts.clear(); + Sizes.clear(); + return; + } + continue; } @@ -7375,7 +7495,6 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions( for (const SCEV *S : Subscripts) dbgs() << *S << "\n"; }); - return Remainder; } /// Splits the SCEV into two vectors of SCEVs representing the subscripts and @@ -7427,19 +7546,28 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions( /// asking for the SCEV of the memory access with respect to all enclosing /// loops, calling SCEV->delinearize on that and printing the results. -const SCEV * -SCEVAddRecExpr::delinearize(ScalarEvolution &SE, - SmallVectorImpl &Subscripts, - SmallVectorImpl &Sizes) const { +void SCEVAddRecExpr::delinearize(ScalarEvolution &SE, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes, + const SCEV *ElementSize) const { // First step: collect parametric terms. SmallVector Terms; collectParametricTerms(SE, Terms); + if (Terms.empty()) + return; + // Second step: find subscript sizes. - findArrayDimensions(SE, Terms, Sizes); + SE.findArrayDimensions(Terms, Sizes, ElementSize); + + if (Sizes.empty()) + return; // Third step: compute the access functions for each subscript. - const SCEV *Remainder = computeAccessFunctions(SE, Subscripts, Sizes); + computeAccessFunctions(SE, Subscripts, Sizes); + + if (Subscripts.empty()) + return; DEBUG({ dbgs() << "succeeded to delinearize " << *this << "\n"; @@ -7452,8 +7580,6 @@ SCEVAddRecExpr::delinearize(ScalarEvolution &SE, dbgs() << "[" << *S << "]"; dbgs() << "\n"; }); - - return Remainder; } //===----------------------------------------------------------------------===//