[SimplifyCFG] Try to merge edge block when threading (PR55765)

[nikic]

Summary

When threading, we always create a new block for the threaded edge (even if the edge is not critical), which will later get folded back into the predecessor if possible. Depending on precise processing order, this separate block may break the detection of trivial cycles in the threading code, which normally avoids infinite threading of loops. Explicitly merge the created edge block into the predecessor to avoid this.

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

[nikic]

Ping

[spatel]

LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (const auto &Pair : KnownValues) {
 
     if (DTU) {
       Updates.push_back({DominatorTree::Insert, PredBB, EdgeBB});
       Updates.push_back({DominatorTree::Delete, PredBB, BB});
 
       DTU->applyUpdates(Updates);
     }
 
+    // For simplicity, we created a separate basic block for the edge. Merge
+    // it back into the predecessor if possible. This not only avoids
+    // unnecessary SimplifyCFG iterations, but also makes sure that we don't
+    // bypass the check for trivial cycles above.
+    MergeBlockIntoPredecessor(EdgeBB, DTU);
+
     // Signal repeat, simplifying any other constants.
     return None;
   }
 
   return false;
 }
 
 static bool FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI,

llvm/test/Transforms/SimplifyCFG/pr55765.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -simplifycfg < %s | FileCheck %s
+
+; This used to infinitely thread between loop and loop.latch without reaching a
+; fixed point.
+
+declare void @dummy()
+
+define i32 @main(i1 %c1, i1 %c2, i32 %y) {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[EXIT:%.*]], label [[LOOP_PRE_PREHEADER:%.*]]
+; CHECK:       loop.pre.preheader:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], -1
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_PREHEADER:%.*]], label [[EXIT]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[Y]], 0
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[C1]], label [[LOOP2:%.*]], label [[LOOP]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT]]
+; CHECK:       loop2:
+; CHECK-NEXT:    br i1 [[CMP2]], label [[JOIN:%.*]], label [[IF:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    call void @dummy()
+; CHECK-NEXT:    br label [[JOIN]]
+; CHECK:       join:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP2]], label [[LOOP_LATCH:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+  br i1 %c1, label %exit, label %loop.pre.preheader
+
+loop.pre.preheader:
+  %cmp = icmp sgt i32 %y, -1
+  br i1 %cmp, label %loop.preheader, label %exit
+
+loop.preheader:
+  %cmp2 = icmp eq i32 %y, 0
+  br label %loop
+
+loop:
+  br i1 %c1, label %loop2, label %loop.latch
+
+loop.latch:
+  br i1 %cmp, label %loop, label %exit
+
+loop2:
+  br i1 %cmp2, label %join, label %if
+
+if:
+  call void @dummy()
+  br label %join
+
+join:
+  br i1 %c2, label %loop2, label %loop.latch
+
+exit:
+  ret i32 0
+
+; uselistorder directives
+  uselistorder label %loop2, { 1, 0 }
+}