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