LLVM  6.0.0svn
MachineOutliner.cpp
Go to the documentation of this file.
1 //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// Replaces repeated sequences of instructions with function calls.
12 ///
13 /// This works by placing every instruction from every basic block in a
14 /// suffix tree, and repeatedly querying that tree for repeated sequences of
15 /// instructions. If a sequence of instructions appears often, then it ought
16 /// to be beneficial to pull out into a function.
17 ///
18 /// The MachineOutliner communicates with a given target using hooks defined in
19 /// TargetInstrInfo.h. The target supplies the outliner with information on how
20 /// a specific sequence of instructions should be outlined. This information
21 /// is used to deduce the number of instructions necessary to
22 ///
23 /// * Create an outlined function
24 /// * Call that outlined function
25 ///
26 /// Targets must implement
27 /// * getOutliningCandidateInfo
28 /// * insertOutlinerEpilogue
29 /// * insertOutlinedCall
30 /// * insertOutlinerPrologue
31 /// * isFunctionSafeToOutlineFrom
32 ///
33 /// in order to make use of the MachineOutliner.
34 ///
35 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
36 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
37 /// how this pass works, the talk is available on YouTube at
38 ///
39 /// https://www.youtube.com/watch?v=yorld-WSOeU
40 ///
41 /// The slides for the talk are available at
42 ///
43 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
44 ///
45 /// The talk provides an overview of how the outliner finds candidates and
46 /// ultimately outlines them. It describes how the main data structure for this
47 /// pass, the suffix tree, is queried and purged for candidates. It also gives
48 /// a simplified suffix tree construction algorithm for suffix trees based off
49 /// of the algorithm actually used here, Ukkonen's algorithm.
50 ///
51 /// For the original RFC for this pass, please see
52 ///
53 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
54 ///
55 /// For more information on the suffix tree data structure, please see
56 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
57 ///
58 //===----------------------------------------------------------------------===//
59 #include "llvm/ADT/DenseMap.h"
60 #include "llvm/ADT/Statistic.h"
61 #include "llvm/ADT/Twine.h"
67 #include "llvm/CodeGen/Passes.h"
71 #include "llvm/IR/IRBuilder.h"
72 #include "llvm/Support/Allocator.h"
73 #include "llvm/Support/Debug.h"
76 #include <functional>
77 #include <map>
78 #include <sstream>
79 #include <tuple>
80 #include <vector>
81 
82 #define DEBUG_TYPE "machine-outliner"
83 
84 using namespace llvm;
85 using namespace ore;
86 
87 STATISTIC(NumOutlined, "Number of candidates outlined");
88 STATISTIC(FunctionsCreated, "Number of functions created");
89 
90 namespace {
91 
92 /// \brief An individual sequence of instructions to be replaced with a call to
93 /// an outlined function.
94 struct Candidate {
95 private:
96  /// The start index of this \p Candidate in the instruction list.
97  unsigned StartIdx;
98 
99  /// The number of instructions in this \p Candidate.
100  unsigned Len;
101 
102 public:
103  /// Set to false if the candidate overlapped with another candidate.
104  bool InCandidateList = true;
105 
106  /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of
107  /// \p OutlinedFunctions.
108  unsigned FunctionIdx;
109 
110  /// Contains all target-specific information for this \p Candidate.
112 
113  /// Return the number of instructions in this Candidate.
114  unsigned getLength() const { return Len; }
115 
116  /// Return the start index of this candidate.
117  unsigned getStartIdx() const { return StartIdx; }
118 
119  // Return the end index of this candidate.
120  unsigned getEndIdx() const { return StartIdx + Len - 1; }
121 
122  /// \brief The number of instructions that would be saved by outlining every
123  /// candidate of this type.
124  ///
125  /// This is a fixed value which is not updated during the candidate pruning
126  /// process. It is only used for deciding which candidate to keep if two
127  /// candidates overlap. The true benefit is stored in the OutlinedFunction
128  /// for some given candidate.
129  unsigned Benefit = 0;
130 
131  Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx)
132  : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
133 
134  Candidate() {}
135 
136  /// \brief Used to ensure that \p Candidates are outlined in an order that
137  /// preserves the start and end indices of other \p Candidates.
138  bool operator<(const Candidate &RHS) const {
139  return getStartIdx() > RHS.getStartIdx();
140  }
141 };
142 
143 /// \brief The information necessary to create an outlined function for some
144 /// class of candidate.
145 struct OutlinedFunction {
146 
147 private:
148  /// The number of candidates for this \p OutlinedFunction.
149  unsigned OccurrenceCount = 0;
150 
151 public:
152  std::vector<std::shared_ptr<Candidate>> Candidates;
153 
154  /// The actual outlined function created.
155  /// This is initialized after we go through and create the actual function.
156  MachineFunction *MF = nullptr;
157 
158  /// A number assigned to this function which appears at the end of its name.
159  unsigned Name;
160 
161  /// \brief The sequence of integers corresponding to the instructions in this
162  /// function.
163  std::vector<unsigned> Sequence;
164 
165  /// Contains all target-specific information for this \p OutlinedFunction.
167 
168  /// Return the number of candidates for this \p OutlinedFunction.
169  unsigned getOccurrenceCount() { return OccurrenceCount; }
170 
171  /// Decrement the occurrence count of this OutlinedFunction and return the
172  /// new count.
173  unsigned decrement() {
174  assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
175  OccurrenceCount--;
176  return getOccurrenceCount();
177  }
178 
179  /// \brief Return the number of instructions it would take to outline this
180  /// function.
181  unsigned getOutliningCost() {
182  return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() +
183  MInfo.FrameOverhead;
184  }
185 
186  /// \brief Return the number of instructions that would be saved by outlining
187  /// this function.
188  unsigned getBenefit() {
189  unsigned NotOutlinedCost = OccurrenceCount * Sequence.size();
190  unsigned OutlinedCost = getOutliningCost();
191  return (NotOutlinedCost < OutlinedCost) ? 0
192  : NotOutlinedCost - OutlinedCost;
193  }
194 
195  OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
196  const std::vector<unsigned> &Sequence,
198  : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
199  MInfo(MInfo) {}
200 };
201 
202 /// Represents an undefined index in the suffix tree.
203 const unsigned EmptyIdx = -1;
204 
205 /// A node in a suffix tree which represents a substring or suffix.
206 ///
207 /// Each node has either no children or at least two children, with the root
208 /// being a exception in the empty tree.
209 ///
210 /// Children are represented as a map between unsigned integers and nodes. If
211 /// a node N has a child M on unsigned integer k, then the mapping represented
212 /// by N is a proper prefix of the mapping represented by M. Note that this,
213 /// although similar to a trie is somewhat different: each node stores a full
214 /// substring of the full mapping rather than a single character state.
215 ///
216 /// Each internal node contains a pointer to the internal node representing
217 /// the same string, but with the first character chopped off. This is stored
218 /// in \p Link. Each leaf node stores the start index of its respective
219 /// suffix in \p SuffixIdx.
220 struct SuffixTreeNode {
221 
222  /// The children of this node.
223  ///
224  /// A child existing on an unsigned integer implies that from the mapping
225  /// represented by the current node, there is a way to reach another
226  /// mapping by tacking that character on the end of the current string.
228 
229  /// A flag set to false if the node has been pruned from the tree.
230  bool IsInTree = true;
231 
232  /// The start index of this node's substring in the main string.
233  unsigned StartIdx = EmptyIdx;
234 
235  /// The end index of this node's substring in the main string.
236  ///
237  /// Every leaf node must have its \p EndIdx incremented at the end of every
238  /// step in the construction algorithm. To avoid having to update O(N)
239  /// nodes individually at the end of every step, the end index is stored
240  /// as a pointer.
241  unsigned *EndIdx = nullptr;
242 
243  /// For leaves, the start index of the suffix represented by this node.
244  ///
245  /// For all other nodes, this is ignored.
246  unsigned SuffixIdx = EmptyIdx;
247 
248  /// \brief For internal nodes, a pointer to the internal node representing
249  /// the same sequence with the first character chopped off.
250  ///
251  /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
252  /// Ukkonen's algorithm does to achieve linear-time construction is
253  /// keep track of which node the next insert should be at. This makes each
254  /// insert O(1), and there are a total of O(N) inserts. The suffix link
255  /// helps with inserting children of internal nodes.
256  ///
257  /// Say we add a child to an internal node with associated mapping S. The
258  /// next insertion must be at the node representing S - its first character.
259  /// This is given by the way that we iteratively build the tree in Ukkonen's
260  /// algorithm. The main idea is to look at the suffixes of each prefix in the
261  /// string, starting with the longest suffix of the prefix, and ending with
262  /// the shortest. Therefore, if we keep pointers between such nodes, we can
263  /// move to the next insertion point in O(1) time. If we don't, then we'd
264  /// have to query from the root, which takes O(N) time. This would make the
265  /// construction algorithm O(N^2) rather than O(N).
266  SuffixTreeNode *Link = nullptr;
267 
268  /// The parent of this node. Every node except for the root has a parent.
269  SuffixTreeNode *Parent = nullptr;
270 
271  /// The number of times this node's string appears in the tree.
272  ///
273  /// This is equal to the number of leaf children of the string. It represents
274  /// the number of suffixes that the node's string is a prefix of.
275  unsigned OccurrenceCount = 0;
276 
277  /// The length of the string formed by concatenating the edge labels from the
278  /// root to this node.
279  unsigned ConcatLen = 0;
280 
281  /// Returns true if this node is a leaf.
282  bool isLeaf() const { return SuffixIdx != EmptyIdx; }
283 
284  /// Returns true if this node is the root of its owning \p SuffixTree.
285  bool isRoot() const { return StartIdx == EmptyIdx; }
286 
287  /// Return the number of elements in the substring associated with this node.
288  size_t size() const {
289 
290  // Is it the root? If so, it's the empty string so return 0.
291  if (isRoot())
292  return 0;
293 
294  assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
295 
296  // Size = the number of elements in the string.
297  // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
298  return *EndIdx - StartIdx + 1;
299  }
300 
301  SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
302  SuffixTreeNode *Parent)
303  : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
304 
305  SuffixTreeNode() {}
306 };
307 
308 /// A data structure for fast substring queries.
309 ///
310 /// Suffix trees represent the suffixes of their input strings in their leaves.
311 /// A suffix tree is a type of compressed trie structure where each node
312 /// represents an entire substring rather than a single character. Each leaf
313 /// of the tree is a suffix.
314 ///
315 /// A suffix tree can be seen as a type of state machine where each state is a
316 /// substring of the full string. The tree is structured so that, for a string
317 /// of length N, there are exactly N leaves in the tree. This structure allows
318 /// us to quickly find repeated substrings of the input string.
319 ///
320 /// In this implementation, a "string" is a vector of unsigned integers.
321 /// These integers may result from hashing some data type. A suffix tree can
322 /// contain 1 or many strings, which can then be queried as one large string.
323 ///
324 /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
325 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
326 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
327 /// paper is available at
328 ///
329 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
330 class SuffixTree {
331 public:
332  /// Stores each leaf node in the tree.
333  ///
334  /// This is used for finding outlining candidates.
335  std::vector<SuffixTreeNode *> LeafVector;
336 
337  /// Each element is an integer representing an instruction in the module.
338  ArrayRef<unsigned> Str;
339 
340 private:
341  /// Maintains each node in the tree.
343 
344  /// The root of the suffix tree.
345  ///
346  /// The root represents the empty string. It is maintained by the
347  /// \p NodeAllocator like every other node in the tree.
348  SuffixTreeNode *Root = nullptr;
349 
350  /// Maintains the end indices of the internal nodes in the tree.
351  ///
352  /// Each internal node is guaranteed to never have its end index change
353  /// during the construction algorithm; however, leaves must be updated at
354  /// every step. Therefore, we need to store leaf end indices by reference
355  /// to avoid updating O(N) leaves at every step of construction. Thus,
356  /// every internal node must be allocated its own end index.
357  BumpPtrAllocator InternalEndIdxAllocator;
358 
359  /// The end index of each leaf in the tree.
360  unsigned LeafEndIdx = -1;
361 
362  /// \brief Helper struct which keeps track of the next insertion point in
363  /// Ukkonen's algorithm.
364  struct ActiveState {
365  /// The next node to insert at.
366  SuffixTreeNode *Node;
367 
368  /// The index of the first character in the substring currently being added.
369  unsigned Idx = EmptyIdx;
370 
371  /// The length of the substring we have to add at the current step.
372  unsigned Len = 0;
373  };
374 
375  /// \brief The point the next insertion will take place at in the
376  /// construction algorithm.
377  ActiveState Active;
378 
379  /// Allocate a leaf node and add it to the tree.
380  ///
381  /// \param Parent The parent of this node.
382  /// \param StartIdx The start index of this node's associated string.
383  /// \param Edge The label on the edge leaving \p Parent to this node.
384  ///
385  /// \returns A pointer to the allocated leaf node.
386  SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
387  unsigned Edge) {
388 
389  assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
390 
391  SuffixTreeNode *N = new (NodeAllocator.Allocate())
392  SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
393  Parent.Children[Edge] = N;
394 
395  return N;
396  }
397 
398  /// Allocate an internal node and add it to the tree.
399  ///
400  /// \param Parent The parent of this node. Only null when allocating the root.
401  /// \param StartIdx The start index of this node's associated string.
402  /// \param EndIdx The end index of this node's associated string.
403  /// \param Edge The label on the edge leaving \p Parent to this node.
404  ///
405  /// \returns A pointer to the allocated internal node.
406  SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
407  unsigned EndIdx, unsigned Edge) {
408 
409  assert(StartIdx <= EndIdx && "String can't start after it ends!");
410  assert(!(!Parent && StartIdx != EmptyIdx) &&
411  "Non-root internal nodes must have parents!");
412 
413  unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
414  SuffixTreeNode *N = new (NodeAllocator.Allocate())
415  SuffixTreeNode(StartIdx, E, Root, Parent);
416  if (Parent)
417  Parent->Children[Edge] = N;
418 
419  return N;
420  }
421 
422  /// \brief Set the suffix indices of the leaves to the start indices of their
423  /// respective suffixes. Also stores each leaf in \p LeafVector at its
424  /// respective suffix index.
425  ///
426  /// \param[in] CurrNode The node currently being visited.
427  /// \param CurrIdx The current index of the string being visited.
428  void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
429 
430  bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
431 
432  // Store the length of the concatenation of all strings from the root to
433  // this node.
434  if (!CurrNode.isRoot()) {
435  if (CurrNode.ConcatLen == 0)
436  CurrNode.ConcatLen = CurrNode.size();
437 
438  if (CurrNode.Parent)
439  CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
440  }
441 
442  // Traverse the tree depth-first.
443  for (auto &ChildPair : CurrNode.Children) {
444  assert(ChildPair.second && "Node had a null child!");
445  setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
446  }
447 
448  // Is this node a leaf?
449  if (IsLeaf) {
450  // If yes, give it a suffix index and bump its parent's occurrence count.
451  CurrNode.SuffixIdx = Str.size() - CurrIdx;
452  assert(CurrNode.Parent && "CurrNode had no parent!");
453  CurrNode.Parent->OccurrenceCount++;
454 
455  // Store the leaf in the leaf vector for pruning later.
456  LeafVector[CurrNode.SuffixIdx] = &CurrNode;
457  }
458  }
459 
460  /// \brief Construct the suffix tree for the prefix of the input ending at
461  /// \p EndIdx.
462  ///
463  /// Used to construct the full suffix tree iteratively. At the end of each
464  /// step, the constructed suffix tree is either a valid suffix tree, or a
465  /// suffix tree with implicit suffixes. At the end of the final step, the
466  /// suffix tree is a valid tree.
467  ///
468  /// \param EndIdx The end index of the current prefix in the main string.
469  /// \param SuffixesToAdd The number of suffixes that must be added
470  /// to complete the suffix tree at the current phase.
471  ///
472  /// \returns The number of suffixes that have not been added at the end of
473  /// this step.
474  unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
475  SuffixTreeNode *NeedsLink = nullptr;
476 
477  while (SuffixesToAdd > 0) {
478 
479  // Are we waiting to add anything other than just the last character?
480  if (Active.Len == 0) {
481  // If not, then say the active index is the end index.
482  Active.Idx = EndIdx;
483  }
484 
485  assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
486 
487  // The first character in the current substring we're looking at.
488  unsigned FirstChar = Str[Active.Idx];
489 
490  // Have we inserted anything starting with FirstChar at the current node?
491  if (Active.Node->Children.count(FirstChar) == 0) {
492  // If not, then we can just insert a leaf and move too the next step.
493  insertLeaf(*Active.Node, EndIdx, FirstChar);
494 
495  // The active node is an internal node, and we visited it, so it must
496  // need a link if it doesn't have one.
497  if (NeedsLink) {
498  NeedsLink->Link = Active.Node;
499  NeedsLink = nullptr;
500  }
501  } else {
502  // There's a match with FirstChar, so look for the point in the tree to
503  // insert a new node.
504  SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
505 
506  unsigned SubstringLen = NextNode->size();
507 
508  // Is the current suffix we're trying to insert longer than the size of
509  // the child we want to move to?
510  if (Active.Len >= SubstringLen) {
511  // If yes, then consume the characters we've seen and move to the next
512  // node.
513  Active.Idx += SubstringLen;
514  Active.Len -= SubstringLen;
515  Active.Node = NextNode;
516  continue;
517  }
518 
519  // Otherwise, the suffix we're trying to insert must be contained in the
520  // next node we want to move to.
521  unsigned LastChar = Str[EndIdx];
522 
523  // Is the string we're trying to insert a substring of the next node?
524  if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
525  // If yes, then we're done for this step. Remember our insertion point
526  // and move to the next end index. At this point, we have an implicit
527  // suffix tree.
528  if (NeedsLink && !Active.Node->isRoot()) {
529  NeedsLink->Link = Active.Node;
530  NeedsLink = nullptr;
531  }
532 
533  Active.Len++;
534  break;
535  }
536 
537  // The string we're trying to insert isn't a substring of the next node,
538  // but matches up to a point. Split the node.
539  //
540  // For example, say we ended our search at a node n and we're trying to
541  // insert ABD. Then we'll create a new node s for AB, reduce n to just
542  // representing C, and insert a new leaf node l to represent d. This
543  // allows us to ensure that if n was a leaf, it remains a leaf.
544  //
545  // | ABC ---split---> | AB
546  // n s
547  // C / \ D
548  // n l
549 
550  // The node s from the diagram
551  SuffixTreeNode *SplitNode =
552  insertInternalNode(Active.Node, NextNode->StartIdx,
553  NextNode->StartIdx + Active.Len - 1, FirstChar);
554 
555  // Insert the new node representing the new substring into the tree as
556  // a child of the split node. This is the node l from the diagram.
557  insertLeaf(*SplitNode, EndIdx, LastChar);
558 
559  // Make the old node a child of the split node and update its start
560  // index. This is the node n from the diagram.
561  NextNode->StartIdx += Active.Len;
562  NextNode->Parent = SplitNode;
563  SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
564 
565  // SplitNode is an internal node, update the suffix link.
566  if (NeedsLink)
567  NeedsLink->Link = SplitNode;
568 
569  NeedsLink = SplitNode;
570  }
571 
572  // We've added something new to the tree, so there's one less suffix to
573  // add.
574  SuffixesToAdd--;
575 
576  if (Active.Node->isRoot()) {
577  if (Active.Len > 0) {
578  Active.Len--;
579  Active.Idx = EndIdx - SuffixesToAdd + 1;
580  }
581  } else {
582  // Start the next phase at the next smallest suffix.
583  Active.Node = Active.Node->Link;
584  }
585  }
586 
587  return SuffixesToAdd;
588  }
589 
590 public:
591  /// Construct a suffix tree from a sequence of unsigned integers.
592  ///
593  /// \param Str The string to construct the suffix tree for.
594  SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
595  Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
596  Root->IsInTree = true;
597  Active.Node = Root;
598  LeafVector = std::vector<SuffixTreeNode *>(Str.size());
599 
600  // Keep track of the number of suffixes we have to add of the current
601  // prefix.
602  unsigned SuffixesToAdd = 0;
603  Active.Node = Root;
604 
605  // Construct the suffix tree iteratively on each prefix of the string.
606  // PfxEndIdx is the end index of the current prefix.
607  // End is one past the last element in the string.
608  for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
609  PfxEndIdx++) {
610  SuffixesToAdd++;
611  LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
612  SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
613  }
614 
615  // Set the suffix indices of each leaf.
616  assert(Root && "Root node can't be nullptr!");
617  setSuffixIndices(*Root, 0);
618  }
619 };
620 
621 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
622 struct InstructionMapper {
623 
624  /// \brief The next available integer to assign to a \p MachineInstr that
625  /// cannot be outlined.
626  ///
627  /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
628  unsigned IllegalInstrNumber = -3;
629 
630  /// \brief The next available integer to assign to a \p MachineInstr that can
631  /// be outlined.
632  unsigned LegalInstrNumber = 0;
633 
634  /// Correspondence from \p MachineInstrs to unsigned integers.
636  InstructionIntegerMap;
637 
638  /// Corresponcence from unsigned integers to \p MachineInstrs.
639  /// Inverse of \p InstructionIntegerMap.
640  DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
641 
642  /// The vector of unsigned integers that the module is mapped to.
643  std::vector<unsigned> UnsignedVec;
644 
645  /// \brief Stores the location of the instruction associated with the integer
646  /// at index i in \p UnsignedVec for each index i.
647  std::vector<MachineBasicBlock::iterator> InstrList;
648 
649  /// \brief Maps \p *It to a legal integer.
650  ///
651  /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
652  /// \p IntegerInstructionMap, and \p LegalInstrNumber.
653  ///
654  /// \returns The integer that \p *It was mapped to.
655  unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
656 
657  // Get the integer for this instruction or give it the current
658  // LegalInstrNumber.
659  InstrList.push_back(It);
660  MachineInstr &MI = *It;
661  bool WasInserted;
663  ResultIt;
664  std::tie(ResultIt, WasInserted) =
665  InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
666  unsigned MINumber = ResultIt->second;
667 
668  // There was an insertion.
669  if (WasInserted) {
670  LegalInstrNumber++;
671  IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
672  }
673 
674  UnsignedVec.push_back(MINumber);
675 
676  // Make sure we don't overflow or use any integers reserved by the DenseMap.
677  if (LegalInstrNumber >= IllegalInstrNumber)
678  report_fatal_error("Instruction mapping overflow!");
679 
680  assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
681  "Tried to assign DenseMap tombstone or empty key to instruction.");
682  assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
683  "Tried to assign DenseMap tombstone or empty key to instruction.");
684 
685  return MINumber;
686  }
687 
688  /// Maps \p *It to an illegal integer.
689  ///
690  /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
691  ///
692  /// \returns The integer that \p *It was mapped to.
693  unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
694  unsigned MINumber = IllegalInstrNumber;
695 
696  InstrList.push_back(It);
697  UnsignedVec.push_back(IllegalInstrNumber);
698  IllegalInstrNumber--;
699 
700  assert(LegalInstrNumber < IllegalInstrNumber &&
701  "Instruction mapping overflow!");
702 
703  assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
704  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
705 
706  assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
707  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
708 
709  return MINumber;
710  }
711 
712  /// \brief Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
713  /// and appends it to \p UnsignedVec and \p InstrList.
714  ///
715  /// Two instructions are assigned the same integer if they are identical.
716  /// If an instruction is deemed unsafe to outline, then it will be assigned an
717  /// unique integer. The resulting mapping is placed into a suffix tree and
718  /// queried for candidates.
719  ///
720  /// \param MBB The \p MachineBasicBlock to be translated into integers.
721  /// \param TRI \p TargetRegisterInfo for the module.
722  /// \param TII \p TargetInstrInfo for the module.
723  void convertToUnsignedVec(MachineBasicBlock &MBB,
724  const TargetRegisterInfo &TRI,
725  const TargetInstrInfo &TII) {
726  for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
727  It++) {
728 
729  // Keep track of where this instruction is in the module.
730  switch (TII.getOutliningType(*It)) {
731  case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
732  mapToIllegalUnsigned(It);
733  break;
734 
735  case TargetInstrInfo::MachineOutlinerInstrType::Legal:
736  mapToLegalUnsigned(It);
737  break;
738 
739  case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
740  break;
741  }
742  }
743 
744  // After we're done every insertion, uniquely terminate this part of the
745  // "string". This makes sure we won't match across basic block or function
746  // boundaries since the "end" is encoded uniquely and thus appears in no
747  // repeated substring.
748  InstrList.push_back(MBB.end());
749  UnsignedVec.push_back(IllegalInstrNumber);
750  IllegalInstrNumber--;
751  }
752 
753  InstructionMapper() {
754  // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
755  // changed.
756  assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
757  "DenseMapInfo<unsigned>'s empty key isn't -1!");
759  "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
760  }
761 };
762 
763 /// \brief An interprocedural pass which finds repeated sequences of
764 /// instructions and replaces them with calls to functions.
765 ///
766 /// Each instruction is mapped to an unsigned integer and placed in a string.
767 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
768 /// is then repeatedly queried for repeated sequences of instructions. Each
769 /// non-overlapping repeated sequence is then placed in its own
770 /// \p MachineFunction and each instance is then replaced with a call to that
771 /// function.
772 struct MachineOutliner : public ModulePass {
773 
774  static char ID;
775 
776  /// \brief Set to true if the outliner should consider functions with
777  /// linkonceodr linkage.
778  bool OutlineFromLinkOnceODRs = false;
779 
780  StringRef getPassName() const override { return "Machine Outliner"; }
781 
782  void getAnalysisUsage(AnalysisUsage &AU) const override {
785  AU.setPreservesAll();
787  }
788 
789  MachineOutliner(bool OutlineFromLinkOnceODRs = false)
790  : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) {
792  }
793 
794  /// Find all repeated substrings that satisfy the outlining cost model.
795  ///
796  /// If a substring appears at least twice, then it must be represented by
797  /// an internal node which appears in at least two suffixes. Each suffix is
798  /// represented by a leaf node. To do this, we visit each internal node in
799  /// the tree, using the leaf children of each internal node. If an internal
800  /// node represents a beneficial substring, then we use each of its leaf
801  /// children to find the locations of its substring.
802  ///
803  /// \param ST A suffix tree to query.
804  /// \param TII TargetInstrInfo for the target.
805  /// \param Mapper Contains outlining mapping information.
806  /// \param[out] CandidateList Filled with candidates representing each
807  /// beneficial substring.
808  /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each
809  /// type of candidate.
810  ///
811  /// \returns The length of the longest candidate found.
812  unsigned
813  findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
814  InstructionMapper &Mapper,
815  std::vector<std::shared_ptr<Candidate>> &CandidateList,
816  std::vector<OutlinedFunction> &FunctionList);
817 
818  /// \brief Replace the sequences of instructions represented by the
819  /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
820  /// described in \p FunctionList.
821  ///
822  /// \param M The module we are outlining from.
823  /// \param CandidateList A list of candidates to be outlined.
824  /// \param FunctionList A list of functions to be inserted into the module.
825  /// \param Mapper Contains the instruction mappings for the module.
826  bool outline(Module &M,
827  const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
828  std::vector<OutlinedFunction> &FunctionList,
829  InstructionMapper &Mapper);
830 
831  /// Creates a function for \p OF and inserts it into the module.
832  MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
833  InstructionMapper &Mapper);
834 
835  /// Find potential outlining candidates and store them in \p CandidateList.
836  ///
837  /// For each type of potential candidate, also build an \p OutlinedFunction
838  /// struct containing the information to build the function for that
839  /// candidate.
840  ///
841  /// \param[out] CandidateList Filled with outlining candidates for the module.
842  /// \param[out] FunctionList Filled with functions corresponding to each type
843  /// of \p Candidate.
844  /// \param ST The suffix tree for the module.
845  /// \param TII TargetInstrInfo for the module.
846  ///
847  /// \returns The length of the longest candidate found. 0 if there are none.
848  unsigned
849  buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
850  std::vector<OutlinedFunction> &FunctionList,
851  SuffixTree &ST, InstructionMapper &Mapper,
852  const TargetInstrInfo &TII);
853 
854  /// Helper function for pruneOverlaps.
855  /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
856  void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
857 
858  /// \brief Remove any overlapping candidates that weren't handled by the
859  /// suffix tree's pruning method.
860  ///
861  /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
862  /// If a short candidate is chosen for outlining, then a longer candidate
863  /// which has that short candidate as a suffix is chosen, the tree's pruning
864  /// method will not find it. Thus, we need to prune before outlining as well.
865  ///
866  /// \param[in,out] CandidateList A list of outlining candidates.
867  /// \param[in,out] FunctionList A list of functions to be outlined.
868  /// \param Mapper Contains instruction mapping info for outlining.
869  /// \param MaxCandidateLen The length of the longest candidate.
870  /// \param TII TargetInstrInfo for the module.
871  void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
872  std::vector<OutlinedFunction> &FunctionList,
873  InstructionMapper &Mapper, unsigned MaxCandidateLen,
874  const TargetInstrInfo &TII);
875 
876  /// Construct a suffix tree on the instructions in \p M and outline repeated
877  /// strings from that tree.
878  bool runOnModule(Module &M) override;
879 };
880 
881 } // Anonymous namespace.
882 
883 char MachineOutliner::ID = 0;
884 
885 namespace llvm {
886 ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) {
887  return new MachineOutliner(OutlineFromLinkOnceODRs);
888 }
889 
890 } // namespace llvm
891 
892 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
893  false)
894 
895 unsigned MachineOutliner::findCandidates(
896  SuffixTree &ST, const TargetInstrInfo &TII, InstructionMapper &Mapper,
897  std::vector<std::shared_ptr<Candidate>> &CandidateList,
898  std::vector<OutlinedFunction> &FunctionList) {
899  CandidateList.clear();
900  FunctionList.clear();
901  unsigned MaxLen = 0;
902 
903  // FIXME: Visit internal nodes instead of leaves.
904  for (SuffixTreeNode *Leaf : ST.LeafVector) {
905  assert(Leaf && "Leaves in LeafVector cannot be null!");
906  if (!Leaf->IsInTree)
907  continue;
908 
909  assert(Leaf->Parent && "All leaves must have parents!");
910  SuffixTreeNode &Parent = *(Leaf->Parent);
911 
912  // If it doesn't appear enough, or we already outlined from it, skip it.
913  if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
914  continue;
915 
916  // Figure out if this candidate is beneficial.
917  unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
918 
919  // Too short to be beneficial; skip it.
920  // FIXME: This isn't necessarily true for, say, X86. If we factor in
921  // instruction lengths we need more information than this.
922  if (StringLen < 2)
923  continue;
924 
925  // If this is a beneficial class of candidate, then every one is stored in
926  // this vector.
927  std::vector<Candidate> CandidatesForRepeatedSeq;
928 
929  // Describes the start and end point of each candidate. This allows the
930  // target to infer some information about each occurrence of each repeated
931  // sequence.
932  // FIXME: CandidatesForRepeatedSeq and this should be combined.
933  std::vector<
934  std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
935  RepeatedSequenceLocs;
936 
937  // Figure out the call overhead for each instance of the sequence.
938  for (auto &ChildPair : Parent.Children) {
939  SuffixTreeNode *M = ChildPair.second;
940 
941  if (M && M->IsInTree && M->isLeaf()) {
942  // Each sequence is over [StartIt, EndIt].
943  MachineBasicBlock::iterator StartIt = Mapper.InstrList[M->SuffixIdx];
945  Mapper.InstrList[M->SuffixIdx + StringLen - 1];
946 
947  CandidatesForRepeatedSeq.emplace_back(M->SuffixIdx, StringLen,
948  FunctionList.size());
949  RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
950 
951  // Never visit this leaf again.
952  M->IsInTree = false;
953  }
954  }
955 
956  // We've found something we might want to outline.
957  // Create an OutlinedFunction to store it and check if it'd be beneficial
958  // to outline.
960  TII.getOutlininingCandidateInfo(RepeatedSequenceLocs);
961  std::vector<unsigned> Seq;
962  for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
963  Seq.push_back(ST.Str[i]);
964  OutlinedFunction OF(FunctionList.size(), Parent.OccurrenceCount, Seq,
965  MInfo);
966  unsigned Benefit = OF.getBenefit();
967 
968  // Is it better to outline this candidate than not?
969  if (Benefit < 1) {
970  // Outlining this candidate would take more instructions than not
971  // outlining.
972  // Emit a remark explaining why we didn't outline this candidate.
973  std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C =
974  RepeatedSequenceLocs[0];
976  *(C.first->getParent()->getParent()), nullptr);
977  MORE.emit([&]() {
978  MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
979  C.first->getDebugLoc(),
980  C.first->getParent());
981  R << "Did not outline " << NV("Length", StringLen) << " instructions"
982  << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
983  << " locations."
984  << " Instructions from outlining all occurrences ("
985  << NV("OutliningCost", OF.getOutliningCost()) << ")"
986  << " >= Unoutlined instruction count ("
987  << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")"
988  << " (Also found at: ";
989 
990  // Tell the user the other places the candidate was found.
991  for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
992  R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
993  RepeatedSequenceLocs[i].first->getDebugLoc());
994  if (i != e - 1)
995  R << ", ";
996  }
997 
998  R << ")";
999  return R;
1000  });
1001 
1002  // Move to the next candidate.
1003  continue;
1004  }
1005 
1006  if (StringLen > MaxLen)
1007  MaxLen = StringLen;
1008 
1009  // At this point, the candidate class is seen as beneficial. Set their
1010  // benefit values and save them in the candidate list.
1011  std::vector<std::shared_ptr<Candidate>> CandidatesForFn;
1012  for (Candidate &C : CandidatesForRepeatedSeq) {
1013  C.Benefit = Benefit;
1014  C.MInfo = MInfo;
1015  std::shared_ptr<Candidate> Cptr = std::make_shared<Candidate>(C);
1016  CandidateList.push_back(Cptr);
1017  CandidatesForFn.push_back(Cptr);
1018  }
1019 
1020  FunctionList.push_back(OF);
1021  FunctionList.back().Candidates = CandidatesForFn;
1022 
1023  // Move to the next function.
1024  Parent.IsInTree = false;
1025  }
1026 
1027  return MaxLen;
1028 }
1029 
1030 // Remove C from the candidate space, and update its OutlinedFunction.
1031 void MachineOutliner::prune(Candidate &C,
1032  std::vector<OutlinedFunction> &FunctionList) {
1033  // Get the OutlinedFunction associated with this Candidate.
1034  OutlinedFunction &F = FunctionList[C.FunctionIdx];
1035 
1036  // Update C's associated function's occurrence count.
1037  F.decrement();
1038 
1039  // Remove C from the CandidateList.
1040  C.InCandidateList = false;
1041 
1042  DEBUG(dbgs() << "- Removed a Candidate \n";
1043  dbgs() << "--- Num fns left for candidate: " << F.getOccurrenceCount()
1044  << "\n";
1045  dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
1046  << "\n";);
1047 }
1048 
1049 void MachineOutliner::pruneOverlaps(
1050  std::vector<std::shared_ptr<Candidate>> &CandidateList,
1051  std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
1052  unsigned MaxCandidateLen, const TargetInstrInfo &TII) {
1053 
1054  // Return true if this candidate became unbeneficial for outlining in a
1055  // previous step.
1056  auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
1057 
1058  // Check if the candidate was removed in a previous step.
1059  if (!C.InCandidateList)
1060  return true;
1061 
1062  // C must be alive. Check if we should remove it.
1063  if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
1064  prune(C, FunctionList);
1065  return true;
1066  }
1067 
1068  // C is in the list, and F is still beneficial.
1069  return false;
1070  };
1071 
1072  // TODO: Experiment with interval trees or other interval-checking structures
1073  // to lower the time complexity of this function.
1074  // TODO: Can we do better than the simple greedy choice?
1075  // Check for overlaps in the range.
1076  // This is O(MaxCandidateLen * CandidateList.size()).
1077  for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
1078  It++) {
1079  Candidate &C1 = **It;
1080 
1081  // If C1 was already pruned, or its function is no longer beneficial for
1082  // outlining, move to the next candidate.
1083  if (ShouldSkipCandidate(C1))
1084  continue;
1085 
1086  // The minimum start index of any candidate that could overlap with this
1087  // one.
1088  unsigned FarthestPossibleIdx = 0;
1089 
1090  // Either the index is 0, or it's at most MaxCandidateLen indices away.
1091  if (C1.getStartIdx() > MaxCandidateLen)
1092  FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
1093 
1094  // Compare against the candidates in the list that start at at most
1095  // FarthestPossibleIdx indices away from C1. There are at most
1096  // MaxCandidateLen of these.
1097  for (auto Sit = It + 1; Sit != Et; Sit++) {
1098  Candidate &C2 = **Sit;
1099 
1100  // Is this candidate too far away to overlap?
1101  if (C2.getStartIdx() < FarthestPossibleIdx)
1102  break;
1103 
1104  // If C2 was already pruned, or its function is no longer beneficial for
1105  // outlining, move to the next candidate.
1106  if (ShouldSkipCandidate(C2))
1107  continue;
1108 
1109  // Do C1 and C2 overlap?
1110  //
1111  // Not overlapping:
1112  // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
1113  //
1114  // We sorted our candidate list so C2Start <= C1Start. We know that
1115  // C2End > C2Start since each candidate has length >= 2. Therefore, all we
1116  // have to check is C2End < C2Start to see if we overlap.
1117  if (C2.getEndIdx() < C1.getStartIdx())
1118  continue;
1119 
1120  // C1 and C2 overlap.
1121  // We need to choose the better of the two.
1122  //
1123  // Approximate this by picking the one which would have saved us the
1124  // most instructions before any pruning.
1125 
1126  // Is C2 a better candidate?
1127  if (C2.Benefit > C1.Benefit) {
1128  // Yes, so prune C1. Since C1 is dead, we don't have to compare it
1129  // against anything anymore, so break.
1130  prune(C1, FunctionList);
1131  break;
1132  }
1133 
1134  // Prune C2 and move on to the next candidate.
1135  prune(C2, FunctionList);
1136  }
1137  }
1138 }
1139 
1140 unsigned MachineOutliner::buildCandidateList(
1141  std::vector<std::shared_ptr<Candidate>> &CandidateList,
1142  std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
1143  InstructionMapper &Mapper, const TargetInstrInfo &TII) {
1144 
1145  std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1146  unsigned MaxCandidateLen = 0; // Length of the longest candidate.
1147 
1148  MaxCandidateLen =
1149  findCandidates(ST, TII, Mapper, CandidateList, FunctionList);
1150 
1151  // Sort the candidates in decending order. This will simplify the outlining
1152  // process when we have to remove the candidates from the mapping by
1153  // allowing us to cut them out without keeping track of an offset.
1154  std::stable_sort(
1155  CandidateList.begin(), CandidateList.end(),
1156  [](const std::shared_ptr<Candidate> &LHS,
1157  const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
1158 
1159  return MaxCandidateLen;
1160 }
1161 
1163 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1164  InstructionMapper &Mapper) {
1165 
1166  // Create the function name. This should be unique. For now, just hash the
1167  // module name and include it in the function name plus the number of this
1168  // function.
1169  std::ostringstream NameStream;
1170  NameStream << "OUTLINED_FUNCTION_" << OF.Name;
1171 
1172  // Create the function using an IR-level function.
1173  LLVMContext &C = M.getContext();
1175  M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1176  assert(F && "Function was null!");
1177 
1178  // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1179  // which gives us better results when we outline from linkonceodr functions.
1182 
1183  BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1184  IRBuilder<> Builder(EntryBB);
1185  Builder.CreateRetVoid();
1186 
1187  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1189  MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1190  const TargetSubtargetInfo &STI = MF.getSubtarget();
1191  const TargetInstrInfo &TII = *STI.getInstrInfo();
1192 
1193  // Insert the new function into the module.
1194  MF.insert(MF.begin(), &MBB);
1195 
1196  TII.insertOutlinerPrologue(MBB, MF, OF.MInfo);
1197 
1198  // Copy over the instructions for the function using the integer mappings in
1199  // its sequence.
1200  for (unsigned Str : OF.Sequence) {
1201  MachineInstr *NewMI =
1202  MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1203  NewMI->dropMemRefs();
1204 
1205  // Don't keep debug information for outlined instructions.
1206  // FIXME: This means outlined functions are currently undebuggable.
1207  NewMI->setDebugLoc(DebugLoc());
1208  MBB.insert(MBB.end(), NewMI);
1209  }
1210 
1211  TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
1212 
1213  return &MF;
1214 }
1215 
1216 bool MachineOutliner::outline(
1217  Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
1218  std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
1219 
1220  bool OutlinedSomething = false;
1221  // Replace the candidates with calls to their respective outlined functions.
1222  for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
1223  Candidate &C = *Cptr;
1224  // Was the candidate removed during pruneOverlaps?
1225  if (!C.InCandidateList)
1226  continue;
1227 
1228  // If not, then look at its OutlinedFunction.
1229  OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1230 
1231  // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1232  if (OF.getBenefit() < 1)
1233  continue;
1234 
1235  // If not, then outline it.
1236  assert(C.getStartIdx() < Mapper.InstrList.size() &&
1237  "Candidate out of bounds!");
1238  MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent();
1239  MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()];
1240  unsigned EndIdx = C.getEndIdx();
1241 
1242  assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
1243  MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
1244  assert(EndIt != MBB->end() && "EndIt out of bounds!");
1245 
1246  EndIt++; // Erase needs one past the end index.
1247 
1248  // Does this candidate have a function yet?
1249  if (!OF.MF) {
1250  OF.MF = createOutlinedFunction(M, OF, Mapper);
1251  MachineBasicBlock *MBB = &*OF.MF->begin();
1252 
1253  // Output a remark telling the user that an outlined function was created,
1254  // and explaining where it came from.
1255  MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
1256  MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
1257  MBB->findDebugLoc(MBB->begin()), MBB);
1258  R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
1259  << " instructions by "
1260  << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
1261  << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
1262  << " locations. "
1263  << "(Found at: ";
1264 
1265  // Tell the user the other places the candidate was found.
1266  for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
1267 
1268  // Skip over things that were pruned.
1269  if (!OF.Candidates[i]->InCandidateList)
1270  continue;
1271 
1272  R << NV(
1273  (Twine("StartLoc") + Twine(i)).str(),
1274  Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc());
1275  if (i != e - 1)
1276  R << ", ";
1277  }
1278 
1279  R << ")";
1280 
1281  MORE.emit(R);
1282  FunctionsCreated++;
1283  }
1284 
1285  MachineFunction *MF = OF.MF;
1286  const TargetSubtargetInfo &STI = MF->getSubtarget();
1287  const TargetInstrInfo &TII = *STI.getInstrInfo();
1288 
1289  // Insert a call to the new function and erase the old sequence.
1290  TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo);
1291  StartIt = Mapper.InstrList[C.getStartIdx()];
1292  MBB->erase(StartIt, EndIt);
1293 
1294  OutlinedSomething = true;
1295 
1296  // Statistics.
1297  NumOutlined++;
1298  }
1299 
1300  DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1301 
1302  return OutlinedSomething;
1303 }
1304 
1305 bool MachineOutliner::runOnModule(Module &M) {
1306 
1307  // Is there anything in the module at all?
1308  if (M.empty())
1309  return false;
1310 
1311  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1312  const TargetSubtargetInfo &STI =
1313  MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget();
1314  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
1315  const TargetInstrInfo *TII = STI.getInstrInfo();
1316 
1317  InstructionMapper Mapper;
1318 
1319  // Build instruction mappings for each function in the module.
1320  for (Function &F : M) {
1322 
1323  // Is the function empty? Safe to outline from?
1324  if (F.empty() ||
1325  !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs))
1326  continue;
1327 
1328  // If it is, look at each MachineBasicBlock in the function.
1329  for (MachineBasicBlock &MBB : MF) {
1330 
1331  // Is there anything in MBB?
1332  if (MBB.empty())
1333  continue;
1334 
1335  // If yes, map it.
1336  Mapper.convertToUnsignedVec(MBB, *TRI, *TII);
1337  }
1338  }
1339 
1340  // Construct a suffix tree, use it to find candidates, and then outline them.
1341  SuffixTree ST(Mapper.UnsignedVec);
1342  std::vector<std::shared_ptr<Candidate>> CandidateList;
1343  std::vector<OutlinedFunction> FunctionList;
1344 
1345  // Find all of the outlining candidates.
1346  unsigned MaxCandidateLen =
1347  buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
1348 
1349  // Remove candidates that overlap with other candidates.
1350  pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII);
1351 
1352  // Outline each of the candidates and return true if something was outlined.
1353  return outline(M, CandidateList, FunctionList, Mapper);
1354 }
uint64_t CallInst * C
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Constant * getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:142
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
Diagnostic information for applied optimization remarks.
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:57
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
F(f)
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
AnalysisUsage & addRequired()
Definition: BitVector.h:920
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
const HexagonInstrInfo * TII
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:237
virtual void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF, const MachineOutlinerInfo &MInfo) const
Insert a custom epilogue for outlined functions.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:91
bool empty() const
Definition: Module.h:581
INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) unsigned MachineOutliner
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
virtual bool isFunctionSafeToOutlineFrom(MachineFunction &MF, bool OutlineFromLinkOnceODRs) const
Return true if the function can safely be outlined from.
TargetInstrInfo - Interface to description of machine instruction set.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
Describes the number of instructions that it will take to call and construct a frame for a given outl...
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:963
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE instructions.
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
virtual void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF, const MachineOutlinerInfo &MInfo) const
Insert a custom prologue for outlined functions.
static const unsigned End
unsigned FrameOverhead
Number of instructions to construct an outlined function frame for this candidate.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:434
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MachineFunction & getOrCreateMachineFunction(const Function &F)
Returns the MachineFunction constructed for the IR function F.
unsigned first
void initializeMachineOutlinerPass(PassRegistry &)
void dropMemRefs()
Clear this MachineInstr&#39;s memory reference descriptor list.
The optimization diagnostic interface.
#define MORE()
Definition: regcomp.c:256
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:385
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:436
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
void setPreservesAll()
Set by analyses that do not transform their input at all.
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
Definition: MachineInstr.h:59
ReturnInst * CreateRetVoid()
Create a &#39;ret void&#39; instruction.
Definition: IRBuilder.h:749
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:208
virtual MachineBasicBlock::iterator insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, const MachineOutlinerInfo &MInfo) const
Insert a call to an outlined function into the program.
#define N
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
iterator begin()
Definition: Module.h:572
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Diagnostic information for missed-optimization remarks.
unsigned CallOverhead
Number of instructions to call an outlined function for this candidate.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
aarch64 promote const
static const Function * getParent(const Value *V)
#define DEBUG(X)
Definition: Debug.h:118
ModulePass * createMachineOutlinerPass(bool OutlineFromLinkOnceODRs=false)
This pass performs outlining on machine instructions directly before printing assembly.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
#define DEBUG_TYPE
virtual MachineOutlinerInstrType getOutliningType(MachineInstr &MI) const
Returns how or if MI should be outlined.
This class contains meta information specific to a module.