From 616011418e7460f765469f6347417fa25b5b740b Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Fri, 31 May 2013 06:43:25 +0000 Subject: Fix ScalarEvolution::ComputeExitLimitFromCond for 'or' conditions. Fixes PR16130 - clang produces incorrect code with loop/expression at -O2. This is a 2+ year old bug that's now holding up the release. It's a case where we knowingly made aggressive assumptions about undefined behavior. These assumptions are wrong when SCEV is computing a subexpression that does not directly control the branch. With this fix, we avoid making assumptions in those cases but still optimize the common case. SCEV's trip count computation for exits controlled by 'or' expressions is now analagous to the trip count computation for loops with multiple exits. I had already fixed the multiple exit case to be conservative. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182989 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 86 +++++++++++++++++++++++++--------------- 1 file changed, 54 insertions(+), 32 deletions(-) (limited to 'lib/Analysis') 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(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(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(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(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); -- cgit v1.1