Fill in some holes in ScalarEvolution's loop iteration condition

analysis. This allows indvars to emit a simpler loop trip count
expression.


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

1 files changed, 27 insertions, 2 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 7c68f8920e..dcd6558d34 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -960,6 +960,22 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
             return getAddRecExpr(getSignExtendExpr(Start, Ty),
                                  getSignExtendExpr(Step, Ty),
                                  L);
+
+          // Similar to above, only this time treat the step value as unsigned.
+          // This covers loops that count up with an unsigned step.
+          const SCEV *UMul =
+            getMulExpr(CastedMaxBECount,
+                       getTruncateOrZeroExtend(Step, Start->getType()));
+          Add = getAddExpr(Start, UMul);
+          OperandExtendedAdd =
+            getAddExpr(getZeroExtendExpr(Start, WideTy),
+                       getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+                                  getZeroExtendExpr(Step, WideTy)));
+          if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+            // Return the expression with the addrec on the outside.
+            return getAddRecExpr(getSignExtendExpr(Start, Ty),
+                                 getZeroExtendExpr(Step, Ty),
+                                 L);
         }
 
         // If the backedge is guarded by a comparison with the pre-inc value
@@ -4248,7 +4264,7 @@ bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
 
   switch (Pred) {
   default:
-    assert(0 && "Unexpected ICmpInst::Predicate value!");
+    llvm_unreachable("Unexpected ICmpInst::Predicate value!");
     break;
   case ICmpInst::ICMP_SGT:
     Pred = ICmpInst::ICMP_SLT;
@@ -4556,23 +4572,32 @@ ScalarEvolution::isNecessaryCondOperands(ICmpInst::Predicate Pred,
                                          const SCEV *FoundLHS,
                                          const SCEV *FoundRHS) {
   switch (Pred) {
-  default: break;
+  default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
+  case ICmpInst::ICMP_EQ:
+  case ICmpInst::ICMP_NE:
+    if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
+      return true;
+    break;
   case ICmpInst::ICMP_SLT:
+  case ICmpInst::ICMP_SLE:
     if (isKnownPredicate(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
         isKnownPredicate(ICmpInst::ICMP_SGE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_SGT:
+  case ICmpInst::ICMP_SGE:
     if (isKnownPredicate(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
         isKnownPredicate(ICmpInst::ICMP_SLE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_ULT:
+  case ICmpInst::ICMP_ULE:
     if (isKnownPredicate(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
         isKnownPredicate(ICmpInst::ICMP_UGE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_UGT:
+  case ICmpInst::ICMP_UGE:
     if (isKnownPredicate(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
         isKnownPredicate(ICmpInst::ICMP_ULE, RHS, FoundRHS))
       return true;