[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. SCEVRewriteVisiter is another bottleneck that could take exponential time to finish. I will upload another patch to fix it.

[sanjoy]

Hi Li,

I know this sounds stupid, but can you please re-create the revision with llvm-commits added as a subscriber from the very beginning? I don't remember clearly, but at least the last version of phabricator had some issues if you didn't do that.

[lihuang]

Okay, I will re-create a revision.

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
+}