[SCEV] Prohibit SCEV transformations for huge SCEVs

[mkazantsev]

Summary

Currently SCEV attempts to limit transformations so that they do not work with
big SCEVs (that may take almost infinite compile time). But for this, it uses heuristics
such as recursion depth and number of operands, which do not give us a guarantee
that we don't actually have big SCEVs. This situation is still possible, though it is not
likely to happen. However, the bug PR33494 showed a bunch of simple corner case
tests where we still produce huge SCEVs, even not reaching big recursion depth etc.

This patch introduces a concept of 'huge' SCEVs. A SCEV is huge if its expression
size (intoduced in D35989) exceeds some threshold value. We prohibit optimizing
transformations if any of SCEVs we are dealing with is huge. This gives us a reliable
check that we don't spend too much time working with them.

As the next step, we can possibly get rid of old limiting mechanisms, such as recursion
depth thresholds.

[mkazantsev]

Reused smart version of any_of

[mkazantsev]

Some tests from https://bugs.llvm.org/show_bug.cgi?id=33494 fail when huge expressions threshold is set to low values (like 100). It is not automatically this patch's problem, but this should be fixed before this is merged.

[mkazantsev]

UPD: The mentioned crash is actually assertion failure on cast<SCEVAddRecExpr>. Something happens to be non-addrec after we limit transformations by huge scevs. This bug also should be (in theory) reproducible without this patch, but I don't have an example.

[mkazantsev]

We need it to fix PR40292. Reclaiming.

[mkazantsev]

Updated test to preserve current behavior (it creates *really* big SCEVs in test_05).

[reames]

You need some tests highlighting the limit working in practice. These can be easily written by using non-default threshold values.

lib/Analysis/ScalarEvolution.cpp

858 ↗

