1 //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Replaces repeated sequences of instructions with function calls.
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.
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
23 /// * Create an outlined function
24 /// * Call that outlined function
26 /// Targets must implement
27 /// * getOutliningCandidateInfo
28 /// * insertOutlinerEpilogue
29 /// * insertOutlinedCall
30 /// * insertOutlinerPrologue
31 /// * isFunctionSafeToOutlineFrom
33 /// in order to make use of the MachineOutliner.
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
39 /// https://www.youtube.com/watch?v=yorld-WSOeU
41 /// The slides for the talk are available at
43 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
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.
51 /// For the original RFC for this pass, please see
53 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
55 /// For more information on the suffix tree data structure, please see
56 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
58 //===----------------------------------------------------------------------===//
59 #include "llvm/ADT/DenseMap.h"
60 #include "llvm/ADT/Statistic.h"
61 #include "llvm/ADT/Twine.h"
62 #include "llvm/CodeGen/MachineFrameInfo.h"
63 #include "llvm/CodeGen/MachineFunction.h"
64 #include "llvm/CodeGen/MachineInstrBuilder.h"
65 #include "llvm/CodeGen/MachineModuleInfo.h"
66 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
67 #include "llvm/CodeGen/Passes.h"
68 #include "llvm/CodeGen/TargetInstrInfo.h"
69 #include "llvm/CodeGen/TargetRegisterInfo.h"
70 #include "llvm/CodeGen/TargetSubtargetInfo.h"
71 #include "llvm/IR/IRBuilder.h"
72 #include "llvm/Support/Allocator.h"
73 #include "llvm/Support/Debug.h"
74 #include "llvm/Support/raw_ostream.h"
75 #include "llvm/Target/TargetMachine.h"
82 #define DEBUG_TYPE "machine-outliner"
87 STATISTIC(NumOutlined, "Number of candidates outlined");
88 STATISTIC(FunctionsCreated, "Number of functions created");
92 /// \brief An individual sequence of instructions to be replaced with a call to
93 /// an outlined function.
96 /// The start index of this \p Candidate in the instruction list.
99 /// The number of instructions in this \p Candidate.
103 /// Set to false if the candidate overlapped with another candidate.
104 bool InCandidateList = true;
106 /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of
107 /// \p OutlinedFunctions.
108 unsigned FunctionIdx;
110 /// Contains all target-specific information for this \p Candidate.
111 TargetInstrInfo::MachineOutlinerInfo MInfo;
113 /// Return the number of instructions in this Candidate.
114 unsigned getLength() const { return Len; }
116 /// Return the start index of this candidate.
117 unsigned getStartIdx() const { return StartIdx; }
119 // Return the end index of this candidate.
120 unsigned getEndIdx() const { return StartIdx + Len - 1; }
122 /// \brief The number of instructions that would be saved by outlining every
123 /// candidate of this type.
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;
131 Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx)
132 : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
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();
143 /// \brief The information necessary to create an outlined function for some
144 /// class of candidate.
145 struct OutlinedFunction {
148 /// The number of candidates for this \p OutlinedFunction.
149 unsigned OccurrenceCount = 0;
152 std::vector<std::shared_ptr<Candidate>> Candidates;
154 /// The actual outlined function created.
155 /// This is initialized after we go through and create the actual function.
156 MachineFunction *MF = nullptr;
158 /// A number assigned to this function which appears at the end of its name.
161 /// \brief The sequence of integers corresponding to the instructions in this
163 std::vector<unsigned> Sequence;
165 /// Contains all target-specific information for this \p OutlinedFunction.
166 TargetInstrInfo::MachineOutlinerInfo MInfo;
168 /// Return the number of candidates for this \p OutlinedFunction.
169 unsigned getOccurrenceCount() { return OccurrenceCount; }
171 /// Decrement the occurrence count of this OutlinedFunction and return the
173 unsigned decrement() {
174 assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
176 return getOccurrenceCount();
179 /// \brief Return the number of instructions it would take to outline this
181 unsigned getOutliningCost() {
182 return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() +
186 /// \brief Return the number of instructions that would be saved by outlining
188 unsigned getBenefit() {
189 unsigned NotOutlinedCost = OccurrenceCount * Sequence.size();
190 unsigned OutlinedCost = getOutliningCost();
191 return (NotOutlinedCost < OutlinedCost) ? 0
192 : NotOutlinedCost - OutlinedCost;
195 OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
196 const std::vector<unsigned> &Sequence,
197 TargetInstrInfo::MachineOutlinerInfo &MInfo)
198 : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
202 /// Represents an undefined index in the suffix tree.
203 const unsigned EmptyIdx = -1;
205 /// A node in a suffix tree which represents a substring or suffix.
207 /// Each node has either no children or at least two children, with the root
208 /// being a exception in the empty tree.
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.
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 {
222 /// The children of this node.
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.
227 DenseMap<unsigned, SuffixTreeNode *> Children;
229 /// A flag set to false if the node has been pruned from the tree.
230 bool IsInTree = true;
232 /// The start index of this node's substring in the main string.
233 unsigned StartIdx = EmptyIdx;
235 /// The end index of this node's substring in the main string.
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
241 unsigned *EndIdx = nullptr;
243 /// For leaves, the start index of the suffix represented by this node.
245 /// For all other nodes, this is ignored.
246 unsigned SuffixIdx = EmptyIdx;
248 /// \brief For internal nodes, a pointer to the internal node representing
249 /// the same sequence with the first character chopped off.
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.
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;
268 /// The parent of this node. Every node except for the root has a parent.
269 SuffixTreeNode *Parent = nullptr;
271 /// The number of times this node's string appears in the tree.
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;
277 /// The length of the string formed by concatenating the edge labels from the
278 /// root to this node.
279 unsigned ConcatLen = 0;
281 /// Returns true if this node is a leaf.
282 bool isLeaf() const { return SuffixIdx != EmptyIdx; }
284 /// Returns true if this node is the root of its owning \p SuffixTree.
285 bool isRoot() const { return StartIdx == EmptyIdx; }
287 /// Return the number of elements in the substring associated with this node.
288 size_t size() const {
290 // Is it the root? If so, it's the empty string so return 0.
294 assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
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;
301 SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
302 SuffixTreeNode *Parent)
303 : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
308 /// A data structure for fast substring queries.
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.
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.
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.
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
329 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
332 /// Stores each leaf node in the tree.
334 /// This is used for finding outlining candidates.
335 std::vector<SuffixTreeNode *> LeafVector;
337 /// Each element is an integer representing an instruction in the module.
338 ArrayRef<unsigned> Str;
341 /// Maintains each node in the tree.
342 SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
344 /// The root of the suffix tree.
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;
350 /// Maintains the end indices of the internal nodes in the tree.
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;
359 /// The end index of each leaf in the tree.
360 unsigned LeafEndIdx = -1;
362 /// \brief Helper struct which keeps track of the next insertion point in
363 /// Ukkonen's algorithm.
365 /// The next node to insert at.
366 SuffixTreeNode *Node;
368 /// The index of the first character in the substring currently being added.
369 unsigned Idx = EmptyIdx;
371 /// The length of the substring we have to add at the current step.
375 /// \brief The point the next insertion will take place at in the
376 /// construction algorithm.
379 /// Allocate a leaf node and add it to the tree.
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.
385 /// \returns A pointer to the allocated leaf node.
386 SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
389 assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
391 SuffixTreeNode *N = new (NodeAllocator.Allocate())
392 SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
393 Parent.Children[Edge] = N;
398 /// Allocate an internal node and add it to the tree.
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.
405 /// \returns A pointer to the allocated internal node.
406 SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
407 unsigned EndIdx, unsigned Edge) {
409 assert(StartIdx <= EndIdx && "String can't start after it ends!");
410 assert(!(!Parent && StartIdx != EmptyIdx) &&
411 "Non-root internal nodes must have parents!");
413 unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
414 SuffixTreeNode *N = new (NodeAllocator.Allocate())
415 SuffixTreeNode(StartIdx, E, Root, Parent);
417 Parent->Children[Edge] = N;
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.
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) {
430 bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
432 // Store the length of the concatenation of all strings from the root to
434 if (!CurrNode.isRoot()) {
435 if (CurrNode.ConcatLen == 0)
436 CurrNode.ConcatLen = CurrNode.size();
439 CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
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());
448 // Is this node a leaf?
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++;
455 // Store the leaf in the leaf vector for pruning later.
456 LeafVector[CurrNode.SuffixIdx] = &CurrNode;
460 /// \brief Construct the suffix tree for the prefix of the input ending at
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.
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.
472 /// \returns The number of suffixes that have not been added at the end of
474 unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
475 SuffixTreeNode *NeedsLink = nullptr;
477 while (SuffixesToAdd > 0) {
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.
485 assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
487 // The first character in the current substring we're looking at.
488 unsigned FirstChar = Str[Active.Idx];
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);
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.
498 NeedsLink->Link = Active.Node;
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];
506 unsigned SubstringLen = NextNode->size();
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
513 Active.Idx += SubstringLen;
514 Active.Len -= SubstringLen;
515 Active.Node = NextNode;
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];
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
528 if (NeedsLink && !Active.Node->isRoot()) {
529 NeedsLink->Link = Active.Node;
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.
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.
545 // | ABC ---split---> | AB
550 // The node s from the diagram
551 SuffixTreeNode *SplitNode =
552 insertInternalNode(Active.Node, NextNode->StartIdx,
553 NextNode->StartIdx + Active.Len - 1, FirstChar);
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);
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;
565 // SplitNode is an internal node, update the suffix link.
567 NeedsLink->Link = SplitNode;
569 NeedsLink = SplitNode;
572 // We've added something new to the tree, so there's one less suffix to
576 if (Active.Node->isRoot()) {
577 if (Active.Len > 0) {
579 Active.Idx = EndIdx - SuffixesToAdd + 1;
582 // Start the next phase at the next smallest suffix.
583 Active.Node = Active.Node->Link;
587 return SuffixesToAdd;
591 /// Construct a suffix tree from a sequence of unsigned integers.
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;
598 LeafVector = std::vector<SuffixTreeNode *>(Str.size());
600 // Keep track of the number of suffixes we have to add of the current
602 unsigned SuffixesToAdd = 0;
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;
611 LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
612 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
615 // Set the suffix indices of each leaf.
616 assert(Root && "Root node can't be nullptr!");
617 setSuffixIndices(*Root, 0);
621 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
622 struct InstructionMapper {
624 /// \brief The next available integer to assign to a \p MachineInstr that
625 /// cannot be outlined.
627 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
628 unsigned IllegalInstrNumber = -3;
630 /// \brief The next available integer to assign to a \p MachineInstr that can
632 unsigned LegalInstrNumber = 0;
634 /// Correspondence from \p MachineInstrs to unsigned integers.
635 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
636 InstructionIntegerMap;
638 /// Corresponcence from unsigned integers to \p MachineInstrs.
639 /// Inverse of \p InstructionIntegerMap.
640 DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
642 /// The vector of unsigned integers that the module is mapped to.
643 std::vector<unsigned> UnsignedVec;
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;
649 /// \brief Maps \p *It to a legal integer.
651 /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
652 /// \p IntegerInstructionMap, and \p LegalInstrNumber.
654 /// \returns The integer that \p *It was mapped to.
655 unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
657 // Get the integer for this instruction or give it the current
659 InstrList.push_back(It);
660 MachineInstr &MI = *It;
662 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
664 std::tie(ResultIt, WasInserted) =
665 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
666 unsigned MINumber = ResultIt->second;
668 // There was an insertion.
671 IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
674 UnsignedVec.push_back(MINumber);
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!");
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.");
688 /// Maps \p *It to an illegal integer.
690 /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
692 /// \returns The integer that \p *It was mapped to.
693 unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
694 unsigned MINumber = IllegalInstrNumber;
696 InstrList.push_back(It);
697 UnsignedVec.push_back(IllegalInstrNumber);
698 IllegalInstrNumber--;
700 assert(LegalInstrNumber < IllegalInstrNumber &&
701 "Instruction mapping overflow!");
703 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
704 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
706 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
707 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
712 /// \brief Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
713 /// and appends it to \p UnsignedVec and \p InstrList.
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.
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;
729 // Keep track of where this instruction is in the module.
730 switch (TII.getOutliningType(*It)) {
731 case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
732 mapToIllegalUnsigned(It);
735 case TargetInstrInfo::MachineOutlinerInstrType::Legal:
736 mapToLegalUnsigned(It);
739 case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
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--;
753 InstructionMapper() {
754 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
756 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
757 "DenseMapInfo<unsigned>'s empty key isn't -1!");
758 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
759 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
763 /// \brief An interprocedural pass which finds repeated sequences of
764 /// instructions and replaces them with calls to functions.
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
772 struct MachineOutliner : public ModulePass {
776 /// \brief Set to true if the outliner should consider functions with
777 /// linkonceodr linkage.
778 bool OutlineFromLinkOnceODRs = false;
780 StringRef getPassName() const override { return "Machine Outliner"; }
782 void getAnalysisUsage(AnalysisUsage &AU) const override {
783 AU.addRequired<MachineModuleInfo>();
784 AU.addPreserved<MachineModuleInfo>();
785 AU.setPreservesAll();
786 ModulePass::getAnalysisUsage(AU);
789 MachineOutliner(bool OutlineFromLinkOnceODRs = false)
790 : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) {
791 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
794 /// Find all repeated substrings that satisfy the outlining cost model.
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.
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.
811 /// \returns The length of the longest candidate found.
813 findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
814 InstructionMapper &Mapper,
815 std::vector<std::shared_ptr<Candidate>> &CandidateList,
816 std::vector<OutlinedFunction> &FunctionList);
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.
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);
831 /// Creates a function for \p OF and inserts it into the module.
832 MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
833 InstructionMapper &Mapper);
835 /// Find potential outlining candidates and store them in \p CandidateList.
837 /// For each type of potential candidate, also build an \p OutlinedFunction
838 /// struct containing the information to build the function for that
841 /// \param[out] CandidateList Filled with outlining candidates for the module.
842 /// \param[out] FunctionList Filled with functions corresponding to each type
844 /// \param ST The suffix tree for the module.
845 /// \param TII TargetInstrInfo for the module.
847 /// \returns The length of the longest candidate found. 0 if there are none.
849 buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
850 std::vector<OutlinedFunction> &FunctionList,
851 SuffixTree &ST, InstructionMapper &Mapper,
852 const TargetInstrInfo &TII);
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);
858 /// \brief Remove any overlapping candidates that weren't handled by the
859 /// suffix tree's pruning method.
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.
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);
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;
881 } // Anonymous namespace.
883 char MachineOutliner::ID = 0;
886 ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) {
887 return new MachineOutliner(OutlineFromLinkOnceODRs);
892 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
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();
903 // FIXME: Visit internal nodes instead of leaves.
904 for (SuffixTreeNode *Leaf : ST.LeafVector) {
905 assert(Leaf && "Leaves in LeafVector cannot be null!");
909 assert(Leaf->Parent && "All leaves must have parents!");
910 SuffixTreeNode &Parent = *(Leaf->Parent);
912 // If it doesn't appear enough, or we already outlined from it, skip it.
913 if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
916 // Figure out if this candidate is beneficial.
917 unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
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.
925 // If this is a beneficial class of candidate, then every one is stored in
927 std::vector<Candidate> CandidatesForRepeatedSeq;
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
932 // FIXME: CandidatesForRepeatedSeq and this should be combined.
934 std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
935 RepeatedSequenceLocs;
937 // Figure out the call overhead for each instance of the sequence.
938 for (auto &ChildPair : Parent.Children) {
939 SuffixTreeNode *M = ChildPair.second;
941 if (M && M->IsInTree && M->isLeaf()) {
942 // Never visit this leaf again.
944 unsigned StartIdx = M->SuffixIdx;
945 unsigned EndIdx = StartIdx + StringLen - 1;
947 // Trick: Discard some candidates that would be incompatible with the
948 // ones we've already found for this sequence. This will save us some
949 // work in candidate selection.
951 // If two candidates overlap, then we can't outline them both. This
952 // happens when we have candidates that look like, say
954 // AA (where each "A" is an instruction).
956 // We might have some portion of the module that looks like this:
959 // In this case, there are 5 different copies of "AA" in this range, but
960 // at most 3 can be outlined. If only outlining 3 of these is going to
961 // be unbeneficial, then we ought to not bother.
963 // Note that two things DON'T overlap when they look like this:
964 // start1...end1 .... start2...end2
965 // That is, one must either
966 // * End before the other starts
967 // * Start after the other ends
968 if (std::all_of(CandidatesForRepeatedSeq.begin(),
969 CandidatesForRepeatedSeq.end(),
970 [&StartIdx, &EndIdx](const Candidate &C) {
971 return (EndIdx < C.getStartIdx() ||
972 StartIdx > C.getEndIdx());
974 // It doesn't overlap with anything, so we can outline it.
975 // Each sequence is over [StartIt, EndIt].
976 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
977 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
979 // Save the candidate and its location.
980 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen,
981 FunctionList.size());
982 RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
987 // We've found something we might want to outline.
988 // Create an OutlinedFunction to store it and check if it'd be beneficial
990 TargetInstrInfo::MachineOutlinerInfo MInfo =
991 TII.getOutlininingCandidateInfo(RepeatedSequenceLocs);
992 std::vector<unsigned> Seq;
993 for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
994 Seq.push_back(ST.Str[i]);
995 OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(),
997 unsigned Benefit = OF.getBenefit();
999 // Is it better to outline this candidate than not?
1001 // Outlining this candidate would take more instructions than not
1003 // Emit a remark explaining why we didn't outline this candidate.
1004 std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C =
1005 RepeatedSequenceLocs[0];
1006 MachineOptimizationRemarkEmitter MORE(
1007 *(C.first->getParent()->getParent()), nullptr);
1009 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
1010 C.first->getDebugLoc(),
1011 C.first->getParent());
1012 R << "Did not outline " << NV("Length", StringLen) << " instructions"
1013 << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
1015 << " Instructions from outlining all occurrences ("
1016 << NV("OutliningCost", OF.getOutliningCost()) << ")"
1017 << " >= Unoutlined instruction count ("
1018 << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")"
1019 << " (Also found at: ";
1021 // Tell the user the other places the candidate was found.
1022 for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
1023 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
1024 RepeatedSequenceLocs[i].first->getDebugLoc());
1033 // Move to the next candidate.
1037 if (StringLen > MaxLen)
1040 // At this point, the candidate class is seen as beneficial. Set their
1041 // benefit values and save them in the candidate list.
1042 std::vector<std::shared_ptr<Candidate>> CandidatesForFn;
1043 for (Candidate &C : CandidatesForRepeatedSeq) {
1044 C.Benefit = Benefit;
1046 std::shared_ptr<Candidate> Cptr = std::make_shared<Candidate>(C);
1047 CandidateList.push_back(Cptr);
1048 CandidatesForFn.push_back(Cptr);
1051 FunctionList.push_back(OF);
1052 FunctionList.back().Candidates = CandidatesForFn;
1054 // Move to the next function.
1055 Parent.IsInTree = false;
1061 // Remove C from the candidate space, and update its OutlinedFunction.
1062 void MachineOutliner::prune(Candidate &C,
1063 std::vector<OutlinedFunction> &FunctionList) {
1064 // Get the OutlinedFunction associated with this Candidate.
1065 OutlinedFunction &F = FunctionList[C.FunctionIdx];
1067 // Update C's associated function's occurrence count.
1070 // Remove C from the CandidateList.
1071 C.InCandidateList = false;
1073 DEBUG(dbgs() << "- Removed a Candidate \n";
1074 dbgs() << "--- Num fns left for candidate: " << F.getOccurrenceCount()
1076 dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
1080 void MachineOutliner::pruneOverlaps(
1081 std::vector<std::shared_ptr<Candidate>> &CandidateList,
1082 std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
1083 unsigned MaxCandidateLen, const TargetInstrInfo &TII) {
1085 // Return true if this candidate became unbeneficial for outlining in a
1087 auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
1089 // Check if the candidate was removed in a previous step.
1090 if (!C.InCandidateList)
1093 // C must be alive. Check if we should remove it.
1094 if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
1095 prune(C, FunctionList);
1099 // C is in the list, and F is still beneficial.
1103 // TODO: Experiment with interval trees or other interval-checking structures
1104 // to lower the time complexity of this function.
1105 // TODO: Can we do better than the simple greedy choice?
1106 // Check for overlaps in the range.
1107 // This is O(MaxCandidateLen * CandidateList.size()).
1108 for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
1110 Candidate &C1 = **It;
1112 // If C1 was already pruned, or its function is no longer beneficial for
1113 // outlining, move to the next candidate.
1114 if (ShouldSkipCandidate(C1))
1117 // The minimum start index of any candidate that could overlap with this
1119 unsigned FarthestPossibleIdx = 0;
1121 // Either the index is 0, or it's at most MaxCandidateLen indices away.
1122 if (C1.getStartIdx() > MaxCandidateLen)
1123 FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
1125 // Compare against the candidates in the list that start at at most
1126 // FarthestPossibleIdx indices away from C1. There are at most
1127 // MaxCandidateLen of these.
1128 for (auto Sit = It + 1; Sit != Et; Sit++) {
1129 Candidate &C2 = **Sit;
1131 // Is this candidate too far away to overlap?
1132 if (C2.getStartIdx() < FarthestPossibleIdx)
1135 // If C2 was already pruned, or its function is no longer beneficial for
1136 // outlining, move to the next candidate.
1137 if (ShouldSkipCandidate(C2))
1140 // Do C1 and C2 overlap?
1143 // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
1145 // We sorted our candidate list so C2Start <= C1Start. We know that
1146 // C2End > C2Start since each candidate has length >= 2. Therefore, all we
1147 // have to check is C2End < C2Start to see if we overlap.
1148 if (C2.getEndIdx() < C1.getStartIdx())
1151 // C1 and C2 overlap.
1152 // We need to choose the better of the two.
1154 // Approximate this by picking the one which would have saved us the
1155 // most instructions before any pruning.
1157 // Is C2 a better candidate?
1158 if (C2.Benefit > C1.Benefit) {
1159 // Yes, so prune C1. Since C1 is dead, we don't have to compare it
1160 // against anything anymore, so break.
1161 prune(C1, FunctionList);
1165 // Prune C2 and move on to the next candidate.
1166 prune(C2, FunctionList);
1171 unsigned MachineOutliner::buildCandidateList(
1172 std::vector<std::shared_ptr<Candidate>> &CandidateList,
1173 std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
1174 InstructionMapper &Mapper, const TargetInstrInfo &TII) {
1176 std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1177 unsigned MaxCandidateLen = 0; // Length of the longest candidate.
1180 findCandidates(ST, TII, Mapper, CandidateList, FunctionList);
1182 // Sort the candidates in decending order. This will simplify the outlining
1183 // process when we have to remove the candidates from the mapping by
1184 // allowing us to cut them out without keeping track of an offset.
1186 CandidateList.begin(), CandidateList.end(),
1187 [](const std::shared_ptr<Candidate> &LHS,
1188 const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
1190 return MaxCandidateLen;
1194 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1195 InstructionMapper &Mapper) {
1197 // Create the function name. This should be unique. For now, just hash the
1198 // module name and include it in the function name plus the number of this
1200 std::ostringstream NameStream;
1201 NameStream << "OUTLINED_FUNCTION_" << OF.Name;
1203 // Create the function using an IR-level function.
1204 LLVMContext &C = M.getContext();
1205 Function *F = dyn_cast<Function>(
1206 M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1207 assert(F && "Function was null!");
1209 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1210 // which gives us better results when we outline from linkonceodr functions.
1211 F->setLinkage(GlobalValue::PrivateLinkage);
1212 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1214 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1215 IRBuilder<> Builder(EntryBB);
1216 Builder.CreateRetVoid();
1218 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1219 MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
1220 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1221 const TargetSubtargetInfo &STI = MF.getSubtarget();
1222 const TargetInstrInfo &TII = *STI.getInstrInfo();
1224 // Insert the new function into the module.
1225 MF.insert(MF.begin(), &MBB);
1227 TII.insertOutlinerPrologue(MBB, MF, OF.MInfo);
1229 // Copy over the instructions for the function using the integer mappings in
1231 for (unsigned Str : OF.Sequence) {
1232 MachineInstr *NewMI =
1233 MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1234 NewMI->dropMemRefs();
1236 // Don't keep debug information for outlined instructions.
1237 // FIXME: This means outlined functions are currently undebuggable.
1238 NewMI->setDebugLoc(DebugLoc());
1239 MBB.insert(MBB.end(), NewMI);
1242 TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
1247 bool MachineOutliner::outline(
1248 Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
1249 std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
1251 bool OutlinedSomething = false;
1252 // Replace the candidates with calls to their respective outlined functions.
1253 for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
1254 Candidate &C = *Cptr;
1255 // Was the candidate removed during pruneOverlaps?
1256 if (!C.InCandidateList)
1259 // If not, then look at its OutlinedFunction.
1260 OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1262 // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1263 if (OF.getBenefit() < 1)
1266 // If not, then outline it.
1267 assert(C.getStartIdx() < Mapper.InstrList.size() &&
1268 "Candidate out of bounds!");
1269 MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent();
1270 MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()];
1271 unsigned EndIdx = C.getEndIdx();
1273 assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
1274 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
1275 assert(EndIt != MBB->end() && "EndIt out of bounds!");
1277 EndIt++; // Erase needs one past the end index.
1279 // Does this candidate have a function yet?
1281 OF.MF = createOutlinedFunction(M, OF, Mapper);
1282 MachineBasicBlock *MBB = &*OF.MF->begin();
1284 // Output a remark telling the user that an outlined function was created,
1285 // and explaining where it came from.
1286 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
1287 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
1288 MBB->findDebugLoc(MBB->begin()), MBB);
1289 R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
1290 << " instructions by "
1291 << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
1292 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
1296 // Tell the user the other places the candidate was found.
1297 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
1299 // Skip over things that were pruned.
1300 if (!OF.Candidates[i]->InCandidateList)
1304 (Twine("StartLoc") + Twine(i)).str(),
1305 Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc());
1316 MachineFunction *MF = OF.MF;
1317 const TargetSubtargetInfo &STI = MF->getSubtarget();
1318 const TargetInstrInfo &TII = *STI.getInstrInfo();
1320 // Insert a call to the new function and erase the old sequence.
1321 TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo);
1322 StartIt = Mapper.InstrList[C.getStartIdx()];
1323 MBB->erase(StartIt, EndIt);
1325 OutlinedSomething = true;
1331 DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1333 return OutlinedSomething;
1336 bool MachineOutliner::runOnModule(Module &M) {
1338 // Is there anything in the module at all?
1342 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1343 const TargetSubtargetInfo &STI =
1344 MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget();
1345 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
1346 const TargetInstrInfo *TII = STI.getInstrInfo();
1348 InstructionMapper Mapper;
1350 // Build instruction mappings for each function in the module.
1351 for (Function &F : M) {
1352 MachineFunction &MF = MMI.getOrCreateMachineFunction(F);
1354 // Is the function empty? Safe to outline from?
1356 !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs))
1359 // If it is, look at each MachineBasicBlock in the function.
1360 for (MachineBasicBlock &MBB : MF) {
1362 // Is there anything in MBB?
1367 Mapper.convertToUnsignedVec(MBB, *TRI, *TII);
1371 // Construct a suffix tree, use it to find candidates, and then outline them.
1372 SuffixTree ST(Mapper.UnsignedVec);
1373 std::vector<std::shared_ptr<Candidate>> CandidateList;
1374 std::vector<OutlinedFunction> FunctionList;
1376 // Find all of the outlining candidates.
1377 unsigned MaxCandidateLen =
1378 buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
1380 // Remove candidates that overlap with other candidates.
1381 pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII);
1383 // Outline each of the candidates and return true if something was outlined.
1384 return outline(M, CandidateList, FunctionList, Mapper);