[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV

[lihuang]

Summary

[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV

This is to solve the same slow-compile issue in SCEV that D3127 was trying to solve. But that patch is no longer active.

Without a threshold for mul ops inlining, getMulExpr could have exponential time complexity in the worst case. The case in PR18606 is an example that causes clang to hang.

However, this patch does not completely solve the slow-compile issue in SCEV. The reason is, not completely flattening the SCEV DAG will make SCEVRewriteVisitor another bottleneck, which visits the same SCEV multiple times and could take exponential time to finish. I will fix this in another patch.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

2514

I'd have phrased the limit as a cap on the size of Ops (either Ops.size() directly, or a cap on the number of new elements added to Ops in this loop). Any specific reason why you chose this approach over that?

test/Analysis/ScalarEvolution/max-mulops-inline.ll

24

Can this test case be simplified? For instance, why do we need a loop at all? Why not just have a sequence of multiplication instructions in a single basic block?

[lihuang]

lib/Analysis/ScalarEvolution.cpp

2514

I agree, limiting the size of Ops is the right way. My previous change was wrong, it's limiting the number of ops to be inlined in a single iteration.

test/Analysis/ScalarEvolution/max-mulops-inline.ll

24

Yes I removed the loop. I thought I'd need a loop to trigger SCEV analysis. Thanks!

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

 static cl::opt<bool>
 VerifySCEV("verify-scev",
            cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
 static cl::opt<bool>
     VerifySCEVMap("verify-scev-maps",
                   cl::desc("Verify no dangling value in ScalarEvolution's "
                            "ExprValueMap (slow)"));
 
+static cl::opt<unsigned> MaxMulOpsToInline(
+    "scev-max-mulops-inline", cl::Hidden,
+    cl::desc("Maximum number of multiplication operands to be "
+             "inlined to current multiplication SCEV"),
+    cl::init(1000));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
#endif
   // Skip over the add expression until we get to a multiply.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
     ++Idx;
 
   // If there are mul operands inline them all into this expression.
   if (Idx < Ops.size()) {
     bool DeletedMul = false;
     while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
+      if (Mul->getNumOperands() > MaxMulOpsToInline)
+        break;
       // If we have an mul, expand the mul operands onto the end of the operands
       // list.
       Ops.erase(Ops.begin()+Idx);
       Ops.append(Mul->op_begin(), Mul->op_end());
       DeletedMul = true;
     }
 
     // If we deleted at least one mul, we added operands to the end of the list,

test/Analysis/ScalarEvolution/max-mulops-inline.ll

+; RUN: opt -analyze -scalar-evolution -scev-max-mulops-inline=1 < %s | FileCheck --check-prefix=CHECK1 %s
+; RUN: opt -analyze -scalar-evolution -scev-max-mulops-inline=10 < %s | FileCheck --check-prefix=CHECK10 %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@a = local_unnamed_addr global i32 0, align 4
+@b = local_unnamed_addr global i32 0, align 4
+@c = local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: norecurse nounwind uwtable
+define i32 @main() local_unnamed_addr {
+
+; CHECK1: %mul.1 = mul nsw i32 %mul, %mul
+; CHECK1: -->  ((%mul.lcssa5 * %mul.lcssa5) * (%mul.lcssa5 * %mul.lcssa5))
+
+; CHECK10: %mul.1 = mul nsw i32 %mul, %mul
+; CHECK10: -->  (%mul.lcssa5 * %mul.lcssa5 * %mul.lcssa5 * %mul.lcssa5)
+
+entry:
+  %a.promoted4 = load i32, i32* @a, align 4
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.body3, %entry
+  %mul.lcssa5 = phi i32 [ %a.promoted4, %entry ], [ %mul.5, %for.body3 ]
+  %i.03 = phi i32 [ 0, %entry ], [ %inc5, %for.body3 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %mul.lcssa5, %mul.lcssa5
+  %mul.1 = mul nsw i32 %mul, %mul
+  %mul.2 = mul nsw i32 %mul.1, %mul.1
+  %mul.3 = mul nsw i32 %mul.2, %mul.2
+  %mul.4 = mul nsw i32 %mul.3, %mul.3
+  %mul.5 = mul nsw i32 %mul.4, %mul.4
+  %inc5 = add nsw i32 %i.03, 1
+  %cmp = icmp slt i32 %inc5, 10
+  br i1 %cmp, label %for.cond1.preheader, label %for.end6
+
+for.end6:                                         ; preds = %for.body3
+  %mul.lcssa.lcssa = phi i32 [ %mul.5, %for.body3 ]
+  %inc.lcssa.lcssa = phi i32 [ 6, %for.body3 ]
+  store i32 %mul.lcssa.lcssa, i32* @a, align 4
+  store i32 %inc.lcssa.lcssa, i32* @b, align 4
+  ret i32 0
+}