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