diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -207,6 +207,9 @@ "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 { @@ -263,6 +266,7 @@ 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); @@ -6794,9 +6798,81 @@ 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; + // When the number of instructions is the same, we consider these basic blocks + // are potentially identical. + SmallDenseMap, 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 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 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; diff --git a/llvm/test/Transforms/SimplifyCFG/switch-simplify-identical-succs.ll b/llvm/test/Transforms/SimplifyCFG/switch-simplify-identical-succs.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SimplifyCFG/switch-simplify-identical-succs.ll @@ -0,0 +1,50 @@ +; 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 +} diff --git a/llvm/test/Transforms/SimplifyCFG/tail-merge-noreturn.ll b/llvm/test/Transforms/SimplifyCFG/tail-merge-noreturn.ll --- a/llvm/test/Transforms/SimplifyCFG/tail-merge-noreturn.ll +++ b/llvm/test/Transforms/SimplifyCFG/tail-merge-noreturn.ll @@ -447,16 +447,12 @@ ; 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 ;