LLVM  12.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"
72 #include "llvm/InitializePasses.h"
74 #include "llvm/Support/Debug.h"
77 #include <functional>
78 #include <tuple>
79 #include <vector>
80 
81 #define DEBUG_TYPE "machine-outliner"
82 
83 using namespace llvm;
84 using namespace ore;
85 using namespace outliner;
86 
87 STATISTIC(NumOutlined, "Number of candidates outlined");
88 STATISTIC(FunctionsCreated, "Number of functions created");
89 
90 // Set to true if the user wants the outliner to run on linkonceodr linkage
91 // functions. This is false by default because the linker can dedupe linkonceodr
92 // functions. Since the outliner is confined to a single module (modulo LTO),
93 // this is off by default. It should, however, be the default behaviour in
94 // LTO.
96  "enable-linkonceodr-outlining", cl::Hidden,
97  cl::desc("Enable the machine outliner on linkonceodr functions"),
98  cl::init(false));
99 
100 /// Number of times to re-run the outliner. This is not the total number of runs
101 /// as the outliner will run at least one time. The default value is set to 0,
102 /// meaning the outliner will run one time and rerun zero times after that.
104  "machine-outliner-reruns", cl::init(0), cl::Hidden,
105  cl::desc(
106  "Number of times to rerun the outliner after the initial outline"));
107 
108 namespace {
109 
110 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
111 struct InstructionMapper {
112 
113  /// The next available integer to assign to a \p MachineInstr that
114  /// cannot be outlined.
115  ///
116  /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
117  unsigned IllegalInstrNumber = -3;
118 
119  /// The next available integer to assign to a \p MachineInstr that can
120  /// be outlined.
121  unsigned LegalInstrNumber = 0;
122 
123  /// Correspondence from \p MachineInstrs to unsigned integers.
125  InstructionIntegerMap;
126 
127  /// Correspondence between \p MachineBasicBlocks and target-defined flags.
129 
130  /// The vector of unsigned integers that the module is mapped to.
131  std::vector<unsigned> UnsignedVec;
132 
133  /// Stores the location of the instruction associated with the integer
134  /// at index i in \p UnsignedVec for each index i.
135  std::vector<MachineBasicBlock::iterator> InstrList;
136 
137  // Set if we added an illegal number in the previous step.
138  // Since each illegal number is unique, we only need one of them between
139  // each range of legal numbers. This lets us make sure we don't add more
140  // than one illegal number per range.
141  bool AddedIllegalLastTime = false;
142 
143  /// Maps \p *It to a legal integer.
144  ///
145  /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
146  /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
147  ///
148  /// \returns The integer that \p *It was mapped to.
149  unsigned mapToLegalUnsigned(
150  MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
151  bool &HaveLegalRange, unsigned &NumLegalInBlock,
152  std::vector<unsigned> &UnsignedVecForMBB,
153  std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
154  // We added something legal, so we should unset the AddedLegalLastTime
155  // flag.
156  AddedIllegalLastTime = false;
157 
158  // If we have at least two adjacent legal instructions (which may have
159  // invisible instructions in between), remember that.
160  if (CanOutlineWithPrevInstr)
161  HaveLegalRange = true;
162  CanOutlineWithPrevInstr = true;
163 
164  // Keep track of the number of legal instructions we insert.
165  NumLegalInBlock++;
166 
167  // Get the integer for this instruction or give it the current
168  // LegalInstrNumber.
169  InstrListForMBB.push_back(It);
170  MachineInstr &MI = *It;
171  bool WasInserted;
173  ResultIt;
174  std::tie(ResultIt, WasInserted) =
175  InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
176  unsigned MINumber = ResultIt->second;
177 
178  // There was an insertion.
179  if (WasInserted)
180  LegalInstrNumber++;
181 
182  UnsignedVecForMBB.push_back(MINumber);
183 
184  // Make sure we don't overflow or use any integers reserved by the DenseMap.
185  if (LegalInstrNumber >= IllegalInstrNumber)
186  report_fatal_error("Instruction mapping overflow!");
187 
188  assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
189  "Tried to assign DenseMap tombstone or empty key to instruction.");
190  assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
191  "Tried to assign DenseMap tombstone or empty key to instruction.");
192 
193  return MINumber;
194  }
195 
196  /// Maps \p *It to an illegal integer.
197  ///
198  /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
199  /// IllegalInstrNumber.
200  ///
201  /// \returns The integer that \p *It was mapped to.
202  unsigned mapToIllegalUnsigned(
203  MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
204  std::vector<unsigned> &UnsignedVecForMBB,
205  std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
206  // Can't outline an illegal instruction. Set the flag.
207  CanOutlineWithPrevInstr = false;
208 
209  // Only add one illegal number per range of legal numbers.
210  if (AddedIllegalLastTime)
211  return IllegalInstrNumber;
212 
213  // Remember that we added an illegal number last time.
214  AddedIllegalLastTime = true;
215  unsigned MINumber = IllegalInstrNumber;
216 
217  InstrListForMBB.push_back(It);
218  UnsignedVecForMBB.push_back(IllegalInstrNumber);
219  IllegalInstrNumber--;
220 
221  assert(LegalInstrNumber < IllegalInstrNumber &&
222  "Instruction mapping overflow!");
223 
224  assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
225  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
226 
227  assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
228  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
229 
230  return MINumber;
231  }
232 
233  /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
234  /// and appends it to \p UnsignedVec and \p InstrList.
235  ///
236  /// Two instructions are assigned the same integer if they are identical.
237  /// If an instruction is deemed unsafe to outline, then it will be assigned an
238  /// unique integer. The resulting mapping is placed into a suffix tree and
239  /// queried for candidates.
240  ///
241  /// \param MBB The \p MachineBasicBlock to be translated into integers.
242  /// \param TII \p TargetInstrInfo for the function.
243  void convertToUnsignedVec(MachineBasicBlock &MBB,
244  const TargetInstrInfo &TII) {
245  unsigned Flags = 0;
246 
247  // Don't even map in this case.
248  if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
249  return;
250 
251  // Store info for the MBB for later outlining.
252  MBBFlagsMap[&MBB] = Flags;
253 
255 
256  // The number of instructions in this block that will be considered for
257  // outlining.
258  unsigned NumLegalInBlock = 0;
259 
260  // True if we have at least two legal instructions which aren't separated
261  // by an illegal instruction.
262  bool HaveLegalRange = false;
263 
264  // True if we can perform outlining given the last mapped (non-invisible)
265  // instruction. This lets us know if we have a legal range.
266  bool CanOutlineWithPrevInstr = false;
267 
268  // FIXME: Should this all just be handled in the target, rather than using
269  // repeated calls to getOutliningType?
270  std::vector<unsigned> UnsignedVecForMBB;
271  std::vector<MachineBasicBlock::iterator> InstrListForMBB;
272 
273  for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; ++It) {
274  // Keep track of where this instruction is in the module.
275  switch (TII.getOutliningType(It, Flags)) {
276  case InstrType::Illegal:
277  mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
278  InstrListForMBB);
279  break;
280 
281  case InstrType::Legal:
282  mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
283  NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
284  break;
285 
287  mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
288  NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
289  // The instruction also acts as a terminator, so we have to record that
290  // in the string.
291  mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
292  InstrListForMBB);
293  break;
294 
296  // Normally this is set by mapTo(Blah)Unsigned, but we just want to
297  // skip this instruction. So, unset the flag here.
298  AddedIllegalLastTime = false;
299  break;
300  }
301  }
302 
303  // Are there enough legal instructions in the block for outlining to be
304  // possible?
305  if (HaveLegalRange) {
306  // After we're done every insertion, uniquely terminate this part of the
307  // "string". This makes sure we won't match across basic block or function
308  // boundaries since the "end" is encoded uniquely and thus appears in no
309  // repeated substring.
310  mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
311  InstrListForMBB);
312  InstrList.insert(InstrList.end(), InstrListForMBB.begin(),
313  InstrListForMBB.end());
314  UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForMBB.begin(),
315  UnsignedVecForMBB.end());
316  }
317  }
318 
319  InstructionMapper() {
320  // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
321  // changed.
322  assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
323  "DenseMapInfo<unsigned>'s empty key isn't -1!");
325  "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
326  }
327 };
328 
329 /// An interprocedural pass which finds repeated sequences of
330 /// instructions and replaces them with calls to functions.
331 ///
332 /// Each instruction is mapped to an unsigned integer and placed in a string.
333 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
334 /// is then repeatedly queried for repeated sequences of instructions. Each
335 /// non-overlapping repeated sequence is then placed in its own
336 /// \p MachineFunction and each instance is then replaced with a call to that
337 /// function.
338 struct MachineOutliner : public ModulePass {
339 
340  static char ID;
341 
342  /// Set to true if the outliner should consider functions with
343  /// linkonceodr linkage.
344  bool OutlineFromLinkOnceODRs = false;
345 
346  /// The current repeat number of machine outlining.
347  unsigned OutlineRepeatedNum = 0;
348 
349  /// Set to true if the outliner should run on all functions in the module
350  /// considered safe for outlining.
351  /// Set to true by default for compatibility with llc's -run-pass option.
352  /// Set when the pass is constructed in TargetPassConfig.
353  bool RunOnAllFunctions = true;
354 
355  StringRef getPassName() const override { return "Machine Outliner"; }
356 
357  void getAnalysisUsage(AnalysisUsage &AU) const override {
360  AU.setPreservesAll();
362  }
363 
364  MachineOutliner() : ModulePass(ID) {
366  }
367 
368  /// Remark output explaining that not outlining a set of candidates would be
369  /// better than outlining that set.
370  void emitNotOutliningCheaperRemark(
371  unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
372  OutlinedFunction &OF);
373 
374  /// Remark output explaining that a function was outlined.
375  void emitOutlinedFunctionRemark(OutlinedFunction &OF);
376 
377  /// Find all repeated substrings that satisfy the outlining cost model by
378  /// constructing a suffix tree.
379  ///
380  /// If a substring appears at least twice, then it must be represented by
381  /// an internal node which appears in at least two suffixes. Each suffix
382  /// is represented by a leaf node. To do this, we visit each internal node
383  /// in the tree, using the leaf children of each internal node. If an
384  /// internal node represents a beneficial substring, then we use each of
385  /// its leaf children to find the locations of its substring.
386  ///
387  /// \param Mapper Contains outlining mapping information.
388  /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
389  /// each type of candidate.
390  void findCandidates(InstructionMapper &Mapper,
391  std::vector<OutlinedFunction> &FunctionList);
392 
393  /// Replace the sequences of instructions represented by \p OutlinedFunctions
394  /// with calls to functions.
395  ///
396  /// \param M The module we are outlining from.
397  /// \param FunctionList A list of functions to be inserted into the module.
398  /// \param Mapper Contains the instruction mappings for the module.
399  bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
400  InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
401 
402  /// Creates a function for \p OF and inserts it into the module.
403  MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
404  InstructionMapper &Mapper,
405  unsigned Name);
406 
407  /// Calls 'doOutline()' 1 + OutlinerReruns times.
408  bool runOnModule(Module &M) override;
409 
410  /// Construct a suffix tree on the instructions in \p M and outline repeated
411  /// strings from that tree.
412  bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
413 
414  /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
415  /// function for remark emission.
416  DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
417  for (const Candidate &C : OF.Candidates)
418  if (MachineFunction *MF = C.getMF())
419  if (DISubprogram *SP = MF->getFunction().getSubprogram())
420  return SP;
421  return nullptr;
422  }
423 
424  /// Populate and \p InstructionMapper with instruction-to-integer mappings.
425  /// These are used to construct a suffix tree.
426  void populateMapper(InstructionMapper &Mapper, Module &M,
427  MachineModuleInfo &MMI);
428 
429  /// Initialize information necessary to output a size remark.
430  /// FIXME: This should be handled by the pass manager, not the outliner.
431  /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
432  /// pass manager.
433  void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI,
434  StringMap<unsigned> &FunctionToInstrCount);
435 
436  /// Emit the remark.
437  // FIXME: This should be handled by the pass manager, not the outliner.
438  void
439  emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
440  const StringMap<unsigned> &FunctionToInstrCount);
441 };
442 } // Anonymous namespace.
443 
444 char MachineOutliner::ID = 0;
445 
446 namespace llvm {
447 ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
448  MachineOutliner *OL = new MachineOutliner();
449  OL->RunOnAllFunctions = RunOnAllFunctions;
450  return OL;
451 }
452 
453 } // namespace llvm
454 
455 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
456  false)
457 
458 void MachineOutliner::emitNotOutliningCheaperRemark(
459  unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
460  OutlinedFunction &OF) {
461  // FIXME: Right now, we arbitrarily choose some Candidate from the
462  // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
463  // We should probably sort these by function name or something to make sure
464  // the remarks are stable.
465  Candidate &C = CandidatesForRepeatedSeq.front();
466  MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
467  MORE.emit([&]() {
468  MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
469  C.front()->getDebugLoc(), C.getMBB());
470  R << "Did not outline " << NV("Length", StringLen) << " instructions"
471  << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
472  << " locations."
473  << " Bytes from outlining all occurrences ("
474  << NV("OutliningCost", OF.getOutliningCost()) << ")"
475  << " >= Unoutlined instruction bytes ("
476  << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
477  << " (Also found at: ";
478 
479  // Tell the user the other places the candidate was found.
480  for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
481  R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
482  CandidatesForRepeatedSeq[i].front()->getDebugLoc());
483  if (i != e - 1)
484  R << ", ";
485  }
486 
487  R << ")";
488  return R;
489  });
490 }
491 
492 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
493  MachineBasicBlock *MBB = &*OF.MF->begin();
494  MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
495  MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
496  MBB->findDebugLoc(MBB->begin()), MBB);
497  R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
498  << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
499  << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
500  << " locations. "
501  << "(Found at: ";
502 
503  // Tell the user the other places the candidate was found.
504  for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
505 
506  R << NV((Twine("StartLoc") + Twine(i)).str(),
507  OF.Candidates[i].front()->getDebugLoc());
508  if (i != e - 1)
509  R << ", ";
510  }
511 
512  R << ")";
513 
514  MORE.emit(R);
515 }
516 
517 void MachineOutliner::findCandidates(
518  InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
519  FunctionList.clear();
520  SuffixTree ST(Mapper.UnsignedVec);
521 
522  // First, find all of the repeated substrings in the tree of minimum length
523  // 2.
524  std::vector<Candidate> CandidatesForRepeatedSeq;
525  for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
526  CandidatesForRepeatedSeq.clear();
528  unsigned StringLen = RS.Length;
529  for (const unsigned &StartIdx : RS.StartIndices) {
530  unsigned EndIdx = StartIdx + StringLen - 1;
531  // Trick: Discard some candidates that would be incompatible with the
532  // ones we've already found for this sequence. This will save us some
533  // work in candidate selection.
534  //
535  // If two candidates overlap, then we can't outline them both. This
536  // happens when we have candidates that look like, say
537  //
538  // AA (where each "A" is an instruction).
539  //
540  // We might have some portion of the module that looks like this:
541  // AAAAAA (6 A's)
542  //
543  // In this case, there are 5 different copies of "AA" in this range, but
544  // at most 3 can be outlined. If only outlining 3 of these is going to
545  // be unbeneficial, then we ought to not bother.
546  //
547  // Note that two things DON'T overlap when they look like this:
548  // start1...end1 .... start2...end2
549  // That is, one must either
550  // * End before the other starts
551  // * Start after the other ends
552  if (std::all_of(
553  CandidatesForRepeatedSeq.begin(), CandidatesForRepeatedSeq.end(),
554  [&StartIdx, &EndIdx](const Candidate &C) {
555  return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx());
556  })) {
557  // It doesn't overlap with anything, so we can outline it.
558  // Each sequence is over [StartIt, EndIt].
559  // Save the candidate and its location.
560 
561  MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
562  MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
563  MachineBasicBlock *MBB = StartIt->getParent();
564 
565  CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
566  EndIt, MBB, FunctionList.size(),
567  Mapper.MBBFlagsMap[MBB]);
568  }
569  }
570 
571  // We've found something we might want to outline.
572  // Create an OutlinedFunction to store it and check if it'd be beneficial
573  // to outline.
574  if (CandidatesForRepeatedSeq.size() < 2)
575  continue;
576 
577  // Arbitrarily choose a TII from the first candidate.
578  // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
579  const TargetInstrInfo *TII =
580  CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
581 
582  OutlinedFunction OF =
583  TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
584 
585  // If we deleted too many candidates, then there's nothing worth outlining.
586  // FIXME: This should take target-specified instruction sizes into account.
587  if (OF.Candidates.size() < 2)
588  continue;
589 
590  // Is it better to outline this candidate than not?
591  if (OF.getBenefit() < 1) {
592  emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
593  continue;
594  }
595 
596  FunctionList.push_back(OF);
597  }
598 }
599 
600 MachineFunction *MachineOutliner::createOutlinedFunction(
601  Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
602 
603  // Create the function name. This should be unique.
604  // FIXME: We should have a better naming scheme. This should be stable,
605  // regardless of changes to the outliner's cost model/traversal order.
606  std::string FunctionName = "OUTLINED_FUNCTION_";
607  if (OutlineRepeatedNum > 0)
608  FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";
609  FunctionName += std::to_string(Name);
610 
611  // Create the function using an IR-level function.
612  LLVMContext &C = M.getContext();
614  Function::ExternalLinkage, FunctionName, M);
615 
616  // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
617  // which gives us better results when we outline from linkonceodr functions.
620 
621  // Set optsize/minsize, so we don't insert padding between outlined
622  // functions.
623  F->addFnAttr(Attribute::OptimizeForSize);
624  F->addFnAttr(Attribute::MinSize);
625 
626  // Include target features from an arbitrary candidate for the outlined
627  // function. This makes sure the outlined function knows what kinds of
628  // instructions are going into it. This is fine, since all parent functions
629  // must necessarily support the instructions that are in the outlined region.
630  Candidate &FirstCand = OF.Candidates.front();
631  const Function &ParentFn = FirstCand.getMF()->getFunction();
632  if (ParentFn.hasFnAttribute("target-features"))
633  F->addFnAttr(ParentFn.getFnAttribute("target-features"));
634 
635  // Set nounwind, so we don't generate eh_frame.
636  if (llvm::all_of(OF.Candidates, [](const outliner::Candidate &C) {
637  return C.getMF()->getFunction().hasFnAttribute(Attribute::NoUnwind);
638  }))
639  F->addFnAttr(Attribute::NoUnwind);
640 
641  BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
642  IRBuilder<> Builder(EntryBB);
643  Builder.CreateRetVoid();
644 
645  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
648  const TargetSubtargetInfo &STI = MF.getSubtarget();
649  const TargetInstrInfo &TII = *STI.getInstrInfo();
650 
651  // Insert the new function into the module.
652  MF.insert(MF.begin(), &MBB);
653 
654  MachineFunction *OriginalMF = FirstCand.front()->getMF();
655  const std::vector<MCCFIInstruction> &Instrs =
656  OriginalMF->getFrameInstructions();
657  for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
658  ++I) {
659  MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
660  if (I->isCFIInstruction()) {
661  unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
662  MCCFIInstruction CFI = Instrs[CFIIndex];
663  (void)MF.addFrameInst(CFI);
664  }
665  NewMI->dropMemRefs(MF);
666 
667  // Don't keep debug information for outlined instructions.
668  NewMI->setDebugLoc(DebugLoc());
669  MBB.insert(MBB.end(), NewMI);
670  }
671 
672  // Set normal properties for a late MachineFunction.
678 
679  // Compute live-in set for outlined fn
680  const MachineRegisterInfo &MRI = MF.getRegInfo();
682  LivePhysRegs LiveIns(TRI);
683  for (auto &Cand : OF.Candidates) {
684  // Figure out live-ins at the first instruction.
685  MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
686  LivePhysRegs CandLiveIns(TRI);
687  CandLiveIns.addLiveOuts(OutlineBB);
688  for (const MachineInstr &MI :
689  reverse(make_range(Cand.front(), OutlineBB.end())))
690  CandLiveIns.stepBackward(MI);
691 
692  // The live-in set for the outlined function is the union of the live-ins
693  // from all the outlining points.
694  for (MCPhysReg Reg : make_range(CandLiveIns.begin(), CandLiveIns.end()))
695  LiveIns.addReg(Reg);
696  }
697  addLiveIns(MBB, LiveIns);
698 
699  TII.buildOutlinedFrame(MBB, MF, OF);
700 
701  // If there's a DISubprogram associated with this outlined function, then
702  // emit debug info for the outlined function.
703  if (DISubprogram *SP = getSubprogramOrNull(OF)) {
704  // We have a DISubprogram. Get its DICompileUnit.
705  DICompileUnit *CU = SP->getUnit();
706  DIBuilder DB(M, true, CU);
707  DIFile *Unit = SP->getFile();
708  Mangler Mg;
709  // Get the mangled name of the function for the linkage name.
710  std::string Dummy;
711  llvm::raw_string_ostream MangledNameStream(Dummy);
712  Mg.getNameWithPrefix(MangledNameStream, F, false);
713 
714  DISubprogram *OutlinedSP = DB.createFunction(
715  Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
716  Unit /* File */,
717  0 /* Line 0 is reserved for compiler-generated code. */,
718  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
719  0, /* Line 0 is reserved for compiler-generated code. */
720  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
721  /* Outlined code is optimized code by definition. */
722  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
723 
724  // Don't add any new variables to the subprogram.
725  DB.finalizeSubprogram(OutlinedSP);
726 
727  // Attach subprogram to the function.
728  F->setSubprogram(OutlinedSP);
729  // We're done with the DIBuilder.
730  DB.finalize();
731  }
732 
733  return &MF;
734 }
735 
736 bool MachineOutliner::outline(Module &M,
737  std::vector<OutlinedFunction> &FunctionList,
738  InstructionMapper &Mapper,
739  unsigned &OutlinedFunctionNum) {
740 
741  bool OutlinedSomething = false;
742 
743  // Sort by benefit. The most beneficial functions should be outlined first.
744  llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
745  const OutlinedFunction &RHS) {
746  return LHS.getBenefit() > RHS.getBenefit();
747  });
748 
749  // Walk over each function, outlining them as we go along. Functions are
750  // outlined greedily, based off the sort above.
751  for (OutlinedFunction &OF : FunctionList) {
752  // If we outlined something that overlapped with a candidate in a previous
753  // step, then we can't outline from it.
754  erase_if(OF.Candidates, [&Mapper](Candidate &C) {
755  return std::any_of(
756  Mapper.UnsignedVec.begin() + C.getStartIdx(),
757  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
758  [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
759  });
760 
761  // If we made it unbeneficial to outline this function, skip it.
762  if (OF.getBenefit() < 1)
763  continue;
764 
765  // It's beneficial. Create the function and outline its sequence's
766  // occurrences.
767  OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
768  emitOutlinedFunctionRemark(OF);
769  FunctionsCreated++;
770  OutlinedFunctionNum++; // Created a function, move to the next name.
771  MachineFunction *MF = OF.MF;
772  const TargetSubtargetInfo &STI = MF->getSubtarget();
773  const TargetInstrInfo &TII = *STI.getInstrInfo();
774 
775  // Replace occurrences of the sequence with calls to the new function.
776  for (Candidate &C : OF.Candidates) {
777  MachineBasicBlock &MBB = *C.getMBB();
778  MachineBasicBlock::iterator StartIt = C.front();
779  MachineBasicBlock::iterator EndIt = C.back();
780 
781  // Insert the call.
782  auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
783 
784  // If the caller tracks liveness, then we need to make sure that
785  // anything we outline doesn't break liveness assumptions. The outlined
786  // functions themselves currently don't track liveness, but we should
787  // make sure that the ranges we yank things out of aren't wrong.
788  if (MBB.getParent()->getProperties().hasProperty(
790  // The following code is to add implicit def operands to the call
791  // instruction. It also updates call site information for moved
792  // code.
793  SmallSet<Register, 2> UseRegs, DefRegs;
794  // Copy over the defs in the outlined range.
795  // First inst in outlined range <-- Anything that's defined in this
796  // ... .. range has to be added as an
797  // implicit Last inst in outlined range <-- def to the call
798  // instruction. Also remove call site information for outlined block
799  // of code. The exposed uses need to be copied in the outlined range.
801  Iter = EndIt.getReverse(),
802  Last = std::next(CallInst.getReverse());
803  Iter != Last; Iter++) {
804  MachineInstr *MI = &*Iter;
805  for (MachineOperand &MOP : MI->operands()) {
806  // Skip over anything that isn't a register.
807  if (!MOP.isReg())
808  continue;
809 
810  if (MOP.isDef()) {
811  // Introduce DefRegs set to skip the redundant register.
812  DefRegs.insert(MOP.getReg());
813  if (UseRegs.count(MOP.getReg()))
814  // Since the regiester is modeled as defined,
815  // it is not necessary to be put in use register set.
816  UseRegs.erase(MOP.getReg());
817  } else if (!MOP.isUndef()) {
818  // Any register which is not undefined should
819  // be put in the use register set.
820  UseRegs.insert(MOP.getReg());
821  }
822  }
823  if (MI->isCandidateForCallSiteEntry())
824  MI->getMF()->eraseCallSiteInfo(MI);
825  }
826 
827  for (const Register &I : DefRegs)
828  // If it's a def, add it to the call instruction.
829  CallInst->addOperand(
830  MachineOperand::CreateReg(I, true, /* isDef = true */
831  true /* isImp = true */));
832 
833  for (const Register &I : UseRegs)
834  // If it's a exposed use, add it to the call instruction.
835  CallInst->addOperand(
836  MachineOperand::CreateReg(I, false, /* isDef = false */
837  true /* isImp = true */));
838  }
839 
840  // Erase from the point after where the call was inserted up to, and
841  // including, the final instruction in the sequence.
842  // Erase needs one past the end, so we need std::next there too.
843  MBB.erase(std::next(StartIt), std::next(EndIt));
844 
845  // Keep track of what we removed by marking them all as -1.
846  std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
847  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
848  [](unsigned &I) { I = static_cast<unsigned>(-1); });
849  OutlinedSomething = true;
850 
851  // Statistics.
852  NumOutlined++;
853  }
854  }
855 
856  LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
857  return OutlinedSomething;
858 }
859 
860 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
861  MachineModuleInfo &MMI) {
862  // Build instruction mappings for each function in the module. Start by
863  // iterating over each Function in M.
864  for (Function &F : M) {
865 
866  // If there's nothing in F, then there's no reason to try and outline from
867  // it.
868  if (F.empty())
869  continue;
870 
871  // There's something in F. Check if it has a MachineFunction associated with
872  // it.
874 
875  // If it doesn't, then there's nothing to outline from. Move to the next
876  // Function.
877  if (!MF)
878  continue;
879 
880  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
881 
882  if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
883  continue;
884 
885  // We have a MachineFunction. Ask the target if it's suitable for outlining.
886  // If it isn't, then move on to the next Function in the module.
887  if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
888  continue;
889 
890  // We have a function suitable for outlining. Iterate over every
891  // MachineBasicBlock in MF and try to map its instructions to a list of
892  // unsigned integers.
893  for (MachineBasicBlock &MBB : *MF) {
894  // If there isn't anything in MBB, then there's no point in outlining from
895  // it.
896  // If there are fewer than 2 instructions in the MBB, then it can't ever
897  // contain something worth outlining.
898  // FIXME: This should be based off of the maximum size in B of an outlined
899  // call versus the size in B of the MBB.
900  if (MBB.empty() || MBB.size() < 2)
901  continue;
902 
903  // Check if MBB could be the target of an indirect branch. If it is, then
904  // we don't want to outline from it.
905  if (MBB.hasAddressTaken())
906  continue;
907 
908  // MBB is suitable for outlining. Map it to a list of unsigneds.
909  Mapper.convertToUnsignedVec(MBB, *TII);
910  }
911  }
912 }
913 
914 void MachineOutliner::initSizeRemarkInfo(
915  const Module &M, const MachineModuleInfo &MMI,
916  StringMap<unsigned> &FunctionToInstrCount) {
917  // Collect instruction counts for every function. We'll use this to emit
918  // per-function size remarks later.
919  for (const Function &F : M) {
921 
922  // We only care about MI counts here. If there's no MachineFunction at this
923  // point, then there won't be after the outliner runs, so let's move on.
924  if (!MF)
925  continue;
926  FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
927  }
928 }
929 
930 void MachineOutliner::emitInstrCountChangedRemark(
931  const Module &M, const MachineModuleInfo &MMI,
932  const StringMap<unsigned> &FunctionToInstrCount) {
933  // Iterate over each function in the module and emit remarks.
934  // Note that we won't miss anything by doing this, because the outliner never
935  // deletes functions.
936  for (const Function &F : M) {
938 
939  // The outliner never deletes functions. If we don't have a MF here, then we
940  // didn't have one prior to outlining either.
941  if (!MF)
942  continue;
943 
944  std::string Fname = std::string(F.getName());
945  unsigned FnCountAfter = MF->getInstructionCount();
946  unsigned FnCountBefore = 0;
947 
948  // Check if the function was recorded before.
949  auto It = FunctionToInstrCount.find(Fname);
950 
951  // Did we have a previously-recorded size? If yes, then set FnCountBefore
952  // to that.
953  if (It != FunctionToInstrCount.end())
954  FnCountBefore = It->second;
955 
956  // Compute the delta and emit a remark if there was a change.
957  int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
958  static_cast<int64_t>(FnCountBefore);
959  if (FnDelta == 0)
960  continue;
961 
963  MORE.emit([&]() {
964  MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
965  DiagnosticLocation(), &MF->front());
966  R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
967  << ": Function: "
968  << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
969  << ": MI instruction count changed from "
970  << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
971  FnCountBefore)
972  << " to "
973  << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
974  FnCountAfter)
975  << "; Delta: "
976  << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
977  return R;
978  });
979  }
980 }
981 
982 bool MachineOutliner::runOnModule(Module &M) {
983  // Check if there's anything in the module. If it's empty, then there's
984  // nothing to outline.
985  if (M.empty())
986  return false;
987 
988  // Number to append to the current outlined function.
989  unsigned OutlinedFunctionNum = 0;
990 
991  OutlineRepeatedNum = 0;
992  if (!doOutline(M, OutlinedFunctionNum))
993  return false;
994 
995  for (unsigned I = 0; I < OutlinerReruns; ++I) {
996  OutlinedFunctionNum = 0;
997  OutlineRepeatedNum++;
998  if (!doOutline(M, OutlinedFunctionNum)) {
999  LLVM_DEBUG({
1000  dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1001  << OutlinerReruns + 1 << "\n";
1002  });
1003  break;
1004  }
1005  }
1006 
1007  return true;
1008 }
1009 
1010 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1011  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1012 
1013  // If the user passed -enable-machine-outliner=always or
1014  // -enable-machine-outliner, the pass will run on all functions in the module.
1015  // Otherwise, if the target supports default outlining, it will run on all
1016  // functions deemed by the target to be worth outlining from by default. Tell
1017  // the user how the outliner is running.
1018  LLVM_DEBUG({
1019  dbgs() << "Machine Outliner: Running on ";
1020  if (RunOnAllFunctions)
1021  dbgs() << "all functions";
1022  else
1023  dbgs() << "target-default functions";
1024  dbgs() << "\n";
1025  });
1026 
1027  // If the user specifies that they want to outline from linkonceodrs, set
1028  // it here.
1029  OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1030  InstructionMapper Mapper;
1031 
1032  // Prepare instruction mappings for the suffix tree.
1033  populateMapper(Mapper, M, MMI);
1034  std::vector<OutlinedFunction> FunctionList;
1035 
1036  // Find all of the outlining candidates.
1037  findCandidates(Mapper, FunctionList);
1038 
1039  // If we've requested size remarks, then collect the MI counts of every
1040  // function before outlining, and the MI counts after outlining.
1041  // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1042  // the pass manager's responsibility.
1043  // This could pretty easily be placed in outline instead, but because we
1044  // really ultimately *don't* want this here, it's done like this for now
1045  // instead.
1046 
1047  // Check if we want size remarks.
1048  bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1049  StringMap<unsigned> FunctionToInstrCount;
1050  if (ShouldEmitSizeRemarks)
1051  initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1052 
1053  // Outline each of the candidates and return true if something was outlined.
1054  bool OutlinedSomething =
1055  outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1056 
1057  // If we outlined something, we definitely changed the MI count of the
1058  // module. If we've asked for size remarks, then output them.
1059  // FIXME: This should be in the pass manager.
1060  if (ShouldEmitSizeRemarks && OutlinedSomething)
1061  emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1062 
1063  LLVM_DEBUG({
1064  if (!OutlinedSomething)
1065  dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1066  << " because no changes were found.\n";
1067  });
1068 
1069  return OutlinedSomething;
1070 }
void finalize()
Construct any deferred debug info descriptors.
Definition: DIBuilder.cpp:69
const Function & getFunction() const
Definition: Function.h:135
const NoneType None
Definition: None.h:23
uint64_t CallInst * C
unsigned getInstructionCount() const
Return the number of MachineInstrs in this MachineFunction.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
const std::vector< MCCFIInstruction > & getFrameInstructions() const
Returns a reference to a list of cfi instructions in the function&#39;s prologue.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MachineFunctionProperties & reset(Property P)
DEBUG_TYPE to vector
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
const MachineFunctionProperties & getProperties() const
Get the function properties.
LLVM_NODISCARD unsigned addFrameInst(const MCCFIInstruction &Inst)
Diagnostic information for applied optimization remarks.
This class represents a function call, abstracting a target machine&#39;s calling convention.
unsigned Reg
iterator find(StringRef Key)
Definition: StringMap.h:216
unsigned Length
The length of the string.
Definition: SuffixTree.h:145
Externally visible function.
Definition: GlobalValue.h:48
iterator begin()
Definition: SuffixTree.h:344
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:330
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1491
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
F(f)
DISubprogram * createFunction(DIScope *Scope, StringRef Name, StringRef LinkageName, DIFile *File, unsigned LineNo, DISubroutineType *Ty, unsigned ScopeLine, DINode::DIFlags Flags=DINode::FlagZero, DISubprogram::DISPFlags SPFlags=DISubprogram::SPFlagZero, DITemplateParameterArray TParams=nullptr, DISubprogram *Decl=nullptr, DITypeArray ThrownTypes=nullptr)
Create a new descriptor for the specified subprogram.
Definition: DIBuilder.cpp:768
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:559
bool erase(const T &V)
Definition: SmallSet.h:207
const_iterator begin() const
Definition: LivePhysRegs.h:151
An individual sequence of instructions to be replaced with a call to an outlined function.
A repeated substring in the tree.
Definition: SuffixTree.h:143
MachineBasicBlock & MBB
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
AnalysisUsage & addRequired()
Definition: BitVector.h:959
virtual MachineBasicBlock::iterator insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, const outliner::Candidate &C) const
Insert a call to an outlined function into the program.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
const HexagonInstrInfo * TII
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:253
std::vector< unsigned > StartIndices
The start indices of each occurrence.
Definition: SuffixTree.h:148
DISubroutineType * createSubroutineType(DITypeRefArray ParameterTypes, DINode::DIFlags Flags=DINode::FlagZero, unsigned CC=0)
Create subroutine type.
Definition: DIBuilder.cpp:502
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
unsigned getCFIIndex() const
Diagnostic information for optimization analysis remarks.
Subprogram description.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
bool empty() const
Definition: Module.h:619
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator end()
Definition: SuffixTree.h:345
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void dropMemRefs(MachineFunction &MF)
Clear this MachineInstr&#39;s memory reference descriptor list.
virtual bool isFunctionSafeToOutlineFrom(MachineFunction &MF, bool OutlineFromLinkOnceODRs) const
Return true if the function can safely be outlined from.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
ReturnInst * CreateRetVoid()
Create a &#39;ret void&#39; instruction.
Definition: IRBuilder.h:928
TargetInstrInfo - Interface to description of machine instruction set.
DITypeRefArray getOrCreateTypeArray(ArrayRef< Metadata *> Elements)
Get a DITypeRefArray, create one if required.
Definition: DIBuilder.cpp:616
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
virtual bool shouldOutlineFromFunctionByDefault(MachineFunction &MF) const
Return true if the function should be outlined from by default.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1524
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:137
const TargetRegisterInfo * getTargetRegisterInfo() const
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
bool shouldEmitInstrCountChangedRemark()
Return true if size-info optimization remark is enabled, false otherwise.
Definition: Module.h:272
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
virtual outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const
Returns how or if MI should be outlined.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
Contains all data structures shared between the outliner implemented in MachineOutliner.cpp and target implementations of the outliner.
virtual bool isMBBSafeToOutlineFrom(MachineBasicBlock &MBB, unsigned &Flags) const
Optional target hook that returns true if MBB is safe to outline from, and returns any target-specifi...
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:170
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
constexpr double e
Definition: MathExtras.h:58
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:311
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
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)
assume Assume Builder
Used in the streaming interface as the general argument type.
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
const MachineBasicBlock & front() const
ModulePass * createMachineOutlinerPass(bool RunOnAllFunctions=true)
This pass performs outlining on machine instructions directly before printing assembly.
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:539
void initializeMachineOutlinerPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
virtual void buildOutlinedFrame(MachineBasicBlock &MBB, MachineFunction &MF, const outliner::OutlinedFunction &OF) const
Insert a custom frame for outlined functions.
The optimization diagnostic interface.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
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.
#define MORE()
Definition: regcomp.c:252
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2&#39;s erase_if which is equivalent t...
Definition: STLExtras.h:1653
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:280
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
Definition: MachineInstr.h:62
bool isCandidateForCallSiteEntry(QueryType Type=IgnoreBundle) const
Return true if this is a call instruction that may have an associated call site entry in the debug in...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineFunction & getOrCreateMachineFunction(Function &F)
Returns the MachineFunction constructed for the IR function F.
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:212
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
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.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
#define I(x, y, z)
Definition: MD5.cpp:59
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
const_iterator end() const
Definition: LivePhysRegs.h:152
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
A data structure for fast substring queries.
Definition: SuffixTree.h:137
void finalizeSubprogram(DISubprogram *SP)
Finalize a specific subprogram - no new variables may be added to this subprogram afterwards...
Definition: DIBuilder.cpp:49
Diagnostic information for missed-optimization remarks.
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) void MachineOutliner
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
void insert(iterator MBBI, MachineBasicBlock *MBB)
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.
void stable_sort(R &&Range)
Definition: STLExtras.h:1619
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:521
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:79
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:340
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable&#39;s name.
Definition: Mangler.cpp:114
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:236
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:341
UnaryPredicate for_each(R &&Range, UnaryPredicate P)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1484
static cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
virtual outliner::OutlinedFunction getOutliningCandidateInfo(std::vector< outliner::Candidate > &RepeatedSequenceLocs) const
Returns a outliner::OutlinedFunction struct containing target-specific information for a set of outli...
#define DEBUG_TYPE
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:49
iterator end()
Definition: StringMap.h:203
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This class contains meta information specific to a module.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164