From c511b2a5a1b91f08be6572ca7d7215c261176bc4 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Sat, 26 May 2012 20:01:32 +0000 Subject: SelectionDAGBuilder: When emitting small compare chains for switches order them by using edge weights. SimplifyCFG tends to form a lot of 2-3 case switches when merging branches. Move the most likely condition to the front so it is checked first and the others can be skipped. This is currently not as effective as it could be because SimplifyCFG destroys profiling metadata when merging branches and switches. Merging branch weight metadata is tricky though. This code touches at most 3 cases so I didn't use a proper sorting algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157521 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp') 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; -- cgit v1.2.3-18-g5258