[SCEV] Limit recursion depth of constant evolving

[hliao]

Summary

For a loop body with complicated exit condition evaluation, constant evolving may run out of stack on some platforms, such as Windows. Need to limit the recursion depth.

[atrick]

Rather than a command line option, can you find the recursion limit hit by the LLVM test suite (and SPEC if you have access) and set the limit a bit higher with sufficient comments?

[hliao]

sure, I will schedule that test this night to see whether we need to raise that limit.

[sanjoy]

Please upload with context?

Did you try to see how much work it would be to avoid recursion altogether (and do an iterative scheme instead)?

[hliao]

iterative one is quite straight-forward but I don't see whether it's necessary. 'getConstantEvolvingPHI' is used in 'computeExitCountExhaustively' to evolve loop symbolically to check trip count in brute-force manner. I hardly to see it's widely applied. Ofc, let's check the statistics to see whether that's reasonable.

In addition, if ' getConstantEvolvingPHI' is re-written in iterative scheme, 'EvaluateExpression' needs to be re-written too as the later is predicated from the former and may push the out-of-stack into the later.

[hliao]

I collected the maximum depth of 'getConstantEvolvingPHIOperands' when it returns successfully or otherwise. Here is the statistics collected on SingleSource, MultiSource, and External (spec2000 and spec2006).

• when 'getConstantEvolvingPHIOperands' returns null

MAX-DEPTH-PER-CUNIT	NUM-OF-CUNITS
0	103
1	169
2	653
3	187
4	145
5	76
6	65
7	18
8	94
9	5
10	12
11	10
12	5
13	3

• when 'getConstantEvolvingPHIOperands' return non-null

MAX-DEPTH-PER-CUNIT	NUM-OF-CUNITS
0	159
1	323
2	502
3	218
4	546
5	167
6	100
7	49
8	432
9	46
10	29
11	10
12	4
13	10
16	1
17	3
18	1
19	1

It sounds to me that 32 is a reasonable choice.

[atrick]

Sounds good to me. I don't think you need to add a command line flag.

FWIW, I'm also in favor of moving to iterative solutions, although that does not always eliminate the need for arbitrary thresholds to bound the compute time.

I'm strongly against unbounded recursion anywhere in the compiler.

[hliao]

Sure, I will look into the rewriting them later as we need to rewrite both getConstantEvolvingPHIOperands and EvaluateExpression. The command line option is still preferred as platforms targetting for very different target may found it's necessary to goes deep due to aggressive inlining and other code bloating optimizations. Thanks for the review.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

static cl::opt<unsigned> MulOpsInlineThreshold(
     cl::desc("Threshold for inlining multiplication operands into a SCEV"),
     cl::init(1000));
 
 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));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
static bool canConstantEvolve(Instruction *I, const Loop *L) {
   // are constants, bail early.
   return CanConstantFold(I);
 }
 
 /// getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by
 /// recursing through each instruction operand until reaching a loop header phi.
 static PHINode *
 getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
-                               DenseMap<Instruction *, PHINode *> &PHIMap) {
+                               DenseMap<Instruction *, PHINode *> &PHIMap,
+                               unsigned Depth) {
+  if (Depth > MaxConstantEvolvingDepth)
+    return nullptr;
 
   // Otherwise, we can evaluate this instruction if all of its operands are
   // constant or derived from a PHI node themselves.
   PHINode *PHI = nullptr;
   for (Value *Op : UseInst->operands()) {
     if (isa<Constant>(Op)) continue;
 
     Instruction *OpInst = dyn_cast<Instruction>(Op);
     if (!OpInst || !canConstantEvolve(OpInst, L)) return nullptr;
 
     PHINode *P = dyn_cast<PHINode>(OpInst);
     if (!P)
       // If this operand is already visited, reuse the prior result.
       // We may have P != PHI if this is the deepest point at which the
       // inconsistent paths meet.
       P = PHIMap.lookup(OpInst);
     if (!P) {
       // Recurse and memoize the results, whether a phi is found or not.
       // This recursive call invalidates pointers into PHIMap.
-      P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap);
+      P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap, Depth + 1);
       PHIMap[OpInst] = P;
     }
     if (!P)
       return nullptr;  // Not evolving from PHI
     if (PHI && PHI != P)
       return nullptr;  // Evolving from multiple different PHIs.
     PHI = P;
   }
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || !canConstantEvolve(I, L)) return nullptr;
 
   if (PHINode *PN = dyn_cast<PHINode>(I))
     return PN;
 
   // Record non-constant instructions contained by the loop.
   DenseMap<Instruction *, PHINode *> PHIMap;
-  return getConstantEvolvingPHIOperands(I, L, PHIMap);
+  return getConstantEvolvingPHIOperands(I, L, PHIMap, 0);
 }
 
 /// EvaluateExpression - Given an expression that passes the
 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
 /// in the loop has the value PHIVal.  If we can't fold this expression for some
 /// reason, return null.
 static Constant *EvaluateExpression(Value *V, const Loop *L,
                                     DenseMap<Instruction *, Constant *> &Vals,