X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=8fb46dd883b9089c28eed9dd4185a4861c7695e0;hb=dd643f26c43d162e905a07bf0826680aa10f7161;hp=473057caf5a55b184d1926be551adfb5fae1b7ca;hpb=26e4b216c0c065dece616c1c9931252e2a0e40c6;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 473057caf5a..8fb46dd883b 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -83,9 +83,6 @@ #include using namespace llvm; -STATISTIC(NumBruteForceEvaluations, - "Number of brute force evaluations needed to " - "calculate high-order polynomial exit values"); STATISTIC(NumArrayLenItCounts, "Number of trip counts computed with array length"); STATISTIC(NumTripCountsComputed, @@ -644,11 +641,12 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It, // The computation is correct in the face of overflow provided that the // multiplication is performed _after_ the evaluation of the binomial // coefficient. - SCEVHandle Val = - SE.getMulExpr(getOperand(i), - BinomialCoefficient(It, i, SE, - cast(getType()))); - Result = SE.getAddExpr(Result, Val); + SCEVHandle Coeff = BinomialCoefficient(It, i, SE, + cast(getType())); + if (isa(Coeff)) + return Coeff; + + Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff)); } return Result; } @@ -676,9 +674,6 @@ SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty return getAddRecExpr(Operands, AddRec->getLoop()); } - if (isa(Op)) - return new SCEVCouldNotCompute(); - SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); return Result; @@ -694,9 +689,6 @@ SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type * // operands (often constants). This would allow analysis of something like // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } - if (isa(Op)) - return new SCEVCouldNotCompute(); - SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); return Result; @@ -712,9 +704,6 @@ SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type * // operands (often constants). This would allow analysis of something like // this: for (signed char X = 0; X < 100; ++X) { int Y = X; } - if (isa(Op)) - return new SCEVCouldNotCompute(); - SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty); return Result; @@ -743,10 +732,6 @@ SCEVHandle ScalarEvolution::getAddExpr(std::vector &Ops) { // Sort by complexity, this groups all similar expression types together. GroupByComplexity(Ops); - // Could not compute plus anything equals could not compute. - if (isa(Ops.back())) - return new SCEVCouldNotCompute(); - // If there are any constants, fold them together. unsigned Idx = 0; if (SCEVConstant *LHSC = dyn_cast(Ops[0])) { @@ -972,21 +957,6 @@ SCEVHandle ScalarEvolution::getMulExpr(std::vector &Ops) { // Sort by complexity, this groups all similar expression types together. GroupByComplexity(Ops); - if (isa(Ops.back())) { - // CNC * 0 = 0 - for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) { - if (Ops[i]->getSCEVType() != scConstant) - break; - - SCEVConstant *SC = cast(Ops[i]); - if (SC->getValue()->isMinValue(false)) - return SC; - } - - // Otherwise, we can't compute it. - return new SCEVCouldNotCompute(); - } - // If there are any constants, fold them together. unsigned Idx = 0; if (SCEVConstant *LHSC = dyn_cast(Ops[0])) { @@ -1152,9 +1122,6 @@ SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. - if (isa(LHS) || isa(RHS)) - return new SCEVCouldNotCompute(); - SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)]; if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); return Result; @@ -1202,12 +1169,6 @@ SCEVHandle ScalarEvolution::getAddRecExpr(std::vector &Operands, } } - // Refuse to build an AddRec out of SCEVCouldNotCompute. - for (unsigned i = 0, e = Operands.size(); i != e; ++i) { - if (isa(Operands[i])) - return new SCEVCouldNotCompute(); - } - SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, std::vector(Operands.begin(), Operands.end()))]; @@ -1230,21 +1191,6 @@ SCEVHandle ScalarEvolution::getSMaxExpr(std::vector Ops) { // Sort by complexity, this groups all similar expression types together. GroupByComplexity(Ops); - if (isa(Ops.back())) { - // CNC smax +inf = +inf. - for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) { - if (Ops[i]->getSCEVType() != scConstant) - break; - - SCEVConstant *SC = cast(Ops[i]); - if (SC->getValue()->isMaxValue(true)) - return SC; - } - - // Otherwise, we can't compute it. - return new SCEVCouldNotCompute(); - } - // If there are any constants, fold them together. unsigned Idx = 0; if (SCEVConstant *LHSC = dyn_cast(Ops[0])) { @@ -1325,21 +1271,6 @@ SCEVHandle ScalarEvolution::getUMaxExpr(std::vector Ops) { // Sort by complexity, this groups all similar expression types together. GroupByComplexity(Ops); - if (isa(Ops[0])) { - // CNC umax inf = inf. - for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) { - if (Ops[i]->getSCEVType() != scConstant) - break; - - SCEVConstant *SC = cast(Ops[i]); - if (SC->getValue()->isMaxValue(false)) - return SC; - } - - // Otherwise, we can't compute it. - return new SCEVCouldNotCompute(); - } - // If there are any constants, fold them together. unsigned Idx = 0; if (SCEVConstant *LHSC = dyn_cast(Ops[0])) { @@ -1472,6 +1403,7 @@ namespace { void setSCEV(Value *V, const SCEVHandle &H) { bool isNew = Scalars.insert(std::make_pair(V, H)).second; assert(isNew && "This entry already existed!"); + isNew = false; } @@ -1545,7 +1477,7 @@ namespace { /// specified less-than comparison will execute. If not computable, return /// UnknownValue. isSigned specifies whether the less-than is signed. SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, - bool isSigned); + bool isSigned, bool trueWhenEqual); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -1555,7 +1487,13 @@ namespace { /// executesAtLeastOnce - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. - bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS); + bool executesAtLeastOnce(const Loop *L, bool isSigned, bool trueWhenEqual, + SCEV *LHS, SCEV *RHS); + + /// potentialInfiniteLoop - Test whether the loop might jump over the exit value + /// due to wrapping. + bool potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, bool isSigned, + bool trueWhenEqual); /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a @@ -2093,24 +2031,46 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { break; } case ICmpInst::ICMP_SLT: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true); + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, false); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_SGT: { SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, true); + SE.getNotSCEV(RHS), L, true, false); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_ULT: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false); + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false, false); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_UGT: { SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, false); + SE.getNotSCEV(RHS), L, false, false); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_SLE: { + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, true); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_SGE: { + SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), + SE.getNotSCEV(RHS), L, true, true); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_ULE: { + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false, true); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_UGE: { + SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), + SE.getNotSCEV(RHS), L, false, true); if (!isa(TC)) return TC; break; } @@ -2670,6 +2630,11 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { // The divisions must be performed as signed divisions. APInt NegB(-B); APInt TwoA( A << 1 ); + if (TwoA.isMinValue()) { + SCEV *CNC = new SCEVCouldNotCompute(); + return std::make_pair(CNC, CNC); + } + ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA)); ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA)); @@ -2801,6 +2766,7 @@ ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { /// executesAtLeastOnce - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, + bool trueWhenEqual, SCEV *LHS, SCEV *RHS) { BasicBlock *Preheader = L->getLoopPreheader(); BasicBlock *PreheaderDest = L->getHeader(); @@ -2833,20 +2799,36 @@ bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, switch (Cond) { case ICmpInst::ICMP_UGT: - if (isSigned) continue; + if (isSigned || trueWhenEqual) continue; std::swap(PreCondLHS, PreCondRHS); Cond = ICmpInst::ICMP_ULT; break; case ICmpInst::ICMP_SGT: - if (!isSigned) continue; + if (!isSigned || trueWhenEqual) continue; std::swap(PreCondLHS, PreCondRHS); Cond = ICmpInst::ICMP_SLT; break; case ICmpInst::ICMP_ULT: - if (isSigned) continue; + if (isSigned || trueWhenEqual) continue; break; case ICmpInst::ICMP_SLT: - if (!isSigned) continue; + if (!isSigned || trueWhenEqual) continue; + break; + case ICmpInst::ICMP_UGE: + if (isSigned || !trueWhenEqual) continue; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULE; + break; + case ICmpInst::ICMP_SGE: + if (!isSigned || !trueWhenEqual) continue; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLE; + break; + case ICmpInst::ICMP_ULE: + if (isSigned || !trueWhenEqual) continue; + break; + case ICmpInst::ICMP_SLE: + if (!isSigned || !trueWhenEqual) continue; break; default: continue; @@ -2865,11 +2847,46 @@ bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, return false; } +/// potentialInfiniteLoop - Test whether the loop might jump over the exit value +/// due to wrapping around 2^n. +bool ScalarEvolutionsImpl::potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, + bool isSigned, bool trueWhenEqual) { + // Return true when the distance from RHS to maxint > Stride. + + if (!isa(Stride)) + return true; + SCEVConstant *SC = cast(Stride); + + if (SC->getValue()->isZero()) + return true; + if (!trueWhenEqual && SC->getValue()->isOne()) + return false; + + if (!isa(RHS)) + return true; + SCEVConstant *R = cast(RHS); + + if (isSigned) + return true; // XXX: because we don't have an sdiv scev. + + // If negative, it wraps around every iteration, but we don't care about that. + APInt S = SC->getValue()->getValue().abs(); + + APInt Dist = APInt::getMaxValue(R->getValue()->getBitWidth()) - + R->getValue()->getValue(); + + if (trueWhenEqual) + return !S.ult(Dist); + else + return !S.ule(Dist); +} + /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// UnknownValue. SCEVHandle ScalarEvolutionsImpl:: -HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) { +HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, + bool isSigned, bool trueWhenEqual) { // Only handle: "ADDREC < LoopInvariant". if (!RHS->isLoopInvariant(L)) return UnknownValue; @@ -2878,34 +2895,50 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) { return UnknownValue; if (AddRec->isAffine()) { - // FORNOW: We only support unit strides. - SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType()); - if (AddRec->getOperand(1) != One) + SCEVHandle Stride = AddRec->getOperand(1); + if (potentialInfiniteLoop(Stride, RHS, isSigned, trueWhenEqual)) return UnknownValue; - // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant - // m. So, we count the number of iterations in which {n,+,1} < m is true. - // Note that we cannot simply return max(m-n,0) because it's not safe to + // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant + // m. So, we count the number of iterations in which {n,+,s} < m is true. + // Note that we cannot simply return max(m-n,0)/s because it's not safe to // treat m-n as signed nor unsigned due to overflow possibility. // First, we get the value of the LHS in the first iteration: n SCEVHandle Start = AddRec->getOperand(0); - if (executesAtLeastOnce(L, isSigned, - SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) { - // Since we know that the condition is true in order to enter the loop, - // we know that it will run exactly m-n times. - return SE.getMinusSCEV(RHS, Start); - } else { - // Then, we get the value of the LHS in the first iteration in which the - // above condition doesn't hold. This equals to max(m,n). - SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start) - : SE.getUMaxExpr(RHS, Start); - - // Finally, we subtract these two values to get the number of times the - // backedge is executed: max(m,n)-n. - return SE.getMinusSCEV(End, Start); + SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType()); + + // Assuming that the loop will run at least once, we know that it will + // run (m-n)/s times. + SCEVHandle End = RHS; + + if (!executesAtLeastOnce(L, isSigned, trueWhenEqual, + SE.getMinusSCEV(Start, One), RHS)) { + // If not, we get the value of the LHS in the first iteration in which + // the above condition doesn't hold. This equals to max(m,n). + End = isSigned ? SE.getSMaxExpr(RHS, Start) + : SE.getUMaxExpr(RHS, Start); } + + // If the expression is less-than-or-equal to, we need to extend the + // loop by one iteration. + // + // The loop won't actually run (m-n)/s times because the loop iterations + // won't divide evenly. For example, if you have {2,+,5} u< 10 the + // division would equal one, but the loop runs twice putting the + // induction variable at 12. + + if (!trueWhenEqual) + // (Stride - 1) is correct only because we know it's unsigned. + // What we really want is to decrease the magnitude of Stride by one. + Start = SE.getMinusSCEV(Start, SE.getMinusSCEV(Stride, One)); + else + Start = SE.getMinusSCEV(Start, Stride); + + // Finally, we subtract these two values to get the number of times the + // backedge is executed: max(m,n)-n. + return SE.getUDivExpr(SE.getMinusSCEV(End, Start), Stride); } return UnknownValue; @@ -3027,27 +3060,6 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, } } - // Fallback, if this is a general polynomial, figure out the progression - // through brute force: evaluate until we find an iteration that fails the - // test. This is likely to be slow, but getting an accurate trip count is - // incredibly important, we will be able to simplify the exit test a lot, and - // we are almost guaranteed to get a trip count in this case. - ConstantInt *TestVal = ConstantInt::get(getType(), 0); - ConstantInt *EndVal = TestVal; // Stop when we wrap around. - do { - ++NumBruteForceEvaluations; - SCEVHandle Val = evaluateAtIteration(SE.getConstant(TestVal), SE); - if (!isa(Val)) // This shouldn't happen. - return new SCEVCouldNotCompute(); - - // Check to see if we found the value! - if (!Range.contains(cast(Val)->getValue()->getValue())) - return SE.getConstant(TestVal); - - // Increment to test the next index. - TestVal = ConstantInt::get(TestVal->getValue()+1); - } while (TestVal != EndVal); - return new SCEVCouldNotCompute(); }