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
15using namespace llvm;
16
17namespace llvm {
18namespace bolt {
19
20bool 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
29void 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(Condition: false);
49 BinaryBasicBlock *TrueSucc = BB->getConditionalSuccessor(Condition: 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(Condition: false);
67 BinaryBasicBlock *ThirdEndpoint =
68 SecondBranch->getConditionalSuccessor(Condition: 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(Inst: *FirstJump);
81 if (SecondBranch != FalseSucc)
82 FirstCC = BC.MIB->getInvertedCondCode(CC: FirstCC);
83 // ThirdCC = ThirdCond && !FirstCC = !(!ThirdCond ||
84 // !(!FirstCC)) = !(!ThirdCond || FirstCC)
85 unsigned ThirdCC =
86 BC.MIB->getInvertedCondCode(CC: BC.MIB->getCondCodesLogicalOr(
87 CC1: BC.MIB->getInvertedCondCode(CC: BC.MIB->getCondCode(Inst: *SecondJump)),
88 CC2: FirstCC));
89 // SecondCC = !ThirdCond && !FirstCC = !(!(!ThirdCond) ||
90 // !(!FirstCC)) = !(ThirdCond || FirstCC)
91 unsigned SecondCC =
92 BC.MIB->getInvertedCondCode(CC: BC.MIB->getCondCodesLogicalOr(
93 CC1: BC.MIB->getCondCode(Inst: *SecondJump), CC2: FirstCC));
94
95 if (!BC.MIB->isValidCondCode(CC: FirstCC) ||
96 !BC.MIB->isValidCondCode(CC: ThirdCC) || !BC.MIB->isValidCondCode(CC: SecondCC))
97 continue;
98
99 std::vector<std::pair<BinaryBasicBlock *, unsigned>> Blocks;
100 Blocks.push_back(x: std::make_pair(x&: FirstEndpoint, y&: FirstCC));
101 Blocks.push_back(x: std::make_pair(x&: SecondEndpoint, y&: SecondCC));
102 Blocks.push_back(x: std::make_pair(x&: ThirdEndpoint, y&: ThirdCC));
103
104 llvm::sort(C&: Blocks, Comp: [&](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(Succ: Blocks[2].first, Count: Blocks[2].first->getExecutionCount());
117 BB->addSuccessor(Succ: SecondBranch, Count: NewSecondBranchCount);
118 } else {
119 BB->addSuccessor(Succ: SecondBranch, Count: NewSecondBranchCount);
120 BB->addSuccessor(Succ: Blocks[2].first, Count: Blocks[2].first->getExecutionCount());
121 }
122
123 // Remove and add so there is no duplicate successors
124 SecondBranch->removeAllSuccessors();
125 SecondBranch->addSuccessor(Succ: Blocks[0].first,
126 Count: Blocks[0].first->getExecutionCount());
127 SecondBranch->addSuccessor(Succ: Blocks[1].first,
128 Count: 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(Inst&: *FirstJump, TBB: Blocks[2].first->getLabel(),
135 Ctx, CC: Blocks[2].second);
136 else
137 BC.MIB->replaceBranchCondition(
138 Inst&: *FirstJump, TBB: SecondBranch->getLabel(), Ctx,
139 CC: BC.MIB->getInvertedCondCode(CC: Blocks[2].second));
140
141 // Replace the branch condition to fallthrough for the second most common
142 // block
143 BC.MIB->replaceBranchCondition(Inst&: *SecondJump, TBB: Blocks[0].first->getLabel(),
144 Ctx, CC: Blocks[0].second);
145
146 ++BranchesAltered;
147 }
148}
149
150Error 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

source code of bolt/lib/Passes/ThreeWayBranch.cpp