xref: /llvm-project/bolt/lib/Passes/ThreeWayBranch.cpp (revision 52cf07116bf0a8cab87b0f55176d198bcaa02575)
1 //===- bolt/Passes/ThreeWayBranch.cpp -------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the ThreeWayBranch class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/ThreeWayBranch.h"
14 
15 using namespace llvm;
16 
17 namespace llvm {
18 namespace bolt {
19 
shouldRunOnFunction(BinaryFunction & Function)20 bool ThreeWayBranch::shouldRunOnFunction(BinaryFunction &Function) {
21   BinaryContext &BC = Function.getBinaryContext();
22   for (const BinaryBasicBlock &BB : Function)
23     for (const MCInst &Inst : BB)
24       if (BC.MIB->isPacked(Inst))
25         return false;
26   return true;
27 }
28 
runOnFunction(BinaryFunction & Function)29 void ThreeWayBranch::runOnFunction(BinaryFunction &Function) {
30   BinaryContext &BC = Function.getBinaryContext();
31   MCContext *Ctx = BC.Ctx.get();
32   // New blocks will be added and layout will change,
33   // so make a copy here to iterate over the original layout
34   BinaryFunction::BasicBlockOrderType BlockLayout(
35       Function.getLayout().block_begin(), Function.getLayout().block_end());
36   for (BinaryBasicBlock *BB : BlockLayout) {
37     // The block must be hot
38     if (BB->getExecutionCount() == 0 ||
39         BB->getExecutionCount() == BinaryBasicBlock::COUNT_NO_PROFILE)
40       continue;
41     // with two successors
42     if (BB->succ_size() != 2)
43       continue;
44     // no jump table
45     if (BB->hasJumpTable())
46       continue;
47 
48     BinaryBasicBlock *FalseSucc = BB->getConditionalSuccessor(false);
49     BinaryBasicBlock *TrueSucc = BB->getConditionalSuccessor(true);
50 
51     // One of BB's successors must have only one instruction that is a
52     // conditional jump
53     if ((FalseSucc->succ_size() != 2 || FalseSucc->size() != 1) &&
54         (TrueSucc->succ_size() != 2 || TrueSucc->size() != 1))
55       continue;
56 
57     // SecondBranch has the second conditional jump
58     BinaryBasicBlock *SecondBranch = FalseSucc;
59     BinaryBasicBlock *FirstEndpoint = TrueSucc;
60     if (FalseSucc->succ_size() != 2) {
61       SecondBranch = TrueSucc;
62       FirstEndpoint = FalseSucc;
63     }
64 
65     BinaryBasicBlock *SecondEndpoint =
66         SecondBranch->getConditionalSuccessor(false);
67     BinaryBasicBlock *ThirdEndpoint =
68         SecondBranch->getConditionalSuccessor(true);
69 
70     // Make sure we can modify the jump in SecondBranch without disturbing any
71     // other paths
72     if (SecondBranch->pred_size() != 1)
73       continue;
74 
75     // Get Jump Instructions
76     MCInst *FirstJump = BB->getLastNonPseudoInstr();
77     MCInst *SecondJump = SecondBranch->getLastNonPseudoInstr();
78 
79     // Get condition codes
80     unsigned FirstCC = BC.MIB->getCondCode(*FirstJump);
81     if (SecondBranch != FalseSucc)
82       FirstCC = BC.MIB->getInvertedCondCode(FirstCC);
83     // ThirdCC = ThirdCond && !FirstCC = !(!ThirdCond ||
84     // !(!FirstCC)) = !(!ThirdCond || FirstCC)
85     unsigned ThirdCC =
86         BC.MIB->getInvertedCondCode(BC.MIB->getCondCodesLogicalOr(
87             BC.MIB->getInvertedCondCode(BC.MIB->getCondCode(*SecondJump)),
88             FirstCC));
89     // SecondCC = !ThirdCond && !FirstCC = !(!(!ThirdCond) ||
90     // !(!FirstCC)) = !(ThirdCond || FirstCC)
91     unsigned SecondCC =
92         BC.MIB->getInvertedCondCode(BC.MIB->getCondCodesLogicalOr(
93             BC.MIB->getCondCode(*SecondJump), FirstCC));
94 
95     if (!BC.MIB->isValidCondCode(FirstCC) ||
96         !BC.MIB->isValidCondCode(ThirdCC) || !BC.MIB->isValidCondCode(SecondCC))
97       continue;
98 
99     std::vector<std::pair<BinaryBasicBlock *, unsigned>> Blocks;
100     Blocks.push_back(std::make_pair(FirstEndpoint, FirstCC));
101     Blocks.push_back(std::make_pair(SecondEndpoint, SecondCC));
102     Blocks.push_back(std::make_pair(ThirdEndpoint, ThirdCC));
103 
104     llvm::sort(Blocks, [&](const std::pair<BinaryBasicBlock *, unsigned> A,
105                            const std::pair<BinaryBasicBlock *, unsigned> B) {
106       return A.first->getExecutionCount() < B.first->getExecutionCount();
107     });
108 
109     uint64_t NewSecondBranchCount = Blocks[1].first->getExecutionCount() +
110                                     Blocks[0].first->getExecutionCount();
111     bool SecondBranchBigger =
112         NewSecondBranchCount > Blocks[2].first->getExecutionCount();
113 
114     BB->removeAllSuccessors();
115     if (SecondBranchBigger) {
116       BB->addSuccessor(Blocks[2].first, Blocks[2].first->getExecutionCount());
117       BB->addSuccessor(SecondBranch, NewSecondBranchCount);
118     } else {
119       BB->addSuccessor(SecondBranch, NewSecondBranchCount);
120       BB->addSuccessor(Blocks[2].first, Blocks[2].first->getExecutionCount());
121     }
122 
123     // Remove and add so there is no duplicate successors
124     SecondBranch->removeAllSuccessors();
125     SecondBranch->addSuccessor(Blocks[0].first,
126                                Blocks[0].first->getExecutionCount());
127     SecondBranch->addSuccessor(Blocks[1].first,
128                                Blocks[1].first->getExecutionCount());
129 
130     SecondBranch->setExecutionCount(NewSecondBranchCount);
131 
132     // Replace the branch condition to fallthrough for the most common block
133     if (SecondBranchBigger)
134       BC.MIB->replaceBranchCondition(*FirstJump, Blocks[2].first->getLabel(),
135                                      Ctx, Blocks[2].second);
136     else
137       BC.MIB->replaceBranchCondition(
138           *FirstJump, SecondBranch->getLabel(), Ctx,
139           BC.MIB->getInvertedCondCode(Blocks[2].second));
140 
141     // Replace the branch condition to fallthrough for the second most common
142     // block
143     BC.MIB->replaceBranchCondition(*SecondJump, Blocks[0].first->getLabel(),
144                                    Ctx, Blocks[0].second);
145 
146     ++BranchesAltered;
147   }
148 }
149 
runOnFunctions(BinaryContext & BC)150 Error ThreeWayBranch::runOnFunctions(BinaryContext &BC) {
151   for (auto &It : BC.getBinaryFunctions()) {
152     BinaryFunction &Function = It.second;
153     if (!shouldRunOnFunction(Function))
154       continue;
155     runOnFunction(Function);
156   }
157 
158   BC.outs() << "BOLT-INFO: number of three way branches order changed: "
159             << BranchesAltered << "\n";
160   return Error::success();
161 }
162 
163 } // end namespace bolt
164 } // end namespace llvm
165