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