[SimplifyCFG] limit recursion depth when speculating instructions (PR26308)

[spatel]

Summary

This is a fix for:
https://llvm.org/bugs/show_bug.cgi?id=26308

With the switch to using the TTI cost model in:
http://reviews.llvm.org/rL228826
...it became possible to hit a zero-cost cycle of instructions (gep -> phi -> gep...), so we need a cap for the recursion in DominatesMergePoint().

A recursion depth parameter was already added for a different reason in:
http://reviews.llvm.org/rL255660
...so I think we just need to set a limit.

I pulled "10" out of the air and made it an independent parameter that we can play with. It might be higher than it needs to be given the currently low default value of PHINodeFoldingThreshold (2). That's the starting cost value that we enter the recursion with, and most instructions have cost set to TCC_Basic (1), so I don't think we're going to speculate more than 2 instructions with the current parameters.

[majnemer]

LGTM

We can always adjust 10 if it is too low.

[• dberlin]

Errr, rather than limit recursion depth, why not just keep track of what's
visited and avoid the cycles?

(You could also cheaply build sccs of the instruction and it's uses, and
decide what to do for each SCC as a whole, which would avoid this issue as
well)

[majnemer]

In D16637#337461, @dberlin wrote:

Errr, rather than limit recursion depth, why not just keep track of what's
visited and avoid the cycles?

(You could also cheaply build sccs of the instruction and it's uses, and
decide what to do for each SCC as a whole, which would avoid this issue as
well)

We run DominatesMergePoint on every two entry phi node. Using a set of visited blocks would still be pretty expensive because, in the worst case, DominatesMergePoint might recurse back to the entry node if there are a lot of cheap BBs. I think it would make sense to have a depth limit to handle such pathological cases.

[• dberlin]

If you do it on literally every two entry phi nodes, why is the answer not:

Number each node of dominator tree with depth in dom tree (IE level).
Process dominator tree in level order, visiting all nodes of a given level
before the next deeper level:

Try to speculate a given phi node.
Stop anytime you hit a phi node with a level above you above you (because

you will have already speculated it if you could).

Track visited phi nodes to avoid cycles.

Or something similar.
Over time, we seem to expand a lot of lazy-walking optimizations to do
these "walk possibly everything backwards" types of algorithms, and at the
point we want to walk *everything of a certain type* there is no point in
doing it lazily.

[majnemer]

In D16637#337486, @dberlin wrote:

If you do it on literally every two entry phi nodes, why is the answer not:

Number each node of dominator tree with depth in dom tree (IE level).
Process dominator tree in level order, visiting all nodes of a given level
before the next deeper level:

Try to speculate a given phi node.
Stop anytime you hit a phi node with a level above you above you (because

you will have already speculated it if you could).

Track visited phi nodes to avoid cycles.

Or something similar.
Over time, we seem to expand a lot of lazy-walking optimizations to do
these "walk possibly everything backwards" types of algorithms, and at the
point we want to walk *everything of a certain type* there is no point in
doing it lazily.

You will find no disagreement on this point from me :)
On the other hand, there is no reason not to apply this patch. The code as-written obviously intended to do something with this recursion depth counter, it's disuse was an oversight.

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<bool> MergeCondStoresAggressively(
     cl::desc("When merging conditional stores, do so even if the resultant "
              "basic blocks are unlikely to be if-converted as a result"));
 
 static cl::opt<bool> SpeculateOneExpensiveInst(
     "speculate-one-expensive-inst", cl::Hidden, cl::init(true),
     cl::desc("Allow exactly one expensive instruction to be speculatively "
              "executed"));
 
+static cl::opt<unsigned> MaxSpeculationDepth(
+    "max-speculation-depth", cl::Hidden, cl::init(10),
+    cl::desc("Limit maximum recursion depth when calculating costs of "
+             "speculatively executed instructions"));
+
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 

 /// After this function returns, CostRemaining is decreased by the cost of
 /// V plus its non-dominating operands.  If that cost is greater than
 /// CostRemaining, false is returned and CostRemaining is undefined.
 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
                                 SmallPtrSetImpl<Instruction*> *AggressiveInsts,
                                 unsigned &CostRemaining,
                                 const TargetTransformInfo &TTI,
                                 unsigned Depth = 0) {
+  // It is possible to hit a zero-cost cycle (phi/gep instructions for example),
+  // so limit the recursion depth.
+  // TODO: While this recursion limit does prevent pathological behavior, it
+  // would be better to track visited instructions to avoid cycles.
+  if (Depth == MaxSpeculationDepth)
+    return false;
+
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) {
     // Non-instructions all dominate instructions, but not all constantexprs
     // can be executed unconditionally.
     if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
       if (C->canTrap())
         return false;
     return true;

llvm/trunk/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 
 l6:
   %r = phi i32 [ %x, %l2 ], [ 0, %entry ]
   ret i32 %r
 ; CHECK-LABEL: @covered_switch_with_bit_tests
 ; CHECK: entry
 ; CHECK-NEXT: switch
 }
+
+; Speculation depth must be limited to avoid a zero-cost instruction cycle.
+
+; CHECK-LABEL: @PR26308(
+; CHECK:       cleanup4:
+; CHECK-NEXT:  br label %cleanup4
+
+define i32 @PR26308(i1 %B, i64 %load) {
+entry:
+  br label %while.body
+
+while.body:
+  br label %cleanup
+
+cleanup:
+  %cleanup.dest.slot.0 = phi i1 [ false, %while.body ]
+  br i1 %cleanup.dest.slot.0, label %for.cond, label %cleanup4
+
+for.cond:
+  %e.0 = phi i64* [ undef, %cleanup ], [ %incdec.ptr, %for.cond2 ]
+  %pi = ptrtoint i64* %e.0 to i64
+  %incdec.ptr = getelementptr inbounds i64, i64* %e.0, i64 1
+  br label %for.cond2
+
+for.cond2:
+  %storemerge = phi i64 [ %pi, %for.cond ], [ %load, %for.cond2 ]
+  br i1 %B, label %for.cond2, label %for.cond
+
+cleanup4:
+  br label %while.body
+}
+