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

source code of llvm/lib/CodeGen/MachineOutliner.cpp