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  MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
669  if (I->isCFIInstruction()) {
670  unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
671  MCCFIInstruction CFI = Instrs[CFIIndex];
672  (void)MF.addFrameInst(CFI);
673  }
674  NewMI->dropMemRefs(MF);
675 
676  // Don't keep debug information for outlined instructions.
677  NewMI->setDebugLoc(DebugLoc());
678  MBB.insert(MBB.end(), NewMI);
679  }
680 
681  // Set normal properties for a late MachineFunction.
687 
688  // Compute live-in set for outlined fn
689  const MachineRegisterInfo &MRI = MF.getRegInfo();
691  LivePhysRegs LiveIns(TRI);
692  for (auto &Cand : OF.Candidates) {
693  // Figure out live-ins at the first instruction.
694  MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
695  LivePhysRegs CandLiveIns(TRI);
696  CandLiveIns.addLiveOuts(OutlineBB);
697  for (const MachineInstr &MI :
698  reverse(make_range(Cand.front(), OutlineBB.end())))
699  CandLiveIns.stepBackward(MI);
700 
701  // The live-in set for the outlined function is the union of the live-ins
702  // from all the outlining points.
703  for (MCPhysReg Reg : CandLiveIns)
704  LiveIns.addReg(Reg);
705  }
706  addLiveIns(MBB, LiveIns);
707 
708  TII.buildOutlinedFrame(MBB, MF, OF);
709 
710  // If there's a DISubprogram associated with this outlined function, then
711  // emit debug info for the outlined function.
712  if (DISubprogram *SP = getSubprogramOrNull(OF)) {
713  // We have a DISubprogram. Get its DICompileUnit.
714  DICompileUnit *CU = SP->getUnit();
715  DIBuilder DB(M, true, CU);
716  DIFile *Unit = SP->getFile();
717  Mangler Mg;
718  // Get the mangled name of the function for the linkage name.
719  std::string Dummy;
720  llvm::raw_string_ostream MangledNameStream(Dummy);
721  Mg.getNameWithPrefix(MangledNameStream, F, false);
722 
723  DISubprogram *OutlinedSP = DB.createFunction(
724  Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
725  Unit /* File */,
726  0 /* Line 0 is reserved for compiler-generated code. */,
727  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
728  0, /* Line 0 is reserved for compiler-generated code. */
729  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
730  /* Outlined code is optimized code by definition. */
731  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
732 
733  // Don't add any new variables to the subprogram.
734  DB.finalizeSubprogram(OutlinedSP);
735 
736  // Attach subprogram to the function.
737  F->setSubprogram(OutlinedSP);
738  // We're done with the DIBuilder.
739  DB.finalize();
740  }
741 
742  return &MF;
743 }
744 
745 bool MachineOutliner::outline(Module &M,
746  std::vector<OutlinedFunction> &FunctionList,
747  InstructionMapper &Mapper,
748  unsigned &OutlinedFunctionNum) {
749 
750  bool OutlinedSomething = false;
751 
752  // Sort by benefit. The most beneficial functions should be outlined first.
753  llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
754  const OutlinedFunction &RHS) {
755  return LHS.getBenefit() > RHS.getBenefit();
756  });
757 
758  // Walk over each function, outlining them as we go along. Functions are
759  // outlined greedily, based off the sort above.
760  for (OutlinedFunction &OF : FunctionList) {
761  // If we outlined something that overlapped with a candidate in a previous
762  // step, then we can't outline from it.
763  erase_if(OF.Candidates, [&Mapper](Candidate &C) {
764  return std::any_of(
765  Mapper.UnsignedVec.begin() + C.getStartIdx(),
766  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
767  [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
768  });
769 
770  // If we made it unbeneficial to outline this function, skip it.
771  if (OF.getBenefit() < 1)
772  continue;
773 
774  // It's beneficial. Create the function and outline its sequence's
775  // occurrences.
776  OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
777  emitOutlinedFunctionRemark(OF);
778  FunctionsCreated++;
779  OutlinedFunctionNum++; // Created a function, move to the next name.
780  MachineFunction *MF = OF.MF;
781  const TargetSubtargetInfo &STI = MF->getSubtarget();
782  const TargetInstrInfo &TII = *STI.getInstrInfo();
783 
784  // Replace occurrences of the sequence with calls to the new function.
785  for (Candidate &C : OF.Candidates) {
786  MachineBasicBlock &MBB = *C.getMBB();
787  MachineBasicBlock::iterator StartIt = C.front();
788  MachineBasicBlock::iterator EndIt = C.back();
789 
790  // Insert the call.
791  auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
792 
793  // If the caller tracks liveness, then we need to make sure that
794  // anything we outline doesn't break liveness assumptions. The outlined
795  // functions themselves currently don't track liveness, but we should
796  // make sure that the ranges we yank things out of aren't wrong.
799  // The following code is to add implicit def operands to the call
800  // instruction. It also updates call site information for moved
801  // code.
802  SmallSet<Register, 2> UseRegs, DefRegs;
803  // Copy over the defs in the outlined range.
804  // First inst in outlined range <-- Anything that's defined in this
805  // ... .. range has to be added as an
806  // implicit Last inst in outlined range <-- def to the call
807  // instruction. Also remove call site information for outlined block
808  // of code. The exposed uses need to be copied in the outlined range.
810  Iter = EndIt.getReverse(),
811  Last = std::next(CallInst.getReverse());
812  Iter != Last; Iter++) {
813  MachineInstr *MI = &*Iter;
814  SmallSet<Register, 2> InstrUseRegs;
815  for (MachineOperand &MOP : MI->operands()) {
816  // Skip over anything that isn't a register.
817  if (!MOP.isReg())
818  continue;
819 
820  if (MOP.isDef()) {
821  // Introduce DefRegs set to skip the redundant register.
822  DefRegs.insert(MOP.getReg());
823  if (UseRegs.count(MOP.getReg()) &&
824  !InstrUseRegs.count(MOP.getReg()))
825  // Since the regiester is modeled as defined,
826  // it is not necessary to be put in use register set.
827  UseRegs.erase(MOP.getReg());
828  } else if (!MOP.isUndef()) {
829  // Any register which is not undefined should
830  // be put in the use register set.
831  UseRegs.insert(MOP.getReg());
832  InstrUseRegs.insert(MOP.getReg());
833  }
834  }
835  if (MI->isCandidateForCallSiteEntry())
836  MI->getMF()->eraseCallSiteInfo(MI);
837  }
838 
839  for (const Register &I : DefRegs)
840  // If it's a def, add it to the call instruction.
841  CallInst->addOperand(
842  MachineOperand::CreateReg(I, true, /* isDef = true */
843  true /* isImp = true */));
844 
845  for (const Register &I : UseRegs)
846  // If it's a exposed use, add it to the call instruction.
847  CallInst->addOperand(
848  MachineOperand::CreateReg(I, false, /* isDef = false */
849  true /* isImp = true */));
850  }
851 
852  // Erase from the point after where the call was inserted up to, and
853  // including, the final instruction in the sequence.
854  // Erase needs one past the end, so we need std::next there too.
855  MBB.erase(std::next(StartIt), std::next(EndIt));
856 
857  // Keep track of what we removed by marking them all as -1.
858  std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
859  Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
860  [](unsigned &I) { I = static_cast<unsigned>(-1); });
861  OutlinedSomething = true;
862 
863  // Statistics.
864  NumOutlined++;
865  }
866  }
867 
868  LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
869  return OutlinedSomething;
870 }
871 
872 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
873  MachineModuleInfo &MMI) {
874  // Build instruction mappings for each function in the module. Start by
875  // iterating over each Function in M.
876  for (Function &F : M) {
877 
878  // If there's nothing in F, then there's no reason to try and outline from
879  // it.
880  if (F.empty())
881  continue;
882 
883  // There's something in F. Check if it has a MachineFunction associated with
884  // it.
886 
887  // If it doesn't, then there's nothing to outline from. Move to the next
888  // Function.
889  if (!MF)
890  continue;
891 
892  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
893 
894  if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
895  continue;
896 
897  // We have a MachineFunction. Ask the target if it's suitable for outlining.
898  // If it isn't, then move on to the next Function in the module.
899  if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
900  continue;
901 
902  // We have a function suitable for outlining. Iterate over every
903  // MachineBasicBlock in MF and try to map its instructions to a list of
904  // unsigned integers.
905  for (MachineBasicBlock &MBB : *MF) {
906  // If there isn't anything in MBB, then there's no point in outlining from
907  // it.
908  // If there are fewer than 2 instructions in the MBB, then it can't ever
909  // contain something worth outlining.
910  // FIXME: This should be based off of the maximum size in B of an outlined
911  // call versus the size in B of the MBB.
912  if (MBB.empty() || MBB.size() < 2)
913  continue;
914 
915  // Check if MBB could be the target of an indirect branch. If it is, then
916  // we don't want to outline from it.
917  if (MBB.hasAddressTaken())
918  continue;
919 
920  // MBB is suitable for outlining. Map it to a list of unsigneds.
921  Mapper.convertToUnsignedVec(MBB, *TII);
922  }
923 
924  // Statistics.
925  UnsignedVecSize = Mapper.UnsignedVec.size();
926  }
927 }
928 
929 void MachineOutliner::initSizeRemarkInfo(
930  const Module &M, const MachineModuleInfo &MMI,
931  StringMap<unsigned> &FunctionToInstrCount) {
932  // Collect instruction counts for every function. We'll use this to emit
933  // per-function size remarks later.
934  for (const Function &F : M) {
936 
937  // We only care about MI counts here. If there's no MachineFunction at this
938  // point, then there won't be after the outliner runs, so let's move on.
939  if (!MF)
940  continue;
941  FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
942  }
943 }
944 
945 void MachineOutliner::emitInstrCountChangedRemark(
946  const Module &M, const MachineModuleInfo &MMI,
947  const StringMap<unsigned> &FunctionToInstrCount) {
948  // Iterate over each function in the module and emit remarks.
949  // Note that we won't miss anything by doing this, because the outliner never
950  // deletes functions.
951  for (const Function &F : M) {
953 
954  // The outliner never deletes functions. If we don't have a MF here, then we
955  // didn't have one prior to outlining either.
956  if (!MF)
957  continue;
958 
959  std::string Fname = std::string(F.getName());
960  unsigned FnCountAfter = MF->getInstructionCount();
961  unsigned FnCountBefore = 0;
962 
963  // Check if the function was recorded before.
964  auto It = FunctionToInstrCount.find(Fname);
965 
966  // Did we have a previously-recorded size? If yes, then set FnCountBefore
967  // to that.
968  if (It != FunctionToInstrCount.end())
969  FnCountBefore = It->second;
970 
971  // Compute the delta and emit a remark if there was a change.
972  int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
973  static_cast<int64_t>(FnCountBefore);
974  if (FnDelta == 0)
975  continue;
976 
978  MORE.emit([&]() {
979  MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
980  DiagnosticLocation(), &MF->front());
981  R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
982  << ": Function: "
983  << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
984  << ": MI instruction count changed from "
985  << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
986  FnCountBefore)
987  << " to "
988  << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
989  FnCountAfter)
990  << "; Delta: "
991  << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
992  return R;
993  });
994  }
995 }
996 
997 bool MachineOutliner::runOnModule(Module &M) {
998  // Check if there's anything in the module. If it's empty, then there's
999  // nothing to outline.
1000  if (M.empty())
1001  return false;
1002 
1003  // Number to append to the current outlined function.
1004  unsigned OutlinedFunctionNum = 0;
1005 
1006  OutlineRepeatedNum = 0;
1007  if (!doOutline(M, OutlinedFunctionNum))
1008  return false;
1009 
1010  for (unsigned I = 0; I < OutlinerReruns; ++I) {
1011  OutlinedFunctionNum = 0;
1012  OutlineRepeatedNum++;
1013  if (!doOutline(M, OutlinedFunctionNum)) {
1014  LLVM_DEBUG({
1015  dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1016  << OutlinerReruns + 1 << "\n";
1017  });
1018  break;
1019  }
1020  }
1021 
1022  return true;
1023 }
1024 
1025 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1026  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1027 
1028  // If the user passed -enable-machine-outliner=always or
1029  // -enable-machine-outliner, the pass will run on all functions in the module.
1030  // Otherwise, if the target supports default outlining, it will run on all
1031  // functions deemed by the target to be worth outlining from by default. Tell
1032  // the user how the outliner is running.
1033  LLVM_DEBUG({
1034  dbgs() << "Machine Outliner: Running on ";
1035  if (RunOnAllFunctions)
1036  dbgs() << "all functions";
1037  else
1038  dbgs() << "target-default functions";
1039  dbgs() << "\n";
1040  });
1041 
1042  // If the user specifies that they want to outline from linkonceodrs, set
1043  // it here.
1044  OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1045  InstructionMapper Mapper;
1046 
1047  // Prepare instruction mappings for the suffix tree.
1048  populateMapper(Mapper, M, MMI);
1049  std::vector<OutlinedFunction> FunctionList;
1050 
1051  // Find all of the outlining candidates.
1052  findCandidates(Mapper, FunctionList);
1053 
1054  // If we've requested size remarks, then collect the MI counts of every
1055  // function before outlining, and the MI counts after outlining.
1056  // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1057  // the pass manager's responsibility.
1058  // This could pretty easily be placed in outline instead, but because we
1059  // really ultimately *don't* want this here, it's done like this for now
1060  // instead.
1061 
1062  // Check if we want size remarks.
1063  bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1064  StringMap<unsigned> FunctionToInstrCount;
1065  if (ShouldEmitSizeRemarks)
1066  initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1067 
1068  // Outline each of the candidates and return true if something was outlined.
1069  bool OutlinedSomething =
1070  outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1071 
1072  // If we outlined something, we definitely changed the MI count of the
1073  // module. If we've asked for size remarks, then output them.
1074  // FIXME: This should be in the pass manager.
1075  if (ShouldEmitSizeRemarks && OutlinedSomething)
1076  emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1077 
1078  LLVM_DEBUG({
1079  if (!OutlinedSomething)
1080  dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1081  << " because no changes were found.\n";
1082  });
1083 
1084  return OutlinedSomething;
1085 }
i
i
Definition: README.txt:29
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:176
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::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:1797
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:1369
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:865
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:841
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:1620
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:240
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:1023
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:1295
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:1607
llvm::UWTableKind
UWTableKind
Definition: CodeGen.h:100
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:834
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:650
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
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:731
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
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:180
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:822
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:640
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::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1600
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:385
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:1316
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:441
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:241
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:1813
TargetSubtargetInfo.h
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:185
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:1751
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:1308
llvm::MachineOperand::getCFIIndex
unsigned getCFIIndex() const
Definition: MachineOperand.h:587
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:256
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
Definition: MachineInstr.h:1724
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:312
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:277
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:86
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:249
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1797
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:1474
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:279
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:37
LivePhysRegs.h
MachineOutliner.h