1//===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
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/// \file
10/// Replaces repeated sequences of instructions with function calls.
11///
12/// This works by placing every instruction from every basic block in a
13/// suffix tree, and repeatedly querying that tree for repeated sequences of
14/// instructions. If a sequence of instructions appears often, then it ought
15/// to be beneficial to pull out into a function.
16///
17/// The MachineOutliner communicates with a given target using hooks defined in
18/// TargetInstrInfo.h. The target supplies the outliner with information on how
19/// a specific sequence of instructions should be outlined. This information
20/// is used to deduce the number of instructions necessary to
21///
22/// * Create an outlined function
23/// * Call that outlined function
24///
25/// Targets must implement
26/// * getOutliningCandidateInfo
27/// * buildOutlinedFrame
28/// * insertOutlinedCall
29/// * isFunctionSafeToOutlineFrom
30///
31/// in order to make use of the MachineOutliner.
32///
33/// This was originally presented at the 2016 LLVM Developers' Meeting in the
34/// talk "Reducing Code Size Using Outlining". For a high-level overview of
35/// how this pass works, the talk is available on YouTube at
36///
37/// https://www.youtube.com/watch?v=yorld-WSOeU
38///
39/// The slides for the talk are available at
40///
41/// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
42///
43/// The talk provides an overview of how the outliner finds candidates and
44/// ultimately outlines them. It describes how the main data structure for this
45/// pass, the suffix tree, is queried and purged for candidates. It also gives
46/// a simplified suffix tree construction algorithm for suffix trees based off
47/// of the algorithm actually used here, Ukkonen's algorithm.
48///
49/// For the original RFC for this pass, please see
50///
51/// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
52///
53/// For more information on the suffix tree data structure, please see
54/// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
55///
56//===----------------------------------------------------------------------===//
57#include "llvm/CodeGen/MachineOutliner.h"
58#include "llvm/ADT/DenseMap.h"
59#include "llvm/ADT/SmallSet.h"
60#include "llvm/ADT/Statistic.h"
61#include "llvm/ADT/Twine.h"
62#include "llvm/Analysis/BlockFrequencyInfo.h"
63#include "llvm/Analysis/ModuleSummaryAnalysis.h"
64#include "llvm/Analysis/OptimizationRemarkEmitter.h"
65#include "llvm/Analysis/ProfileSummaryInfo.h"
66#include "llvm/CGData/CodeGenDataReader.h"
67#include "llvm/CodeGen/LivePhysRegs.h"
68#include "llvm/CodeGen/MachineInstrBundle.h"
69#include "llvm/CodeGen/MachineModuleInfo.h"
70#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
71#include "llvm/CodeGen/Passes.h"
72#include "llvm/CodeGen/TargetInstrInfo.h"
73#include "llvm/CodeGen/TargetPassConfig.h"
74#include "llvm/CodeGen/TargetSubtargetInfo.h"
75#include "llvm/IR/DIBuilder.h"
76#include "llvm/IR/IRBuilder.h"
77#include "llvm/IR/Mangler.h"
78#include "llvm/IR/Module.h"
79#include "llvm/InitializePasses.h"
80#include "llvm/Support/CommandLine.h"
81#include "llvm/Support/Debug.h"
82#include "llvm/Support/SuffixTree.h"
83#include "llvm/Support/raw_ostream.h"
84#include "llvm/Target/TargetMachine.h"
85#include "llvm/Transforms/Utils/ModuleUtils.h"
86#include <tuple>
87#include <vector>
88
89#define DEBUG_TYPE "machine-outliner"
90
91using namespace llvm;
92using namespace ore;
93using namespace outliner;
94
95// Statistics for outlined functions.
96STATISTIC(NumOutlined, "Number of candidates outlined");
97STATISTIC(FunctionsCreated, "Number of functions created");
98
99// Statistics for instruction mapping.
100STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped");
101STATISTIC(NumIllegalInUnsignedVec,
102 "Unoutlinable instructions mapped + number of sentinel values");
103STATISTIC(NumSentinels, "Sentinel values inserted during mapping");
104STATISTIC(NumInvisible,
105 "Non-debug invisible instructions skipped during mapping");
106STATISTIC(UnsignedVecSize,
107 "Total number of instructions mapped and saved to mapping vector");
108STATISTIC(StableHashAttempts,
109 "Count of hashing attempts made for outlined functions");
110STATISTIC(StableHashDropped,
111 "Count of unsuccessful hashing attempts for outlined functions");
112STATISTIC(NumRemovedLOHs, "Total number of Linker Optimization Hints removed");
113STATISTIC(NumPGOBlockedOutlined,
114 "Number of times outlining was blocked by PGO");
115STATISTIC(NumPGOAllowedCold,
116 "Number of times outlining was allowed from cold functions");
117STATISTIC(NumPGOConservativeBlockedOutlined,
118 "Number of times outlining was blocked conservatively when profile "
119 "counts were missing");
120STATISTIC(NumPGOOptimisticOutlined,
121 "Number of times outlining was allowed optimistically when profile "
122 "counts were missing");
123
124// Set to true if the user wants the outliner to run on linkonceodr linkage
125// functions. This is false by default because the linker can dedupe linkonceodr
126// functions. Since the outliner is confined to a single module (modulo LTO),
127// this is off by default. It should, however, be the default behaviour in
128// LTO.
129static cl::opt<bool> EnableLinkOnceODROutlining(
130 "enable-linkonceodr-outlining", cl::Hidden,
131 cl::desc("Enable the machine outliner on linkonceodr functions"),
132 cl::init(Val: false));
133
134/// Number of times to re-run the outliner. This is not the total number of runs
135/// as the outliner will run at least one time. The default value is set to 0,
136/// meaning the outliner will run one time and rerun zero times after that.
137static cl::opt<unsigned> OutlinerReruns(
138 "machine-outliner-reruns", cl::init(Val: 0), cl::Hidden,
139 cl::desc(
140 "Number of times to rerun the outliner after the initial outline"));
141
142static cl::opt<unsigned> OutlinerBenefitThreshold(
143 "outliner-benefit-threshold", cl::init(Val: 1), cl::Hidden,
144 cl::desc(
145 "The minimum size in bytes before an outlining candidate is accepted"));
146
147static cl::opt<bool> OutlinerLeafDescendants(
148 "outliner-leaf-descendants", cl::init(Val: true), cl::Hidden,
149 cl::desc("Consider all leaf descendants of internal nodes of the suffix "
150 "tree as candidates for outlining (if false, only leaf children "
151 "are considered)"));
152
153static cl::opt<bool>
154 DisableGlobalOutlining("disable-global-outlining", cl::Hidden,
155 cl::desc("Disable global outlining only by ignoring "
156 "the codegen data generation or use"),
157 cl::init(Val: false));
158
159static cl::opt<bool> AppendContentHashToOutlinedName(
160 "append-content-hash-outlined-name", cl::Hidden,
161 cl::desc("This appends the content hash to the globally outlined function "
162 "name. It's beneficial for enhancing the precision of the stable "
163 "hash and for ordering the outlined functions."),
164 cl::init(Val: true));
165
166namespace {
167
168/// Maps \p MachineInstrs to unsigned integers and stores the mappings.
169struct InstructionMapper {
170 const MachineModuleInfo &MMI;
171
172 /// The next available integer to assign to a \p MachineInstr that
173 /// cannot be outlined.
174 ///
175 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
176 unsigned IllegalInstrNumber = -3;
177
178 /// The next available integer to assign to a \p MachineInstr that can
179 /// be outlined.
180 unsigned LegalInstrNumber = 0;
181
182 /// Correspondence from \p MachineInstrs to unsigned integers.
183 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
184 InstructionIntegerMap;
185
186 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
187 DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
188
189 /// The vector of unsigned integers that the module is mapped to.
190 SmallVector<unsigned> UnsignedVec;
191
192 /// Stores the location of the instruction associated with the integer
193 /// at index i in \p UnsignedVec for each index i.
194 SmallVector<MachineBasicBlock::iterator> InstrList;
195
196 // Set if we added an illegal number in the previous step.
197 // Since each illegal number is unique, we only need one of them between
198 // each range of legal numbers. This lets us make sure we don't add more
199 // than one illegal number per range.
200 bool AddedIllegalLastTime = false;
201
202 /// Maps \p *It to a legal integer.
203 ///
204 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
205 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
206 ///
207 /// \returns The integer that \p *It was mapped to.
208 unsigned mapToLegalUnsigned(
209 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
210 bool &HaveLegalRange, unsigned &NumLegalInBlock,
211 SmallVector<unsigned> &UnsignedVecForMBB,
212 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {
213 // We added something legal, so we should unset the AddedLegalLastTime
214 // flag.
215 AddedIllegalLastTime = false;
216
217 // If we have at least two adjacent legal instructions (which may have
218 // invisible instructions in between), remember that.
219 if (CanOutlineWithPrevInstr)
220 HaveLegalRange = true;
221 CanOutlineWithPrevInstr = true;
222
223 // Keep track of the number of legal instructions we insert.
224 NumLegalInBlock++;
225
226 // Get the integer for this instruction or give it the current
227 // LegalInstrNumber.
228 InstrListForMBB.push_back(Elt: It);
229 MachineInstr &MI = *It;
230 bool WasInserted;
231 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
232 ResultIt;
233 std::tie(args&: ResultIt, args&: WasInserted) =
234 InstructionIntegerMap.insert(KV: std::make_pair(x: &MI, y&: LegalInstrNumber));
235 unsigned MINumber = ResultIt->second;
236
237 // There was an insertion.
238 if (WasInserted)
239 LegalInstrNumber++;
240
241 UnsignedVecForMBB.push_back(Elt: MINumber);
242
243 // Make sure we don't overflow or use any integers reserved by the DenseMap.
244 if (LegalInstrNumber >= IllegalInstrNumber)
245 report_fatal_error(reason: "Instruction mapping overflow!");
246
247 // Statistics.
248 ++NumLegalInUnsignedVec;
249 return MINumber;
250 }
251
252 /// Maps \p *It to an illegal integer.
253 ///
254 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
255 /// IllegalInstrNumber.
256 ///
257 /// \returns The integer that \p *It was mapped to.
258 unsigned mapToIllegalUnsigned(
259 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
260 SmallVector<unsigned> &UnsignedVecForMBB,
261 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {
262 // Can't outline an illegal instruction. Set the flag.
263 CanOutlineWithPrevInstr = false;
264
265 // Only add one illegal number per range of legal numbers.
266 if (AddedIllegalLastTime)
267 return IllegalInstrNumber;
268
269 // Remember that we added an illegal number last time.
270 AddedIllegalLastTime = true;
271 unsigned MINumber = IllegalInstrNumber;
272
273 InstrListForMBB.push_back(Elt: It);
274 UnsignedVecForMBB.push_back(Elt: IllegalInstrNumber);
275 IllegalInstrNumber--;
276 // Statistics.
277 ++NumIllegalInUnsignedVec;
278
279 assert(LegalInstrNumber < IllegalInstrNumber &&
280 "Instruction mapping overflow!");
281
282 return MINumber;
283 }
284
285 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
286 /// and appends it to \p UnsignedVec and \p InstrList.
287 ///
288 /// Two instructions are assigned the same integer if they are identical.
289 /// If an instruction is deemed unsafe to outline, then it will be assigned an
290 /// unique integer. The resulting mapping is placed into a suffix tree and
291 /// queried for candidates.
292 ///
293 /// \param MBB The \p MachineBasicBlock to be translated into integers.
294 /// \param TII \p TargetInstrInfo for the function.
295 void convertToUnsignedVec(MachineBasicBlock &MBB,
296 const TargetInstrInfo &TII) {
297 LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName()
298 << "' to unsigned vector ***\n");
299 unsigned Flags = 0;
300
301 // Don't even map in this case.
302 if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
303 return;
304
305 auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags);
306 LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size()
307 << " outlinable range(s)\n");
308 if (OutlinableRanges.empty())
309 return;
310
311 // Store info for the MBB for later outlining.
312 MBBFlagsMap[&MBB] = Flags;
313
314 MachineBasicBlock::iterator It = MBB.begin();
315
316 // The number of instructions in this block that will be considered for
317 // outlining.
318 unsigned NumLegalInBlock = 0;
319
320 // True if we have at least two legal instructions which aren't separated
321 // by an illegal instruction.
322 bool HaveLegalRange = false;
323
324 // True if we can perform outlining given the last mapped (non-invisible)
325 // instruction. This lets us know if we have a legal range.
326 bool CanOutlineWithPrevInstr = false;
327
328 // FIXME: Should this all just be handled in the target, rather than using
329 // repeated calls to getOutliningType?
330 SmallVector<unsigned> UnsignedVecForMBB;
331 SmallVector<MachineBasicBlock::iterator> InstrListForMBB;
332
333 LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n");
334 for (auto &OutlinableRange : OutlinableRanges) {
335 auto OutlinableRangeBegin = OutlinableRange.first;
336 auto OutlinableRangeEnd = OutlinableRange.second;
337#ifndef NDEBUG
338 LLVM_DEBUG(
339 dbgs() << "Mapping "
340 << std::distance(OutlinableRangeBegin, OutlinableRangeEnd)
341 << " instruction range\n");
342 // Everything outside of an outlinable range is illegal.
343 unsigned NumSkippedInRange = 0;
344#endif
345 for (; It != OutlinableRangeBegin; ++It) {
346 if (It->isDebugInstr())
347 continue;
348#ifndef NDEBUG
349 ++NumSkippedInRange;
350#endif
351 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
352 InstrListForMBB);
353 }
354#ifndef NDEBUG
355 LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange
356 << " instructions outside outlinable range\n");
357#endif
358 assert(It != MBB.end() && "Should still have instructions?");
359 // `It` is now positioned at the beginning of a range of instructions
360 // which may be outlinable. Check if each instruction is known to be safe.
361 for (; It != OutlinableRangeEnd; ++It) {
362 if (It->isDebugInstr())
363 continue;
364 // Keep track of where this instruction is in the module.
365 switch (TII.getOutliningType(MMI, MIT&: It, Flags)) {
366 case InstrType::Illegal:
367 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
368 InstrListForMBB);
369 break;
370
371 case InstrType::Legal:
372 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
373 NumLegalInBlock, UnsignedVecForMBB,
374 InstrListForMBB);
375 break;
376
377 case InstrType::LegalTerminator:
378 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
379 NumLegalInBlock, UnsignedVecForMBB,
380 InstrListForMBB);
381 // The instruction also acts as a terminator, so we have to record
382 // that in the string.
383 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
384 InstrListForMBB);
385 break;
386
387 case InstrType::Invisible:
388 // Normally this is set by mapTo(Blah)Unsigned, but we just want to
389 // skip this instruction. So, unset the flag here.
390 ++NumInvisible;
391 AddedIllegalLastTime = false;
392 break;
393 }
394 }
395 }
396
397 LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n");
398
399 // Are there enough legal instructions in the block for outlining to be
400 // possible?
401 if (HaveLegalRange) {
402 // After we're done every insertion, uniquely terminate this part of the
403 // "string". This makes sure we won't match across basic block or function
404 // boundaries since the "end" is encoded uniquely and thus appears in no
405 // repeated substring.
406 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
407 InstrListForMBB);
408 ++NumSentinels;
409 append_range(C&: InstrList, R&: InstrListForMBB);
410 append_range(C&: UnsignedVec, R&: UnsignedVecForMBB);
411 }
412 }
413
414 InstructionMapper(const MachineModuleInfo &MMI_) : MMI(MMI_) {}
415};
416
417/// An interprocedural pass which finds repeated sequences of
418/// instructions and replaces them with calls to functions.
419///
420/// Each instruction is mapped to an unsigned integer and placed in a string.
421/// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
422/// is then repeatedly queried for repeated sequences of instructions. Each
423/// non-overlapping repeated sequence is then placed in its own
424/// \p MachineFunction and each instance is then replaced with a call to that
425/// function.
426struct MachineOutliner : public ModulePass {
427
428 static char ID;
429
430 MachineModuleInfo *MMI = nullptr;
431 const TargetMachine *TM = nullptr;
432
433 /// Set to true if the outliner should consider functions with
434 /// linkonceodr linkage.
435 bool OutlineFromLinkOnceODRs = false;
436
437 /// The current repeat number of machine outlining.
438 unsigned OutlineRepeatedNum = 0;
439
440 /// The mode for whether to run the outliner
441 /// Set to always-outline by default for compatibility with llc's -run-pass
442 /// option.
443 RunOutliner RunOutlinerMode = RunOutliner::AlwaysOutline;
444
445 /// This is a compact representation of hash sequences of outlined functions.
446 /// It is used when OutlinerMode = CGDataMode::Write.
447 /// The resulting hash tree will be emitted into __llvm_outlined section
448 /// which will be dead-stripped not going to the final binary.
449 /// A post-process using llvm-cgdata, lld, or ThinLTO can merge them into
450 /// a global oulined hash tree for the subsequent codegen.
451 std::unique_ptr<OutlinedHashTree> LocalHashTree;
452
453 /// The mode of the outliner.
454 /// When is's CGDataMode::None, candidates are populated with the suffix tree
455 /// within a module and outlined.
456 /// When it's CGDataMode::Write, in addition to CGDataMode::None, the hash
457 /// sequences of outlined functions are published into LocalHashTree.
458 /// When it's CGDataMode::Read, candidates are populated with the global
459 /// outlined hash tree that has been built by the previous codegen.
460 CGDataMode OutlinerMode = CGDataMode::None;
461
462 StringRef getPassName() const override { return "Machine Outliner"; }
463
464 void getAnalysisUsage(AnalysisUsage &AU) const override {
465 AU.addRequired<MachineModuleInfoWrapperPass>();
466 AU.addRequired<TargetPassConfig>();
467 AU.addPreserved<MachineModuleInfoWrapperPass>();
468 AU.addUsedIfAvailable<ImmutableModuleSummaryIndexWrapperPass>();
469 if (RunOutlinerMode == RunOutliner::OptimisticPGO ||
470 RunOutlinerMode == RunOutliner::ConservativePGO) {
471 AU.addRequired<BlockFrequencyInfoWrapperPass>();
472 AU.addRequired<ProfileSummaryInfoWrapperPass>();
473 }
474 AU.setPreservesAll();
475 ModulePass::getAnalysisUsage(AU);
476 }
477
478 MachineOutliner() : ModulePass(ID) {}
479
480 /// Remark output explaining that not outlining a set of candidates would be
481 /// better than outlining that set.
482 void emitNotOutliningCheaperRemark(
483 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
484 OutlinedFunction &OF);
485
486 /// Run the outlining cost model for a group of candidates and append the
487 /// resulting outlined function if it is profitable.
488 void createOutlinedFunctionIfBeneficial(
489 std::vector<Candidate> &Candidates, unsigned StringLen,
490 unsigned MinRepeats, const TargetInstrInfo &TII,
491 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList);
492
493 /// Remark output explaining that a function was outlined.
494 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
495
496 /// Find all repeated substrings that satisfy the outlining cost model by
497 /// constructing a suffix tree.
498 ///
499 /// If a substring appears at least twice, then it must be represented by
500 /// an internal node which appears in at least two suffixes. Each suffix
501 /// is represented by a leaf node. To do this, we visit each internal node
502 /// in the tree, using the leaf children of each internal node. If an
503 /// internal node represents a beneficial substring, then we use each of
504 /// its leaf children to find the locations of its substring.
505 ///
506 /// \param Mapper Contains outlining mapping information.
507 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
508 /// each type of candidate.
509 void
510 findCandidates(InstructionMapper &Mapper,
511 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList);
512
513 /// Find all repeated substrings that match in the global outlined hash
514 /// tree built from the previous codegen.
515 ///
516 /// \param Mapper Contains outlining mapping information.
517 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
518 /// each type of candidate.
519 void findGlobalCandidates(
520 InstructionMapper &Mapper,
521 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList);
522
523 /// Replace the sequences of instructions represented by \p OutlinedFunctions
524 /// with calls to functions.
525 ///
526 /// \param M The module we are outlining from.
527 /// \param FunctionList A list of functions to be inserted into the module.
528 /// \param Mapper Contains the instruction mappings for the module.
529 /// \param[out] OutlinedFunctionNum The outlined function number.
530 bool outline(Module &M,
531 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList,
532 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
533
534 /// Creates a function for \p OF and inserts it into the module.
535 MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
536 InstructionMapper &Mapper,
537 unsigned Name);
538
539 /// Compute and publish the stable hash sequence of instructions in the
540 /// outlined function, \p MF. The parameter \p CandSize represents the number
541 /// of candidates that have identical instruction sequences to \p MF.
542 void computeAndPublishHashSequence(MachineFunction &MF, unsigned CandSize);
543
544 /// Initialize the outliner mode.
545 void initializeOutlinerMode(const Module &M);
546
547 /// Emit the outlined hash tree into __llvm_outline section.
548 void emitOutlinedHashTree(Module &M);
549
550 /// Calls 'doOutline()' 1 + OutlinerReruns times.
551 bool runOnModule(Module &M) override;
552
553 /// Construct a suffix tree on the instructions in \p M and outline repeated
554 /// strings from that tree.
555 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
556
557 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
558 /// function for remark emission.
559 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
560 for (const Candidate &C : OF.Candidates)
561 if (MachineFunction *MF = C.getMF())
562 if (DISubprogram *SP = MF->getFunction().getSubprogram())
563 return SP;
564 return nullptr;
565 }
566
567 /// Populate and \p InstructionMapper with instruction-to-integer mappings.
568 /// These are used to construct a suffix tree.
569 void populateMapper(InstructionMapper &Mapper, Module &M);
570
571 /// Initialize information necessary to output a size remark.
572 /// FIXME: This should be handled by the pass manager, not the outliner.
573 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
574 /// pass manager.
575 void initSizeRemarkInfo(const Module &M,
576 StringMap<unsigned> &FunctionToInstrCount);
577
578 /// Emit the remark.
579 // FIXME: This should be handled by the pass manager, not the outliner.
580 void
581 emitInstrCountChangedRemark(const Module &M,
582 const StringMap<unsigned> &FunctionToInstrCount);
583};
584} // Anonymous namespace.
585
586char MachineOutliner::ID = 0;
587
588ModulePass *llvm::createMachineOutlinerPass(RunOutliner RunOutlinerMode) {
589 MachineOutliner *OL = new MachineOutliner();
590 OL->RunOutlinerMode = RunOutlinerMode;
591 return OL;
592}
593
594INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
595 false)
596
597void MachineOutliner::emitNotOutliningCheaperRemark(
598 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
599 OutlinedFunction &OF) {
600 // FIXME: Right now, we arbitrarily choose some Candidate from the
601 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
602 // We should probably sort these by function name or something to make sure
603 // the remarks are stable.
604 Candidate &C = CandidatesForRepeatedSeq.front();
605 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
606 MORE.emit(RemarkBuilder: [&]() {
607 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
608 C.front().getDebugLoc(), C.getMBB());
609 R << "Did not outline " << NV("Length", StringLen) << " instructions"
610 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
611 << " locations."
612 << " Bytes from outlining all occurrences ("
613 << NV("OutliningCost", OF.getOutliningCost()) << ")"
614 << " >= Unoutlined instruction bytes ("
615 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
616 << " (Also found at: ";
617
618 // Tell the user the other places the candidate was found.
619 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
620 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
621 CandidatesForRepeatedSeq[i].front().getDebugLoc());
622 if (i != e - 1)
623 R << ", ";
624 }
625
626 R << ")";
627 return R;
628 });
629}
630
631void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
632 MachineBasicBlock *MBB = &*OF.MF->begin();
633 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
634 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
635 MBB->findDebugLoc(MBBI: MBB->begin()), MBB);
636 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
637 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
638 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
639 << " locations. "
640 << "(Found at: ";
641
642 // Tell the user the other places the candidate was found.
643 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
644
645 R << NV((Twine("StartLoc") + Twine(i)).str(),
646 OF.Candidates[i].front().getDebugLoc());
647 if (i != e - 1)
648 R << ", ";
649 }
650
651 R << ")";
652
653 MORE.emit(OptDiag&: R);
654}
655
656static stable_hash hashInstruction(const MachineInstr &MI) {
657 // Globals with local linkage are qualified with their module's source file
658 // name so that same-named locals in different modules do not match when hash
659 // sequences are compared across modules.
660 return stableHashValue(MI, /*HashVRegs=*/false,
661 /*HashConstantPoolIndices=*/false,
662 /*HashMemOperands=*/false,
663 /*SourceQualifyLocalGlobals=*/true);
664}
665
666struct MatchedEntry {
667 unsigned StartIdx;
668 unsigned EndIdx;
669 unsigned Count;
670 MatchedEntry(unsigned StartIdx, unsigned EndIdx, unsigned Count)
671 : StartIdx(StartIdx), EndIdx(EndIdx), Count(Count) {}
672 MatchedEntry() = delete;
673};
674
675// Find all matches in the global outlined hash tree.
676// It's quadratic complexity in theory, but it's nearly linear in practice
677// since the length of outlined sequences are small within a block.
678static SmallVector<MatchedEntry> getMatchedEntries(InstructionMapper &Mapper) {
679 auto &InstrList = Mapper.InstrList;
680 auto &UnsignedVec = Mapper.UnsignedVec;
681
682 SmallVector<MatchedEntry> MatchedEntries;
683 auto Size = UnsignedVec.size();
684
685 // Get the global outlined hash tree built from the previous run.
686 const cl::LibraryOptionsContext &LibraryOptions =
687 Mapper.MMI.getModule()->getContext().getLibraryOptions();
688 assert(cgdata::hasOutlinedHashTree(LibraryOptions));
689 const auto *RootNode = cgdata::getOutlinedHashTree(LibraryOptions)->getRoot();
690
691 auto getValidInstr = [&](unsigned Index) -> const MachineInstr * {
692 if (UnsignedVec[Index] >= Mapper.LegalInstrNumber)
693 return nullptr;
694 return &(*InstrList[Index]);
695 };
696
697 auto getStableHashAndFollow =
698 [](const MachineInstr &MI, const HashNode *CurrNode) -> const HashNode * {
699 stable_hash StableHash = hashInstruction(MI);
700 if (!StableHash)
701 return nullptr;
702 auto It = CurrNode->Successors.find(Val: StableHash);
703 return (It == CurrNode->Successors.end()) ? nullptr : It->second.get();
704 };
705
706 for (unsigned I = 0; I < Size; ++I) {
707 const MachineInstr *MI = getValidInstr(I);
708 if (!MI || MI->isDebugInstr())
709 continue;
710 const HashNode *CurrNode = getStableHashAndFollow(*MI, RootNode);
711 if (!CurrNode)
712 continue;
713
714 for (unsigned J = I + 1; J < Size; ++J) {
715 const MachineInstr *MJ = getValidInstr(J);
716 if (!MJ)
717 break;
718 // Skip debug instructions as we did for the outlined function.
719 if (MJ->isDebugInstr())
720 continue;
721 CurrNode = getStableHashAndFollow(*MJ, CurrNode);
722 if (!CurrNode)
723 break;
724 // Even with a match ending with a terminal, we continue finding
725 // matches to populate all candidates.
726 if (auto Count = CurrNode->Terminals)
727 MatchedEntries.emplace_back(Args&: I, Args&: J, Args&: *Count);
728 }
729 }
730
731 return MatchedEntries;
732}
733
734void MachineOutliner::findGlobalCandidates(
735 InstructionMapper &Mapper,
736 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) {
737 FunctionList.clear();
738 auto &InstrList = Mapper.InstrList;
739 auto &MBBFlagsMap = Mapper.MBBFlagsMap;
740
741 std::vector<Candidate> CandidatesForRepeatedSeq;
742 for (auto &ME : getMatchedEntries(Mapper)) {
743 CandidatesForRepeatedSeq.clear();
744 MachineBasicBlock::iterator StartIt = InstrList[ME.StartIdx];
745 MachineBasicBlock::iterator EndIt = InstrList[ME.EndIdx];
746 auto Length = ME.EndIdx - ME.StartIdx + 1;
747 MachineBasicBlock *MBB = StartIt->getParent();
748 CandidatesForRepeatedSeq.emplace_back(args&: ME.StartIdx, args&: Length, args&: StartIt, args&: EndIt,
749 args&: MBB, args&: MBBFlagsMap[MBB]);
750 const TargetInstrInfo *TII =
751 MBB->getParent()->getSubtarget().getInstrInfo();
752 unsigned MinRepeats = 1;
753 std::optional<std::unique_ptr<OutlinedFunction>> OF =
754 TII->getOutliningCandidateInfo(MMI: *MMI, RepeatedSequenceLocs&: CandidatesForRepeatedSeq,
755 MinRepeats);
756 if (!OF.has_value() || OF.value()->Candidates.empty())
757 continue;
758 // We create a global candidate for each match.
759 assert(OF.value()->Candidates.size() == MinRepeats);
760 FunctionList.emplace_back(args: std::make_unique<GlobalOutlinedFunction>(
761 args: std::move(OF.value()), args&: ME.Count));
762 }
763}
764
765static StringRef getCandidateInputSection(const Candidate &C) {
766 const Function &F = C.getMF()->getFunction();
767 return F.hasSection() ? F.getSection() : StringRef();
768}
769
770static SmallVector<std::vector<Candidate>>
771partitionCandidatesByInputSection(std::vector<Candidate> &Candidates) {
772 // Each candidate belongs to exactly one MachineFunction, so the partitions
773 // are disjoint and can be outlined independently.
774 SmallVector<std::vector<Candidate>> Partitions;
775 SmallVector<StringRef> Sections;
776 for (Candidate &C : Candidates) {
777 StringRef Section = getCandidateInputSection(C);
778 auto It = llvm::find(Range&: Sections, Val: Section);
779 if (It == Sections.end()) {
780 Sections.push_back(Elt: Section);
781 Partitions.emplace_back();
782 It = Sections.end() - 1;
783 }
784 Partitions[std::distance(first: Sections.begin(), last: It)].push_back(x: std::move(C));
785 }
786 return Partitions;
787}
788
789void MachineOutliner::createOutlinedFunctionIfBeneficial(
790 std::vector<Candidate> &Candidates, unsigned StringLen, unsigned MinRepeats,
791 const TargetInstrInfo &TII,
792 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) {
793 if (Candidates.size() < MinRepeats)
794 return;
795
796 std::optional<std::unique_ptr<OutlinedFunction>> OF =
797 TII.getOutliningCandidateInfo(MMI: *MMI, RepeatedSequenceLocs&: Candidates, MinRepeats);
798
799 // If we deleted too many candidates, then there's nothing worth outlining.
800 // FIXME: This should take target-specified instruction sizes into account.
801 if (!OF.has_value() || OF.value()->Candidates.size() < MinRepeats)
802 return;
803
804 // Is it better to outline this candidate than not?
805 if (OF.value()->getBenefit() < OutlinerBenefitThreshold) {
806 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq&: Candidates, OF&: *OF.value());
807 return;
808 }
809
810 FunctionList.emplace_back(args: std::move(OF.value()));
811}
812
813void MachineOutliner::findCandidates(
814 InstructionMapper &Mapper,
815 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) {
816 FunctionList.clear();
817 SuffixTree ST(Mapper.UnsignedVec, OutlinerLeafDescendants);
818
819 // First, find all of the repeated substrings in the tree of minimum length
820 // 2.
821 std::vector<Candidate> CandidatesForRepeatedSeq;
822 LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n");
823 LLVM_DEBUG(
824 dbgs() << "Searching for overlaps in all repeated sequences...\n");
825 for (SuffixTree::RepeatedSubstring &RS : ST) {
826 CandidatesForRepeatedSeq.clear();
827 unsigned StringLen = RS.Length;
828 LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n");
829 // Debug code to keep track of how many candidates we removed.
830#ifndef NDEBUG
831 unsigned NumDiscarded = 0;
832 unsigned NumKept = 0;
833#endif
834 // Sort the start indices so that we can efficiently check if candidates
835 // overlap with the ones we've already found for this sequence.
836 llvm::sort(C&: RS.StartIndices);
837 for (const unsigned &StartIdx : RS.StartIndices) {
838 // Trick: Discard some candidates that would be incompatible with the
839 // ones we've already found for this sequence. This will save us some
840 // work in candidate selection.
841 //
842 // If two candidates overlap, then we can't outline them both. This
843 // happens when we have candidates that look like, say
844 //
845 // AA (where each "A" is an instruction).
846 //
847 // We might have some portion of the module that looks like this:
848 // AAAAAA (6 A's)
849 //
850 // In this case, there are 5 different copies of "AA" in this range, but
851 // at most 3 can be outlined. If only outlining 3 of these is going to
852 // be unbeneficial, then we ought to not bother.
853 //
854 // Note that two things DON'T overlap when they look like this:
855 // start1...end1 .... start2...end2
856 // That is, one must either
857 // * End before the other starts
858 // * Start after the other ends
859 unsigned EndIdx = StartIdx + StringLen - 1;
860 if (!CandidatesForRepeatedSeq.empty() &&
861 StartIdx <= CandidatesForRepeatedSeq.back().getEndIdx()) {
862#ifndef NDEBUG
863 ++NumDiscarded;
864 LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx << ", "
865 << EndIdx << "]; overlaps with candidate @ ["
866 << CandidatesForRepeatedSeq.back().getStartIdx()
867 << ", " << CandidatesForRepeatedSeq.back().getEndIdx()
868 << "]\n");
869#endif
870 continue;
871 }
872 // It doesn't overlap with anything, so we can outline it.
873 // Each sequence is over [StartIt, EndIt].
874 // Save the candidate and its location.
875#ifndef NDEBUG
876 ++NumKept;
877#endif
878 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
879 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
880 MachineBasicBlock *MBB = StartIt->getParent();
881 CandidatesForRepeatedSeq.emplace_back(args: StartIdx, args&: StringLen, args&: StartIt, args&: EndIt,
882 args&: MBB, args&: Mapper.MBBFlagsMap[MBB]);
883 }
884#ifndef NDEBUG
885 LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded
886 << "\n");
887 LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n");
888#endif
889 unsigned MinRepeats = 2;
890
891 // We've found something we might want to outline.
892 // Create an OutlinedFunction to store it and check if it'd be beneficial
893 // to outline.
894 if (CandidatesForRepeatedSeq.size() < MinRepeats)
895 continue;
896
897 // Arbitrarily choose a TII from the first candidate.
898 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
899 const TargetInstrInfo *TII =
900 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
901
902 // Targets that do not opt in to section aware outlining never map
903 // functions with a section marking, so every candidate would land in a
904 // single partition. Skip partitioning entirely to avoid the allocation.
905 if (!TII->supportsSectionAwareOutlining()) {
906 createOutlinedFunctionIfBeneficial(Candidates&: CandidatesForRepeatedSeq, StringLen,
907 MinRepeats, TII: *TII, FunctionList);
908 continue;
909 }
910
911 LLVM_DEBUG(
912 dbgs()
913 << "*** Section Aware Outlining is enabled for the target *** \n");
914
915 SmallVector<std::vector<Candidate>> Partitions =
916 partitionCandidatesByInputSection(Candidates&: CandidatesForRepeatedSeq);
917 LLVM_DEBUG(dbgs() << " Input section partitions: " << Partitions.size()
918 << "\n");
919
920 for (std::vector<Candidate> &Partition : Partitions) {
921 LLVM_DEBUG({
922 StringRef Section = getCandidateInputSection(Partition.front());
923 dbgs() << " .. section '"
924 << (Section.empty() ? StringRef("<none>") : Section)
925 << "': " << Partition.size() << " candidates\n";
926 });
927 createOutlinedFunctionIfBeneficial(Candidates&: Partition, StringLen, MinRepeats, TII: *TII,
928 FunctionList);
929 }
930 }
931}
932
933void MachineOutliner::computeAndPublishHashSequence(MachineFunction &MF,
934 unsigned CandSize) {
935 // Compute the hash sequence for the outlined function.
936 SmallVector<stable_hash> OutlinedHashSequence;
937 for (auto &MBB : MF) {
938 for (auto &NewMI : MBB) {
939 stable_hash Hash = hashInstruction(MI: NewMI);
940 if (!Hash) {
941 OutlinedHashSequence.clear();
942 break;
943 }
944 OutlinedHashSequence.push_back(Elt: Hash);
945 }
946 }
947
948 // Append a unique name based on the non-empty hash sequence.
949 if (AppendContentHashToOutlinedName && !OutlinedHashSequence.empty()) {
950 auto CombinedHash = stable_hash_combine(Buffer: OutlinedHashSequence);
951 auto NewName =
952 MF.getName().str() + ".content." + std::to_string(val: CombinedHash);
953 MF.getFunction().setName(NewName);
954 }
955
956 // Publish the non-empty hash sequence to the local hash tree.
957 if (OutlinerMode == CGDataMode::Write) {
958 StableHashAttempts++;
959 if (!OutlinedHashSequence.empty())
960 LocalHashTree->insert(SequencePair: {OutlinedHashSequence, CandSize});
961 else
962 StableHashDropped++;
963 }
964}
965
966MachineFunction *MachineOutliner::createOutlinedFunction(
967 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
968
969 // Create the function name. This should be unique.
970 // FIXME: We should have a better naming scheme. This should be stable,
971 // regardless of changes to the outliner's cost model/traversal order.
972 std::string FunctionName = "OUTLINED_FUNCTION_";
973 if (OutlineRepeatedNum > 0)
974 FunctionName += std::to_string(val: OutlineRepeatedNum + 1) + "_";
975 FunctionName += std::to_string(val: Name);
976 LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n");
977
978 // Create the function using an IR-level function.
979 LLVMContext &C = M.getContext();
980 Function *F = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false),
981 Linkage: Function::ExternalLinkage, N: FunctionName, M);
982
983 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
984 // which gives us better results when we outline from linkonceodr functions.
985 F->setLinkage(GlobalValue::InternalLinkage);
986 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
987
988 // Set optsize/minsize, so we don't insert padding between outlined
989 // functions.
990 F->addFnAttr(Kind: Attribute::OptimizeForSize);
991 F->addFnAttr(Kind: Attribute::MinSize);
992
993 Candidate &FirstCand = OF.Candidates.front();
994 const TargetInstrInfo &TII =
995 *FirstCand.getMF()->getSubtarget().getInstrInfo();
996
997 TII.mergeOutliningCandidateAttributes(F&: *F, Candidates&: OF.Candidates);
998
999 if (TII.supportsSectionAwareOutlining()) {
1000 const Function &ParentFn = FirstCand.getMF()->getFunction();
1001 if (ParentFn.hasSection()) {
1002 F->setSection(ParentFn.getSection());
1003 LLVM_DEBUG(dbgs() << " INHERITED SECTION: " << ParentFn.getSection()
1004 << "\n");
1005 }
1006 }
1007
1008 // Set uwtable, so we generate eh_frame.
1009 UWTableKind UW = std::accumulate(
1010 first: OF.Candidates.cbegin(), last: OF.Candidates.cend(), init: UWTableKind::None,
1011 binary_op: [](UWTableKind K, const outliner::Candidate &C) {
1012 return std::max(a: K, b: C.getMF()->getFunction().getUWTableKind());
1013 });
1014 F->setUWTableKind(UW);
1015
1016 BasicBlock *EntryBB = BasicBlock::Create(Context&: C, Name: "entry", Parent: F);
1017 IRBuilder<> Builder(EntryBB);
1018 Builder.CreateRetVoid();
1019
1020 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1021 MachineFunction &MF = MMI.getOrCreateMachineFunction(F&: *F);
1022 MF.setIsOutlined(true);
1023 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1024
1025 // Insert the new function into the module.
1026 MF.insert(MBBI: MF.begin(), MBB: &MBB);
1027
1028 MachineFunction *OriginalMF = FirstCand.front().getMF();
1029 const std::vector<MCCFIInstruction> &Instrs =
1030 OriginalMF->getFrameInstructions();
1031 for (auto &MI : FirstCand) {
1032 if (MI.isDebugInstr())
1033 continue;
1034
1035 // Don't keep debug information for outlined instructions.
1036 auto DL = DebugLoc();
1037 if (MI.isCFIInstruction()) {
1038 unsigned CFIIndex = MI.getOperand(i: 0).getCFIIndex();
1039 MCCFIInstruction CFI = Instrs[CFIIndex];
1040 BuildMI(BB&: MBB, I: MBB.end(), MIMD: DL, MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
1041 .addCFIIndex(CFIIndex: MF.addFrameInst(Inst: CFI));
1042 } else {
1043 MachineInstr &NewMI = TII.duplicate(MBB, InsertBefore: MBB.end(), Orig: MI);
1044 NewMI.dropMemRefs(MF);
1045 NewMI.setDebugLoc(DL);
1046 NewMI.clearKillInfo();
1047 // Also clear debug locations and kill info on any bundled instructions.
1048 if (NewMI.isBundledWithSucc()) {
1049 auto BundleEnd = getBundleEnd(I: NewMI.getIterator());
1050 for (auto I = std::next(x: NewMI.getIterator()); I != BundleEnd; ++I) {
1051 I->setDebugLoc(DL);
1052 I->clearKillInfo();
1053 }
1054 }
1055 }
1056 }
1057
1058 if (OutlinerMode != CGDataMode::None)
1059 computeAndPublishHashSequence(MF, CandSize: OF.Candidates.size());
1060
1061 // Set normal properties for a late MachineFunction.
1062 MF.getProperties().resetIsSSA();
1063 MF.getProperties().setNoPHIs();
1064 MF.getProperties().setNoVRegs();
1065 MF.getProperties().setTracksLiveness();
1066 MF.getRegInfo().freezeReservedRegs();
1067
1068 // Compute live-in set for outlined fn
1069 const MachineRegisterInfo &MRI = MF.getRegInfo();
1070 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1071 LivePhysRegs LiveIns(TRI);
1072 for (auto &Cand : OF.Candidates) {
1073 // Figure out live-ins at the first instruction.
1074 MachineBasicBlock &OutlineBB = *Cand.front().getParent();
1075 LivePhysRegs CandLiveIns(TRI);
1076 CandLiveIns.addLiveOuts(MBB: OutlineBB);
1077 for (const MachineInstr &MI :
1078 reverse(C: make_range(x: Cand.begin(), y: OutlineBB.end())))
1079 CandLiveIns.stepBackward(MI);
1080
1081 // The live-in set for the outlined function is the union of the live-ins
1082 // from all the outlining points.
1083 for (MCPhysReg Reg : CandLiveIns)
1084 LiveIns.addReg(Reg);
1085 }
1086 addLiveIns(MBB, LiveRegs: LiveIns);
1087
1088 TII.buildOutlinedFrame(MBB, MF, OF);
1089
1090 // If there's a DISubprogram associated with this outlined function, then
1091 // emit debug info for the outlined function.
1092 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
1093 // We have a DISubprogram. Get its DICompileUnit.
1094 DICompileUnit *CU = SP->getUnit();
1095 DIBuilder DB(M, true, CU);
1096 DIFile *Unit = SP->getFile();
1097 Mangler Mg;
1098 // Get the mangled name of the function for the linkage name.
1099 std::string Dummy;
1100 raw_string_ostream MangledNameStream(Dummy);
1101 Mg.getNameWithPrefix(OS&: MangledNameStream, GV: F, CannotUsePrivateLabel: false);
1102
1103 DISubprogram *OutlinedSP = DB.createFunction(
1104 Scope: Unit /* Context */, Name: F->getName(), LinkageName: StringRef(Dummy), File: Unit /* File */,
1105 LineNo: 0 /* Line 0 is reserved for compiler-generated code. */,
1106 Ty: DB.createSubroutineType(ParameterTypes: DB.getOrCreateTypeArray(Elements: {})), /* void type */
1107 ScopeLine: 0, /* Line 0 is reserved for compiler-generated code. */
1108 Flags: DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
1109 /* Outlined code is optimized code by definition. */
1110 SPFlags: DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
1111
1112 // Attach subprogram to the function.
1113 F->setSubprogram(OutlinedSP);
1114 // We're done with the DIBuilder.
1115 DB.finalize();
1116 }
1117
1118 return &MF;
1119}
1120
1121bool MachineOutliner::outline(
1122 Module &M, std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList,
1123 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) {
1124 LLVM_DEBUG(dbgs() << "*** Outlining ***\n");
1125 LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size()
1126 << "\n");
1127 bool OutlinedSomething = false;
1128
1129 // Sort by priority where priority := getNotOutlinedCost / getOutliningCost.
1130 // The function with highest priority should be outlined first.
1131 stable_sort(Range&: FunctionList, C: [](const std::unique_ptr<OutlinedFunction> &LHS,
1132 const std::unique_ptr<OutlinedFunction> &RHS) {
1133 return LHS->getNotOutlinedCost() * RHS->getOutliningCost() >
1134 RHS->getNotOutlinedCost() * LHS->getOutliningCost();
1135 });
1136
1137 // Walk over each function, outlining them as we go along. Functions are
1138 // outlined greedily, based off the sort above.
1139 auto *UnsignedVecBegin = Mapper.UnsignedVec.begin();
1140 LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n");
1141 for (auto &OF : FunctionList) {
1142#ifndef NDEBUG
1143 auto NumCandidatesBefore = OF->Candidates.size();
1144#endif
1145 // If we outlined something that overlapped with a candidate in a previous
1146 // step, then we can't outline from it.
1147 erase_if(C&: OF->Candidates, P: [&UnsignedVecBegin](Candidate &C) {
1148 return std::any_of(first: UnsignedVecBegin + C.getStartIdx(),
1149 last: UnsignedVecBegin + C.getEndIdx() + 1, pred: [](unsigned I) {
1150 return I == static_cast<unsigned>(-1);
1151 });
1152 });
1153
1154#ifndef NDEBUG
1155 auto NumCandidatesAfter = OF->Candidates.size();
1156 LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter
1157 << "/" << NumCandidatesBefore << " candidates\n");
1158#endif
1159
1160 // If we made it unbeneficial to outline this function, skip it.
1161 if (OF->getBenefit() < OutlinerBenefitThreshold) {
1162 LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF->getBenefit()
1163 << " B) < threshold (" << OutlinerBenefitThreshold
1164 << " B)\n");
1165 continue;
1166 }
1167
1168 LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF->getBenefit()
1169 << " B) > threshold (" << OutlinerBenefitThreshold
1170 << " B)\n");
1171
1172 // Remove all Linker Optimization Hints from the candidates.
1173 // TODO: The intersection of the LOHs from all candidates should be legal in
1174 // the outlined function.
1175 SmallPtrSet<MachineInstr *, 2> MIs;
1176 for (Candidate &C : OF->Candidates) {
1177 for (MachineInstr &MI : C)
1178 MIs.insert(Ptr: &MI);
1179 NumRemovedLOHs += TM->clearLinkerOptimizationHints(MIs);
1180 MIs.clear();
1181 }
1182
1183 // It's beneficial. Create the function and outline its sequence's
1184 // occurrences.
1185 OF->MF = createOutlinedFunction(M, OF&: *OF, Mapper, Name: OutlinedFunctionNum);
1186 emitOutlinedFunctionRemark(OF&: *OF);
1187 FunctionsCreated++;
1188 OutlinedFunctionNum++; // Created a function, move to the next name.
1189 MachineFunction *MF = OF->MF;
1190 const TargetSubtargetInfo &STI = MF->getSubtarget();
1191 const TargetInstrInfo &TII = *STI.getInstrInfo();
1192
1193 // Replace occurrences of the sequence with calls to the new function.
1194 LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n");
1195 for (Candidate &C : OF->Candidates) {
1196 MachineBasicBlock &MBB = *C.getMBB();
1197 MachineBasicBlock::iterator StartIt = C.begin();
1198 MachineBasicBlock::iterator EndIt = std::prev(x: C.end());
1199
1200 // Find the first non-debug instruction with a non-zero source line, and
1201 // the location of the last call in the candidate, if it has one.
1202 DebugLoc FirstLoc, LastCallLoc;
1203 for (MachineInstr &MI : C) {
1204 if (MI.isDebugInstr())
1205 continue;
1206 const DebugLoc &DL = MI.getDebugLoc();
1207 bool HasLine = DL && DL.getLine();
1208 if (!FirstLoc && HasLine)
1209 FirstLoc = DL;
1210 if (MI.isCall())
1211 LastCallLoc = HasLine ? DL : DebugLoc();
1212 }
1213
1214 // Remember the instruction the call sequence will be inserted after, so
1215 // we can find every instruction the target inserts below.
1216 MachineBasicBlock::iterator PrevIt =
1217 StartIt == MBB.begin() ? MBB.end() : std::prev(x: StartIt);
1218
1219 // Insert the call.
1220 auto CallInst = TII.insertOutlinedCall(M, MBB, It&: StartIt, MF&: *MF, C);
1221
1222 // Unwinding through a call in the candidate symbolizes the caller frame
1223 // at the outlined call, so it should carry that call's location. Use the
1224 // last call: a candidate ending in a call may be outlined as a thunk
1225 // whose tail call returns directly past the outlined call. With multiple
1226 // calls, only the last is attributed exactly. Nothing returns to a tail
1227 // branch, so it keeps the first location.
1228 DebugLoc CallLoc =
1229 !CallInst->isTerminator() && LastCallLoc ? LastCallLoc : FirstLoc;
1230
1231 // insertOutlinedCall may emit link register save/restore instructions
1232 // around the call, and leaves StartIt on the last instruction it
1233 // inserted. Give the whole sequence the same location. Otherwise, a
1234 // locationless save or restore can introduce a line 0 row, including at
1235 // the return address immediately after the call.
1236 MachineBasicBlock::iterator SeqBegin =
1237 PrevIt == MBB.end() ? MBB.begin() : std::next(x: PrevIt);
1238 for (MachineInstr &MI : make_range(x: SeqBegin, y: std::next(x: StartIt)))
1239 MI.setDebugLoc(CallLoc);
1240
1241#ifndef NDEBUG
1242 auto MBBBeingOutlinedFromName =
1243 MBB.getName().empty() ? "<unknown>" : MBB.getName().str();
1244 auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty()
1245 ? "<unknown>"
1246 : MBB.getParent()->getName().str();
1247 LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in "
1248 << MFBeingOutlinedFromName << ":"
1249 << MBBBeingOutlinedFromName << "\n");
1250 LLVM_DEBUG(dbgs() << " .. " << *CallInst);
1251#endif
1252
1253 // If the caller tracks liveness, then we need to make sure that
1254 // anything we outline doesn't break liveness assumptions. The outlined
1255 // functions themselves currently don't track liveness, but we should
1256 // make sure that the ranges we yank things out of aren't wrong.
1257 if (MBB.getParent()->getProperties().hasTracksLiveness()) {
1258 // The following code is to add implicit def operands to the call
1259 // instruction. It also updates call site information for moved
1260 // code.
1261 SmallSet<Register, 2> UseRegs, DefRegs;
1262 // Copy over the defs in the outlined range.
1263 // First inst in outlined range <-- Anything that's defined in this
1264 // ... .. range has to be added as an
1265 // implicit Last inst in outlined range <-- def to the call
1266 // instruction. Also remove call site information for outlined block
1267 // of code. The exposed uses need to be copied in the outlined range.
1268 for (MachineBasicBlock::reverse_iterator
1269 Iter = EndIt.getReverse(),
1270 Last = std::next(x: CallInst.getReverse());
1271 Iter != Last; Iter++) {
1272 MachineInstr *MI = &*Iter;
1273 if (MI->isDebugInstr())
1274 continue;
1275 SmallSet<Register, 2> InstrUseRegs;
1276 for (MachineOperand &MOP : MI->operands()) {
1277 // Skip over anything that isn't a register.
1278 if (!MOP.isReg())
1279 continue;
1280
1281 if (MOP.isDef()) {
1282 // Introduce DefRegs set to skip the redundant register.
1283 DefRegs.insert(V: MOP.getReg());
1284 if (UseRegs.count(V: MOP.getReg()) &&
1285 !InstrUseRegs.count(V: MOP.getReg()))
1286 // Since the regiester is modeled as defined,
1287 // it is not necessary to be put in use register set.
1288 UseRegs.erase(V: MOP.getReg());
1289 } else if (!MOP.isUndef()) {
1290 // Any register which is not undefined should
1291 // be put in the use register set.
1292 UseRegs.insert(V: MOP.getReg());
1293 InstrUseRegs.insert(V: MOP.getReg());
1294 }
1295 }
1296 if (MI->isCandidateForAdditionalCallInfo())
1297 MI->getMF()->eraseAdditionalCallInfo(MI);
1298 }
1299
1300 for (const Register &I : DefRegs)
1301 // If it's a def, add it to the call instruction.
1302 CallInst->addOperand(
1303 Op: MachineOperand::CreateReg(Reg: I, isDef: true, /* isDef = true */
1304 isImp: true /* isImp = true */));
1305
1306 for (const Register &I : UseRegs)
1307 // If it's a exposed use, add it to the call instruction.
1308 CallInst->addOperand(
1309 Op: MachineOperand::CreateReg(Reg: I, isDef: false, /* isDef = false */
1310 isImp: true /* isImp = true */));
1311 }
1312
1313 // Erase from the point after where the call was inserted up to, and
1314 // including, the final instruction in the sequence.
1315 // Erase needs one past the end, so we need std::next there too.
1316 MBB.erase(I: std::next(x: StartIt), E: std::next(x: EndIt));
1317
1318 // Keep track of what we removed by marking them all as -1.
1319 for (unsigned &I : make_range(x: UnsignedVecBegin + C.getStartIdx(),
1320 y: UnsignedVecBegin + C.getEndIdx() + 1))
1321 I = static_cast<unsigned>(-1);
1322 OutlinedSomething = true;
1323
1324 // Statistics.
1325 NumOutlined++;
1326 }
1327 }
1328
1329 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n");
1330 return OutlinedSomething;
1331}
1332
1333static bool allowPGOOutlining(RunOutliner RunOutlinerMode,
1334 const ProfileSummaryInfo *PSI,
1335 const BlockFrequencyInfo *BFI,
1336 MachineBasicBlock &MBB) {
1337 if (RunOutlinerMode != RunOutliner::OptimisticPGO &&
1338 RunOutlinerMode != RunOutliner::ConservativePGO)
1339 return true;
1340 auto *MF = MBB.getParent();
1341 if (MF->getFunction().hasFnAttribute(Kind: Attribute::Cold)) {
1342 ++NumPGOAllowedCold;
1343 return true;
1344 }
1345
1346 auto *BB = MBB.getBasicBlock();
1347 if (BB && PSI && BFI)
1348 if (auto Count = BFI->getBlockProfileCount(BB))
1349 return *Count <= PSI->getOrCompColdCountThreshold();
1350
1351 if (RunOutlinerMode == RunOutliner::OptimisticPGO) {
1352 auto *TII = MF->getSubtarget().getInstrInfo();
1353 if (TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) {
1354 // Profile data is unavailable, but we optimistically allow outlining
1355 ++NumPGOOptimisticOutlined;
1356 return true;
1357 }
1358 return false;
1359 }
1360 assert(RunOutlinerMode == RunOutliner::ConservativePGO);
1361 // Profile data is unavailable, so we conservatively block outlining
1362 ++NumPGOConservativeBlockedOutlined;
1363 return false;
1364}
1365
1366void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M) {
1367 // Build instruction mappings for each function in the module. Start by
1368 // iterating over each Function in M.
1369 LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n");
1370 bool EnableProfileGuidedOutlining =
1371 RunOutlinerMode == RunOutliner::OptimisticPGO ||
1372 RunOutlinerMode == RunOutliner::ConservativePGO;
1373 ProfileSummaryInfo *PSI = nullptr;
1374 if (EnableProfileGuidedOutlining)
1375 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
1376 for (Function &F : M) {
1377 LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n");
1378
1379 if (F.hasFnAttribute(Kind: Attribute::NoOutline)) {
1380 LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n");
1381 continue;
1382 }
1383
1384 // There's something in F. Check if it has a MachineFunction associated with
1385 // it.
1386 MachineFunction *MF = MMI->getMachineFunction(F);
1387
1388 // If it doesn't, then there's nothing to outline from. Move to the next
1389 // Function.
1390 if (!MF) {
1391 LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n");
1392 continue;
1393 }
1394
1395 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1396 BlockFrequencyInfo *BFI = nullptr;
1397 if (EnableProfileGuidedOutlining && F.hasProfileData())
1398 BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1399 if (RunOutlinerMode == RunOutliner::TargetDefault &&
1400 !TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) {
1401 LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from "
1402 "function by default\n");
1403 continue;
1404 }
1405
1406 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1407 // If it isn't, then move on to the next Function in the module.
1408 if (!TII->isFunctionSafeToOutlineFrom(MF&: *MF, OutlineFromLinkOnceODRs)) {
1409 LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName()
1410 << ": unsafe to outline from\n");
1411 continue;
1412 }
1413
1414 // We have a function suitable for outlining. Iterate over every
1415 // MachineBasicBlock in MF and try to map its instructions to a list of
1416 // unsigned integers.
1417 const unsigned MinMBBSize = 2;
1418
1419 for (MachineBasicBlock &MBB : *MF) {
1420 LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n");
1421 // If there isn't anything in MBB, then there's no point in outlining from
1422 // it.
1423 // If there are fewer than 2 non-debug instructions in the MBB, then it
1424 // can't ever contain something worth outlining. Count raw instructions,
1425 // including bundle interiors, to preserve MBB.size() behavior. Pseudo
1426 // probes also retain their historical treatment as ordinary
1427 // instructions.
1428 // FIXME: This should be based off of the maximum size in B of an outlined
1429 // call versus the size in B of the MBB.
1430 if (!hasNItemsOrMore(C: instructionsWithoutDebug(It: MBB.instr_begin(),
1431 End: MBB.instr_end(),
1432 /* SkipPseudoOp */ false),
1433 N: MinMBBSize)) {
1434 LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of "
1435 << MinMBBSize << "\n");
1436 continue;
1437 }
1438
1439 // Check if MBB could be the target of an indirect branch. If it is, then
1440 // we don't want to outline from it.
1441 if (MBB.hasAddressTaken()) {
1442 LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n");
1443 continue;
1444 }
1445
1446 if (!allowPGOOutlining(RunOutlinerMode, PSI, BFI, MBB)) {
1447 ++NumPGOBlockedOutlined;
1448 continue;
1449 }
1450
1451 // MBB is suitable for outlining. Map it to a list of unsigneds.
1452 Mapper.convertToUnsignedVec(MBB, TII: *TII);
1453 }
1454 }
1455 // Statistics.
1456 UnsignedVecSize = Mapper.UnsignedVec.size();
1457}
1458
1459void MachineOutliner::initSizeRemarkInfo(
1460 const Module &M, StringMap<unsigned> &FunctionToInstrCount) {
1461 // Collect instruction counts for every function. We'll use this to emit
1462 // per-function size remarks later.
1463 for (const Function &F : M) {
1464 MachineFunction *MF = MMI->getMachineFunction(F);
1465
1466 // We only care about MI counts here. If there's no MachineFunction at this
1467 // point, then there won't be after the outliner runs, so let's move on.
1468 if (!MF)
1469 continue;
1470 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
1471 }
1472}
1473
1474void MachineOutliner::emitInstrCountChangedRemark(
1475 const Module &M, const StringMap<unsigned> &FunctionToInstrCount) {
1476 // Iterate over each function in the module and emit remarks.
1477 // Note that we won't miss anything by doing this, because the outliner never
1478 // deletes functions.
1479 for (const Function &F : M) {
1480 MachineFunction *MF = MMI->getMachineFunction(F);
1481
1482 // The outliner never deletes functions. If we don't have a MF here, then we
1483 // didn't have one prior to outlining either.
1484 if (!MF)
1485 continue;
1486
1487 std::string Fname = std::string(F.getName());
1488 unsigned FnCountAfter = MF->getInstructionCount();
1489 unsigned FnCountBefore = 0;
1490
1491 // Check if the function was recorded before.
1492 auto It = FunctionToInstrCount.find(Key: Fname);
1493
1494 // Did we have a previously-recorded size? If yes, then set FnCountBefore
1495 // to that.
1496 if (It != FunctionToInstrCount.end())
1497 FnCountBefore = It->second;
1498
1499 // Compute the delta and emit a remark if there was a change.
1500 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
1501 static_cast<int64_t>(FnCountBefore);
1502 if (FnDelta == 0)
1503 continue;
1504
1505 MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
1506 MORE.emit(RemarkBuilder: [&]() {
1507 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
1508 DiagnosticLocation(), &MF->front());
1509 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
1510 << ": Function: "
1511 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
1512 << ": MI instruction count changed from "
1513 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
1514 FnCountBefore)
1515 << " to "
1516 << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
1517 FnCountAfter)
1518 << "; Delta: "
1519 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1520 return R;
1521 });
1522 }
1523}
1524
1525void MachineOutliner::initializeOutlinerMode(const Module &M) {
1526 if (DisableGlobalOutlining)
1527 return;
1528
1529 if (auto *IndexWrapperPass =
1530 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>()) {
1531 auto *TheIndex = IndexWrapperPass->getIndex();
1532 // (Full)LTO module does not have functions added to the index.
1533 // In this case, we run the outliner without using codegen data as usual.
1534 if (TheIndex && !TheIndex->hasExportedFunctions(M))
1535 return;
1536 }
1537
1538 // When codegen data write is enabled, we want to write the local outlined
1539 // hash tree to the custom section, `__llvm_outline`.
1540 // When the outlined hash tree is available from the previous codegen data,
1541 // we want to read it to optimistically create global outlining candidates.
1542 const cl::LibraryOptionsContext &LibraryOptions =
1543 M.getContext().getLibraryOptions();
1544 if (cgdata::emitCGData(LibraryOptions)) {
1545 OutlinerMode = CGDataMode::Write;
1546 // Create a local outlined hash tree to be published.
1547 LocalHashTree = std::make_unique<OutlinedHashTree>();
1548 // We don't need to read the outlined hash tree from the previous codegen
1549 } else if (cgdata::hasOutlinedHashTree(LibraryOptions))
1550 OutlinerMode = CGDataMode::Read;
1551}
1552
1553void MachineOutliner::emitOutlinedHashTree(Module &M) {
1554 assert(LocalHashTree);
1555 if (!LocalHashTree->empty()) {
1556 LLVM_DEBUG({
1557 dbgs() << "Emit outlined hash tree. Size: " << LocalHashTree->size()
1558 << "\n";
1559 });
1560 SmallVector<char> Buf;
1561 raw_svector_ostream OS(Buf);
1562
1563 OutlinedHashTreeRecord HTR(std::move(LocalHashTree));
1564 HTR.serialize(OS);
1565
1566 llvm::StringRef Data(Buf.data(), Buf.size());
1567 std::unique_ptr<MemoryBuffer> Buffer =
1568 MemoryBuffer::getMemBuffer(InputData: Data, BufferName: "in-memory outlined hash tree", RequiresNullTerminator: false);
1569
1570 Triple TT(M.getTargetTriple());
1571 embedBufferInModule(
1572 M, Buf: *Buffer,
1573 SectionName: getCodeGenDataSectionName(CGSK: CG_outline, OF: TT.getObjectFormat()));
1574 }
1575}
1576
1577bool MachineOutliner::runOnModule(Module &M) {
1578 if (skipModule(M))
1579 return false;
1580
1581 // Check if there's anything in the module. If it's empty, then there's
1582 // nothing to outline.
1583 if (M.empty())
1584 return false;
1585
1586 // Initialize the outliner mode.
1587 initializeOutlinerMode(M);
1588
1589 MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1590 TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
1591
1592 // Number to append to the current outlined function.
1593 unsigned OutlinedFunctionNum = 0;
1594
1595 OutlineRepeatedNum = 0;
1596 if (!doOutline(M, OutlinedFunctionNum))
1597 return false;
1598
1599 for (unsigned I = 0; I < OutlinerReruns; ++I) {
1600 OutlinedFunctionNum = 0;
1601 OutlineRepeatedNum++;
1602 if (!doOutline(M, OutlinedFunctionNum)) {
1603 LLVM_DEBUG({
1604 dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1605 << OutlinerReruns + 1 << "\n";
1606 });
1607 break;
1608 }
1609 }
1610
1611 if (OutlinerMode == CGDataMode::Write)
1612 emitOutlinedHashTree(M);
1613
1614 return true;
1615}
1616
1617bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1618 // If the user passed -enable-machine-outliner=always or
1619 // -enable-machine-outliner, the pass will run on all functions in the module.
1620 // Otherwise, if the target supports default outlining, it will run on all
1621 // functions deemed by the target to be worth outlining from by default. Tell
1622 // the user how the outliner is running.
1623 LLVM_DEBUG({
1624 dbgs() << "Machine Outliner: Running on ";
1625 switch (RunOutlinerMode) {
1626 case RunOutliner::AlwaysOutline:
1627 dbgs() << "all functions";
1628 break;
1629 case RunOutliner::OptimisticPGO:
1630 dbgs() << "optimistically cold functions";
1631 break;
1632 case RunOutliner::ConservativePGO:
1633 dbgs() << "conservatively cold functions";
1634 break;
1635 case RunOutliner::TargetDefault:
1636 dbgs() << "target-default functions";
1637 break;
1638 case RunOutliner::NeverOutline:
1639 llvm_unreachable("should not outline");
1640 }
1641 dbgs() << "\n";
1642 });
1643
1644 // If the user specifies that they want to outline from linkonceodrs, set
1645 // it here.
1646 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1647 InstructionMapper Mapper(*MMI);
1648
1649 // Prepare instruction mappings for the suffix tree.
1650 populateMapper(Mapper, M);
1651 std::vector<std::unique_ptr<OutlinedFunction>> FunctionList;
1652
1653 // Find all of the outlining candidates.
1654 if (OutlinerMode == CGDataMode::Read)
1655 findGlobalCandidates(Mapper, FunctionList);
1656 else
1657 findCandidates(Mapper, FunctionList);
1658
1659 // If we've requested size remarks, then collect the MI counts of every
1660 // function before outlining, and the MI counts after outlining.
1661 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1662 // the pass manager's responsibility.
1663 // This could pretty easily be placed in outline instead, but because we
1664 // really ultimately *don't* want this here, it's done like this for now
1665 // instead.
1666
1667 // Check if we want size remarks.
1668 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1669 StringMap<unsigned> FunctionToInstrCount;
1670 if (ShouldEmitSizeRemarks)
1671 initSizeRemarkInfo(M, FunctionToInstrCount);
1672
1673 // Outline each of the candidates and return true if something was outlined.
1674 bool OutlinedSomething =
1675 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1676
1677 // If we outlined something, we definitely changed the MI count of the
1678 // module. If we've asked for size remarks, then output them.
1679 // FIXME: This should be in the pass manager.
1680 if (ShouldEmitSizeRemarks && OutlinedSomething)
1681 emitInstrCountChangedRemark(M, FunctionToInstrCount);
1682
1683 LLVM_DEBUG({
1684 if (!OutlinedSomething)
1685 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1686 << " because no changes were found.\n";
1687 });
1688
1689 return OutlinedSomething;
1690}
1691