[SimplifyCFG] Remove identical successors in switch instructions in simple cases.

[DianQK]

Summary

Resolve Inefficient codegen for eq of enum with identical variants #113506.

I implemented identical successors check for a simple case, expecting it to cover some common patterns.
I consider this to be a series of patches, balancing optimization improvements while considering compile time.

[DianQK]

This comment was removed by DianQK.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6810

return false when BB´s sizes are not same?

[nikic]

I don't think this is the right way to approach the problem. We should instead extend the existing sinking transform to support sinking instructions from only a subset of predecessors (into a new intermediate block).

[DianQK]

Update simplifySwitchIdenticalSucc.
Fix some failing test cases.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6810

We don't need to consider the same instances of BB, as this is already the expected result. If we still replace the same instances of BB, the update for DTU will become complicated.
But this logic is actually contrary to the semantics of this function. Let me revise it.

[DianQK]

In D155395#4504028, @nikic wrote:

I don't think this is the right way to approach the problem. We should instead extend the existing sinking transform to support sinking instructions from only a subset of predecessors (into a new intermediate block).

Oh, thank you. I will give it a try.

[DianQK]

I don't think this is the right way to approach the problem. We should instead extend the existing sinking transform to support sinking instructions from only a subset of predecessors (into a new intermediate block).

Yes, we should extend the sinking common instructions. I noticed that the current sinking operation has already performed the related transformations (a simple subset of predecessors), but it seems to trigger some optimization conflicts.
I made a simple strategy adjustment at D155404.

I will try to address this issue during my next spare time.

The simple subset of predecessors is:

define i64 @compare(i64 %a, i64 %b, i64 %c) {
start:
  switch i64 %c, label %bb0 [
  i64 1, label %bb1
  i64 2, label %bb2
  ]

bb0:                                              ; preds = %start
  %0 = add i64 %a, %b
  br label %exit

bb1:                                              ; preds = %start
  %1 = add i64 %a, %b
  br label %exit

bb2:                                              ; preds = %start
  %2 = add i64 %a, %b
  br label %exit

exit:                                             ; preds = %bb3, %bb2, %bb1, %bb0
  %result = phi i64 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
  ret i64 %result
}

There is another more complex case that can be considered in the future:

define i64 @compare2(i64 %a, i64 %b, i64 %c) {
start:
  switch i64 %c, label %bb0 [
  i64 1, label %bb1
  i64 2, label %bb2
  ]

bb0:                                              ; preds = %start
  %0 = add i64 %a, %b
  br label %exit

bb1:                                              ; preds = %start
  %1 = add i64 %a, %b
  br label %exit

bb2:                                              ; preds = %start
  %2 = sub i64 %a, %b                ; here is `sub`
  br label %exit

exit:                                             ; preds = %bb3, %bb2, %bb1, %bb0
  %result = phi i64 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
  ret i64 %result
}

[DianQK]

I reopened this revision to present my new idea and findings. Maybe such as Discord, discourse, or GitHub issues would be a preferable discussion?

I found that the sink common instructions are not often helpful for performance, see https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2255-L2272.
But I found I could take this problem and turn it into two optimizations.

1. Eliminating unreachable basic blocks. But here are specific patches, such as D6697 and D6471, that prevent this behavior. I'll look into that later.
2. Without unreachable basic blocks, it should be possible to extend the hoist common instructions.

[DianQK]

D155711 should be a better option.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

STATISTIC(NumSinkCommonCode,
           "Number of common instruction 'blocks' sunk down to the end block");
 STATISTIC(NumSinkCommonInstrs,
           "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 STATISTIC(NumInvokes,
           "Number of invokes with empty resume blocks simplified into calls");
 STATISTIC(NumInvokesMerged, "Number of invokes that were merged together");
 STATISTIC(NumInvokeSetsFormed, "Number of invoke sets that were formed");
+STATISTIC(
+    NumReduceIdenticalBasicBlock,
+    "Number of identical blocks that follow switch instructions was reduced.");
 
 namespace {
 
 // The first field contains the value that the switch produces when a certain
 // case group is selected, and the second field is a vector containing the
 // cases composing the case group.
 using SwitchCaseResultVectorTy =
     SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>;
bool FoldValueComparisonIntoPredecessors(Instruction *TI,
                                            IRBuilder<> &Builder);
 
   bool simplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
   bool simplifySingleResume(ResumeInst *RI);
   bool simplifyCommonResume(ResumeInst *RI);
   bool simplifyCleanupReturn(CleanupReturnInst *RI);
   bool simplifyUnreachable(UnreachableInst *UI);
   bool simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
+  bool simplifySwitchIdenticalSucc(SwitchInst *SI);
   bool simplifyIndirectBr(IndirectBrInst *IBI);
   bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder);
   bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
 
   bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
                                              IRBuilder<> &Builder);
 
bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
       SwitchToLookupTable(SI, Builder, DTU, DL, TTI))
     return requestResimplify();
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
     return requestResimplify();
 
