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 @@ -13,6 +13,7 @@ #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" @@ -207,6 +208,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 +267,7 @@ bool simplifyCleanupReturn(CleanupReturnInst *RI); bool simplifyUnreachable(UnreachableInst *UI); bool simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); + bool simplifySwitchIdenticalSucc(SwitchInst *SI, IRBuilder<> &Builder); bool simplifyIndirectBr(IndirectBrInst *IBI); bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder); bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder); @@ -6794,9 +6799,73 @@ if (ReduceSwitchRange(SI, Builder, DL, TTI)) return requestResimplify(); + if (simplifySwitchIdenticalSucc(SI, Builder)) + return requestResimplify(); + return false; } +static bool isIdenticalBBWithoutDebug(BasicBlock *BB1, BasicBlock *BB2) { + if (BB1 == BB2) { + return false; + } + auto BB1Itr = BB1->instructionsWithoutDebug(); + auto BB2Itr = BB2->instructionsWithoutDebug(); + + for (auto [I1, I2] : zip_equal(BB1Itr, BB2Itr)) { + if (!I1.isIdenticalToWhenDefined(&I2)) + return false; + } + return true; +} + +/// Attempt to remove very simple identical successors in switch instructions. +bool SimplifyCFGOpt::simplifySwitchIdenticalSucc(SwitchInst *SI, + IRBuilder<> &Builder) { + 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(); + 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++; + if (isIdenticalBBWithoutDebug(FirstSucc, Succ)) { + 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 +}