[JumpThreading] Put a limit on the PHI nodes when duplicating a BB.

[mnadeem]

Summary

Do not duplicate a BB if it has a lot of PHI nodes.
If a threadable chain is too long then the number of duplicated PHI nodes
can add up, leading to a substantial increase in compile time when rewriting
the SSA.

Fixes https://github.com/llvm/llvm-project/issues/58203

The threshold of 76 in this patch is reasonably high and reduces the compile
time of cldwat2m_macro.f90 in SPEC2017/cam4 from 80+min to <2min.

[efriedma]

This approach seems fine. Is there any particular reason behind the threshold 76?

llvm/lib/Transforms/Scalar/JumpThreading.cpp

542

Since we're iterating over the beginning of the block anyway, can we use the computed non-PHI instruction?

[vzakhari]

Looks good to me.

[mnadeem]

In D136716#3896687, @efriedma wrote:

This approach seems fine. Is there any particular reason behind the threshold 76?

I didn't want to miss any threading opportunities if the compile time was reasonable, 76 seemed high enough (after some experimentation) to cover a lot of cases in SPEC2017/cam4 while maintaining a reasonable compile time.

[mnadeem]

Reuse the computed non-PHI instruction.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 
 static cl::opt<unsigned>
 ImplicationSearchThreshold(
   "jump-threading-implication-search-threshold",
   cl::desc("The number of predecessors to search for a stronger "
            "condition to use to thread over a weaker condition"),
   cl::init(3), cl::Hidden);
 
+static cl::opt<unsigned> PhiDuplicateThreshold(
+    "jump-threading-phi-threshold",
+    cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76),
+    cl::Hidden);
+
 static cl::opt<bool> PrintLVIAfterJumpThreading(
     "print-lvi-after-jump-threading",
     cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false),
     cl::Hidden);
 
 static cl::opt<bool> ThreadAcrossLoopHeaders(
     "jump-threading-across-loop-headers",
     cl::desc("Allow JumpThreading to thread across loop headers, for testing"),

 /// Return the cost of duplicating a piece of this block from first non-phi
 /// and before StopAt instruction to thread across it. Stop scanning the block
 /// when exceeding the threshold. If duplication is impossible, returns ~0U.
 static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI,
                                              BasicBlock *BB,
                                              Instruction *StopAt,
                                              unsigned Threshold) {
   assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
+
+  // Do not duplicate the BB if it has a lot of PHI nodes.
+  // If a threadable chain is too long then the number of PHI nodes can add up,
+  // leading to a substantial increase in compile time when rewriting the SSA.
+  unsigned PhiCount = 0;
+  Instruction *FirstNonPHI = nullptr;
+  for (Instruction &I : *BB) {
+    if (!isa<PHINode>(&I)) {
+      FirstNonPHI = &I;
+      break;
+    }
+    if (++PhiCount > PhiDuplicateThreshold)
+      return ~0U;
+  }
+
   /// Ignore PHI nodes, these will be flattened when duplication happens.
-  BasicBlock::const_iterator I(BB->getFirstNonPHI());
+  BasicBlock::const_iterator I(FirstNonPHI);
 
   // FIXME: THREADING will delete values that are just used to compute the
   // branch, so they shouldn't count against the duplication cost.
 
   unsigned Bonus = 0;
   if (BB->getTerminator() == StopAt) {
     // Threading through a switch statement is particularly profitable.  If this
     // block ends in a switch, decrease its cost to make it more likely to