LLVM  14.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 (const SuffixTree::RepeatedSubstring &RS : ST) {
522  CandidatesForRepeatedSeq.clear();
523  unsigned StringLen = RS.Length;
524  for (const unsigned &StartIdx : RS.StartIndices) {
525  unsigned EndIdx = StartIdx + StringLen - 1;
526  // Trick: Discard some candidates that would be incompatible with the
527  // ones we've already found for this sequence. This will save us some
528  // work in candidate selection.
529  //
530  // If two candidates overlap, then we can't outline them both. This
531  // happens when we have candidates that look like, say
532  //
533  // AA (where each "A" is an instruction).
534  //
535  // We might have some portion of the module that looks like this:
536  // AAAAAA (6 A's)
537  //
538  // In this case, there are 5 different copies of "AA" in this range, but
539  // at most 3 can be outlined. If only outlining 3 of these is going to
540  // be unbeneficial, then we ought to not bother.
541  //
542  // Note that two things DON'T overlap when they look like this:
543  // start1...end1 .... start2...end2
544  // That is, one must either
545  // * End before the other starts
546  // * Start after the other ends
547  if (llvm::all_of(CandidatesForRepeatedSeq, [&StartIdx,
548  &EndIdx](const Candidate &C) {
549  return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx());
550  })) {
551  // It doesn't overlap with anything, so we can outline it.
552  // Each sequence is over [StartIt, EndIt].
553  // Save the candidate and its location.
554 
555  MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
556  MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
557  MachineBasicBlock *MBB = StartIt->getParent();
558 
559  CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
560  EndIt, MBB, FunctionList.size(),
561  Mapper.MBBFlagsMap[MBB]);
562  }
563  }
564 
565  // We've found something we might want to outline.
566  // Create an OutlinedFunction to store it and check if it'd be beneficial
567  // to outline.
568  if (CandidatesForRepeatedSeq.size() < 2)
569  continue;
570 
571  // Arbitrarily choose a TII from the first candidate.
572  // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
573  const TargetInstrInfo *TII =
574  CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
575 
576  OutlinedFunction OF =
577  TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
578 
579  // If we deleted too many candidates, then there's nothing worth outlining.
580  // FIXME: This should take target-specified instruction sizes into account.
581  if (OF.Candidates.size() < 2)
582  continue;
583 
584  // Is it better to outline this candidate than not?
585  if (OF.getBenefit() < 1) {
586  emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
587  continue;
588  }
589 
590  FunctionList.push_back(OF);
591  }
592 }
593 
594 MachineFunction *MachineOutliner::createOutlinedFunction(
595  Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
596 
597  // Create the function name. This should be unique.
598  // FIXME: We should have a better naming scheme. This should be stable,
599  // regardless of changes to the outliner's cost model/traversal order.
600  std::string FunctionName = "OUTLINED_FUNCTION_";
601  if (OutlineRepeatedNum > 0)
602  FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";
603  FunctionName += std::to_string(Name);
604 
605  // Create the function using an IR-level function.
606  LLVMContext &C = M.getContext();
608  Function::ExternalLinkage, FunctionName, M);
609 
610  // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
611  // which gives us better results when we outline from linkonceodr functions.
612  F->setLinkage(GlobalValue::InternalLinkage);
613  F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
614 
615  // Set optsize/minsize, so we don't insert padding between outlined
616  // functions.
617  F->addFnAttr(Attribute::OptimizeForSize);
618  F->addFnAttr(Attribute::MinSize);
619 
620  // Include target features from an arbitrary candidate for the outlined
621  // function. This makes sure the outlined function knows what kinds of
622  // instructions are going into it. This is fine, since all parent functions
623  // must necessarily support the instructions that are in the outlined region.
624  Candidate &FirstCand = OF.Candidates.front();
625  const Function &ParentFn = FirstCand.getMF()->getFunction();
626  if (ParentFn.hasFnAttribute("target-features"))
627  F->addFnAttr(ParentFn.getFnAttribute("target-features"));
628 
629  // Set nounwind, so we don't generate eh_frame.
630  if (llvm::all_of(OF.Candidates, [](const outliner::Candidate &C) {
631  return C.getMF()->getFunction().hasFnAttribute(Attribute::NoUnwind);
632  }))
633  F->addFnAttr(Attribute::NoUnwind);
634 
635  BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
636  IRBuilder<> Builder(EntryBB);
637  Builder.CreateRetVoid();
638 
639  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
642  const TargetSubtargetInfo &STI = MF.getSubtarget();
643  const TargetInstrInfo &TII = *STI.getInstrInfo();
644 
645  // Insert the new function into the module.
646  MF.insert(MF.begin(), &MBB);
647 
648  MachineFunction *OriginalMF = FirstCand.front()->getMF();
649  const std::vector<MCCFIInstruction> &Instrs =
650  OriginalMF->getFrameInstructions();
651  for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
652  ++I) {
653  if (I->isDebugInstr())
654  continue;
655  MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
656  if (I->isCFIInstruction()) {
657  unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
658  MCCFIInstruction CFI = Instrs[CFIIndex];
659  (void)MF.addFrameInst(CFI);
660  }
661  NewMI->dropMemRefs(MF);
662 
663  // Don't keep debug information for outlined instructions.
664  NewMI->setDebugLoc(DebugLoc());
665  MBB.insert(MBB.end(), NewMI);
666  }
667 
668  // Set normal properties for a late MachineFunction.
674 
675  // Compute live-in set for outlined fn
676  const MachineRegisterInfo &MRI = MF.getRegInfo();
678  LivePhysRegs LiveIns(TRI);
679  for (auto &Cand : OF.Candidates) {
680  // Figure out live-ins at the first instruction.
681  MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
682  LivePhysRegs CandLiveIns(TRI);
683  CandLiveIns.addLiveOuts(OutlineBB);
684  for (const MachineInstr &MI :
685  reverse(make_range(Cand.front(), OutlineBB.end())))
686  CandLiveIns.stepBackward(MI);
687 
688  // The live-in set for the outlined function is the union of the live-ins
689  // from all the outlining points.
690  for (MCPhysReg Reg : CandLiveIns)
691  LiveIns.addReg(Reg);
692  }
693  addLiveIns(MBB, LiveIns);
694 
695  TII.buildOutlinedFrame(MBB, MF, OF);
696 
697  // If there's a DISubprogram associated with this outlined function, then
698  // emit debug info for the outlined function.
699  if (DISubprogram *SP = getSubprogramOrNull(OF)) {
700  // We have a DISubprogram. Get its DICompileUnit.
701  DICompileUnit *CU = SP->getUnit();
702  DIBuilder DB(M, true, CU);
703  DIFile *Unit = SP->getFile();
704  Mangler Mg;
705  // Get the mangled name of the function for the linkage name.
706  std::string Dummy;
707  llvm::raw_string_ostream MangledNameStream(Dummy);
708  Mg.getNameWithPrefix(MangledNameStream, F, false);
709 
710  DISubprogram *OutlinedSP = DB.createFunction(
711  Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
712  Unit /* File */,
713  0 /* Line 0 is reserved for compiler-generated code. */,
714  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
715  0, /* Line 0 is reserved for compiler-generated code. */
716  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
717  /* Outlined code is optimized code by definition. */
718  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
719 
720  // Don't add any new variables to the subprogram.
721  DB.finalizeSubprogram(OutlinedSP);
722 
723  // Attach subprogram to the function.
724  F->setSubprogram(OutlinedSP);
725  // We're done with the DIBuilder.
726  DB.finalize();
727  }
728 
729  return &MF;
730 }
731 
732 bool MachineOutliner::outline(Module &M,
733  std::vector<OutlinedFunction> &FunctionList,
734  InstructionMapper &Mapper,
735  unsigned &OutlinedFunctionNum) {
736 
737  bool OutlinedSomething = false;
738 
739  // Sort by benefit. The most beneficial functions should be outlined first.
740  llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
741  const OutlinedFunction &RHS) {
742  return LHS.getBenefit() > RHS.getBenefit();
743  });
744 
745  // Walk over each function, outlining them as we go along. Functions are
746  // outlined greedily, based off the sort above.
747  for (OutlinedFunction &OF : FunctionList) {
748  // If we outlined something that overlapped with a candidate in a previous
749  // step, then we can't outline from it.
750  erase_if(OF.Candidates, [&Mapper](Candidate &C) {
751  return std::any_of(
752  Mapper.UnsignedVec.begin() + C.getStartIdx(),
753  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
754  [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
755  });
756 
757  // If we made it unbeneficial to outline this function, skip it.
758  if (OF.getBenefit() < 1)
759  continue;
760 
761  // It's beneficial. Create the function and outline its sequence's
762  // occurrences.
763  OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
764  emitOutlinedFunctionRemark(OF);
765  FunctionsCreated++;
766  OutlinedFunctionNum++; // Created a function, move to the next name.
767  MachineFunction *MF = OF.MF;
768  const TargetSubtargetInfo &STI = MF->getSubtarget();
769  const TargetInstrInfo &TII = *STI.getInstrInfo();
770 
771  // Replace occurrences of the sequence with calls to the new function.
772  for (Candidate &C : OF.Candidates) {
773  MachineBasicBlock &MBB = *C.getMBB();
774  MachineBasicBlock::iterator StartIt = C.front();
775  MachineBasicBlock::iterator EndIt = C.back();
776 
777  // Insert the call.
778  auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
779 
780  // If the caller tracks liveness, then we need to make sure that
781  // anything we outline doesn't break liveness assumptions. The outlined
782  // functions themselves currently don't track liveness, but we should
783  // make sure that the ranges we yank things out of aren't wrong.
786  // The following code is to add implicit def operands to the call
787  // instruction. It also updates call site information for moved
788  // code.
789  SmallSet<Register, 2> UseRegs, DefRegs;
790  // Copy over the defs in the outlined range.
791  // First inst in outlined range <-- Anything that's defined in this
792  // ... .. range has to be added as an
793  // implicit Last inst in outlined range <-- def to the call
794  // instruction. Also remove call site information for outlined block
795  // of code. The exposed uses need to be copied in the outlined range.
797  Iter = EndIt.getReverse(),
798  Last = std::next(CallInst.getReverse());
799  Iter != Last; Iter++) {
800  MachineInstr *MI = &*Iter;
801  for (MachineOperand &MOP : MI->operands()) {
802  // Skip over anything that isn't a register.
803  if (!MOP.isReg())
804  continue;
805 
806  if (MOP.isDef()) {
807  // Introduce DefRegs set to skip the redundant register.
808  DefRegs.insert(MOP.getReg());
809  if (!MOP.isDead() && UseRegs.count(MOP.getReg()))
810  // Since the regiester is modeled as defined,
811  // it is not necessary to be put in use register set.
812  UseRegs.erase(MOP.getReg());
813  } else if (!MOP.isUndef()) {
814  // Any register which is not undefined should
815  // be put in the use register set.
816  UseRegs.insert(MOP.getReg());
817  }
818  }
819  if (MI->isCandidateForCallSiteEntry())
820  MI->getMF()->eraseCallSiteInfo(MI);
821  }
822 
823  for (const Register &I : DefRegs)
824  // If it's a def, add it to the call instruction.
825  CallInst->addOperand(
826  MachineOperand::CreateReg(I, true, /* isDef = true */
827  true /* isImp = true */));
828 
829  for (const Register &I : UseRegs)
830  // If it's a exposed use, add it to the call instruction.
831  CallInst->addOperand(
832  MachineOperand::CreateReg(I, false, /* isDef = false */
833  true /* isImp = true */));
834  }
835 
836  // Erase from the point after where the call was inserted up to, and
837  // including, the final instruction in the sequence.
838  // Erase needs one past the end, so we need std::next there too.
839  MBB.erase(std::next(StartIt), std::next(EndIt));
840 
841  // Keep track of what we removed by marking them all as -1.
842  std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
843  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
844  [](unsigned &I) { I = static_cast<unsigned>(-1); });
845  OutlinedSomething = true;
846 
847  // Statistics.
848  NumOutlined++;
849  }
850  }
851 
852  LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
853  return OutlinedSomething;
854 }
855 
856 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
857  MachineModuleInfo &MMI) {
858  // Build instruction mappings for each function in the module. Start by
859  // iterating over each Function in M.
860  for (Function &F : M) {
861 
862  // If there's nothing in F, then there's no reason to try and outline from
863  // it.
864  if (F.empty())
865  continue;
866 
867  // There's something in F. Check if it has a MachineFunction associated with
868  // it.
870 
871  // If it doesn't, then there's nothing to outline from. Move to the next
872  // Function.
873  if (!MF)
874  continue;
875 
876  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
877 
878  if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
879  continue;
880 
881  // We have a MachineFunction. Ask the target if it's suitable for outlining.
882  // If it isn't, then move on to the next Function in the module.
883  if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
884  continue;
885 
886  // We have a function suitable for outlining. Iterate over every
887  // MachineBasicBlock in MF and try to map its instructions to a list of
888  // unsigned integers.
889  for (MachineBasicBlock &MBB : *MF) {
890  // If there isn't anything in MBB, then there's no point in outlining from
891  // it.
892  // If there are fewer than 2 instructions in the MBB, then it can't ever
893  // contain something worth outlining.
894  // FIXME: This should be based off of the maximum size in B of an outlined
895  // call versus the size in B of the MBB.
896  if (MBB.empty() || MBB.size() < 2)
897  continue;
898 
899  // Check if MBB could be the target of an indirect branch. If it is, then
900  // we don't want to outline from it.
901  if (MBB.hasAddressTaken())
902  continue;
903 
904  // MBB is suitable for outlining. Map it to a list of unsigneds.
905  Mapper.convertToUnsignedVec(MBB, *TII);
906  }
907  }
908 }
909 
910 void MachineOutliner::initSizeRemarkInfo(
911  const Module &M, const MachineModuleInfo &MMI,
912  StringMap<unsigned> &FunctionToInstrCount) {
913  // Collect instruction counts for every function. We'll use this to emit
914  // per-function size remarks later.
915  for (const Function &F : M) {
917 
918  // We only care about MI counts here. If there's no MachineFunction at this
919  // point, then there won't be after the outliner runs, so let's move on.
920  if (!MF)
921  continue;
922  FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
923  }
924 }
925 
926 void MachineOutliner::emitInstrCountChangedRemark(
927  const Module &M, const MachineModuleInfo &MMI,
928  const StringMap<unsigned> &FunctionToInstrCount) {
929  // Iterate over each function in the module and emit remarks.
930  // Note that we won't miss anything by doing this, because the outliner never
931  // deletes functions.
932  for (const Function &F : M) {
934 
935  // The outliner never deletes functions. If we don't have a MF here, then we
936  // didn't have one prior to outlining either.
937  if (!MF)
938  continue;
939 
940  std::string Fname = std::string(F.getName());
941  unsigned FnCountAfter = MF->getInstructionCount();
942  unsigned FnCountBefore = 0;
943 
944  // Check if the function was recorded before.
945  auto It = FunctionToInstrCount.find(Fname);
946 
947  // Did we have a previously-recorded size? If yes, then set FnCountBefore
948  // to that.
949  if (It != FunctionToInstrCount.end())
950  FnCountBefore = It->second;
951 
952  // Compute the delta and emit a remark if there was a change.
953  int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
954  static_cast<int64_t>(FnCountBefore);
955  if (FnDelta == 0)
956  continue;
957 
959  MORE.emit([&]() {
960  MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
961  DiagnosticLocation(), &MF->front());
962  R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
963  << ": Function: "
964  << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
965  << ": MI instruction count changed from "
966  << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
967  FnCountBefore)
968  << " to "
969  << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
970  FnCountAfter)
971  << "; Delta: "
972  << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
973  return R;
974  });
975  }
976 }
977 
978 bool MachineOutliner::runOnModule(Module &M) {
979  // Check if there's anything in the module. If it's empty, then there's
980  // nothing to outline.
981  if (M.empty())
982  return false;
983 
984  // Number to append to the current outlined function.
985  unsigned OutlinedFunctionNum = 0;
986 
987  OutlineRepeatedNum = 0;
988  if (!doOutline(M, OutlinedFunctionNum))
989  return false;
990 
991  for (unsigned I = 0; I < OutlinerReruns; ++I) {
992  OutlinedFunctionNum = 0;
993  OutlineRepeatedNum++;
994  if (!doOutline(M, OutlinedFunctionNum)) {
995  LLVM_DEBUG({
996  dbgs() << "Did not outline on iteration " << I + 2 << " out of "
997  << OutlinerReruns + 1 << "\n";
998  });
999  break;
1000  }
1001  }
1002 
1003  return true;
1004 }
1005 
1006 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1007  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1008 
1009  // If the user passed -enable-machine-outliner=always or
1010  // -enable-machine-outliner, the pass will run on all functions in the module.
1011  // Otherwise, if the target supports default outlining, it will run on all
1012  // functions deemed by the target to be worth outlining from by default. Tell
1013  // the user how the outliner is running.
1014  LLVM_DEBUG({
1015  dbgs() << "Machine Outliner: Running on ";
1016  if (RunOnAllFunctions)
1017  dbgs() << "all functions";
1018  else
1019  dbgs() << "target-default functions";
1020  dbgs() << "\n";
1021  });
1022 
1023  // If the user specifies that they want to outline from linkonceodrs, set
1024  // it here.
1025  OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1026  InstructionMapper Mapper;
1027 
1028  // Prepare instruction mappings for the suffix tree.
1029  populateMapper(Mapper, M, MMI);
1030  std::vector<OutlinedFunction> FunctionList;
1031 
1032  // Find all of the outlining candidates.
1033  findCandidates(Mapper, FunctionList);
1034 
1035  // If we've requested size remarks, then collect the MI counts of every
1036  // function before outlining, and the MI counts after outlining.
1037  // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1038  // the pass manager's responsibility.
1039  // This could pretty easily be placed in outline instead, but because we
1040  // really ultimately *don't* want this here, it's done like this for now
1041  // instead.
1042 
1043  // Check if we want size remarks.
1044  bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1045  StringMap<unsigned> FunctionToInstrCount;
1046  if (ShouldEmitSizeRemarks)
1047  initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1048 
1049  // Outline each of the candidates and return true if something was outlined.
1050  bool OutlinedSomething =
1051  outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1052 
1053  // If we outlined something, we definitely changed the MI count of the
1054  // module. If we've asked for size remarks, then output them.
1055  // FIXME: This should be in the pass manager.
1056  if (ShouldEmitSizeRemarks && OutlinedSomething)
1057  emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1058 
1059  LLVM_DEBUG({
1060  if (!OutlinedSomething)
1061  dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1062  << " because no changes were found.\n";
1063  });
1064 
1065  return OutlinedSomething;
1066 }
i
i
Definition: README.txt:29
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:169
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::DILocalScope::getSubprogram
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Definition: DebugInfoMetadata.cpp:814
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::MachineOperand::CreateReg
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)
Definition: MachineOperand.h:791
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
llvm::DIBuilder
Definition: DIBuilder.h:41
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Function
Definition: Function.h:62
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:625
Statistic.h
llvm::IRBuilder<>
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:153
llvm::erase_if
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:1732
llvm::MachineOptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: MachineOptimizationRemarkEmitter.h:150
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:363
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:75
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
EnableLinkOnceODROutlining
static cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))
llvm::MachineBasicBlock::findDebugLoc
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions.
Definition: MachineBasicBlock.cpp:1378
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::StringMap::end
iterator end()
Definition: StringMap.h:203
llvm::MachineFunction::getInstructionCount
unsigned getInstructionCount() const
Return the number of MachineInstrs in this MachineFunction.
Definition: MachineFunction.h:855
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::SuffixTree
A data structure for fast substring queries.
Definition: SuffixTree.h:137
TargetInstrInfo.h
llvm::MachineFunction::insert
void insert(iterator MBBI, MachineBasicBlock *MBB)
Definition: MachineFunction.h:831
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::GlobalValue::UnnamedAddr::Global
@ Global
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
Definition: MachineInstr.h:1745
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::addLiveIns
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
Definition: LivePhysRegs.cpp:257
llvm::StringMap::find
iterator find(StringRef Key)
Definition: StringMap.h:216
llvm::Mangler
Definition: Mangler.h:27
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::MachineFunction::getFrameInstructions
const std::vector< MCCFIInstruction > & getFrameInstructions() const
Returns a reference to a list of cfi instructions in the function's prologue.
Definition: MachineFunction.h:1010
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1304
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineOptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: MachineOptimizationRemarkEmitter.h:56
CommandLine.h
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::all_of
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:1551
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:824
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:640
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::IRSimilarity::Illegal
@ Illegal
Definition: IRSimilarityIdentifier.h:75
Twine.h
INITIALIZE_PASS
INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) void MachineOutliner
Definition: MachineOutliner.cpp:451
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineFunction::getProperties
const MachineFunctionProperties & getProperties() const
Get the function properties.
Definition: MachineFunction.h:721
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::Mangler::getNameWithPrefix
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable's name.
Definition: Mangler.cpp:119
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::Function::getFnAttribute
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.cpp:652
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:173
llvm::MachineModuleInfo
This class contains meta information specific to a module.
Definition: MachineModuleInfo.h:78
llvm::MachineOptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: MachineOptimizationRemarkEmitter.h:108
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:812
llvm::MachineRegisterInfo::freezeReservedRegs
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
Definition: MachineRegisterInfo.cpp:507
llvm::GlobalValue::InternalLinkage
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
llvm::MCCFIInstruction
Definition: MCDwarf.h:457
llvm::createMachineOutlinerPass
ModulePass * createMachineOutlinerPass(bool RunOnAllFunctions=true)
This pass performs outlining on machine instructions directly before printing assembly.
Definition: MachineOutliner.cpp:443
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::StringMap< unsigned >
MachineOptimizationRemarkEmitter.h
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
Passes.h
llvm::initializeMachineOutlinerPass
void initializeMachineOutlinerPass(PassRegistry &)
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:626
llvm::cl::opt< bool >
llvm::DiagnosticInfoOptimizationBase::Argument
Used in the streaming interface as the general argument type.
Definition: DiagnosticInfo.h:422
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
llvm::MachineInstrBundleIterator::getReverse
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Definition: MachineInstrBundleIterator.h:283
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:75
llvm::MachineFunctionProperties::Property::TracksLiveness
@ TracksLiveness
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::for_each
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:1544
llvm::MachineBasicBlock::hasAddressTaken
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
Definition: MachineBasicBlock.h:211
llvm::MachineOptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: MachineOptimizationRemarkEmitter.h:82
llvm::MachineModuleInfoWrapperPass
Definition: MachineModuleInfo.h:279
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:359
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::outliner::LegalTerminator
@ LegalTerminator
Definition: MachineOutliner.h:34
llvm::outliner::Candidate
An individual sequence of instructions to be replaced with a call to an outlined function.
Definition: MachineOutliner.h:38
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SuffixTree::RepeatedSubstring
A repeated substring in the tree.
Definition: SuffixTree.h:143
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
DIBuilder.h
llvm::DICompileUnit
Compile unit.
Definition: DebugInfoMetadata.h:1335
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:415
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:139
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:239
SuffixTree.h
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
MachineModuleInfo.h
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:207
llvm::Function::getFunction
const Function & getFunction() const
Definition: Function.h:137
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::MachineFunction
Definition: MachineFunction.h:234
Mangler.h
getDebugLoc
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.
Definition: MachineInstrBundle.cpp:109
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
OutlinerReruns
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.
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::DiagnosticLocation
Definition: DiagnosticInfo.h:349
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
TargetSubtargetInfo.h
llvm::MachineModuleInfo::getOrCreateMachineFunction
MachineFunction & getOrCreateMachineFunction(Function &F)
Returns the MachineFunction constructed for the IR function F.
Definition: MachineModuleInfo.cpp:291
llvm::SmallSet::insert
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
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
llvm::MachineFunctionProperties::reset
MachineFunctionProperties & reset(Property P)
Definition: MachineFunction.h:178
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
MORE
#define MORE()
Definition: regcomp.c:252
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
getSubprogramOrNull
static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)
Get the subprogram if it exists for one of the outlined regions.
Definition: IROutliner.cpp:441
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1686
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::MachineModuleInfo::getMachineFunction
MachineFunction * getMachineFunction(const Function &F) const
Returns the MachineFunction associated to IR function F if there is one, otherwise nullptr.
Definition: MachineModuleInfo.cpp:286
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1317
llvm::MachineOperand::getCFIIndex
unsigned getCFIIndex() const
Definition: MachineOperand.h:578
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:247
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:224
llvm::MachineFunction::addFrameInst
LLVM_NODISCARD unsigned addFrameInst(const MCCFIInstruction &Inst)
Definition: MachineFunction.cpp:286
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:63
llvm::MachineInstr::dropMemRefs
void dropMemRefs(MachineFunction &MF)
Clear this MachineInstr's memory reference descriptor list.
Definition: MachineInstr.cpp:366
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:240
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1820
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
llvm::MachineInstrBundleIterator< MachineInstr >
CU
Definition: AArch64AsmBackend.cpp:501
InitializePasses.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineOutliner.cpp:79
llvm::DIFile
File.
Definition: DebugInfoMetadata.h:530
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
MachineOutliner.h