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