(On Diff #181726)

Please add a comment here explaining what "huge" means and is used for. This the obvious point for someone reading the code to try to find the explanation.

862 ↗

(On Diff #181726)

Probably better to use an ArrayRef as the argument.

2909 ↗

(On Diff #181726)

Not related to your review, but I notice inconsistency about whether we merge adjacent constants before or after the bailout check.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

862 ↗

(On Diff #181726)

SCEV uses SmallVectorImpl to pass argument lists in all places. What you propose is inconsistent with the current code. We can do a global refactoring if there is any benefit from it.

2909 ↗

(On Diff #181726)

We can change that separately.

[mkazantsev]

Added comments.

[reames]

Still needs tests

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

862 ↗

(On Diff #181726)

SCEV uses SmallVectorImpl in many places because it needs to modify the container in place (e.g. getAddExpr will reduce the size of SmallVectorImpl in place when folding constants). Functions that do not modify the input sequence in place should use ArrayRef.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

862 ↗

(On Diff #181726)

It makes sense, yet it was untrue for SCEV code. I've commited rL352466 to leverage this. Will rebase on top of it.

[mkazantsev]

Added some tests to show that it works, rebased, replaced with ArrayRef.

[reames]

LGTM

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

MaxExtDepth("scalar-evolution-max-ext-depth", cl::Hidden,
                 cl::desc("Maximum depth of recursive SExt/ZExt"),
                 cl::init(8));
 
 static cl::opt<unsigned>
     MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden,
                   cl::desc("Max coefficients in AddRec during evolving"),
                   cl::init(8));
 
+static cl::opt<unsigned>
+    HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden,
+                  cl::desc("Size of the expression which is considered huge"),
+                  cl::init(4096));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
static inline int sizeOfSCEV(const SCEV *S) {
   };
 
   FindSCEVSize F;
   SCEVTraversal<FindSCEVSize> ST(F);
   ST.visitAll(S);
   return F.Size;
 }
 
+/// Returns true if the subtree of \p S contains at least HugeExprThreshold
+/// nodes.
+static bool isHugeExpression(const SCEV *S) {
+  return S->getExpressionSize() >= HugeExprThreshold;
+}
+
+/// Returns true of \p Ops contains a huge SCEV (see definition above).
+static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) {
+  return any_of(Ops, isHugeExpression);
+}
+
 namespace {
 
 struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
 public:
   // Computes the Quotient and Remainder of the division of Numerator by
   // Denominator.
   static void divide(ScalarEvolution &SE, const SCEV *Numerator,
                      const SCEV *Denominator, const SCEV **Quotient,
if (LHSC->getValue()->isZero()) {
       Ops.erase(Ops.begin());
       --Idx;
     }
 
     if (Ops.size() == 1) return Ops[0];
   }
 
   // Limit recursion calls depth.
-  if (Depth > MaxArithDepth)
+  if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateAddExpr(Ops, Flags);
 
   // Okay, check to see if the same value occurs in the operand list more than
   // once.  If so, merge them together into an multiply expression.  Since we
   // sorted the list, these values are required to be adjacent.
   Type *Ty = Ops[0]->getType();
   bool FoundMatch = false;
   for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)

 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
   // Limit recursion calls depth.
-  if (Depth > MaxArithDepth)
+  if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateMulExpr(Ops, Flags);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
     if (Ops.size() == 2)
       // C1*(C2+V) -> C1*C2 + C1*V
for (unsigned OtherIdx = Idx+1;
       const SCEVAddRecExpr *OtherAddRec =
         dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
       if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
         continue;
 
       // Limit max number of arguments to avoid creation of unreasonably big
       // SCEVAddRecs with very complex operands.
       if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
-          MaxAddRecSize)
+          MaxAddRecSize || isHugeExpression(AddRec) ||
+          isHugeExpression(OtherAddRec))
         continue;
 
       bool Overflow = false;
       Type *Ty = AddRec->getType();
       bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
       SmallVector<const SCEV*, 7> AddRecOps;
       for (int x = 0, xe = AddRec->getNumOperands() +
              OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {

llvm/trunk/test/Analysis/ScalarEvolution/huge_expression_limit.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -scalar-evolution -scalar-evolution-huge-expr-threshold=1 | FileCheck %s
+
+define void @test(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
+; CHECK-LABEL: 'test'
+; CHECK-NEXT:  Classifying expressions for: @test
+; CHECK-NEXT:    %add1 = add i32 %a, %b
+; CHECK-NEXT:    --> (%a + %b) U: full-set S: full-set
+; CHECK-NEXT:    %add2 = add i32 %add1, %c
+; CHECK-NEXT:    --> ((%a + %b) + %c) U: full-set S: full-set
+; CHECK-NEXT:    %add3 = add i32 %add2, %d
+; CHECK-NEXT:    --> (((%a + %b) + %c) + %d) U: full-set S: full-set
+; CHECK-NEXT:    %add4 = add i32 %add3, %e
+; CHECK-NEXT:    --> ((((%a + %b) + %c) + %d) + %e) U: full-set S: full-set
+; CHECK-NEXT:    %add5 = add i32 %add4, %f
+; CHECK-NEXT:    --> (((((%a + %b) + %c) + %d) + %e) + %f) U: full-set S: full-set
+; CHECK-NEXT:    %mul1 = mul i32 %a, %b
+; CHECK-NEXT:    --> (%a * %b) U: full-set S: full-set
+; CHECK-NEXT:    %mul2 = mul i32 %mul1, %c
+; CHECK-NEXT:    --> ((%a * %b) * %c) U: full-set S: full-set
+; CHECK-NEXT:    %mul3 = mul i32 %mul2, %d
+; CHECK-NEXT:    --> (((%a * %b) * %c) * %d) U: full-set S: full-set
+; CHECK-NEXT:    %mul4 = mul i32 %mul3, %e
+; CHECK-NEXT:    --> ((((%a * %b) * %c) * %d) * %e) U: full-set S: full-set
+; CHECK-NEXT:    %mul5 = mul i32 %mul4, %f
+; CHECK-NEXT:    --> (((((%a * %b) * %c) * %d) * %e) * %f) U: full-set S: full-set
+; CHECK-NEXT:  Determining loop execution counts for: @test
+;
+  %add1 = add i32 %a, %b
+  %add2 = add i32 %add1, %c
+  %add3 = add i32 %add2, %d
+  %add4 = add i32 %add3, %e
+  %add5 = add i32 %add4, %f
+
+  %mul1 = mul i32 %a, %b
+  %mul2 = mul i32 %mul1, %c
+  %mul3 = mul i32 %mul2, %d
+  %mul4 = mul i32 %mul3, %e
+  %mul5 = mul i32 %mul4, %f
+  ret void
+}

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/bin_power.ll

-; RUN: opt < %s -loop-reduce -S | FileCheck %s
+; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s
 
 target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Show that the b^2 is expanded correctly.
 define i32 @test_01(i32 %a) {
 ; CHECK-LABEL: @test_01
 ; CHECK:       entry: