LLVM 17.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 I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
739 ++I) {
740 if (I->isDebugInstr())
741 continue;
742
743 // Don't keep debug information for outlined instructions.
744 auto DL = DebugLoc();
745 if (I->isCFIInstruction()) {
746 unsigned CFIIndex = I->getOperand(0).getCFIIndex();
747 MCCFIInstruction CFI = Instrs[CFIIndex];
748 BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))
749 .addCFIIndex(MF.addFrameInst(CFI));
750 } else {
751 MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
752 NewMI->dropMemRefs(MF);
753 NewMI->setDebugLoc(DL);
754 MBB.insert(MBB.end(), NewMI);
755 }
756 }
757
758 // Set normal properties for a late MachineFunction.
759 MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
760 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
761 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
762 MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
764
765 // Compute live-in set for outlined fn
766 const MachineRegisterInfo &MRI = MF.getRegInfo();
767 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
768 LivePhysRegs LiveIns(TRI);
769 for (auto &Cand : OF.Candidates) {
770 // Figure out live-ins at the first instruction.
771 MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
772 LivePhysRegs CandLiveIns(TRI);
773 CandLiveIns.addLiveOuts(OutlineBB);
774 for (const MachineInstr &MI :
775 reverse(make_range(Cand.front(), OutlineBB.end())))
776 CandLiveIns.stepBackward(MI);
777
778 // The live-in set for the outlined function is the union of the live-ins
779 // from all the outlining points.
780 for (MCPhysReg Reg : CandLiveIns)
781 LiveIns.addReg(Reg);
782 }
783 addLiveIns(MBB, LiveIns);
784
785 TII.buildOutlinedFrame(MBB, MF, OF);
786
787 // If there's a DISubprogram associated with this outlined function, then
788 // emit debug info for the outlined function.
789 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
790 // We have a DISubprogram. Get its DICompileUnit.
791 DICompileUnit *CU = SP->getUnit();
792 DIBuilder DB(M, true, CU);
793 DIFile *Unit = SP->getFile();
794 Mangler Mg;
795 // Get the mangled name of the function for the linkage name.
796 std::string Dummy;
797 raw_string_ostream MangledNameStream(Dummy);
798 Mg.getNameWithPrefix(MangledNameStream, F, false);
799
800 DISubprogram *OutlinedSP = DB.createFunction(
801 Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
802 Unit /* File */,
803 0 /* Line 0 is reserved for compiler-generated code. */,
804 DB.createSubroutineType(
805 DB.getOrCreateTypeArray(std::nullopt)), /* void type */
806 0, /* Line 0 is reserved for compiler-generated code. */
807 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
808 /* Outlined code is optimized code by definition. */
809 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
810
811 // Don't add any new variables to the subprogram.
812 DB.finalizeSubprogram(OutlinedSP);
813
814 // Attach subprogram to the function.
815 F->setSubprogram(OutlinedSP);
816 // We're done with the DIBuilder.
817 DB.finalize();
818 }
819
820 return &MF;
821}
822
823bool MachineOutliner::outline(Module &M,
824 std::vector<OutlinedFunction> &FunctionList,
825 InstructionMapper &Mapper,
826 unsigned &OutlinedFunctionNum) {
827 LLVM_DEBUG(dbgs() << "*** Outlining ***\n");
828 LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size()
829 << "\n");
830 bool OutlinedSomething = false;
831
832 // Sort by benefit. The most beneficial functions should be outlined first.
833 stable_sort(FunctionList,
834 [](const OutlinedFunction &LHS, const OutlinedFunction &RHS) {
835 return LHS.getBenefit() > RHS.getBenefit();
836 });
837
838 // Walk over each function, outlining them as we go along. Functions are
839 // outlined greedily, based off the sort above.
840 auto *UnsignedVecBegin = Mapper.UnsignedVec.begin();
841 LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n");
842 for (OutlinedFunction &OF : FunctionList) {
843#ifndef NDEBUG
844 auto NumCandidatesBefore = OF.Candidates.size();
845#endif
846 // If we outlined something that overlapped with a candidate in a previous
847 // step, then we can't outline from it.
848 erase_if(OF.Candidates, [&UnsignedVecBegin](Candidate &C) {
849 return std::any_of(UnsignedVecBegin + C.getStartIdx(),
850 UnsignedVecBegin + C.getEndIdx() + 1, [](unsigned I) {
851 return I == static_cast<unsigned>(-1);
852 });
853 });
854
855#ifndef NDEBUG
856 auto NumCandidatesAfter = OF.Candidates.size();
857 LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter
858 << "/" << NumCandidatesBefore << " candidates\n");
859#endif
860
861 // If we made it unbeneficial to outline this function, skip it.
863 LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF.getBenefit()
864 << " B) < threshold (" << OutlinerBenefitThreshold
865 << " B)\n");
866 continue;
867 }
868
869 LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF.getBenefit()
870 << " B) > threshold (" << OutlinerBenefitThreshold
871 << " B)\n");
872
873 // It's beneficial. Create the function and outline its sequence's
874 // occurrences.
875 OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
876 emitOutlinedFunctionRemark(OF);
877 FunctionsCreated++;
878 OutlinedFunctionNum++; // Created a function, move to the next name.
879 MachineFunction *MF = OF.MF;
880 const TargetSubtargetInfo &STI = MF->getSubtarget();
881 const TargetInstrInfo &TII = *STI.getInstrInfo();
882
883 // Replace occurrences of the sequence with calls to the new function.
884 LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n");
885 for (Candidate &C : OF.Candidates) {
886 MachineBasicBlock &MBB = *C.getMBB();
887 MachineBasicBlock::iterator StartIt = C.front();
888 MachineBasicBlock::iterator EndIt = C.back();
889
890 // Insert the call.
891 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
892// Insert the call.
893#ifndef NDEBUG
894 auto MBBBeingOutlinedFromName =
895 MBB.getName().empty() ? "<unknown>" : MBB.getName().str();
896 auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty()
897 ? "<unknown>"
898 : MBB.getParent()->getName().str();
899 LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in "
900 << MFBeingOutlinedFromName << ":"
901 << MBBBeingOutlinedFromName << "\n");
902 LLVM_DEBUG(dbgs() << " .. " << *CallInst);
903#endif
904
905 // If the caller tracks liveness, then we need to make sure that
906 // anything we outline doesn't break liveness assumptions. The outlined
907 // functions themselves currently don't track liveness, but we should
908 // make sure that the ranges we yank things out of aren't wrong.
910 MachineFunctionProperties::Property::TracksLiveness)) {
911 // The following code is to add implicit def operands to the call
912 // instruction. It also updates call site information for moved
913 // code.
914 SmallSet<Register, 2> UseRegs, DefRegs;
915 // Copy over the defs in the outlined range.
916 // First inst in outlined range <-- Anything that's defined in this
917 // ... .. range has to be added as an
918 // implicit Last inst in outlined range <-- def to the call
919 // instruction. Also remove call site information for outlined block
920 // of code. The exposed uses need to be copied in the outlined range.
922 Iter = EndIt.getReverse(),
923 Last = std::next(CallInst.getReverse());
924 Iter != Last; Iter++) {
925 MachineInstr *MI = &*Iter;
926 SmallSet<Register, 2> InstrUseRegs;
927 for (MachineOperand &MOP : MI->operands()) {
928 // Skip over anything that isn't a register.
929 if (!MOP.isReg())
930 continue;
931
932 if (MOP.isDef()) {
933 // Introduce DefRegs set to skip the redundant register.
934 DefRegs.insert(MOP.getReg());
935 if (UseRegs.count(MOP.getReg()) &&
936 !InstrUseRegs.count(MOP.getReg()))
937 // Since the regiester is modeled as defined,
938 // it is not necessary to be put in use register set.
939 UseRegs.erase(MOP.getReg());
940 } else if (!MOP.isUndef()) {
941 // Any register which is not undefined should
942 // be put in the use register set.
943 UseRegs.insert(MOP.getReg());
944 InstrUseRegs.insert(MOP.getReg());
945 }
946 }
947 if (MI->isCandidateForCallSiteEntry())
948 MI->getMF()->eraseCallSiteInfo(MI);
949 }
950
951 for (const Register &I : DefRegs)
952 // If it's a def, add it to the call instruction.
953 CallInst->addOperand(
954 MachineOperand::CreateReg(I, true, /* isDef = true */
955 true /* isImp = true */));
956
957 for (const Register &I : UseRegs)
958 // If it's a exposed use, add it to the call instruction.
959 CallInst->addOperand(
960 MachineOperand::CreateReg(I, false, /* isDef = false */
961 true /* isImp = true */));
962 }
963
964 // Erase from the point after where the call was inserted up to, and
965 // including, the final instruction in the sequence.
966 // Erase needs one past the end, so we need std::next there too.
967 MBB.erase(std::next(StartIt), std::next(EndIt));
968
969 // Keep track of what we removed by marking them all as -1.
970 for (unsigned &I : make_range(UnsignedVecBegin + C.getStartIdx(),
971 UnsignedVecBegin + C.getEndIdx() + 1))
972 I = static_cast<unsigned>(-1);
973 OutlinedSomething = true;
974
975 // Statistics.
976 NumOutlined++;
977 }
978 }
979
980 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
981 return OutlinedSomething;
982}
983
984void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
985 MachineModuleInfo &MMI) {
986 // Build instruction mappings for each function in the module. Start by
987 // iterating over each Function in M.
988 LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n");
989 for (Function &F : M) {
990 LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n");
991
992 if (F.hasFnAttribute("nooutline")) {
993 LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n");
994 continue;
995 }
996
997 // There's something in F. Check if it has a MachineFunction associated with
998 // it.
1000
1001 // If it doesn't, then there's nothing to outline from. Move to the next
1002 // Function.
1003 if (!MF) {
1004 LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n");
1005 continue;
1006 }
1007
1009 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF)) {
1010 LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from "
1011 "function by default\n");
1012 continue;
1013 }
1014
1015 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1016 // If it isn't, then move on to the next Function in the module.
1017 if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) {
1018 LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName()
1019 << ": unsafe to outline from\n");
1020 continue;
1021 }
1022
1023 // We have a function suitable for outlining. Iterate over every
1024 // MachineBasicBlock in MF and try to map its instructions to a list of
1025 // unsigned integers.
1026 const unsigned MinMBBSize = 2;
1027
1028 for (MachineBasicBlock &MBB : *MF) {
1029 LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n");
1030 // If there isn't anything in MBB, then there's no point in outlining from
1031 // it.
1032 // If there are fewer than 2 instructions in the MBB, then it can't ever
1033 // contain something worth outlining.
1034 // FIXME: This should be based off of the maximum size in B of an outlined
1035 // call versus the size in B of the MBB.
1036 if (MBB.size() < MinMBBSize) {
1037 LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of "
1038 << MinMBBSize << "\n");
1039 continue;
1040 }
1041
1042 // Check if MBB could be the target of an indirect branch. If it is, then
1043 // we don't want to outline from it.
1044 if (MBB.hasAddressTaken()) {
1045 LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n");
1046 continue;
1047 }
1048
1049 // MBB is suitable for outlining. Map it to a list of unsigneds.
1050 Mapper.convertToUnsignedVec(MBB, *TII);
1051 }
1052 }
1053 // Statistics.
1054 UnsignedVecSize = Mapper.UnsignedVec.size();
1055}
1056
1057void MachineOutliner::initSizeRemarkInfo(
1058 const Module &M, const MachineModuleInfo &MMI,
1059 StringMap<unsigned> &FunctionToInstrCount) {
1060 // Collect instruction counts for every function. We'll use this to emit
1061 // per-function size remarks later.
1062 for (const Function &F : M) {
1064
1065 // We only care about MI counts here. If there's no MachineFunction at this
1066 // point, then there won't be after the outliner runs, so let's move on.
1067 if (!MF)
1068 continue;
1069 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
1070 }
1071}
1072
1073void MachineOutliner::emitInstrCountChangedRemark(
1074 const Module &M, const MachineModuleInfo &MMI,
1075 const StringMap<unsigned> &FunctionToInstrCount) {
1076 // Iterate over each function in the module and emit remarks.
1077 // Note that we won't miss anything by doing this, because the outliner never
1078 // deletes functions.
1079 for (const Function &F : M) {
1081
1082 // The outliner never deletes functions. If we don't have a MF here, then we
1083 // didn't have one prior to outlining either.
1084 if (!MF)
1085 continue;
1086
1087 std::string Fname = std::string(F.getName());
1088 unsigned FnCountAfter = MF->getInstructionCount();
1089 unsigned FnCountBefore = 0;
1090
1091 // Check if the function was recorded before.
1092 auto It = FunctionToInstrCount.find(Fname);
1093
1094 // Did we have a previously-recorded size? If yes, then set FnCountBefore
1095 // to that.
1096 if (It != FunctionToInstrCount.end())
1097 FnCountBefore = It->second;
1098
1099 // Compute the delta and emit a remark if there was a change.
1100 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
1101 static_cast<int64_t>(FnCountBefore);
1102 if (FnDelta == 0)
1103 continue;
1104
1106 MORE.emit([&]() {
1107 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
1108 DiagnosticLocation(), &MF->front());
1109 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
1110 << ": Function: "
1111 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
1112 << ": MI instruction count changed from "
1113 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
1114 FnCountBefore)
1115 << " to "
1117 FnCountAfter)
1118 << "; Delta: "
1119 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1120 return R;
1121 });
1122 }
1123}
1124
1125bool MachineOutliner::runOnModule(Module &M) {
1126 // Check if there's anything in the module. If it's empty, then there's
1127 // nothing to outline.
1128 if (M.empty())
1129 return false;
1130
1131 // Number to append to the current outlined function.
1132 unsigned OutlinedFunctionNum = 0;
1133
1134 OutlineRepeatedNum = 0;
1135 if (!doOutline(M, OutlinedFunctionNum))
1136 return false;
1137
1138 for (unsigned I = 0; I < OutlinerReruns; ++I) {
1139 OutlinedFunctionNum = 0;
1140 OutlineRepeatedNum++;
1141 if (!doOutline(M, OutlinedFunctionNum)) {
1142 LLVM_DEBUG({
1143 dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1144 << OutlinerReruns + 1 << "\n";
1145 });
1146 break;
1147 }
1148 }
1149
1150 return true;
1151}
1152
1153bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1154 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1155
1156 // If the user passed -enable-machine-outliner=always or
1157 // -enable-machine-outliner, the pass will run on all functions in the module.
1158 // Otherwise, if the target supports default outlining, it will run on all
1159 // functions deemed by the target to be worth outlining from by default. Tell
1160 // the user how the outliner is running.
1161 LLVM_DEBUG({
1162 dbgs() << "Machine Outliner: Running on ";
1163 if (RunOnAllFunctions)
1164 dbgs() << "all functions";
1165 else
1166 dbgs() << "target-default functions";
1167 dbgs() << "\n";
1168 });
1169
1170 // If the user specifies that they want to outline from linkonceodrs, set
1171 // it here.
1172 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1173 InstructionMapper Mapper;
1174
1175 // Prepare instruction mappings for the suffix tree.
1176 populateMapper(Mapper, M, MMI);
1177 std::vector<OutlinedFunction> FunctionList;
1178
1179 // Find all of the outlining candidates.
1180 findCandidates(Mapper, FunctionList);
1181
1182 // If we've requested size remarks, then collect the MI counts of every
1183 // function before outlining, and the MI counts after outlining.
1184 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1185 // the pass manager's responsibility.
1186 // This could pretty easily be placed in outline instead, but because we
1187 // really ultimately *don't* want this here, it's done like this for now
1188 // instead.
1189
1190 // Check if we want size remarks.
1191 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1192 StringMap<unsigned> FunctionToInstrCount;
1193 if (ShouldEmitSizeRemarks)
1194 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1195
1196 // Outline each of the candidates and return true if something was outlined.
1197 bool OutlinedSomething =
1198 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1199
1200 // If we outlined something, we definitely changed the MI count of the
1201 // module. If we've asked for size remarks, then output them.
1202 // FIXME: This should be in the pass manager.
1203 if (ShouldEmitSizeRemarks && OutlinedSomething)
1204 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1205
1206 LLVM_DEBUG({
1207 if (!OutlinedSomething)
1208 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1209 << " because no changes were found.\n";
1210 });
1211
1212 return OutlinedSomething;
1213}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
assume Assume Builder
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#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:621
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)
#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
@ Flags
Definition: TextStubV5.cpp:93
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:56
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
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:136
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2564
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 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.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
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
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:68
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
void dropMemRefs(MachineFunction &MF)
Clear this MachineInstr's memory reference descriptor list.
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(const MachineFunction &)
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:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:111
iterator end()
Definition: StringMap.h:204
iterator find(StringRef Key)
Definition: StringMap.h:217
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:642
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:445
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:2063
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 a range to a container.
Definition: STLExtras.h:2129
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
UWTableKind
Definition: CodeGen.h:121
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:145
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:1846
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:2113
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
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:51
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.
MachineBasicBlock::iterator & front()
MachineFunction * getMF() const
MachineBasicBlock::iterator & back()
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