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 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 150 void 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 outs() << "BOLT-INFO: number of three way branches order changed: " 159 << BranchesAltered << "\n"; 160 } 161 162 } // end namespace bolt 163 } // end namespace llvm 164