[SCEV] Introduce add operation inlining limit

[dfukalov]

Summary

Inlining in getAddExpr() can cause abnormal computational time in some cases. new parameter -scev-addops-inline-threshold is intruduced with default value 500.

[dfukalov]

ping...

[sanjoy]

LGTM

I generally don't like thresholds, but I can't immediately think of anything better than AddOpsInlineThreshold.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

VerifySCEVMap("verify-scev-maps",
                   cl::desc("Verify no dangling value in ScalarEvolution's "
                            "ExprValueMap (slow)"));
 
 static cl::opt<unsigned> MulOpsInlineThreshold(
     "scev-mulops-inline-threshold", cl::Hidden,
     cl::desc("Threshold for inlining multiplication operands into a SCEV"),
     cl::init(1000));
 
+static cl::opt<unsigned> AddOpsInlineThreshold(
+    "scev-addops-inline-threshold", cl::Hidden,
+    cl::desc("Threshold for inlining multiplication operands into a SCEV"),
+    cl::init(500));
+
 static cl::opt<unsigned>
     MaxCompareDepth("scalar-evolution-max-compare-depth", cl::Hidden,
                     cl::desc("Maximum depth of recursive compare complexity"),
                     cl::init(32));
 
 static cl::opt<unsigned> MaxConstantEvolvingDepth(
     "scalar-evolution-max-constant-evolving-depth", cl::Hidden,
     cl::desc("Maximum depth of recursive constant evolving"), cl::init(32));
#endif
   // Skip past any other cast SCEVs.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
     ++Idx;
 
   // If there are add operands they would be next.
   if (Idx < Ops.size()) {
     bool DeletedAdd = false;
     while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
+      if (Ops.size() > AddOpsInlineThreshold ||
+          Add->getNumOperands() > AddOpsInlineThreshold)
+        break;
       // If we have an add, expand the add operands onto the end of the operands
       // list.
       Ops.erase(Ops.begin()+Idx);
       Ops.append(Add->op_begin(), Add->op_end());
       DeletedAdd = true;
     }
 
     // If we deleted at least one add, we added operands to the end of the list,

llvm/trunk/test/Analysis/ScalarEvolution/max-addops-inline.ll

+; RUN: opt -analyze -scalar-evolution -scev-addops-inline-threshold=1 < %s | FileCheck --check-prefix=CHECK1 %s
+; RUN: opt -analyze -scalar-evolution -scev-addops-inline-threshold=10 < %s | FileCheck --check-prefix=CHECK10 %s
+
+define i32 @foo(i64 %p0, i32 %p1) {
+; CHECK1: %add2 = add nsw i32 %mul1, %add
+; CHECK1-NEXT: -->  ((trunc i64 %p0 to i32) * (1 + (trunc i64 %p0 to i32)) * (1 + %p1))
+
+; CHECK10: %add2 = add nsw i32 %mul1, %add
+; CHECK10-NEXT: -->  ((trunc i64 %p0 to i32) * (1 + ((trunc i64 %p0 to i32) * (1 + %p1)) + %p1))
+entry:
+  %tr = trunc i64 %p0 to i32
+  %mul = mul nsw i32 %tr, %p1
+  %add = add nsw i32 %mul, %tr
+  %mul1 = mul nsw i32 %add, %tr
+  %add2 = add nsw i32 %mul1, %add
+  ret i32 %add2
+}