Stop creating extraneous smax/umax in SCEV. This removes a regression where we

started complicating many loops ('for' loops, in fact).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53508 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index ab0de275b04df75e73bf8b46fbd90542e81bf512..d3ff2a5afbb353c4a3b45962a2ad47e61b43686e 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1431,6 +1431,10 @@ namespace {
     SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
                                 bool isSigned);
 
+    /// executesAtLeastOnce - Test whether entry to the loop is protected by
+    /// a conditional between LHS and RHS.
+    bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS);
+
     /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
     /// in the header of its containing loop, we know the loop executes a
     /// constant number of times, and the PHI node is just a recurrence
@@ -2612,6 +2616,70 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
   return UnknownValue;
 }
 
+/// executesAtLeastOnce - Test whether entry to the loop is protected by
+/// a conditional between LHS and RHS.
+bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
+                                               SCEV *LHS, SCEV *RHS) {
+  BasicBlock *Preheader = L->getLoopPreheader();
+  BasicBlock *PreheaderDest = L->getHeader();
+  if (Preheader == 0) return false;
+
+  BranchInst *LoopEntryPredicate =
+    dyn_cast<BranchInst>(Preheader->getTerminator());
+  if (!LoopEntryPredicate) return false;
+
+  // This might be a critical edge broken out.  If the loop preheader ends in
+  // an unconditional branch to the loop, check to see if the preheader has a
+  // single predecessor, and if so, look for its terminator.
+  while (LoopEntryPredicate->isUnconditional()) {
+    PreheaderDest = Preheader;
+    Preheader = Preheader->getSinglePredecessor();
+    if (!Preheader) return false;  // Multiple preds.
+    
+    LoopEntryPredicate =
+      dyn_cast<BranchInst>(Preheader->getTerminator());
+    if (!LoopEntryPredicate) return false;
+  }
+
+  ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
+  if (!ICI) return false;
+
+  // Now that we found a conditional branch that dominates the loop, check to
+  // see if it is the comparison we are looking for.
+  Value *PreCondLHS = ICI->getOperand(0);
+  Value *PreCondRHS = ICI->getOperand(1);
+  ICmpInst::Predicate Cond;
+  if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
+    Cond = ICI->getPredicate();
+  else
+    Cond = ICI->getInversePredicate();
+
+  switch (Cond) {
+  case ICmpInst::ICMP_UGT:
+    if (isSigned) return false;
+    std::swap(PreCondLHS, PreCondRHS);
+    Cond = ICmpInst::ICMP_ULT;
+    break;
+  case ICmpInst::ICMP_SGT:
+    if (!isSigned) return false;
+    std::swap(PreCondLHS, PreCondRHS);
+    Cond = ICmpInst::ICMP_SLT;
+    break;
+  case ICmpInst::ICMP_ULT:
+    if (isSigned) return false;
+    break;
+  case ICmpInst::ICMP_SLT:
+    if (!isSigned) return false;
+    break;
+  default:
+    return false;
+  }
+
+  if (!PreCondLHS->getType()->isInteger()) return false;
+
+  return LHS == getSCEV(PreCondLHS) && RHS == getSCEV(PreCondRHS);
+}
+
 /// HowManyLessThans - Return the number of times a backedge containing the
 /// specified less-than comparison will execute.  If not computable, return
 /// UnknownValue.
@@ -2640,12 +2708,17 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
 
     // Then, 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).
-    SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
-                              : SE.getUMaxExpr(RHS, Start);
-
-    // Finally, we subtract these two values to get the number of times the
-    // backedge is executed: max(m,n)-n.
-    return SE.getMinusSCEV(End, Start);
+    if (executesAtLeastOnce(L, isSigned,
+                            SE.getMinusSCEV(AddRec->getOperand(0), One), RHS))
+      return SE.getMinusSCEV(RHS, Start);
+    else {
+      SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
+                                : SE.getUMaxExpr(RHS, Start);
+
+      // Finally, we subtract these two values to get the number of times the
+      // backedge is executed: max(m,n)-n.
+      return SE.getMinusSCEV(End, Start);
+    }
   }
 
   return UnknownValue;