+  if (simplifySwitchIdenticalSucc(SI))
+    return requestResimplify();
+
+  return false;
+}
+
+static bool isIdenticalBBWithoutDebug(BasicBlock *BB1, BasicBlock *BB2,
+                                      const TargetTransformInfo &TTI) {
+  auto BB1Itr = BB1->instructionsWithoutDebug();
+  auto BB2Itr = BB2->instructionsWithoutDebug();
+
+  for (auto [I1, I2] : zip_equal(BB1Itr, BB2Itr)) {
+    if (!I1.isIdenticalToWhenDefined(&I2) ||
+        !shouldHoistCommonInstructions(&I1, &I2, TTI))
       return false;
   }
+  return true;
+}
+
+/// Attempt to remove very simple identical successors in switch instructions.
+bool SimplifyCFGOpt::simplifySwitchIdenticalSucc(SwitchInst *SI) {
+  bool Changed = false;
+  unsigned NumSuccs = SI->getNumSuccessors();
+  if (NumSuccs < 2) {
+    return false;
+  }
+  using IdxSucc = std::pair<unsigned, BasicBlock *>;
+  // When the number of instructions is the same, we consider these basic blocks
+  // are potentially identical.
+  SmallDenseMap<unsigned, SmallSetVector<IdxSucc, 8>, 8> EqualInstCountSuccMap;
+  for (unsigned Idx = 0; Idx < NumSuccs; ++Idx) {
+    auto *Succ = SI->getSuccessor(Idx);
+    // Keep a simplified approach and only focus where the successors come only
+    // from switch instructions.
+    if (!Succ->getUniquePredecessor() || Succ->hasAddressTaken())
+      continue;
+    unsigned InstCount = Succ->sizeWithoutDebug();
+    // Excluding the single-instruction case, there are already many
+    // optimizations in place.
+    if (InstCount == 1)
+      continue;
+    EqualInstCountSuccMap[InstCount].insert(IdxSucc(Idx, Succ));
+  }
+  SmallSetVector<BasicBlock *, 8> RemovedSuccs;
+  for (auto [_, Succs] : EqualInstCountSuccMap) {
+    if (Succs.size() < 2)
+      continue;
+    const auto *SuccIdxIter = Succs.begin();
+    auto *FirstSucc = (*SuccIdxIter++).second;
+    while (SuccIdxIter != Succs.end()) {
+      auto [Idx, Succ] = *SuccIdxIter++;
+      // We don't need to consider the same instances of BB, as this is already
+      // the expected result. If we still replace the same instances of BB, the
+      // update for DTU will become complicated.
+      if (FirstSucc == Succ) {
+        continue;
+      }
+      if (isIdenticalBBWithoutDebug(FirstSucc, Succ, TTI)) {
+        NumReduceIdenticalBasicBlock++;
+        SI->setSuccessor(Idx, FirstSucc);
+        RemovedSuccs.insert(Succ);
+        Changed |= true;
+      }
+    }
+  }
+  if (DTU && Changed) {
+    std::vector<DominatorTree::UpdateType> Updates;
+    Updates.reserve(RemovedSuccs.size());
+    for (auto *RemovedSucc : RemovedSuccs)
+      Updates.push_back({DominatorTree::Delete, SI->getParent(), RemovedSucc});
+    DTU->applyUpdates(Updates);
+  }
+  return Changed;
+}
 
 bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
   // Eliminate redundant destinations.
   SmallPtrSet<Value *, 8> Succs;
   SmallSetVector<BasicBlock *, 8> RemovedSuccs;

llvm/test/Transforms/SimplifyCFG/switch-simplify-identical-succs.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -sink-common-insts=1 < %s | FileCheck %s
+
+define i64 @compare(i64 %a, i64 %b, i64 %c) {
+; CHECK-LABEL: @compare(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    switch i64 [[C:%.*]], label [[BB0:%.*]] [
+; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
+; CHECK-NEXT:    i64 3, label [[BB3:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb0:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[A]], [[B]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[B]], [[A]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RESULT:%.*]] = phi i64 [ [[TMP0]], [[BB0]] ], [ [[TMP1]], [[BB1]] ], [ [[TMP2]], [[BB3]] ]
+; CHECK-NEXT:    ret i64 [[RESULT]]
+;
+start:
+  switch i64 %c, label %bb0 [
+  i64 1, label %bb1
+  i64 2, label %bb2
+  i64 3, label %bb3
+  ]
+
+bb0:                                              ; preds = %start
+  %0 = add i64 %a, %b
+  br label %exit
+
+bb1:                                              ; preds = %start
+  %1 = sub i64 %a, %b
+  br label %exit
+
+bb2:                                              ; preds = %start
+  %2 = add i64 %a, %b
+  br label %exit
+
+bb3:                                              ; preds = %start
+  %3 = sub i64 %b, %a
+  br label %exit
+
+exit:                                             ; preds = %bb3, %bb2, %bb1, %bb0
+  %result = phi i64 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ], [ %3, %bb3 ]
+  ret i64 %result
+}

llvm/test/Transforms/SimplifyCFG/tail-merge-noreturn.ll

 }
 
 define void @strip_dbg_value(i32 %c) {
 ; CHECK-LABEL: @strip_dbg_value(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[C:%.*]], metadata [[META5:![0-9]+]], metadata !DIExpression()), !dbg [[DBG7:![0-9]+]]
 ; CHECK-NEXT:    switch i32 [[C]], label [[SW_EPILOG:%.*]] [
 ; CHECK-NEXT:    i32 13, label [[SW_BB:%.*]]
-; CHECK-NEXT:    i32 42, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 42, label [[SW_BB]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb:
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 55, metadata [[META5]], metadata !DIExpression()), !dbg [[DBG7]]
 ; CHECK-NEXT:    tail call void @abort()
 ; CHECK-NEXT:    unreachable
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 67, metadata [[META5]], metadata !DIExpression()), !dbg [[DBG7]]
-; CHECK-NEXT:    tail call void @abort()
-; CHECK-NEXT:    unreachable
 ; CHECK:       sw.epilog:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   call void @llvm.dbg.value(metadata i32 %c, i64 0, metadata !12, metadata !13), !dbg !14
   switch i32 %c, label %sw.epilog [
   i32 13, label %sw.bb
   i32 42, label %sw.bb1