diff options
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 21 | ||||
| -rw-r--r-- | test/CodeGen/X86/switch-order-weight.ll | 37 |
2 files changed, 55 insertions, 3 deletions
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index a9b7f666de..0d37c62660 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1903,8 +1903,6 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, const Value* SV, MachineBasicBlock *Default, MachineBasicBlock *SwitchBB) { - Case& BackCase = *(CR.Range.second-1); - // Size is the number of Cases represented by this range. size_t Size = CR.Range.second - CR.Range.first; if (Size > 3) @@ -1972,11 +1970,28 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, } } + // Order cases by weight so the most likely case will be checked first. + BranchProbabilityInfo *BPI = FuncInfo.BPI; + if (BPI) { + for (CaseItr I = CR.Range.first, IE = CR.Range.second; I != IE; ++I) { + uint32_t IWeight = BPI->getEdgeWeight(SwitchBB->getBasicBlock(), + I->BB->getBasicBlock()); + for (CaseItr J = CR.Range.first; J < I; ++J) { + uint32_t JWeight = BPI->getEdgeWeight(SwitchBB->getBasicBlock(), + J->BB->getBasicBlock()); + if (IWeight > JWeight) + std::swap(*I, *J); + } + } + } + // Rearrange the case blocks so that the last one falls through if possible. + Case &BackCase = *(CR.Range.second-1); if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) { // The last case block won't fall through into 'NextBlock' if we emit the // branches in this order. See if rearranging a case value would help. - for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) { + // We start at the bottom as it's the case with the least weight. + for (CaseItr I = CR.Range.second-2, E = CR.Range.first-1; I != E; --I) { if (I->BB == NextBlock) { std::swap(*I, BackCase); break; diff --git a/test/CodeGen/X86/switch-order-weight.ll b/test/CodeGen/X86/switch-order-weight.ll new file mode 100644 index 0000000000..0fdd56d4e1 --- /dev/null +++ b/test/CodeGen/X86/switch-order-weight.ll @@ -0,0 +1,37 @@ +; RUN: llc -mtriple=x86_64-apple-darwin11 < %s | FileCheck %s + +; Check that the cases which lead to unreachable are checked after "10" + +define void @test1(i32 %x) nounwind uwtable ssp { +entry: + switch i32 %x, label %if.end7 [ + i32 0, label %if.then + i32 10, label %if.then2 + i32 20, label %if.then5 + ] + +; CHECK: test1: +; CHECK-NOT: unr +; CHECK: cmpl $10 +; CHECK: bar +; CHECK: cmpl $20 + +if.then: + tail call void @unr(i32 23) noreturn nounwind + unreachable + +if.then2: + tail call void @bar(i32 42) nounwind + br label %if.end7 + +if.then5: + tail call void @unr(i32 5) noreturn nounwind + unreachable + +if.end7: + ret void +} + +declare void @unr(i32) noreturn + +declare void @bar(i32) |