1 //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// Replaces repeated sequences of instructions with function calls.
12 /// This works by placing every instruction from every basic block in a
13 /// suffix tree, and repeatedly querying that tree for repeated sequences of
14 /// instructions. If a sequence of instructions appears often, then it ought
15 /// to be beneficial to pull out into a function.
17 /// The MachineOutliner communicates with a given target using hooks defined in
18 /// TargetInstrInfo.h. The target supplies the outliner with information on how
19 /// a specific sequence of instructions should be outlined. This information
20 /// is used to deduce the number of instructions necessary to
22 /// * Create an outlined function
23 /// * Call that outlined function
25 /// Targets must implement
26 /// * getOutliningCandidateInfo
27 /// * buildOutlinedFrame
28 /// * insertOutlinedCall
29 /// * isFunctionSafeToOutlineFrom
31 /// in order to make use of the MachineOutliner.
33 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
34 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
35 /// how this pass works, the talk is available on YouTube at
37 /// https://www.youtube.com/watch?v=yorld-WSOeU
39 /// The slides for the talk are available at
41 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
43 /// The talk provides an overview of how the outliner finds candidates and
44 /// ultimately outlines them. It describes how the main data structure for this
45 /// pass, the suffix tree, is queried and purged for candidates. It also gives
46 /// a simplified suffix tree construction algorithm for suffix trees based off
47 /// of the algorithm actually used here, Ukkonen's algorithm.
49 /// For the original RFC for this pass, please see
51 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
53 /// For more information on the suffix tree data structure, please see
54 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
56 //===----------------------------------------------------------------------===//
57 #include "llvm/CodeGen/MachineOutliner.h"
58 #include "llvm/ADT/DenseMap.h"
59 #include "llvm/ADT/Statistic.h"
60 #include "llvm/ADT/Twine.h"
61 #include "llvm/CodeGen/MachineFunction.h"
62 #include "llvm/CodeGen/MachineModuleInfo.h"
63 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
64 #include "llvm/CodeGen/MachineRegisterInfo.h"
65 #include "llvm/CodeGen/Passes.h"
66 #include "llvm/CodeGen/TargetInstrInfo.h"
67 #include "llvm/CodeGen/TargetSubtargetInfo.h"
68 #include "llvm/IR/DIBuilder.h"
69 #include "llvm/IR/IRBuilder.h"
70 #include "llvm/IR/Mangler.h"
71 #include "llvm/InitializePasses.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"
80 #define DEBUG_TYPE "machine-outliner"
84 using namespace outliner;
86 STATISTIC(NumOutlined, "Number of candidates outlined");
87 STATISTIC(FunctionsCreated, "Number of functions created");
89 // Set to true if the user wants the outliner to run on linkonceodr linkage
90 // functions. This is false by default because the linker can dedupe linkonceodr
91 // functions. Since the outliner is confined to a single module (modulo LTO),
92 // this is off by default. It should, however, be the default behaviour in
94 static cl::opt<bool> EnableLinkOnceODROutlining(
95 "enable-linkonceodr-outlining", cl::Hidden,
96 cl::desc("Enable the machine outliner on linkonceodr functions"),
101 /// Represents an undefined index in the suffix tree.
102 const unsigned EmptyIdx = -1;
104 /// A node in a suffix tree which represents a substring or suffix.
106 /// Each node has either no children or at least two children, with the root
107 /// being a exception in the empty tree.
109 /// Children are represented as a map between unsigned integers and nodes. If
110 /// a node N has a child M on unsigned integer k, then the mapping represented
111 /// by N is a proper prefix of the mapping represented by M. Note that this,
112 /// although similar to a trie is somewhat different: each node stores a full
113 /// substring of the full mapping rather than a single character state.
115 /// Each internal node contains a pointer to the internal node representing
116 /// the same string, but with the first character chopped off. This is stored
117 /// in \p Link. Each leaf node stores the start index of its respective
118 /// suffix in \p SuffixIdx.
119 struct SuffixTreeNode {
121 /// The children of this node.
123 /// A child existing on an unsigned integer implies that from the mapping
124 /// represented by the current node, there is a way to reach another
125 /// mapping by tacking that character on the end of the current string.
126 DenseMap<unsigned, SuffixTreeNode *> Children;
128 /// The start index of this node's substring in the main string.
129 unsigned StartIdx = EmptyIdx;
131 /// The end index of this node's substring in the main string.
133 /// Every leaf node must have its \p EndIdx incremented at the end of every
134 /// step in the construction algorithm. To avoid having to update O(N)
135 /// nodes individually at the end of every step, the end index is stored
137 unsigned *EndIdx = nullptr;
139 /// For leaves, the start index of the suffix represented by this node.
141 /// For all other nodes, this is ignored.
142 unsigned SuffixIdx = EmptyIdx;
144 /// For internal nodes, a pointer to the internal node representing
145 /// the same sequence with the first character chopped off.
147 /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
148 /// Ukkonen's algorithm does to achieve linear-time construction is
149 /// keep track of which node the next insert should be at. This makes each
150 /// insert O(1), and there are a total of O(N) inserts. The suffix link
151 /// helps with inserting children of internal nodes.
153 /// Say we add a child to an internal node with associated mapping S. The
154 /// next insertion must be at the node representing S - its first character.
155 /// This is given by the way that we iteratively build the tree in Ukkonen's
156 /// algorithm. The main idea is to look at the suffixes of each prefix in the
157 /// string, starting with the longest suffix of the prefix, and ending with
158 /// the shortest. Therefore, if we keep pointers between such nodes, we can
159 /// move to the next insertion point in O(1) time. If we don't, then we'd
160 /// have to query from the root, which takes O(N) time. This would make the
161 /// construction algorithm O(N^2) rather than O(N).
162 SuffixTreeNode *Link = nullptr;
164 /// The length of the string formed by concatenating the edge labels from the
165 /// root to this node.
166 unsigned ConcatLen = 0;
168 /// Returns true if this node is a leaf.
169 bool isLeaf() const { return SuffixIdx != EmptyIdx; }
171 /// Returns true if this node is the root of its owning \p SuffixTree.
172 bool isRoot() const { return StartIdx == EmptyIdx; }
174 /// Return the number of elements in the substring associated with this node.
175 size_t size() const {
177 // Is it the root? If so, it's the empty string so return 0.
181 assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
183 // Size = the number of elements in the string.
184 // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
185 return *EndIdx - StartIdx + 1;
188 SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link)
189 : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link) {}
194 /// A data structure for fast substring queries.
196 /// Suffix trees represent the suffixes of their input strings in their leaves.
197 /// A suffix tree is a type of compressed trie structure where each node
198 /// represents an entire substring rather than a single character. Each leaf
199 /// of the tree is a suffix.
201 /// A suffix tree can be seen as a type of state machine where each state is a
202 /// substring of the full string. The tree is structured so that, for a string
203 /// of length N, there are exactly N leaves in the tree. This structure allows
204 /// us to quickly find repeated substrings of the input string.
206 /// In this implementation, a "string" is a vector of unsigned integers.
207 /// These integers may result from hashing some data type. A suffix tree can
208 /// contain 1 or many strings, which can then be queried as one large string.
210 /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
211 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
212 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
213 /// paper is available at
215 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
218 /// Each element is an integer representing an instruction in the module.
219 ArrayRef<unsigned> Str;
221 /// A repeated substring in the tree.
222 struct RepeatedSubstring {
223 /// The length of the string.
226 /// The start indices of each occurrence.
227 std::vector<unsigned> StartIndices;
231 /// Maintains each node in the tree.
232 SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
234 /// The root of the suffix tree.
236 /// The root represents the empty string. It is maintained by the
237 /// \p NodeAllocator like every other node in the tree.
238 SuffixTreeNode *Root = nullptr;
240 /// Maintains the end indices of the internal nodes in the tree.
242 /// Each internal node is guaranteed to never have its end index change
243 /// during the construction algorithm; however, leaves must be updated at
244 /// every step. Therefore, we need to store leaf end indices by reference
245 /// to avoid updating O(N) leaves at every step of construction. Thus,
246 /// every internal node must be allocated its own end index.
247 BumpPtrAllocator InternalEndIdxAllocator;
249 /// The end index of each leaf in the tree.
250 unsigned LeafEndIdx = -1;
252 /// Helper struct which keeps track of the next insertion point in
253 /// Ukkonen's algorithm.
255 /// The next node to insert at.
256 SuffixTreeNode *Node = nullptr;
258 /// The index of the first character in the substring currently being added.
259 unsigned Idx = EmptyIdx;
261 /// The length of the substring we have to add at the current step.
265 /// The point the next insertion will take place at in the
266 /// construction algorithm.
269 /// Allocate a leaf node and add it to the tree.
271 /// \param Parent The parent of this node.
272 /// \param StartIdx The start index of this node's associated string.
273 /// \param Edge The label on the edge leaving \p Parent to this node.
275 /// \returns A pointer to the allocated leaf node.
276 SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
279 assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
281 SuffixTreeNode *N = new (NodeAllocator.Allocate())
282 SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr);
283 Parent.Children[Edge] = N;
288 /// Allocate an internal node and add it to the tree.
290 /// \param Parent The parent of this node. Only null when allocating the root.
291 /// \param StartIdx The start index of this node's associated string.
292 /// \param EndIdx The end index of this node's associated string.
293 /// \param Edge The label on the edge leaving \p Parent to this node.
295 /// \returns A pointer to the allocated internal node.
296 SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
297 unsigned EndIdx, unsigned Edge) {
299 assert(StartIdx <= EndIdx && "String can't start after it ends!");
300 assert(!(!Parent && StartIdx != EmptyIdx) &&
301 "Non-root internal nodes must have parents!");
303 unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
305 new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx, E, Root);
307 Parent->Children[Edge] = N;
312 /// Set the suffix indices of the leaves to the start indices of their
313 /// respective suffixes.
314 void setSuffixIndices() {
315 // List of nodes we need to visit along with the current length of the
317 std::vector<std::pair<SuffixTreeNode *, unsigned>> ToVisit;
319 // Current node being visited.
320 SuffixTreeNode *CurrNode = Root;
322 // Sum of the lengths of the nodes down the path to the current one.
323 unsigned CurrNodeLen = 0;
324 ToVisit.push_back({CurrNode, CurrNodeLen});
325 while (!ToVisit.empty()) {
326 std::tie(CurrNode, CurrNodeLen) = ToVisit.back();
328 CurrNode->ConcatLen = CurrNodeLen;
329 for (auto &ChildPair : CurrNode->Children) {
330 assert(ChildPair.second && "Node had a null child!");
332 {ChildPair.second, CurrNodeLen + ChildPair.second->size()});
335 // No children, so we are at the end of the string.
336 if (CurrNode->Children.size() == 0 && !CurrNode->isRoot())
337 CurrNode->SuffixIdx = Str.size() - CurrNodeLen;
341 /// Construct the suffix tree for the prefix of the input ending at
344 /// Used to construct the full suffix tree iteratively. At the end of each
345 /// step, the constructed suffix tree is either a valid suffix tree, or a
346 /// suffix tree with implicit suffixes. At the end of the final step, the
347 /// suffix tree is a valid tree.
349 /// \param EndIdx The end index of the current prefix in the main string.
350 /// \param SuffixesToAdd The number of suffixes that must be added
351 /// to complete the suffix tree at the current phase.
353 /// \returns The number of suffixes that have not been added at the end of
355 unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
356 SuffixTreeNode *NeedsLink = nullptr;
358 while (SuffixesToAdd > 0) {
360 // Are we waiting to add anything other than just the last character?
361 if (Active.Len == 0) {
362 // If not, then say the active index is the end index.
366 assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
368 // The first character in the current substring we're looking at.
369 unsigned FirstChar = Str[Active.Idx];
371 // Have we inserted anything starting with FirstChar at the current node?
372 if (Active.Node->Children.count(FirstChar) == 0) {
373 // If not, then we can just insert a leaf and move too the next step.
374 insertLeaf(*Active.Node, EndIdx, FirstChar);
376 // The active node is an internal node, and we visited it, so it must
377 // need a link if it doesn't have one.
379 NeedsLink->Link = Active.Node;
383 // There's a match with FirstChar, so look for the point in the tree to
384 // insert a new node.
385 SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
387 unsigned SubstringLen = NextNode->size();
389 // Is the current suffix we're trying to insert longer than the size of
390 // the child we want to move to?
391 if (Active.Len >= SubstringLen) {
392 // If yes, then consume the characters we've seen and move to the next
394 Active.Idx += SubstringLen;
395 Active.Len -= SubstringLen;
396 Active.Node = NextNode;
400 // Otherwise, the suffix we're trying to insert must be contained in the
401 // next node we want to move to.
402 unsigned LastChar = Str[EndIdx];
404 // Is the string we're trying to insert a substring of the next node?
405 if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
406 // If yes, then we're done for this step. Remember our insertion point
407 // and move to the next end index. At this point, we have an implicit
409 if (NeedsLink && !Active.Node->isRoot()) {
410 NeedsLink->Link = Active.Node;
418 // The string we're trying to insert isn't a substring of the next node,
419 // but matches up to a point. Split the node.
421 // For example, say we ended our search at a node n and we're trying to
422 // insert ABD. Then we'll create a new node s for AB, reduce n to just
423 // representing C, and insert a new leaf node l to represent d. This
424 // allows us to ensure that if n was a leaf, it remains a leaf.
426 // | ABC ---split---> | AB
431 // The node s from the diagram
432 SuffixTreeNode *SplitNode =
433 insertInternalNode(Active.Node, NextNode->StartIdx,
434 NextNode->StartIdx + Active.Len - 1, FirstChar);
436 // Insert the new node representing the new substring into the tree as
437 // a child of the split node. This is the node l from the diagram.
438 insertLeaf(*SplitNode, EndIdx, LastChar);
440 // Make the old node a child of the split node and update its start
441 // index. This is the node n from the diagram.
442 NextNode->StartIdx += Active.Len;
443 SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
445 // SplitNode is an internal node, update the suffix link.
447 NeedsLink->Link = SplitNode;
449 NeedsLink = SplitNode;
452 // We've added something new to the tree, so there's one less suffix to
456 if (Active.Node->isRoot()) {
457 if (Active.Len > 0) {
459 Active.Idx = EndIdx - SuffixesToAdd + 1;
462 // Start the next phase at the next smallest suffix.
463 Active.Node = Active.Node->Link;
467 return SuffixesToAdd;
471 /// Construct a suffix tree from a sequence of unsigned integers.
473 /// \param Str The string to construct the suffix tree for.
474 SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
475 Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
478 // Keep track of the number of suffixes we have to add of the current
480 unsigned SuffixesToAdd = 0;
482 // Construct the suffix tree iteratively on each prefix of the string.
483 // PfxEndIdx is the end index of the current prefix.
484 // End is one past the last element in the string.
485 for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
488 LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
489 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
492 // Set the suffix indices of each leaf.
493 assert(Root && "Root node can't be nullptr!");
497 /// Iterator for finding all repeated substrings in the suffix tree.
498 struct RepeatedSubstringIterator {
500 /// The current node we're visiting.
501 SuffixTreeNode *N = nullptr;
503 /// The repeated substring associated with this node.
504 RepeatedSubstring RS;
506 /// The nodes left to visit.
507 std::vector<SuffixTreeNode *> ToVisit;
509 /// The minimum length of a repeated substring to find.
510 /// Since we're outlining, we want at least two instructions in the range.
511 /// FIXME: This may not be true for targets like X86 which support many
512 /// instruction lengths.
513 const unsigned MinLength = 2;
515 /// Move the iterator to the next repeated substring.
517 // Clear the current state. If we're at the end of the range, then this
518 // is the state we want to be in.
519 RS = RepeatedSubstring();
522 // Each leaf node represents a repeat of a string.
523 std::vector<SuffixTreeNode *> LeafChildren;
525 // Continue visiting nodes until we find one which repeats more than once.
526 while (!ToVisit.empty()) {
527 SuffixTreeNode *Curr = ToVisit.back();
529 LeafChildren.clear();
531 // Keep track of the length of the string associated with the node. If
532 // it's too short, we'll quit.
533 unsigned Length = Curr->ConcatLen;
535 // Iterate over each child, saving internal nodes for visiting, and
536 // leaf nodes in LeafChildren. Internal nodes represent individual
537 // strings, which may repeat.
538 for (auto &ChildPair : Curr->Children) {
539 // Save all of this node's children for processing.
540 if (!ChildPair.second->isLeaf())
541 ToVisit.push_back(ChildPair.second);
543 // It's not an internal node, so it must be a leaf. If we have a
544 // long enough string, then save the leaf children.
545 else if (Length >= MinLength)
546 LeafChildren.push_back(ChildPair.second);
549 // The root never represents a repeated substring. If we're looking at
550 // that, then skip it.
554 // Do we have any repeated substrings?
555 if (LeafChildren.size() >= 2) {
556 // Yes. Update the state to reflect this, and then bail out.
559 for (SuffixTreeNode *Leaf : LeafChildren)
560 RS.StartIndices.push_back(Leaf->SuffixIdx);
565 // At this point, either NewRS is an empty RepeatedSubstring, or it was
566 // set in the above loop. Similarly, N is either nullptr, or the node
567 // associated with NewRS.
571 /// Return the current repeated substring.
572 RepeatedSubstring &operator*() { return RS; }
574 RepeatedSubstringIterator &operator++() {
579 RepeatedSubstringIterator operator++(int I) {
580 RepeatedSubstringIterator It(*this);
585 bool operator==(const RepeatedSubstringIterator &Other) {
588 bool operator!=(const RepeatedSubstringIterator &Other) {
589 return !(*this == Other);
592 RepeatedSubstringIterator(SuffixTreeNode *N) : N(N) {
593 // Do we have a non-null node?
595 // Yes. At the first step, we need to visit all of N's children.
596 // Note: This means that we visit N last.
597 ToVisit.push_back(N);
603 typedef RepeatedSubstringIterator iterator;
604 iterator begin() { return iterator(Root); }
605 iterator end() { return iterator(nullptr); }
608 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
609 struct InstructionMapper {
611 /// The next available integer to assign to a \p MachineInstr that
612 /// cannot be outlined.
614 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
615 unsigned IllegalInstrNumber = -3;
617 /// The next available integer to assign to a \p MachineInstr that can
619 unsigned LegalInstrNumber = 0;
621 /// Correspondence from \p MachineInstrs to unsigned integers.
622 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
623 InstructionIntegerMap;
625 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
626 DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
628 /// The vector of unsigned integers that the module is mapped to.
629 std::vector<unsigned> UnsignedVec;
631 /// Stores the location of the instruction associated with the integer
632 /// at index i in \p UnsignedVec for each index i.
633 std::vector<MachineBasicBlock::iterator> InstrList;
635 // Set if we added an illegal number in the previous step.
636 // Since each illegal number is unique, we only need one of them between
637 // each range of legal numbers. This lets us make sure we don't add more
638 // than one illegal number per range.
639 bool AddedIllegalLastTime = false;
641 /// Maps \p *It to a legal integer.
643 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
644 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
646 /// \returns The integer that \p *It was mapped to.
647 unsigned mapToLegalUnsigned(
648 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
649 bool &HaveLegalRange, unsigned &NumLegalInBlock,
650 std::vector<unsigned> &UnsignedVecForMBB,
651 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
652 // We added something legal, so we should unset the AddedLegalLastTime
654 AddedIllegalLastTime = false;
656 // If we have at least two adjacent legal instructions (which may have
657 // invisible instructions in between), remember that.
658 if (CanOutlineWithPrevInstr)
659 HaveLegalRange = true;
660 CanOutlineWithPrevInstr = true;
662 // Keep track of the number of legal instructions we insert.
665 // Get the integer for this instruction or give it the current
667 InstrListForMBB.push_back(It);
668 MachineInstr &MI = *It;
670 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
672 std::tie(ResultIt, WasInserted) =
673 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
674 unsigned MINumber = ResultIt->second;
676 // There was an insertion.
680 UnsignedVecForMBB.push_back(MINumber);
682 // Make sure we don't overflow or use any integers reserved by the DenseMap.
683 if (LegalInstrNumber >= IllegalInstrNumber)
684 report_fatal_error("Instruction mapping overflow!");
686 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
687 "Tried to assign DenseMap tombstone or empty key to instruction.");
688 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
689 "Tried to assign DenseMap tombstone or empty key to instruction.");
694 /// Maps \p *It to an illegal integer.
696 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
697 /// IllegalInstrNumber.
699 /// \returns The integer that \p *It was mapped to.
700 unsigned mapToIllegalUnsigned(
701 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
702 std::vector<unsigned> &UnsignedVecForMBB,
703 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
704 // Can't outline an illegal instruction. Set the flag.
705 CanOutlineWithPrevInstr = false;
707 // Only add one illegal number per range of legal numbers.
708 if (AddedIllegalLastTime)
709 return IllegalInstrNumber;
711 // Remember that we added an illegal number last time.
712 AddedIllegalLastTime = true;
713 unsigned MINumber = IllegalInstrNumber;
715 InstrListForMBB.push_back(It);
716 UnsignedVecForMBB.push_back(IllegalInstrNumber);
717 IllegalInstrNumber--;
719 assert(LegalInstrNumber < IllegalInstrNumber &&
720 "Instruction mapping overflow!");
722 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
723 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
725 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
726 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
731 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
732 /// and appends it to \p UnsignedVec and \p InstrList.
734 /// Two instructions are assigned the same integer if they are identical.
735 /// If an instruction is deemed unsafe to outline, then it will be assigned an
736 /// unique integer. The resulting mapping is placed into a suffix tree and
737 /// queried for candidates.
739 /// \param MBB The \p MachineBasicBlock to be translated into integers.
740 /// \param TII \p TargetInstrInfo for the function.
741 void convertToUnsignedVec(MachineBasicBlock &MBB,
742 const TargetInstrInfo &TII) {
745 // Don't even map in this case.
746 if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
749 // Store info for the MBB for later outlining.
750 MBBFlagsMap[&MBB] = Flags;
752 MachineBasicBlock::iterator It = MBB.begin();
754 // The number of instructions in this block that will be considered for
756 unsigned NumLegalInBlock = 0;
758 // True if we have at least two legal instructions which aren't separated
759 // by an illegal instruction.
760 bool HaveLegalRange = false;
762 // True if we can perform outlining given the last mapped (non-invisible)
763 // instruction. This lets us know if we have a legal range.
764 bool CanOutlineWithPrevInstr = false;
766 // FIXME: Should this all just be handled in the target, rather than using
767 // repeated calls to getOutliningType?
768 std::vector<unsigned> UnsignedVecForMBB;
769 std::vector<MachineBasicBlock::iterator> InstrListForMBB;
771 for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; ++It) {
772 // Keep track of where this instruction is in the module.
773 switch (TII.getOutliningType(It, Flags)) {
774 case InstrType::Illegal:
775 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
779 case InstrType::Legal:
780 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
781 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
784 case InstrType::LegalTerminator:
785 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
786 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
787 // The instruction also acts as a terminator, so we have to record that
789 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
793 case InstrType::Invisible:
794 // Normally this is set by mapTo(Blah)Unsigned, but we just want to
795 // skip this instruction. So, unset the flag here.
796 AddedIllegalLastTime = false;
801 // Are there enough legal instructions in the block for outlining to be
803 if (HaveLegalRange) {
804 // After we're done every insertion, uniquely terminate this part of the
805 // "string". This makes sure we won't match across basic block or function
806 // boundaries since the "end" is encoded uniquely and thus appears in no
807 // repeated substring.
808 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
810 InstrList.insert(InstrList.end(), InstrListForMBB.begin(),
811 InstrListForMBB.end());
812 UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForMBB.begin(),
813 UnsignedVecForMBB.end());
817 InstructionMapper() {
818 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
820 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
821 "DenseMapInfo<unsigned>'s empty key isn't -1!");
822 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
823 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
827 /// An interprocedural pass which finds repeated sequences of
828 /// instructions and replaces them with calls to functions.
830 /// Each instruction is mapped to an unsigned integer and placed in a string.
831 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
832 /// is then repeatedly queried for repeated sequences of instructions. Each
833 /// non-overlapping repeated sequence is then placed in its own
834 /// \p MachineFunction and each instance is then replaced with a call to that
836 struct MachineOutliner : public ModulePass {
840 /// Set to true if the outliner should consider functions with
841 /// linkonceodr linkage.
842 bool OutlineFromLinkOnceODRs = false;
844 /// Set to true if the outliner should run on all functions in the module
845 /// considered safe for outlining.
846 /// Set to true by default for compatibility with llc's -run-pass option.
847 /// Set when the pass is constructed in TargetPassConfig.
848 bool RunOnAllFunctions = true;
850 StringRef getPassName() const override { return "Machine Outliner"; }
852 void getAnalysisUsage(AnalysisUsage &AU) const override {
853 AU.addRequired<MachineModuleInfoWrapperPass>();
854 AU.addPreserved<MachineModuleInfoWrapperPass>();
855 AU.setPreservesAll();
856 ModulePass::getAnalysisUsage(AU);
859 MachineOutliner() : ModulePass(ID) {
860 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
863 /// Remark output explaining that not outlining a set of candidates would be
864 /// better than outlining that set.
865 void emitNotOutliningCheaperRemark(
866 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
867 OutlinedFunction &OF);
869 /// Remark output explaining that a function was outlined.
870 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
872 /// Find all repeated substrings that satisfy the outlining cost model by
873 /// constructing a suffix tree.
875 /// If a substring appears at least twice, then it must be represented by
876 /// an internal node which appears in at least two suffixes. Each suffix
877 /// is represented by a leaf node. To do this, we visit each internal node
878 /// in the tree, using the leaf children of each internal node. If an
879 /// internal node represents a beneficial substring, then we use each of
880 /// its leaf children to find the locations of its substring.
882 /// \param Mapper Contains outlining mapping information.
883 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
884 /// each type of candidate.
885 void findCandidates(InstructionMapper &Mapper,
886 std::vector<OutlinedFunction> &FunctionList);
888 /// Replace the sequences of instructions represented by \p OutlinedFunctions
889 /// with calls to functions.
891 /// \param M The module we are outlining from.
892 /// \param FunctionList A list of functions to be inserted into the module.
893 /// \param Mapper Contains the instruction mappings for the module.
894 bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
895 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
897 /// Creates a function for \p OF and inserts it into the module.
898 MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
899 InstructionMapper &Mapper,
902 /// Calls 'doOutline()'.
903 bool runOnModule(Module &M) override;
905 /// Construct a suffix tree on the instructions in \p M and outline repeated
906 /// strings from that tree.
907 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
909 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
910 /// function for remark emission.
911 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
912 for (const Candidate &C : OF.Candidates)
913 if (MachineFunction *MF = C.getMF())
914 if (DISubprogram *SP = MF->getFunction().getSubprogram())
919 /// Populate and \p InstructionMapper with instruction-to-integer mappings.
920 /// These are used to construct a suffix tree.
921 void populateMapper(InstructionMapper &Mapper, Module &M,
922 MachineModuleInfo &MMI);
924 /// Initialize information necessary to output a size remark.
925 /// FIXME: This should be handled by the pass manager, not the outliner.
926 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
928 void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI,
929 StringMap<unsigned> &FunctionToInstrCount);
932 // FIXME: This should be handled by the pass manager, not the outliner.
934 emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
935 const StringMap<unsigned> &FunctionToInstrCount);
937 } // Anonymous namespace.
939 char MachineOutliner::ID = 0;
942 ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
943 MachineOutliner *OL = new MachineOutliner();
944 OL->RunOnAllFunctions = RunOnAllFunctions;
950 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
953 void MachineOutliner::emitNotOutliningCheaperRemark(
954 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
955 OutlinedFunction &OF) {
956 // FIXME: Right now, we arbitrarily choose some Candidate from the
957 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
958 // We should probably sort these by function name or something to make sure
959 // the remarks are stable.
960 Candidate &C = CandidatesForRepeatedSeq.front();
961 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
963 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
964 C.front()->getDebugLoc(), C.getMBB());
965 R << "Did not outline " << NV("Length", StringLen) << " instructions"
966 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
968 << " Bytes from outlining all occurrences ("
969 << NV("OutliningCost", OF.getOutliningCost()) << ")"
970 << " >= Unoutlined instruction bytes ("
971 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
972 << " (Also found at: ";
974 // Tell the user the other places the candidate was found.
975 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
976 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
977 CandidatesForRepeatedSeq[i].front()->getDebugLoc());
987 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
988 MachineBasicBlock *MBB = &*OF.MF->begin();
989 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
990 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
991 MBB->findDebugLoc(MBB->begin()), MBB);
992 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
993 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
994 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
998 // Tell the user the other places the candidate was found.
999 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
1001 R << NV((Twine("StartLoc") + Twine(i)).str(),
1002 OF.Candidates[i].front()->getDebugLoc());
1012 void MachineOutliner::findCandidates(
1013 InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
1014 FunctionList.clear();
1015 SuffixTree ST(Mapper.UnsignedVec);
1017 // First, find all of the repeated substrings in the tree of minimum length
1019 std::vector<Candidate> CandidatesForRepeatedSeq;
1020 for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
1021 CandidatesForRepeatedSeq.clear();
1022 SuffixTree::RepeatedSubstring RS = *It;
1023 unsigned StringLen = RS.Length;
1024 for (const unsigned &StartIdx : RS.StartIndices) {
1025 unsigned EndIdx = StartIdx + StringLen - 1;
1026 // Trick: Discard some candidates that would be incompatible with the
1027 // ones we've already found for this sequence. This will save us some
1028 // work in candidate selection.
1030 // If two candidates overlap, then we can't outline them both. This
1031 // happens when we have candidates that look like, say
1033 // AA (where each "A" is an instruction).
1035 // We might have some portion of the module that looks like this:
1038 // In this case, there are 5 different copies of "AA" in this range, but
1039 // at most 3 can be outlined. If only outlining 3 of these is going to
1040 // be unbeneficial, then we ought to not bother.
1042 // Note that two things DON'T overlap when they look like this:
1043 // start1...end1 .... start2...end2
1044 // That is, one must either
1045 // * End before the other starts
1046 // * Start after the other ends
1048 CandidatesForRepeatedSeq.begin(), CandidatesForRepeatedSeq.end(),
1049 [&StartIdx, &EndIdx](const Candidate &C) {
1050 return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx());
1052 // It doesn't overlap with anything, so we can outline it.
1053 // Each sequence is over [StartIt, EndIt].
1054 // Save the candidate and its location.
1056 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
1057 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
1058 MachineBasicBlock *MBB = StartIt->getParent();
1060 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
1061 EndIt, MBB, FunctionList.size(),
1062 Mapper.MBBFlagsMap[MBB]);
1066 // We've found something we might want to outline.
1067 // Create an OutlinedFunction to store it and check if it'd be beneficial
1069 if (CandidatesForRepeatedSeq.size() < 2)
1072 // Arbitrarily choose a TII from the first candidate.
1073 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
1074 const TargetInstrInfo *TII =
1075 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
1077 OutlinedFunction OF =
1078 TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
1080 // If we deleted too many candidates, then there's nothing worth outlining.
1081 // FIXME: This should take target-specified instruction sizes into account.
1082 if (OF.Candidates.size() < 2)
1085 // Is it better to outline this candidate than not?
1086 if (OF.getBenefit() < 1) {
1087 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
1091 FunctionList.push_back(OF);
1095 MachineFunction *MachineOutliner::createOutlinedFunction(
1096 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
1098 // Create the function name. This should be unique.
1099 // FIXME: We should have a better naming scheme. This should be stable,
1100 // regardless of changes to the outliner's cost model/traversal order.
1101 std::string FunctionName = ("OUTLINED_FUNCTION_" + Twine(Name)).str();
1103 // Create the function using an IR-level function.
1104 LLVMContext &C = M.getContext();
1105 Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),
1106 Function::ExternalLinkage, FunctionName, M);
1108 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1109 // which gives us better results when we outline from linkonceodr functions.
1110 F->setLinkage(GlobalValue::InternalLinkage);
1111 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1113 // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's
1116 // Set optsize/minsize, so we don't insert padding between outlined
1118 F->addFnAttr(Attribute::OptimizeForSize);
1119 F->addFnAttr(Attribute::MinSize);
1121 // Include target features from an arbitrary candidate for the outlined
1122 // function. This makes sure the outlined function knows what kinds of
1123 // instructions are going into it. This is fine, since all parent functions
1124 // must necessarily support the instructions that are in the outlined region.
1125 Candidate &FirstCand = OF.Candidates.front();
1126 const Function &ParentFn = FirstCand.getMF()->getFunction();
1127 if (ParentFn.hasFnAttribute("target-features"))
1128 F->addFnAttr(ParentFn.getFnAttribute("target-features"));
1130 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1131 IRBuilder<> Builder(EntryBB);
1132 Builder.CreateRetVoid();
1134 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1135 MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
1136 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1137 const TargetSubtargetInfo &STI = MF.getSubtarget();
1138 const TargetInstrInfo &TII = *STI.getInstrInfo();
1140 // Insert the new function into the module.
1141 MF.insert(MF.begin(), &MBB);
1143 for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
1145 MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
1146 NewMI->dropMemRefs(MF);
1148 // Don't keep debug information for outlined instructions.
1149 NewMI->setDebugLoc(DebugLoc());
1150 MBB.insert(MBB.end(), NewMI);
1153 TII.buildOutlinedFrame(MBB, MF, OF);
1155 // Outlined functions shouldn't preserve liveness.
1156 MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness);
1157 MF.getRegInfo().freezeReservedRegs(MF);
1159 // If there's a DISubprogram associated with this outlined function, then
1160 // emit debug info for the outlined function.
1161 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
1162 // We have a DISubprogram. Get its DICompileUnit.
1163 DICompileUnit *CU = SP->getUnit();
1164 DIBuilder DB(M, true, CU);
1165 DIFile *Unit = SP->getFile();
1167 // Get the mangled name of the function for the linkage name.
1169 llvm::raw_string_ostream MangledNameStream(Dummy);
1170 Mg.getNameWithPrefix(MangledNameStream, F, false);
1172 DISubprogram *OutlinedSP = DB.createFunction(
1173 Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
1175 0 /* Line 0 is reserved for compiler-generated code. */,
1176 DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
1177 0, /* Line 0 is reserved for compiler-generated code. */
1178 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
1179 /* Outlined code is optimized code by definition. */
1180 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
1182 // Don't add any new variables to the subprogram.
1183 DB.finalizeSubprogram(OutlinedSP);
1185 // Attach subprogram to the function.
1186 F->setSubprogram(OutlinedSP);
1187 // We're done with the DIBuilder.
1194 bool MachineOutliner::outline(Module &M,
1195 std::vector<OutlinedFunction> &FunctionList,
1196 InstructionMapper &Mapper,
1197 unsigned &OutlinedFunctionNum) {
1199 bool OutlinedSomething = false;
1201 // Sort by benefit. The most beneficial functions should be outlined first.
1202 llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
1203 const OutlinedFunction &RHS) {
1204 return LHS.getBenefit() > RHS.getBenefit();
1207 // Walk over each function, outlining them as we go along. Functions are
1208 // outlined greedily, based off the sort above.
1209 for (OutlinedFunction &OF : FunctionList) {
1210 // If we outlined something that overlapped with a candidate in a previous
1211 // step, then we can't outline from it.
1212 erase_if(OF.Candidates, [&Mapper](Candidate &C) {
1214 Mapper.UnsignedVec.begin() + C.getStartIdx(),
1215 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
1216 [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
1219 // If we made it unbeneficial to outline this function, skip it.
1220 if (OF.getBenefit() < 1)
1223 // It's beneficial. Create the function and outline its sequence's
1225 OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
1226 emitOutlinedFunctionRemark(OF);
1228 OutlinedFunctionNum++; // Created a function, move to the next name.
1229 MachineFunction *MF = OF.MF;
1230 const TargetSubtargetInfo &STI = MF->getSubtarget();
1231 const TargetInstrInfo &TII = *STI.getInstrInfo();
1233 // Replace occurrences of the sequence with calls to the new function.
1234 for (Candidate &C : OF.Candidates) {
1235 MachineBasicBlock &MBB = *C.getMBB();
1236 MachineBasicBlock::iterator StartIt = C.front();
1237 MachineBasicBlock::iterator EndIt = C.back();
1240 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
1242 // If the caller tracks liveness, then we need to make sure that
1243 // anything we outline doesn't break liveness assumptions. The outlined
1244 // functions themselves currently don't track liveness, but we should
1245 // make sure that the ranges we yank things out of aren't wrong.
1246 if (MBB.getParent()->getProperties().hasProperty(
1247 MachineFunctionProperties::Property::TracksLiveness)) {
1248 // Helper lambda for adding implicit def operands to the call
1249 // instruction. It also updates call site information for moved
1251 auto CopyDefsAndUpdateCalls = [&CallInst](MachineInstr &MI) {
1252 for (MachineOperand &MOP : MI.operands()) {
1253 // Skip over anything that isn't a register.
1257 // If it's a def, add it to the call instruction.
1259 CallInst->addOperand(MachineOperand::CreateReg(
1260 MOP.getReg(), true, /* isDef = true */
1261 true /* isImp = true */));
1264 MI.getMF()->eraseCallSiteInfo(&MI);
1266 // Copy over the defs in the outlined range.
1267 // First inst in outlined range <-- Anything that's defined in this
1268 // ... .. range has to be added as an
1269 // implicit Last inst in outlined range <-- def to the call
1270 // instruction. Also remove call site information for outlined block
1272 std::for_each(CallInst, std::next(EndIt), CopyDefsAndUpdateCalls);
1275 // Erase from the point after where the call was inserted up to, and
1276 // including, the final instruction in the sequence.
1277 // Erase needs one past the end, so we need std::next there too.
1278 MBB.erase(std::next(StartIt), std::next(EndIt));
1280 // Keep track of what we removed by marking them all as -1.
1281 std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
1282 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
1283 [](unsigned &I) { I = static_cast<unsigned>(-1); });
1284 OutlinedSomething = true;
1291 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1293 return OutlinedSomething;
1296 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
1297 MachineModuleInfo &MMI) {
1298 // Build instruction mappings for each function in the module. Start by
1299 // iterating over each Function in M.
1300 for (Function &F : M) {
1302 // If there's nothing in F, then there's no reason to try and outline from
1307 // There's something in F. Check if it has a MachineFunction associated with
1309 MachineFunction *MF = MMI.getMachineFunction(F);
1311 // If it doesn't, then there's nothing to outline from. Move to the next
1316 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1318 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
1321 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1322 // If it isn't, then move on to the next Function in the module.
1323 if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
1326 // We have a function suitable for outlining. Iterate over every
1327 // MachineBasicBlock in MF and try to map its instructions to a list of
1328 // unsigned integers.
1329 for (MachineBasicBlock &MBB : *MF) {
1330 // If there isn't anything in MBB, then there's no point in outlining from
1332 // If there are fewer than 2 instructions in the MBB, then it can't ever
1333 // contain something worth outlining.
1334 // FIXME: This should be based off of the maximum size in B of an outlined
1335 // call versus the size in B of the MBB.
1336 if (MBB.empty() || MBB.size() < 2)
1339 // Check if MBB could be the target of an indirect branch. If it is, then
1340 // we don't want to outline from it.
1341 if (MBB.hasAddressTaken())
1344 // MBB is suitable for outlining. Map it to a list of unsigneds.
1345 Mapper.convertToUnsignedVec(MBB, *TII);
1350 void MachineOutliner::initSizeRemarkInfo(
1351 const Module &M, const MachineModuleInfo &MMI,
1352 StringMap<unsigned> &FunctionToInstrCount) {
1353 // Collect instruction counts for every function. We'll use this to emit
1354 // per-function size remarks later.
1355 for (const Function &F : M) {
1356 MachineFunction *MF = MMI.getMachineFunction(F);
1358 // We only care about MI counts here. If there's no MachineFunction at this
1359 // point, then there won't be after the outliner runs, so let's move on.
1362 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
1366 void MachineOutliner::emitInstrCountChangedRemark(
1367 const Module &M, const MachineModuleInfo &MMI,
1368 const StringMap<unsigned> &FunctionToInstrCount) {
1369 // Iterate over each function in the module and emit remarks.
1370 // Note that we won't miss anything by doing this, because the outliner never
1371 // deletes functions.
1372 for (const Function &F : M) {
1373 MachineFunction *MF = MMI.getMachineFunction(F);
1375 // The outliner never deletes functions. If we don't have a MF here, then we
1376 // didn't have one prior to outlining either.
1380 std::string Fname = F.getName();
1381 unsigned FnCountAfter = MF->getInstructionCount();
1382 unsigned FnCountBefore = 0;
1384 // Check if the function was recorded before.
1385 auto It = FunctionToInstrCount.find(Fname);
1387 // Did we have a previously-recorded size? If yes, then set FnCountBefore
1389 if (It != FunctionToInstrCount.end())
1390 FnCountBefore = It->second;
1392 // Compute the delta and emit a remark if there was a change.
1393 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
1394 static_cast<int64_t>(FnCountBefore);
1398 MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
1400 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
1401 DiagnosticLocation(), &MF->front());
1402 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
1404 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
1405 << ": MI instruction count changed from "
1406 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
1409 << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
1412 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1418 bool MachineOutliner::runOnModule(Module &M) {
1419 // Check if there's anything in the module. If it's empty, then there's
1420 // nothing to outline.
1424 // Number to append to the current outlined function.
1425 unsigned OutlinedFunctionNum = 0;
1427 if (!doOutline(M, OutlinedFunctionNum))
1432 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1433 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1435 // If the user passed -enable-machine-outliner=always or
1436 // -enable-machine-outliner, the pass will run on all functions in the module.
1437 // Otherwise, if the target supports default outlining, it will run on all
1438 // functions deemed by the target to be worth outlining from by default. Tell
1439 // the user how the outliner is running.
1441 dbgs() << "Machine Outliner: Running on ";
1442 if (RunOnAllFunctions)
1443 dbgs() << "all functions";
1445 dbgs() << "target-default functions";
1449 // If the user specifies that they want to outline from linkonceodrs, set
1451 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1452 InstructionMapper Mapper;
1454 // Prepare instruction mappings for the suffix tree.
1455 populateMapper(Mapper, M, MMI);
1456 std::vector<OutlinedFunction> FunctionList;
1458 // Find all of the outlining candidates.
1459 findCandidates(Mapper, FunctionList);
1461 // If we've requested size remarks, then collect the MI counts of every
1462 // function before outlining, and the MI counts after outlining.
1463 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1464 // the pass manager's responsibility.
1465 // This could pretty easily be placed in outline instead, but because we
1466 // really ultimately *don't* want this here, it's done like this for now
1469 // Check if we want size remarks.
1470 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1471 StringMap<unsigned> FunctionToInstrCount;
1472 if (ShouldEmitSizeRemarks)
1473 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1475 // Outline each of the candidates and return true if something was outlined.
1476 bool OutlinedSomething =
1477 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1479 // If we outlined something, we definitely changed the MI count of the
1480 // module. If we've asked for size remarks, then output them.
1481 // FIXME: This should be in the pass manager.
1482 if (ShouldEmitSizeRemarks && OutlinedSomething)
1483 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1485 return OutlinedSomething;