LLVM  17.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(
731  DB.getOrCreateTypeArray(std::nullopt)), /* void type */
732  0, /* Line 0 is reserved for compiler-generated code. */
733  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
734  /* Outlined code is optimized code by definition. */
735  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
736 
737  // Don't add any new variables to the subprogram.
738  DB.finalizeSubprogram(OutlinedSP);
739 
740  // Attach subprogram to the function.
741  F->setSubprogram(OutlinedSP);
742  // We're done with the DIBuilder.
743  DB.finalize();
744  }
745 
746  return &MF;
747 }
748 
749 bool MachineOutliner::outline(Module &M,
750  std::vector<OutlinedFunction> &FunctionList,
751  InstructionMapper &Mapper,
752  unsigned &OutlinedFunctionNum) {
753 
754  bool OutlinedSomething = false;
755 
756  // Sort by benefit. The most beneficial functions should be outlined first.
757  llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
758  const OutlinedFunction &RHS) {
759  return LHS.getBenefit() > RHS.getBenefit();
760  });
761 
762  // Walk over each function, outlining them as we go along. Functions are
763  // outlined greedily, based off the sort above.
764  for (OutlinedFunction &OF : FunctionList) {
765  // If we outlined something that overlapped with a candidate in a previous
766  // step, then we can't outline from it.
767  erase_if(OF.Candidates, [&Mapper](Candidate &C) {
768  return std::any_of(
769  Mapper.UnsignedVec.begin() + C.getStartIdx(),
770  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
771  [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
772  });
773 
774  // If we made it unbeneficial to outline this function, skip it.
775  if (OF.getBenefit() < 1)
776  continue;
777 
778  // It's beneficial. Create the function and outline its sequence's
779  // occurrences.
780  OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
781  emitOutlinedFunctionRemark(OF);
782  FunctionsCreated++;
783  OutlinedFunctionNum++; // Created a function, move to the next name.
784  MachineFunction *MF = OF.MF;
785  const TargetSubtargetInfo &STI = MF->getSubtarget();
786  const TargetInstrInfo &TII = *STI.getInstrInfo();
787 
788  // Replace occurrences of the sequence with calls to the new function.
789  for (Candidate &C : OF.Candidates) {
790  MachineBasicBlock &MBB = *C.getMBB();
791  MachineBasicBlock::iterator StartIt = C.front();
792  MachineBasicBlock::iterator EndIt = C.back();
793 
794  // Insert the call.
795  auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
796 
797  // If the caller tracks liveness, then we need to make sure that
798  // anything we outline doesn't break liveness assumptions. The outlined
799  // functions themselves currently don't track liveness, but we should
800  // make sure that the ranges we yank things out of aren't wrong.
803  // The following code is to add implicit def operands to the call
804  // instruction. It also updates call site information for moved
805  // code.
806  SmallSet<Register, 2> UseRegs, DefRegs;
807  // Copy over the defs in the outlined range.
808  // First inst in outlined range <-- Anything that's defined in this
809  // ... .. range has to be added as an
810  // implicit Last inst in outlined range <-- def to the call
811  // instruction. Also remove call site information for outlined block
812  // of code. The exposed uses need to be copied in the outlined range.
814  Iter = EndIt.getReverse(),
815  Last = std::next(CallInst.getReverse());
816  Iter != Last; Iter++) {
817  MachineInstr *MI = &*Iter;
818  SmallSet<Register, 2> InstrUseRegs;
819  for (MachineOperand &MOP : MI->operands()) {
820  // Skip over anything that isn't a register.
821  if (!MOP.isReg())
822  continue;
823 
824  if (MOP.isDef()) {
825  // Introduce DefRegs set to skip the redundant register.
826  DefRegs.insert(MOP.getReg());
827  if (UseRegs.count(MOP.getReg()) &&
828  !InstrUseRegs.count(MOP.getReg()))
829  // Since the regiester is modeled as defined,
830  // it is not necessary to be put in use register set.
831  UseRegs.erase(MOP.getReg());
832  } else if (!MOP.isUndef()) {
833  // Any register which is not undefined should
834  // be put in the use register set.
835  UseRegs.insert(MOP.getReg());
836  InstrUseRegs.insert(MOP.getReg());
837  }
838  }
839  if (MI->isCandidateForCallSiteEntry())
840  MI->getMF()->eraseCallSiteInfo(MI);
841  }
842 
843  for (const Register &I : DefRegs)
844  // If it's a def, add it to the call instruction.
845  CallInst->addOperand(
846  MachineOperand::CreateReg(I, true, /* isDef = true */
847  true /* isImp = true */));
848 
849  for (const Register &I : UseRegs)
850  // If it's a exposed use, add it to the call instruction.
851  CallInst->addOperand(
852  MachineOperand::CreateReg(I, false, /* isDef = false */
853  true /* isImp = true */));
854  }
855 
856  // Erase from the point after where the call was inserted up to, and
857  // including, the final instruction in the sequence.
858  // Erase needs one past the end, so we need std::next there too.
859  MBB.erase(std::next(StartIt), std::next(EndIt));
860 
861  // Keep track of what we removed by marking them all as -1.
862  for (unsigned &I :
863  llvm::make_range(Mapper.UnsignedVec.begin() + C.getStartIdx(),
864  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1))
865  I = static_cast<unsigned>(-1);
866  OutlinedSomething = true;
867 
868  // Statistics.
869  NumOutlined++;
870  }
871  }
872 
873  LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
874  return OutlinedSomething;
875 }
876 
877 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
878  MachineModuleInfo &MMI) {
879  // Build instruction mappings for each function in the module. Start by
880  // iterating over each Function in M.
881  for (Function &F : M) {
882 
883  if (F.hasFnAttribute("nooutline")) {
884  LLVM_DEBUG({
885  dbgs() << "... Skipping function with nooutline attribute: "
886  << F.getName() << "\n";
887  });
888  continue;
889  }
890 
891  // There's something in F. Check if it has a MachineFunction associated with
892  // it.
894 
895  // If it doesn't, then there's nothing to outline from. Move to the next
896  // Function.
897  if (!MF)
898  continue;
899 
900  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
901 
902  if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
903  continue;
904 
905  // We have a MachineFunction. Ask the target if it's suitable for outlining.
906  // If it isn't, then move on to the next Function in the module.
907  if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
908  continue;
909 
910  // We have a function suitable for outlining. Iterate over every
911  // MachineBasicBlock in MF and try to map its instructions to a list of
912  // unsigned integers.
913  for (MachineBasicBlock &MBB : *MF) {
914  // If there isn't anything in MBB, then there's no point in outlining from
915  // it.
916  // If there are fewer than 2 instructions in the MBB, then it can't ever
917  // contain something worth outlining.
918  // FIXME: This should be based off of the maximum size in B of an outlined
919  // call versus the size in B of the MBB.
920  if (MBB.empty() || MBB.size() < 2)
921  continue;
922 
923  // Check if MBB could be the target of an indirect branch. If it is, then
924  // we don't want to outline from it.
925  if (MBB.hasAddressTaken())
926  continue;
927 
928  // MBB is suitable for outlining. Map it to a list of unsigneds.
929  Mapper.convertToUnsignedVec(MBB, *TII);
930  }
931 
932  // Statistics.
933  UnsignedVecSize = Mapper.UnsignedVec.size();
934  }
935 }
936 
937 void MachineOutliner::initSizeRemarkInfo(
938  const Module &M, const MachineModuleInfo &MMI,
939  StringMap<unsigned> &FunctionToInstrCount) {
940  // Collect instruction counts for every function. We'll use this to emit
941  // per-function size remarks later.
942  for (const Function &F : M) {
944 
945  // We only care about MI counts here. If there's no MachineFunction at this
946  // point, then there won't be after the outliner runs, so let's move on.
947  if (!MF)
948  continue;
949  FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
950  }
951 }
952 
953 void MachineOutliner::emitInstrCountChangedRemark(
954  const Module &M, const MachineModuleInfo &MMI,
955  const StringMap<unsigned> &FunctionToInstrCount) {
956  // Iterate over each function in the module and emit remarks.
957  // Note that we won't miss anything by doing this, because the outliner never
958  // deletes functions.
959  for (const Function &F : M) {
961 
962  // The outliner never deletes functions. If we don't have a MF here, then we
963  // didn't have one prior to outlining either.
964  if (!MF)
965  continue;
966 
967  std::string Fname = std::string(F.getName());
968  unsigned FnCountAfter = MF->getInstructionCount();
969  unsigned FnCountBefore = 0;
970 
971  // Check if the function was recorded before.
972  auto It = FunctionToInstrCount.find(Fname);
973 
974  // Did we have a previously-recorded size? If yes, then set FnCountBefore
975  // to that.
976  if (It != FunctionToInstrCount.end())
977  FnCountBefore = It->second;
978 
979  // Compute the delta and emit a remark if there was a change.
980  int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
981  static_cast<int64_t>(FnCountBefore);
982  if (FnDelta == 0)
983  continue;
984 
986  MORE.emit([&]() {
987  MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
988  DiagnosticLocation(), &MF->front());
989  R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
990  << ": Function: "
991  << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
992  << ": MI instruction count changed from "
993  << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
994  FnCountBefore)
995  << " to "
996  << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
997  FnCountAfter)
998  << "; Delta: "
999  << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1000  return R;
1001  });
1002  }
1003 }
1004 
1005 bool MachineOutliner::runOnModule(Module &M) {
1006  // Check if there's anything in the module. If it's empty, then there's
1007  // nothing to outline.
1008  if (M.empty())
1009  return false;
1010 
1011  // Number to append to the current outlined function.
1012  unsigned OutlinedFunctionNum = 0;
1013 
1014  OutlineRepeatedNum = 0;
1015  if (!doOutline(M, OutlinedFunctionNum))
1016  return false;
1017 
1018  for (unsigned I = 0; I < OutlinerReruns; ++I) {
1019  OutlinedFunctionNum = 0;
1020  OutlineRepeatedNum++;
1021  if (!doOutline(M, OutlinedFunctionNum)) {
1022  LLVM_DEBUG({
1023  dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1024  << OutlinerReruns + 1 << "\n";
1025  });
1026  break;
1027  }
1028  }
1029 
1030  return true;
1031 }
1032 
1033 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1034  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1035 
1036  // If the user passed -enable-machine-outliner=always or
1037  // -enable-machine-outliner, the pass will run on all functions in the module.
1038  // Otherwise, if the target supports default outlining, it will run on all
1039  // functions deemed by the target to be worth outlining from by default. Tell
1040  // the user how the outliner is running.
1041  LLVM_DEBUG({
1042  dbgs() << "Machine Outliner: Running on ";
1043  if (RunOnAllFunctions)
1044  dbgs() << "all functions";
1045  else
1046  dbgs() << "target-default functions";
1047  dbgs() << "\n";
1048  });
1049 
1050  // If the user specifies that they want to outline from linkonceodrs, set
1051  // it here.
1052  OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1053  InstructionMapper Mapper;
1054 
1055  // Prepare instruction mappings for the suffix tree.
1056  populateMapper(Mapper, M, MMI);
1057  std::vector<OutlinedFunction> FunctionList;
1058 
1059  // Find all of the outlining candidates.
1060  findCandidates(Mapper, FunctionList);
1061 
1062  // If we've requested size remarks, then collect the MI counts of every
1063  // function before outlining, and the MI counts after outlining.
1064  // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1065  // the pass manager's responsibility.
1066  // This could pretty easily be placed in outline instead, but because we
1067  // really ultimately *don't* want this here, it's done like this for now
1068  // instead.
1069 
1070  // Check if we want size remarks.
1071  bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1072  StringMap<unsigned> FunctionToInstrCount;
1073  if (ShouldEmitSizeRemarks)
1074  initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1075 
1076  // Outline each of the candidates and return true if something was outlined.
1077  bool OutlinedSomething =
1078  outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1079 
1080  // If we outlined something, we definitely changed the MI count of the
1081  // module. If we've asked for size remarks, then output them.
1082  // FIXME: This should be in the pass manager.
1083  if (ShouldEmitSizeRemarks && OutlinedSomething)
1084  emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1085 
1086  LLVM_DEBUG({
1087  if (!OutlinedSomething)
1088  dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1089  << " because no changes were found.\n";
1090  });
1091 
1092  return OutlinedSomething;
1093 }
i
i
Definition: README.txt:29
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:193
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DILocalScope::getSubprogram
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Definition: DebugInfoMetadata.cpp:965
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:830
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::DIBuilder
Definition: DIBuilder.h:42
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:51
llvm::Function
Definition: Function.h:59
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
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:642
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:156
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:1998
llvm::MachineOptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: MachineOptimizationRemarkEmitter.h:152
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
OptimizationRemarkEmitter.h
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:77
llvm::SPIRV::InstrList
SmallVector< MachineInstr * > InstrList
Definition: SPIRVModuleAnalysis.h:115
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:138
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:1397
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
llvm::StringMap::end
iterator end()
Definition: StringMap.h:204
llvm::MachineFunction::getInstructionCount
unsigned getInstructionCount() const
Return the number of MachineInstrs in this MachineFunction.
Definition: MachineFunction.h:913
DenseMap.h
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:889
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
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:217
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:275
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:1072
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::AArch64PACKey::DB
@ DB
Definition: AArch64BaseInfo.h:828
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1323
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:58
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:1735
llvm::UWTableKind
UWTableKind
Definition: CodeGen.h:121
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:882
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:682
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:77
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:763
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:197
llvm::MachineModuleInfo
This class contains meta information specific to a module.
Definition: MachineModuleInfo.h:74
llvm::MachineOptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: MachineOptimizationRemarkEmitter.h:110
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:145
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:870
llvm::MachineRegisterInfo::freezeReservedRegs
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
Definition: MachineRegisterInfo.cpp:511
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:479
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:672
llvm::cl::opt< bool >
llvm::DiagnosticInfoOptimizationBase::Argument
Used in the streaming interface as the general argument type.
Definition: DiagnosticInfo.h:426
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:77
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 used as as something other than the target of a terminator,...
Definition: MachineBasicBlock.h:231
llvm::MachineOptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: MachineOptimizationRemarkEmitter.h:84
llvm::MachineModuleInfoWrapperPass
Definition: MachineModuleInfo.h:203
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:390
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:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
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: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:445
DIBuilder.h
llvm::DICompileUnit
Compile unit.
Definition: DebugInfoMetadata.h:1363
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:446
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:279
SuffixTree.h
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:265
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:205
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::MachineFunction
Definition: MachineFunction.h:258
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:50
llvm::DiagnosticLocation
Definition: DiagnosticInfo.h:298
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:105
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
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:96
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
llvm::MachineFunctionProperties::reset
MachineFunctionProperties & reset(Property P)
Definition: MachineFunction.h:202
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:62
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
llvm::MachineFunction::addFrameInst
unsigned addFrameInst(const MCCFIInstruction &Inst)
Definition: MachineFunction.cpp:317
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:625
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1948
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:91
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:1336
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:288
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
Definition: MachineInstr.h:1775
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:177
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:224
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:309
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:344
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:281
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1851
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
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:98
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1485
llvm::omp::RTLDependInfoFields::Flags
@ Flags
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:411
raw_ostream.h
llvm::MachineInstrBundleIterator< MachineInstr >
CU
Definition: AArch64AsmBackend.cpp:505
InitializePasses.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:311
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineOutliner.cpp:81
llvm::DIFile
File.
Definition: DebugInfoMetadata.h:562
SmallSet.h
LivePhysRegs.h
MachineOutliner.h