LLVM 19.0.0git
MachineOutliner.cpp
Go to the documentation of this file.
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//===----------------------------------------------------------------------===//
58#include "llvm/ADT/DenseMap.h"
59#include "llvm/ADT/SmallSet.h"
60#include "llvm/ADT/Statistic.h"
61#include "llvm/ADT/Twine.h"
66#include "llvm/CodeGen/Passes.h"
69#include "llvm/IR/DIBuilder.h"
70#include "llvm/IR/IRBuilder.h"
71#include "llvm/IR/Mangler.h"
74#include "llvm/Support/Debug.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.
107 "enable-linkonceodr-outlining", cl::Hidden,
108 cl::desc("Enable the machine outliner on linkonceodr functions"),
109 cl::init(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.
115 "machine-outliner-reruns", cl::init(0), cl::Hidden,
116 cl::desc(
117 "Number of times to rerun the outliner after the initial outline"));
118
120 "outliner-benefit-threshold", cl::init(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.
141 InstructionIntegerMap;
142
143 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
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.
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,
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(It);
186 MachineInstr &MI = *It;
187 bool WasInserted;
189 ResultIt;
190 std::tie(ResultIt, WasInserted) =
191 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
192 unsigned MINumber = ResultIt->second;
193
194 // There was an insertion.
195 if (WasInserted)
196 LegalInstrNumber++;
197
198 UnsignedVecForMBB.push_back(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("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,
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(It);
236 UnsignedVecForMBB.push_back(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
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;
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
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(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(InstrList, InstrListForMBB);
374 append_range(UnsignedVec, UnsignedVecForMBB);
375 }
376 }
377
378 InstructionMapper() {
379 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
380 // changed.
382 "DenseMapInfo<unsigned>'s empty key isn't -1!");
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 {
419 AU.setPreservesAll();
421 }
422
423 MachineOutliner() : ModulePass(ID) {
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.
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.
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([&]() {
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();
554 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
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(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");
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 CandidatesForRepeatedSeq, [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(StartIdx, StringLen, StartIt, EndIt,
643 MBB, FunctionList.size(),
644 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(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);
674 continue;
675 }
676
677 FunctionList.push_back(*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(OutlineRepeatedNum + 1) + "_";
690 FunctionName += std::to_string(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(FunctionType::get(Type::getVoidTy(C), false),
696 Function::ExternalLinkage, 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, OF.Candidates);
713
714 // Set uwtable, so we generate eh_frame.
715 UWTableKind UW = std::accumulate(
716 OF.Candidates.cbegin(), OF.Candidates.cend(), UWTableKind::None,
717 [](UWTableKind K, const outliner::Candidate &C) {
718 return std::max(K, C.getMF()->getFunction().getUWTableKind());
719 });
720 if (UW != UWTableKind::None)
721 F->setUWTableKind(UW);
722
723 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
724 IRBuilder<> Builder(EntryBB);
725 Builder.CreateRetVoid();
726
727 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
729 MF.setIsOutlined(true);
731
732 // Insert the new function into the module.
733 MF.insert(MF.begin(), &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(0).getCFIIndex();
746 MCCFIInstruction CFI = Instrs[CFIIndex];
747 BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))
748 .addCFIIndex(MF.addFrameInst(CFI));
749 } else {
750 MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
751 NewMI->dropMemRefs(MF);
752 NewMI->setDebugLoc(DL);
753 MBB.insert(MBB.end(), NewMI);
754 }
755 }
756
757 // Set normal properties for a late MachineFunction.
758 MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
759 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
760 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
761 MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
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(OutlineBB);
773 for (const MachineInstr &MI :
774 reverse(make_range(Cand.begin(), 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, 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(MangledNameStream, F, false);
798
799 DISubprogram *OutlinedSP = DB.createFunction(
800 Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
801 Unit /* File */,
802 0 /* Line 0 is reserved for compiler-generated code. */,
803 DB.createSubroutineType(
804 DB.getOrCreateTypeArray(std::nullopt)), /* void type */
805 0, /* Line 0 is reserved for compiler-generated code. */
806 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
807 /* Outlined code is optimized code by definition. */
808 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
809
810 // Don't add any new variables to the subprogram.
811 DB.finalizeSubprogram(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(FunctionList,
833 [](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(OF.Candidates, [&UnsignedVecBegin](Candidate &C) {
848 return std::any_of(UnsignedVecBegin + C.getStartIdx(),
849 UnsignedVecBegin + C.getEndIdx() + 1, [](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.
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, 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(C.end());
888
889 // Insert the call.
890 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *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.
909 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.
921 Iter = EndIt.getReverse(),
922 Last = std::next(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(MOP.getReg());
934 if (UseRegs.count(MOP.getReg()) &&
935 !InstrUseRegs.count(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(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(MOP.getReg());
943 InstrUseRegs.insert(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 MachineOperand::CreateReg(I, true, /* isDef = true */
954 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 MachineOperand::CreateReg(I, false, /* isDef = false */
960 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(std::next(StartIt), std::next(EndIt));
967
968 // Keep track of what we removed by marking them all as -1.
969 for (unsigned &I : make_range(UnsignedVecBegin + C.getStartIdx(),
970 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("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.
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
1008 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*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, 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);
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) {
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) {
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(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
1105 MORE.emit([&]() {
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 "
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}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
AMDGPU promote alloca to vector or false DEBUG_TYPE to vector
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
std::string Name
const HexagonInstrInfo * TII
static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)
Get the subprogram if it exists for one of the outlined regions.
Definition: IROutliner.cpp:620
IRTranslator LLVM IR MI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
Return the first found DebugLoc that has a DILocation, given a range of instructions.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
static cl::opt< unsigned > OutlinerBenefitThreshold("outliner-benefit-threshold", cl::init(1), cl::Hidden, cl::desc("The minimum size in bytes before an outlining candidate is accepted"))
static cl::opt< unsigned > OutlinerReruns("machine-outliner-reruns", cl::init(0), cl::Hidden, cl::desc("Number of times to rerun the outliner after the initial outline"))
Number of times to re-run the outliner.
#define DEBUG_TYPE
static cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))
Contains all data structures shared between the outliner implemented in MachineOutliner....
unsigned const TargetRegisterInfo * TRI
static Function * createOutlinedFunction(OpenMPIRBuilder &OMPBuilder, IRBuilderBase &Builder, StringRef FuncName, SmallVectorImpl< Value * > &Inputs, OpenMPIRBuilder::TargetBodyGenCallbackTy &CBFunc, OpenMPIRBuilder::TargetGenArgAccessorsCallbackTy &ArgAccessorFuncCB)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Value * RHS
Value * LHS
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
This class represents a function call, abstracting a target machine's calling convention.
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Subprogram description.
A debug info location.
Definition: DebugLoc.h:33
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:162
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:59
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2644
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
MachineFunctionProperties & set(Property P)
bool hasProperty(Property P) const
MachineFunctionProperties & reset(Property P)
unsigned getInstructionCount() const
Return the number of MachineInstrs in this MachineFunction.
unsigned addFrameInst(const MCCFIInstruction &Inst)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
const std::vector< MCCFIInstruction > & getFrameInstructions() const
Returns a reference to a list of cfi instructions in the function's prologue.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MachineFunctionProperties & getProperties() const
Get the function properties.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
const MachineBasicBlock & front() const
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void insert(iterator MBBI, MachineBasicBlock *MBB)
const MachineInstrBuilder & addCFIIndex(unsigned CFIIndex) const
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:329
void dropMemRefs(MachineFunction &MF)
Clear this MachineInstr's memory reference descriptor list.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
This class contains meta information specific to a module.
MachineFunction & getOrCreateMachineFunction(Function &F)
Returns the MachineFunction constructed for the IR function F.
MachineFunction * getMachineFunction(const Function &F) const
Returns the MachineFunction associated to IR function F if there is one, otherwise nullptr.
MachineOperand class - Representation of each machine instruction operand.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
Diagnostic information for optimization analysis remarks.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
void freezeReservedRegs()
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable's name.
Definition: Mangler.cpp:119
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool erase(const T &V)
Definition: SmallSet.h:207
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:128
iterator end()
Definition: StringMap.h:221
iterator find(StringRef Key)
Definition: StringMap.h:234
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:222
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
constexpr size_t size() const
size - Get the string size.
Definition: StringRef.h:137
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
static Type * getVoidTy(LLVMContext &C)
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:660
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:2004
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2082
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
UWTableKind
Definition: CodeGen.h:120
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
void initializeMachineOutlinerPass(PassRegistry &)
ModulePass * createMachineOutlinerPass(bool RunOnAllFunctions=true)
This pass performs outlining on machine instructions directly before printing assembly.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1758
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2060
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define MORE()
Definition: regcomp.c:252
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:50
Used in the streaming interface as the general argument type.
A repeated substring in the tree.
Definition: SuffixTree.h:46
An individual sequence of instructions to be replaced with a call to an outlined function.
MachineFunction * getMF() const
The information necessary to create an outlined function for some class of candidate.
unsigned getBenefit() const
Return the number of instructions that would be saved by outlining this function.
MachineFunction * MF
The actual outlined function created.
unsigned getNumInstrs() const
Return the number of instructions in this sequence.
unsigned getOccurrenceCount() const
Return the number of candidates for this OutlinedFunction.
std::vector< Candidate > Candidates