bolt/lib/Passes/ThreeWayBranch.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-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   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
  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
 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