Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -279,11 +279,12 @@ const Value *SValue; MachineBasicBlock *HeaderBB; bool Emitted; + bool OmitRangeCheck; JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, - bool E = false) + bool E = false, bool ORC = false) : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H), - Emitted(E) {} + Emitted(E), OmitRangeCheck(ORC) {} }; using JumpTableBlock = std::pair; Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2189,24 +2189,31 @@ JumpTableReg, SwitchOp); JT.Reg = JumpTableReg; - // Emit the range check for the jump table, and branch to the default block - // for the switch statement if the value being switched on exceeds the largest - // case in the switch. - SDValue CMP = DAG.getSetCC( - dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), - Sub.getValueType()), - Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT); + if (!JTH.OmitRangeCheck) { + // Emit the range check for the jump table, and branch to the default block + // for the switch statement if the value being switched on exceeds the + // largest case in the switch. + SDValue CMP = DAG.getSetCC( + dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), + Sub.getValueType()), + Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT); + + SDValue BrCond = DAG.getNode(ISD::BRCOND, dl, + MVT::Other, CopyTo, CMP, + DAG.getBasicBlock(JT.Default)); + + // Avoid emitting unnecessary branches to the next block. + if (JT.MBB != NextBlock(SwitchBB)) + BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond, + DAG.getBasicBlock(JT.MBB)); - SDValue BrCond = DAG.getNode(ISD::BRCOND, dl, - MVT::Other, CopyTo, CMP, - DAG.getBasicBlock(JT.Default)); - - // Avoid emitting unnecessary branches to the next block. - if (JT.MBB != NextBlock(SwitchBB)) - BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond, - DAG.getBasicBlock(JT.MBB)); - - DAG.setRoot(BrCond); + DAG.setRoot(BrCond); + } else { + SDValue BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, CopyTo, + DAG.getBasicBlock(JT.MBB)); + DAG.setRoot(BrCond); + SwitchBB->removeSuccessor(JT.Default, true); + } } /// Create a LOAD_STACK_GUARD node, and let it carry the target specific global @@ -9558,10 +9565,13 @@ ->createJumpTableIndex(Table); // Set up the jump table info. + bool UnreachableDefault = + isa(SI->getDefaultDest()->getFirstNonPHIOrDbg()); + bool OmitRangeCheck = UnreachableDefault; JumpTable JT(-1U, JTI, JumpTableMBB, nullptr); JumpTableHeader JTH(Clusters[First].Low->getValue(), Clusters[Last].High->getValue(), SI->getCondition(), - nullptr, false); + nullptr, false, OmitRangeCheck); JTCases.emplace_back(std::move(JTH), std::move(JT)); JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High, @@ -10298,6 +10308,7 @@ const SwitchInst &SI, CaseClusterVector &Clusters, BranchProbability &PeeledCaseProb) { MachineBasicBlock *SwitchMBB = FuncInfo.MBB; + // Don't perform if there is only one cluster or optimizing for size. if (SwitchPeelThreshold > 100 || !FuncInfo.BPI || Clusters.size() < 2 || TM.getOptLevel() == CodeGenOpt::None || @@ -10350,6 +10361,7 @@ // Extract cases from the switch. BranchProbabilityInfo *BPI = FuncInfo.BPI; CaseClusterVector Clusters; + Clusters.reserve(SI.getNumCases()); for (auto I : SI.cases()) { MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()]; @@ -10367,38 +10379,6 @@ // if there are many clusters. sortAndRangeify(Clusters); - if (TM.getOptLevel() != CodeGenOpt::None) { - // Replace an unreachable default with the most popular destination. - // FIXME: Exploit unreachable default more aggressively. - bool UnreachableDefault = - isa(SI.getDefaultDest()->getFirstNonPHIOrDbg()); - if (UnreachableDefault && !Clusters.empty()) { - DenseMap Popularity; - unsigned 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 && MaxBB); - DefaultMBB = FuncInfo.MBBMap[MaxBB]; - - // Remove cases that were pointing to the destination that is now the - // default. - CaseClusterVector New; - New.reserve(Clusters.size()); - for (CaseCluster &CC : Clusters) { - if (CC.MBB != DefaultMBB) - New.push_back(CC); - } - Clusters = std::move(New); - } - } - // The branch probablity of the peeled case. BranchProbability PeeledCaseProb = BranchProbability::getZero(); MachineBasicBlock *PeeledSwitchMBB = Index: test/CodeGen/AArch64/switch-unreachable-default.ll =================================================================== --- test/CodeGen/AArch64/switch-unreachable-default.ll +++ test/CodeGen/AArch64/switch-unreachable-default.ll @@ -0,0 +1,62 @@ +; RUN: llc -O3 -o - %s | FileCheck %s + +; Test that the output in the presence of an unreachable default does not have +; a compare and branch at the top of the switch to handle the default case. + +target triple = "aarch64-unknown-linux-gnu" + +; Function Attrs: nounwind +define void @fn(i4) { + switch i4 %0, label %default [ + i4 0, label %case_0 + i4 1, label %case_1 + i4 2, label %case_2 + i4 3, label %case_3 + i4 4, label %case_4 + i4 5, label %case_5 + ] + +; CHECK-LABEL: fn: +; CHECK-NOT: sub +; CHECK-NOT: cmp +; CHECK-NOT: b.hi +; CHECK: {{ldr|add}} x[[REGISTER:[0-9]+]], {{[[]*}}{{x[0-9]+}}, {{x[0-9]+}}, lsl #{{2|3}}{{[]]*}} +; CHECK: br x[[REGISTER]] + +default: + unreachable + +case_0: + tail call void @handle_case_00(i4 %0) #2 + br label %return_label + +case_1: + tail call void @handle_case_01(i4 %0) #2 + br label %return_label + +case_2: + tail call void @handle_case_02(i4 %0) #2 + br label %return_label + +case_3: + tail call void @handle_case_03(i4 %0) #2 + br label %return_label + +case_4: + tail call void @handle_case_04(i4 %0) #2 + br label %return_label + +case_5: + tail call void @handle_case_05(i4 %0) #2 + br label %return_label + +return_label: + ret void +} + +declare void @handle_case_00(i4) +declare void @handle_case_01(i4) +declare void @handle_case_02(i4) +declare void @handle_case_03(i4) +declare void @handle_case_04(i4) +declare void @handle_case_05(i4) Index: test/CodeGen/X86/pr38743.ll =================================================================== --- test/CodeGen/X86/pr38743.ll +++ test/CodeGen/X86/pr38743.ll @@ -18,41 +18,43 @@ define void @pr38743() #1 align 2 { ; CHECK-LABEL: pr38743: -; CHECK: # %bb.0: # %bb -; CHECK-NEXT: cmpl $3, %eax -; CHECK-NEXT: je .LBB0_4 -; CHECK-NEXT: # %bb.1: # %bb -; CHECK-NEXT: cmpl $1, %eax -; CHECK-NEXT: je .LBB0_2 -; CHECK-NEXT: # %bb.3: # %bb5 -; CHECK-NEXT: movzwl .str.17+{{.*}}(%rip), %eax -; CHECK-NEXT: movw %ax, -{{[0-9]+}}(%rsp) -; CHECK-NEXT: movq {{.*}}(%rip), %rax -; CHECK-NEXT: jmp .LBB0_5 -; CHECK-NEXT: .LBB0_4: # %bb8 -; CHECK-NEXT: movq .str.18+{{.*}}(%rip), %rax -; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) -; CHECK-NEXT: movq {{.*}}(%rip), %rax -; CHECK-NEXT: jmp .LBB0_5 -; CHECK-NEXT: .LBB0_2: # %bb2 -; CHECK-NEXT: movq .str.16+{{.*}}(%rip), %rax -; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) -; CHECK-NEXT: movq {{.*}}(%rip), %rax -; CHECK-NEXT: .LBB0_5: # %bb12 -; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) -; CHECK-NEXT: movq -{{[0-9]+}}(%rsp), %rax -; CHECK-NEXT: movq %rax, (%rax) -; CHECK-NEXT: movb -{{[0-9]+}}(%rsp), %al -; CHECK-NEXT: movq -{{[0-9]+}}(%rsp), %rcx -; CHECK-NEXT: movzwl -{{[0-9]+}}(%rsp), %edx -; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %esi -; CHECK-NEXT: movb -{{[0-9]+}}(%rsp), %dil -; CHECK-NEXT: movb %al, (%rax) -; CHECK-NEXT: movq %rcx, 1(%rax) -; CHECK-NEXT: movw %dx, 9(%rax) -; CHECK-NEXT: movl %esi, 11(%rax) -; CHECK-NEXT: movb %dil, 15(%rax) -; CHECK-NEXT: retq +; CHECK: # %bb.0: # %bb +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: jmpq *.LJTI0_0(,%rax,8) +; CHECK-NEXT: .[[LABEL1:[A-Z_0-9]+]]: # %bb5 +; CHECK-NEXT: movzwl .str.17+{{.*}}(%rip), %eax +; CHECK-NEXT: movw %ax, -{{[0-9]+}}(%rsp) +; CHECK-NEXT: movq .str.17(%rip), %rax +; CHECK-NEXT: jmp .[[LABEL4:[A-Z_0-9]+]] +; CHECK-NEXT: .[[LABEL2:[A-Z_0-9]+]]: # %bb2 +; CHECK-NEXT: movq .str.16+{{.*}}(%rip), %rax +; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) +; CHECK-NEXT: movq .str.16(%rip), %rax +; CHECK-NEXT: jmp .[[LABEL4]] +; CHECK-NEXT: .[[LABEL3:[A-Z_0-9]+]]: # %bb8 +; CHECK-NEXT: movq .str.18+{{.*}}(%rip), %rax +; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) +; CHECK-NEXT: movq .str.18(%rip), %rax +; CHECK-NEXT: .[[LABEL4]]: # %bb12 +; CHECK-NEXT: movq %rax, -{{[0-9]+}}(%rsp) +; CHECK-NEXT: movq -{{[0-9]+}}(%rsp), %rax +; CHECK-NEXT: movq %rax, (%rax) +; CHECK-NEXT: movb -{{[0-9]+}}(%rsp), %al +; CHECK-NEXT: movq -{{[0-9]+}}(%rsp), %rcx +; CHECK-NEXT: movzwl -{{[0-9]+}}(%rsp), %edx +; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %esi +; CHECK-NEXT: movb -{{[0-9]+}}(%rsp), %dil +; CHECK-NEXT: movb %al, (%rax) +; CHECK-NEXT: movq %rcx, {{[0-9]+}}(%rax) +; CHECK-NEXT: movw %dx, {{[0-9]+}}(%rax) +; CHECK-NEXT: movl %esi, {{[0-9]+}}(%rax) +; CHECK-NEXT: movb %dil, {{[0-9]+}}(%rax) +; CHECK-NEXT: retq +; CHECK-LABEL: .LJTI0_0: +; CHECK: .quad .[[LABEL2]] +; CHECK-NEXT: .quad .[[LABEL1]] +; CHECK-NEXT: .quad .[[LABEL3]] +; CHECK-NEXT: .quad .[[LABEL1]] bb: %tmp = alloca %0, align 16 %tmp1 = bitcast %0* %tmp to i8* Index: test/CodeGen/X86/switch-jump-table.ll =================================================================== --- test/CodeGen/X86/switch-jump-table.ll +++ test/CodeGen/X86/switch-jump-table.ll @@ -7,13 +7,10 @@ define void @foo(i32 %x, i32* %to) { ; CHECK-LABEL: foo: ; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]] -; CHECK: cmpl $3, [[REG]] -; CHECK: ja .LBB0_6 -; CHECK-NEXT: # %bb.1: ; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4) +; CHECK-LABEL: .LBB0_{{[0-9]+}}: ; CHECK: movl $4 ; CHECK: retl - entry: switch i32 %x, label %default [ i32 0, label %bb0 @@ -43,12 +40,14 @@ default: unreachable -; The jump table has four entries. +; The jump table has six entries. ; CHECK-LABEL: .LJTI0_0: +; CHECK-NEXT: .long .LBB0_1 ; CHECK-NEXT: .long .LBB0_2 ; CHECK-NEXT: .long .LBB0_3 ; CHECK-NEXT: .long .LBB0_4 ; CHECK-NEXT: .long .LBB0_5 +; CHECK-NEXT: .long .LBB0_5 } ; Check if branch probabilities are correctly assigned to the jump table.