SCEV] Do not use induction in isKnownPredicate for simplification umax.

During simplification umax we trigger isKnownPredicate twice. As a first attempt it
tries the induction. To do that it tries to get post increment of SCEV.
Re-writing the SCEV may result in simplification of umax. If the SCEV contains a lot
of umax operations this recursion becomes very slow.

The added test demonstrates the slow behavior.

To resolve this we use only simple ways to check whether the predicate is known.

Reviewers: sanjoy, mkazantsev
Reviewed By: sanjoy
Subscribers: lebedev.ri, javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D46046

llvm-svn: 331949

1 files changed, 6 insertions, 5 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 65c8b855868..47de68c1a35 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -3517,12 +3517,13 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
     //  X umax Y umax Y  -->  X umax Y
     //  X umax Y         -->  X, if X is always greater than Y
-    if (Ops[i] == Ops[i+1] ||
-        isKnownPredicate(ICmpInst::ICMP_UGE, Ops[i], Ops[i+1])) {
-      Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
+    if (Ops[i] == Ops[i + 1] || isKnownViaNonRecursiveReasoning(
+                                    ICmpInst::ICMP_UGE, Ops[i], Ops[i + 1])) {
+      Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2);
       --i; --e;
-    } else if (isKnownPredicate(ICmpInst::ICMP_ULE, Ops[i], Ops[i+1])) {
-      Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
+    } else if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_ULE, Ops[i],
+                                               Ops[i + 1])) {
+      Ops.erase(Ops.begin() + i, Ops.begin() + i + 1);
       --i; --e;
     }