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  Candidate &FirstCand = OF.Candidates.front();
621  const TargetInstrInfo &TII =
622  *FirstCand.getMF()->getSubtarget().getInstrInfo();
623 
624  TII.mergeOutliningCandidateAttributes(*F, OF.Candidates);
625 
626  BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
627  IRBuilder<> Builder(EntryBB);
628  Builder.CreateRetVoid();
629 
630  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
633 
634  // Insert the new function into the module.
635  MF.insert(MF.begin(), &MBB);
636 
637  MachineFunction *OriginalMF = FirstCand.front()->getMF();
638  const std::vector<MCCFIInstruction> &Instrs =
639  OriginalMF->getFrameInstructions();
640  for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
641  ++I) {
642  if (I->isDebugInstr())
643  continue;
644  MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
645  if (I->isCFIInstruction()) {
646  unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
647  MCCFIInstruction CFI = Instrs[CFIIndex];
648  (void)MF.addFrameInst(CFI);
649  }
650  NewMI->dropMemRefs(MF);
651 
652  // Don't keep debug information for outlined instructions.
653  NewMI->setDebugLoc(DebugLoc());
654  MBB.insert(MBB.end(), NewMI);
655  }
656 
657  // Set normal properties for a late MachineFunction.
663 
664  // Compute live-in set for outlined fn
665  const MachineRegisterInfo &MRI = MF.getRegInfo();
667  LivePhysRegs LiveIns(TRI);
668  for (auto &Cand : OF.Candidates) {
669  // Figure out live-ins at the first instruction.
670  MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
671  LivePhysRegs CandLiveIns(TRI);
672  CandLiveIns.addLiveOuts(OutlineBB);
673  for (const MachineInstr &MI :
674  reverse(make_range(Cand.front(), OutlineBB.end())))
675  CandLiveIns.stepBackward(MI);
676 
677  // The live-in set for the outlined function is the union of the live-ins
678  // from all the outlining points.
679  for (MCPhysReg Reg : CandLiveIns)
680  LiveIns.addReg(Reg);
681  }
682  addLiveIns(MBB, LiveIns);
683 
684  TII.buildOutlinedFrame(MBB, MF, OF);
685 
686  // If there's a DISubprogram associated with this outlined function, then
687  // emit debug info for the outlined function.
688  if (DISubprogram *SP = getSubprogramOrNull(OF)) {
689  // We have a DISubprogram. Get its DICompileUnit.
690  DICompileUnit *CU = SP->getUnit();
691  DIBuilder DB(M, true, CU);
692  DIFile *Unit = SP->getFile();
693  Mangler Mg;
694  // Get the mangled name of the function for the linkage name.
695  std::string Dummy;
696  llvm::raw_string_ostream MangledNameStream(Dummy);
697  Mg.getNameWithPrefix(MangledNameStream, F, false);
698 
699  DISubprogram *OutlinedSP = DB.createFunction(
700  Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
701  Unit /* File */,
702  0 /* Line 0 is reserved for compiler-generated code. */,
703  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
704  0, /* Line 0 is reserved for compiler-generated code. */
705  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
706  /* Outlined code is optimized code by definition. */
707  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
708 
709  // Don't add any new variables to the subprogram.
710  DB.finalizeSubprogram(OutlinedSP);
711 
712  // Attach subprogram to the function.
713  F->setSubprogram(OutlinedSP);
714  // We're done with the DIBuilder.
715  DB.finalize();
716  }
717 
718  return &MF;
719 }
720 
721 bool MachineOutliner::outline(Module &M,
722  std::vector<OutlinedFunction> &FunctionList,
723  InstructionMapper &Mapper,
724  unsigned &OutlinedFunctionNum) {
725 
726  bool OutlinedSomething = false;
727 
728  // Sort by benefit. The most beneficial functions should be outlined first.
729  llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
730  const OutlinedFunction &RHS) {
731  return LHS.getBenefit() > RHS.getBenefit();
732  });
733 
734  // Walk over each function, outlining them as we go along. Functions are
735  // outlined greedily, based off the sort above.
736  for (OutlinedFunction &OF : FunctionList) {
737  // If we outlined something that overlapped with a candidate in a previous
738  // step, then we can't outline from it.
739  erase_if(OF.Candidates, [&Mapper](Candidate &C) {
740  return std::any_of(
741  Mapper.UnsignedVec.begin() + C.getStartIdx(),
742  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
743  [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
744  });
745 
746  // If we made it unbeneficial to outline this function, skip it.
747  if (OF.getBenefit() < 1)
748  continue;
749 
750  // It's beneficial. Create the function and outline its sequence's
751  // occurrences.
752  OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
753  emitOutlinedFunctionRemark(OF);
754  FunctionsCreated++;
755  OutlinedFunctionNum++; // Created a function, move to the next name.
756  MachineFunction *MF = OF.MF;
757  const TargetSubtargetInfo &STI = MF->getSubtarget();
758  const TargetInstrInfo &TII = *STI.getInstrInfo();
759 
760  // Replace occurrences of the sequence with calls to the new function.
761  for (Candidate &C : OF.Candidates) {
762  MachineBasicBlock &MBB = *C.getMBB();
763  MachineBasicBlock::iterator StartIt = C.front();
764  MachineBasicBlock::iterator EndIt = C.back();
765 
766  // Insert the call.
767  auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
768 
769  // If the caller tracks liveness, then we need to make sure that
770  // anything we outline doesn't break liveness assumptions. The outlined
771  // functions themselves currently don't track liveness, but we should
772  // make sure that the ranges we yank things out of aren't wrong.
775  // The following code is to add implicit def operands to the call
776  // instruction. It also updates call site information for moved
777  // code.
778  SmallSet<Register, 2> UseRegs, DefRegs;
779  // Copy over the defs in the outlined range.
780  // First inst in outlined range <-- Anything that's defined in this
781  // ... .. range has to be added as an
782  // implicit Last inst in outlined range <-- def to the call
783  // instruction. Also remove call site information for outlined block
784  // of code. The exposed uses need to be copied in the outlined range.
786  Iter = EndIt.getReverse(),
787  Last = std::next(CallInst.getReverse());
788  Iter != Last; Iter++) {
789  MachineInstr *MI = &*Iter;
790  SmallSet<Register, 2> InstrUseRegs;
791  for (MachineOperand &MOP : MI->operands()) {
792  // Skip over anything that isn't a register.
793  if (!MOP.isReg())
794  continue;
795 
796  if (MOP.isDef()) {
797  // Introduce DefRegs set to skip the redundant register.
798  DefRegs.insert(MOP.getReg());
799  if (UseRegs.count(MOP.getReg()) &&
800  !InstrUseRegs.count(MOP.getReg()))
801  // Since the regiester is modeled as defined,
802  // it is not necessary to be put in use register set.
803  UseRegs.erase(MOP.getReg());
804  } else if (!MOP.isUndef()) {
805  // Any register which is not undefined should
806  // be put in the use register set.
807  UseRegs.insert(MOP.getReg());
808  InstrUseRegs.insert(MOP.getReg());
809  }
810  }
811  if (MI->isCandidateForCallSiteEntry())
812  MI->getMF()->eraseCallSiteInfo(MI);
813  }
814 
815  for (const Register &I : DefRegs)
816  // If it's a def, add it to the call instruction.
817  CallInst->addOperand(
818  MachineOperand::CreateReg(I, true, /* isDef = true */
819  true /* isImp = true */));
820 
821  for (const Register &I : UseRegs)
822  // If it's a exposed use, add it to the call instruction.
823  CallInst->addOperand(
824  MachineOperand::CreateReg(I, false, /* isDef = false */
825  true /* isImp = true */));
826  }
827 
828  // Erase from the point after where the call was inserted up to, and
829  // including, the final instruction in the sequence.
830  // Erase needs one past the end, so we need std::next there too.
831  MBB.erase(std::next(StartIt), std::next(EndIt));
832 
833  // Keep track of what we removed by marking them all as -1.
834  std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
835  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
836  [](unsigned &I) { I = static_cast<unsigned>(-1); });
837  OutlinedSomething = true;
838 
839  // Statistics.
840  NumOutlined++;
841  }
842  }
843 
844  LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
845  return OutlinedSomething;
846 }
847 
848 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
849  MachineModuleInfo &MMI) {
850  // Build instruction mappings for each function in the module. Start by
851  // iterating over each Function in M.
852  for (Function &F : M) {
853 
854  // If there's nothing in F, then there's no reason to try and outline from
855  // it.
856  if (F.empty())
857  continue;
858 
859  // There's something in F. Check if it has a MachineFunction associated with
860  // it.
862 
863  // If it doesn't, then there's nothing to outline from. Move to the next
864  // Function.
865  if (!MF)
866  continue;
867 
868  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
869 
870  if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
871  continue;
872 
873  // We have a MachineFunction. Ask the target if it's suitable for outlining.
874  // If it isn't, then move on to the next Function in the module.
875  if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
876  continue;
877 
878  // We have a function suitable for outlining. Iterate over every
879  // MachineBasicBlock in MF and try to map its instructions to a list of
880  // unsigned integers.
881  for (MachineBasicBlock &MBB : *MF) {
882  // If there isn't anything in MBB, then there's no point in outlining from
883  // it.
884  // If there are fewer than 2 instructions in the MBB, then it can't ever
885  // contain something worth outlining.
886  // FIXME: This should be based off of the maximum size in B of an outlined
887  // call versus the size in B of the MBB.
888  if (MBB.empty() || MBB.size() < 2)
889  continue;
890 
891  // Check if MBB could be the target of an indirect branch. If it is, then
892  // we don't want to outline from it.
893  if (MBB.hasAddressTaken())
894  continue;
895 
896  // MBB is suitable for outlining. Map it to a list of unsigneds.
897  Mapper.convertToUnsignedVec(MBB, *TII);
898  }
899  }
900 }
901 
902 void MachineOutliner::initSizeRemarkInfo(
903  const Module &M, const MachineModuleInfo &MMI,
904  StringMap<unsigned> &FunctionToInstrCount) {
905  // Collect instruction counts for every function. We'll use this to emit
906  // per-function size remarks later.
907  for (const Function &F : M) {
909 
910  // We only care about MI counts here. If there's no MachineFunction at this
911  // point, then there won't be after the outliner runs, so let's move on.
912  if (!MF)
913  continue;
914  FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
915  }
916 }
917 
918 void MachineOutliner::emitInstrCountChangedRemark(
919  const Module &M, const MachineModuleInfo &MMI,
920  const StringMap<unsigned> &FunctionToInstrCount) {
921  // Iterate over each function in the module and emit remarks.
922  // Note that we won't miss anything by doing this, because the outliner never
923  // deletes functions.
924  for (const Function &F : M) {
926 
927  // The outliner never deletes functions. If we don't have a MF here, then we
928  // didn't have one prior to outlining either.
929  if (!MF)
930  continue;
931 
932  std::string Fname = std::string(F.getName());
933  unsigned FnCountAfter = MF->getInstructionCount();
934  unsigned FnCountBefore = 0;
935 
936  // Check if the function was recorded before.
937  auto It = FunctionToInstrCount.find(Fname);
938 
939  // Did we have a previously-recorded size? If yes, then set FnCountBefore
940  // to that.
941  if (It != FunctionToInstrCount.end())
942  FnCountBefore = It->second;
943 
944  // Compute the delta and emit a remark if there was a change.
945  int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
946  static_cast<int64_t>(FnCountBefore);
947  if (FnDelta == 0)
948  continue;
949 
951  MORE.emit([&]() {
952  MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
953  DiagnosticLocation(), &MF->front());
954  R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
955  << ": Function: "
956  << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
957  << ": MI instruction count changed from "
958  << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
959  FnCountBefore)
960  << " to "
961  << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
962  FnCountAfter)
963  << "; Delta: "
964  << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
965  return R;
966  });
967  }
968 }
969 
970 bool MachineOutliner::runOnModule(Module &M) {
971  // Check if there's anything in the module. If it's empty, then there's
972  // nothing to outline.
973  if (M.empty())
974  return false;
975 
976  // Number to append to the current outlined function.
977  unsigned OutlinedFunctionNum = 0;
978 
979  OutlineRepeatedNum = 0;
980  if (!doOutline(M, OutlinedFunctionNum))
981  return false;
982 
983  for (unsigned I = 0; I < OutlinerReruns; ++I) {
984  OutlinedFunctionNum = 0;
985  OutlineRepeatedNum++;
986  if (!doOutline(M, OutlinedFunctionNum)) {
987  LLVM_DEBUG({
988  dbgs() << "Did not outline on iteration " << I + 2 << " out of "
989  << OutlinerReruns + 1 << "\n";
990  });
991  break;
992  }
993  }
994 
995  return true;
996 }
997 
998 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
999  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1000 
1001  // If the user passed -enable-machine-outliner=always or
1002  // -enable-machine-outliner, the pass will run on all functions in the module.
1003  // Otherwise, if the target supports default outlining, it will run on all
1004  // functions deemed by the target to be worth outlining from by default. Tell
1005  // the user how the outliner is running.
1006  LLVM_DEBUG({
1007  dbgs() << "Machine Outliner: Running on ";
1008  if (RunOnAllFunctions)
1009  dbgs() << "all functions";
1010  else
1011  dbgs() << "target-default functions";
1012  dbgs() << "\n";
1013  });
1014 
1015  // If the user specifies that they want to outline from linkonceodrs, set
1016  // it here.
1017  OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1018  InstructionMapper Mapper;
1019 
1020  // Prepare instruction mappings for the suffix tree.
1021  populateMapper(Mapper, M, MMI);
1022  std::vector<OutlinedFunction> FunctionList;
1023 
1024  // Find all of the outlining candidates.
1025  findCandidates(Mapper, FunctionList);
1026 
1027  // If we've requested size remarks, then collect the MI counts of every
1028  // function before outlining, and the MI counts after outlining.
1029  // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1030  // the pass manager's responsibility.
1031  // This could pretty easily be placed in outline instead, but because we
1032  // really ultimately *don't* want this here, it's done like this for now
1033  // instead.
1034 
1035  // Check if we want size remarks.
1036  bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1037  StringMap<unsigned> FunctionToInstrCount;
1038  if (ShouldEmitSizeRemarks)
1039  initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1040 
1041  // Outline each of the candidates and return true if something was outlined.
1042  bool OutlinedSomething =
1043  outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1044 
1045  // If we outlined something, we definitely changed the MI count of the
1046  // module. If we've asked for size remarks, then output them.
1047  // FIXME: This should be in the pass manager.
1048  if (ShouldEmitSizeRemarks && OutlinedSomething)
1049  emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1050 
1051  LLVM_DEBUG({
1052  if (!OutlinedSomething)
1053  dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1054  << " because no changes were found.\n";
1055  });
1056 
1057  return OutlinedSomething;
1058 }
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 is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
llvm::DILocalScope::getSubprogram
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Definition: DebugInfoMetadata.cpp:828
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:1781
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:1375
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:859
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:359
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:835
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:1746
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:259
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:1559
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:207
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:1015
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:1301
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
An information struct used to provide DenseMap with the various necessary components for a given valu...
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:1600
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:828
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:644
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:725
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::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:143
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:816
llvm::MachineRegisterInfo::freezeReservedRegs
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
Definition: MachineRegisterInfo.cpp:505
llvm::GlobalValue::InternalLinkage
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
llvm::MCCFIInstruction
Definition: MCDwarf.h:470
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:634
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:1593
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::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:1337
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
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:57
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:1797
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:437
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:1735
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:1314
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:1826
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:1469
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:504
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:38
MachineOutliner.h