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 /// * buildOutlinedFrame
29 /// * insertOutlinedCall
30 /// * isFunctionSafeToOutlineFrom
32 /// in order to make use of the MachineOutliner.
34 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
35 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
36 /// how this pass works, the talk is available on YouTube at
38 /// https://www.youtube.com/watch?v=yorld-WSOeU
40 /// The slides for the talk are available at
42 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
44 /// The talk provides an overview of how the outliner finds candidates and
45 /// ultimately outlines them. It describes how the main data structure for this
46 /// pass, the suffix tree, is queried and purged for candidates. It also gives
47 /// a simplified suffix tree construction algorithm for suffix trees based off
48 /// of the algorithm actually used here, Ukkonen's algorithm.
50 /// For the original RFC for this pass, please see
52 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
54 /// For more information on the suffix tree data structure, please see
55 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
57 //===----------------------------------------------------------------------===//
58 #include "llvm/CodeGen/MachineOutliner.h"
59 #include "llvm/ADT/DenseMap.h"
60 #include "llvm/ADT/Statistic.h"
61 #include "llvm/ADT/Twine.h"
62 #include "llvm/CodeGen/MachineFunction.h"
63 #include "llvm/CodeGen/MachineModuleInfo.h"
64 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
65 #include "llvm/CodeGen/MachineRegisterInfo.h"
66 #include "llvm/CodeGen/Passes.h"
67 #include "llvm/CodeGen/TargetInstrInfo.h"
68 #include "llvm/CodeGen/TargetSubtargetInfo.h"
69 #include "llvm/IR/DIBuilder.h"
70 #include "llvm/IR/IRBuilder.h"
71 #include "llvm/IR/Mangler.h"
72 #include "llvm/Support/Allocator.h"
73 #include "llvm/Support/CommandLine.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/raw_ostream.h"
82 #define DEBUG_TYPE "machine-outliner"
86 using namespace outliner;
88 STATISTIC(NumOutlined, "Number of candidates outlined");
89 STATISTIC(FunctionsCreated, "Number of functions created");
91 // Set to true if the user wants the outliner to run on linkonceodr linkage
92 // functions. This is false by default because the linker can dedupe linkonceodr
93 // functions. Since the outliner is confined to a single module (modulo LTO),
94 // this is off by default. It should, however, be the default behaviour in
96 static cl::opt<bool> EnableLinkOnceODROutlining(
97 "enable-linkonceodr-outlining",
99 cl::desc("Enable the machine outliner on linkonceodr functions"),
104 /// Represents an undefined index in the suffix tree.
105 const unsigned EmptyIdx = -1;
107 /// A node in a suffix tree which represents a substring or suffix.
109 /// Each node has either no children or at least two children, with the root
110 /// being a exception in the empty tree.
112 /// Children are represented as a map between unsigned integers and nodes. If
113 /// a node N has a child M on unsigned integer k, then the mapping represented
114 /// by N is a proper prefix of the mapping represented by M. Note that this,
115 /// although similar to a trie is somewhat different: each node stores a full
116 /// substring of the full mapping rather than a single character state.
118 /// Each internal node contains a pointer to the internal node representing
119 /// the same string, but with the first character chopped off. This is stored
120 /// in \p Link. Each leaf node stores the start index of its respective
121 /// suffix in \p SuffixIdx.
122 struct SuffixTreeNode {
124 /// The children of this node.
126 /// A child existing on an unsigned integer implies that from the mapping
127 /// represented by the current node, there is a way to reach another
128 /// mapping by tacking that character on the end of the current string.
129 DenseMap<unsigned, SuffixTreeNode *> Children;
131 /// A flag set to false if the node has been pruned from the tree.
132 bool IsInTree = true;
134 /// The start index of this node's substring in the main string.
135 unsigned StartIdx = EmptyIdx;
137 /// The end index of this node's substring in the main string.
139 /// Every leaf node must have its \p EndIdx incremented at the end of every
140 /// step in the construction algorithm. To avoid having to update O(N)
141 /// nodes individually at the end of every step, the end index is stored
143 unsigned *EndIdx = nullptr;
145 /// For leaves, the start index of the suffix represented by this node.
147 /// For all other nodes, this is ignored.
148 unsigned SuffixIdx = EmptyIdx;
150 /// For internal nodes, a pointer to the internal node representing
151 /// the same sequence with the first character chopped off.
153 /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
154 /// Ukkonen's algorithm does to achieve linear-time construction is
155 /// keep track of which node the next insert should be at. This makes each
156 /// insert O(1), and there are a total of O(N) inserts. The suffix link
157 /// helps with inserting children of internal nodes.
159 /// Say we add a child to an internal node with associated mapping S. The
160 /// next insertion must be at the node representing S - its first character.
161 /// This is given by the way that we iteratively build the tree in Ukkonen's
162 /// algorithm. The main idea is to look at the suffixes of each prefix in the
163 /// string, starting with the longest suffix of the prefix, and ending with
164 /// the shortest. Therefore, if we keep pointers between such nodes, we can
165 /// move to the next insertion point in O(1) time. If we don't, then we'd
166 /// have to query from the root, which takes O(N) time. This would make the
167 /// construction algorithm O(N^2) rather than O(N).
168 SuffixTreeNode *Link = nullptr;
170 /// The parent of this node. Every node except for the root has a parent.
171 SuffixTreeNode *Parent = nullptr;
173 /// The number of times this node's string appears in the tree.
175 /// This is equal to the number of leaf children of the string. It represents
176 /// the number of suffixes that the node's string is a prefix of.
177 unsigned OccurrenceCount = 0;
179 /// The length of the string formed by concatenating the edge labels from the
180 /// root to this node.
181 unsigned ConcatLen = 0;
183 /// Returns true if this node is a leaf.
184 bool isLeaf() const { return SuffixIdx != EmptyIdx; }
186 /// Returns true if this node is the root of its owning \p SuffixTree.
187 bool isRoot() const { return StartIdx == EmptyIdx; }
189 /// Return the number of elements in the substring associated with this node.
190 size_t size() const {
192 // Is it the root? If so, it's the empty string so return 0.
196 assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
198 // Size = the number of elements in the string.
199 // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
200 return *EndIdx - StartIdx + 1;
203 SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
204 SuffixTreeNode *Parent)
205 : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
210 /// A data structure for fast substring queries.
212 /// Suffix trees represent the suffixes of their input strings in their leaves.
213 /// A suffix tree is a type of compressed trie structure where each node
214 /// represents an entire substring rather than a single character. Each leaf
215 /// of the tree is a suffix.
217 /// A suffix tree can be seen as a type of state machine where each state is a
218 /// substring of the full string. The tree is structured so that, for a string
219 /// of length N, there are exactly N leaves in the tree. This structure allows
220 /// us to quickly find repeated substrings of the input string.
222 /// In this implementation, a "string" is a vector of unsigned integers.
223 /// These integers may result from hashing some data type. A suffix tree can
224 /// contain 1 or many strings, which can then be queried as one large string.
226 /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
227 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
228 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
229 /// paper is available at
231 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
234 /// Stores each leaf node in the tree.
236 /// This is used for finding outlining candidates.
237 std::vector<SuffixTreeNode *> LeafVector;
239 /// Each element is an integer representing an instruction in the module.
240 ArrayRef<unsigned> Str;
243 /// Maintains each node in the tree.
244 SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
246 /// The root of the suffix tree.
248 /// The root represents the empty string. It is maintained by the
249 /// \p NodeAllocator like every other node in the tree.
250 SuffixTreeNode *Root = nullptr;
252 /// Maintains the end indices of the internal nodes in the tree.
254 /// Each internal node is guaranteed to never have its end index change
255 /// during the construction algorithm; however, leaves must be updated at
256 /// every step. Therefore, we need to store leaf end indices by reference
257 /// to avoid updating O(N) leaves at every step of construction. Thus,
258 /// every internal node must be allocated its own end index.
259 BumpPtrAllocator InternalEndIdxAllocator;
261 /// The end index of each leaf in the tree.
262 unsigned LeafEndIdx = -1;
264 /// Helper struct which keeps track of the next insertion point in
265 /// Ukkonen's algorithm.
267 /// The next node to insert at.
268 SuffixTreeNode *Node;
270 /// The index of the first character in the substring currently being added.
271 unsigned Idx = EmptyIdx;
273 /// The length of the substring we have to add at the current step.
277 /// The point the next insertion will take place at in the
278 /// construction algorithm.
281 /// Allocate a leaf node and add it to the tree.
283 /// \param Parent The parent of this node.
284 /// \param StartIdx The start index of this node's associated string.
285 /// \param Edge The label on the edge leaving \p Parent to this node.
287 /// \returns A pointer to the allocated leaf node.
288 SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
291 assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
293 SuffixTreeNode *N = new (NodeAllocator.Allocate())
294 SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
295 Parent.Children[Edge] = N;
300 /// Allocate an internal node and add it to the tree.
302 /// \param Parent The parent of this node. Only null when allocating the root.
303 /// \param StartIdx The start index of this node's associated string.
304 /// \param EndIdx The end index of this node's associated string.
305 /// \param Edge The label on the edge leaving \p Parent to this node.
307 /// \returns A pointer to the allocated internal node.
308 SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
309 unsigned EndIdx, unsigned Edge) {
311 assert(StartIdx <= EndIdx && "String can't start after it ends!");
312 assert(!(!Parent && StartIdx != EmptyIdx) &&
313 "Non-root internal nodes must have parents!");
315 unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
316 SuffixTreeNode *N = new (NodeAllocator.Allocate())
317 SuffixTreeNode(StartIdx, E, Root, Parent);
319 Parent->Children[Edge] = N;
324 /// Set the suffix indices of the leaves to the start indices of their
325 /// respective suffixes. Also stores each leaf in \p LeafVector at its
326 /// respective suffix index.
328 /// \param[in] CurrNode The node currently being visited.
329 /// \param CurrIdx The current index of the string being visited.
330 void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
332 bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
334 // Store the length of the concatenation of all strings from the root to
336 if (!CurrNode.isRoot()) {
337 if (CurrNode.ConcatLen == 0)
338 CurrNode.ConcatLen = CurrNode.size();
341 CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
344 // Traverse the tree depth-first.
345 for (auto &ChildPair : CurrNode.Children) {
346 assert(ChildPair.second && "Node had a null child!");
347 setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
350 // Is this node a leaf?
352 // If yes, give it a suffix index and bump its parent's occurrence count.
353 CurrNode.SuffixIdx = Str.size() - CurrIdx;
354 assert(CurrNode.Parent && "CurrNode had no parent!");
355 CurrNode.Parent->OccurrenceCount++;
357 // Store the leaf in the leaf vector for pruning later.
358 LeafVector[CurrNode.SuffixIdx] = &CurrNode;
362 /// Construct the suffix tree for the prefix of the input ending at
365 /// Used to construct the full suffix tree iteratively. At the end of each
366 /// step, the constructed suffix tree is either a valid suffix tree, or a
367 /// suffix tree with implicit suffixes. At the end of the final step, the
368 /// suffix tree is a valid tree.
370 /// \param EndIdx The end index of the current prefix in the main string.
371 /// \param SuffixesToAdd The number of suffixes that must be added
372 /// to complete the suffix tree at the current phase.
374 /// \returns The number of suffixes that have not been added at the end of
376 unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
377 SuffixTreeNode *NeedsLink = nullptr;
379 while (SuffixesToAdd > 0) {
381 // Are we waiting to add anything other than just the last character?
382 if (Active.Len == 0) {
383 // If not, then say the active index is the end index.
387 assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
389 // The first character in the current substring we're looking at.
390 unsigned FirstChar = Str[Active.Idx];
392 // Have we inserted anything starting with FirstChar at the current node?
393 if (Active.Node->Children.count(FirstChar) == 0) {
394 // If not, then we can just insert a leaf and move too the next step.
395 insertLeaf(*Active.Node, EndIdx, FirstChar);
397 // The active node is an internal node, and we visited it, so it must
398 // need a link if it doesn't have one.
400 NeedsLink->Link = Active.Node;
404 // There's a match with FirstChar, so look for the point in the tree to
405 // insert a new node.
406 SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
408 unsigned SubstringLen = NextNode->size();
410 // Is the current suffix we're trying to insert longer than the size of
411 // the child we want to move to?
412 if (Active.Len >= SubstringLen) {
413 // If yes, then consume the characters we've seen and move to the next
415 Active.Idx += SubstringLen;
416 Active.Len -= SubstringLen;
417 Active.Node = NextNode;
421 // Otherwise, the suffix we're trying to insert must be contained in the
422 // next node we want to move to.
423 unsigned LastChar = Str[EndIdx];
425 // Is the string we're trying to insert a substring of the next node?
426 if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
427 // If yes, then we're done for this step. Remember our insertion point
428 // and move to the next end index. At this point, we have an implicit
430 if (NeedsLink && !Active.Node->isRoot()) {
431 NeedsLink->Link = Active.Node;
439 // The string we're trying to insert isn't a substring of the next node,
440 // but matches up to a point. Split the node.
442 // For example, say we ended our search at a node n and we're trying to
443 // insert ABD. Then we'll create a new node s for AB, reduce n to just
444 // representing C, and insert a new leaf node l to represent d. This
445 // allows us to ensure that if n was a leaf, it remains a leaf.
447 // | ABC ---split---> | AB
452 // The node s from the diagram
453 SuffixTreeNode *SplitNode =
454 insertInternalNode(Active.Node, NextNode->StartIdx,
455 NextNode->StartIdx + Active.Len - 1, FirstChar);
457 // Insert the new node representing the new substring into the tree as
458 // a child of the split node. This is the node l from the diagram.
459 insertLeaf(*SplitNode, EndIdx, LastChar);
461 // Make the old node a child of the split node and update its start
462 // index. This is the node n from the diagram.
463 NextNode->StartIdx += Active.Len;
464 NextNode->Parent = SplitNode;
465 SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
467 // SplitNode is an internal node, update the suffix link.
469 NeedsLink->Link = SplitNode;
471 NeedsLink = SplitNode;
474 // We've added something new to the tree, so there's one less suffix to
478 if (Active.Node->isRoot()) {
479 if (Active.Len > 0) {
481 Active.Idx = EndIdx - SuffixesToAdd + 1;
484 // Start the next phase at the next smallest suffix.
485 Active.Node = Active.Node->Link;
489 return SuffixesToAdd;
493 /// Construct a suffix tree from a sequence of unsigned integers.
495 /// \param Str The string to construct the suffix tree for.
496 SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
497 Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
498 Root->IsInTree = true;
500 LeafVector = std::vector<SuffixTreeNode *>(Str.size());
502 // Keep track of the number of suffixes we have to add of the current
504 unsigned SuffixesToAdd = 0;
507 // Construct the suffix tree iteratively on each prefix of the string.
508 // PfxEndIdx is the end index of the current prefix.
509 // End is one past the last element in the string.
510 for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
513 LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
514 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
517 // Set the suffix indices of each leaf.
518 assert(Root && "Root node can't be nullptr!");
519 setSuffixIndices(*Root, 0);
523 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
524 struct InstructionMapper {
526 /// The next available integer to assign to a \p MachineInstr that
527 /// cannot be outlined.
529 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
530 unsigned IllegalInstrNumber = -3;
532 /// The next available integer to assign to a \p MachineInstr that can
534 unsigned LegalInstrNumber = 0;
536 /// Correspondence from \p MachineInstrs to unsigned integers.
537 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
538 InstructionIntegerMap;
540 /// Corresponcence from unsigned integers to \p MachineInstrs.
541 /// Inverse of \p InstructionIntegerMap.
542 DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
544 /// The vector of unsigned integers that the module is mapped to.
545 std::vector<unsigned> UnsignedVec;
547 /// Stores the location of the instruction associated with the integer
548 /// at index i in \p UnsignedVec for each index i.
549 std::vector<MachineBasicBlock::iterator> InstrList;
551 /// Maps \p *It to a legal integer.
553 /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
554 /// \p IntegerInstructionMap, and \p LegalInstrNumber.
556 /// \returns The integer that \p *It was mapped to.
557 unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
559 // Get the integer for this instruction or give it the current
561 InstrList.push_back(It);
562 MachineInstr &MI = *It;
564 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
566 std::tie(ResultIt, WasInserted) =
567 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
568 unsigned MINumber = ResultIt->second;
570 // There was an insertion.
573 IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
576 UnsignedVec.push_back(MINumber);
578 // Make sure we don't overflow or use any integers reserved by the DenseMap.
579 if (LegalInstrNumber >= IllegalInstrNumber)
580 report_fatal_error("Instruction mapping overflow!");
582 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
583 "Tried to assign DenseMap tombstone or empty key to instruction.");
584 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
585 "Tried to assign DenseMap tombstone or empty key to instruction.");
590 /// Maps \p *It to an illegal integer.
592 /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
594 /// \returns The integer that \p *It was mapped to.
595 unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
596 unsigned MINumber = IllegalInstrNumber;
598 InstrList.push_back(It);
599 UnsignedVec.push_back(IllegalInstrNumber);
600 IllegalInstrNumber--;
602 assert(LegalInstrNumber < IllegalInstrNumber &&
603 "Instruction mapping overflow!");
605 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
606 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
608 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
609 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
614 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
615 /// and appends it to \p UnsignedVec and \p InstrList.
617 /// Two instructions are assigned the same integer if they are identical.
618 /// If an instruction is deemed unsafe to outline, then it will be assigned an
619 /// unique integer. The resulting mapping is placed into a suffix tree and
620 /// queried for candidates.
622 /// \param MBB The \p MachineBasicBlock to be translated into integers.
623 /// \param TII \p TargetInstrInfo for the function.
624 void convertToUnsignedVec(MachineBasicBlock &MBB,
625 const TargetInstrInfo &TII) {
626 unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB);
628 for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
631 // Keep track of where this instruction is in the module.
632 switch (TII.getOutliningType(It, Flags)) {
633 case InstrType::Illegal:
634 mapToIllegalUnsigned(It);
637 case InstrType::Legal:
638 mapToLegalUnsigned(It);
641 case InstrType::LegalTerminator:
642 mapToLegalUnsigned(It);
643 InstrList.push_back(It);
644 UnsignedVec.push_back(IllegalInstrNumber);
645 IllegalInstrNumber--;
648 case InstrType::Invisible:
653 // After we're done every insertion, uniquely terminate this part of the
654 // "string". This makes sure we won't match across basic block or function
655 // boundaries since the "end" is encoded uniquely and thus appears in no
656 // repeated substring.
657 InstrList.push_back(MBB.end());
658 UnsignedVec.push_back(IllegalInstrNumber);
659 IllegalInstrNumber--;
662 InstructionMapper() {
663 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
665 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
666 "DenseMapInfo<unsigned>'s empty key isn't -1!");
667 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
668 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
672 /// An interprocedural pass which finds repeated sequences of
673 /// instructions and replaces them with calls to functions.
675 /// Each instruction is mapped to an unsigned integer and placed in a string.
676 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
677 /// is then repeatedly queried for repeated sequences of instructions. Each
678 /// non-overlapping repeated sequence is then placed in its own
679 /// \p MachineFunction and each instance is then replaced with a call to that
681 struct MachineOutliner : public ModulePass {
685 /// Set to true if the outliner should consider functions with
686 /// linkonceodr linkage.
687 bool OutlineFromLinkOnceODRs = false;
689 /// Set to true if the outliner should run on all functions in the module
690 /// considered safe for outlining.
691 /// Set to true by default for compatibility with llc's -run-pass option.
692 /// Set when the pass is constructed in TargetPassConfig.
693 bool RunOnAllFunctions = true;
695 // Collection of IR functions created by the outliner.
696 std::vector<Function *> CreatedIRFunctions;
698 StringRef getPassName() const override { return "Machine Outliner"; }
700 void getAnalysisUsage(AnalysisUsage &AU) const override {
701 AU.addRequired<MachineModuleInfo>();
702 AU.addPreserved<MachineModuleInfo>();
703 AU.setPreservesAll();
704 ModulePass::getAnalysisUsage(AU);
707 MachineOutliner() : ModulePass(ID) {
708 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
711 /// Remark output explaining that not outlining a set of candidates would be
712 /// better than outlining that set.
713 void emitNotOutliningCheaperRemark(
714 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
715 OutlinedFunction &OF);
717 /// Remark output explaining that a function was outlined.
718 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
720 /// Find all repeated substrings that satisfy the outlining cost model.
722 /// If a substring appears at least twice, then it must be represented by
723 /// an internal node which appears in at least two suffixes. Each suffix
724 /// is represented by a leaf node. To do this, we visit each internal node
725 /// in the tree, using the leaf children of each internal node. If an
726 /// internal node represents a beneficial substring, then we use each of
727 /// its leaf children to find the locations of its substring.
729 /// \param ST A suffix tree to query.
730 /// \param Mapper Contains outlining mapping information.
731 /// \param[out] CandidateList Filled with candidates representing each
732 /// beneficial substring.
733 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
734 /// each type of candidate.
736 /// \returns The length of the longest candidate found.
738 findCandidates(SuffixTree &ST,
739 InstructionMapper &Mapper,
740 std::vector<std::shared_ptr<Candidate>> &CandidateList,
741 std::vector<OutlinedFunction> &FunctionList);
743 /// Replace the sequences of instructions represented by the
744 /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
745 /// described in \p FunctionList.
747 /// \param M The module we are outlining from.
748 /// \param CandidateList A list of candidates to be outlined.
749 /// \param FunctionList A list of functions to be inserted into the module.
750 /// \param Mapper Contains the instruction mappings for the module.
751 bool outline(Module &M,
752 const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
753 std::vector<OutlinedFunction> &FunctionList,
754 InstructionMapper &Mapper);
756 /// Creates a function for \p OF and inserts it into the module.
757 MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
758 InstructionMapper &Mapper);
760 /// Find potential outlining candidates and store them in \p CandidateList.
762 /// For each type of potential candidate, also build an \p OutlinedFunction
763 /// struct containing the information to build the function for that
766 /// \param[out] CandidateList Filled with outlining candidates for the module.
767 /// \param[out] FunctionList Filled with functions corresponding to each type
769 /// \param ST The suffix tree for the module.
771 /// \returns The length of the longest candidate found. 0 if there are none.
773 buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
774 std::vector<OutlinedFunction> &FunctionList,
775 SuffixTree &ST, InstructionMapper &Mapper);
777 /// Helper function for pruneOverlaps.
778 /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
779 void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
781 /// Remove any overlapping candidates that weren't handled by the
782 /// suffix tree's pruning method.
784 /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
785 /// If a short candidate is chosen for outlining, then a longer candidate
786 /// which has that short candidate as a suffix is chosen, the tree's pruning
787 /// method will not find it. Thus, we need to prune before outlining as well.
789 /// \param[in,out] CandidateList A list of outlining candidates.
790 /// \param[in,out] FunctionList A list of functions to be outlined.
791 /// \param Mapper Contains instruction mapping info for outlining.
792 /// \param MaxCandidateLen The length of the longest candidate.
793 void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
794 std::vector<OutlinedFunction> &FunctionList,
795 InstructionMapper &Mapper, unsigned MaxCandidateLen);
797 /// Construct a suffix tree on the instructions in \p M and outline repeated
798 /// strings from that tree.
799 bool runOnModule(Module &M) override;
801 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
802 /// function for remark emission.
803 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
805 for (const std::shared_ptr<Candidate> &C : OF.Candidates)
806 if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram()))
812 } // Anonymous namespace.
814 char MachineOutliner::ID = 0;
817 ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
818 MachineOutliner *OL = new MachineOutliner();
819 OL->RunOnAllFunctions = RunOnAllFunctions;
825 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
828 void MachineOutliner::emitNotOutliningCheaperRemark(
829 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
830 OutlinedFunction &OF) {
831 Candidate &C = CandidatesForRepeatedSeq.front();
832 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
834 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
835 C.front()->getDebugLoc(), C.getMBB());
836 R << "Did not outline " << NV("Length", StringLen) << " instructions"
837 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
839 << " Bytes from outlining all occurrences ("
840 << NV("OutliningCost", OF.getOutliningCost()) << ")"
841 << " >= Unoutlined instruction bytes ("
842 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
843 << " (Also found at: ";
845 // Tell the user the other places the candidate was found.
846 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
847 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
848 CandidatesForRepeatedSeq[i].front()->getDebugLoc());
858 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
859 MachineBasicBlock *MBB = &*OF.MF->begin();
860 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
861 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
862 MBB->findDebugLoc(MBB->begin()), MBB);
863 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
864 << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
865 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
869 // Tell the user the other places the candidate was found.
870 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
872 // Skip over things that were pruned.
873 if (!OF.Candidates[i]->InCandidateList)
876 R << NV((Twine("StartLoc") + Twine(i)).str(),
877 OF.Candidates[i]->front()->getDebugLoc());
887 unsigned MachineOutliner::findCandidates(
888 SuffixTree &ST, InstructionMapper &Mapper,
889 std::vector<std::shared_ptr<Candidate>> &CandidateList,
890 std::vector<OutlinedFunction> &FunctionList) {
891 CandidateList.clear();
892 FunctionList.clear();
895 // FIXME: Visit internal nodes instead of leaves.
896 for (SuffixTreeNode *Leaf : ST.LeafVector) {
897 assert(Leaf && "Leaves in LeafVector cannot be null!");
901 assert(Leaf->Parent && "All leaves must have parents!");
902 SuffixTreeNode &Parent = *(Leaf->Parent);
904 // If it doesn't appear enough, or we already outlined from it, skip it.
905 if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
908 // Figure out if this candidate is beneficial.
909 unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
911 // Too short to be beneficial; skip it.
912 // FIXME: This isn't necessarily true for, say, X86. If we factor in
913 // instruction lengths we need more information than this.
917 // If this is a beneficial class of candidate, then every one is stored in
919 std::vector<Candidate> CandidatesForRepeatedSeq;
921 // Figure out the call overhead for each instance of the sequence.
922 for (auto &ChildPair : Parent.Children) {
923 SuffixTreeNode *M = ChildPair.second;
925 if (M && M->IsInTree && M->isLeaf()) {
926 // Never visit this leaf again.
928 unsigned StartIdx = M->SuffixIdx;
929 unsigned EndIdx = StartIdx + StringLen - 1;
931 // Trick: Discard some candidates that would be incompatible with the
932 // ones we've already found for this sequence. This will save us some
933 // work in candidate selection.
935 // If two candidates overlap, then we can't outline them both. This
936 // happens when we have candidates that look like, say
938 // AA (where each "A" is an instruction).
940 // We might have some portion of the module that looks like this:
943 // In this case, there are 5 different copies of "AA" in this range, but
944 // at most 3 can be outlined. If only outlining 3 of these is going to
945 // be unbeneficial, then we ought to not bother.
947 // Note that two things DON'T overlap when they look like this:
948 // start1...end1 .... start2...end2
949 // That is, one must either
950 // * End before the other starts
951 // * Start after the other ends
952 if (std::all_of(CandidatesForRepeatedSeq.begin(),
953 CandidatesForRepeatedSeq.end(),
954 [&StartIdx, &EndIdx](const Candidate &C) {
955 return (EndIdx < C.getStartIdx() ||
956 StartIdx > C.getEndIdx());
958 // It doesn't overlap with anything, so we can outline it.
959 // Each sequence is over [StartIt, EndIt].
960 // Save the candidate and its location.
962 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
963 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
965 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
966 EndIt, StartIt->getParent(),
967 FunctionList.size());
972 // We've found something we might want to outline.
973 // Create an OutlinedFunction to store it and check if it'd be beneficial
975 if (CandidatesForRepeatedSeq.empty())
978 // Arbitrarily choose a TII from the first candidate.
979 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
980 const TargetInstrInfo *TII =
981 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
983 OutlinedFunction OF =
984 TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
986 // If we deleted every candidate, then there's nothing to outline.
987 if (OF.Candidates.empty())
990 std::vector<unsigned> Seq;
991 for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
992 Seq.push_back(ST.Str[i]);
994 OF.Name = FunctionList.size();
996 // Is it better to outline this candidate than not?
997 if (OF.getBenefit() < 1) {
998 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
1002 if (StringLen > MaxLen)
1005 // The function is beneficial. Save its candidates to the candidate list
1007 for (std::shared_ptr<Candidate> &C : OF.Candidates)
1008 CandidateList.push_back(C);
1009 FunctionList.push_back(OF);
1011 // Move to the next function.
1012 Parent.IsInTree = false;
1018 // Remove C from the candidate space, and update its OutlinedFunction.
1019 void MachineOutliner::prune(Candidate &C,
1020 std::vector<OutlinedFunction> &FunctionList) {
1021 // Get the OutlinedFunction associated with this Candidate.
1022 OutlinedFunction &F = FunctionList[C.FunctionIdx];
1024 // Update C's associated function's occurrence count.
1027 // Remove C from the CandidateList.
1028 C.InCandidateList = false;
1030 LLVM_DEBUG(dbgs() << "- Removed a Candidate \n";
1031 dbgs() << "--- Num fns left for candidate: "
1032 << F.getOccurrenceCount() << "\n";
1033 dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
1037 void MachineOutliner::pruneOverlaps(
1038 std::vector<std::shared_ptr<Candidate>> &CandidateList,
1039 std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
1040 unsigned MaxCandidateLen) {
1042 // Return true if this candidate became unbeneficial for outlining in a
1044 auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
1046 // Check if the candidate was removed in a previous step.
1047 if (!C.InCandidateList)
1050 // C must be alive. Check if we should remove it.
1051 if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
1052 prune(C, FunctionList);
1056 // C is in the list, and F is still beneficial.
1060 // TODO: Experiment with interval trees or other interval-checking structures
1061 // to lower the time complexity of this function.
1062 // TODO: Can we do better than the simple greedy choice?
1063 // Check for overlaps in the range.
1064 // This is O(MaxCandidateLen * CandidateList.size()).
1065 for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
1067 Candidate &C1 = **It;
1069 // If C1 was already pruned, or its function is no longer beneficial for
1070 // outlining, move to the next candidate.
1071 if (ShouldSkipCandidate(C1))
1074 // The minimum start index of any candidate that could overlap with this
1076 unsigned FarthestPossibleIdx = 0;
1078 // Either the index is 0, or it's at most MaxCandidateLen indices away.
1079 if (C1.getStartIdx() > MaxCandidateLen)
1080 FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
1082 // Compare against the candidates in the list that start at most
1083 // FarthestPossibleIdx indices away from C1. There are at most
1084 // MaxCandidateLen of these.
1085 for (auto Sit = It + 1; Sit != Et; Sit++) {
1086 Candidate &C2 = **Sit;
1088 // Is this candidate too far away to overlap?
1089 if (C2.getStartIdx() < FarthestPossibleIdx)
1092 // If C2 was already pruned, or its function is no longer beneficial for
1093 // outlining, move to the next candidate.
1094 if (ShouldSkipCandidate(C2))
1097 // Do C1 and C2 overlap?
1100 // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
1102 // We sorted our candidate list so C2Start <= C1Start. We know that
1103 // C2End > C2Start since each candidate has length >= 2. Therefore, all we
1104 // have to check is C2End < C2Start to see if we overlap.
1105 if (C2.getEndIdx() < C1.getStartIdx())
1108 // C1 and C2 overlap.
1109 // We need to choose the better of the two.
1111 // Approximate this by picking the one which would have saved us the
1112 // most instructions before any pruning.
1114 // Is C2 a better candidate?
1115 if (C2.Benefit > C1.Benefit) {
1116 // Yes, so prune C1. Since C1 is dead, we don't have to compare it
1117 // against anything anymore, so break.
1118 prune(C1, FunctionList);
1122 // Prune C2 and move on to the next candidate.
1123 prune(C2, FunctionList);
1128 unsigned MachineOutliner::buildCandidateList(
1129 std::vector<std::shared_ptr<Candidate>> &CandidateList,
1130 std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
1131 InstructionMapper &Mapper) {
1133 std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1134 unsigned MaxCandidateLen = 0; // Length of the longest candidate.
1137 findCandidates(ST, Mapper, CandidateList, FunctionList);
1139 // Sort the candidates in decending order. This will simplify the outlining
1140 // process when we have to remove the candidates from the mapping by
1141 // allowing us to cut them out without keeping track of an offset.
1143 CandidateList.begin(), CandidateList.end(),
1144 [](const std::shared_ptr<Candidate> &LHS,
1145 const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
1147 return MaxCandidateLen;
1151 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1152 InstructionMapper &Mapper) {
1154 // Create the function name. This should be unique. For now, just hash the
1155 // module name and include it in the function name plus the number of this
1157 std::ostringstream NameStream;
1158 NameStream << "OUTLINED_FUNCTION_" << OF.Name;
1160 // Create the function using an IR-level function.
1161 LLVMContext &C = M.getContext();
1162 Function *F = dyn_cast<Function>(
1163 M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1164 assert(F && "Function was null!");
1166 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1167 // which gives us better results when we outline from linkonceodr functions.
1168 F->setLinkage(GlobalValue::InternalLinkage);
1169 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1171 // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's
1174 // Set optsize/minsize, so we don't insert padding between outlined
1176 F->addFnAttr(Attribute::OptimizeForSize);
1177 F->addFnAttr(Attribute::MinSize);
1179 // Save F so that we can add debug info later if we need to.
1180 CreatedIRFunctions.push_back(F);
1182 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1183 IRBuilder<> Builder(EntryBB);
1184 Builder.CreateRetVoid();
1186 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1187 MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
1188 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1189 const TargetSubtargetInfo &STI = MF.getSubtarget();
1190 const TargetInstrInfo &TII = *STI.getInstrInfo();
1192 // Insert the new function into the module.
1193 MF.insert(MF.begin(), &MBB);
1195 // Copy over the instructions for the function using the integer mappings in
1197 for (unsigned Str : OF.Sequence) {
1198 MachineInstr *NewMI =
1199 MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1200 NewMI->dropMemRefs();
1202 // Don't keep debug information for outlined instructions.
1203 NewMI->setDebugLoc(DebugLoc());
1204 MBB.insert(MBB.end(), NewMI);
1207 TII.buildOutlinedFrame(MBB, MF, OF);
1209 // If there's a DISubprogram associated with this outlined function, then
1210 // emit debug info for the outlined function.
1211 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
1212 // We have a DISubprogram. Get its DICompileUnit.
1213 DICompileUnit *CU = SP->getUnit();
1214 DIBuilder DB(M, true, CU);
1215 DIFile *Unit = SP->getFile();
1218 // Walk over each IR function we created in the outliner and create
1219 // DISubprograms for each function.
1220 for (Function *F : CreatedIRFunctions) {
1221 // Get the mangled name of the function for the linkage name.
1223 llvm::raw_string_ostream MangledNameStream(Dummy);
1224 Mg.getNameWithPrefix(MangledNameStream, F, false);
1226 DISubprogram *SP = DB.createFunction(
1227 Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
1229 0 /* Line 0 is reserved for compiler-generated code. */,
1230 DB.createSubroutineType(
1231 DB.getOrCreateTypeArray(None)), /* void type */
1232 false, true, 0, /* Line 0 is reserved for compiler-generated code. */
1233 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
1234 true /* Outlined code is optimized code by definition. */);
1236 // Don't add any new variables to the subprogram.
1237 DB.finalizeSubprogram(SP);
1239 // Attach subprogram to the function.
1240 F->setSubprogram(SP);
1243 // We're done with the DIBuilder.
1247 // Outlined functions shouldn't preserve liveness.
1248 MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness);
1249 MF.getRegInfo().freezeReservedRegs(MF);
1253 bool MachineOutliner::outline(
1254 Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
1255 std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
1257 bool OutlinedSomething = false;
1258 // Replace the candidates with calls to their respective outlined functions.
1259 for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
1260 Candidate &C = *Cptr;
1261 // Was the candidate removed during pruneOverlaps?
1262 if (!C.InCandidateList)
1265 // If not, then look at its OutlinedFunction.
1266 OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1268 // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1269 if (OF.getBenefit() < 1)
1272 // Does this candidate have a function yet?
1274 OF.MF = createOutlinedFunction(M, OF, Mapper);
1275 emitOutlinedFunctionRemark(OF);
1279 MachineFunction *MF = OF.MF;
1280 MachineBasicBlock &MBB = *C.getMBB();
1281 MachineBasicBlock::iterator StartIt = C.front();
1282 MachineBasicBlock::iterator EndIt = C.back();
1283 assert(StartIt != C.getMBB()->end() && "StartIt out of bounds!");
1284 assert(EndIt != C.getMBB()->end() && "EndIt out of bounds!");
1286 const TargetSubtargetInfo &STI = MF->getSubtarget();
1287 const TargetInstrInfo &TII = *STI.getInstrInfo();
1289 // Insert a call to the new function and erase the old sequence.
1290 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.MF, C);
1292 // If the caller tracks liveness, then we need to make sure that anything
1293 // we outline doesn't break liveness assumptions.
1294 // The outlined functions themselves currently don't track liveness, but
1295 // we should make sure that the ranges we yank things out of aren't
1297 if (MBB.getParent()->getProperties().hasProperty(
1298 MachineFunctionProperties::Property::TracksLiveness)) {
1299 // Helper lambda for adding implicit def operands to the call instruction.
1300 auto CopyDefs = [&CallInst](MachineInstr &MI) {
1301 for (MachineOperand &MOP : MI.operands()) {
1302 // Skip over anything that isn't a register.
1306 // If it's a def, add it to the call instruction.
1308 CallInst->addOperand(
1309 MachineOperand::CreateReg(MOP.getReg(), true, /* isDef = true */
1310 true /* isImp = true */));
1314 // Copy over the defs in the outlined range.
1315 // First inst in outlined range <-- Anything that's defined in this
1316 // ... .. range has to be added as an implicit
1317 // Last inst in outlined range <-- def to the call instruction.
1318 std::for_each(CallInst, std::next(EndIt), CopyDefs);
1321 // Erase from the point after where the call was inserted up to, and
1322 // including, the final instruction in the sequence.
1323 // Erase needs one past the end, so we need std::next there too.
1324 MBB.erase(std::next(StartIt), std::next(EndIt));
1325 OutlinedSomething = true;
1331 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1333 return OutlinedSomething;
1336 bool MachineOutliner::runOnModule(Module &M) {
1337 // Check if there's anything in the module. If it's empty, then there's
1338 // nothing to outline.
1342 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1344 // If the user passed -enable-machine-outliner=always or
1345 // -enable-machine-outliner, the pass will run on all functions in the module.
1346 // Otherwise, if the target supports default outlining, it will run on all
1347 // functions deemed by the target to be worth outlining from by default. Tell
1348 // the user how the outliner is running.
1350 dbgs() << "Machine Outliner: Running on ";
1351 if (RunOnAllFunctions)
1352 dbgs() << "all functions";
1354 dbgs() << "target-default functions";
1358 // If the user specifies that they want to outline from linkonceodrs, set
1360 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1362 InstructionMapper Mapper;
1364 // Build instruction mappings for each function in the module. Start by
1365 // iterating over each Function in M.
1366 for (Function &F : M) {
1368 // If there's nothing in F, then there's no reason to try and outline from
1373 // There's something in F. Check if it has a MachineFunction associated with
1375 MachineFunction *MF = MMI.getMachineFunction(F);
1377 // If it doesn't, then there's nothing to outline from. Move to the next
1382 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1384 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
1387 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1388 // If it isn't, then move on to the next Function in the module.
1389 if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
1392 // We have a function suitable for outlining. Iterate over every
1393 // MachineBasicBlock in MF and try to map its instructions to a list of
1394 // unsigned integers.
1395 for (MachineBasicBlock &MBB : *MF) {
1396 // If there isn't anything in MBB, then there's no point in outlining from
1401 // Check if MBB could be the target of an indirect branch. If it is, then
1402 // we don't want to outline from it.
1403 if (MBB.hasAddressTaken())
1406 // MBB is suitable for outlining. Map it to a list of unsigneds.
1407 Mapper.convertToUnsignedVec(MBB, *TII);
1411 // Construct a suffix tree, use it to find candidates, and then outline them.
1412 SuffixTree ST(Mapper.UnsignedVec);
1413 std::vector<std::shared_ptr<Candidate>> CandidateList;
1414 std::vector<OutlinedFunction> FunctionList;
1416 // Find all of the outlining candidates.
1417 unsigned MaxCandidateLen =
1418 buildCandidateList(CandidateList, FunctionList, ST, Mapper);
1420 // Remove candidates that overlap with other candidates.
1421 pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen);
1423 // Outline each of the candidates and return true if something was outlined.
1424 bool OutlinedSomething = outline(M, CandidateList, FunctionList, Mapper);
1426 return OutlinedSomething;