Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -3396,6 +3396,73 @@ return !DeadCases.empty(); } +/// Checks if the bodies of two basic blocks are identical. +static bool AreBasicBlocksIdentical(BasicBlock &B1, BasicBlock &B2) { + + // Two blocks cannot be equivalent if they are different sizes. + if (B1.size() != B2.size()) { + return false; + } + + auto Cur1 = B1.begin(); + auto Cur2 = B2.begin(); + + while(Cur1 != B1.end()) { + + if (!(*Cur1).isIdenticalTo(&*Cur2)) { + return false; + } + + ++Cur1; + ++Cur2; + } + + // We should've handled this case earlier. + assert(Cur1 == B1.end() && Cur2 == B2.end() && + "basics blocks are not the same size"); + + return true; +} + +/// Attempts to remove redundant duplicate case successors. +/// +/// We only check adjacent case values because they are the most +/// likely to be the same in real-world code, and it avoids the +/// O(n^2) complexity of checking every case. +/// +/// Returns `true` if the instruction was modified. +static bool EliminateDuplicateSwitchSuccessors(SwitchInst *SI, AssumptionCache *AC, + const DataLayout &DL) { + + // We don't care if the switch has one case. + if (SI->getNumCases() <= 1) + return false; + + SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); + + // Loop for every case. + while(1) { + + BasicBlock *CurSuccessor = I.getCaseSuccessor(); + ++I; + + // Check if we finished iteration. + if (I == E) + break; + + BasicBlock *NextSuccessor = I.getCaseSuccessor(); + + // If the basic blocks are identical, we can remove one because + // it is redundant. + if (AreBasicBlocksIdentical(*CurSuccessor, *NextSuccessor)) { + // Throw away one of the successors. + I.setSuccessor(CurSuccessor); + } + } + + return false; +} + /// If BB would be eligible for simplification by /// TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated /// by an unconditional branch), look at the phi node for BB in the successor @@ -4412,6 +4479,9 @@ if (ForwardSwitchConditionToPHI(SI)) return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (EliminateDuplicateSwitchSuccessors(SI, AC, DL)) + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (SwitchToLookupTable(SI, Builder, DL, TTI)) return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; Index: test/Transforms/SimplifyCFG/switch-duplicate-successors.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-duplicate-successors.ll @@ -0,0 +1,84 @@ +; RUN: opt %s -S -simplifycfg | FileCheck %s + +declare void @foo() + +; This test checks that SimplifyCFG correctly recognizes +; that switch arms point to duplicate basic blocks, and +; removes references to all all unneeded blocks. +define void @main() { +; CHECK-LABEL: @main + +; CHECK: switch i32 %1, label %join [ + +; CHECK-NEXT: i32 1, label %match_case +; CHECK-NEXT: i32 48, label %match_case +; CHECK-NEXT: i32 92, label %match_case +; CHECK-NEXT: i32 23, label %match_case +; CHECK-NEXT: i32 4, label %match_case +; CHECK-NEXT: i32 70, label %match_case +; CHECK-NEXT: i32 29, label %match_case +; CHECK-NEXT: i32 36, label %match_case +; CHECK-NEXT: i32 34, label %match_case +; CHECK-NEXT: i32 58, label %match_case + + %value = alloca i32 + store i32 5, i32* %value + %1 = load i32, i32* %value + + switch i32 %1, label %join [ + i32 1, label %match_case + i32 48, label %match_case1 + i32 92, label %match_case2 + i32 23, label %match_case3 + i32 4, label %match_case4 + i32 70, label %match_case5 + i32 29, label %match_case6 + i32 36, label %match_case7 + i32 34, label %match_case8 + i32 58, label %match_case9 + ] + +match_case: + call void @foo() + unreachable + +match_case1: + call void @foo() + unreachable + +match_case2: + call void @foo() + unreachable + +match_case3: + call void @foo() + unreachable + +match_case4: + call void @foo() + unreachable + +match_case5: + call void @foo() + unreachable + +match_case6: + call void @foo() + unreachable + +match_case7: + call void @foo() + unreachable + +match_case8: + call void @foo() + unreachable + +match_case9: + call void @foo() + unreachable + +join: + ret void +} +