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