bolt/lib/Passes/CMOVConversion.cpp

   1 //===- bolt/Passes/CMOVConversion.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 CMOV conversion pass.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/CMOVConversion.h"
  14 #include "bolt/Core/BinaryBasicBlock.h"
  15 #include "bolt/Core/BinaryContext.h"
  16 #include "bolt/Utils/CommandLineOpts.h"
  17 #include "llvm/ADT/PostOrderIterator.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/ErrorHandling.h"
  20 #include <numeric>
  21
  22 #define DEBUG_TYPE "cmov"
  23
  24 using namespace llvm;
  25
  26 namespace opts {
  27
  28 extern cl::OptionCategory BoltOptCategory;
  29
  30 static cl::opt<int> BiasThreshold(
  31     "cmov-conversion-bias-threshold",
  32     cl::desc("minimum condition bias (pct) to perform a CMOV conversion, "
  33              "-1 to not account bias"),
  34     cl::ReallyHidden, cl::init(1), cl::cat(BoltOptCategory));
  35
  36 static cl::opt<int> MispredictionThreshold(
  37     "cmov-conversion-misprediction-threshold",
  38     cl::desc("minimum misprediction rate (pct) to perform a CMOV conversion, "
  39              "-1 to not account misprediction rate"),
  40     cl::ReallyHidden, cl::init(5), cl::cat(BoltOptCategory));
  41
  42 static cl::opt<bool> ConvertStackMemOperand(
  43     "cmov-conversion-convert-stack-mem-operand",
  44     cl::desc("convert moves with stack memory operand (potentially unsafe)"),
  45     cl::ReallyHidden, cl::init(false), cl::cat(BoltOptCategory));
  46
  47 static cl::opt<bool> ConvertBasePtrStackMemOperand(
  48     "cmov-conversion-convert-rbp-stack-mem-operand",
  49     cl::desc("convert moves with rbp stack memory operand (unsafe, must be off "
  50              "for binaries compiled with -fomit-frame-pointer)"),
  51     cl::ReallyHidden, cl::init(false), cl::cat(BoltOptCategory));
  52
  53 } // namespace opts
  54
  55 namespace llvm {
  56 namespace bolt {
  57
  58 // Return true if the CFG conforms to the following subgraph:
  59 // Predecessor
  60 //   /     \
  61 //  |     RHS
  62 //   \     /
  63 //     LHS
  64 // Caller guarantees that LHS and RHS share the same predecessor.
  65 bool isIfThenSubgraph(const BinaryBasicBlock &LHS,
  66                       const BinaryBasicBlock &RHS) {
  67   if (LHS.pred_size() != 2 || RHS.pred_size() != 1)
  68     return false;
  69
  70   // Sanity check
  71   BinaryBasicBlock *Predecessor = *RHS.pred_begin();
  72   assert(Predecessor && LHS.isPredecessor(Predecessor) && "invalid subgraph");
  73   (void)Predecessor;
  74
  75   if (!LHS.isPredecessor(&RHS))
  76     return false;
  77   if (RHS.succ_size() != 1)
  78     return false;
  79   return true;
  80 }
  81
  82 bool matchCFGSubgraph(BinaryBasicBlock &BB, BinaryBasicBlock *&ConditionalSucc,
  83                       BinaryBasicBlock *&UnconditionalSucc,
  84                       bool &IsConditionalTaken) {
  85   BinaryBasicBlock *TakenSucc = BB.getConditionalSuccessor(true);
  86   BinaryBasicBlock *FallthroughSucc = BB.getConditionalSuccessor(false);
  87   bool IsIfThenTaken = isIfThenSubgraph(*FallthroughSucc, *TakenSucc);
  88   bool IsIfThenFallthrough = isIfThenSubgraph(*TakenSucc, *FallthroughSucc);
  89   if (!IsIfThenFallthrough && !IsIfThenTaken)
  90     return false;
  91   assert((!IsIfThenFallthrough || !IsIfThenTaken) && "Invalid subgraph");
  92
  93   // Output parameters
  94   ConditionalSucc = IsIfThenTaken ? TakenSucc : FallthroughSucc;
  95   UnconditionalSucc = IsIfThenTaken ? FallthroughSucc : TakenSucc;
  96   IsConditionalTaken = IsIfThenTaken;
  97   return true;
  98 }
  99
 100 // Return true if basic block instructions can be converted into cmov(s).
 101 bool canConvertInstructions(const BinaryContext &BC, const BinaryBasicBlock &BB,
 102                             unsigned CC) {
 103   if (BB.empty())
 104     return false;
 105   const MCInst *LastInst = BB.getLastNonPseudoInstr();
 106   // Only pseudo instructions, can't be converted into CMOV
 107   if (LastInst == nullptr)
 108     return false;
 109   for (const MCInst &Inst : BB) {
 110     if (BC.MIB->isPseudo(Inst))
 111       continue;
 112     // Unconditional branch as a last instruction is OK
 113     if (&Inst == LastInst && BC.MIB->isUnconditionalBranch(Inst))
 114       continue;
 115     MCInst Cmov(Inst);
 116     // GPR move is OK
 117     if (!BC.MIB->convertMoveToConditionalMove(
 118             Cmov, CC, opts::ConvertStackMemOperand,
 119             opts::ConvertBasePtrStackMemOperand)) {
 120       LLVM_DEBUG({
 121         dbgs() << BB.getName() << ": can't convert instruction ";
 122         BC.printInstruction(dbgs(), Cmov);
 123       });
 124       return false;
 125     }
 126   }
 127   return true;
 128 }
 129
 130 void convertMoves(const BinaryContext &BC, BinaryBasicBlock &BB, unsigned CC) {
 131   for (auto II = BB.begin(), IE = BB.end(); II != IE; ++II) {
 132     if (BC.MIB->isPseudo(*II))
 133       continue;
 134     if (BC.MIB->isUnconditionalBranch(*II)) {
 135       // XXX: this invalidates II but we return immediately
 136       BB.eraseInstruction(II);
 137       return;
 138     }
 139     bool Result = BC.MIB->convertMoveToConditionalMove(
 140         *II, CC, opts::ConvertStackMemOperand,
 141         opts::ConvertBasePtrStackMemOperand);
 142     assert(Result && "unexpected instruction");
 143     (void)Result;
 144   }
 145 }
 146
 147 // Returns misprediction rate if the profile data is available, -1 otherwise.
 148 std::pair<int, uint64_t>
 149 calculateMispredictionRate(const BinaryBasicBlock &BB) {
 150   uint64_t TotalExecCount = 0;
 151   uint64_t TotalMispredictionCount = 0;
 152   for (auto BI : BB.branch_info()) {
 153     TotalExecCount += BI.Count;
 154     if (BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED)
 155       TotalMispredictionCount += BI.MispredictedCount;
 156   }
 157   if (!TotalExecCount)
 158     return {-1, TotalMispredictionCount};
 159   return {100.0f * TotalMispredictionCount / TotalExecCount,
 160           TotalMispredictionCount};
 161 }
 162
 163 // Returns conditional succ bias if the profile is available, -1 otherwise.
 164 int calculateConditionBias(const BinaryBasicBlock &BB,
 165                            const BinaryBasicBlock &ConditionalSucc) {
 166   if (auto BranchStats = BB.getBranchStats(&ConditionalSucc))
 167     return BranchStats->first;
 168   return -1;
 169 }
 170
 171 void CMOVConversion::Stats::dump() {
 172   outs() << "converted static " << StaticPerformed << "/" << StaticPossible
 173          << formatv(" ({0:P}) ", getStaticRatio())
 174          << "hammock(s) into CMOV sequences, with dynamic execution count "
 175          << DynamicPerformed << "/" << DynamicPossible
 176          << formatv(" ({0:P}), ", getDynamicRatio()) << "saving " << RemovedMP
 177          << "/" << PossibleMP << formatv(" ({0:P}) ", getMPRatio())
 178          << "mispredictions\n";
 179 }
 180
 181 void CMOVConversion::runOnFunction(BinaryFunction &Function) {
 182   BinaryContext &BC = Function.getBinaryContext();
 183   bool Modified = false;
 184   // Function-local stats
 185   Stats Local;
 186   // Traverse blocks in RPO, merging block with a converted cmov with its
 187   // successor.
 188   for (BinaryBasicBlock *BB : post_order(&Function)) {
 189     uint64_t BBExecCount = BB->getKnownExecutionCount();
 190     if (BB->empty() ||          // The block must have instructions
 191         BBExecCount == 0 ||     // must be hot
 192         BB->succ_size() != 2 || // with two successors
 193         BB->hasJumpTable())     // no jump table
 194       continue;
 195
 196     assert(BB->isValid() && "traversal internal error");
 197
 198     // Check branch instruction
 199     auto BranchInstrIter = BB->getLastNonPseudo();
 200     if (BranchInstrIter == BB->rend() ||
 201         !BC.MIB->isConditionalBranch(*BranchInstrIter))
 202       continue;
 203
 204     // Check successors
 205     BinaryBasicBlock *ConditionalSucc, *UnconditionalSucc;
 206     bool IsConditionalTaken;
 207     if (!matchCFGSubgraph(*BB, ConditionalSucc, UnconditionalSucc,
 208                           IsConditionalTaken)) {
 209       LLVM_DEBUG(dbgs() << BB->getName() << ": couldn't match hammock\n");
 210       continue;
 211     }
 212
 213     unsigned CC = BC.MIB->getCondCode(*BranchInstrIter);
 214     if (!IsConditionalTaken)
 215       CC = BC.MIB->getInvertedCondCode(CC);
 216     // Check contents of the conditional block
 217     if (!canConvertInstructions(BC, *ConditionalSucc, CC))
 218       continue;
 219
 220     int ConditionBias = calculateConditionBias(*BB, *ConditionalSucc);
 221     int MispredictionRate = 0;
 222     uint64_t MispredictionCount = 0;
 223     std::tie(MispredictionRate, MispredictionCount) =
 224         calculateMispredictionRate(*BB);
 225
 226     Local.StaticPossible++;
 227     Local.DynamicPossible += BBExecCount;
 228     Local.PossibleMP += MispredictionCount;
 229
 230     // If the conditional successor is never executed, don't convert it
 231     if (ConditionBias < opts::BiasThreshold) {
 232       LLVM_DEBUG(dbgs() << BB->getName() << "->" << ConditionalSucc->getName()
 233                         << " bias = " << ConditionBias
 234                         << ", less than threshold " << opts::BiasThreshold
 235                         << '\n');
 236       continue;
 237     }
 238
 239     // Check the misprediction rate of a branch
 240     if (MispredictionRate < opts::MispredictionThreshold) {
 241       LLVM_DEBUG(dbgs() << BB->getName() << " misprediction rate = "
 242                         << MispredictionRate << ", less than threshold "
 243                         << opts::MispredictionThreshold << '\n');
 244       continue;
 245     }
 246
 247     // remove conditional branch
 248     BB->eraseInstruction(std::prev(BranchInstrIter.base()));
 249     BB->removeAllSuccessors();
 250     // Convert instructions from the conditional successor into cmov's in BB.
 251     convertMoves(BC, *ConditionalSucc, CC);
 252     BB->addInstructions(ConditionalSucc->begin(), ConditionalSucc->end());
 253     ConditionalSucc->markValid(false);
 254
 255     // RPO traversal guarantees that the successor is visited and merged if
 256     // necessary. Merge the unconditional successor into the current block.
 257     BB->addInstructions(UnconditionalSucc->begin(), UnconditionalSucc->end());
 258     UnconditionalSucc->moveAllSuccessorsTo(BB);
 259     UnconditionalSucc->markValid(false);
 260     Local.StaticPerformed++;
 261     Local.DynamicPerformed += BBExecCount;
 262     Local.RemovedMP += MispredictionCount;
 263     Modified = true;
 264   }
 265   if (Modified)
 266     Function.eraseInvalidBBs();
 267   if (opts::Verbosity > 1) {
 268     outs() << "BOLT-INFO: CMOVConversion: " << Function << ", ";
 269     Local.dump();
 270   }
 271   Global = Global + Local;
 272 }
 273
 274 void CMOVConversion::runOnFunctions(BinaryContext &BC) {
 275   for (auto &It : BC.getBinaryFunctions()) {
 276     BinaryFunction &Function = It.second;
 277     if (!shouldOptimize(Function))
 278       continue;
 279     runOnFunction(Function);
 280   }
 281
 282   outs() << "BOLT-INFO: CMOVConversion total: ";
 283   Global.dump();
 284 }
 285
 286 } // end namespace bolt
 287 } // end namespace llvm