570 lines · cpp
1//===- bolt/Rewrite/BinaryPassManager.cpp - Binary-level pass manager -----===//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#include "bolt/Rewrite/BinaryPassManager.h"10#include "bolt/Passes/AArch64RelaxationPass.h"11#include "bolt/Passes/Aligner.h"12#include "bolt/Passes/AllocCombiner.h"13#include "bolt/Passes/AsmDump.h"14#include "bolt/Passes/CMOVConversion.h"15#include "bolt/Passes/FixRISCVCallsPass.h"16#include "bolt/Passes/FixRelaxationPass.h"17#include "bolt/Passes/FrameOptimizer.h"18#include "bolt/Passes/Hugify.h"19#include "bolt/Passes/IdenticalCodeFolding.h"20#include "bolt/Passes/IndirectCallPromotion.h"21#include "bolt/Passes/Inliner.h"22#include "bolt/Passes/InsertNegateRAStatePass.h"23#include "bolt/Passes/Instrumentation.h"24#include "bolt/Passes/JTFootprintReduction.h"25#include "bolt/Passes/LongJmp.h"26#include "bolt/Passes/LoopInversionPass.h"27#include "bolt/Passes/MCF.h"28#include "bolt/Passes/MarkRAStates.h"29#include "bolt/Passes/PLTCall.h"30#include "bolt/Passes/PatchEntries.h"31#include "bolt/Passes/ProfileQualityStats.h"32#include "bolt/Passes/RegReAssign.h"33#include "bolt/Passes/ReorderData.h"34#include "bolt/Passes/ReorderFunctions.h"35#include "bolt/Passes/RetpolineInsertion.h"36#include "bolt/Passes/SplitFunctions.h"37#include "bolt/Passes/StokeInfo.h"38#include "bolt/Passes/TailDuplication.h"39#include "bolt/Passes/ThreeWayBranch.h"40#include "bolt/Passes/ValidateInternalCalls.h"41#include "bolt/Passes/ValidateMemRefs.h"42#include "bolt/Passes/VeneerElimination.h"43#include "bolt/Utils/CommandLineOpts.h"44#include "llvm/Support/FormatVariadic.h"45#include "llvm/Support/Timer.h"46#include "llvm/Support/raw_ostream.h"47#include <memory>48#include <numeric>49 50using namespace llvm;51 52namespace opts {53 54extern cl::opt<bool> PrintAll;55extern cl::opt<bool> PrintDynoStats;56extern cl::opt<bool> DumpDotAll;57extern bool shouldDumpDot(const bolt::BinaryFunction &Function);58extern cl::opt<std::string> AsmDump;59extern cl::opt<bolt::PLTCall::OptType> PLT;60extern cl::opt<bolt::IdenticalCodeFolding::ICFLevel, false,61 llvm::bolt::DeprecatedICFNumericOptionParser>62 ICF;63 64static cl::opt<bool>65DynoStatsAll("dyno-stats-all",66 cl::desc("print dyno stats after each stage"),67 cl::ZeroOrMore, cl::Hidden, cl::cat(BoltCategory));68 69static cl::opt<bool>70 EliminateUnreachable("eliminate-unreachable",71 cl::desc("eliminate unreachable code"), cl::init(true),72 cl::cat(BoltOptCategory));73 74static cl::opt<bool> JTFootprintReductionFlag(75 "jt-footprint-reduction",76 cl::desc("make jump tables size smaller at the cost of using more "77 "instructions at jump sites"),78 cl::cat(BoltOptCategory));79 80cl::opt<bool>81 KeepNops("keep-nops",82 cl::desc("keep no-op instructions. By default they are removed."),83 cl::Hidden, cl::cat(BoltOptCategory));84 85cl::opt<bool> NeverPrint("never-print", cl::desc("never print"),86 cl::ReallyHidden, cl::cat(BoltOptCategory));87 88cl::opt<bool>89PrintAfterBranchFixup("print-after-branch-fixup",90 cl::desc("print function after fixing local branches"),91 cl::Hidden, cl::cat(BoltOptCategory));92 93static cl::opt<bool>94PrintAfterLowering("print-after-lowering",95 cl::desc("print function after instruction lowering"),96 cl::Hidden, cl::cat(BoltOptCategory));97 98static cl::opt<bool> PrintEstimateEdgeCounts(99 "print-estimate-edge-counts",100 cl::desc("print function after edge counts are set for no-LBR profile"),101 cl::Hidden, cl::cat(BoltOptCategory));102 103cl::opt<bool>104PrintFinalized("print-finalized",105 cl::desc("print function after CFG is finalized"),106 cl::Hidden, cl::cat(BoltOptCategory));107 108static cl::opt<bool>109 PrintFOP("print-fop",110 cl::desc("print functions after frame optimizer pass"), cl::Hidden,111 cl::cat(BoltOptCategory));112 113static cl::opt<bool>114 PrintICF("print-icf", cl::desc("print functions after ICF optimization"),115 cl::Hidden, cl::cat(BoltOptCategory));116 117static cl::opt<bool>118 PrintICP("print-icp",119 cl::desc("print functions after indirect call promotion"),120 cl::Hidden, cl::cat(BoltOptCategory));121 122static cl::opt<bool>123 PrintInline("print-inline",124 cl::desc("print functions after inlining optimization"),125 cl::Hidden, cl::cat(BoltOptCategory));126 127static cl::opt<bool> PrintJTFootprintReduction(128 "print-after-jt-footprint-reduction",129 cl::desc("print function after jt-footprint-reduction pass"), cl::Hidden,130 cl::cat(BoltOptCategory));131 132static cl::opt<bool> PrintAArch64Relaxation(133 "print-adr-ldr-relaxation",134 cl::desc("print functions after ADR/LDR Relaxation pass"), cl::Hidden,135 cl::cat(BoltOptCategory));136 137static cl::opt<bool>138 PrintLongJmp("print-longjmp",139 cl::desc("print functions after longjmp pass"), cl::Hidden,140 cl::cat(BoltOptCategory));141 142cl::opt<bool>143 PrintNormalized("print-normalized",144 cl::desc("print functions after CFG is normalized"),145 cl::Hidden, cl::cat(BoltCategory));146 147static cl::opt<bool> PrintOptimizeBodyless(148 "print-optimize-bodyless",149 cl::desc("print functions after bodyless optimization"), cl::Hidden,150 cl::cat(BoltOptCategory));151 152static cl::opt<bool>153 PrintPeepholes("print-peepholes",154 cl::desc("print functions after peephole optimization"),155 cl::Hidden, cl::cat(BoltOptCategory));156 157static cl::opt<bool>158 PrintPLT("print-plt", cl::desc("print functions after PLT optimization"),159 cl::Hidden, cl::cat(BoltOptCategory));160 161static cl::opt<bool>162 PrintProfileStats("print-profile-stats",163 cl::desc("print profile quality/bias analysis"),164 cl::cat(BoltCategory));165 166static cl::opt<bool>167 PrintRegReAssign("print-regreassign",168 cl::desc("print functions after regreassign pass"),169 cl::Hidden, cl::cat(BoltOptCategory));170 171cl::opt<bool>172 PrintReordered("print-reordered",173 cl::desc("print functions after layout optimization"),174 cl::Hidden, cl::cat(BoltOptCategory));175 176static cl::opt<bool>177 PrintReorderedFunctions("print-reordered-functions",178 cl::desc("print functions after clustering"),179 cl::Hidden, cl::cat(BoltOptCategory));180 181static cl::opt<bool> PrintRetpolineInsertion(182 "print-retpoline-insertion",183 cl::desc("print functions after retpoline insertion pass"), cl::Hidden,184 cl::cat(BoltCategory));185 186static cl::opt<bool> PrintSCTC(187 "print-sctc",188 cl::desc("print functions after conditional tail call simplification"),189 cl::Hidden, cl::cat(BoltOptCategory));190 191static cl::opt<bool> PrintSimplifyROLoads(192 "print-simplify-rodata-loads",193 cl::desc("print functions after simplification of RO data loads"),194 cl::Hidden, cl::cat(BoltOptCategory));195 196static cl::opt<bool>197 PrintSplit("print-split", cl::desc("print functions after code splitting"),198 cl::Hidden, cl::cat(BoltOptCategory));199 200static cl::opt<bool>201 PrintStoke("print-stoke", cl::desc("print functions after stoke analysis"),202 cl::Hidden, cl::cat(BoltOptCategory));203 204static cl::opt<bool>205 PrintFixRelaxations("print-fix-relaxations",206 cl::desc("print functions after fix relaxations pass"),207 cl::Hidden, cl::cat(BoltOptCategory));208 209static cl::opt<bool>210 PrintFixRISCVCalls("print-fix-riscv-calls",211 cl::desc("print functions after fix RISCV calls pass"),212 cl::Hidden, cl::cat(BoltOptCategory));213 214static cl::opt<bool> PrintVeneerElimination(215 "print-veneer-elimination",216 cl::desc("print functions after veneer elimination pass"), cl::Hidden,217 cl::cat(BoltOptCategory));218 219static cl::opt<bool>220 PrintUCE("print-uce",221 cl::desc("print functions after unreachable code elimination"),222 cl::Hidden, cl::cat(BoltOptCategory));223 224static cl::opt<bool> RegReAssign(225 "reg-reassign",226 cl::desc(227 "reassign registers so as to avoid using REX prefixes in hot code"),228 cl::cat(BoltOptCategory));229 230static cl::opt<bool> SimplifyConditionalTailCalls(231 "simplify-conditional-tail-calls",232 cl::desc("simplify conditional tail calls by removing unnecessary jumps"),233 cl::init(true), cl::cat(BoltOptCategory));234 235static cl::opt<bool> SimplifyRODataLoads(236 "simplify-rodata-loads",237 cl::desc("simplify loads from read-only sections by replacing the memory "238 "operand with the constant found in the corresponding section"),239 cl::cat(BoltOptCategory));240 241static cl::list<std::string>242SpecializeMemcpy1("memcpy1-spec",243 cl::desc("list of functions with call sites for which to specialize memcpy() "244 "for size 1"),245 cl::value_desc("func1,func2:cs1:cs2,func3:cs1,..."),246 cl::ZeroOrMore, cl::cat(BoltOptCategory));247 248static cl::opt<bool> Stoke("stoke", cl::desc("turn on the stoke analysis"),249 cl::cat(BoltOptCategory));250 251static cl::opt<bool> StringOps(252 "inline-memcpy",253 cl::desc(254 "inline memcpy using size-specific optimized instructions "255 "(X86: 'rep movsb', AArch64: width-optimized register operations)"),256 cl::cat(BoltOptCategory));257 258static cl::opt<bool> StripRepRet(259 "strip-rep-ret",260 cl::desc("strip 'repz' prefix from 'repz retq' sequence (on by default)"),261 cl::init(true), cl::cat(BoltOptCategory));262 263static cl::opt<bool> VerifyCFG("verify-cfg",264 cl::desc("verify the CFG after every pass"),265 cl::Hidden, cl::cat(BoltOptCategory));266 267static cl::opt<bool> ThreeWayBranchFlag("three-way-branch",268 cl::desc("reorder three way branches"),269 cl::ReallyHidden,270 cl::cat(BoltOptCategory));271 272static cl::opt<bool> CMOVConversionFlag("cmov-conversion",273 cl::desc("fold jcc+mov into cmov"),274 cl::ReallyHidden,275 cl::cat(BoltOptCategory));276 277static cl::opt<bool> ShortenInstructions("shorten-instructions",278 cl::desc("shorten instructions"),279 cl::init(true),280 cl::cat(BoltOptCategory));281 282cl::opt<bool>283 UpdateBranchProtection("update-branch-protection",284 cl::desc("Rewrites pac-ret DWARF CFI instructions "285 "(AArch64-only, on by default)"),286 cl::init(true), cl::Hidden, cl::cat(BoltCategory));287} // namespace opts288 289namespace llvm {290namespace bolt {291 292using namespace opts;293 294const char BinaryFunctionPassManager::TimerGroupName[] = "passman";295const char BinaryFunctionPassManager::TimerGroupDesc[] =296 "Binary Function Pass Manager";297 298Error BinaryFunctionPassManager::runPasses() {299 auto &BFs = BC.getBinaryFunctions();300 for (size_t PassIdx = 0; PassIdx < Passes.size(); PassIdx++) {301 const std::pair<const bool, std::unique_ptr<BinaryFunctionPass>>302 &OptPassPair = Passes[PassIdx];303 if (!OptPassPair.first)304 continue;305 306 const std::unique_ptr<BinaryFunctionPass> &Pass = OptPassPair.second;307 std::string PassIdName =308 formatv("{0:2}_{1}", PassIdx, Pass->getName()).str();309 310 if (opts::Verbosity > 0)311 BC.outs() << "BOLT-INFO: Starting pass: " << Pass->getName() << "\n";312 313 NamedRegionTimer T(Pass->getName(), Pass->getName(), TimerGroupName,314 TimerGroupDesc, TimeOpts);315 316 Error E = Error::success();317 callWithDynoStats(318 BC.outs(),319 [this, &E, &Pass] {320 E = joinErrors(std::move(E), Pass->runOnFunctions(BC));321 },322 BFs, Pass->getName(), opts::DynoStatsAll, BC.isAArch64());323 if (E)324 return Error(std::move(E));325 326 if (opts::VerifyCFG &&327 !std::accumulate(328 BFs.begin(), BFs.end(), true,329 [](const bool Valid,330 const std::pair<const uint64_t, BinaryFunction> &It) {331 return Valid && It.second.validateCFG();332 })) {333 return createFatalBOLTError(334 Twine("BOLT-ERROR: Invalid CFG detected after pass ") +335 Twine(Pass->getName()) + Twine("\n"));336 }337 338 if (opts::Verbosity > 0)339 BC.outs() << "BOLT-INFO: Finished pass: " << Pass->getName() << "\n";340 341 if (!opts::PrintAll && !opts::DumpDotAll && !Pass->printPass())342 continue;343 344 const std::string Message = std::string("after ") + Pass->getName();345 346 for (auto &It : BFs) {347 BinaryFunction &Function = It.second;348 349 if (!Pass->shouldPrint(Function))350 continue;351 352 Function.print(BC.outs(), Message);353 354 if (opts::shouldDumpDot(Function))355 Function.dumpGraphForPass(PassIdName);356 }357 }358 return Error::success();359}360 361Error BinaryFunctionPassManager::runAllPasses(BinaryContext &BC) {362 BinaryFunctionPassManager Manager(BC);363 364 if (BC.isAArch64())365 Manager.registerPass(std::make_unique<MarkRAStates>());366 367 Manager.registerPass(368 std::make_unique<EstimateEdgeCounts>(PrintEstimateEdgeCounts));369 370 Manager.registerPass(std::make_unique<DynoStatsSetPass>());371 372 Manager.registerPass(std::make_unique<AsmDumpPass>(),373 opts::AsmDump.getNumOccurrences());374 375 if (BC.isAArch64()) {376 Manager.registerPass(std::make_unique<FixRelaxations>(PrintFixRelaxations));377 378 Manager.registerPass(379 std::make_unique<VeneerElimination>(PrintVeneerElimination));380 }381 382 if (BC.isRISCV()) {383 Manager.registerPass(384 std::make_unique<FixRISCVCallsPass>(PrintFixRISCVCalls));385 }386 387 // Here we manage dependencies/order manually, since passes are run in the388 // order they're registered.389 390 // Run this pass first to use stats for the original functions.391 Manager.registerPass(std::make_unique<PrintProgramStats>());392 393 if (opts::PrintProfileStats)394 Manager.registerPass(std::make_unique<PrintProfileStats>(NeverPrint));395 396 Manager.registerPass(std::make_unique<PrintProfileQualityStats>(NeverPrint));397 398 Manager.registerPass(std::make_unique<ValidateInternalCalls>(NeverPrint));399 400 Manager.registerPass(std::make_unique<ValidateMemRefs>(NeverPrint));401 402 if (opts::Instrument)403 Manager.registerPass(std::make_unique<Instrumentation>(NeverPrint));404 else if (opts::Hugify)405 Manager.registerPass(std::make_unique<HugePage>(NeverPrint));406 407 Manager.registerPass(std::make_unique<ShortenInstructions>(NeverPrint),408 opts::ShortenInstructions);409 410 Manager.registerPass(std::make_unique<RemoveNops>(NeverPrint),411 !opts::KeepNops);412 413 Manager.registerPass(std::make_unique<NormalizeCFG>(PrintNormalized));414 415 if (BC.isX86())416 Manager.registerPass(std::make_unique<StripRepRet>(NeverPrint),417 opts::StripRepRet);418 419 Manager.registerPass(std::make_unique<IdenticalCodeFolding>(PrintICF),420 opts::ICF != IdenticalCodeFolding::ICFLevel::None);421 422 Manager.registerPass(423 std::make_unique<SpecializeMemcpy1>(NeverPrint, opts::SpecializeMemcpy1),424 !opts::SpecializeMemcpy1.empty());425 426 Manager.registerPass(std::make_unique<InlineMemcpy>(NeverPrint),427 opts::StringOps);428 429 Manager.registerPass(std::make_unique<IndirectCallPromotion>(PrintICP));430 431 Manager.registerPass(432 std::make_unique<JTFootprintReduction>(PrintJTFootprintReduction),433 opts::JTFootprintReductionFlag);434 435 Manager.registerPass(436 std::make_unique<SimplifyRODataLoads>(PrintSimplifyROLoads),437 opts::SimplifyRODataLoads);438 439 Manager.registerPass(std::make_unique<RegReAssign>(PrintRegReAssign),440 opts::RegReAssign);441 442 Manager.registerPass(std::make_unique<Inliner>(PrintInline));443 444 Manager.registerPass(std::make_unique<IdenticalCodeFolding>(PrintICF),445 opts::ICF != IdenticalCodeFolding::ICFLevel::None);446 447 Manager.registerPass(std::make_unique<PLTCall>(PrintPLT));448 449 Manager.registerPass(std::make_unique<ThreeWayBranch>(),450 opts::ThreeWayBranchFlag);451 452 Manager.registerPass(std::make_unique<ReorderBasicBlocks>(PrintReordered));453 454 Manager.registerPass(std::make_unique<EliminateUnreachableBlocks>(PrintUCE),455 opts::EliminateUnreachable);456 457 Manager.registerPass(std::make_unique<SplitFunctions>(PrintSplit));458 459 Manager.registerPass(std::make_unique<LoopInversionPass>());460 461 Manager.registerPass(std::make_unique<TailDuplication>());462 463 Manager.registerPass(std::make_unique<CMOVConversion>(),464 opts::CMOVConversionFlag);465 466 // This pass syncs local branches with CFG. If any of the following467 // passes breaks the sync - they either need to re-run the pass or468 // fix branches consistency internally.469 Manager.registerPass(std::make_unique<FixupBranches>(PrintAfterBranchFixup));470 471 // This pass should come close to last since it uses the estimated hot472 // size of a function to determine the order. It should definitely473 // also happen after any changes to the call graph are made, e.g. inlining.474 Manager.registerPass(475 std::make_unique<ReorderFunctions>(PrintReorderedFunctions));476 477 // This is the second run of the SplitFunctions pass required by certain478 // splitting strategies (e.g. cdsplit). Running the SplitFunctions pass again479 // after ReorderFunctions allows the finalized function order to be utilized480 // to make more sophisticated splitting decisions, like hot-warm-cold481 // splitting.482 Manager.registerPass(std::make_unique<SplitFunctions>(PrintSplit));483 484 // Print final dyno stats right while CFG and instruction analysis are intact.485 Manager.registerPass(std::make_unique<DynoStatsPrintPass>(486 "after all optimizations before SCTC and FOP"),487 opts::PrintDynoStats || opts::DynoStatsAll);488 489 // Add the StokeInfo pass, which extract functions for stoke optimization and490 // get the liveness information for them491 Manager.registerPass(std::make_unique<StokeInfo>(PrintStoke), opts::Stoke);492 493 // This pass introduces conditional jumps into external functions.494 // Between extending CFG to support this and isolating this pass we chose495 // the latter. Thus this pass will do double jump removal and unreachable496 // code elimination if necessary and won't rely on peepholes/UCE for these497 // optimizations.498 // More generally this pass should be the last optimization pass that499 // modifies branches/control flow. This pass is run after function500 // reordering so that it can tell whether calls are forward/backward501 // accurately.502 Manager.registerPass(503 std::make_unique<SimplifyConditionalTailCalls>(PrintSCTC),504 opts::SimplifyConditionalTailCalls);505 506 Manager.registerPass(std::make_unique<Peepholes>(PrintPeepholes));507 508 Manager.registerPass(std::make_unique<AlignerPass>());509 510 // Perform reordering on data contained in one or more sections using511 // memory profiling data.512 Manager.registerPass(std::make_unique<ReorderData>());513 514 // Patch original function entries515 if (BC.HasRelocations)516 Manager.registerPass(std::make_unique<PatchEntries>());517 518 if (BC.isAArch64()) {519 Manager.registerPass(520 std::make_unique<AArch64RelaxationPass>(PrintAArch64Relaxation));521 522 // Tighten branches according to offset differences between branch and523 // targets. No extra instructions after this pass, otherwise we may have524 // relocations out of range and crash during linking.525 Manager.registerPass(std::make_unique<LongJmpPass>(PrintLongJmp));526 527 Manager.registerPass(std::make_unique<InsertNegateRAState>());528 }529 530 // This pass should always run last.*531 Manager.registerPass(std::make_unique<FinalizeFunctions>(PrintFinalized));532 533 // FrameOptimizer has an implicit dependency on FinalizeFunctions.534 // FrameOptimizer move values around and needs to update CFIs. To do this, it535 // must read CFI, interpret it and rewrite it, so CFIs need to be correctly536 // placed according to the final layout.537 Manager.registerPass(std::make_unique<FrameOptimizerPass>(PrintFOP));538 539 Manager.registerPass(std::make_unique<AllocCombinerPass>(PrintFOP));540 541 Manager.registerPass(542 std::make_unique<RetpolineInsertion>(PrintRetpolineInsertion));543 544 // Assign each function an output section.545 Manager.registerPass(std::make_unique<AssignSections>());546 547 // This pass turns tail calls into jumps which makes them invisible to548 // function reordering. It's unsafe to use any CFG or instruction analysis549 // after this point.550 Manager.registerPass(551 std::make_unique<InstructionLowering>(PrintAfterLowering));552 553 // In non-relocation mode, mark functions that do not fit into their original554 // space as non-simple if we have to (e.g. for correct debug info update).555 // NOTE: this pass depends on finalized code.556 if (!BC.HasRelocations)557 Manager.registerPass(std::make_unique<CheckLargeFunctions>(NeverPrint));558 559 Manager.registerPass(std::make_unique<LowerAnnotations>(NeverPrint));560 561 // Check for dirty state of MCSymbols caused by running calculateEmittedSize562 // in parallel and restore them563 Manager.registerPass(std::make_unique<CleanMCState>(NeverPrint));564 565 return Manager.runPasses();566}567 568} // namespace bolt569} // namespace llvm570