From 1447f5ca1f59fdbe885df36c74e868267297a59d Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Tue, 16 Dec 2008 08:30:01 +0000 Subject: [PATCH] Generalize support for analyzing loops to include SLE/SGE loop exit conditions and support for non-unit strides with signed exit conditions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61082 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 47 +++++++++---------- .../ScalarEvolution/2008-12-08-FiniteSGE.ll | 1 - .../2008-12-11-SMaxOverflow.ll | 1 - .../2008-12-14-StrideAndSigned.ll | 21 +++++++++ .../ScalarEvolution/2008-12-15-DontUseSDiv.ll | 20 ++++++++ 5 files changed, 64 insertions(+), 26 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/2008-12-14-StrideAndSigned.ll create mode 100644 test/Analysis/ScalarEvolution/2008-12-15-DontUseSDiv.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 2b714de3b3f..142b82d2232 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2924,15 +2924,16 @@ bool ScalarEvolutionsImpl::potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, if (!R) return true; - 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(); + uint32_t Width = R->getValue()->getBitWidth(); + APInt Dist = (isSigned ? APInt::getSignedMaxValue(Width) + : APInt::getMaxValue(Width)) + - R->getValue()->getValue(); + // Because we're looking at distance, we perform an unsigned comparison, + // regardless of the sign of the computation. if (trueWhenEqual) return !S.ult(Dist); else @@ -2961,24 +2962,15 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, // 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. + // + // Assuming that the loop will run at least once, we know that it will + // run (m-n)/s times. // First, we get the value of the LHS in the first iteration: n SCEVHandle Start = AddRec->getOperand(0); 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. // @@ -2986,16 +2978,23 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, // might not divide cleanly. 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. - + SCEVHandle End = SE.getAddExpr(RHS, Stride); 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); + End = SE.getMinusSCEV(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. + // backedge is executed: (max(m,n)-n)/s. + // + // Note that a trip count is always positive. Using SDiv here produces + // wrong answers when Start < End. return SE.getUDivExpr(SE.getMinusSCEV(End, Start), Stride); } diff --git a/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll b/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll index 1bf24d7f487..a9a7c056585 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 index 9703bcb1542..1e8787d0944 100644 --- a/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll +++ b/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll @@ -1,5 +1,4 @@ ; RUN: llvm-as < %s | opt -analyze -scalar-evolution | grep {0 smax} -; XFAIL: * define i32 @f(i32 %c.idx.val) { diff --git a/test/Analysis/ScalarEvolution/2008-12-14-StrideAndSigned.ll b/test/Analysis/ScalarEvolution/2008-12-14-StrideAndSigned.ll new file mode 100644 index 00000000000..e1f2da46570 --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-12-14-StrideAndSigned.ll @@ -0,0 +1,21 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& \ +; RUN: grep {(((-1 \\* %i0) + (100005 smax %i0)) /u 5)} + +define i32 @foo0(i32 %i0) nounwind { +entry: + br label %bb1 + +bb: ; preds = %bb1 + %0 = add i32 %j.0, 1 ; [#uses=1] + %1 = add i32 %i.0, 5 ; [#uses=1] + br label %bb1 + +bb1: ; preds = %bb, %entry + %j.0 = phi i32 [ 0, %entry ], [ %0, %bb ] ; [#uses=2] + %i.0 = phi i32 [ %i0, %entry ], [ %1, %bb ] ; [#uses=2] + %2 = icmp sgt i32 %i.0, 100000 ; [#uses=1] + br i1 %2, label %return, label %bb + +return: ; preds = %bb1 + ret i32 %j.0 +} diff --git a/test/Analysis/ScalarEvolution/2008-12-15-DontUseSDiv.ll b/test/Analysis/ScalarEvolution/2008-12-15-DontUseSDiv.ll new file mode 100644 index 00000000000..ad8914ecdcb --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-12-15-DontUseSDiv.ll @@ -0,0 +1,20 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& grep {/u 5} + +define i8 @foo0(i8 %i0) nounwind { +entry: + br label %bb1 + +bb: ; preds = %bb1 + %0 = add i8 %j.0, 1 ; [#uses=1] + %1 = add i8 %i.0, 5 ; [#uses=1] + br label %bb1 + +bb1: ; preds = %bb, %entry + %j.0 = phi i8 [ 0, %entry ], [ %0, %bb ] ; [#uses=2] + %i.0 = phi i8 [ %i0, %entry ], [ %1, %bb ] ; [#uses=2] + %2 = icmp sgt i8 %i.0, 100 ; [#uses=1] + br i1 %2, label %return, label %bb + +return: ; preds = %bb1 + ret i8 %j.0 +} -- 2.34.1