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/OptimizationRemarkEmitter.h"
63#include "llvm/CodeGen/LivePhysRegs.h"
64#include "llvm/CodeGen/MachineModuleInfo.h"
65#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
66#include "llvm/CodeGen/Passes.h"
67#include "llvm/CodeGen/TargetInstrInfo.h"
68#include "llvm/CodeGen/TargetSubtargetInfo.h"
69#include "llvm/IR/DIBuilder.h"
70#include "llvm/IR/IRBuilder.h"
71#include "llvm/IR/Mangler.h"
72#include "llvm/IR/Module.h"
73#include "llvm/InitializePasses.h"
74#include "llvm/Support/CommandLine.h"
75#include "llvm/Support/Debug.h"
76#include "llvm/Support/SuffixTree.h"
77#include "llvm/Support/raw_ostream.h"
78#include <functional>
79#include <tuple>
80#include <vector>
81
82#define DEBUG_TYPE "machine-outliner"
83
84using namespace llvm;
85using namespace ore;
86using namespace outliner;
87
88// Statistics for outlined functions.
89STATISTIC(NumOutlined, "Number of candidates outlined");
90STATISTIC(FunctionsCreated, "Number of functions created");
91
92// Statistics for instruction mapping.
93STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped");
94STATISTIC(NumIllegalInUnsignedVec,
95 "Unoutlinable instructions mapped + number of sentinel values");
96STATISTIC(NumSentinels, "Sentinel values inserted during mapping");
97STATISTIC(NumInvisible,
98 "Invisible instructions skipped during mapping");
99STATISTIC(UnsignedVecSize,
100 "Total number of instructions mapped and saved to mapping vector");
101
102// Set to true if the user wants the outliner to run on linkonceodr linkage
103// functions. This is false by default because the linker can dedupe linkonceodr
104// functions. Since the outliner is confined to a single module (modulo LTO),
105// this is off by default. It should, however, be the default behaviour in
106// LTO.
107static cl::opt<bool> EnableLinkOnceODROutlining(
108 "enable-linkonceodr-outlining", cl::Hidden,
109 cl::desc("Enable the machine outliner on linkonceodr functions"),
110 cl::init(Val: false));
111
112/// Number of times to re-run the outliner. This is not the total number of runs
113/// as the outliner will run at least one time. The default value is set to 0,
114/// meaning the outliner will run one time and rerun zero times after that.
115static cl::opt<unsigned> OutlinerReruns(
116 "machine-outliner-reruns", cl::init(Val: 0), cl::Hidden,
117 cl::desc(
118 "Number of times to rerun the outliner after the initial outline"));
119
120static cl::opt<unsigned> OutlinerBenefitThreshold(
121 "outliner-benefit-threshold", cl::init(Val: 1), cl::Hidden,
122 cl::desc(
123 "The minimum size in bytes before an outlining candidate is accepted"));
124
125static cl::opt<bool> OutlinerLeafDescendants(
126 "outliner-leaf-descendants", cl::init(Val: true), cl::Hidden,
127 cl::desc("Consider all leaf descendants of internal nodes of the suffix "
128 "tree as candidates for outlining (if false, only leaf children "
129 "are considered)"));
130
131namespace {
132
133/// Maps \p MachineInstrs to unsigned integers and stores the mappings.
134struct InstructionMapper {
135
136 /// The next available integer to assign to a \p MachineInstr that
137 /// cannot be outlined.
138 ///
139 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
140 unsigned IllegalInstrNumber = -3;
141
142 /// The next available integer to assign to a \p MachineInstr that can
143 /// be outlined.
144 unsigned LegalInstrNumber = 0;
145
146 /// Correspondence from \p MachineInstrs to unsigned integers.
147 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
148 InstructionIntegerMap;
149
150 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
151 DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
152
153 /// The vector of unsigned integers that the module is mapped to.
154 SmallVector<unsigned> UnsignedVec;
155
156 /// Stores the location of the instruction associated with the integer
157 /// at index i in \p UnsignedVec for each index i.
158 SmallVector<MachineBasicBlock::iterator> InstrList;
159
160 // Set if we added an illegal number in the previous step.
161 // Since each illegal number is unique, we only need one of them between
162 // each range of legal numbers. This lets us make sure we don't add more
163 // than one illegal number per range.
164 bool AddedIllegalLastTime = false;
165
166 /// Maps \p *It to a legal integer.
167 ///
168 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
169 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
170 ///
171 /// \returns The integer that \p *It was mapped to.
172 unsigned mapToLegalUnsigned(
173 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
174 bool &HaveLegalRange, unsigned &NumLegalInBlock,
175 SmallVector<unsigned> &UnsignedVecForMBB,
176 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {
177 // We added something legal, so we should unset the AddedLegalLastTime
178 // flag.
179 AddedIllegalLastTime = false;
180
181 // If we have at least two adjacent legal instructions (which may have
182 // invisible instructions in between), remember that.
183 if (CanOutlineWithPrevInstr)
184 HaveLegalRange = true;
185 CanOutlineWithPrevInstr = true;
186
187 // Keep track of the number of legal instructions we insert.
188 NumLegalInBlock++;
189
190 // Get the integer for this instruction or give it the current
191 // LegalInstrNumber.
192 InstrListForMBB.push_back(Elt: It);
193 MachineInstr &MI = *It;
194 bool WasInserted;
195 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
196 ResultIt;
197 std::tie(args&: ResultIt, args&: WasInserted) =
198 InstructionIntegerMap.insert(KV: std::make_pair(x: &MI, y&: LegalInstrNumber));
199 unsigned MINumber = ResultIt->second;
200
201 // There was an insertion.
202 if (WasInserted)
203 LegalInstrNumber++;
204
205 UnsignedVecForMBB.push_back(Elt: MINumber);
206
207 // Make sure we don't overflow or use any integers reserved by the DenseMap.
208 if (LegalInstrNumber >= IllegalInstrNumber)
209 report_fatal_error(reason: "Instruction mapping overflow!");
210
211 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
212 "Tried to assign DenseMap tombstone or empty key to instruction.");
213 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
214 "Tried to assign DenseMap tombstone or empty key to instruction.");
215
216 // Statistics.
217 ++NumLegalInUnsignedVec;
218 return MINumber;
219 }
220
221 /// Maps \p *It to an illegal integer.
222 ///
223 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
224 /// IllegalInstrNumber.
225 ///
226 /// \returns The integer that \p *It was mapped to.
227 unsigned mapToIllegalUnsigned(
228 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
229 SmallVector<unsigned> &UnsignedVecForMBB,
230 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {
231 // Can't outline an illegal instruction. Set the flag.
232 CanOutlineWithPrevInstr = false;
233
234 // Only add one illegal number per range of legal numbers.
235 if (AddedIllegalLastTime)
236 return IllegalInstrNumber;
237
238 // Remember that we added an illegal number last time.
239 AddedIllegalLastTime = true;
240 unsigned MINumber = IllegalInstrNumber;
241
242 InstrListForMBB.push_back(Elt: It);
243 UnsignedVecForMBB.push_back(Elt: IllegalInstrNumber);
244 IllegalInstrNumber--;
245 // Statistics.
246 ++NumIllegalInUnsignedVec;
247
248 assert(LegalInstrNumber < IllegalInstrNumber &&
249 "Instruction mapping overflow!");
250
251 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
252 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
253
254 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
255 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
256
257 return MINumber;
258 }
259
260 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
261 /// and appends it to \p UnsignedVec and \p InstrList.
262 ///
263 /// Two instructions are assigned the same integer if they are identical.
264 /// If an instruction is deemed unsafe to outline, then it will be assigned an
265 /// unique integer. The resulting mapping is placed into a suffix tree and
266 /// queried for candidates.
267 ///
268 /// \param MBB The \p MachineBasicBlock to be translated into integers.
269 /// \param TII \p TargetInstrInfo for the function.
270 void convertToUnsignedVec(MachineBasicBlock &MBB,
271 const TargetInstrInfo &TII) {
272 LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName()
273 << "' to unsigned vector ***\n");
274 unsigned Flags = 0;
275
276 // Don't even map in this case.
277 if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
278 return;
279
280 auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags);
281 LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size()
282 << " outlinable range(s)\n");
283 if (OutlinableRanges.empty())
284 return;
285
286 // Store info for the MBB for later outlining.
287 MBBFlagsMap[&MBB] = Flags;
288
289 MachineBasicBlock::iterator It = MBB.begin();
290
291 // The number of instructions in this block that will be considered for
292 // outlining.
293 unsigned NumLegalInBlock = 0;
294
295 // True if we have at least two legal instructions which aren't separated
296 // by an illegal instruction.
297 bool HaveLegalRange = false;
298
299 // True if we can perform outlining given the last mapped (non-invisible)
300 // instruction. This lets us know if we have a legal range.
301 bool CanOutlineWithPrevInstr = false;
302
303 // FIXME: Should this all just be handled in the target, rather than using
304 // repeated calls to getOutliningType?
305 SmallVector<unsigned> UnsignedVecForMBB;
306 SmallVector<MachineBasicBlock::iterator> InstrListForMBB;
307
308 LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n");
309 for (auto &OutlinableRange : OutlinableRanges) {
310 auto OutlinableRangeBegin = OutlinableRange.first;
311 auto OutlinableRangeEnd = OutlinableRange.second;
312#ifndef NDEBUG
313 LLVM_DEBUG(
314 dbgs() << "Mapping "
315 << std::distance(OutlinableRangeBegin, OutlinableRangeEnd)
316 << " instruction range\n");
317 // Everything outside of an outlinable range is illegal.
318 unsigned NumSkippedInRange = 0;
319#endif
320 for (; It != OutlinableRangeBegin; ++It) {
321#ifndef NDEBUG
322 ++NumSkippedInRange;
323#endif
324 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
325 InstrListForMBB);
326 }
327#ifndef NDEBUG
328 LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange
329 << " instructions outside outlinable range\n");
330#endif
331 assert(It != MBB.end() && "Should still have instructions?");
332 // `It` is now positioned at the beginning of a range of instructions
333 // which may be outlinable. Check if each instruction is known to be safe.
334 for (; It != OutlinableRangeEnd; ++It) {
335 // Keep track of where this instruction is in the module.
336 switch (TII.getOutliningType(MIT&: It, Flags)) {
337 case InstrType::Illegal:
338 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
339 InstrListForMBB);
340 break;
341
342 case InstrType::Legal:
343 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
344 NumLegalInBlock, UnsignedVecForMBB,
345 InstrListForMBB);
346 break;
347
348 case InstrType::LegalTerminator:
349 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
350 NumLegalInBlock, UnsignedVecForMBB,
351 InstrListForMBB);
352 // The instruction also acts as a terminator, so we have to record
353 // that in the string.
354 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
355 InstrListForMBB);
356 break;
357
358 case InstrType::Invisible:
359 // Normally this is set by mapTo(Blah)Unsigned, but we just want to
360 // skip this instruction. So, unset the flag here.
361 ++NumInvisible;
362 AddedIllegalLastTime = false;
363 break;
364 }
365 }
366 }
367
368 LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n");
369
370 // Are there enough legal instructions in the block for outlining to be
371 // possible?
372 if (HaveLegalRange) {
373 // After we're done every insertion, uniquely terminate this part of the
374 // "string". This makes sure we won't match across basic block or function
375 // boundaries since the "end" is encoded uniquely and thus appears in no
376 // repeated substring.
377 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
378 InstrListForMBB);
379 ++NumSentinels;
380 append_range(C&: InstrList, R&: InstrListForMBB);
381 append_range(C&: UnsignedVec, R&: UnsignedVecForMBB);
382 }
383 }
384
385 InstructionMapper() {
386 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
387 // changed.
388 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
389 "DenseMapInfo<unsigned>'s empty key isn't -1!");
390 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
391 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
392 }
393};
394
395/// An interprocedural pass which finds repeated sequences of
396/// instructions and replaces them with calls to functions.
397///
398/// Each instruction is mapped to an unsigned integer and placed in a string.
399/// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
400/// is then repeatedly queried for repeated sequences of instructions. Each
401/// non-overlapping repeated sequence is then placed in its own
402/// \p MachineFunction and each instance is then replaced with a call to that
403/// function.
404struct MachineOutliner : public ModulePass {
405
406 static char ID;
407
408 /// Set to true if the outliner should consider functions with
409 /// linkonceodr linkage.
410 bool OutlineFromLinkOnceODRs = false;
411
412 /// The current repeat number of machine outlining.
413 unsigned OutlineRepeatedNum = 0;
414
415 /// Set to true if the outliner should run on all functions in the module
416 /// considered safe for outlining.
417 /// Set to true by default for compatibility with llc's -run-pass option.
418 /// Set when the pass is constructed in TargetPassConfig.
419 bool RunOnAllFunctions = true;
420
421 StringRef getPassName() const override { return "Machine Outliner"; }
422
423 void getAnalysisUsage(AnalysisUsage &AU) const override {
424 AU.addRequired<MachineModuleInfoWrapperPass>();
425 AU.addPreserved<MachineModuleInfoWrapperPass>();
426 AU.setPreservesAll();
427 ModulePass::getAnalysisUsage(AU);
428 }
429
430 MachineOutliner() : ModulePass(ID) {
431 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
432 }
433
434 /// Remark output explaining that not outlining a set of candidates would be
435 /// better than outlining that set.
436 void emitNotOutliningCheaperRemark(
437 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
438 OutlinedFunction &OF);
439
440 /// Remark output explaining that a function was outlined.
441 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
442
443 /// Find all repeated substrings that satisfy the outlining cost model by
444 /// constructing a suffix tree.
445 ///
446 /// If a substring appears at least twice, then it must be represented by
447 /// an internal node which appears in at least two suffixes. Each suffix
448 /// is represented by a leaf node. To do this, we visit each internal node
449 /// in the tree, using the leaf children of each internal node. If an
450 /// internal node represents a beneficial substring, then we use each of
451 /// its leaf children to find the locations of its substring.
452 ///
453 /// \param Mapper Contains outlining mapping information.
454 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
455 /// each type of candidate.
456 void findCandidates(InstructionMapper &Mapper,
457 std::vector<OutlinedFunction> &FunctionList);
458
459 /// Replace the sequences of instructions represented by \p OutlinedFunctions
460 /// with calls to functions.
461 ///
462 /// \param M The module we are outlining from.
463 /// \param FunctionList A list of functions to be inserted into the module.
464 /// \param Mapper Contains the instruction mappings for the module.
465 bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
466 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
467
468 /// Creates a function for \p OF and inserts it into the module.
469 MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
470 InstructionMapper &Mapper,
471 unsigned Name);
472
473 /// Calls 'doOutline()' 1 + OutlinerReruns times.
474 bool runOnModule(Module &M) override;
475
476 /// Construct a suffix tree on the instructions in \p M and outline repeated
477 /// strings from that tree.
478 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
479
480 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
481 /// function for remark emission.
482 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
483 for (const Candidate &C : OF.Candidates)
484 if (MachineFunction *MF = C.getMF())
485 if (DISubprogram *SP = MF->getFunction().getSubprogram())
486 return SP;
487 return nullptr;
488 }
489
490 /// Populate and \p InstructionMapper with instruction-to-integer mappings.
491 /// These are used to construct a suffix tree.
492 void populateMapper(InstructionMapper &Mapper, Module &M,
493 MachineModuleInfo &MMI);
494
495 /// Initialize information necessary to output a size remark.
496 /// FIXME: This should be handled by the pass manager, not the outliner.
497 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
498 /// pass manager.
499 void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI,
500 StringMap<unsigned> &FunctionToInstrCount);
501
502 /// Emit the remark.
503 // FIXME: This should be handled by the pass manager, not the outliner.
504 void
505 emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
506 const StringMap<unsigned> &FunctionToInstrCount);
507};
508} // Anonymous namespace.
509
510char MachineOutliner::ID = 0;
511
512namespace llvm {
513ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
514 MachineOutliner *OL = new MachineOutliner();
515 OL->RunOnAllFunctions = RunOnAllFunctions;
516 return OL;
517}
518
519} // namespace llvm
520
521INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
522 false)
523
524void MachineOutliner::emitNotOutliningCheaperRemark(
525 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
526 OutlinedFunction &OF) {
527 // FIXME: Right now, we arbitrarily choose some Candidate from the
528 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
529 // We should probably sort these by function name or something to make sure
530 // the remarks are stable.
531 Candidate &C = CandidatesForRepeatedSeq.front();
532 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
533 MORE.emit(RemarkBuilder: [&]() {
534 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
535 C.front().getDebugLoc(), C.getMBB());
536 R << "Did not outline " << NV("Length", StringLen) << " instructions"
537 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
538 << " locations."
539 << " Bytes from outlining all occurrences ("
540 << NV("OutliningCost", OF.getOutliningCost()) << ")"
541 << " >= Unoutlined instruction bytes ("
542 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
543 << " (Also found at: ";
544
545 // Tell the user the other places the candidate was found.
546 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
547 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
548 CandidatesForRepeatedSeq[i].front().getDebugLoc());
549 if (i != e - 1)
550 R << ", ";
551 }
552
553 R << ")";
554 return R;
555 });
556}
557
558void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
559 MachineBasicBlock *MBB = &*OF.MF->begin();
560 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
561 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
562 MBB->findDebugLoc(MBBI: MBB->begin()), MBB);
563 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
564 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
565 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
566 << " locations. "
567 << "(Found at: ";
568
569 // Tell the user the other places the candidate was found.
570 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
571
572 R << NV((Twine("StartLoc") + Twine(i)).str(),
573 OF.Candidates[i].front().getDebugLoc());
574 if (i != e - 1)
575 R << ", ";
576 }
577
578 R << ")";
579
580 MORE.emit(OptDiag&: R);
581}
582
583void MachineOutliner::findCandidates(
584 InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
585 FunctionList.clear();
586 SuffixTree ST(Mapper.UnsignedVec, OutlinerLeafDescendants);
587
588 // First, find all of the repeated substrings in the tree of minimum length
589 // 2.
590 std::vector<Candidate> CandidatesForRepeatedSeq;
591 LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n");
592 LLVM_DEBUG(
593 dbgs() << "Searching for overlaps in all repeated sequences...\n");
594 for (SuffixTree::RepeatedSubstring &RS : ST) {
595 CandidatesForRepeatedSeq.clear();
596 unsigned StringLen = RS.Length;
597 LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n");
598 // Debug code to keep track of how many candidates we removed.
599#ifndef NDEBUG
600 unsigned NumDiscarded = 0;
601 unsigned NumKept = 0;
602#endif
603 // Sort the start indices so that we can efficiently check if candidates
604 // overlap with the ones we've already found for this sequence.
605 llvm::sort(C&: RS.StartIndices);
606 for (const unsigned &StartIdx : RS.StartIndices) {
607 // Trick: Discard some candidates that would be incompatible with the
608 // ones we've already found for this sequence. This will save us some
609 // work in candidate selection.
610 //
611 // If two candidates overlap, then we can't outline them both. This
612 // happens when we have candidates that look like, say
613 //
614 // AA (where each "A" is an instruction).
615 //
616 // We might have some portion of the module that looks like this:
617 // AAAAAA (6 A's)
618 //
619 // In this case, there are 5 different copies of "AA" in this range, but
620 // at most 3 can be outlined. If only outlining 3 of these is going to
621 // be unbeneficial, then we ought to not bother.
622 //
623 // Note that two things DON'T overlap when they look like this:
624 // start1...end1 .... start2...end2
625 // That is, one must either
626 // * End before the other starts
627 // * Start after the other ends
628 unsigned EndIdx = StartIdx + StringLen - 1;
629 if (!CandidatesForRepeatedSeq.empty() &&
630 StartIdx <= CandidatesForRepeatedSeq.back().getEndIdx()) {
631#ifndef NDEBUG
632 ++NumDiscarded;
633 LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx << ", "
634 << EndIdx << "]; overlaps with candidate @ ["
635 << CandidatesForRepeatedSeq.back().getStartIdx()
636 << ", " << CandidatesForRepeatedSeq.back().getEndIdx()
637 << "]\n");
638#endif
639 continue;
640 }
641 // It doesn't overlap with anything, so we can outline it.
642 // Each sequence is over [StartIt, EndIt].
643 // Save the candidate and its location.
644#ifndef NDEBUG
645 ++NumKept;
646#endif
647 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
648 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
649 MachineBasicBlock *MBB = StartIt->getParent();
650 CandidatesForRepeatedSeq.emplace_back(args: StartIdx, args&: StringLen, args&: StartIt, args&: EndIt,
651 args&: MBB, args: FunctionList.size(),
652 args&: Mapper.MBBFlagsMap[MBB]);
653 }
654#ifndef NDEBUG
655 LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded
656 << "\n");
657 LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n");
658#endif
659
660 // We've found something we might want to outline.
661 // Create an OutlinedFunction to store it and check if it'd be beneficial
662 // to outline.
663 if (CandidatesForRepeatedSeq.size() < 2)
664 continue;
665
666 // Arbitrarily choose a TII from the first candidate.
667 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
668 const TargetInstrInfo *TII =
669 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
670
671 std::optional<OutlinedFunction> OF =
672 TII->getOutliningCandidateInfo(RepeatedSequenceLocs&: CandidatesForRepeatedSeq);
673
674 // If we deleted too many candidates, then there's nothing worth outlining.
675 // FIXME: This should take target-specified instruction sizes into account.
676 if (!OF || OF->Candidates.size() < 2)
677 continue;
678
679 // Is it better to outline this candidate than not?
680 if (OF->getBenefit() < OutlinerBenefitThreshold) {
681 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF&: *OF);
682 continue;
683 }
684
685 FunctionList.push_back(x: *OF);
686 }
687}
688
689MachineFunction *MachineOutliner::createOutlinedFunction(
690 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
691
692 // Create the function name. This should be unique.
693 // FIXME: We should have a better naming scheme. This should be stable,
694 // regardless of changes to the outliner's cost model/traversal order.
695 std::string FunctionName = "OUTLINED_FUNCTION_";
696 if (OutlineRepeatedNum > 0)
697 FunctionName += std::to_string(val: OutlineRepeatedNum + 1) + "_";
698 FunctionName += std::to_string(val: Name);
699 LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n");
700
701 // Create the function using an IR-level function.
702 LLVMContext &C = M.getContext();
703 Function *F = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false),
704 Linkage: Function::ExternalLinkage, N: FunctionName, M);
705
706 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
707 // which gives us better results when we outline from linkonceodr functions.
708 F->setLinkage(GlobalValue::InternalLinkage);
709 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
710
711 // Set optsize/minsize, so we don't insert padding between outlined
712 // functions.
713 F->addFnAttr(Kind: Attribute::OptimizeForSize);
714 F->addFnAttr(Kind: Attribute::MinSize);
715
716 Candidate &FirstCand = OF.Candidates.front();
717 const TargetInstrInfo &TII =
718 *FirstCand.getMF()->getSubtarget().getInstrInfo();
719
720 TII.mergeOutliningCandidateAttributes(F&: *F, Candidates&: OF.Candidates);
721
722 // Set uwtable, so we generate eh_frame.
723 UWTableKind UW = std::accumulate(
724 first: OF.Candidates.cbegin(), last: OF.Candidates.cend(), init: UWTableKind::None,
725 binary_op: [](UWTableKind K, const outliner::Candidate &C) {
726 return std::max(a: K, b: C.getMF()->getFunction().getUWTableKind());
727 });
728 F->setUWTableKind(UW);
729
730 BasicBlock *EntryBB = BasicBlock::Create(Context&: C, Name: "entry", Parent: F);
731 IRBuilder<> Builder(EntryBB);
732 Builder.CreateRetVoid();
733
734 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
735 MachineFunction &MF = MMI.getOrCreateMachineFunction(F&: *F);
736 MF.setIsOutlined(true);
737 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
738
739 // Insert the new function into the module.
740 MF.insert(MBBI: MF.begin(), MBB: &MBB);
741
742 MachineFunction *OriginalMF = FirstCand.front().getMF();
743 const std::vector<MCCFIInstruction> &Instrs =
744 OriginalMF->getFrameInstructions();
745 for (auto &MI : FirstCand) {
746 if (MI.isDebugInstr())
747 continue;
748
749 // Don't keep debug information for outlined instructions.
750 auto DL = DebugLoc();
751 if (MI.isCFIInstruction()) {
752 unsigned CFIIndex = MI.getOperand(i: 0).getCFIIndex();
753 MCCFIInstruction CFI = Instrs[CFIIndex];
754 BuildMI(BB&: MBB, I: MBB.end(), MIMD: DL, MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
755 .addCFIIndex(CFIIndex: MF.addFrameInst(Inst: CFI));
756 } else {
757 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: &MI);
758 NewMI->dropMemRefs(MF);
759 NewMI->setDebugLoc(DL);
760 MBB.insert(I: MBB.end(), MI: NewMI);
761 }
762 }
763
764 // Set normal properties for a late MachineFunction.
765 MF.getProperties().reset(P: MachineFunctionProperties::Property::IsSSA);
766 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
767 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
768 MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
769 MF.getRegInfo().freezeReservedRegs();
770
771 // Compute live-in set for outlined fn
772 const MachineRegisterInfo &MRI = MF.getRegInfo();
773 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
774 LivePhysRegs LiveIns(TRI);
775 for (auto &Cand : OF.Candidates) {
776 // Figure out live-ins at the first instruction.
777 MachineBasicBlock &OutlineBB = *Cand.front().getParent();
778 LivePhysRegs CandLiveIns(TRI);
779 CandLiveIns.addLiveOuts(MBB: OutlineBB);
780 for (const MachineInstr &MI :
781 reverse(C: make_range(x: Cand.begin(), y: OutlineBB.end())))
782 CandLiveIns.stepBackward(MI);
783
784 // The live-in set for the outlined function is the union of the live-ins
785 // from all the outlining points.
786 for (MCPhysReg Reg : CandLiveIns)
787 LiveIns.addReg(Reg);
788 }
789 addLiveIns(MBB, LiveRegs: LiveIns);
790
791 TII.buildOutlinedFrame(MBB, MF, OF);
792
793 // If there's a DISubprogram associated with this outlined function, then
794 // emit debug info for the outlined function.
795 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
796 // We have a DISubprogram. Get its DICompileUnit.
797 DICompileUnit *CU = SP->getUnit();
798 DIBuilder DB(M, true, CU);
799 DIFile *Unit = SP->getFile();
800 Mangler Mg;
801 // Get the mangled name of the function for the linkage name.
802 std::string Dummy;
803 raw_string_ostream MangledNameStream(Dummy);
804 Mg.getNameWithPrefix(OS&: MangledNameStream, GV: F, CannotUsePrivateLabel: false);
805
806 DISubprogram *OutlinedSP = DB.createFunction(
807 Scope: Unit /* Context */, Name: F->getName(), LinkageName: StringRef(Dummy), File: Unit /* File */,
808 LineNo: 0 /* Line 0 is reserved for compiler-generated code. */,
809 Ty: DB.createSubroutineType(
810 ParameterTypes: DB.getOrCreateTypeArray(Elements: std::nullopt)), /* void type */
811 ScopeLine: 0, /* Line 0 is reserved for compiler-generated code. */
812 Flags: DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
813 /* Outlined code is optimized code by definition. */
814 SPFlags: DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
815
816 // Don't add any new variables to the subprogram.
817 DB.finalizeSubprogram(SP: OutlinedSP);
818
819 // Attach subprogram to the function.
820 F->setSubprogram(OutlinedSP);
821 // We're done with the DIBuilder.
822 DB.finalize();
823 }
824
825 return &MF;
826}
827
828bool MachineOutliner::outline(Module &M,
829 std::vector<OutlinedFunction> &FunctionList,
830 InstructionMapper &Mapper,
831 unsigned &OutlinedFunctionNum) {
832 LLVM_DEBUG(dbgs() << "*** Outlining ***\n");
833 LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size()
834 << "\n");
835 bool OutlinedSomething = false;
836
837 // Sort by priority where priority := getNotOutlinedCost / getOutliningCost.
838 // The function with highest priority should be outlined first.
839 stable_sort(Range&: FunctionList,
840 C: [](const OutlinedFunction &LHS, const OutlinedFunction &RHS) {
841 return LHS.getNotOutlinedCost() * RHS.getOutliningCost() >
842 RHS.getNotOutlinedCost() * LHS.getOutliningCost();
843 });
844
845 // Walk over each function, outlining them as we go along. Functions are
846 // outlined greedily, based off the sort above.
847 auto *UnsignedVecBegin = Mapper.UnsignedVec.begin();
848 LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n");
849 for (OutlinedFunction &OF : FunctionList) {
850#ifndef NDEBUG
851 auto NumCandidatesBefore = OF.Candidates.size();
852#endif
853 // If we outlined something that overlapped with a candidate in a previous
854 // step, then we can't outline from it.
855 erase_if(C&: OF.Candidates, P: [&UnsignedVecBegin](Candidate &C) {
856 return std::any_of(first: UnsignedVecBegin + C.getStartIdx(),
857 last: UnsignedVecBegin + C.getEndIdx() + 1, pred: [](unsigned I) {
858 return I == static_cast<unsigned>(-1);
859 });
860 });
861
862#ifndef NDEBUG
863 auto NumCandidatesAfter = OF.Candidates.size();
864 LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter
865 << "/" << NumCandidatesBefore << " candidates\n");
866#endif
867
868 // If we made it unbeneficial to outline this function, skip it.
869 if (OF.getBenefit() < OutlinerBenefitThreshold) {
870 LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF.getBenefit()
871 << " B) < threshold (" << OutlinerBenefitThreshold
872 << " B)\n");
873 continue;
874 }
875
876 LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF.getBenefit()
877 << " B) > threshold (" << OutlinerBenefitThreshold
878 << " B)\n");
879
880 // It's beneficial. Create the function and outline its sequence's
881 // occurrences.
882 OF.MF = createOutlinedFunction(M, OF, Mapper, Name: OutlinedFunctionNum);
883 emitOutlinedFunctionRemark(OF);
884 FunctionsCreated++;
885 OutlinedFunctionNum++; // Created a function, move to the next name.
886 MachineFunction *MF = OF.MF;
887 const TargetSubtargetInfo &STI = MF->getSubtarget();
888 const TargetInstrInfo &TII = *STI.getInstrInfo();
889
890 // Replace occurrences of the sequence with calls to the new function.
891 LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n");
892 for (Candidate &C : OF.Candidates) {
893 MachineBasicBlock &MBB = *C.getMBB();
894 MachineBasicBlock::iterator StartIt = C.begin();
895 MachineBasicBlock::iterator EndIt = std::prev(x: C.end());
896
897 // Insert the call.
898 auto CallInst = TII.insertOutlinedCall(M, MBB, It&: StartIt, MF&: *MF, C);
899// Insert the call.
900#ifndef NDEBUG
901 auto MBBBeingOutlinedFromName =
902 MBB.getName().empty() ? "<unknown>" : MBB.getName().str();
903 auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty()
904 ? "<unknown>"
905 : MBB.getParent()->getName().str();
906 LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in "
907 << MFBeingOutlinedFromName << ":"
908 << MBBBeingOutlinedFromName << "\n");
909 LLVM_DEBUG(dbgs() << " .. " << *CallInst);
910#endif
911
912 // If the caller tracks liveness, then we need to make sure that
913 // anything we outline doesn't break liveness assumptions. The outlined
914 // functions themselves currently don't track liveness, but we should
915 // make sure that the ranges we yank things out of aren't wrong.
916 if (MBB.getParent()->getProperties().hasProperty(
917 P: MachineFunctionProperties::Property::TracksLiveness)) {
918 // The following code is to add implicit def operands to the call
919 // instruction. It also updates call site information for moved
920 // code.
921 SmallSet<Register, 2> UseRegs, DefRegs;
922 // Copy over the defs in the outlined range.
923 // First inst in outlined range <-- Anything that's defined in this
924 // ... .. range has to be added as an
925 // implicit Last inst in outlined range <-- def to the call
926 // instruction. Also remove call site information for outlined block
927 // of code. The exposed uses need to be copied in the outlined range.
928 for (MachineBasicBlock::reverse_iterator
929 Iter = EndIt.getReverse(),
930 Last = std::next(x: CallInst.getReverse());
931 Iter != Last; Iter++) {
932 MachineInstr *MI = &*Iter;
933 SmallSet<Register, 2> InstrUseRegs;
934 for (MachineOperand &MOP : MI->operands()) {
935 // Skip over anything that isn't a register.
936 if (!MOP.isReg())
937 continue;
938
939 if (MOP.isDef()) {
940 // Introduce DefRegs set to skip the redundant register.
941 DefRegs.insert(V: MOP.getReg());
942 if (UseRegs.count(V: MOP.getReg()) &&
943 !InstrUseRegs.count(V: MOP.getReg()))
944 // Since the regiester is modeled as defined,
945 // it is not necessary to be put in use register set.
946 UseRegs.erase(V: MOP.getReg());
947 } else if (!MOP.isUndef()) {
948 // Any register which is not undefined should
949 // be put in the use register set.
950 UseRegs.insert(V: MOP.getReg());
951 InstrUseRegs.insert(V: MOP.getReg());
952 }
953 }
954 if (MI->isCandidateForCallSiteEntry())
955 MI->getMF()->eraseCallSiteInfo(MI);
956 }
957
958 for (const Register &I : DefRegs)
959 // If it's a def, add it to the call instruction.
960 CallInst->addOperand(
961 Op: MachineOperand::CreateReg(Reg: I, isDef: true, /* isDef = true */
962 isImp: true /* isImp = true */));
963
964 for (const Register &I : UseRegs)
965 // If it's a exposed use, add it to the call instruction.
966 CallInst->addOperand(
967 Op: MachineOperand::CreateReg(Reg: I, isDef: false, /* isDef = false */
968 isImp: true /* isImp = true */));
969 }
970
971 // Erase from the point after where the call was inserted up to, and
972 // including, the final instruction in the sequence.
973 // Erase needs one past the end, so we need std::next there too.
974 MBB.erase(I: std::next(x: StartIt), E: std::next(x: EndIt));
975
976 // Keep track of what we removed by marking them all as -1.
977 for (unsigned &I : make_range(x: UnsignedVecBegin + C.getStartIdx(),
978 y: UnsignedVecBegin + C.getEndIdx() + 1))
979 I = static_cast<unsigned>(-1);
980 OutlinedSomething = true;
981
982 // Statistics.
983 NumOutlined++;
984 }
985 }
986
987 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
988 return OutlinedSomething;
989}
990
991void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
992 MachineModuleInfo &MMI) {
993 // Build instruction mappings for each function in the module. Start by
994 // iterating over each Function in M.
995 LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n");
996 for (Function &F : M) {
997 LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n");
998
999 if (F.hasFnAttribute(Kind: "nooutline")) {
1000 LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n");
1001 continue;
1002 }
1003
1004 // There's something in F. Check if it has a MachineFunction associated with
1005 // it.
1006 MachineFunction *MF = MMI.getMachineFunction(F);
1007
1008 // If it doesn't, then there's nothing to outline from. Move to the next
1009 // Function.
1010 if (!MF) {
1011 LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n");
1012 continue;
1013 }
1014
1015 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1016 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) {
1017 LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from "
1018 "function by default\n");
1019 continue;
1020 }
1021
1022 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1023 // If it isn't, then move on to the next Function in the module.
1024 if (!TII->isFunctionSafeToOutlineFrom(MF&: *MF, OutlineFromLinkOnceODRs)) {
1025 LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName()
1026 << ": unsafe to outline from\n");
1027 continue;
1028 }
1029
1030 // We have a function suitable for outlining. Iterate over every
1031 // MachineBasicBlock in MF and try to map its instructions to a list of
1032 // unsigned integers.
1033 const unsigned MinMBBSize = 2;
1034
1035 for (MachineBasicBlock &MBB : *MF) {
1036 LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n");
1037 // If there isn't anything in MBB, then there's no point in outlining from
1038 // it.
1039 // If there are fewer than 2 instructions in the MBB, then it can't ever
1040 // contain something worth outlining.
1041 // FIXME: This should be based off of the maximum size in B of an outlined
1042 // call versus the size in B of the MBB.
1043 if (MBB.size() < MinMBBSize) {
1044 LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of "
1045 << MinMBBSize << "\n");
1046 continue;
1047 }
1048
1049 // Check if MBB could be the target of an indirect branch. If it is, then
1050 // we don't want to outline from it.
1051 if (MBB.hasAddressTaken()) {
1052 LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n");
1053 continue;
1054 }
1055
1056 // MBB is suitable for outlining. Map it to a list of unsigneds.
1057 Mapper.convertToUnsignedVec(MBB, TII: *TII);
1058 }
1059 }
1060 // Statistics.
1061 UnsignedVecSize = Mapper.UnsignedVec.size();
1062}
1063
1064void MachineOutliner::initSizeRemarkInfo(
1065 const Module &M, const MachineModuleInfo &MMI,
1066 StringMap<unsigned> &FunctionToInstrCount) {
1067 // Collect instruction counts for every function. We'll use this to emit
1068 // per-function size remarks later.
1069 for (const Function &F : M) {
1070 MachineFunction *MF = MMI.getMachineFunction(F);
1071
1072 // We only care about MI counts here. If there's no MachineFunction at this
1073 // point, then there won't be after the outliner runs, so let's move on.
1074 if (!MF)
1075 continue;
1076 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
1077 }
1078}
1079
1080void MachineOutliner::emitInstrCountChangedRemark(
1081 const Module &M, const MachineModuleInfo &MMI,
1082 const StringMap<unsigned> &FunctionToInstrCount) {
1083 // Iterate over each function in the module and emit remarks.
1084 // Note that we won't miss anything by doing this, because the outliner never
1085 // deletes functions.
1086 for (const Function &F : M) {
1087 MachineFunction *MF = MMI.getMachineFunction(F);
1088
1089 // The outliner never deletes functions. If we don't have a MF here, then we
1090 // didn't have one prior to outlining either.
1091 if (!MF)
1092 continue;
1093
1094 std::string Fname = std::string(F.getName());
1095 unsigned FnCountAfter = MF->getInstructionCount();
1096 unsigned FnCountBefore = 0;
1097
1098 // Check if the function was recorded before.
1099 auto It = FunctionToInstrCount.find(Key: Fname);
1100
1101 // Did we have a previously-recorded size? If yes, then set FnCountBefore
1102 // to that.
1103 if (It != FunctionToInstrCount.end())
1104 FnCountBefore = It->second;
1105
1106 // Compute the delta and emit a remark if there was a change.
1107 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
1108 static_cast<int64_t>(FnCountBefore);
1109 if (FnDelta == 0)
1110 continue;
1111
1112 MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
1113 MORE.emit(RemarkBuilder: [&]() {
1114 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
1115 DiagnosticLocation(), &MF->front());
1116 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
1117 << ": Function: "
1118 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
1119 << ": MI instruction count changed from "
1120 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
1121 FnCountBefore)
1122 << " to "
1123 << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
1124 FnCountAfter)
1125 << "; Delta: "
1126 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1127 return R;
1128 });
1129 }
1130}
1131
1132bool MachineOutliner::runOnModule(Module &M) {
1133 // Check if there's anything in the module. If it's empty, then there's
1134 // nothing to outline.
1135 if (M.empty())
1136 return false;
1137
1138 // Number to append to the current outlined function.
1139 unsigned OutlinedFunctionNum = 0;
1140
1141 OutlineRepeatedNum = 0;
1142 if (!doOutline(M, OutlinedFunctionNum))
1143 return false;
1144
1145 for (unsigned I = 0; I < OutlinerReruns; ++I) {
1146 OutlinedFunctionNum = 0;
1147 OutlineRepeatedNum++;
1148 if (!doOutline(M, OutlinedFunctionNum)) {
1149 LLVM_DEBUG({
1150 dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1151 << OutlinerReruns + 1 << "\n";
1152 });
1153 break;
1154 }
1155 }
1156
1157 return true;
1158}
1159
1160bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1161 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1162
1163 // If the user passed -enable-machine-outliner=always or
1164 // -enable-machine-outliner, the pass will run on all functions in the module.
1165 // Otherwise, if the target supports default outlining, it will run on all
1166 // functions deemed by the target to be worth outlining from by default. Tell
1167 // the user how the outliner is running.
1168 LLVM_DEBUG({
1169 dbgs() << "Machine Outliner: Running on ";
1170 if (RunOnAllFunctions)
1171 dbgs() << "all functions";
1172 else
1173 dbgs() << "target-default functions";
1174 dbgs() << "\n";
1175 });
1176
1177 // If the user specifies that they want to outline from linkonceodrs, set
1178 // it here.
1179 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1180 InstructionMapper Mapper;
1181
1182 // Prepare instruction mappings for the suffix tree.
1183 populateMapper(Mapper, M, MMI);
1184 std::vector<OutlinedFunction> FunctionList;
1185
1186 // Find all of the outlining candidates.
1187 findCandidates(Mapper, FunctionList);
1188
1189 // If we've requested size remarks, then collect the MI counts of every
1190 // function before outlining, and the MI counts after outlining.
1191 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1192 // the pass manager's responsibility.
1193 // This could pretty easily be placed in outline instead, but because we
1194 // really ultimately *don't* want this here, it's done like this for now
1195 // instead.
1196
1197 // Check if we want size remarks.
1198 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1199 StringMap<unsigned> FunctionToInstrCount;
1200 if (ShouldEmitSizeRemarks)
1201 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1202
1203 // Outline each of the candidates and return true if something was outlined.
1204 bool OutlinedSomething =
1205 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1206
1207 // If we outlined something, we definitely changed the MI count of the
1208 // module. If we've asked for size remarks, then output them.
1209 // FIXME: This should be in the pass manager.
1210 if (ShouldEmitSizeRemarks && OutlinedSomething)
1211 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1212
1213 LLVM_DEBUG({
1214 if (!OutlinedSomething)
1215 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1216 << " because no changes were found.\n";
1217 });
1218
1219 return OutlinedSomething;
1220}
1221