165 lines · cpp
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-exception6//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 layout34 BinaryFunction::BasicBlockOrderType BlockLayout(35 Function.getLayout().block_begin(), Function.getLayout().block_end());36 for (BinaryBasicBlock *BB : BlockLayout) {37 // The block must be hot38 if (BB->getExecutionCount() == 0 ||39 BB->getExecutionCount() == BinaryBasicBlock::COUNT_NO_PROFILE)40 continue;41 // with two successors42 if (BB->succ_size() != 2)43 continue;44 // no jump table45 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 a52 // conditional jump53 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 jump58 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 any71 // other paths72 if (SecondBranch->pred_size() != 1)73 continue;74 75 // Get Jump Instructions76 MCInst *FirstJump = BB->getLastNonPseudoInstr();77 MCInst *SecondJump = SecondBranch->getLastNonPseudoInstr();78 79 // Get condition codes80 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 successors124 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 block133 if (SecondBranchBigger)134 BC.MIB->replaceBranchCondition(*FirstJump, Blocks[2].first->getLabel(),135 Ctx, Blocks[2].second);136 else137 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 common142 // block143 BC.MIB->replaceBranchCondition(*SecondJump, Blocks[0].first->getLabel(),144 Ctx, 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 bolt164} // end namespace llvm165