[JumpThreading] In updatePredecessorProfileMetadata, stop searching predecessor when the current bb is an unreachable single bb loop

[wmi]

Summary

updatePredecessorProfileMetadata in jumpthreading tries to find the first dominating predecessor block for a PHI value by searching upwards the predecessor block chain.

But jumpthreading may see some temporary IR state which contains unreachable bb not being cleaned up. If an unreachable single bb loop happens to be on the predecessor block chain, keeping following the predecessor block will run into an infinite loop.

The patch fixes it.

[efriedma]

Is there any reason to expect that unreachable loops have exactly one block?

[wmi]

In D65310#1601929, @efriedma wrote:

Is there any reason to expect that unreachable loops have exactly one block?

I was wrong. I thought getSinglePredecessor already handle the case but I didn't think it carefully enough. Thanks for catching it.

I update the patch to stop searching whenever unreachable code is seen, and update the test with unreachable multi-bbs loop case.

[wmi]

Address Eli's comment.

[efriedma]

Please rebase against trunk.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1214

Calling getDomTree() here is expensive; it flushes all updates in the DomTreeUpdater.

[wmi]

Address Eli's comment.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 //
 //  which gives us:
 //     P(A) is less than P(cond == true), i.e.
 //     P(t == true) <= P(cond == true)
 //
 //  In other words, if we know P(cond == true) is unlikely, we know
 //  that P(t == true) is also unlikely.
 //
-static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) {
+static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB,
+                                             DominatorTree &DT) {
   BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
   if (!CondBr)
     return;
 
   BranchProbability BP;
   uint64_t TrueWeight, FalseWeight;
   if (!CondBr->extractProfMetadata(TrueWeight, FalseWeight))
     return;
 
   // Returns the outgoing edge of the dominating predecessor block
   // that leads to the PhiNode's incoming block:
   auto GetPredOutEdge =
-      [](BasicBlock *IncomingBB,
+      [&](BasicBlock *IncomingBB,
           BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
     auto *PredBB = IncomingBB;
     auto *SuccBB = PhiBB;
     while (true) {
+      // Stop searching when PredBB is unreachable. It is waste of time
+      // to propagate prof meta data to unreachable code and may also
+      // cause infinite loop.
+      if (!DT.isReachableFromEntry(PredBB))
+        return {nullptr, nullptr};
+
       BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
       if (PredBr && PredBr->isConditional())
         return {PredBB, SuccBB};
       auto *SinglePredBB = PredBB->getSinglePredecessor();
       if (!SinglePredBB)
         return {nullptr, nullptr};
-      // For unreachable one block loop, stop searching.
-      if (PredBB == SinglePredBB)
-        return {PredBB, SuccBB};
       SuccBB = PredBB;
       PredBB = SinglePredBB;
     }
   };
 
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *PhiOpnd = PN->getIncomingValue(i);
     ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
   // more complex comparisons.
   if (LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
     if (SimplifyPartiallyRedundantLoad(LoadI))
       return true;
 
   // Before threading, try to propagate profile data backwards:
   if (PHINode *PN = dyn_cast<PHINode>(CondInst))
     if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
-      updatePredecessorProfileMetadata(PN, BB);
+      updatePredecessorProfileMetadata(PN, BB, DTU->getDomTree());
 
   // Handle a variety of cases where we are branching on something derived from
   // a PHI node in the current block.  If we can prove that any predecessors
   // compute a predictable value based on a PHI node, thread those predecessors.
   if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator))
     return true;
 
   // If this is an otherwise-unfoldable branch on a phi node in the current

llvm/test/Transforms/JumpThreading/unreachable-single-bb-loop.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 ; RUN: opt -passes=jump-threading -S < %s | FileCheck %s
-; Check the unreachable single bb loop won't cause infinite loop
+; Check the unreachable loop won't cause infinite loop
 ; in jump-threading when it tries to update the predecessors'
 ; profile metadata from a phi node.
 
-define void @test() {
-; CHECK-LABEL: @test()
+define void @unreachable_single_bb_loop() {
+; CHECK-LABEL: @unreachable_single_bb_loop()
 bb:
   %tmp = call i32 @a()
   %tmp1 = icmp eq i32 %tmp, 1
   br i1 %tmp1, label %bb5, label %bb8
 
 ; unreachable single bb loop.
 bb2:                                              ; preds = %bb2
   %tmp4 = icmp ne i32 %tmp, 1
   switch i1 %tmp4, label %bb2 [
     i1 0, label %bb5
     i1 1, label %bb8
   ]
 
 bb5:                                              ; preds = %bb2, %bb
   %tmp6 = phi i1 [ %tmp1, %bb ], [ false, %bb2 ]
   br i1 %tmp6, label %bb8, label %bb7, !prof !0
 
 bb7:                                              ; preds = %bb5
   br label %bb8
 
 bb8:                                              ; preds = %bb8, %bb7, %bb5, %bb2
   ret void
 }
 
+define void @unreachable_multi_bbs_loop() {
+; CHECK-LABEL: @unreachable_multi_bbs_loop()
+bb:
+  %tmp = call i32 @a()
+  %tmp1 = icmp eq i32 %tmp, 1
+  br i1 %tmp1, label %bb5, label %bb8
+
+; unreachable two bbs loop.
+bb3:                                              ; preds = %bb2
+  br label %bb2
+
+bb2:                                              ; preds = %bb3
+  %tmp4 = icmp ne i32 %tmp, 1
+  switch i1 %tmp4, label %bb3 [
+    i1 0, label %bb5
+    i1 1, label %bb8
+  ]
+
+bb5:                                              ; preds = %bb2, %bb
+  %tmp6 = phi i1 [ %tmp1, %bb ], [ false, %bb2 ]
+  br i1 %tmp6, label %bb8, label %bb7, !prof !0
+
+bb7:                                              ; preds = %bb5
+  br label %bb8
+
+bb8:                                              ; preds = %bb8, %bb7, %bb5, %bb2
+  ret void
+}
 declare i32 @a()
 
 !0 = !{!"branch_weights", i32 2146410443, i32 1073205}