From d6dac0eebc2c9c2d9107db9b2e1bdfd231bac535 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Mon, 6 Aug 2007 19:21:00 +0000 Subject: [PATCH] Let scalar-evolution analyze loops with an unsigned comparison for the exit condition. Fixes 1597. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40867 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 52 +++++++++++++------ .../ScalarEvolution/2007-09-06-Unsigned.ll | 29 +++++++++++ 2 files changed, 64 insertions(+), 17 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/2007-09-06-Unsigned.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 879347f7f72..31facd182a7 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1220,8 +1220,9 @@ namespace { /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return - /// UnknownValue. - SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L); + /// UnknownValue. isSigned specifies whether the less-than is signed. + SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, + bool isSigned); /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a @@ -1690,13 +1691,24 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { break; } case ICmpInst::ICMP_SLT: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L); + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_SGT: { SCEVHandle TC = HowManyLessThans(SCEV::getNegativeSCEV(LHS), - SCEV::getNegativeSCEV(RHS), L); + SCEV::getNegativeSCEV(RHS), L, true); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_ULT: { + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_UGT: { + SCEVHandle TC = HowManyLessThans(SCEV::getNegativeSCEV(LHS), + SCEV::getNegativeSCEV(RHS), L, false); if (!isa(TC)) return TC; break; } @@ -2310,7 +2322,7 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { /// specified less-than comparison will execute. If not computable, return /// UnknownValue. SCEVHandle ScalarEvolutionsImpl:: -HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { +HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) { // Only handle: "ADDREC < LoopInvariant". if (!RHS->isLoopInvariant(L)) return UnknownValue; @@ -2367,28 +2379,34 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { switch (Cond) { case ICmpInst::ICMP_UGT: + if (isSigned) return UnknownValue; std::swap(PreCondLHS, PreCondRHS); Cond = ICmpInst::ICMP_ULT; break; case ICmpInst::ICMP_SGT: + if (!isSigned) return UnknownValue; std::swap(PreCondLHS, PreCondRHS); Cond = ICmpInst::ICMP_SLT; break; - default: break; + case ICmpInst::ICMP_ULT: + if (isSigned) return UnknownValue; + break; + case ICmpInst::ICMP_SLT: + if (!isSigned) return UnknownValue; + break; + default: + return UnknownValue; } - if (Cond == ICmpInst::ICMP_SLT) { - if (PreCondLHS->getType()->isInteger()) { - if (RHS != getSCEV(PreCondRHS)) - return UnknownValue; // Not a comparison against 'm'. + if (PreCondLHS->getType()->isInteger()) { + if (RHS != getSCEV(PreCondRHS)) + return UnknownValue; // Not a comparison against 'm'. - if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) - != getSCEV(PreCondLHS)) - return UnknownValue; // Not a comparison against 'n-1'. - } - else return UnknownValue; - } else - return UnknownValue; + if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) + != getSCEV(PreCondLHS)) + return UnknownValue; // Not a comparison against 'n-1'. + } + else return UnknownValue; // cerr << "Computed Loop Trip Count as: " // << // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n"; diff --git a/test/Analysis/ScalarEvolution/2007-09-06-Unsigned.ll b/test/Analysis/ScalarEvolution/2007-09-06-Unsigned.ll new file mode 100644 index 00000000000..1b8dc4dfaae --- /dev/null +++ b/test/Analysis/ScalarEvolution/2007-09-06-Unsigned.ll @@ -0,0 +1,29 @@ +; RUN: llvm-as < %s | opt -scalar-evolution -analyze |& grep "Loop bb: ( -1 + ( -1 * %x) + %y) iterations!" + +define i32 @f(i32 %x, i32 %y) { +entry: + %tmp63 = icmp ult i32 %x, %y ; [#uses=1] + br i1 %tmp63, label %bb.preheader, label %bb8 + +bb.preheader: ; preds = %entry + br label %bb + +bb: ; preds = %bb3, %bb.preheader + %x_addr.0 = phi i32 [ %tmp2, %bb3 ], [ %x, %bb.preheader ] ; [#uses=1] + %tmp2 = add i32 %x_addr.0, 1 ; [#uses=3] + br label %bb3 + +bb3: ; preds = %bb + %tmp6 = icmp ult i32 %tmp2, %y ; [#uses=1] + br i1 %tmp6, label %bb, label %bb8.loopexit + +bb8.loopexit: ; preds = %bb3 + br label %bb8 + +bb8: ; preds = %bb8.loopexit, %entry + %x_addr.1 = phi i32 [ %x, %entry ], [ %tmp2, %bb8.loopexit ] ; [#uses=1] + br label %return + +return: ; preds = %bb8 + ret i32 %x_addr.1 +} -- 2.34.1