diff options
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 10 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 86 |
2 files changed, 60 insertions, 36 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 306549f..349447f 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -453,7 +453,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeExitLimitFromICmp - Compute the number of times the backedge of /// the specified loop will execute if its exit condition were a conditional @@ -461,7 +462,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the @@ -483,7 +485,7 @@ namespace llvm { /// HowFarToZero - Return the number of times an exit condition comparing /// the specified value to zero will execute. If not computable, return /// CouldNotCompute. - ExitLimit HowFarToZero(const SCEV *V, const Loop *L); + ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); /// HowFarToNonZero - Return the number of times an exit condition checking /// the specified value for nonzero will execute. If not computable, return @@ -495,7 +497,7 @@ namespace llvm { /// computable, return CouldNotCompute. isSigned specifies whether the /// less-than is signed. ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned); + const Loop *L, bool isSigned, bool IsSubExpr); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 6ea915f..d26ec9a 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4382,26 +4382,36 @@ ScalarEvolution::ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock) { // Proceed to the next level to examine the exit condition expression. return ComputeExitLimitFromCond(L, ExitBr->getCondition(), ExitBr->getSuccessor(0), - ExitBr->getSuccessor(1)); + ExitBr->getSuccessor(1), + /*IsSubExpr=*/false); } /// ComputeExitLimitFromCond - Compute the number of times the /// backedge of the specified loop will execute if its exit condition /// were a conditional branch of ExitCond, TBB, and FBB. +/// +/// @param IsSubExpr is true if ExitCond does not directly control the exit +/// branch. In this case, we cannot assume that the loop only exits when the +/// condition is true and cannot infer that failing to meet the condition prior +/// to integer wraparound results in undefined behavior. ScalarEvolution::ExitLimit ScalarEvolution::ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB) { + BasicBlock *FBB, + bool IsSubExpr) { // Check if the controlling expression for this loop is an And or Or. if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) { if (BO->getOpcode() == Instruction::And) { // Recurse on the operands of the and. - ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB); - ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB); + bool EitherMayExit = L->contains(TBB); + ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB, + IsSubExpr || EitherMayExit); + ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB, + IsSubExpr || EitherMayExit); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (L->contains(TBB)) { + if (EitherMayExit) { // Both conditions must be true for the loop to continue executing. // Choose the less conservative count. if (EL0.Exact == getCouldNotCompute() || @@ -4429,11 +4439,14 @@ ScalarEvolution::ComputeExitLimitFromCond(const Loop *L, } if (BO->getOpcode() == Instruction::Or) { // Recurse on the operands of the or. - ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB); - ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB); + bool EitherMayExit = L->contains(FBB); + ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB, + IsSubExpr || EitherMayExit); + ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB, + IsSubExpr || EitherMayExit); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (L->contains(FBB)) { + if (EitherMayExit) { // Both conditions must be false for the loop to continue executing. // Choose the less conservative count. if (EL0.Exact == getCouldNotCompute() || @@ -4464,7 +4477,7 @@ ScalarEvolution::ComputeExitLimitFromCond(const Loop *L, // With an icmp, it may be feasible to compute an exact backedge-taken count. // Proceed to the next level to examine the icmp. if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) - return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB); + return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, IsSubExpr); // Check for a constant condition. These are normally stripped out by // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to @@ -4490,7 +4503,8 @@ ScalarEvolution::ExitLimit ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB) { + BasicBlock *FBB, + bool IsSubExpr) { // If the condition was exit on true, convert the condition to exit on false ICmpInst::Predicate Cond; @@ -4542,7 +4556,7 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L, switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L); + ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } @@ -4553,24 +4567,24 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L, break; } case ICmpInst::ICMP_SLT: { - ExitLimit EL = HowManyLessThans(LHS, RHS, L, true); + ExitLimit EL = HowManyLessThans(LHS, RHS, L, true, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_SGT: { ExitLimit EL = HowManyLessThans(getNotSCEV(LHS), - getNotSCEV(RHS), L, true); + getNotSCEV(RHS), L, true, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_ULT: { - ExitLimit EL = HowManyLessThans(LHS, RHS, L, false); + ExitLimit EL = HowManyLessThans(LHS, RHS, L, false, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_UGT: { ExitLimit EL = HowManyLessThans(getNotSCEV(LHS), - getNotSCEV(RHS), L, false); + getNotSCEV(RHS), L, false, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } @@ -5439,7 +5453,7 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { /// effectively V != 0. We know and take advantage of the fact that this /// expression only being used in a comparison by zero context. ScalarEvolution::ExitLimit -ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { +ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr) { // If the value is a constant if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { // If the value is already zero, the branch will execute zero times. @@ -5537,19 +5551,20 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { } // If the recurrence is known not to wraparound, unsigned divide computes the - // back edge count. We know that the value will either become zero (and thus - // the loop terminates), that the loop will terminate through some other exit - // condition first, or that the loop has undefined behavior. This means - // we can't "miss" the exit value, even with nonunit stride. + // back edge count. (Ideally we would have an "isexact" bit for udiv). We know + // that the value will either become zero (and thus the loop terminates), that + // the loop will terminate through some other exit condition first, or that + // the loop has undefined behavior. This means we can't "miss" the exit + // value, even with nonunit stride. // - // FIXME: Prove that loops always exhibits *acceptable* undefined - // behavior. Loops must exhibit defined behavior until a wrapped value is - // actually used. So the trip count computed by udiv could be smaller than the - // number of well-defined iterations. - if (AddRec->getNoWrapFlags(SCEV::FlagNW)) { - // FIXME: We really want an "isexact" bit for udiv. + // This is only valid for expressions that directly compute the loop exit. It + // is invalid for subexpressions in which the loop may exit through this + // branch even if this subexpression is false. In that case, the trip count + // computed by this udiv could be smaller than the number of well-defined + // iterations. + if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); - } + // Then, try to solve the above equation provided that Start is constant. if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), @@ -6315,9 +6330,14 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start, /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// CouldNotCompute. +/// +/// @param IsSubExpr is true when the LHS < RHS condition does not directly +/// control the branch. In this case, we can only compute an iteration count for +/// a subexpression that cannot overflow before evaluating true. ScalarEvolution::ExitLimit ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned) { + const Loop *L, bool isSigned, + bool IsSubExpr) { // Only handle: "ADDREC < LoopInvariant". if (!isLoopInvariant(RHS, L)) return getCouldNotCompute(); @@ -6326,10 +6346,12 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, return getCouldNotCompute(); // Check to see if we have a flag which makes analysis easy. - bool NoWrap = isSigned ? - AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNW)) : - AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNW)); - + bool NoWrap = false; + if (!IsSubExpr) { + NoWrap = AddRec->getNoWrapFlags( + (SCEV::NoWrapFlags)(((isSigned ? SCEV::FlagNSW : SCEV::FlagNUW)) + | SCEV::FlagNW)); + } if (AddRec->isAffine()) { unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); const SCEV *Step = AddRec->getStepRecurrence(*this); |