Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -286,9 +286,9 @@ BitTestBlock(APInt F, APInt R, const Value* SV, unsigned Rg, MVT RgVT, bool E, MachineBasicBlock* P, MachineBasicBlock* D, - BitTestInfo C): + BitTestInfo C, uint32_t W): First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), - Parent(P), Default(D), Cases(std::move(C)) { } + Parent(P), Default(D), Cases(std::move(C)), Weight(W) { } APInt First; APInt Range; const Value *SValue; @@ -298,6 +298,7 @@ MachineBasicBlock *Parent; MachineBasicBlock *Default; BitTestInfo Cases; + uint32_t Weight; }; /// Minimum jump table density, in percent. Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1897,8 +1897,9 @@ MachineBasicBlock* MBB = B.Cases[0].ThisBB; - addSuccessorWithWeight(SwitchBB, B.Default); - addSuccessorWithWeight(SwitchBB, MBB); + uint32_t DefaultWeight = getEdgeWeight(SwitchBB, B.Default); + addSuccessorWithWeight(SwitchBB, B.Default, DefaultWeight); + addSuccessorWithWeight(SwitchBB, MBB, B.Weight); SDValue BrRange = DAG.getNode(ISD::BRCOND, dl, MVT::Other, CopyTo, RangeCmp, @@ -7789,7 +7790,7 @@ } BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange), SI->getCondition(), -1U, MVT::Other, false, nullptr, - nullptr, std::move(BTI)); + nullptr, std::move(BTI), TotalWeight); BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High, BitTestCases.size() - 1, TotalWeight); @@ -8010,8 +8011,16 @@ // The jump block hasn't been inserted yet; insert it here. MachineBasicBlock *JumpMBB = JT->MBB; CurMF->insert(BBI, JumpMBB); - addSuccessorWithWeight(CurMBB, Fallthrough); - addSuccessorWithWeight(CurMBB, JumpMBB); + + // Collect the sum of weights of outgoing edges from JumpMBB, which will + // be the edge weight on CurMBB->JumpMBB. + uint32_t JumpWeight = 0; + for (auto Succ : JumpMBB->successors()) + JumpWeight += getEdgeWeight(JumpMBB, Succ); + uint32_t FallthruWeight = getEdgeWeight(CurMBB, Fallthrough); + + addSuccessorWithWeight(CurMBB, Fallthrough, FallthruWeight); + addSuccessorWithWeight(CurMBB, JumpMBB, JumpWeight); // The jump table header will be inserted in our current block, do the // range check, and fall through to our fallthrough block. Index: test/CodeGen/ARM/jump-table-islands.ll =================================================================== --- test/CodeGen/ARM/jump-table-islands.ll +++ test/CodeGen/ARM/jump-table-islands.ll @@ -13,7 +13,7 @@ ; CHECK: .long LBB{{[0-9]+_[0-9]+}}-[[JUMP_TABLE]] ; CHECK: [[SKIP_TABLE]]: -; CHECK: add pc, {{r[0-9]+}}, {{r[0-9]+}} +; CHECK: add pc, lr, {{r[0-9]+}} br i1 %tst, label %simple, label %complex simple: Index: test/CodeGen/Mips/nacl-align.ll =================================================================== --- test/CodeGen/Mips/nacl-align.ll +++ test/CodeGen/Mips/nacl-align.ll @@ -44,18 +44,17 @@ ; CHECK-NEXT: ${{BB[0-9]+_[0-9]+}}: ; CHECK-NEXT: jr $ra ; CHECK-NEXT: addiu $2, $zero, 111 -; CHECK-NEXT: .align 4 ; CHECK-NEXT: ${{BB[0-9]+_[0-9]+}}: ; CHECK-NEXT: jr $ra -; CHECK-NEXT: addiu $2, $zero, 222 +; CHECK-NEXT: addiu $2, $zero, 555 ; CHECK-NEXT: .align 4 ; CHECK-NEXT: ${{BB[0-9]+_[0-9]+}}: ; CHECK-NEXT: jr $ra -; CHECK-NEXT: addiu $2, $zero, 333 +; CHECK-NEXT: addiu $2, $zero, 222 ; CHECK-NEXT: .align 4 ; CHECK-NEXT: ${{BB[0-9]+_[0-9]+}}: ; CHECK-NEXT: jr $ra -; CHECK-NEXT: addiu $2, $zero, 444 +; CHECK-NEXT: addiu $2, $zero, 333 } Index: test/CodeGen/X86/switch-jump-table.ll =================================================================== --- test/CodeGen/X86/switch-jump-table.ll +++ test/CodeGen/X86/switch-jump-table.ll @@ -1,17 +1,18 @@ -; RUN: llc -mtriple=i686-pc-gnu-linux < %s | FileCheck %s +; RUN: llc -mtriple=i686-pc-gnu-linux < %s | FileCheck %s -check-prefix=CHECK +; RUN: llc -mtriple=i686-pc-gnu-linux -print-machineinstrs=block-placement %s -o /dev/null | FileCheck %s -check-prefix=CHECK2 ; An unreachable default destination is replaced with the most popular case label. -define void @sum2(i32 %x, i32* %to) { -; CHECK-LABEL: sum2: +define void @foo(i32 %x, i32* %to) { +; CHECK-LABEL: foo: ; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]] ; CHECK: cmpl $3, [[REG]] -; CHECK: jbe .LBB0_1 +; CHECK: ja .LBB0_6 +; CHECK-NEXT: # BB#1: +; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4) ; CHECK: movl $4 ; CHECK: retl -; CHECK-LABEL: .LBB0_1: -; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4) entry: switch i32 %x, label %default [ @@ -48,5 +49,44 @@ ; CHECK-NEXT: .long .LBB0_3 ; CHECK-NEXT: .long .LBB0_4 ; CHECK-NEXT: .long .LBB0_5 -; CHECK-NOT: .long } + +; Check if branch probabilities are correctly assigned to the jump table. + +define void @bar(i32 %x, i32* %to) { +; CHECK2-LABEL: bar: +; CHECK2: Successors according to CFG: BB#7(16) BB#1(96) +; CHECK2: Successors according to CFG: BB#2(16) BB#3(16) BB#4(16) BB#5(16) BB#6(32) + +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 + ], !prof !1 +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 +default: + store i32 5, i32* %to + br label %exit +exit: + ret void +} + +!1 = !{!"branch_weights", i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16} Index: test/CodeGen/X86/switch.ll =================================================================== --- test/CodeGen/X86/switch.ll +++ test/CodeGen/X86/switch.ll @@ -90,7 +90,7 @@ ; but with 6-8, the whole switch is suitable for a jump table. ; CHECK-LABEL: jt_is_better ; CHECK: cmpl $8 -; CHECK: jbe +; CHECK: ja ; CHECK: jmpq *.LJTI } Index: test/CodeGen/X86/x86-shrink-wrapping.ll =================================================================== --- test/CodeGen/X86/x86-shrink-wrapping.ll +++ test/CodeGen/X86/x86-shrink-wrapping.ll @@ -532,7 +532,11 @@ ; ; CHECK: movl $24599, [[TMP2:%e[a-z]+]] ; CHECK-NEXT: btl [[TMP]], [[TMP2]] -; CHECK-NEXT: jb [[CLEANUP]] +; CHECK-NEXT: jae [[LOR_LHS_FALSE:LBB[0-9_]+]] +; +; CHECK: [[CLEANUP]]: ## %cleanup +; DISABLE: popq +; CHECK-NEXT: retq ; ; CHECK: [[LOR_LHS_FALSE]]: ## %lor.lhs.false ; CHECK: cmpl $134, %e[[BF_LOAD2]] @@ -551,10 +555,6 @@ ; CHECK-NEXT: je [[CLEANUP]] ; ; CHECK: movb $1, 57(%rax) -; -; CHECK: [[CLEANUP]]: ## %cleanup -; DISABLE: popq -; CHECK-NEXT: retq define void @useLEA(%struct.rtx_def* readonly %x) { entry: %cmp = icmp eq %struct.rtx_def* %x, null