diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 30 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll | 1 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll | 27 |
3 files changed, 42 insertions, 16 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 2b714de3b3..1dd5026d74 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2924,8 +2924,12 @@ bool ScalarEvolutionsImpl::potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, if (!R) return true; - if (isSigned) + if (isSigned) { + if (SC->getValue()->isOne()) + return R->getValue()->isMaxValue(true); + 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(); @@ -2971,14 +2975,6 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, // 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. // @@ -2987,12 +2983,16 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, // 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); + if (trueWhenEqual) + End = SE.getAddExpr(End, One); + + 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(End, Start) + : SE.getUMaxExpr(End, Start); + } // Finally, we subtract these two values to get the number of times the // backedge is executed: max(m,n)-n. diff --git a/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll b/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll index 1bf24d7f48..a9a7c05658 100644 --- a/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll +++ b/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll @@ -1,5 +1,4 @@ ; RUN: llvm-as < %s | opt -analyze -scalar-evolution | grep {255 iterations} -; XFAIL: * define i32 @foo(i32 %x, i32 %y, i32* %lam, i32* %alp) nounwind { bb1.thread: diff --git a/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll b/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll new file mode 100644 index 0000000000..1e8787d094 --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll @@ -0,0 +1,27 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution | grep {0 smax} + +define i32 @f(i32 %c.idx.val) { + +bb2: + %k.018 = add i32 %c.idx.val, -1 ; <i32> [#uses=2] + %a14 = icmp slt i32 %k.018, 0 ; <i1> [#uses=1] + br i1 %a14, label %bb19, label %bb16.preheader + +bb16.preheader: + %k.019 = phi i32 [ %k.0, %bb18 ], [ %k.018, %bb2 ] ; <i32> [#uses=5] + %x = phi i32 [ 0, %bb2 ], [ %x.1, %bb18] + br label %bb18 + +bb18: ; preds = %bb18.loopexit + %x.1 = add i32 %x, 1 + %k.0 = add i32 %k.019, -1 ; <i32> [#uses=2] + %a107 = icmp slt i32 %k.0, 0 ; <i1> [#uses=1] + br i1 %a107, label %bb18.bb19_crit_edge, label %bb16.preheader + +bb18.bb19_crit_edge: + ret i32 %x + +bb19: + ret i32 0 + +} |