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