2057 lines · cpp
1//===- bolt/Passes/BinaryPasses.cpp - Binary-level passes -----------------===//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 multiple passes for binary optimization and analysis.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/BinaryPasses.h"14#include "bolt/Core/FunctionLayout.h"15#include "bolt/Core/ParallelUtilities.h"16#include "bolt/Passes/ReorderAlgorithm.h"17#include "bolt/Passes/ReorderFunctions.h"18#include "bolt/Utils/CommandLineOpts.h"19#include "llvm/Support/CommandLine.h"20#include <atomic>21#include <mutex>22#include <numeric>23#include <vector>24 25#define DEBUG_TYPE "bolt-opts"26 27using namespace llvm;28using namespace bolt;29 30static const char *dynoStatsOptName(const bolt::DynoStats::Category C) {31 assert(C > bolt::DynoStats::FIRST_DYNO_STAT &&32 C < DynoStats::LAST_DYNO_STAT && "Unexpected dyno stat category.");33 34 static std::string OptNames[bolt::DynoStats::LAST_DYNO_STAT + 1];35 36 OptNames[C] = bolt::DynoStats::Description(C);37 38 llvm::replace(OptNames[C], ' ', '-');39 40 return OptNames[C].c_str();41}42 43namespace opts {44 45extern cl::OptionCategory BoltCategory;46extern cl::OptionCategory BoltOptCategory;47 48extern cl::opt<unsigned> Verbosity;49extern cl::opt<bool> EnableBAT;50extern cl::opt<unsigned> ExecutionCountThreshold;51extern cl::opt<bool> UpdateDebugSections;52extern cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions;53 54enum DynoStatsSortOrder : char {55 Ascending,56 Descending57};58 59static cl::opt<DynoStatsSortOrder> DynoStatsSortOrderOpt(60 "print-sorted-by-order",61 cl::desc("use ascending or descending order when printing functions "62 "ordered by dyno stats"),63 cl::init(DynoStatsSortOrder::Descending),64 cl::values(clEnumValN(DynoStatsSortOrder::Ascending, "ascending",65 "Ascending order"),66 clEnumValN(DynoStatsSortOrder::Descending, "descending",67 "Descending order")),68 cl::cat(BoltOptCategory));69 70cl::list<std::string>71HotTextMoveSections("hot-text-move-sections",72 cl::desc("list of sections containing functions used for hugifying hot text. "73 "BOLT makes sure these functions are not placed on the same page as "74 "the hot text. (default=\'.stub,.mover\')."),75 cl::value_desc("sec1,sec2,sec3,..."),76 cl::CommaSeparated,77 cl::ZeroOrMore,78 cl::cat(BoltCategory));79 80bool isHotTextMover(const BinaryFunction &Function) {81 for (std::string &SectionName : opts::HotTextMoveSections) {82 if (Function.getOriginSectionName() &&83 *Function.getOriginSectionName() == SectionName)84 return true;85 }86 87 return false;88}89 90static cl::opt<bool> MinBranchClusters(91 "min-branch-clusters",92 cl::desc("use a modified clustering algorithm geared towards minimizing "93 "branches"),94 cl::Hidden, cl::cat(BoltOptCategory));95 96static cl::list<Peepholes::PeepholeOpts> Peepholes(97 "peepholes", cl::CommaSeparated, cl::desc("enable peephole optimizations"),98 cl::value_desc("opt1,opt2,opt3,..."),99 cl::values(clEnumValN(Peepholes::PEEP_NONE, "none", "disable peepholes"),100 clEnumValN(Peepholes::PEEP_DOUBLE_JUMPS, "double-jumps",101 "remove double jumps when able"),102 clEnumValN(Peepholes::PEEP_TAILCALL_TRAPS, "tailcall-traps",103 "insert tail call traps"),104 clEnumValN(Peepholes::PEEP_USELESS_BRANCHES, "useless-branches",105 "remove useless conditional branches"),106 clEnumValN(Peepholes::PEEP_ALL, "all",107 "enable all peephole optimizations")),108 cl::ZeroOrMore, cl::cat(BoltOptCategory));109 110static cl::opt<unsigned>111 PrintFuncStat("print-function-statistics",112 cl::desc("print statistics about basic block ordering"),113 cl::init(0), cl::cat(BoltOptCategory));114 115static cl::opt<bool> PrintLargeFunctions(116 "print-large-functions",117 cl::desc("print functions that could not be overwritten due to excessive "118 "size"),119 cl::init(false), cl::cat(BoltOptCategory));120 121static cl::list<bolt::DynoStats::Category>122 PrintSortedBy("print-sorted-by", cl::CommaSeparated,123 cl::desc("print functions sorted by order of dyno stats"),124 cl::value_desc("key1,key2,key3,..."),125 cl::values(126#define D(name, description, ...) \127 clEnumValN(bolt::DynoStats::name, dynoStatsOptName(bolt::DynoStats::name), \128 description),129 REAL_DYNO_STATS130#undef D131 clEnumValN(bolt::DynoStats::LAST_DYNO_STAT, "all",132 "sorted by all names")),133 cl::ZeroOrMore, cl::cat(BoltOptCategory));134 135static cl::opt<bool>136 PrintUnknown("print-unknown",137 cl::desc("print names of functions with unknown control flow"),138 cl::cat(BoltCategory), cl::Hidden);139 140static cl::opt<bool>141 PrintUnknownCFG("print-unknown-cfg",142 cl::desc("dump CFG of functions with unknown control flow"),143 cl::cat(BoltCategory), cl::ReallyHidden);144 145// Please MSVC19 with a forward declaration: otherwise it reports an error about146// an undeclared variable inside a callback.147extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks;148cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks(149 "reorder-blocks", cl::desc("change layout of basic blocks in a function"),150 cl::init(bolt::ReorderBasicBlocks::LT_NONE),151 cl::values(152 clEnumValN(bolt::ReorderBasicBlocks::LT_NONE, "none",153 "do not reorder basic blocks"),154 clEnumValN(bolt::ReorderBasicBlocks::LT_REVERSE, "reverse",155 "layout blocks in reverse order"),156 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE, "normal",157 "perform optimal layout based on profile"),158 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_BRANCH,159 "branch-predictor",160 "perform optimal layout prioritizing branch "161 "predictions"),162 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE, "cache",163 "perform optimal layout prioritizing I-cache "164 "behavior"),165 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE_PLUS, "cache+",166 "perform layout optimizing I-cache behavior"),167 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_EXT_TSP, "ext-tsp",168 "perform layout optimizing I-cache behavior"),169 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_SHUFFLE,170 "cluster-shuffle", "perform random layout of clusters")),171 cl::ZeroOrMore, cl::cat(BoltOptCategory),172 cl::callback([](const bolt::ReorderBasicBlocks::LayoutType &option) {173 if (option == bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE_PLUS) {174 errs() << "BOLT-WARNING: '-reorder-blocks=cache+' is deprecated, please"175 << " use '-reorder-blocks=ext-tsp' instead\n";176 ReorderBlocks = bolt::ReorderBasicBlocks::LT_OPTIMIZE_EXT_TSP;177 }178 }));179 180static cl::opt<unsigned> ReportBadLayout(181 "report-bad-layout",182 cl::desc("print top <uint> functions with suboptimal code layout on input"),183 cl::init(0), cl::Hidden, cl::cat(BoltOptCategory));184 185static cl::opt<bool>186 ReportStaleFuncs("report-stale",187 cl::desc("print the list of functions with stale profile"),188 cl::Hidden, cl::cat(BoltOptCategory));189 190enum SctcModes : char {191 SctcAlways,192 SctcPreserveDirection,193 SctcHeuristic194};195 196static cl::opt<SctcModes>197SctcMode("sctc-mode",198 cl::desc("mode for simplify conditional tail calls"),199 cl::init(SctcAlways),200 cl::values(clEnumValN(SctcAlways, "always", "always perform sctc"),201 clEnumValN(SctcPreserveDirection,202 "preserve",203 "only perform sctc when branch direction is "204 "preserved"),205 clEnumValN(SctcHeuristic,206 "heuristic",207 "use branch prediction data to control sctc")),208 cl::ZeroOrMore,209 cl::cat(BoltOptCategory));210 211static cl::opt<unsigned>212StaleThreshold("stale-threshold",213 cl::desc(214 "maximum percentage of stale functions to tolerate (default: 100)"),215 cl::init(100),216 cl::Hidden,217 cl::cat(BoltOptCategory));218 219static cl::opt<unsigned> TSPThreshold(220 "tsp-threshold",221 cl::desc(222 "maximum number of hot basic blocks in a function for which to use "223 "a precise TSP solution while re-ordering basic blocks"),224 cl::init(10), cl::Hidden, cl::cat(BoltOptCategory));225 226static cl::opt<unsigned> TopCalledLimit(227 "top-called-limit",228 cl::desc("maximum number of functions to print in top called "229 "functions section"),230 cl::init(100), cl::Hidden, cl::cat(BoltCategory));231 232// Profile density options, synced with llvm-profgen/ProfileGenerator.cpp233static cl::opt<int> ProfileDensityCutOffHot(234 "profile-density-cutoff-hot", cl::init(990000),235 cl::desc("Total samples cutoff for functions used to calculate "236 "profile density."));237 238static cl::opt<double> ProfileDensityThreshold(239 "profile-density-threshold", cl::init(60),240 cl::desc("If the profile density is below the given threshold, it "241 "will be suggested to increase the sampling rate."),242 cl::Optional);243 244} // namespace opts245 246namespace llvm {247namespace bolt {248 249bool BinaryFunctionPass::shouldOptimize(const BinaryFunction &BF) const {250 return BF.isSimple() && BF.getState() == BinaryFunction::State::CFG &&251 !BF.isIgnored();252}253 254bool BinaryFunctionPass::shouldPrint(const BinaryFunction &BF) const {255 return BF.isSimple() && !BF.isIgnored();256}257 258void NormalizeCFG::runOnFunction(BinaryFunction &BF) {259 uint64_t NumRemoved = 0;260 uint64_t NumDuplicateEdges = 0;261 uint64_t NeedsFixBranches = 0;262 for (BinaryBasicBlock &BB : BF) {263 if (!BB.empty())264 continue;265 266 if (BB.isEntryPoint() || BB.isLandingPad())267 continue;268 269 // Handle a dangling empty block.270 if (BB.succ_size() == 0) {271 // If an empty dangling basic block has a predecessor, it could be a272 // result of codegen for __builtin_unreachable. In such case, do not273 // remove the block.274 if (BB.pred_size() == 0) {275 BB.markValid(false);276 ++NumRemoved;277 }278 continue;279 }280 281 // The block should have just one successor.282 BinaryBasicBlock *Successor = BB.getSuccessor();283 assert(Successor && "invalid CFG encountered");284 285 // Redirect all predecessors to the successor block.286 while (!BB.pred_empty()) {287 BinaryBasicBlock *Predecessor = *BB.pred_begin();288 if (Predecessor->hasJumpTable())289 break;290 291 if (Predecessor == Successor)292 break;293 294 BinaryBasicBlock::BinaryBranchInfo &BI = Predecessor->getBranchInfo(BB);295 Predecessor->replaceSuccessor(&BB, Successor, BI.Count,296 BI.MispredictedCount);297 // We need to fix branches even if we failed to replace all successors298 // and remove the block.299 NeedsFixBranches = true;300 }301 302 if (BB.pred_empty()) {303 BB.removeAllSuccessors();304 BB.markValid(false);305 ++NumRemoved;306 }307 }308 309 if (NumRemoved)310 BF.eraseInvalidBBs();311 312 // Check for duplicate successors. Do it after the empty block elimination as313 // we can get more duplicate successors.314 for (BinaryBasicBlock &BB : BF)315 if (!BB.hasJumpTable() && BB.succ_size() == 2 &&316 BB.getConditionalSuccessor(false) == BB.getConditionalSuccessor(true))317 ++NumDuplicateEdges;318 319 // fixBranches() will get rid of duplicate edges and update jump instructions.320 if (NumDuplicateEdges || NeedsFixBranches)321 BF.fixBranches();322 323 NumDuplicateEdgesMerged += NumDuplicateEdges;324 NumBlocksRemoved += NumRemoved;325}326 327Error NormalizeCFG::runOnFunctions(BinaryContext &BC) {328 ParallelUtilities::runOnEachFunction(329 BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR,330 [&](BinaryFunction &BF) { runOnFunction(BF); },331 [&](const BinaryFunction &BF) { return !shouldOptimize(BF); },332 "NormalizeCFG");333 if (NumBlocksRemoved)334 BC.outs() << "BOLT-INFO: removed " << NumBlocksRemoved << " empty block"335 << (NumBlocksRemoved == 1 ? "" : "s") << '\n';336 if (NumDuplicateEdgesMerged)337 BC.outs() << "BOLT-INFO: merged " << NumDuplicateEdgesMerged338 << " duplicate CFG edge"339 << (NumDuplicateEdgesMerged == 1 ? "" : "s") << '\n';340 return Error::success();341}342 343void EliminateUnreachableBlocks::runOnFunction(BinaryFunction &Function) {344 BinaryContext &BC = Function.getBinaryContext();345 unsigned Count;346 uint64_t Bytes;347 Function.markUnreachableBlocks();348 LLVM_DEBUG({349 bool HasInvalidBB = false;350 for (BinaryBasicBlock &BB : Function) {351 if (!BB.isValid()) {352 HasInvalidBB = true;353 dbgs() << "BOLT-INFO: UCE found unreachable block " << BB.getName()354 << " in function " << Function << "\n";355 }356 }357 if (HasInvalidBB)358 Function.dump();359 });360 BinaryContext::IndependentCodeEmitter Emitter =361 BC.createIndependentMCCodeEmitter();362 std::tie(Count, Bytes) = Function.eraseInvalidBBs(Emitter.MCE.get());363 DeletedBlocks += Count;364 DeletedBytes += Bytes;365 if (Count) {366 auto L = BC.scopeLock();367 Modified.insert(&Function);368 if (opts::Verbosity > 0)369 BC.outs() << "BOLT-INFO: removed " << Count370 << " dead basic block(s) accounting for " << Bytes371 << " bytes in function " << Function << '\n';372 }373}374 375Error EliminateUnreachableBlocks::runOnFunctions(BinaryContext &BC) {376 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {377 runOnFunction(BF);378 };379 380 ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {381 return !shouldOptimize(BF) || BF.getLayout().block_empty();382 };383 384 ParallelUtilities::runOnEachFunction(385 BC, ParallelUtilities::SchedulingPolicy::SP_CONSTANT, WorkFun,386 SkipPredicate, "elimininate-unreachable");387 388 if (DeletedBlocks)389 BC.outs() << "BOLT-INFO: UCE removed " << DeletedBlocks << " blocks and "390 << DeletedBytes << " bytes of code\n";391 return Error::success();392}393 394bool ReorderBasicBlocks::shouldPrint(const BinaryFunction &BF) const {395 return (BinaryFunctionPass::shouldPrint(BF) &&396 opts::ReorderBlocks != ReorderBasicBlocks::LT_NONE);397}398 399bool ReorderBasicBlocks::shouldOptimize(const BinaryFunction &BF) const {400 // Apply execution count threshold401 if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)402 return false;403 404 return BinaryFunctionPass::shouldOptimize(BF);405}406 407Error ReorderBasicBlocks::runOnFunctions(BinaryContext &BC) {408 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE)409 return Error::success();410 411 std::atomic_uint64_t ModifiedFuncCount(0);412 std::mutex FunctionEditDistanceMutex;413 DenseMap<const BinaryFunction *, uint64_t> FunctionEditDistance;414 415 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {416 SmallVector<const BinaryBasicBlock *, 0> OldBlockOrder;417 if (opts::PrintFuncStat > 0)418 llvm::copy(BF.getLayout().blocks(), std::back_inserter(OldBlockOrder));419 420 const bool LayoutChanged =421 modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters);422 if (LayoutChanged) {423 ModifiedFuncCount.fetch_add(1, std::memory_order_relaxed);424 if (opts::PrintFuncStat > 0) {425 const uint64_t Distance = BF.getLayout().getEditDistance(OldBlockOrder);426 std::lock_guard<std::mutex> Lock(FunctionEditDistanceMutex);427 FunctionEditDistance[&BF] = Distance;428 }429 }430 };431 432 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {433 return !shouldOptimize(BF);434 };435 436 ParallelUtilities::runOnEachFunction(437 BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR, WorkFun, SkipFunc,438 "ReorderBasicBlocks");439 const size_t NumAllProfiledFunctions =440 BC.NumProfiledFuncs + BC.NumStaleProfileFuncs;441 442 BC.outs() << "BOLT-INFO: basic block reordering modified layout of "443 << format(444 "%zu functions (%.2lf%% of profiled, %.2lf%% of total)\n",445 ModifiedFuncCount.load(std::memory_order_relaxed),446 100.0 * ModifiedFuncCount.load(std::memory_order_relaxed) /447 NumAllProfiledFunctions,448 100.0 * ModifiedFuncCount.load(std::memory_order_relaxed) /449 BC.getBinaryFunctions().size());450 451 if (opts::PrintFuncStat > 0) {452 raw_ostream &OS = BC.outs();453 // Copy all the values into vector in order to sort them454 std::map<uint64_t, BinaryFunction &> ScoreMap;455 auto &BFs = BC.getBinaryFunctions();456 for (auto It = BFs.begin(); It != BFs.end(); ++It)457 ScoreMap.insert(std::pair<uint64_t, BinaryFunction &>(458 It->second.getFunctionScore(), It->second));459 460 OS << "\nBOLT-INFO: Printing Function Statistics:\n\n";461 OS << " There are " << BFs.size() << " functions in total. \n";462 OS << " Number of functions being modified: "463 << ModifiedFuncCount.load(std::memory_order_relaxed) << "\n";464 OS << " User asks for detailed information on top "465 << opts::PrintFuncStat << " functions. (Ranked by function score)"466 << "\n\n";467 uint64_t I = 0;468 for (std::map<uint64_t, BinaryFunction &>::reverse_iterator Rit =469 ScoreMap.rbegin();470 Rit != ScoreMap.rend() && I < opts::PrintFuncStat; ++Rit, ++I) {471 BinaryFunction &Function = Rit->second;472 473 OS << " Information for function of top: " << (I + 1) << ": \n";474 OS << " Function Score is: " << Function.getFunctionScore()475 << "\n";476 OS << " There are " << Function.size()477 << " number of blocks in this function.\n";478 OS << " There are " << Function.getInstructionCount()479 << " number of instructions in this function.\n";480 OS << " The edit distance for this function is: "481 << FunctionEditDistance.lookup(&Function) << "\n\n";482 }483 }484 return Error::success();485}486 487bool ReorderBasicBlocks::modifyFunctionLayout(BinaryFunction &BF,488 LayoutType Type,489 bool MinBranchClusters) const {490 if (BF.size() == 0 || Type == LT_NONE)491 return false;492 493 BinaryFunction::BasicBlockOrderType NewLayout;494 std::unique_ptr<ReorderAlgorithm> Algo;495 496 // Cannot do optimal layout without profile.497 if (Type != LT_REVERSE && !BF.hasValidProfile())498 return false;499 500 if (Type == LT_REVERSE) {501 Algo.reset(new ReverseReorderAlgorithm());502 } else if (BF.size() <= opts::TSPThreshold && Type != LT_OPTIMIZE_SHUFFLE) {503 // Work on optimal solution if problem is small enough504 LLVM_DEBUG(dbgs() << "finding optimal block layout for " << BF << "\n");505 Algo.reset(new TSPReorderAlgorithm());506 } else {507 LLVM_DEBUG(dbgs() << "running block layout heuristics on " << BF << "\n");508 509 std::unique_ptr<ClusterAlgorithm> CAlgo;510 if (MinBranchClusters)511 CAlgo.reset(new MinBranchGreedyClusterAlgorithm());512 else513 CAlgo.reset(new PHGreedyClusterAlgorithm());514 515 switch (Type) {516 case LT_OPTIMIZE:517 Algo.reset(new OptimizeReorderAlgorithm(std::move(CAlgo)));518 break;519 520 case LT_OPTIMIZE_BRANCH:521 Algo.reset(new OptimizeBranchReorderAlgorithm(std::move(CAlgo)));522 break;523 524 case LT_OPTIMIZE_CACHE:525 Algo.reset(new OptimizeCacheReorderAlgorithm(std::move(CAlgo)));526 break;527 528 case LT_OPTIMIZE_EXT_TSP:529 Algo.reset(new ExtTSPReorderAlgorithm());530 break;531 532 case LT_OPTIMIZE_SHUFFLE:533 Algo.reset(new RandomClusterReorderAlgorithm(std::move(CAlgo)));534 break;535 536 default:537 llvm_unreachable("unexpected layout type");538 }539 }540 541 Algo->reorderBasicBlocks(BF, NewLayout);542 543 return BF.getLayout().update(NewLayout);544}545 546Error FixupBranches::runOnFunctions(BinaryContext &BC) {547 for (auto &It : BC.getBinaryFunctions()) {548 BinaryFunction &Function = It.second;549 if (!BC.shouldEmit(Function) || !Function.isSimple())550 continue;551 552 Function.fixBranches();553 }554 return Error::success();555}556 557Error FinalizeFunctions::runOnFunctions(BinaryContext &BC) {558 std::atomic<bool> HasFatal{false};559 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {560 if (!BF.finalizeCFIState()) {561 if (BC.HasRelocations) {562 BC.errs() << "BOLT-ERROR: unable to fix CFI state for function " << BF563 << ". Exiting.\n";564 HasFatal = true;565 return;566 }567 BF.setSimple(false);568 return;569 }570 571 BF.setFinalized();572 573 // Update exception handling information.574 BF.updateEHRanges();575 };576 577 ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {578 return !BC.shouldEmit(BF);579 };580 581 ParallelUtilities::runOnEachFunction(582 BC, ParallelUtilities::SchedulingPolicy::SP_CONSTANT, WorkFun,583 SkipPredicate, "FinalizeFunctions");584 if (HasFatal)585 return createFatalBOLTError("finalize CFI state failure");586 return Error::success();587}588 589Error CheckLargeFunctions::runOnFunctions(BinaryContext &BC) {590 if (BC.HasRelocations)591 return Error::success();592 593 // If the function wouldn't fit, mark it as non-simple. Otherwise, we may emit594 // incorrect meta data.595 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {596 uint64_t HotSize, ColdSize;597 std::tie(HotSize, ColdSize) =598 BC.calculateEmittedSize(BF, /*FixBranches=*/false);599 uint64_t MainFragmentSize = HotSize;600 if (BF.hasIslandsInfo()) {601 MainFragmentSize +=602 offsetToAlignment(BF.getAddress() + MainFragmentSize,603 Align(BF.getConstantIslandAlignment()));604 MainFragmentSize += BF.estimateConstantIslandSize();605 }606 if (MainFragmentSize > BF.getMaxSize()) {607 if (opts::PrintLargeFunctions)608 BC.outs() << "BOLT-INFO: " << BF << " size of " << MainFragmentSize609 << " bytes exceeds allocated space by "610 << (MainFragmentSize - BF.getMaxSize()) << " bytes\n";611 BF.setSimple(false);612 }613 };614 615 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {616 return !shouldOptimize(BF);617 };618 619 ParallelUtilities::runOnEachFunction(620 BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,621 SkipFunc, "CheckLargeFunctions");622 623 return Error::success();624}625 626bool CheckLargeFunctions::shouldOptimize(const BinaryFunction &BF) const {627 // Unlike other passes, allow functions in non-CFG state.628 return BF.isSimple() && !BF.isIgnored();629}630 631Error LowerAnnotations::runOnFunctions(BinaryContext &BC) {632 // Convert GnuArgsSize annotations into CFIs.633 for (BinaryFunction *BF : BC.getAllBinaryFunctions()) {634 for (FunctionFragment &FF : BF->getLayout().fragments()) {635 // Reset at the start of the new fragment.636 int64_t CurrentGnuArgsSize = 0;637 638 for (BinaryBasicBlock *const BB : FF) {639 for (auto II = BB->begin(); II != BB->end(); ++II) {640 if (!BF->usesGnuArgsSize() || !BC.MIB->isInvoke(*II))641 continue;642 643 const int64_t NewGnuArgsSize = BC.MIB->getGnuArgsSize(*II);644 assert(NewGnuArgsSize >= 0 && "Expected non-negative GNU_args_size.");645 if (NewGnuArgsSize == CurrentGnuArgsSize)646 continue;647 648 auto InsertII = BF->addCFIInstruction(649 BB, II,650 MCCFIInstruction::createGnuArgsSize(nullptr, NewGnuArgsSize));651 CurrentGnuArgsSize = NewGnuArgsSize;652 II = std::next(InsertII);653 }654 }655 }656 }657 return Error::success();658}659 660// Check for dirty state in MCSymbol objects that might be a consequence661// of running calculateEmittedSize() in parallel, during split functions662// pass. If an inconsistent state is found (symbol already registered or663// already defined), clean it.664Error CleanMCState::runOnFunctions(BinaryContext &BC) {665 MCContext &Ctx = *BC.Ctx;666 for (const auto &SymMapEntry : Ctx.getSymbols()) {667 const MCSymbol *S = SymMapEntry.getValue().Symbol;668 if (!S)669 continue;670 if (S->isDefined()) {671 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName()672 << "\" is already defined\n");673 const_cast<MCSymbol *>(S)->setFragment(nullptr);674 }675 if (S->isRegistered()) {676 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName()677 << "\" is already registered\n");678 const_cast<MCSymbol *>(S)->setIsRegistered(false);679 }680 LLVM_DEBUG(if (S->isVariable()) {681 dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName() << "\" is variable\n";682 });683 }684 return Error::success();685}686 687// This peephole fixes jump instructions that jump to another basic688// block with a single jump instruction, e.g.689//690// B0: ...691// jmp B1 (or jcc B1)692//693// B1: jmp B2694//695// ->696//697// B0: ...698// jmp B2 (or jcc B2)699//700static uint64_t fixDoubleJumps(BinaryFunction &Function, bool MarkInvalid) {701 uint64_t NumDoubleJumps = 0;702 703 MCContext *Ctx = Function.getBinaryContext().Ctx.get();704 MCPlusBuilder *MIB = Function.getBinaryContext().MIB.get();705 for (BinaryBasicBlock &BB : Function) {706 auto checkAndPatch = [&](BinaryBasicBlock *Pred, BinaryBasicBlock *Succ,707 const MCSymbol *SuccSym,708 std::optional<uint32_t> Offset) {709 // Ignore infinite loop jumps or fallthrough tail jumps.710 if (Pred == Succ || Succ == &BB)711 return false;712 713 if (Succ) {714 const MCSymbol *TBB = nullptr;715 const MCSymbol *FBB = nullptr;716 MCInst *CondBranch = nullptr;717 MCInst *UncondBranch = nullptr;718 bool Res = Pred->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);719 if (!Res) {720 LLVM_DEBUG(dbgs() << "analyzeBranch failed in peepholes in block:\n";721 Pred->dump());722 return false;723 }724 Pred->replaceSuccessor(&BB, Succ);725 726 // We must patch up any existing branch instructions to match up727 // with the new successor.728 assert((CondBranch || (!CondBranch && Pred->succ_size() == 1)) &&729 "Predecessor block has inconsistent number of successors");730 if (CondBranch && MIB->getTargetSymbol(*CondBranch) == BB.getLabel()) {731 MIB->replaceBranchTarget(*CondBranch, Succ->getLabel(), Ctx);732 } else if (UncondBranch &&733 MIB->getTargetSymbol(*UncondBranch) == BB.getLabel()) {734 MIB->replaceBranchTarget(*UncondBranch, Succ->getLabel(), Ctx);735 } else if (!UncondBranch) {736 assert(Function.getLayout().getBasicBlockAfter(Pred, false) != Succ &&737 "Don't add an explicit jump to a fallthrough block.");738 Pred->addBranchInstruction(Succ);739 }740 } else {741 // Succ will be null in the tail call case. In this case we742 // need to explicitly add a tail call instruction.743 MCInst *Branch = Pred->getLastNonPseudoInstr();744 if (Branch && MIB->isUnconditionalBranch(*Branch)) {745 assert(MIB->getTargetSymbol(*Branch) == BB.getLabel());746 Pred->removeSuccessor(&BB);747 Pred->eraseInstruction(Pred->findInstruction(Branch));748 Pred->addTailCallInstruction(SuccSym);749 if (Offset) {750 MCInst *TailCall = Pred->getLastNonPseudoInstr();751 assert(TailCall);752 MIB->setOffset(*TailCall, *Offset);753 }754 } else {755 return false;756 }757 }758 759 ++NumDoubleJumps;760 LLVM_DEBUG(dbgs() << "Removed double jump in " << Function << " from "761 << Pred->getName() << " -> " << BB.getName() << " to "762 << Pred->getName() << " -> " << SuccSym->getName()763 << (!Succ ? " (tail)\n" : "\n"));764 765 return true;766 };767 768 if (BB.getNumNonPseudos() != 1 || BB.isLandingPad())769 continue;770 771 MCInst *Inst = BB.getFirstNonPseudoInstr();772 const bool IsTailCall = MIB->isTailCall(*Inst);773 774 if (!MIB->isUnconditionalBranch(*Inst) && !IsTailCall)775 continue;776 777 // If we operate after SCTC make sure it's not a conditional tail call.778 if (IsTailCall && MIB->isConditionalBranch(*Inst))779 continue;780 781 const MCSymbol *SuccSym = MIB->getTargetSymbol(*Inst);782 BinaryBasicBlock *Succ = BB.getSuccessor();783 784 if (((!Succ || &BB == Succ) && !IsTailCall) || (IsTailCall && !SuccSym))785 continue;786 787 std::vector<BinaryBasicBlock *> Preds = {BB.pred_begin(), BB.pred_end()};788 789 for (BinaryBasicBlock *Pred : Preds) {790 if (Pred->isLandingPad())791 continue;792 793 if (Pred->getSuccessor() == &BB ||794 (Pred->getConditionalSuccessor(true) == &BB && !IsTailCall) ||795 Pred->getConditionalSuccessor(false) == &BB)796 if (checkAndPatch(Pred, Succ, SuccSym, MIB->getOffset(*Inst)) &&797 MarkInvalid)798 BB.markValid(BB.pred_size() != 0 || BB.isLandingPad() ||799 BB.isEntryPoint());800 }801 }802 803 return NumDoubleJumps;804}805 806bool SimplifyConditionalTailCalls::shouldRewriteBranch(807 const BinaryBasicBlock *PredBB, const MCInst &CondBranch,808 const BinaryBasicBlock *BB, const bool DirectionFlag) {809 if (BeenOptimized.count(PredBB))810 return false;811 812 const bool IsForward = BinaryFunction::isForwardBranch(PredBB, BB);813 814 if (IsForward)815 ++NumOrigForwardBranches;816 else817 ++NumOrigBackwardBranches;818 819 if (opts::SctcMode == opts::SctcAlways)820 return true;821 822 if (opts::SctcMode == opts::SctcPreserveDirection)823 return IsForward == DirectionFlag;824 825 const ErrorOr<std::pair<double, double>> Frequency =826 PredBB->getBranchStats(BB);827 828 // It's ok to rewrite the conditional branch if the new target will be829 // a backward branch.830 831 // If no data available for these branches, then it should be ok to832 // do the optimization since it will reduce code size.833 if (Frequency.getError())834 return true;835 836 // TODO: should this use misprediction frequency instead?837 const bool Result = (IsForward && Frequency.get().first >= 0.5) ||838 (!IsForward && Frequency.get().first <= 0.5);839 840 return Result == DirectionFlag;841}842 843uint64_t SimplifyConditionalTailCalls::fixTailCalls(BinaryFunction &BF) {844 // Need updated indices to correctly detect branch' direction.845 BF.getLayout().updateLayoutIndices();846 BF.markUnreachableBlocks();847 848 MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();849 MCContext *Ctx = BF.getBinaryContext().Ctx.get();850 uint64_t NumLocalCTCCandidates = 0;851 uint64_t NumLocalCTCs = 0;852 uint64_t LocalCTCTakenCount = 0;853 uint64_t LocalCTCExecCount = 0;854 std::vector<std::pair<BinaryBasicBlock *, const BinaryBasicBlock *>>855 NeedsUncondBranch;856 857 // Will block be deleted by UCE?858 auto isValid = [](const BinaryBasicBlock *BB) {859 return (BB->pred_size() != 0 || BB->isLandingPad() || BB->isEntryPoint());860 };861 862 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {863 // Locate BB with a single direct tail-call instruction.864 if (BB->getNumNonPseudos() != 1)865 continue;866 867 MCInst *Instr = BB->getFirstNonPseudoInstr();868 if (!MIB->isTailCall(*Instr) || MIB->isConditionalBranch(*Instr))869 continue;870 871 const MCSymbol *CalleeSymbol = MIB->getTargetSymbol(*Instr);872 if (!CalleeSymbol)873 continue;874 875 // Detect direction of the possible conditional tail call.876 const bool IsForwardCTC = BF.isForwardCall(CalleeSymbol);877 878 // Iterate through all predecessors.879 for (BinaryBasicBlock *PredBB : BB->predecessors()) {880 BinaryBasicBlock *CondSucc = PredBB->getConditionalSuccessor(true);881 if (!CondSucc)882 continue;883 884 ++NumLocalCTCCandidates;885 886 const MCSymbol *TBB = nullptr;887 const MCSymbol *FBB = nullptr;888 MCInst *CondBranch = nullptr;889 MCInst *UncondBranch = nullptr;890 bool Result = PredBB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);891 892 // analyzeBranch() can fail due to unusual branch instructions, e.g. jrcxz893 if (!Result) {894 LLVM_DEBUG(dbgs() << "analyzeBranch failed in SCTC in block:\n";895 PredBB->dump());896 continue;897 }898 899 assert(Result && "internal error analyzing conditional branch");900 assert(CondBranch && "conditional branch expected");901 902 // Skip dynamic branches for now.903 if (BF.getBinaryContext().MIB->isDynamicBranch(*CondBranch))904 continue;905 906 // It's possible that PredBB is also a successor to BB that may have907 // been processed by a previous iteration of the SCTC loop, in which908 // case it may have been marked invalid. We should skip rewriting in909 // this case.910 if (!PredBB->isValid()) {911 assert(PredBB->isSuccessor(BB) &&912 "PredBB should be valid if it is not a successor to BB");913 continue;914 }915 916 // We don't want to reverse direction of the branch in new order917 // without further profile analysis.918 const bool DirectionFlag = CondSucc == BB ? IsForwardCTC : !IsForwardCTC;919 if (!shouldRewriteBranch(PredBB, *CondBranch, BB, DirectionFlag))920 continue;921 922 // Record this block so that we don't try to optimize it twice.923 BeenOptimized.insert(PredBB);924 925 uint64_t Count = 0;926 if (CondSucc != BB) {927 // Patch the new target address into the conditional branch.928 MIB->reverseBranchCondition(*CondBranch, CalleeSymbol, Ctx);929 // Since we reversed the condition on the branch we need to change930 // the target for the unconditional branch or add a unconditional931 // branch to the old target. This has to be done manually since932 // fixupBranches is not called after SCTC.933 NeedsUncondBranch.emplace_back(PredBB, CondSucc);934 Count = PredBB->getFallthroughBranchInfo().Count;935 } else {936 // Change destination of the conditional branch.937 MIB->replaceBranchTarget(*CondBranch, CalleeSymbol, Ctx);938 Count = PredBB->getTakenBranchInfo().Count;939 }940 const uint64_t CTCTakenFreq =941 Count == BinaryBasicBlock::COUNT_NO_PROFILE ? 0 : Count;942 943 // Annotate it, so "isCall" returns true for this jcc944 MIB->setConditionalTailCall(*CondBranch);945 // Add info about the conditional tail call frequency, otherwise this946 // info will be lost when we delete the associated BranchInfo entry947 auto &CTCAnnotation =948 MIB->getOrCreateAnnotationAs<uint64_t>(*CondBranch, "CTCTakenCount");949 CTCAnnotation = CTCTakenFreq;950 // Preserve Offset annotation, used in BAT.951 // Instr is a direct tail call instruction that was created when CTCs are952 // first expanded, and has the original CTC offset set.953 if (std::optional<uint32_t> Offset = MIB->getOffset(*Instr))954 MIB->setOffset(*CondBranch, *Offset);955 956 // Remove the unused successor which may be eliminated later957 // if there are no other users.958 PredBB->removeSuccessor(BB);959 // Update BB execution count960 if (CTCTakenFreq && CTCTakenFreq <= BB->getKnownExecutionCount())961 BB->setExecutionCount(BB->getExecutionCount() - CTCTakenFreq);962 else if (CTCTakenFreq > BB->getKnownExecutionCount())963 BB->setExecutionCount(0);964 965 ++NumLocalCTCs;966 LocalCTCTakenCount += CTCTakenFreq;967 LocalCTCExecCount += PredBB->getKnownExecutionCount();968 }969 970 // Remove the block from CFG if all predecessors were removed.971 BB->markValid(isValid(BB));972 }973 974 // Add unconditional branches at the end of BBs to new successors975 // as long as the successor is not a fallthrough.976 for (auto &Entry : NeedsUncondBranch) {977 BinaryBasicBlock *PredBB = Entry.first;978 const BinaryBasicBlock *CondSucc = Entry.second;979 980 const MCSymbol *TBB = nullptr;981 const MCSymbol *FBB = nullptr;982 MCInst *CondBranch = nullptr;983 MCInst *UncondBranch = nullptr;984 PredBB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);985 986 // Find the next valid block. Invalid blocks will be deleted987 // so they shouldn't be considered fallthrough targets.988 const BinaryBasicBlock *NextBlock =989 BF.getLayout().getBasicBlockAfter(PredBB, false);990 while (NextBlock && !isValid(NextBlock))991 NextBlock = BF.getLayout().getBasicBlockAfter(NextBlock, false);992 993 // Get the unconditional successor to this block.994 const BinaryBasicBlock *PredSucc = PredBB->getSuccessor();995 assert(PredSucc && "The other branch should be a tail call");996 997 const bool HasFallthrough = (NextBlock && PredSucc == NextBlock);998 999 if (UncondBranch) {1000 if (HasFallthrough)1001 PredBB->eraseInstruction(PredBB->findInstruction(UncondBranch));1002 else1003 MIB->replaceBranchTarget(*UncondBranch, CondSucc->getLabel(), Ctx);1004 } else if (!HasFallthrough) {1005 MCInst Branch;1006 MIB->createUncondBranch(Branch, CondSucc->getLabel(), Ctx);1007 PredBB->addInstruction(Branch);1008 }1009 }1010 1011 if (NumLocalCTCs > 0) {1012 NumDoubleJumps += fixDoubleJumps(BF, true);1013 // Clean-up unreachable tail-call blocks.1014 const std::pair<unsigned, uint64_t> Stats = BF.eraseInvalidBBs();1015 DeletedBlocks += Stats.first;1016 DeletedBytes += Stats.second;1017 1018 assert(BF.validateCFG());1019 }1020 1021 LLVM_DEBUG(dbgs() << "BOLT: created " << NumLocalCTCs1022 << " conditional tail calls from a total of "1023 << NumLocalCTCCandidates << " candidates in function " << BF1024 << ". CTCs execution count for this function is "1025 << LocalCTCExecCount << " and CTC taken count is "1026 << LocalCTCTakenCount << "\n";);1027 1028 NumTailCallsPatched += NumLocalCTCs;1029 NumCandidateTailCalls += NumLocalCTCCandidates;1030 CTCExecCount += LocalCTCExecCount;1031 CTCTakenCount += LocalCTCTakenCount;1032 1033 return NumLocalCTCs > 0;1034}1035 1036Error SimplifyConditionalTailCalls::runOnFunctions(BinaryContext &BC) {1037 if (!BC.isX86())1038 return Error::success();1039 1040 for (auto &It : BC.getBinaryFunctions()) {1041 BinaryFunction &Function = It.second;1042 1043 if (!shouldOptimize(Function))1044 continue;1045 1046 if (fixTailCalls(Function)) {1047 Modified.insert(&Function);1048 Function.setHasCanonicalCFG(false);1049 }1050 }1051 1052 if (NumTailCallsPatched)1053 BC.outs() << "BOLT-INFO: SCTC: patched " << NumTailCallsPatched1054 << " tail calls (" << NumOrigForwardBranches << " forward)"1055 << " tail calls (" << NumOrigBackwardBranches << " backward)"1056 << " from a total of " << NumCandidateTailCalls1057 << " while removing " << NumDoubleJumps << " double jumps"1058 << " and removing " << DeletedBlocks << " basic blocks"1059 << " totalling " << DeletedBytes1060 << " bytes of code. CTCs total execution count is "1061 << CTCExecCount << " and the number of times CTCs are taken is "1062 << CTCTakenCount << "\n";1063 return Error::success();1064}1065 1066uint64_t ShortenInstructions::shortenInstructions(BinaryFunction &Function) {1067 uint64_t Count = 0;1068 const BinaryContext &BC = Function.getBinaryContext();1069 for (BinaryBasicBlock &BB : Function) {1070 for (MCInst &Inst : BB) {1071 // Skip shortening instructions with Size annotation.1072 if (BC.MIB->getSize(Inst))1073 continue;1074 1075 MCInst OriginalInst;1076 if (opts::Verbosity > 2)1077 OriginalInst = Inst;1078 1079 if (!BC.MIB->shortenInstruction(Inst, *BC.STI))1080 continue;1081 1082 if (opts::Verbosity > 2) {1083 BC.scopeLock();1084 BC.outs() << "BOLT-INFO: shortening:\nBOLT-INFO: ";1085 BC.printInstruction(BC.outs(), OriginalInst, 0, &Function);1086 BC.outs() << "BOLT-INFO: to:";1087 BC.printInstruction(BC.outs(), Inst, 0, &Function);1088 }1089 1090 ++Count;1091 }1092 }1093 1094 return Count;1095}1096 1097Error ShortenInstructions::runOnFunctions(BinaryContext &BC) {1098 std::atomic<uint64_t> NumShortened{0};1099 if (!BC.isX86())1100 return Error::success();1101 1102 ParallelUtilities::runOnEachFunction(1103 BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR,1104 [&](BinaryFunction &BF) { NumShortened += shortenInstructions(BF); },1105 nullptr, "ShortenInstructions");1106 1107 if (NumShortened)1108 BC.outs() << "BOLT-INFO: " << NumShortened1109 << " instructions were shortened\n";1110 return Error::success();1111}1112 1113void Peepholes::addTailcallTraps(BinaryFunction &Function) {1114 MCPlusBuilder *MIB = Function.getBinaryContext().MIB.get();1115 for (BinaryBasicBlock &BB : Function) {1116 MCInst *Inst = BB.getLastNonPseudoInstr();1117 if (Inst && MIB->isTailCall(*Inst) && MIB->isIndirectBranch(*Inst)) {1118 MCInst Trap;1119 MIB->createTrap(Trap);1120 BB.addInstruction(Trap);1121 ++TailCallTraps;1122 }1123 }1124}1125 1126void Peepholes::removeUselessCondBranches(BinaryFunction &Function) {1127 for (BinaryBasicBlock &BB : Function) {1128 if (BB.succ_size() != 2)1129 continue;1130 1131 BinaryBasicBlock *CondBB = BB.getConditionalSuccessor(true);1132 BinaryBasicBlock *UncondBB = BB.getConditionalSuccessor(false);1133 if (CondBB != UncondBB)1134 continue;1135 1136 const MCSymbol *TBB = nullptr;1137 const MCSymbol *FBB = nullptr;1138 MCInst *CondBranch = nullptr;1139 MCInst *UncondBranch = nullptr;1140 bool Result = BB.analyzeBranch(TBB, FBB, CondBranch, UncondBranch);1141 1142 // analyzeBranch() can fail due to unusual branch instructions,1143 // e.g. jrcxz, or jump tables (indirect jump).1144 if (!Result || !CondBranch)1145 continue;1146 1147 BB.removeDuplicateConditionalSuccessor(CondBranch);1148 ++NumUselessCondBranches;1149 }1150}1151 1152Error Peepholes::runOnFunctions(BinaryContext &BC) {1153 const char Opts =1154 std::accumulate(opts::Peepholes.begin(), opts::Peepholes.end(), 0,1155 [](const char A, const PeepholeOpts B) { return A | B; });1156 if (Opts == PEEP_NONE)1157 return Error::success();1158 1159 for (auto &It : BC.getBinaryFunctions()) {1160 BinaryFunction &Function = It.second;1161 if (shouldOptimize(Function)) {1162 if (Opts & PEEP_DOUBLE_JUMPS)1163 NumDoubleJumps += fixDoubleJumps(Function, false);1164 if (Opts & PEEP_TAILCALL_TRAPS)1165 addTailcallTraps(Function);1166 if (Opts & PEEP_USELESS_BRANCHES)1167 removeUselessCondBranches(Function);1168 assert(Function.validateCFG());1169 }1170 }1171 BC.outs() << "BOLT-INFO: Peephole: " << NumDoubleJumps1172 << " double jumps patched.\n"1173 << "BOLT-INFO: Peephole: " << TailCallTraps1174 << " tail call traps inserted.\n"1175 << "BOLT-INFO: Peephole: " << NumUselessCondBranches1176 << " useless conditional branches removed.\n";1177 return Error::success();1178}1179 1180bool SimplifyRODataLoads::simplifyRODataLoads(BinaryFunction &BF) {1181 BinaryContext &BC = BF.getBinaryContext();1182 MCPlusBuilder *MIB = BC.MIB.get();1183 1184 uint64_t NumLocalLoadsSimplified = 0;1185 uint64_t NumDynamicLocalLoadsSimplified = 0;1186 uint64_t NumLocalLoadsFound = 0;1187 uint64_t NumDynamicLocalLoadsFound = 0;1188 1189 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1190 for (MCInst &Inst : *BB) {1191 unsigned Opcode = Inst.getOpcode();1192 const MCInstrDesc &Desc = BC.MII->get(Opcode);1193 1194 // Skip instructions that do not load from memory.1195 if (!Desc.mayLoad())1196 continue;1197 1198 // Try to statically evaluate the target memory address;1199 uint64_t TargetAddress;1200 1201 if (MIB->hasPCRelOperand(Inst)) {1202 // Try to find the symbol that corresponds to the PC-relative operand.1203 MCOperand *DispOpI = MIB->getMemOperandDisp(Inst);1204 assert(DispOpI != Inst.end() && "expected PC-relative displacement");1205 assert(DispOpI->isExpr() &&1206 "found PC-relative with non-symbolic displacement");1207 1208 // Get displacement symbol.1209 const MCSymbol *DisplSymbol;1210 uint64_t DisplOffset;1211 1212 std::tie(DisplSymbol, DisplOffset) =1213 MIB->getTargetSymbolInfo(DispOpI->getExpr());1214 1215 if (!DisplSymbol)1216 continue;1217 1218 // Look up the symbol address in the global symbols map of the binary1219 // context object.1220 BinaryData *BD = BC.getBinaryDataByName(DisplSymbol->getName());1221 if (!BD)1222 continue;1223 TargetAddress = BD->getAddress() + DisplOffset;1224 } else if (!MIB->evaluateMemOperandTarget(Inst, TargetAddress)) {1225 continue;1226 }1227 1228 // Get the contents of the section containing the target address of the1229 // memory operand. We are only interested in read-only sections.1230 ErrorOr<BinarySection &> DataSection =1231 BC.getSectionForAddress(TargetAddress);1232 if (!DataSection || DataSection->isWritable())1233 continue;1234 1235 if (BC.getRelocationAt(TargetAddress) ||1236 BC.getDynamicRelocationAt(TargetAddress))1237 continue;1238 1239 uint32_t Offset = TargetAddress - DataSection->getAddress();1240 StringRef ConstantData = DataSection->getContents();1241 1242 ++NumLocalLoadsFound;1243 if (BB->hasProfile())1244 NumDynamicLocalLoadsFound += BB->getExecutionCount();1245 1246 if (MIB->replaceMemOperandWithImm(Inst, ConstantData, Offset)) {1247 ++NumLocalLoadsSimplified;1248 if (BB->hasProfile())1249 NumDynamicLocalLoadsSimplified += BB->getExecutionCount();1250 }1251 }1252 }1253 1254 NumLoadsFound += NumLocalLoadsFound;1255 NumDynamicLoadsFound += NumDynamicLocalLoadsFound;1256 NumLoadsSimplified += NumLocalLoadsSimplified;1257 NumDynamicLoadsSimplified += NumDynamicLocalLoadsSimplified;1258 1259 return NumLocalLoadsSimplified > 0;1260}1261 1262Error SimplifyRODataLoads::runOnFunctions(BinaryContext &BC) {1263 for (auto &It : BC.getBinaryFunctions()) {1264 BinaryFunction &Function = It.second;1265 if (shouldOptimize(Function) && simplifyRODataLoads(Function))1266 Modified.insert(&Function);1267 }1268 1269 BC.outs() << "BOLT-INFO: simplified " << NumLoadsSimplified << " out of "1270 << NumLoadsFound << " loads from a statically computed address.\n"1271 << "BOLT-INFO: dynamic loads simplified: "1272 << NumDynamicLoadsSimplified << "\n"1273 << "BOLT-INFO: dynamic loads found: " << NumDynamicLoadsFound1274 << "\n";1275 return Error::success();1276}1277 1278Error AssignSections::runOnFunctions(BinaryContext &BC) {1279 for (BinaryFunction *Function : BC.getInjectedBinaryFunctions()) {1280 if (!Function->isPatch()) {1281 Function->setCodeSectionName(BC.getInjectedCodeSectionName());1282 Function->setColdCodeSectionName(BC.getInjectedColdCodeSectionName());1283 }1284 }1285 1286 // In non-relocation mode functions have pre-assigned section names.1287 if (!BC.HasRelocations)1288 return Error::success();1289 1290 const bool UseColdSection =1291 BC.NumProfiledFuncs > 0 ||1292 opts::ReorderFunctions == ReorderFunctions::RT_USER;1293 for (auto &BFI : BC.getBinaryFunctions()) {1294 BinaryFunction &Function = BFI.second;1295 if (opts::isHotTextMover(Function)) {1296 Function.setCodeSectionName(BC.getHotTextMoverSectionName());1297 Function.setColdCodeSectionName(BC.getHotTextMoverSectionName());1298 continue;1299 }1300 1301 if (!UseColdSection || Function.hasValidIndex())1302 Function.setCodeSectionName(BC.getMainCodeSectionName());1303 else1304 Function.setCodeSectionName(BC.getColdCodeSectionName());1305 1306 if (Function.isSplit())1307 Function.setColdCodeSectionName(BC.getColdCodeSectionName());1308 }1309 return Error::success();1310}1311 1312Error PrintProfileStats::runOnFunctions(BinaryContext &BC) {1313 double FlowImbalanceMean = 0.0;1314 size_t NumBlocksConsidered = 0;1315 double WorstBias = 0.0;1316 const BinaryFunction *WorstBiasFunc = nullptr;1317 1318 // For each function CFG, we fill an IncomingMap with the sum of the frequency1319 // of incoming edges for each BB. Likewise for each OutgoingMap and the sum1320 // of the frequency of outgoing edges.1321 using FlowMapTy = std::unordered_map<const BinaryBasicBlock *, uint64_t>;1322 std::unordered_map<const BinaryFunction *, FlowMapTy> TotalIncomingMaps;1323 std::unordered_map<const BinaryFunction *, FlowMapTy> TotalOutgoingMaps;1324 1325 // Compute mean1326 for (const auto &BFI : BC.getBinaryFunctions()) {1327 const BinaryFunction &Function = BFI.second;1328 if (Function.empty() || !Function.isSimple())1329 continue;1330 FlowMapTy &IncomingMap = TotalIncomingMaps[&Function];1331 FlowMapTy &OutgoingMap = TotalOutgoingMaps[&Function];1332 for (const BinaryBasicBlock &BB : Function) {1333 uint64_t TotalOutgoing = 0ULL;1334 auto SuccBIIter = BB.branch_info_begin();1335 for (BinaryBasicBlock *Succ : BB.successors()) {1336 uint64_t Count = SuccBIIter->Count;1337 if (Count == BinaryBasicBlock::COUNT_NO_PROFILE || Count == 0) {1338 ++SuccBIIter;1339 continue;1340 }1341 TotalOutgoing += Count;1342 IncomingMap[Succ] += Count;1343 ++SuccBIIter;1344 }1345 OutgoingMap[&BB] = TotalOutgoing;1346 }1347 1348 size_t NumBlocks = 0;1349 double Mean = 0.0;1350 for (const BinaryBasicBlock &BB : Function) {1351 // Do not compute score for low frequency blocks, entry or exit blocks1352 if (IncomingMap[&BB] < 100 || OutgoingMap[&BB] == 0 || BB.isEntryPoint())1353 continue;1354 ++NumBlocks;1355 const double Difference = (double)OutgoingMap[&BB] - IncomingMap[&BB];1356 Mean += fabs(Difference / IncomingMap[&BB]);1357 }1358 1359 FlowImbalanceMean += Mean;1360 NumBlocksConsidered += NumBlocks;1361 if (!NumBlocks)1362 continue;1363 double FuncMean = Mean / NumBlocks;1364 if (FuncMean > WorstBias) {1365 WorstBias = FuncMean;1366 WorstBiasFunc = &Function;1367 }1368 }1369 if (NumBlocksConsidered > 0)1370 FlowImbalanceMean /= NumBlocksConsidered;1371 1372 // Compute standard deviation1373 NumBlocksConsidered = 0;1374 double FlowImbalanceVar = 0.0;1375 for (const auto &BFI : BC.getBinaryFunctions()) {1376 const BinaryFunction &Function = BFI.second;1377 if (Function.empty() || !Function.isSimple())1378 continue;1379 FlowMapTy &IncomingMap = TotalIncomingMaps[&Function];1380 FlowMapTy &OutgoingMap = TotalOutgoingMaps[&Function];1381 for (const BinaryBasicBlock &BB : Function) {1382 if (IncomingMap[&BB] < 100 || OutgoingMap[&BB] == 0)1383 continue;1384 ++NumBlocksConsidered;1385 const double Difference = (double)OutgoingMap[&BB] - IncomingMap[&BB];1386 FlowImbalanceVar +=1387 pow(fabs(Difference / IncomingMap[&BB]) - FlowImbalanceMean, 2);1388 }1389 }1390 if (NumBlocksConsidered) {1391 FlowImbalanceVar /= NumBlocksConsidered;1392 FlowImbalanceVar = sqrt(FlowImbalanceVar);1393 }1394 1395 // Report to user1396 BC.outs() << format("BOLT-INFO: Profile bias score: %.4lf%% StDev: %.4lf%%\n",1397 (100.0 * FlowImbalanceMean), (100.0 * FlowImbalanceVar));1398 if (WorstBiasFunc && opts::Verbosity >= 1) {1399 BC.outs() << "Worst average bias observed in "1400 << WorstBiasFunc->getPrintName() << "\n";1401 LLVM_DEBUG(WorstBiasFunc->dump());1402 }1403 return Error::success();1404}1405 1406Error PrintProgramStats::runOnFunctions(BinaryContext &BC) {1407 uint64_t NumRegularFunctions = 0;1408 uint64_t NumStaleProfileFunctions = 0;1409 uint64_t NumAllStaleFunctions = 0;1410 uint64_t NumInferredFunctions = 0;1411 uint64_t NumNonSimpleProfiledFunctions = 0;1412 uint64_t NumUnknownControlFlowFunctions = 0;1413 uint64_t TotalSampleCount = 0;1414 uint64_t StaleSampleCount = 0;1415 uint64_t InferredSampleCount = 0;1416 std::vector<const BinaryFunction *> ProfiledFunctions;1417 std::vector<std::pair<double, uint64_t>> FuncDensityList;1418 const char *StaleFuncsHeader = "BOLT-INFO: Functions with stale profile:\n";1419 for (auto &BFI : BC.getBinaryFunctions()) {1420 const BinaryFunction &Function = BFI.second;1421 1422 // Ignore PLT functions for stats.1423 if (Function.isPLTFunction())1424 continue;1425 1426 // Adjustment for BAT mode: the profile for BOLT split fragments is combined1427 // so only count the hot fragment.1428 const uint64_t Address = Function.getAddress();1429 bool IsHotParentOfBOLTSplitFunction = !Function.getFragments().empty() &&1430 BAT && BAT->isBATFunction(Address) &&1431 !BAT->fetchParentAddress(Address);1432 1433 ++NumRegularFunctions;1434 1435 // In BOLTed binaries split functions are non-simple (due to non-relocation1436 // mode), but the original function is known to be simple and we have a1437 // valid profile for it.1438 if (!Function.isSimple() && !IsHotParentOfBOLTSplitFunction) {1439 if (Function.hasProfile())1440 ++NumNonSimpleProfiledFunctions;1441 continue;1442 }1443 1444 if (Function.hasUnknownControlFlow()) {1445 if (opts::PrintUnknownCFG)1446 Function.dump();1447 else if (opts::PrintUnknown)1448 BC.errs() << "function with unknown control flow: " << Function << '\n';1449 1450 ++NumUnknownControlFlowFunctions;1451 }1452 1453 if (!Function.hasProfile())1454 continue;1455 1456 uint64_t SampleCount = Function.getRawSampleCount();1457 TotalSampleCount += SampleCount;1458 1459 if (Function.hasValidProfile()) {1460 ProfiledFunctions.push_back(&Function);1461 if (Function.hasInferredProfile()) {1462 ++NumInferredFunctions;1463 InferredSampleCount += SampleCount;1464 ++NumAllStaleFunctions;1465 }1466 } else {1467 if (opts::ReportStaleFuncs) {1468 BC.outs() << StaleFuncsHeader;1469 StaleFuncsHeader = "";1470 BC.outs() << " " << Function << '\n';1471 }1472 ++NumStaleProfileFunctions;1473 StaleSampleCount += SampleCount;1474 ++NumAllStaleFunctions;1475 }1476 1477 if (opts::ShowDensity) {1478 uint64_t Size = Function.getSize();1479 // In case of BOLT split functions registered in BAT, executed traces are1480 // automatically attributed to the main fragment. Add up function sizes1481 // for all fragments.1482 if (IsHotParentOfBOLTSplitFunction)1483 for (const BinaryFunction *Fragment : Function.getFragments())1484 Size += Fragment->getSize();1485 double Density = (double)1.0 * Function.getSampleCountInBytes() / Size;1486 FuncDensityList.emplace_back(Density, SampleCount);1487 LLVM_DEBUG(BC.outs() << Function << ": executed bytes "1488 << Function.getSampleCountInBytes() << ", size (b) "1489 << Size << ", density " << Density1490 << ", sample count " << SampleCount << '\n');1491 }1492 }1493 BC.NumProfiledFuncs = ProfiledFunctions.size();1494 BC.NumStaleProfileFuncs = NumStaleProfileFunctions;1495 1496 const size_t NumAllProfiledFunctions =1497 ProfiledFunctions.size() + NumStaleProfileFunctions;1498 BC.outs() << "BOLT-INFO: " << NumAllProfiledFunctions << " out of "1499 << NumRegularFunctions << " functions in the binary ("1500 << format("%.1f", NumAllProfiledFunctions /1501 (float)NumRegularFunctions * 100.0f)1502 << "%) have non-empty execution profile\n";1503 if (NumNonSimpleProfiledFunctions) {1504 BC.outs() << "BOLT-INFO: " << NumNonSimpleProfiledFunctions << " function"1505 << (NumNonSimpleProfiledFunctions == 1 ? "" : "s")1506 << " with profile could not be optimized\n";1507 }1508 if (NumAllStaleFunctions) {1509 const float PctStale =1510 NumAllStaleFunctions / (float)NumAllProfiledFunctions * 100.0f;1511 auto printErrorOrWarning = [&]() {1512 if (PctStale > opts::StaleThreshold)1513 BC.errs() << "BOLT-ERROR: ";1514 else1515 BC.errs() << "BOLT-WARNING: ";1516 };1517 printErrorOrWarning();1518 BC.errs() << NumAllStaleFunctions1519 << format(" (%.1f%% of all profiled)", PctStale) << " function"1520 << (NumAllStaleFunctions == 1 ? "" : "s")1521 << " have invalid (possibly stale) profile."1522 " Use -report-stale to see the list.\n";1523 if (TotalSampleCount > 0) {1524 printErrorOrWarning();1525 BC.errs() << (StaleSampleCount + InferredSampleCount) << " out of "1526 << TotalSampleCount << " samples in the binary ("1527 << format("%.1f",1528 ((100.0f * (StaleSampleCount + InferredSampleCount)) /1529 TotalSampleCount))1530 << "%) belong to functions with invalid"1531 " (possibly stale) profile.\n";1532 }1533 if (PctStale > opts::StaleThreshold) {1534 return createFatalBOLTError(1535 Twine("BOLT-ERROR: stale functions exceed specified threshold of ") +1536 Twine(opts::StaleThreshold.getValue()) + Twine("%. Exiting.\n"));1537 }1538 }1539 if (NumInferredFunctions) {1540 BC.outs() << format(1541 "BOLT-INFO: inferred profile for %d (%.2f%% of profiled, "1542 "%.2f%% of stale) functions responsible for %.2f%% samples"1543 " (%zu out of %zu)\n",1544 NumInferredFunctions,1545 100.0 * NumInferredFunctions / NumAllProfiledFunctions,1546 100.0 * NumInferredFunctions / NumAllStaleFunctions,1547 100.0 * InferredSampleCount / TotalSampleCount, InferredSampleCount,1548 TotalSampleCount);1549 BC.outs() << format(1550 "BOLT-INFO: inference found an exact match for %.2f%% of basic blocks"1551 " (%zu out of %zu stale) responsible for %.2f%% samples"1552 " (%zu out of %zu stale)\n",1553 100.0 * BC.Stats.NumExactMatchedBlocks / BC.Stats.NumStaleBlocks,1554 BC.Stats.NumExactMatchedBlocks, BC.Stats.NumStaleBlocks,1555 100.0 * BC.Stats.ExactMatchedSampleCount / BC.Stats.StaleSampleCount,1556 BC.Stats.ExactMatchedSampleCount, BC.Stats.StaleSampleCount);1557 BC.outs() << format(1558 "BOLT-INFO: inference found an exact pseudo probe match for %.2f%% of "1559 "basic blocks (%zu out of %zu stale) responsible for %.2f%% samples"1560 " (%zu out of %zu stale)\n",1561 100.0 * BC.Stats.NumPseudoProbeExactMatchedBlocks /1562 BC.Stats.NumStaleBlocks,1563 BC.Stats.NumPseudoProbeExactMatchedBlocks, BC.Stats.NumStaleBlocks,1564 100.0 * BC.Stats.PseudoProbeExactMatchedSampleCount /1565 BC.Stats.StaleSampleCount,1566 BC.Stats.PseudoProbeExactMatchedSampleCount, BC.Stats.StaleSampleCount);1567 BC.outs() << format(1568 "BOLT-INFO: inference found a loose pseudo probe match for %.2f%% of "1569 "basic blocks (%zu out of %zu stale) responsible for %.2f%% samples"1570 " (%zu out of %zu stale)\n",1571 100.0 * BC.Stats.NumPseudoProbeLooseMatchedBlocks /1572 BC.Stats.NumStaleBlocks,1573 BC.Stats.NumPseudoProbeLooseMatchedBlocks, BC.Stats.NumStaleBlocks,1574 100.0 * BC.Stats.PseudoProbeLooseMatchedSampleCount /1575 BC.Stats.StaleSampleCount,1576 BC.Stats.PseudoProbeLooseMatchedSampleCount, BC.Stats.StaleSampleCount);1577 BC.outs() << format(1578 "BOLT-INFO: inference found a call match for %.2f%% of basic "1579 "blocks"1580 " (%zu out of %zu stale) responsible for %.2f%% samples"1581 " (%zu out of %zu stale)\n",1582 100.0 * BC.Stats.NumCallMatchedBlocks / BC.Stats.NumStaleBlocks,1583 BC.Stats.NumCallMatchedBlocks, BC.Stats.NumStaleBlocks,1584 100.0 * BC.Stats.CallMatchedSampleCount / BC.Stats.StaleSampleCount,1585 BC.Stats.CallMatchedSampleCount, BC.Stats.StaleSampleCount);1586 BC.outs() << format(1587 "BOLT-INFO: inference found a loose match for %.2f%% of basic "1588 "blocks"1589 " (%zu out of %zu stale) responsible for %.2f%% samples"1590 " (%zu out of %zu stale)\n",1591 100.0 * BC.Stats.NumLooseMatchedBlocks / BC.Stats.NumStaleBlocks,1592 BC.Stats.NumLooseMatchedBlocks, BC.Stats.NumStaleBlocks,1593 100.0 * BC.Stats.LooseMatchedSampleCount / BC.Stats.StaleSampleCount,1594 BC.Stats.LooseMatchedSampleCount, BC.Stats.StaleSampleCount);1595 }1596 1597 if (const uint64_t NumUnusedObjects = BC.getNumUnusedProfiledObjects()) {1598 BC.outs() << "BOLT-INFO: profile for " << NumUnusedObjects1599 << " objects was ignored\n";1600 }1601 1602 if (ProfiledFunctions.size() > 10) {1603 if (opts::Verbosity >= 1) {1604 BC.outs() << "BOLT-INFO: top called functions are:\n";1605 llvm::sort(ProfiledFunctions,1606 [](const BinaryFunction *A, const BinaryFunction *B) {1607 return B->getExecutionCount() < A->getExecutionCount();1608 });1609 auto SFI = ProfiledFunctions.begin();1610 auto SFIend = ProfiledFunctions.end();1611 for (unsigned I = 0u; I < opts::TopCalledLimit && SFI != SFIend;1612 ++SFI, ++I)1613 BC.outs() << " " << **SFI << " : " << (*SFI)->getExecutionCount()1614 << '\n';1615 }1616 }1617 1618 if (!opts::PrintSortedBy.empty()) {1619 std::vector<BinaryFunction *> Functions;1620 std::map<const BinaryFunction *, DynoStats> Stats;1621 1622 for (auto &BFI : BC.getBinaryFunctions()) {1623 BinaryFunction &BF = BFI.second;1624 if (shouldOptimize(BF) && BF.hasValidProfile()) {1625 Functions.push_back(&BF);1626 Stats.emplace(&BF, getDynoStats(BF));1627 }1628 }1629 1630 const bool SortAll =1631 llvm::is_contained(opts::PrintSortedBy, DynoStats::LAST_DYNO_STAT);1632 1633 const bool Ascending =1634 opts::DynoStatsSortOrderOpt == opts::DynoStatsSortOrder::Ascending;1635 1636 std::function<bool(const DynoStats &, const DynoStats &)>1637 DynoStatsComparator =1638 SortAll ? [](const DynoStats &StatsA,1639 const DynoStats &StatsB) { return StatsA < StatsB; }1640 : [](const DynoStats &StatsA, const DynoStats &StatsB) {1641 return StatsA.lessThan(StatsB, opts::PrintSortedBy);1642 };1643 1644 llvm::stable_sort(Functions,1645 [Ascending, &Stats, DynoStatsComparator](1646 const BinaryFunction *A, const BinaryFunction *B) {1647 auto StatsItr = Stats.find(A);1648 assert(StatsItr != Stats.end());1649 const DynoStats &StatsA = StatsItr->second;1650 1651 StatsItr = Stats.find(B);1652 assert(StatsItr != Stats.end());1653 const DynoStats &StatsB = StatsItr->second;1654 1655 return Ascending ? DynoStatsComparator(StatsA, StatsB)1656 : DynoStatsComparator(StatsB, StatsA);1657 });1658 1659 BC.outs() << "BOLT-INFO: top functions sorted by ";1660 if (SortAll) {1661 BC.outs() << "dyno stats";1662 } else {1663 BC.outs() << "(";1664 bool PrintComma = false;1665 for (const DynoStats::Category Category : opts::PrintSortedBy) {1666 if (PrintComma)1667 BC.outs() << ", ";1668 BC.outs() << DynoStats::Description(Category);1669 PrintComma = true;1670 }1671 BC.outs() << ")";1672 }1673 1674 BC.outs() << " are:\n";1675 auto SFI = Functions.begin();1676 for (unsigned I = 0; I < 100 && SFI != Functions.end(); ++SFI, ++I) {1677 const DynoStats Stats = getDynoStats(**SFI);1678 BC.outs() << " " << **SFI;1679 if (!SortAll) {1680 BC.outs() << " (";1681 bool PrintComma = false;1682 for (const DynoStats::Category Category : opts::PrintSortedBy) {1683 if (PrintComma)1684 BC.outs() << ", ";1685 BC.outs() << dynoStatsOptName(Category) << "=" << Stats[Category];1686 PrintComma = true;1687 }1688 BC.outs() << ")";1689 }1690 BC.outs() << "\n";1691 }1692 }1693 1694 if (!BC.TrappedFunctions.empty()) {1695 BC.errs() << "BOLT-WARNING: " << BC.TrappedFunctions.size() << " function"1696 << (BC.TrappedFunctions.size() > 1 ? "s" : "")1697 << " will trap on entry. Use -trap-avx512=0 to disable"1698 " traps.";1699 if (opts::Verbosity >= 1 || BC.TrappedFunctions.size() <= 5) {1700 BC.errs() << '\n';1701 for (const BinaryFunction *Function : BC.TrappedFunctions)1702 BC.errs() << " " << *Function << '\n';1703 } else {1704 BC.errs() << " Use -v=1 to see the list.\n";1705 }1706 }1707 1708 // Collect and print information about suboptimal code layout on input.1709 if (opts::ReportBadLayout) {1710 std::vector<BinaryFunction *> SuboptimalFuncs;1711 for (auto &BFI : BC.getBinaryFunctions()) {1712 BinaryFunction &BF = BFI.second;1713 if (!BF.hasValidProfile())1714 continue;1715 1716 const uint64_t HotThreshold =1717 std::max<uint64_t>(BF.getKnownExecutionCount(), 1);1718 bool HotSeen = false;1719 for (const BinaryBasicBlock *BB : BF.getLayout().rblocks()) {1720 if (!HotSeen && BB->getKnownExecutionCount() > HotThreshold) {1721 HotSeen = true;1722 continue;1723 }1724 if (HotSeen && BB->getKnownExecutionCount() == 0) {1725 SuboptimalFuncs.push_back(&BF);1726 break;1727 }1728 }1729 }1730 1731 if (!SuboptimalFuncs.empty()) {1732 llvm::sort(SuboptimalFuncs,1733 [](const BinaryFunction *A, const BinaryFunction *B) {1734 return A->getKnownExecutionCount() / A->getSize() >1735 B->getKnownExecutionCount() / B->getSize();1736 });1737 1738 BC.outs() << "BOLT-INFO: " << SuboptimalFuncs.size()1739 << " functions have "1740 "cold code in the middle of hot code. Top functions are:\n";1741 for (unsigned I = 0;1742 I < std::min(static_cast<size_t>(opts::ReportBadLayout),1743 SuboptimalFuncs.size());1744 ++I)1745 SuboptimalFuncs[I]->print(BC.outs());1746 }1747 }1748 1749 if (NumUnknownControlFlowFunctions) {1750 BC.outs() << "BOLT-INFO: " << NumUnknownControlFlowFunctions1751 << " functions have instructions with unknown control flow";1752 if (!opts::PrintUnknown)1753 BC.outs() << ". Use -print-unknown to see the list.";1754 BC.outs() << '\n';1755 }1756 1757 if (opts::ShowDensity) {1758 double Density = 0.0;1759 llvm::sort(FuncDensityList);1760 1761 uint64_t AccumulatedSamples = 0;1762 assert(opts::ProfileDensityCutOffHot <= 1000000 &&1763 "The cutoff value is greater than 1000000(100%)");1764 // Subtract samples in zero-density functions (no fall-throughs) from1765 // TotalSampleCount (not used anywhere below).1766 for (const auto [CurDensity, CurSamples] : FuncDensityList) {1767 if (CurDensity != 0.0)1768 break;1769 TotalSampleCount -= CurSamples;1770 }1771 const uint64_t CutoffSampleCount =1772 1.f * TotalSampleCount * opts::ProfileDensityCutOffHot / 1000000;1773 // Process functions in decreasing density order1774 for (const auto [CurDensity, CurSamples] : llvm::reverse(FuncDensityList)) {1775 if (AccumulatedSamples >= CutoffSampleCount)1776 break;1777 AccumulatedSamples += CurSamples;1778 Density = CurDensity;1779 }1780 if (Density == 0.0) {1781 BC.errs() << "BOLT-WARNING: the output profile is empty or the "1782 "--profile-density-cutoff-hot option is "1783 "set too low. Please check your command.\n";1784 } else if (Density < opts::ProfileDensityThreshold) {1785 BC.errs()1786 << "BOLT-WARNING: BOLT is estimated to optimize better with "1787 << format("%.1f", opts::ProfileDensityThreshold / Density)1788 << "x more samples. Please consider increasing sampling rate or "1789 "profiling for longer duration to get more samples.\n";1790 }1791 1792 BC.outs() << "BOLT-INFO: Functions with density >= "1793 << format("%.1f", Density) << " account for "1794 << format("%.2f",1795 static_cast<double>(opts::ProfileDensityCutOffHot) /1796 10000)1797 << "% total sample counts.\n";1798 }1799 return Error::success();1800}1801 1802Error InstructionLowering::runOnFunctions(BinaryContext &BC) {1803 for (auto &BFI : BC.getBinaryFunctions())1804 for (BinaryBasicBlock &BB : BFI.second)1805 for (MCInst &Instruction : BB)1806 BC.MIB->lowerTailCall(Instruction);1807 return Error::success();1808}1809 1810Error StripRepRet::runOnFunctions(BinaryContext &BC) {1811 if (!BC.isX86())1812 return Error::success();1813 1814 uint64_t NumPrefixesRemoved = 0;1815 uint64_t NumBytesSaved = 0;1816 for (auto &BFI : BC.getBinaryFunctions()) {1817 for (BinaryBasicBlock &BB : BFI.second) {1818 auto LastInstRIter = BB.getLastNonPseudo();1819 if (LastInstRIter == BB.rend() || !BC.MIB->isReturn(*LastInstRIter) ||1820 !BC.MIB->deleteREPPrefix(*LastInstRIter))1821 continue;1822 1823 NumPrefixesRemoved += BB.getKnownExecutionCount();1824 ++NumBytesSaved;1825 }1826 }1827 1828 if (NumBytesSaved)1829 BC.outs() << "BOLT-INFO: removed " << NumBytesSaved1830 << " 'repz' prefixes"1831 " with estimated execution count of "1832 << NumPrefixesRemoved << " times.\n";1833 return Error::success();1834}1835 1836Error InlineMemcpy::runOnFunctions(BinaryContext &BC) {1837 if (!BC.isX86() && !BC.isAArch64())1838 return Error::success();1839 1840 uint64_t NumInlined = 0;1841 uint64_t NumInlinedDyno = 0;1842 for (auto &BFI : BC.getBinaryFunctions()) {1843 for (BinaryBasicBlock &BB : BFI.second) {1844 for (auto II = BB.begin(); II != BB.end(); ++II) {1845 MCInst &Inst = *II;1846 1847 if (!BC.MIB->isCall(Inst) || MCPlus::getNumPrimeOperands(Inst) != 1 ||1848 !Inst.getOperand(0).isExpr())1849 continue;1850 1851 const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(Inst);1852 if (CalleeSymbol->getName() != "memcpy" &&1853 CalleeSymbol->getName() != "memcpy@PLT" &&1854 CalleeSymbol->getName() != "_memcpy8")1855 continue;1856 1857 const bool IsMemcpy8 = (CalleeSymbol->getName() == "_memcpy8");1858 const bool IsTailCall = BC.MIB->isTailCall(Inst);1859 1860 // Extract size from preceding instructions (AArch64 only).1861 // Pattern: MOV X2, #nb-bytes; BL memcpy src, dest, X2.1862 std::optional<uint64_t> KnownSize =1863 BC.MIB->findMemcpySizeInBytes(BB, II);1864 1865 if (BC.isAArch64() && (!KnownSize.has_value() || *KnownSize > 64))1866 continue;1867 1868 const InstructionListType NewCode =1869 BC.MIB->createInlineMemcpy(IsMemcpy8, KnownSize);1870 II = BB.replaceInstruction(II, NewCode);1871 std::advance(II, NewCode.size() - 1);1872 if (IsTailCall) {1873 MCInst Return;1874 BC.MIB->createReturn(Return);1875 II = BB.insertInstruction(std::next(II), std::move(Return));1876 }1877 1878 ++NumInlined;1879 NumInlinedDyno += BB.getKnownExecutionCount();1880 }1881 }1882 }1883 1884 if (NumInlined) {1885 BC.outs() << "BOLT-INFO: inlined " << NumInlined << " memcpy() calls";1886 if (NumInlinedDyno)1887 BC.outs() << ". The calls were executed " << NumInlinedDyno1888 << " times based on profile.";1889 BC.outs() << '\n';1890 }1891 return Error::success();1892}1893 1894bool SpecializeMemcpy1::shouldOptimize(const BinaryFunction &Function) const {1895 if (!BinaryFunctionPass::shouldOptimize(Function))1896 return false;1897 1898 for (const std::string &FunctionSpec : Spec) {1899 StringRef FunctionName = StringRef(FunctionSpec).split(':').first;1900 if (Function.hasNameRegex(FunctionName))1901 return true;1902 }1903 1904 return false;1905}1906 1907std::set<size_t> SpecializeMemcpy1::getCallSitesToOptimize(1908 const BinaryFunction &Function) const {1909 StringRef SitesString;1910 for (const std::string &FunctionSpec : Spec) {1911 StringRef FunctionName;1912 std::tie(FunctionName, SitesString) = StringRef(FunctionSpec).split(':');1913 if (Function.hasNameRegex(FunctionName))1914 break;1915 SitesString = "";1916 }1917 1918 std::set<size_t> Sites;1919 SmallVector<StringRef, 4> SitesVec;1920 SitesString.split(SitesVec, ':');1921 for (StringRef SiteString : SitesVec) {1922 if (SiteString.empty())1923 continue;1924 size_t Result;1925 if (!SiteString.getAsInteger(10, Result))1926 Sites.emplace(Result);1927 }1928 1929 return Sites;1930}1931 1932Error SpecializeMemcpy1::runOnFunctions(BinaryContext &BC) {1933 if (!BC.isX86())1934 return Error::success();1935 1936 uint64_t NumSpecialized = 0;1937 uint64_t NumSpecializedDyno = 0;1938 for (auto &BFI : BC.getBinaryFunctions()) {1939 BinaryFunction &Function = BFI.second;1940 if (!shouldOptimize(Function))1941 continue;1942 1943 std::set<size_t> CallsToOptimize = getCallSitesToOptimize(Function);1944 auto shouldOptimize = [&](size_t N) {1945 return CallsToOptimize.empty() || CallsToOptimize.count(N);1946 };1947 1948 std::vector<BinaryBasicBlock *> Blocks(Function.pbegin(), Function.pend());1949 size_t CallSiteID = 0;1950 for (BinaryBasicBlock *CurBB : Blocks) {1951 for (auto II = CurBB->begin(); II != CurBB->end(); ++II) {1952 MCInst &Inst = *II;1953 1954 if (!BC.MIB->isCall(Inst) || MCPlus::getNumPrimeOperands(Inst) != 1 ||1955 !Inst.getOperand(0).isExpr())1956 continue;1957 1958 const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(Inst);1959 if (CalleeSymbol->getName() != "memcpy" &&1960 CalleeSymbol->getName() != "memcpy@PLT")1961 continue;1962 1963 if (BC.MIB->isTailCall(Inst))1964 continue;1965 1966 ++CallSiteID;1967 1968 if (!shouldOptimize(CallSiteID))1969 continue;1970 1971 // Create a copy of a call to memcpy(dest, src, size).1972 MCInst MemcpyInstr = Inst;1973 1974 BinaryBasicBlock *OneByteMemcpyBB = CurBB->splitAt(II);1975 1976 BinaryBasicBlock *NextBB = nullptr;1977 if (OneByteMemcpyBB->getNumNonPseudos() > 1) {1978 NextBB = OneByteMemcpyBB->splitAt(OneByteMemcpyBB->begin());1979 NextBB->eraseInstruction(NextBB->begin());1980 } else {1981 NextBB = OneByteMemcpyBB->getSuccessor();1982 OneByteMemcpyBB->eraseInstruction(OneByteMemcpyBB->begin());1983 assert(NextBB && "unexpected call to memcpy() with no return");1984 }1985 1986 BinaryBasicBlock *MemcpyBB = Function.addBasicBlock();1987 MemcpyBB->setOffset(CurBB->getInputOffset());1988 InstructionListType CmpJCC =1989 BC.MIB->createCmpJE(BC.MIB->getIntArgRegister(2), 1,1990 OneByteMemcpyBB->getLabel(), BC.Ctx.get());1991 CurBB->addInstructions(CmpJCC);1992 CurBB->addSuccessor(MemcpyBB);1993 1994 MemcpyBB->addInstruction(std::move(MemcpyInstr));1995 MemcpyBB->addSuccessor(NextBB);1996 MemcpyBB->setCFIState(NextBB->getCFIState());1997 MemcpyBB->setExecutionCount(0);1998 1999 // To prevent the actual call from being moved to cold, we set its2000 // execution count to 1.2001 if (CurBB->getKnownExecutionCount() > 0)2002 MemcpyBB->setExecutionCount(1);2003 2004 InstructionListType OneByteMemcpy = BC.MIB->createOneByteMemcpy();2005 OneByteMemcpyBB->addInstructions(OneByteMemcpy);2006 2007 ++NumSpecialized;2008 NumSpecializedDyno += CurBB->getKnownExecutionCount();2009 2010 CurBB = NextBB;2011 2012 // Note: we don't expect the next instruction to be a call to memcpy.2013 II = CurBB->begin();2014 }2015 }2016 }2017 2018 if (NumSpecialized) {2019 BC.outs() << "BOLT-INFO: specialized " << NumSpecialized2020 << " memcpy() call sites for size 1";2021 if (NumSpecializedDyno)2022 BC.outs() << ". The calls were executed " << NumSpecializedDyno2023 << " times based on profile.";2024 BC.outs() << '\n';2025 }2026 return Error::success();2027}2028 2029void RemoveNops::runOnFunction(BinaryFunction &BF) {2030 const BinaryContext &BC = BF.getBinaryContext();2031 for (BinaryBasicBlock &BB : BF) {2032 for (int64_t I = BB.size() - 1; I >= 0; --I) {2033 MCInst &Inst = BB.getInstructionAtIndex(I);2034 if (BC.MIB->isNoop(Inst) && BC.MIB->hasAnnotation(Inst, "NOP"))2035 BB.eraseInstructionAtIndex(I);2036 }2037 }2038}2039 2040Error RemoveNops::runOnFunctions(BinaryContext &BC) {2041 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {2042 runOnFunction(BF);2043 };2044 2045 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {2046 return BF.shouldPreserveNops();2047 };2048 2049 ParallelUtilities::runOnEachFunction(2050 BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,2051 SkipFunc, "RemoveNops");2052 return Error::success();2053}2054 2055} // namespace bolt2056} // namespace llvm2057