Index: lib/Transforms/Utils/LowerSwitch.cpp =================================================================== --- lib/Transforms/Utils/LowerSwitch.cpp +++ lib/Transforms/Utils/LowerSwitch.cpp @@ -380,26 +380,67 @@ Value *Val = SI->getCondition(); // The value we are switching on... BasicBlock* Default = SI->getDefaultDest(); - // If there is only the default destination, don't bother with the code below. + // If there is only the default destination, just branch. if (!SI->getNumCases()) { - BranchInst::Create(SI->getDefaultDest(), CurBlock); - CurBlock->getInstList().erase(SI); + BranchInst::Create(Default, CurBlock); + SI->eraseFromParent(); return; } - const bool DefaultIsUnreachable = - Default->size() == 1 && isa(Default->getTerminator()); + ConstantInt *LowerBound = nullptr; + ConstantInt *UpperBound = nullptr; + + if (isa(Default->getFirstNonPHIOrDbg())) { + // Find the most popular successor and determine min and max case value. + DenseMap Popularity; + unsigned MaxPop = 0; + BasicBlock *PopSucc = nullptr; + + assert(SI->case_begin() != SI->case_end()); + ConstantInt *MinCase = SI->case_begin().getCaseValue(); + ConstantInt *MaxCase = SI->case_begin().getCaseValue(); + + for (auto I : SI->cases()) { + BasicBlock *Succ = I.getCaseSuccessor(); + if (++Popularity[Succ] > MaxPop) { + MaxPop = Popularity[Succ]; + PopSucc = Succ; + } + if (I.getCaseValue()->getValue().slt(MinCase->getValue())) + MinCase = I.getCaseValue(); + if (I.getCaseValue()->getValue().sgt(MaxCase->getValue())) + MaxCase = I.getCaseValue(); + } + + // Use the most popular block as the new default, reducing the number of cases. + Default = PopSucc; + for (auto I = SI->case_begin(); I != SI->case_end();) { + if (I.getCaseSuccessor() == PopSucc) + SI->removeCase(I); + else + ++I; + } + + // If there is only the default destination left, just branch. + if (!SI->getNumCases()) { + BranchInst::Create(Default, CurBlock); + SI->eraseFromParent(); + return; + } + + // Make the bounds tightly fitted around the case value range, becase we + // know that the value passed to the switch must be exactly one of the case + // values. + LowerBound = MinCase; + UpperBound = MaxCase; + } + // Create a new, empty default block so that the new hierarchy of // if-then statements go to this and the PHI nodes are happy. - // if the default block is set as an unreachable we avoid creating one - // because will never be a valid target. - BasicBlock *NewDefault = nullptr; - if (!DefaultIsUnreachable) { - NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); - F->getBasicBlockList().insert(Default, NewDefault); - - BranchInst::Create(Default, NewDefault); - } + BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); + F->getBasicBlockList().insert(Default, NewDefault); + BranchInst::Create(Default, NewDefault); + // If there is an entry in any PHI nodes for the default edge, make sure // to update them as well. for (BasicBlock::iterator I = Default->begin(); isa(I); ++I) { @@ -418,18 +459,6 @@ DEBUG(dbgs() << "Cases: " << Cases << "\n"); (void)numCmps; - ConstantInt *UpperBound = nullptr; - ConstantInt *LowerBound = nullptr; - - // Optimize the condition where Default is an unreachable block. In this case - // we can make the bounds tightly fitted around the case value ranges, - // because we know that the value passed to the switch should always be - // exactly one of the case values. - if (DefaultIsUnreachable) { - CaseItr LastCase = Cases.begin() + Cases.size() - 1; - UpperBound = cast(LastCase->High); - LowerBound = cast(Cases.begin()->Low); - } BasicBlock *SwitchBlock = switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, OrigBlock, OrigBlock, NewDefault); @@ -438,11 +467,10 @@ BranchInst::Create(SwitchBlock, OrigBlock); // We are now done with the switch instruction, delete it. + BasicBlock *OldDefault = SI->getDefaultDest(); CurBlock->getInstList().erase(SI); - pred_iterator PI = pred_begin(Default), E = pred_end(Default); - // If the Default block has no more predecessors just remove it - if (PI == E) { - DeleteDeadBlock(Default); - } + // If the Default block has no more predecessors just remove it. + if (pred_begin(OldDefault) == pred_end(OldDefault)) + DeleteDeadBlock(OldDefault); } Index: test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll =================================================================== --- test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll +++ test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll @@ -1,5 +1,8 @@ ; RUN: opt < %s -lowerswitch -S | FileCheck %s -; CHECK-NOT: {{.*}}icmp eq{{.*}} +; +; The switch is lowered with a single icmp. +; CHECK: icmp +; CHECK-NOT: icmp ; ;int foo(int a) { ; @@ -14,7 +17,7 @@ ; ;} -define i32 @foo(i32 %a) nounwind ssp uwtable { +define i32 @foo(i32 %a) { %1 = alloca i32, align 4 %2 = alloca i32, align 4 store i32 %a, i32* %2, align 4 Index: test/Transforms/LowerSwitch/fold-popular-case-to-unreachable-default.ll =================================================================== --- /dev/null +++ test/Transforms/LowerSwitch/fold-popular-case-to-unreachable-default.ll @@ -0,0 +1,67 @@ +; RUN: opt %s -lowerswitch -S | FileCheck %s + +define void @foo(i32 %x, i32* %p) { +; Cases 2 and 4 are removed and become the new default case. +; It is now enough to use two icmps to lower the switch. +; +; CHECK-LABEL: @foo +; CHECK: icmp slt i32 %x, 5 +; CHECK: icmp eq i32 %x, 1 +; CHECK-NOT: icmp +; +entry: + switch i32 %x, label %default [ + i32 1, label %bb0 + i32 2, label %popular + i32 4, label %popular + i32 5, label %bb1 + ] +bb0: + store i32 0, i32* %p + br label %exit +bb1: + store i32 1, i32* %p + br label %exit +popular: + store i32 2, i32* %p + br label %exit +exit: + ret void +default: + unreachable +} + +define void @nocases(i32 %x, i32* %p) { +; Don't fall over when there are no cases. +; +; CHECK-LABEL: @nocases +; CHECK-LABEL: entry +; CHECK-NEXT: br label %default +; +entry: + switch i32 %x, label %default [ + ] +default: + unreachable +} + +define void @nocasesleft(i32 %x, i32* %p) { +; Cases 2 and 4 are removed and we are left with no cases. +; +; CHECK-LABEL: @nocasesleft +; CHECK-LABEL: entry +; CHECK-NEXT: br label %popular +; +entry: + switch i32 %x, label %default [ + i32 2, label %popular + i32 4, label %popular + ] +popular: + store i32 2, i32* %p + br label %exit +exit: + ret void +default: + unreachable +}