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

[skatkov]

Summary

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.

[lebedev.ri]

include/llvm/Analysis/ScalarEvolution.h

884 ↗

(On Diff #143869)

s/Do not/Does not/ ?

1864 ↗

(On Diff #143869)

Same

[javed.absar]

Would removing 'isKnownViaInduction' have any impact of the number of cases 'analyzeable by scev?

lib/Analysis/ScalarEvolution.cpp

8729 ↗

(On Diff #143869)

Hi Serguei.

I tried to trace the split and code duplication, and I think it would probably be simpler to combine 'isKnownPredicateWithoutInduction' and 'isKnownPredicateWithoutInductionHelper' into just one function (if that's possible).

[skatkov]

In D46046#1077768, @javed.absar wrote:

Would removing 'isKnownViaInduction' have any impact of the number of cases 'analyzeable by scev?

As I understand it should not.
We will not be able to simplify umax in case it could be simplified before due to usage of induction but late analysis should not in general suffer from that.

But let's wait for Sanjoy's opinion on that.

lib/Analysis/ScalarEvolution.cpp

8729 ↗

(On Diff #143869)

Are you ok that we will have a code duplication in isKnownPredicateWithoutInduction and isKnownPredicate?

[javed.absar]

lib/Analysis/ScalarEvolution.cpp

8729 ↗

(On Diff #143869)

Yes I think that would be better for readability.

[skatkov]

@sanjoy , please take a look.

[sanjoy]

I'm a bit worried about adding yet another IsKnownViaXXX codepath (there are already too many!). Can we be a bit smarter in isKnownPredicate so that it avoids the recursive compile time blowup? If that's not possible, can we instead push the logic in isKnownPredicateWithoutInduction into isKnownViaNonRecursiveReasoning?

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

8797 ↗

(On Diff #144279)

This can invoke isKnownPredicate and isKnownViaInduction from inside. And we will have the same problem again. I suggest invoking non-recursive reasoning check from umax/smax.

[skatkov]

Agreed with Max. Restriction of recursion between isKnownPredicate and simplification of umax is too complex.

[skatkov]

@sanjoy, are you ok with the last change?

[sanjoy]

lgtm

test/Analysis/IVUsers/deep_recursion_in_scev.ll

9 ↗

(On Diff #144980)

Minor nit: this test can probably be cleaned up a bit. For instance, instead of the volatile load you can pass in %tmp as a parameter, and you can remove the addressspace qualifiers.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

#endif
   }
 
   // Okay, check to see if the same value occurs in the operand list twice.  If
   // so, delete one.  Since we sorted the list, these values are required to
   // be adjacent.
   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;
     }
 
   if (Ops.size() == 1) return Ops[0];
 
   assert(!Ops.empty() && "Reduced umax down to nothing!");
 
   // Okay, it looks like we really DO need a umax expr.  Check to see if we