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 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
19 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
20 /// how this pass works, the talk is available on YouTube at
22 /// https://www.youtube.com/watch?v=yorld-WSOeU
24 /// The slides for the talk are available at
26 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
28 /// The talk provides an overview of how the outliner finds candidates and
29 /// ultimately outlines them. It describes how the main data structure for this
30 /// pass, the suffix tree, is queried and purged for candidates. It also gives
31 /// a simplified suffix tree construction algorithm for suffix trees based off
32 /// of the algorithm actually used here, Ukkonen's algorithm.
34 /// For the original RFC for this pass, please see
36 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
38 /// For more information on the suffix tree data structure, please see
39 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
41 //===----------------------------------------------------------------------===//
42 #include "llvm/ADT/DenseMap.h"
43 #include "llvm/ADT/Statistic.h"
44 #include "llvm/ADT/Twine.h"
45 #include "llvm/CodeGen/MachineFrameInfo.h"
46 #include "llvm/CodeGen/MachineFunction.h"
47 #include "llvm/CodeGen/MachineInstrBuilder.h"
48 #include "llvm/CodeGen/MachineModuleInfo.h"
49 #include "llvm/CodeGen/Passes.h"
50 #include "llvm/IR/IRBuilder.h"
51 #include "llvm/Support/Allocator.h"
52 #include "llvm/Support/Debug.h"
53 #include "llvm/Support/raw_ostream.h"
54 #include "llvm/Target/TargetInstrInfo.h"
55 #include "llvm/Target/TargetMachine.h"
56 #include "llvm/Target/TargetRegisterInfo.h"
57 #include "llvm/Target/TargetSubtargetInfo.h"
64 #define DEBUG_TYPE "machine-outliner"
68 STATISTIC(NumOutlined, "Number of candidates outlined");
69 STATISTIC(FunctionsCreated, "Number of functions created");
73 /// \brief An individual sequence of instructions to be replaced with a call to
74 /// an outlined function.
77 /// Set to false if the candidate overlapped with another candidate.
78 bool InCandidateList = true;
80 /// The start index of this \p Candidate.
83 /// The number of instructions in this \p Candidate.
86 /// The index of this \p Candidate's \p OutlinedFunction in the list of
87 /// \p OutlinedFunctions.
90 /// \brief The number of instructions that would be saved by outlining every
91 /// candidate of this type.
93 /// This is a fixed value which is not updated during the candidate pruning
94 /// process. It is only used for deciding which candidate to keep if two
95 /// candidates overlap. The true benefit is stored in the OutlinedFunction
96 /// for some given candidate.
99 Candidate(size_t StartIdx, size_t Len, size_t FunctionIdx)
100 : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
104 /// \brief Used to ensure that \p Candidates are outlined in an order that
105 /// preserves the start and end indices of other \p Candidates.
106 bool operator<(const Candidate &RHS) const { return StartIdx > RHS.StartIdx; }
109 /// \brief The information necessary to create an outlined function for some
110 /// class of candidate.
111 struct OutlinedFunction {
113 /// The actual outlined function created.
114 /// This is initialized after we go through and create the actual function.
115 MachineFunction *MF = nullptr;
117 /// A number assigned to this function which appears at the end of its name.
120 /// The number of candidates for this OutlinedFunction.
121 size_t OccurrenceCount = 0;
123 /// \brief The sequence of integers corresponding to the instructions in this
125 std::vector<unsigned> Sequence;
127 /// The number of instructions this function would save.
128 unsigned Benefit = 0;
130 /// \brief Set to true if candidates for this outlined function should be
131 /// replaced with tail calls to this OutlinedFunction.
132 bool IsTailCall = false;
134 OutlinedFunction(size_t Name, size_t OccurrenceCount,
135 const std::vector<unsigned> &Sequence,
136 unsigned Benefit, bool IsTailCall)
137 : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence),
138 Benefit(Benefit), IsTailCall(IsTailCall)
142 /// Represents an undefined index in the suffix tree.
143 const size_t EmptyIdx = -1;
145 /// A node in a suffix tree which represents a substring or suffix.
147 /// Each node has either no children or at least two children, with the root
148 /// being a exception in the empty tree.
150 /// Children are represented as a map between unsigned integers and nodes. If
151 /// a node N has a child M on unsigned integer k, then the mapping represented
152 /// by N is a proper prefix of the mapping represented by M. Note that this,
153 /// although similar to a trie is somewhat different: each node stores a full
154 /// substring of the full mapping rather than a single character state.
156 /// Each internal node contains a pointer to the internal node representing
157 /// the same string, but with the first character chopped off. This is stored
158 /// in \p Link. Each leaf node stores the start index of its respective
159 /// suffix in \p SuffixIdx.
160 struct SuffixTreeNode {
162 /// The children of this node.
164 /// A child existing on an unsigned integer implies that from the mapping
165 /// represented by the current node, there is a way to reach another
166 /// mapping by tacking that character on the end of the current string.
167 DenseMap<unsigned, SuffixTreeNode *> Children;
169 /// A flag set to false if the node has been pruned from the tree.
170 bool IsInTree = true;
172 /// The start index of this node's substring in the main string.
173 size_t StartIdx = EmptyIdx;
175 /// The end index of this node's substring in the main string.
177 /// Every leaf node must have its \p EndIdx incremented at the end of every
178 /// step in the construction algorithm. To avoid having to update O(N)
179 /// nodes individually at the end of every step, the end index is stored
181 size_t *EndIdx = nullptr;
183 /// For leaves, the start index of the suffix represented by this node.
185 /// For all other nodes, this is ignored.
186 size_t SuffixIdx = EmptyIdx;
188 /// \brief For internal nodes, a pointer to the internal node representing
189 /// the same sequence with the first character chopped off.
191 /// This has two major purposes in the suffix tree. The first is as a
192 /// shortcut in Ukkonen's construction algorithm. One of the things that
193 /// Ukkonen's algorithm does to achieve linear-time construction is
194 /// keep track of which node the next insert should be at. This makes each
195 /// insert O(1), and there are a total of O(N) inserts. The suffix link
196 /// helps with inserting children of internal nodes.
198 /// Say we add a child to an internal node with associated mapping S. The
199 /// next insertion must be at the node representing S - its first character.
200 /// This is given by the way that we iteratively build the tree in Ukkonen's
201 /// algorithm. The main idea is to look at the suffixes of each prefix in the
202 /// string, starting with the longest suffix of the prefix, and ending with
203 /// the shortest. Therefore, if we keep pointers between such nodes, we can
204 /// move to the next insertion point in O(1) time. If we don't, then we'd
205 /// have to query from the root, which takes O(N) time. This would make the
206 /// construction algorithm O(N^2) rather than O(N).
208 /// The suffix link is also used during the tree pruning process to let us
209 /// quickly throw out a bunch of potential overlaps. Say we have a sequence
210 /// S we want to outline. Then each of its suffixes contribute to at least
211 /// one overlapping case. Therefore, we can follow the suffix links
212 /// starting at the node associated with S to the root and "delete" those
213 /// nodes, save for the root. For each candidate, this removes
214 /// O(|candidate|) overlaps from the search space. We don't actually
215 /// completely invalidate these nodes though; doing that is far too
216 /// aggressive. Consider the following pathological string:
218 /// 1 2 3 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3
220 /// If we, for the sake of example, outlined 1 2 3, then we would throw
221 /// out all instances of 2 3. This isn't desirable. To get around this,
222 /// when we visit a link node, we decrement its occurrence count by the
223 /// number of sequences we outlined in the current step. In the pathological
224 /// example, the 2 3 node would have an occurrence count of 8, while the
225 /// 1 2 3 node would have an occurrence count of 2. Thus, the 2 3 node
226 /// would survive to the next round allowing us to outline the extra
227 /// instances of 2 3.
228 SuffixTreeNode *Link = nullptr;
230 /// The parent of this node. Every node except for the root has a parent.
231 SuffixTreeNode *Parent = nullptr;
233 /// The number of times this node's string appears in the tree.
235 /// This is equal to the number of leaf children of the string. It represents
236 /// the number of suffixes that the node's string is a prefix of.
237 size_t OccurrenceCount = 0;
239 /// The length of the string formed by concatenating the edge labels from the
240 /// root to this node.
241 size_t ConcatLen = 0;
243 /// Returns true if this node is a leaf.
244 bool isLeaf() const { return SuffixIdx != EmptyIdx; }
246 /// Returns true if this node is the root of its owning \p SuffixTree.
247 bool isRoot() const { return StartIdx == EmptyIdx; }
249 /// Return the number of elements in the substring associated with this node.
250 size_t size() const {
252 // Is it the root? If so, it's the empty string so return 0.
256 assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
258 // Size = the number of elements in the string.
259 // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
260 return *EndIdx - StartIdx + 1;
263 SuffixTreeNode(size_t StartIdx, size_t *EndIdx, SuffixTreeNode *Link,
264 SuffixTreeNode *Parent)
265 : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
270 /// A data structure for fast substring queries.
272 /// Suffix trees represent the suffixes of their input strings in their leaves.
273 /// A suffix tree is a type of compressed trie structure where each node
274 /// represents an entire substring rather than a single character. Each leaf
275 /// of the tree is a suffix.
277 /// A suffix tree can be seen as a type of state machine where each state is a
278 /// substring of the full string. The tree is structured so that, for a string
279 /// of length N, there are exactly N leaves in the tree. This structure allows
280 /// us to quickly find repeated substrings of the input string.
282 /// In this implementation, a "string" is a vector of unsigned integers.
283 /// These integers may result from hashing some data type. A suffix tree can
284 /// contain 1 or many strings, which can then be queried as one large string.
286 /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
287 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
288 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
289 /// paper is available at
291 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
294 /// Each element is an integer representing an instruction in the module.
295 ArrayRef<unsigned> Str;
297 /// Maintains each node in the tree.
298 SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
300 /// The root of the suffix tree.
302 /// The root represents the empty string. It is maintained by the
303 /// \p NodeAllocator like every other node in the tree.
304 SuffixTreeNode *Root = nullptr;
306 /// Stores each leaf node in the tree.
308 /// This is used for finding outlining candidates.
309 std::vector<SuffixTreeNode *> LeafVector;
311 /// Maintains the end indices of the internal nodes in the tree.
313 /// Each internal node is guaranteed to never have its end index change
314 /// during the construction algorithm; however, leaves must be updated at
315 /// every step. Therefore, we need to store leaf end indices by reference
316 /// to avoid updating O(N) leaves at every step of construction. Thus,
317 /// every internal node must be allocated its own end index.
318 BumpPtrAllocator InternalEndIdxAllocator;
320 /// The end index of each leaf in the tree.
321 size_t LeafEndIdx = -1;
323 /// \brief Helper struct which keeps track of the next insertion point in
324 /// Ukkonen's algorithm.
326 /// The next node to insert at.
327 SuffixTreeNode *Node;
329 /// The index of the first character in the substring currently being added.
330 size_t Idx = EmptyIdx;
332 /// The length of the substring we have to add at the current step.
336 /// \brief The point the next insertion will take place at in the
337 /// construction algorithm.
340 /// Allocate a leaf node and add it to the tree.
342 /// \param Parent The parent of this node.
343 /// \param StartIdx The start index of this node's associated string.
344 /// \param Edge The label on the edge leaving \p Parent to this node.
346 /// \returns A pointer to the allocated leaf node.
347 SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, size_t StartIdx,
350 assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
352 SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx,
356 Parent.Children[Edge] = N;
361 /// Allocate an internal node and add it to the tree.
363 /// \param Parent The parent of this node. Only null when allocating the root.
364 /// \param StartIdx The start index of this node's associated string.
365 /// \param EndIdx The end index of this node's associated string.
366 /// \param Edge The label on the edge leaving \p Parent to this node.
368 /// \returns A pointer to the allocated internal node.
369 SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, size_t StartIdx,
370 size_t EndIdx, unsigned Edge) {
372 assert(StartIdx <= EndIdx && "String can't start after it ends!");
373 assert(!(!Parent && StartIdx != EmptyIdx) &&
374 "Non-root internal nodes must have parents!");
376 size_t *E = new (InternalEndIdxAllocator) size_t(EndIdx);
377 SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx,
382 Parent->Children[Edge] = N;
387 /// \brief Set the suffix indices of the leaves to the start indices of their
388 /// respective suffixes. Also stores each leaf in \p LeafVector at its
389 /// respective suffix index.
391 /// \param[in] CurrNode The node currently being visited.
392 /// \param CurrIdx The current index of the string being visited.
393 void setSuffixIndices(SuffixTreeNode &CurrNode, size_t CurrIdx) {
395 bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
397 // Store the length of the concatenation of all strings from the root to
399 if (!CurrNode.isRoot()) {
400 if (CurrNode.ConcatLen == 0)
401 CurrNode.ConcatLen = CurrNode.size();
404 CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
407 // Traverse the tree depth-first.
408 for (auto &ChildPair : CurrNode.Children) {
409 assert(ChildPair.second && "Node had a null child!");
410 setSuffixIndices(*ChildPair.second,
411 CurrIdx + ChildPair.second->size());
414 // Is this node a leaf?
416 // If yes, give it a suffix index and bump its parent's occurrence count.
417 CurrNode.SuffixIdx = Str.size() - CurrIdx;
418 assert(CurrNode.Parent && "CurrNode had no parent!");
419 CurrNode.Parent->OccurrenceCount++;
421 // Store the leaf in the leaf vector for pruning later.
422 LeafVector[CurrNode.SuffixIdx] = &CurrNode;
426 /// \brief Construct the suffix tree for the prefix of the input ending at
429 /// Used to construct the full suffix tree iteratively. At the end of each
430 /// step, the constructed suffix tree is either a valid suffix tree, or a
431 /// suffix tree with implicit suffixes. At the end of the final step, the
432 /// suffix tree is a valid tree.
434 /// \param EndIdx The end index of the current prefix in the main string.
435 /// \param SuffixesToAdd The number of suffixes that must be added
436 /// to complete the suffix tree at the current phase.
438 /// \returns The number of suffixes that have not been added at the end of
440 unsigned extend(size_t EndIdx, size_t SuffixesToAdd) {
441 SuffixTreeNode *NeedsLink = nullptr;
443 while (SuffixesToAdd > 0) {
445 // Are we waiting to add anything other than just the last character?
446 if (Active.Len == 0) {
447 // If not, then say the active index is the end index.
451 assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
453 // The first character in the current substring we're looking at.
454 unsigned FirstChar = Str[Active.Idx];
456 // Have we inserted anything starting with FirstChar at the current node?
457 if (Active.Node->Children.count(FirstChar) == 0) {
458 // If not, then we can just insert a leaf and move too the next step.
459 insertLeaf(*Active.Node, EndIdx, FirstChar);
461 // The active node is an internal node, and we visited it, so it must
462 // need a link if it doesn't have one.
464 NeedsLink->Link = Active.Node;
468 // There's a match with FirstChar, so look for the point in the tree to
469 // insert a new node.
470 SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
472 size_t SubstringLen = NextNode->size();
474 // Is the current suffix we're trying to insert longer than the size of
475 // the child we want to move to?
476 if (Active.Len >= SubstringLen) {
477 // If yes, then consume the characters we've seen and move to the next
479 Active.Idx += SubstringLen;
480 Active.Len -= SubstringLen;
481 Active.Node = NextNode;
485 // Otherwise, the suffix we're trying to insert must be contained in the
486 // next node we want to move to.
487 unsigned LastChar = Str[EndIdx];
489 // Is the string we're trying to insert a substring of the next node?
490 if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
491 // If yes, then we're done for this step. Remember our insertion point
492 // and move to the next end index. At this point, we have an implicit
494 if (NeedsLink && !Active.Node->isRoot()) {
495 NeedsLink->Link = Active.Node;
503 // The string we're trying to insert isn't a substring of the next node,
504 // but matches up to a point. Split the node.
506 // For example, say we ended our search at a node n and we're trying to
507 // insert ABD. Then we'll create a new node s for AB, reduce n to just
508 // representing C, and insert a new leaf node l to represent d. This
509 // allows us to ensure that if n was a leaf, it remains a leaf.
511 // | ABC ---split---> | AB
516 // The node s from the diagram
517 SuffixTreeNode *SplitNode =
518 insertInternalNode(Active.Node,
520 NextNode->StartIdx + Active.Len - 1,
523 // Insert the new node representing the new substring into the tree as
524 // a child of the split node. This is the node l from the diagram.
525 insertLeaf(*SplitNode, EndIdx, LastChar);
527 // Make the old node a child of the split node and update its start
528 // index. This is the node n from the diagram.
529 NextNode->StartIdx += Active.Len;
530 NextNode->Parent = SplitNode;
531 SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
533 // SplitNode is an internal node, update the suffix link.
535 NeedsLink->Link = SplitNode;
537 NeedsLink = SplitNode;
540 // We've added something new to the tree, so there's one less suffix to
544 if (Active.Node->isRoot()) {
545 if (Active.Len > 0) {
547 Active.Idx = EndIdx - SuffixesToAdd + 1;
550 // Start the next phase at the next smallest suffix.
551 Active.Node = Active.Node->Link;
555 return SuffixesToAdd;
560 /// Find all repeated substrings that satisfy \p BenefitFn.
562 /// If a substring appears at least twice, then it must be represented by
563 /// an internal node which appears in at least two suffixes. Each suffix is
564 /// represented by a leaf node. To do this, we visit each internal node in
565 /// the tree, using the leaf children of each internal node. If an internal
566 /// node represents a beneficial substring, then we use each of its leaf
567 /// children to find the locations of its substring.
569 /// \param[out] CandidateList Filled with candidates representing each
570 /// beneficial substring.
571 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each
572 /// type of candidate.
573 /// \param BenefitFn The function to satisfy.
575 /// \returns The length of the longest candidate found.
576 size_t findCandidates(std::vector<Candidate> &CandidateList,
577 std::vector<OutlinedFunction> &FunctionList,
578 const std::function<unsigned(SuffixTreeNode &, size_t, unsigned)>
581 CandidateList.clear();
582 FunctionList.clear();
586 for (SuffixTreeNode* Leaf : LeafVector) {
587 assert(Leaf && "Leaves in LeafVector cannot be null!");
591 assert(Leaf->Parent && "All leaves must have parents!");
592 SuffixTreeNode &Parent = *(Leaf->Parent);
594 // If it doesn't appear enough, or we already outlined from it, skip it.
595 if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
598 size_t StringLen = Leaf->ConcatLen - Leaf->size();
600 // How many instructions would outlining this string save?
601 unsigned Benefit = BenefitFn(Parent,
602 StringLen, Str[Leaf->SuffixIdx + StringLen - 1]);
604 // If it's not beneficial, skip it.
608 if (StringLen > MaxLen)
611 unsigned OccurrenceCount = 0;
612 for (auto &ChildPair : Parent.Children) {
613 SuffixTreeNode *M = ChildPair.second;
615 // Is it a leaf? If so, we have an occurrence of this candidate.
616 if (M && M->IsInTree && M->isLeaf()) {
618 CandidateList.emplace_back(M->SuffixIdx, StringLen, FnIdx);
619 CandidateList.back().Benefit = Benefit;
624 // Save the function for the new candidate sequence.
625 std::vector<unsigned> CandidateSequence;
626 for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
627 CandidateSequence.push_back(Str[i]);
629 FunctionList.emplace_back(FnIdx, OccurrenceCount, CandidateSequence,
632 // Move to the next function.
634 Parent.IsInTree = false;
640 /// Construct a suffix tree from a sequence of unsigned integers.
642 /// \param Str The string to construct the suffix tree for.
643 SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
644 Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
645 Root->IsInTree = true;
647 LeafVector = std::vector<SuffixTreeNode*>(Str.size());
649 // Keep track of the number of suffixes we have to add of the current
651 size_t SuffixesToAdd = 0;
654 // Construct the suffix tree iteratively on each prefix of the string.
655 // PfxEndIdx is the end index of the current prefix.
656 // End is one past the last element in the string.
657 for (size_t PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; PfxEndIdx++) {
659 LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
660 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
663 // Set the suffix indices of each leaf.
664 assert(Root && "Root node can't be nullptr!");
665 setSuffixIndices(*Root, 0);
669 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
670 struct InstructionMapper {
672 /// \brief The next available integer to assign to a \p MachineInstr that
673 /// cannot be outlined.
675 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
676 unsigned IllegalInstrNumber = -3;
678 /// \brief The next available integer to assign to a \p MachineInstr that can
680 unsigned LegalInstrNumber = 0;
682 /// Correspondence from \p MachineInstrs to unsigned integers.
683 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
684 InstructionIntegerMap;
686 /// Corresponcence from unsigned integers to \p MachineInstrs.
687 /// Inverse of \p InstructionIntegerMap.
688 DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
690 /// The vector of unsigned integers that the module is mapped to.
691 std::vector<unsigned> UnsignedVec;
693 /// \brief Stores the location of the instruction associated with the integer
694 /// at index i in \p UnsignedVec for each index i.
695 std::vector<MachineBasicBlock::iterator> InstrList;
697 /// \brief Maps \p *It to a legal integer.
699 /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
700 /// \p IntegerInstructionMap, and \p LegalInstrNumber.
702 /// \returns The integer that \p *It was mapped to.
703 unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
705 // Get the integer for this instruction or give it the current
707 InstrList.push_back(It);
708 MachineInstr &MI = *It;
710 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
712 std::tie(ResultIt, WasInserted) =
713 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
714 unsigned MINumber = ResultIt->second;
716 // There was an insertion.
719 IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
722 UnsignedVec.push_back(MINumber);
724 // Make sure we don't overflow or use any integers reserved by the DenseMap.
725 if (LegalInstrNumber >= IllegalInstrNumber)
726 report_fatal_error("Instruction mapping overflow!");
728 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey()
729 && "Tried to assign DenseMap tombstone or empty key to instruction.");
730 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey()
731 && "Tried to assign DenseMap tombstone or empty key to instruction.");
736 /// Maps \p *It to an illegal integer.
738 /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
740 /// \returns The integer that \p *It was mapped to.
741 unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
742 unsigned MINumber = IllegalInstrNumber;
744 InstrList.push_back(It);
745 UnsignedVec.push_back(IllegalInstrNumber);
746 IllegalInstrNumber--;
748 assert(LegalInstrNumber < IllegalInstrNumber &&
749 "Instruction mapping overflow!");
751 assert(IllegalInstrNumber !=
752 DenseMapInfo<unsigned>::getEmptyKey() &&
753 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
755 assert(IllegalInstrNumber !=
756 DenseMapInfo<unsigned>::getTombstoneKey() &&
757 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
762 /// \brief Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
763 /// and appends it to \p UnsignedVec and \p InstrList.
765 /// Two instructions are assigned the same integer if they are identical.
766 /// If an instruction is deemed unsafe to outline, then it will be assigned an
767 /// unique integer. The resulting mapping is placed into a suffix tree and
768 /// queried for candidates.
770 /// \param MBB The \p MachineBasicBlock to be translated into integers.
771 /// \param TRI \p TargetRegisterInfo for the module.
772 /// \param TII \p TargetInstrInfo for the module.
773 void convertToUnsignedVec(MachineBasicBlock &MBB,
774 const TargetRegisterInfo &TRI,
775 const TargetInstrInfo &TII) {
776 for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
779 // Keep track of where this instruction is in the module.
780 switch(TII.getOutliningType(*It)) {
781 case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
782 mapToIllegalUnsigned(It);
785 case TargetInstrInfo::MachineOutlinerInstrType::Legal:
786 mapToLegalUnsigned(It);
789 case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
794 // After we're done every insertion, uniquely terminate this part of the
795 // "string". This makes sure we won't match across basic block or function
796 // boundaries since the "end" is encoded uniquely and thus appears in no
797 // repeated substring.
798 InstrList.push_back(MBB.end());
799 UnsignedVec.push_back(IllegalInstrNumber);
800 IllegalInstrNumber--;
803 InstructionMapper() {
804 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
806 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
807 "DenseMapInfo<unsigned>'s empty key isn't -1!");
808 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
809 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
813 /// \brief An interprocedural pass which finds repeated sequences of
814 /// instructions and replaces them with calls to functions.
816 /// Each instruction is mapped to an unsigned integer and placed in a string.
817 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
818 /// is then repeatedly queried for repeated sequences of instructions. Each
819 /// non-overlapping repeated sequence is then placed in its own
820 /// \p MachineFunction and each instance is then replaced with a call to that
822 struct MachineOutliner : public ModulePass {
826 StringRef getPassName() const override { return "Machine Outliner"; }
828 void getAnalysisUsage(AnalysisUsage &AU) const override {
829 AU.addRequired<MachineModuleInfo>();
830 AU.addPreserved<MachineModuleInfo>();
831 AU.setPreservesAll();
832 ModulePass::getAnalysisUsage(AU);
835 MachineOutliner() : ModulePass(ID) {
836 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
839 /// \brief Replace the sequences of instructions represented by the
840 /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
841 /// described in \p FunctionList.
843 /// \param M The module we are outlining from.
844 /// \param CandidateList A list of candidates to be outlined.
845 /// \param FunctionList A list of functions to be inserted into the module.
846 /// \param Mapper Contains the instruction mappings for the module.
847 bool outline(Module &M, const ArrayRef<Candidate> &CandidateList,
848 std::vector<OutlinedFunction> &FunctionList,
849 InstructionMapper &Mapper);
851 /// Creates a function for \p OF and inserts it into the module.
852 MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
853 InstructionMapper &Mapper);
855 /// Find potential outlining candidates and store them in \p CandidateList.
857 /// For each type of potential candidate, also build an \p OutlinedFunction
858 /// struct containing the information to build the function for that
861 /// \param[out] CandidateList Filled with outlining candidates for the module.
862 /// \param[out] FunctionList Filled with functions corresponding to each type
864 /// \param ST The suffix tree for the module.
865 /// \param TII TargetInstrInfo for the module.
867 /// \returns The length of the longest candidate found. 0 if there are none.
868 unsigned buildCandidateList(std::vector<Candidate> &CandidateList,
869 std::vector<OutlinedFunction> &FunctionList,
871 InstructionMapper &Mapper,
872 const TargetInstrInfo &TII);
874 /// \brief Remove any overlapping candidates that weren't handled by the
875 /// suffix tree's pruning method.
877 /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
878 /// If a short candidate is chosen for outlining, then a longer candidate
879 /// which has that short candidate as a suffix is chosen, the tree's pruning
880 /// method will not find it. Thus, we need to prune before outlining as well.
882 /// \param[in,out] CandidateList A list of outlining candidates.
883 /// \param[in,out] FunctionList A list of functions to be outlined.
884 /// \param MaxCandidateLen The length of the longest candidate.
885 /// \param TII TargetInstrInfo for the module.
886 void pruneOverlaps(std::vector<Candidate> &CandidateList,
887 std::vector<OutlinedFunction> &FunctionList,
888 unsigned MaxCandidateLen,
889 const TargetInstrInfo &TII);
891 /// Construct a suffix tree on the instructions in \p M and outline repeated
892 /// strings from that tree.
893 bool runOnModule(Module &M) override;
896 } // Anonymous namespace.
898 char MachineOutliner::ID = 0;
901 ModulePass *createMachineOutlinerPass() { return new MachineOutliner(); }
904 INITIALIZE_PASS(MachineOutliner, "machine-outliner",
905 "Machine Function Outliner", false, false)
907 void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
908 std::vector<OutlinedFunction> &FunctionList,
909 unsigned MaxCandidateLen,
910 const TargetInstrInfo &TII) {
911 // TODO: Experiment with interval trees or other interval-checking structures
912 // to lower the time complexity of this function.
913 // TODO: Can we do better than the simple greedy choice?
914 // Check for overlaps in the range.
915 // This is O(MaxCandidateLen * CandidateList.size()).
916 for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
919 OutlinedFunction &F1 = FunctionList[C1.FunctionIdx];
921 // If we removed this candidate, skip it.
922 if (!C1.InCandidateList)
925 // Is it still worth it to outline C1?
926 if (F1.Benefit < 1 || F1.OccurrenceCount < 2) {
927 assert(F1.OccurrenceCount > 0 &&
928 "Can't remove OutlinedFunction with no occurrences!");
929 F1.OccurrenceCount--;
930 C1.InCandidateList = false;
934 // The minimum start index of any candidate that could overlap with this
936 unsigned FarthestPossibleIdx = 0;
938 // Either the index is 0, or it's at most MaxCandidateLen indices away.
939 if (C1.StartIdx > MaxCandidateLen)
940 FarthestPossibleIdx = C1.StartIdx - MaxCandidateLen;
942 // Compare against the candidates in the list that start at at most
943 // FarthestPossibleIdx indices away from C1. There are at most
944 // MaxCandidateLen of these.
945 for (auto Sit = It + 1; Sit != Et; Sit++) {
946 Candidate &C2 = *Sit;
947 OutlinedFunction &F2 = FunctionList[C2.FunctionIdx];
949 // Is this candidate too far away to overlap?
950 if (C2.StartIdx < FarthestPossibleIdx)
953 // Did we already remove this candidate in a previous step?
954 if (!C2.InCandidateList)
957 // Is the function beneficial to outline?
958 if (F2.OccurrenceCount < 2 || F2.Benefit < 1) {
959 // If not, remove this candidate and move to the next one.
960 assert(F2.OccurrenceCount > 0 &&
961 "Can't remove OutlinedFunction with no occurrences!");
962 F2.OccurrenceCount--;
963 C2.InCandidateList = false;
967 size_t C2End = C2.StartIdx + C2.Len - 1;
969 // Do C1 and C2 overlap?
972 // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
974 // We sorted our candidate list so C2Start <= C1Start. We know that
975 // C2End > C2Start since each candidate has length >= 2. Therefore, all we
976 // have to check is C2End < C2Start to see if we overlap.
977 if (C2End < C1.StartIdx)
980 // C1 and C2 overlap.
981 // We need to choose the better of the two.
983 // Approximate this by picking the one which would have saved us the
984 // most instructions before any pruning.
985 if (C1.Benefit >= C2.Benefit) {
987 // C1 is better, so remove C2 and update C2's OutlinedFunction to
988 // reflect the removal.
989 assert(F2.OccurrenceCount > 0 &&
990 "Can't remove OutlinedFunction with no occurrences!");
991 F2.OccurrenceCount--;
992 F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(),
997 C2.InCandidateList = false;
1000 dbgs() << "- Removed C2. \n";
1001 dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n";
1002 dbgs() << "--- C2's benefit: " << F2.Benefit << "\n";
1006 // C2 is better, so remove C1 and update C1's OutlinedFunction to
1007 // reflect the removal.
1008 assert(F1.OccurrenceCount > 0 &&
1009 "Can't remove OutlinedFunction with no occurrences!");
1010 F1.OccurrenceCount--;
1011 F1.Benefit = TII.getOutliningBenefit(F1.Sequence.size(),
1015 C1.InCandidateList = false;
1018 dbgs() << "- Removed C1. \n";
1019 dbgs() << "--- Num fns left for C1: " << F1.OccurrenceCount << "\n";
1020 dbgs() << "--- C1's benefit: " << F1.Benefit << "\n";
1023 // C1 is out, so we don't have to compare it against anyone else.
1031 MachineOutliner::buildCandidateList(std::vector<Candidate> &CandidateList,
1032 std::vector<OutlinedFunction> &FunctionList,
1034 InstructionMapper &Mapper,
1035 const TargetInstrInfo &TII) {
1037 std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1038 size_t MaxCandidateLen = 0; // Length of the longest candidate.
1040 // Function for maximizing query in the suffix tree.
1041 // This allows us to define more fine-grained types of things to outline in
1042 // the target without putting target-specific info in the suffix tree.
1043 auto BenefitFn = [&TII, &Mapper](const SuffixTreeNode &Curr,
1044 size_t StringLen, unsigned EndVal) {
1046 // The root represents the empty string.
1050 // Is this long enough to outline?
1051 // TODO: Let the target decide how "long" a string is in terms of the sizes
1052 // of the instructions in the string. For example, if a call instruction
1053 // is smaller than a one instruction string, we should outline that string.
1057 size_t Occurrences = Curr.OccurrenceCount;
1059 // Anything we want to outline has to appear at least twice.
1060 if (Occurrences < 2)
1063 // Check if the last instruction in the sequence is a return.
1064 MachineInstr *LastInstr =
1065 Mapper.IntegerInstructionMap[EndVal];
1066 assert(LastInstr && "Last instruction in sequence was unmapped!");
1068 // The only way a terminator could be mapped as legal is if it was safe to
1070 bool IsTailCall = LastInstr->isTerminator();
1071 return TII.getOutliningBenefit(StringLen, Occurrences, IsTailCall);
1074 MaxCandidateLen = ST.findCandidates(CandidateList, FunctionList, BenefitFn);
1076 for (auto &OF : FunctionList)
1077 OF.IsTailCall = Mapper.
1078 IntegerInstructionMap[OF.Sequence.back()]->isTerminator();
1080 // Sort the candidates in decending order. This will simplify the outlining
1081 // process when we have to remove the candidates from the mapping by
1082 // allowing us to cut them out without keeping track of an offset.
1083 std::stable_sort(CandidateList.begin(), CandidateList.end());
1085 return MaxCandidateLen;
1089 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1090 InstructionMapper &Mapper) {
1092 // Create the function name. This should be unique. For now, just hash the
1093 // module name and include it in the function name plus the number of this
1095 std::ostringstream NameStream;
1096 NameStream << "OUTLINED_FUNCTION" << "_" << OF.Name;
1098 // Create the function using an IR-level function.
1099 LLVMContext &C = M.getContext();
1100 Function *F = dyn_cast<Function>(
1101 M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1102 assert(F && "Function was null!");
1104 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1105 // which gives us better results when we outline from linkonceodr functions.
1106 F->setLinkage(GlobalValue::PrivateLinkage);
1107 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1109 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1110 IRBuilder<> Builder(EntryBB);
1111 Builder.CreateRetVoid();
1113 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1114 MachineFunction &MF = MMI.getMachineFunction(*F);
1115 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1116 const TargetSubtargetInfo &STI = MF.getSubtarget();
1117 const TargetInstrInfo &TII = *STI.getInstrInfo();
1119 // Insert the new function into the module.
1120 MF.insert(MF.begin(), &MBB);
1122 TII.insertOutlinerPrologue(MBB, MF, OF.IsTailCall);
1124 // Copy over the instructions for the function using the integer mappings in
1126 for (unsigned Str : OF.Sequence) {
1127 MachineInstr *NewMI =
1128 MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1129 NewMI->dropMemRefs();
1131 // Don't keep debug information for outlined instructions.
1132 // FIXME: This means outlined functions are currently undebuggable.
1133 NewMI->setDebugLoc(DebugLoc());
1134 MBB.insert(MBB.end(), NewMI);
1137 TII.insertOutlinerEpilogue(MBB, MF, OF.IsTailCall);
1142 bool MachineOutliner::outline(Module &M,
1143 const ArrayRef<Candidate> &CandidateList,
1144 std::vector<OutlinedFunction> &FunctionList,
1145 InstructionMapper &Mapper) {
1147 bool OutlinedSomething = false;
1149 // Replace the candidates with calls to their respective outlined functions.
1150 for (const Candidate &C : CandidateList) {
1152 // Was the candidate removed during pruneOverlaps?
1153 if (!C.InCandidateList)
1156 // If not, then look at its OutlinedFunction.
1157 OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1159 // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1160 if (OF.OccurrenceCount < 2 || OF.Benefit < 1)
1163 // If not, then outline it.
1164 assert(C.StartIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
1165 MachineBasicBlock *MBB = (*Mapper.InstrList[C.StartIdx]).getParent();
1166 MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.StartIdx];
1167 unsigned EndIdx = C.StartIdx + C.Len - 1;
1169 assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
1170 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
1171 assert(EndIt != MBB->end() && "EndIt out of bounds!");
1173 EndIt++; // Erase needs one past the end index.
1175 // Does this candidate have a function yet?
1177 OF.MF = createOutlinedFunction(M, OF, Mapper);
1181 MachineFunction *MF = OF.MF;
1182 const TargetSubtargetInfo &STI = MF->getSubtarget();
1183 const TargetInstrInfo &TII = *STI.getInstrInfo();
1185 // Insert a call to the new function and erase the old sequence.
1186 TII.insertOutlinedCall(M, *MBB, StartIt, *MF, OF.IsTailCall);
1187 StartIt = Mapper.InstrList[C.StartIdx];
1188 MBB->erase(StartIt, EndIt);
1190 OutlinedSomething = true;
1197 dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";
1200 return OutlinedSomething;
1203 bool MachineOutliner::runOnModule(Module &M) {
1205 // Is there anything in the module at all?
1209 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1210 const TargetSubtargetInfo &STI = MMI.getMachineFunction(*M.begin())
1212 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
1213 const TargetInstrInfo *TII = STI.getInstrInfo();
1215 InstructionMapper Mapper;
1217 // Build instruction mappings for each function in the module.
1218 for (Function &F : M) {
1219 MachineFunction &MF = MMI.getMachineFunction(F);
1221 // Is the function empty? Safe to outline from?
1222 if (F.empty() || !TII->isFunctionSafeToOutlineFrom(MF))
1225 // If it is, look at each MachineBasicBlock in the function.
1226 for (MachineBasicBlock &MBB : MF) {
1228 // Is there anything in MBB?
1233 Mapper.convertToUnsignedVec(MBB, *TRI, *TII);
1237 // Construct a suffix tree, use it to find candidates, and then outline them.
1238 SuffixTree ST(Mapper.UnsignedVec);
1239 std::vector<Candidate> CandidateList;
1240 std::vector<OutlinedFunction> FunctionList;
1242 // Find all of the outlining candidates.
1243 unsigned MaxCandidateLen =
1244 buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
1246 // Remove candidates that overlap with other candidates.
1247 pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII);
1249 // Outline each of the candidates and return true if something was outlined.
1250 return outline(M, CandidateList, FunctionList, Mapper);