diff --git a/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll b/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll
index 23ffc650b0d5ba62d0ab017be49d1c3067b031d3..e725852cea1ea82ca7300ca7fbbaa93d4fdd638b 100644 (file)
--- a/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll
+++ b/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop bb: ( -1 + ( -1 \\*  %x) + (( 1 +  %x) umax  %y)) iterations!}
+; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop bb: ( -1 + ( -1 \\*  %x) +  %y) iterations!}
 ; PR1597
 
 define i32 @f(i32 %x, i32 %y) {

diff --git a/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll
new file mode 100644 (file)
index 0000000..a0fcad7
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll
@@ -0,0 +1,36 @@
+; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& not grep smax
+; PR2261
+
+@lut = common global [256 x i8] zeroinitializer, align 32              ; <[256 x i8]*> [#uses=1]
+
+define void @foo(i32 %count, i32* %srcptr, i32* %dstptr) nounwind  {
+entry:
+       icmp sgt i32 %count, 0          ; <i1>:0 [#uses=1]
+       br i1 %0, label %bb.nph, label %return
+
+bb.nph:                ; preds = %entry
+       br label %bb
+
+bb:            ; preds = %bb1, %bb.nph
+       %j.01 = phi i32 [ %8, %bb1 ], [ 0, %bb.nph ]            ; <i32> [#uses=1]
+       load i32* %srcptr, align 4              ; <i32>:1 [#uses=2]
+       and i32 %1, 255         ; <i32>:2 [#uses=1]
+       and i32 %1, -256                ; <i32>:3 [#uses=1]
+       getelementptr [256 x i8]* @lut, i32 0, i32 %2           ; <i8*>:4 [#uses=1]
+       load i8* %4, align 1            ; <i8>:5 [#uses=1]
+       zext i8 %5 to i32               ; <i32>:6 [#uses=1]
+       or i32 %6, %3           ; <i32>:7 [#uses=1]
+       store i32 %7, i32* %dstptr, align 4
+       add i32 %j.01, 1                ; <i32>:8 [#uses=2]
+       br label %bb1
+
+bb1:           ; preds = %bb
+       icmp slt i32 %8, %count         ; <i1>:9 [#uses=1]
+       br i1 %9, label %bb, label %bb1.return_crit_edge
+
+bb1.return_crit_edge:          ; preds = %bb1
+       br label %return
+
+return:                ; preds = %bb1.return_crit_edge, %entry
+       ret void
+}

diff --git a/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll
new file mode 100644 (file)
index 0000000..5501ee2
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll
@@ -0,0 +1,30 @@
+; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& not grep smax
+; PR2070
+
+define i32 @a(i32 %x) nounwind  {
+entry:
+       icmp sgt i32 %x, 1              ; <i1>:0 [#uses=1]
+       br i1 %0, label %bb.nph, label %bb2
+
+bb.nph:                ; preds = %entry
+       br label %bb
+
+bb:            ; preds = %bb1, %bb.nph
+       %z.02 = phi i32 [ %1, %bb1 ], [ 1, %bb.nph ]            ; <i32> [#uses=1]
+       %i.01 = phi i32 [ %2, %bb1 ], [ 1, %bb.nph ]            ; <i32> [#uses=2]
+       mul i32 %z.02, %i.01            ; <i32>:1 [#uses=2]
+       add i32 %i.01, 1                ; <i32>:2 [#uses=2]
+       br label %bb1
+
+bb1:           ; preds = %bb
+       icmp slt i32 %2, %x             ; <i1>:3 [#uses=1]
+       br i1 %3, label %bb, label %bb1.bb2_crit_edge
+
+bb1.bb2_crit_edge:             ; preds = %bb1
+       %.lcssa = phi i32 [ %1, %bb1 ]          ; <i32> [#uses=1]
+       br label %bb2
+
+bb2:           ; preds = %bb1.bb2_crit_edge, %entry
+       %z.0.lcssa = phi i32 [ %.lcssa, %bb1.bb2_crit_edge ], [ 1, %entry ]             ; <i32> [#uses=1]
+       ret i32 %z.0.lcssa
+}