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 
20 bool ThreeWayBranch::shouldRunOnFunction(BinaryFunction &Function) {
21   BinaryContext &BC = Function.getBinaryContext();
22   BinaryFunction::BasicBlockOrderType BlockLayout = Function.getLayout();
23   for (BinaryBasicBlock *BB : BlockLayout)
24     for (MCInst &Inst : *BB)
25       if (BC.MIB->isPacked(Inst))
26         return false;
27   return true;
28 }
29 
30 void ThreeWayBranch::runOnFunction(BinaryFunction &Function) {
31   BinaryContext &BC = Function.getBinaryContext();
32   MCContext *Ctx = BC.Ctx.get();
33   // New blocks will be added and layout will change,
34   // so make a copy here to iterate over the original layout
35   BinaryFunction::BasicBlockOrderType BlockLayout = Function.getLayout();
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     std::sort(Blocks.begin(), Blocks.end(),
105               [&](const std::pair<BinaryBasicBlock *, unsigned> A,
106                   const std::pair<BinaryBasicBlock *, unsigned> B) {
107                 return A.first->getExecutionCount() <
108                        B.first->getExecutionCount();
109               });
110 
111     uint64_t NewSecondBranchCount = Blocks[1].first->getExecutionCount() +
112                                     Blocks[0].first->getExecutionCount();
113     bool SecondBranchBigger =
114         NewSecondBranchCount > Blocks[2].first->getExecutionCount();
115 
116     BB->removeAllSuccessors();
117     if (SecondBranchBigger) {
118       BB->addSuccessor(Blocks[2].first, Blocks[2].first->getExecutionCount());
119       BB->addSuccessor(SecondBranch, NewSecondBranchCount);
120     } else {
121       BB->addSuccessor(SecondBranch, NewSecondBranchCount);
122       BB->addSuccessor(Blocks[2].first, Blocks[2].first->getExecutionCount());
123     }
124 
125     // Remove and add so there is no duplicate successors
126     SecondBranch->removeAllSuccessors();
127     SecondBranch->addSuccessor(Blocks[0].first,
128                                Blocks[0].first->getExecutionCount());
129     SecondBranch->addSuccessor(Blocks[1].first,
130                                Blocks[1].first->getExecutionCount());
131 
132     SecondBranch->setExecutionCount(NewSecondBranchCount);
133 
134     // Replace the branch condition to fallthrough for the most common block
135     if (SecondBranchBigger)
136       BC.MIB->replaceBranchCondition(*FirstJump, Blocks[2].first->getLabel(),
137                                      Ctx, Blocks[2].second);
138     else
139       BC.MIB->replaceBranchCondition(
140           *FirstJump, SecondBranch->getLabel(), Ctx,
141           BC.MIB->getInvertedCondCode(Blocks[2].second));
142 
143     // Replace the branch condition to fallthrough for the second most common
144     // block
145     BC.MIB->replaceBranchCondition(*SecondJump, Blocks[0].first->getLabel(),
146                                    Ctx, Blocks[0].second);
147 
148     ++BranchesAltered;
149   }
150 }
151 
152 void ThreeWayBranch::runOnFunctions(BinaryContext &BC) {
153   for (auto &It : BC.getBinaryFunctions()) {
154     BinaryFunction &Function = It.second;
155     if (!shouldRunOnFunction(Function))
156       continue;
157     runOnFunction(Function);
158   }
159 
160   outs() << "BOLT-INFO: number of three way branches order changed: "
161          << BranchesAltered << "\n";
162 }
163 
164 } // end namespace bolt
165 } // end namespace llvm
166