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