Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2695,32 +2695,60 @@ if (SwitchMBB + 1 != FuncInfo.MF->end()) NextBlock = SwitchMBB + 1; + + // Create a vector of Cases, sorted so that we can efficiently create a binary + // search tree from them. + CaseVector Cases; + Clusterify(Cases, SI); + + // Get the default destination MBB. MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()]; - // If there is only the default destination, branch to it if it is not the - // next basic block. Otherwise, just fall through. - if (!SI.getNumCases()) { + if (isa(SI.getDefaultDest()->getFirstNonPHIOrDbg()) && + !Cases.empty()) { + // Replace an unreachable default destination with the most popular case + // destination. + DenseMap Popularity; + uint64_t MaxPop = 0; + const BasicBlock *MaxBB = nullptr; + for (auto I : SI.cases()) { + const BasicBlock *BB = I.getCaseSuccessor(); + if (++Popularity[BB] > MaxPop) { + MaxPop = Popularity[BB]; + MaxBB = BB; + } + } + + // Set new default. + assert(MaxPop > 0); + assert(MaxBB); + Default = FuncInfo.MBBMap[MaxBB]; + + // Remove cases that have been replaced by the default. + CaseItr I = Cases.begin(); + while (I != Cases.end()) { + if (I->BB == Default) { + I = Cases.erase(I); + continue; + } + ++I; + } + } + + // If there is only the default destination, go there directly. + if (Cases.empty()) { // Update machine-CFG edges. SwitchMBB->addSuccessor(Default); // If this is not a fall-through branch, emit the branch. - if (Default != NextBlock) - DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), - MVT::Other, getControlRoot(), - DAG.getBasicBlock(Default))); - + if (Default != NextBlock) { + DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other, + getControlRoot(), DAG.getBasicBlock(Default))); + } return; } - // If there are any non-default case statements, create a vector of Cases - // representing each one, and sort the vector so that we can efficiently - // create a binary search tree from them. - CaseVector Cases; - Clusterify(Cases, SI); - - // Get the Value to be switched on and default basic blocks, which will be - // inserted into CaseBlock records, representing basic blocks in the binary - // search tree. + // Get the Value to be switched on. const Value *SV = SI.getCondition(); // Push the initial CaseRec onto the worklist Index: test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll =================================================================== --- test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll +++ test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll @@ -41,7 +41,7 @@ i1 false, label %label_end ] default: - unreachable + br label %label_end label_true: br label %label_end @@ -80,7 +80,7 @@ i1 false, label %label_end ] default: - unreachable + br label %label_end label_true: br label %label_end @@ -119,7 +119,7 @@ i1 false, label %label_end ] default: - unreachable + br label %label_end label_true: br label %label_end Index: test/CodeGen/X86/asm-label.ll =================================================================== --- test/CodeGen/X86/asm-label.ll +++ test/CodeGen/X86/asm-label.ll @@ -24,7 +24,7 @@ br label %cleanup cleanup: ; preds = %if.end, %if.then9 - switch i32 undef, label %unreachable [ + switch i32 undef, label %default [ i32 0, label %cleanup.cont i32 1, label %if.end11 ] @@ -35,6 +35,6 @@ if.end11: ; preds = %cleanup.cont, %cleanup, %land.lhs.true, %entry ret void -unreachable: ; preds = %cleanup - unreachable +default: ; preds = %cleanup + br label %if.end11 } Index: test/CodeGen/X86/switch-jump-table.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/switch-jump-table.ll @@ -0,0 +1,52 @@ +; RUN: llc -march=x86 < %s | FileCheck %s + + +; An unreachable default destination is replaced with the most popular case label. + +define void @sum2(i32 %x, i32* %to) { +; CHECK-LABEL: sum2: +; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]] +; cmpl $3, [[REG]] +; CHECK: jbe .LBB0_1 +; CHECK: movl $4 +; CHECK: retl +; CHECK-LABEL: .LBB0_1: +; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4) + +entry: + switch i32 %x, label %default [ + i32 0, label %bb0 + i32 1, label %bb1 + i32 2, label %bb2 + i32 3, label %bb3 + i32 4, label %bb4 + i32 5, label %bb4 + ] +bb0: + store i32 0, i32* %to + br label %exit +bb1: + store i32 1, i32* %to + br label %exit +bb2: + store i32 2, i32* %to + br label %exit +bb3: + store i32 3, i32* %to + br label %exit +bb4: + store i32 4, i32* %to + br label %exit +exit: + ret void +default: + unreachable + +; The jump table has four entries. +; CHECK-LABEL: .LJTI0_0: +; CHECK-NEXT: .long .LBB0_2 +; CHECK-NEXT: .long .LBB0_3 +; CHECK-NEXT: .long .LBB0_4 +; CHECK-NEXT: .long .LBB0_5 +; CHECK-NOT: .long +}