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/Support/Allocator.h"
72 #include "llvm/Support/CommandLine.h"
73 #include "llvm/Support/Debug.h"
74 #include "llvm/Support/raw_ostream.h"
79 #define DEBUG_TYPE "machine-outliner"
83 using namespace outliner
;
85 STATISTIC(NumOutlined
, "Number of candidates outlined");
86 STATISTIC(FunctionsCreated
, "Number of functions created");
88 // Set to true if the user wants the outliner to run on linkonceodr linkage
89 // functions. This is false by default because the linker can dedupe linkonceodr
90 // functions. Since the outliner is confined to a single module (modulo LTO),
91 // this is off by default. It should, however, be the default behaviour in
93 static cl::opt
<bool> EnableLinkOnceODROutlining(
94 "enable-linkonceodr-outlining",
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
;
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
);
304 SuffixTreeNode
*N
= new (NodeAllocator
.Allocate())
305 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.
315 /// \param[in] CurrNode The node currently being visited.
316 /// \param CurrNodeLen The concatenation of all node sizes from the root to
317 /// this node. Used to produce suffix indices.
318 void setSuffixIndices(SuffixTreeNode
&CurrNode
, unsigned CurrNodeLen
) {
320 bool IsLeaf
= CurrNode
.Children
.size() == 0 && !CurrNode
.isRoot();
322 // Store the concatenation of lengths down from the root.
323 CurrNode
.ConcatLen
= CurrNodeLen
;
324 // Traverse the tree depth-first.
325 for (auto &ChildPair
: CurrNode
.Children
) {
326 assert(ChildPair
.second
&& "Node had a null child!");
327 setSuffixIndices(*ChildPair
.second
,
328 CurrNodeLen
+ ChildPair
.second
->size());
331 // Is this node a leaf? If it is, give it a suffix index.
333 CurrNode
.SuffixIdx
= Str
.size() - CurrNodeLen
;
336 /// Construct the suffix tree for the prefix of the input ending at
339 /// Used to construct the full suffix tree iteratively. At the end of each
340 /// step, the constructed suffix tree is either a valid suffix tree, or a
341 /// suffix tree with implicit suffixes. At the end of the final step, the
342 /// suffix tree is a valid tree.
344 /// \param EndIdx The end index of the current prefix in the main string.
345 /// \param SuffixesToAdd The number of suffixes that must be added
346 /// to complete the suffix tree at the current phase.
348 /// \returns The number of suffixes that have not been added at the end of
350 unsigned extend(unsigned EndIdx
, unsigned SuffixesToAdd
) {
351 SuffixTreeNode
*NeedsLink
= nullptr;
353 while (SuffixesToAdd
> 0) {
355 // Are we waiting to add anything other than just the last character?
356 if (Active
.Len
== 0) {
357 // If not, then say the active index is the end index.
361 assert(Active
.Idx
<= EndIdx
&& "Start index can't be after end index!");
363 // The first character in the current substring we're looking at.
364 unsigned FirstChar
= Str
[Active
.Idx
];
366 // Have we inserted anything starting with FirstChar at the current node?
367 if (Active
.Node
->Children
.count(FirstChar
) == 0) {
368 // If not, then we can just insert a leaf and move too the next step.
369 insertLeaf(*Active
.Node
, EndIdx
, FirstChar
);
371 // The active node is an internal node, and we visited it, so it must
372 // need a link if it doesn't have one.
374 NeedsLink
->Link
= Active
.Node
;
378 // There's a match with FirstChar, so look for the point in the tree to
379 // insert a new node.
380 SuffixTreeNode
*NextNode
= Active
.Node
->Children
[FirstChar
];
382 unsigned SubstringLen
= NextNode
->size();
384 // Is the current suffix we're trying to insert longer than the size of
385 // the child we want to move to?
386 if (Active
.Len
>= SubstringLen
) {
387 // If yes, then consume the characters we've seen and move to the next
389 Active
.Idx
+= SubstringLen
;
390 Active
.Len
-= SubstringLen
;
391 Active
.Node
= NextNode
;
395 // Otherwise, the suffix we're trying to insert must be contained in the
396 // next node we want to move to.
397 unsigned LastChar
= Str
[EndIdx
];
399 // Is the string we're trying to insert a substring of the next node?
400 if (Str
[NextNode
->StartIdx
+ Active
.Len
] == LastChar
) {
401 // If yes, then we're done for this step. Remember our insertion point
402 // and move to the next end index. At this point, we have an implicit
404 if (NeedsLink
&& !Active
.Node
->isRoot()) {
405 NeedsLink
->Link
= Active
.Node
;
413 // The string we're trying to insert isn't a substring of the next node,
414 // but matches up to a point. Split the node.
416 // For example, say we ended our search at a node n and we're trying to
417 // insert ABD. Then we'll create a new node s for AB, reduce n to just
418 // representing C, and insert a new leaf node l to represent d. This
419 // allows us to ensure that if n was a leaf, it remains a leaf.
421 // | ABC ---split---> | AB
426 // The node s from the diagram
427 SuffixTreeNode
*SplitNode
=
428 insertInternalNode(Active
.Node
, NextNode
->StartIdx
,
429 NextNode
->StartIdx
+ Active
.Len
- 1, FirstChar
);
431 // Insert the new node representing the new substring into the tree as
432 // a child of the split node. This is the node l from the diagram.
433 insertLeaf(*SplitNode
, EndIdx
, LastChar
);
435 // Make the old node a child of the split node and update its start
436 // index. This is the node n from the diagram.
437 NextNode
->StartIdx
+= Active
.Len
;
438 SplitNode
->Children
[Str
[NextNode
->StartIdx
]] = NextNode
;
440 // SplitNode is an internal node, update the suffix link.
442 NeedsLink
->Link
= SplitNode
;
444 NeedsLink
= SplitNode
;
447 // We've added something new to the tree, so there's one less suffix to
451 if (Active
.Node
->isRoot()) {
452 if (Active
.Len
> 0) {
454 Active
.Idx
= EndIdx
- SuffixesToAdd
+ 1;
457 // Start the next phase at the next smallest suffix.
458 Active
.Node
= Active
.Node
->Link
;
462 return SuffixesToAdd
;
466 /// Construct a suffix tree from a sequence of unsigned integers.
468 /// \param Str The string to construct the suffix tree for.
469 SuffixTree(const std::vector
<unsigned> &Str
) : Str(Str
) {
470 Root
= insertInternalNode(nullptr, EmptyIdx
, EmptyIdx
, 0);
473 // Keep track of the number of suffixes we have to add of the current
475 unsigned SuffixesToAdd
= 0;
478 // Construct the suffix tree iteratively on each prefix of the string.
479 // PfxEndIdx is the end index of the current prefix.
480 // End is one past the last element in the string.
481 for (unsigned PfxEndIdx
= 0, End
= Str
.size(); PfxEndIdx
< End
;
484 LeafEndIdx
= PfxEndIdx
; // Extend each of the leaves.
485 SuffixesToAdd
= extend(PfxEndIdx
, SuffixesToAdd
);
488 // Set the suffix indices of each leaf.
489 assert(Root
&& "Root node can't be nullptr!");
490 setSuffixIndices(*Root
, 0);
494 /// Iterator for finding all repeated substrings in the suffix tree.
495 struct RepeatedSubstringIterator
{
497 /// The current node we're visiting.
498 SuffixTreeNode
*N
= nullptr;
500 /// The repeated substring associated with this node.
501 RepeatedSubstring RS
;
503 /// The nodes left to visit.
504 std::vector
<SuffixTreeNode
*> ToVisit
;
506 /// The minimum length of a repeated substring to find.
507 /// Since we're outlining, we want at least two instructions in the range.
508 /// FIXME: This may not be true for targets like X86 which support many
509 /// instruction lengths.
510 const unsigned MinLength
= 2;
512 /// Move the iterator to the next repeated substring.
514 // Clear the current state. If we're at the end of the range, then this
515 // is the state we want to be in.
516 RS
= RepeatedSubstring();
519 // Each leaf node represents a repeat of a string.
520 std::vector
<SuffixTreeNode
*> LeafChildren
;
522 // Continue visiting nodes until we find one which repeats more than once.
523 while (!ToVisit
.empty()) {
524 SuffixTreeNode
*Curr
= ToVisit
.back();
526 LeafChildren
.clear();
528 // Keep track of the length of the string associated with the node. If
529 // it's too short, we'll quit.
530 unsigned Length
= Curr
->ConcatLen
;
532 // Iterate over each child, saving internal nodes for visiting, and
533 // leaf nodes in LeafChildren. Internal nodes represent individual
534 // strings, which may repeat.
535 for (auto &ChildPair
: Curr
->Children
) {
536 // Save all of this node's children for processing.
537 if (!ChildPair
.second
->isLeaf())
538 ToVisit
.push_back(ChildPair
.second
);
540 // It's not an internal node, so it must be a leaf. If we have a
541 // long enough string, then save the leaf children.
542 else if (Length
>= MinLength
)
543 LeafChildren
.push_back(ChildPair
.second
);
546 // The root never represents a repeated substring. If we're looking at
547 // that, then skip it.
551 // Do we have any repeated substrings?
552 if (LeafChildren
.size() >= 2) {
553 // Yes. Update the state to reflect this, and then bail out.
556 for (SuffixTreeNode
*Leaf
: LeafChildren
)
557 RS
.StartIndices
.push_back(Leaf
->SuffixIdx
);
562 // At this point, either NewRS is an empty RepeatedSubstring, or it was
563 // set in the above loop. Similarly, N is either nullptr, or the node
564 // associated with NewRS.
568 /// Return the current repeated substring.
569 RepeatedSubstring
&operator*() { return RS
; }
571 RepeatedSubstringIterator
&operator++() {
576 RepeatedSubstringIterator
operator++(int I
) {
577 RepeatedSubstringIterator
It(*this);
582 bool operator==(const RepeatedSubstringIterator
&Other
) {
585 bool operator!=(const RepeatedSubstringIterator
&Other
) {
586 return !(*this == Other
);
589 RepeatedSubstringIterator(SuffixTreeNode
*N
) : N(N
) {
590 // Do we have a non-null node?
592 // Yes. At the first step, we need to visit all of N's children.
593 // Note: This means that we visit N last.
594 ToVisit
.push_back(N
);
600 typedef RepeatedSubstringIterator iterator
;
601 iterator
begin() { return iterator(Root
); }
602 iterator
end() { return iterator(nullptr); }
605 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
606 struct InstructionMapper
{
608 /// The next available integer to assign to a \p MachineInstr that
609 /// cannot be outlined.
611 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
612 unsigned IllegalInstrNumber
= -3;
614 /// The next available integer to assign to a \p MachineInstr that can
616 unsigned LegalInstrNumber
= 0;
618 /// Correspondence from \p MachineInstrs to unsigned integers.
619 DenseMap
<MachineInstr
*, unsigned, MachineInstrExpressionTrait
>
620 InstructionIntegerMap
;
622 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
623 DenseMap
<MachineBasicBlock
*, unsigned> MBBFlagsMap
;
625 /// The vector of unsigned integers that the module is mapped to.
626 std::vector
<unsigned> UnsignedVec
;
628 /// Stores the location of the instruction associated with the integer
629 /// at index i in \p UnsignedVec for each index i.
630 std::vector
<MachineBasicBlock::iterator
> InstrList
;
632 // Set if we added an illegal number in the previous step.
633 // Since each illegal number is unique, we only need one of them between
634 // each range of legal numbers. This lets us make sure we don't add more
635 // than one illegal number per range.
636 bool AddedIllegalLastTime
= false;
638 /// Maps \p *It to a legal integer.
640 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
641 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
643 /// \returns The integer that \p *It was mapped to.
644 unsigned mapToLegalUnsigned(
645 MachineBasicBlock::iterator
&It
, bool &CanOutlineWithPrevInstr
,
646 bool &HaveLegalRange
, unsigned &NumLegalInBlock
,
647 std::vector
<unsigned> &UnsignedVecForMBB
,
648 std::vector
<MachineBasicBlock::iterator
> &InstrListForMBB
) {
649 // We added something legal, so we should unset the AddedLegalLastTime
651 AddedIllegalLastTime
= false;
653 // If we have at least two adjacent legal instructions (which may have
654 // invisible instructions in between), remember that.
655 if (CanOutlineWithPrevInstr
)
656 HaveLegalRange
= true;
657 CanOutlineWithPrevInstr
= true;
659 // Keep track of the number of legal instructions we insert.
662 // Get the integer for this instruction or give it the current
664 InstrListForMBB
.push_back(It
);
665 MachineInstr
&MI
= *It
;
667 DenseMap
<MachineInstr
*, unsigned, MachineInstrExpressionTrait
>::iterator
669 std::tie(ResultIt
, WasInserted
) =
670 InstructionIntegerMap
.insert(std::make_pair(&MI
, LegalInstrNumber
));
671 unsigned MINumber
= ResultIt
->second
;
673 // There was an insertion.
677 UnsignedVecForMBB
.push_back(MINumber
);
679 // Make sure we don't overflow or use any integers reserved by the DenseMap.
680 if (LegalInstrNumber
>= IllegalInstrNumber
)
681 report_fatal_error("Instruction mapping overflow!");
683 assert(LegalInstrNumber
!= DenseMapInfo
<unsigned>::getEmptyKey() &&
684 "Tried to assign DenseMap tombstone or empty key to instruction.");
685 assert(LegalInstrNumber
!= DenseMapInfo
<unsigned>::getTombstoneKey() &&
686 "Tried to assign DenseMap tombstone or empty key to instruction.");
691 /// Maps \p *It to an illegal integer.
693 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
694 /// IllegalInstrNumber.
696 /// \returns The integer that \p *It was mapped to.
697 unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator
&It
,
698 bool &CanOutlineWithPrevInstr
, std::vector
<unsigned> &UnsignedVecForMBB
,
699 std::vector
<MachineBasicBlock::iterator
> &InstrListForMBB
) {
700 // Can't outline an illegal instruction. Set the flag.
701 CanOutlineWithPrevInstr
= false;
703 // Only add one illegal number per range of legal numbers.
704 if (AddedIllegalLastTime
)
705 return IllegalInstrNumber
;
707 // Remember that we added an illegal number last time.
708 AddedIllegalLastTime
= true;
709 unsigned MINumber
= IllegalInstrNumber
;
711 InstrListForMBB
.push_back(It
);
712 UnsignedVecForMBB
.push_back(IllegalInstrNumber
);
713 IllegalInstrNumber
--;
715 assert(LegalInstrNumber
< IllegalInstrNumber
&&
716 "Instruction mapping overflow!");
718 assert(IllegalInstrNumber
!= DenseMapInfo
<unsigned>::getEmptyKey() &&
719 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
721 assert(IllegalInstrNumber
!= DenseMapInfo
<unsigned>::getTombstoneKey() &&
722 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
727 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
728 /// and appends it to \p UnsignedVec and \p InstrList.
730 /// Two instructions are assigned the same integer if they are identical.
731 /// If an instruction is deemed unsafe to outline, then it will be assigned an
732 /// unique integer. The resulting mapping is placed into a suffix tree and
733 /// queried for candidates.
735 /// \param MBB The \p MachineBasicBlock to be translated into integers.
736 /// \param TII \p TargetInstrInfo for the function.
737 void convertToUnsignedVec(MachineBasicBlock
&MBB
,
738 const TargetInstrInfo
&TII
) {
741 // Don't even map in this case.
742 if (!TII
.isMBBSafeToOutlineFrom(MBB
, Flags
))
745 // Store info for the MBB for later outlining.
746 MBBFlagsMap
[&MBB
] = Flags
;
748 MachineBasicBlock::iterator It
= MBB
.begin();
750 // The number of instructions in this block that will be considered for
752 unsigned NumLegalInBlock
= 0;
754 // True if we have at least two legal instructions which aren't separated
755 // by an illegal instruction.
756 bool HaveLegalRange
= false;
758 // True if we can perform outlining given the last mapped (non-invisible)
759 // instruction. This lets us know if we have a legal range.
760 bool CanOutlineWithPrevInstr
= false;
762 // FIXME: Should this all just be handled in the target, rather than using
763 // repeated calls to getOutliningType?
764 std::vector
<unsigned> UnsignedVecForMBB
;
765 std::vector
<MachineBasicBlock::iterator
> InstrListForMBB
;
767 for (MachineBasicBlock::iterator Et
= MBB
.end(); It
!= Et
; It
++) {
768 // Keep track of where this instruction is in the module.
769 switch (TII
.getOutliningType(It
, Flags
)) {
770 case InstrType::Illegal
:
771 mapToIllegalUnsigned(It
, CanOutlineWithPrevInstr
,
772 UnsignedVecForMBB
, InstrListForMBB
);
775 case InstrType::Legal
:
776 mapToLegalUnsigned(It
, CanOutlineWithPrevInstr
, HaveLegalRange
,
777 NumLegalInBlock
, UnsignedVecForMBB
, InstrListForMBB
);
780 case InstrType::LegalTerminator
:
781 mapToLegalUnsigned(It
, CanOutlineWithPrevInstr
, HaveLegalRange
,
782 NumLegalInBlock
, UnsignedVecForMBB
, InstrListForMBB
);
783 // The instruction also acts as a terminator, so we have to record that
785 mapToIllegalUnsigned(It
, CanOutlineWithPrevInstr
, UnsignedVecForMBB
,
789 case InstrType::Invisible
:
790 // Normally this is set by mapTo(Blah)Unsigned, but we just want to
791 // skip this instruction. So, unset the flag here.
792 AddedIllegalLastTime
= false;
797 // Are there enough legal instructions in the block for outlining to be
799 if (HaveLegalRange
) {
800 // After we're done every insertion, uniquely terminate this part of the
801 // "string". This makes sure we won't match across basic block or function
802 // boundaries since the "end" is encoded uniquely and thus appears in no
803 // repeated substring.
804 mapToIllegalUnsigned(It
, CanOutlineWithPrevInstr
, UnsignedVecForMBB
,
806 InstrList
.insert(InstrList
.end(), InstrListForMBB
.begin(),
807 InstrListForMBB
.end());
808 UnsignedVec
.insert(UnsignedVec
.end(), UnsignedVecForMBB
.begin(),
809 UnsignedVecForMBB
.end());
813 InstructionMapper() {
814 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
816 assert(DenseMapInfo
<unsigned>::getEmptyKey() == (unsigned)-1 &&
817 "DenseMapInfo<unsigned>'s empty key isn't -1!");
818 assert(DenseMapInfo
<unsigned>::getTombstoneKey() == (unsigned)-2 &&
819 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
823 /// An interprocedural pass which finds repeated sequences of
824 /// instructions and replaces them with calls to functions.
826 /// Each instruction is mapped to an unsigned integer and placed in a string.
827 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
828 /// is then repeatedly queried for repeated sequences of instructions. Each
829 /// non-overlapping repeated sequence is then placed in its own
830 /// \p MachineFunction and each instance is then replaced with a call to that
832 struct MachineOutliner
: public ModulePass
{
836 /// Set to true if the outliner should consider functions with
837 /// linkonceodr linkage.
838 bool OutlineFromLinkOnceODRs
= false;
840 /// Set to true if the outliner should run on all functions in the module
841 /// considered safe for outlining.
842 /// Set to true by default for compatibility with llc's -run-pass option.
843 /// Set when the pass is constructed in TargetPassConfig.
844 bool RunOnAllFunctions
= true;
846 StringRef
getPassName() const override
{ return "Machine Outliner"; }
848 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
849 AU
.addRequired
<MachineModuleInfo
>();
850 AU
.addPreserved
<MachineModuleInfo
>();
851 AU
.setPreservesAll();
852 ModulePass::getAnalysisUsage(AU
);
855 MachineOutliner() : ModulePass(ID
) {
856 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
859 /// Remark output explaining that not outlining a set of candidates would be
860 /// better than outlining that set.
861 void emitNotOutliningCheaperRemark(
862 unsigned StringLen
, std::vector
<Candidate
> &CandidatesForRepeatedSeq
,
863 OutlinedFunction
&OF
);
865 /// Remark output explaining that a function was outlined.
866 void emitOutlinedFunctionRemark(OutlinedFunction
&OF
);
868 /// Find all repeated substrings that satisfy the outlining cost model by
869 /// constructing a suffix tree.
871 /// If a substring appears at least twice, then it must be represented by
872 /// an internal node which appears in at least two suffixes. Each suffix
873 /// is represented by a leaf node. To do this, we visit each internal node
874 /// in the tree, using the leaf children of each internal node. If an
875 /// internal node represents a beneficial substring, then we use each of
876 /// its leaf children to find the locations of its substring.
878 /// \param Mapper Contains outlining mapping information.
879 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
880 /// each type of candidate.
881 void findCandidates(InstructionMapper
&Mapper
,
882 std::vector
<OutlinedFunction
> &FunctionList
);
884 /// Replace the sequences of instructions represented by \p OutlinedFunctions
885 /// with calls to functions.
887 /// \param M The module we are outlining from.
888 /// \param FunctionList A list of functions to be inserted into the module.
889 /// \param Mapper Contains the instruction mappings for the module.
890 bool outline(Module
&M
, std::vector
<OutlinedFunction
> &FunctionList
,
891 InstructionMapper
&Mapper
);
893 /// Creates a function for \p OF and inserts it into the module.
894 MachineFunction
*createOutlinedFunction(Module
&M
, OutlinedFunction
&OF
,
895 InstructionMapper
&Mapper
,
898 /// Construct a suffix tree on the instructions in \p M and outline repeated
899 /// strings from that tree.
900 bool runOnModule(Module
&M
) override
;
902 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
903 /// function for remark emission.
904 DISubprogram
*getSubprogramOrNull(const OutlinedFunction
&OF
) {
906 for (const Candidate
&C
: OF
.Candidates
)
907 if (C
.getMF() && (SP
= C
.getMF()->getFunction().getSubprogram()))
912 /// Populate and \p InstructionMapper with instruction-to-integer mappings.
913 /// These are used to construct a suffix tree.
914 void populateMapper(InstructionMapper
&Mapper
, Module
&M
,
915 MachineModuleInfo
&MMI
);
917 /// Initialize information necessary to output a size remark.
918 /// FIXME: This should be handled by the pass manager, not the outliner.
919 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
921 void initSizeRemarkInfo(
922 const Module
&M
, const MachineModuleInfo
&MMI
,
923 StringMap
<unsigned> &FunctionToInstrCount
);
926 // FIXME: This should be handled by the pass manager, not the outliner.
927 void emitInstrCountChangedRemark(
928 const Module
&M
, const MachineModuleInfo
&MMI
,
929 const StringMap
<unsigned> &FunctionToInstrCount
);
931 } // Anonymous namespace.
933 char MachineOutliner::ID
= 0;
936 ModulePass
*createMachineOutlinerPass(bool RunOnAllFunctions
) {
937 MachineOutliner
*OL
= new MachineOutliner();
938 OL
->RunOnAllFunctions
= RunOnAllFunctions
;
944 INITIALIZE_PASS(MachineOutliner
, DEBUG_TYPE
, "Machine Function Outliner", false,
947 void MachineOutliner::emitNotOutliningCheaperRemark(
948 unsigned StringLen
, std::vector
<Candidate
> &CandidatesForRepeatedSeq
,
949 OutlinedFunction
&OF
) {
950 // FIXME: Right now, we arbitrarily choose some Candidate from the
951 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
952 // We should probably sort these by function name or something to make sure
953 // the remarks are stable.
954 Candidate
&C
= CandidatesForRepeatedSeq
.front();
955 MachineOptimizationRemarkEmitter
MORE(*(C
.getMF()), nullptr);
957 MachineOptimizationRemarkMissed
R(DEBUG_TYPE
, "NotOutliningCheaper",
958 C
.front()->getDebugLoc(), C
.getMBB());
959 R
<< "Did not outline " << NV("Length", StringLen
) << " instructions"
960 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq
.size())
962 << " Bytes from outlining all occurrences ("
963 << NV("OutliningCost", OF
.getOutliningCost()) << ")"
964 << " >= Unoutlined instruction bytes ("
965 << NV("NotOutliningCost", OF
.getNotOutlinedCost()) << ")"
966 << " (Also found at: ";
968 // Tell the user the other places the candidate was found.
969 for (unsigned i
= 1, e
= CandidatesForRepeatedSeq
.size(); i
< e
; i
++) {
970 R
<< NV((Twine("OtherStartLoc") + Twine(i
)).str(),
971 CandidatesForRepeatedSeq
[i
].front()->getDebugLoc());
981 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction
&OF
) {
982 MachineBasicBlock
*MBB
= &*OF
.MF
->begin();
983 MachineOptimizationRemarkEmitter
MORE(*OF
.MF
, nullptr);
984 MachineOptimizationRemark
R(DEBUG_TYPE
, "OutlinedFunction",
985 MBB
->findDebugLoc(MBB
->begin()), MBB
);
986 R
<< "Saved " << NV("OutliningBenefit", OF
.getBenefit()) << " bytes by "
987 << "outlining " << NV("Length", OF
.getNumInstrs()) << " instructions "
988 << "from " << NV("NumOccurrences", OF
.getOccurrenceCount())
992 // Tell the user the other places the candidate was found.
993 for (size_t i
= 0, e
= OF
.Candidates
.size(); i
< e
; i
++) {
995 R
<< NV((Twine("StartLoc") + Twine(i
)).str(),
996 OF
.Candidates
[i
].front()->getDebugLoc());
1007 MachineOutliner::findCandidates(InstructionMapper
&Mapper
,
1008 std::vector
<OutlinedFunction
> &FunctionList
) {
1009 FunctionList
.clear();
1010 SuffixTree
ST(Mapper
.UnsignedVec
);
1012 // First, find dall of the repeated substrings in the tree of minimum length
1014 std::vector
<Candidate
> CandidatesForRepeatedSeq
;
1015 for (auto It
= ST
.begin(), Et
= ST
.end(); It
!= Et
; ++It
) {
1016 CandidatesForRepeatedSeq
.clear();
1017 SuffixTree::RepeatedSubstring RS
= *It
;
1018 unsigned StringLen
= RS
.Length
;
1019 for (const unsigned &StartIdx
: RS
.StartIndices
) {
1020 unsigned EndIdx
= StartIdx
+ StringLen
- 1;
1021 // Trick: Discard some candidates that would be incompatible with the
1022 // ones we've already found for this sequence. This will save us some
1023 // work in candidate selection.
1025 // If two candidates overlap, then we can't outline them both. This
1026 // happens when we have candidates that look like, say
1028 // AA (where each "A" is an instruction).
1030 // We might have some portion of the module that looks like this:
1033 // In this case, there are 5 different copies of "AA" in this range, but
1034 // at most 3 can be outlined. If only outlining 3 of these is going to
1035 // be unbeneficial, then we ought to not bother.
1037 // Note that two things DON'T overlap when they look like this:
1038 // start1...end1 .... start2...end2
1039 // That is, one must either
1040 // * End before the other starts
1041 // * Start after the other ends
1043 CandidatesForRepeatedSeq
.begin(), CandidatesForRepeatedSeq
.end(),
1044 [&StartIdx
, &EndIdx
](const Candidate
&C
) {
1045 return (EndIdx
< C
.getStartIdx() || StartIdx
> C
.getEndIdx());
1047 // It doesn't overlap with anything, so we can outline it.
1048 // Each sequence is over [StartIt, EndIt].
1049 // Save the candidate and its location.
1051 MachineBasicBlock::iterator StartIt
= Mapper
.InstrList
[StartIdx
];
1052 MachineBasicBlock::iterator EndIt
= Mapper
.InstrList
[EndIdx
];
1053 MachineBasicBlock
*MBB
= StartIt
->getParent();
1055 CandidatesForRepeatedSeq
.emplace_back(StartIdx
, StringLen
, StartIt
,
1056 EndIt
, MBB
, FunctionList
.size(),
1057 Mapper
.MBBFlagsMap
[MBB
]);
1061 // We've found something we might want to outline.
1062 // Create an OutlinedFunction to store it and check if it'd be beneficial
1064 if (CandidatesForRepeatedSeq
.size() < 2)
1067 // Arbitrarily choose a TII from the first candidate.
1068 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
1069 const TargetInstrInfo
*TII
=
1070 CandidatesForRepeatedSeq
[0].getMF()->getSubtarget().getInstrInfo();
1072 OutlinedFunction OF
=
1073 TII
->getOutliningCandidateInfo(CandidatesForRepeatedSeq
);
1075 // If we deleted too many candidates, then there's nothing worth outlining.
1076 // FIXME: This should take target-specified instruction sizes into account.
1077 if (OF
.Candidates
.size() < 2)
1080 // Is it better to outline this candidate than not?
1081 if (OF
.getBenefit() < 1) {
1082 emitNotOutliningCheaperRemark(StringLen
, CandidatesForRepeatedSeq
, OF
);
1086 FunctionList
.push_back(OF
);
1091 MachineOutliner::createOutlinedFunction(Module
&M
, OutlinedFunction
&OF
,
1092 InstructionMapper
&Mapper
,
1095 // Create the function name. This should be unique.
1096 // FIXME: We should have a better naming scheme. This should be stable,
1097 // regardless of changes to the outliner's cost model/traversal order.
1098 std::string FunctionName
= ("OUTLINED_FUNCTION_" + Twine(Name
)).str();
1100 // Create the function using an IR-level function.
1101 LLVMContext
&C
= M
.getContext();
1102 Function
*F
= Function::Create(FunctionType::get(Type::getVoidTy(C
), false),
1103 Function::ExternalLinkage
, FunctionName
, M
);
1105 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1106 // which gives us better results when we outline from linkonceodr functions.
1107 F
->setLinkage(GlobalValue::InternalLinkage
);
1108 F
->setUnnamedAddr(GlobalValue::UnnamedAddr::Global
);
1110 // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's
1113 // Set optsize/minsize, so we don't insert padding between outlined
1115 F
->addFnAttr(Attribute::OptimizeForSize
);
1116 F
->addFnAttr(Attribute::MinSize
);
1118 // Include target features from an arbitrary candidate for the outlined
1119 // function. This makes sure the outlined function knows what kinds of
1120 // instructions are going into it. This is fine, since all parent functions
1121 // must necessarily support the instructions that are in the outlined region.
1122 Candidate
&FirstCand
= OF
.Candidates
.front();
1123 const Function
&ParentFn
= FirstCand
.getMF()->getFunction();
1124 if (ParentFn
.hasFnAttribute("target-features"))
1125 F
->addFnAttr(ParentFn
.getFnAttribute("target-features"));
1127 BasicBlock
*EntryBB
= BasicBlock::Create(C
, "entry", F
);
1128 IRBuilder
<> Builder(EntryBB
);
1129 Builder
.CreateRetVoid();
1131 MachineModuleInfo
&MMI
= getAnalysis
<MachineModuleInfo
>();
1132 MachineFunction
&MF
= MMI
.getOrCreateMachineFunction(*F
);
1133 MachineBasicBlock
&MBB
= *MF
.CreateMachineBasicBlock();
1134 const TargetSubtargetInfo
&STI
= MF
.getSubtarget();
1135 const TargetInstrInfo
&TII
= *STI
.getInstrInfo();
1137 // Insert the new function into the module.
1138 MF
.insert(MF
.begin(), &MBB
);
1140 for (auto I
= FirstCand
.front(), E
= std::next(FirstCand
.back()); I
!= E
;
1142 MachineInstr
*NewMI
= MF
.CloneMachineInstr(&*I
);
1143 NewMI
->dropMemRefs(MF
);
1145 // Don't keep debug information for outlined instructions.
1146 NewMI
->setDebugLoc(DebugLoc());
1147 MBB
.insert(MBB
.end(), NewMI
);
1150 TII
.buildOutlinedFrame(MBB
, MF
, OF
);
1152 // Outlined functions shouldn't preserve liveness.
1153 MF
.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness
);
1154 MF
.getRegInfo().freezeReservedRegs(MF
);
1156 // If there's a DISubprogram associated with this outlined function, then
1157 // emit debug info for the outlined function.
1158 if (DISubprogram
*SP
= getSubprogramOrNull(OF
)) {
1159 // We have a DISubprogram. Get its DICompileUnit.
1160 DICompileUnit
*CU
= SP
->getUnit();
1161 DIBuilder
DB(M
, true, CU
);
1162 DIFile
*Unit
= SP
->getFile();
1164 // Get the mangled name of the function for the linkage name.
1166 llvm::raw_string_ostream
MangledNameStream(Dummy
);
1167 Mg
.getNameWithPrefix(MangledNameStream
, F
, false);
1169 DISubprogram
*OutlinedSP
= DB
.createFunction(
1170 Unit
/* Context */, F
->getName(), StringRef(MangledNameStream
.str()),
1172 0 /* Line 0 is reserved for compiler-generated code. */,
1173 DB
.createSubroutineType(DB
.getOrCreateTypeArray(None
)), /* void type */
1174 0, /* Line 0 is reserved for compiler-generated code. */
1175 DINode::DIFlags::FlagArtificial
/* Compiler-generated code. */,
1176 /* Outlined code is optimized code by definition. */
1177 DISubprogram::SPFlagDefinition
| DISubprogram::SPFlagOptimized
);
1179 // Don't add any new variables to the subprogram.
1180 DB
.finalizeSubprogram(OutlinedSP
);
1182 // Attach subprogram to the function.
1183 F
->setSubprogram(OutlinedSP
);
1184 // We're done with the DIBuilder.
1191 bool MachineOutliner::outline(Module
&M
,
1192 std::vector
<OutlinedFunction
> &FunctionList
,
1193 InstructionMapper
&Mapper
) {
1195 bool OutlinedSomething
= false;
1197 // Number to append to the current outlined function.
1198 unsigned OutlinedFunctionNum
= 0;
1200 // Sort by benefit. The most beneficial functions should be outlined first.
1201 llvm::stable_sort(FunctionList
, [](const OutlinedFunction
&LHS
,
1202 const OutlinedFunction
&RHS
) {
1203 return LHS
.getBenefit() > RHS
.getBenefit();
1206 // Walk over each function, outlining them as we go along. Functions are
1207 // outlined greedily, based off the sort above.
1208 for (OutlinedFunction
&OF
: FunctionList
) {
1209 // If we outlined something that overlapped with a candidate in a previous
1210 // step, then we can't outline from it.
1211 erase_if(OF
.Candidates
, [&Mapper
](Candidate
&C
) {
1213 Mapper
.UnsignedVec
.begin() + C
.getStartIdx(),
1214 Mapper
.UnsignedVec
.begin() + C
.getEndIdx() + 1,
1215 [](unsigned I
) { return (I
== static_cast<unsigned>(-1)); });
1218 // If we made it unbeneficial to outline this function, skip it.
1219 if (OF
.getBenefit() < 1)
1222 // It's beneficial. Create the function and outline its sequence's
1224 OF
.MF
= createOutlinedFunction(M
, OF
, Mapper
, OutlinedFunctionNum
);
1225 emitOutlinedFunctionRemark(OF
);
1227 OutlinedFunctionNum
++; // Created a function, move to the next name.
1228 MachineFunction
*MF
= OF
.MF
;
1229 const TargetSubtargetInfo
&STI
= MF
->getSubtarget();
1230 const TargetInstrInfo
&TII
= *STI
.getInstrInfo();
1232 // Replace occurrences of the sequence with calls to the new function.
1233 for (Candidate
&C
: OF
.Candidates
) {
1234 MachineBasicBlock
&MBB
= *C
.getMBB();
1235 MachineBasicBlock::iterator StartIt
= C
.front();
1236 MachineBasicBlock::iterator EndIt
= C
.back();
1239 auto CallInst
= TII
.insertOutlinedCall(M
, MBB
, StartIt
, *MF
, C
);
1241 // If the caller tracks liveness, then we need to make sure that
1242 // anything we outline doesn't break liveness assumptions. The outlined
1243 // functions themselves currently don't track liveness, but we should
1244 // make sure that the ranges we yank things out of aren't wrong.
1245 if (MBB
.getParent()->getProperties().hasProperty(
1246 MachineFunctionProperties::Property::TracksLiveness
)) {
1247 // Helper lambda for adding implicit def operands to the call
1248 // instruction. It also updates call site information for moved
1250 auto CopyDefsAndUpdateCalls
= [&CallInst
](MachineInstr
&MI
) {
1251 for (MachineOperand
&MOP
: MI
.operands()) {
1252 // Skip over anything that isn't a register.
1256 // If it's a def, add it to the call instruction.
1258 CallInst
->addOperand(MachineOperand::CreateReg(
1259 MOP
.getReg(), true, /* isDef = true */
1260 true /* isImp = true */));
1263 MI
.getMF()->updateCallSiteInfo(&MI
);
1265 // Copy over the defs in the outlined range.
1266 // First inst in outlined range <-- Anything that's defined in this
1267 // ... .. range has to be added as an
1268 // implicit Last inst in outlined range <-- def to the call
1269 // instruction. Also remove call site information for outlined block
1271 std::for_each(CallInst
, std::next(EndIt
), CopyDefsAndUpdateCalls
);
1274 // Erase from the point after where the call was inserted up to, and
1275 // including, the final instruction in the sequence.
1276 // Erase needs one past the end, so we need std::next there too.
1277 MBB
.erase(std::next(StartIt
), std::next(EndIt
));
1279 // Keep track of what we removed by marking them all as -1.
1280 std::for_each(Mapper
.UnsignedVec
.begin() + C
.getStartIdx(),
1281 Mapper
.UnsignedVec
.begin() + C
.getEndIdx() + 1,
1282 [](unsigned &I
) { I
= static_cast<unsigned>(-1); });
1283 OutlinedSomething
= true;
1290 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething
<< "\n";);
1292 return OutlinedSomething
;
1295 void MachineOutliner::populateMapper(InstructionMapper
&Mapper
, Module
&M
,
1296 MachineModuleInfo
&MMI
) {
1297 // Build instruction mappings for each function in the module. Start by
1298 // iterating over each Function in M.
1299 for (Function
&F
: M
) {
1301 // If there's nothing in F, then there's no reason to try and outline from
1306 // There's something in F. Check if it has a MachineFunction associated with
1308 MachineFunction
*MF
= MMI
.getMachineFunction(F
);
1310 // If it doesn't, then there's nothing to outline from. Move to the next
1315 const TargetInstrInfo
*TII
= MF
->getSubtarget().getInstrInfo();
1317 if (!RunOnAllFunctions
&& !TII
->shouldOutlineFromFunctionByDefault(*MF
))
1320 // We have a MachineFunction. Ask the target if it's suitable for outlining.
1321 // If it isn't, then move on to the next Function in the module.
1322 if (!TII
->isFunctionSafeToOutlineFrom(*MF
, OutlineFromLinkOnceODRs
))
1325 // We have a function suitable for outlining. Iterate over every
1326 // MachineBasicBlock in MF and try to map its instructions to a list of
1327 // unsigned integers.
1328 for (MachineBasicBlock
&MBB
: *MF
) {
1329 // If there isn't anything in MBB, then there's no point in outlining from
1331 // If there are fewer than 2 instructions in the MBB, then it can't ever
1332 // contain something worth outlining.
1333 // FIXME: This should be based off of the maximum size in B of an outlined
1334 // call versus the size in B of the MBB.
1335 if (MBB
.empty() || MBB
.size() < 2)
1338 // Check if MBB could be the target of an indirect branch. If it is, then
1339 // we don't want to outline from it.
1340 if (MBB
.hasAddressTaken())
1343 // MBB is suitable for outlining. Map it to a list of unsigneds.
1344 Mapper
.convertToUnsignedVec(MBB
, *TII
);
1349 void MachineOutliner::initSizeRemarkInfo(
1350 const Module
&M
, const MachineModuleInfo
&MMI
,
1351 StringMap
<unsigned> &FunctionToInstrCount
) {
1352 // Collect instruction counts for every function. We'll use this to emit
1353 // per-function size remarks later.
1354 for (const Function
&F
: M
) {
1355 MachineFunction
*MF
= MMI
.getMachineFunction(F
);
1357 // We only care about MI counts here. If there's no MachineFunction at this
1358 // point, then there won't be after the outliner runs, so let's move on.
1361 FunctionToInstrCount
[F
.getName().str()] = MF
->getInstructionCount();
1365 void MachineOutliner::emitInstrCountChangedRemark(
1366 const Module
&M
, const MachineModuleInfo
&MMI
,
1367 const StringMap
<unsigned> &FunctionToInstrCount
) {
1368 // Iterate over each function in the module and emit remarks.
1369 // Note that we won't miss anything by doing this, because the outliner never
1370 // deletes functions.
1371 for (const Function
&F
: M
) {
1372 MachineFunction
*MF
= MMI
.getMachineFunction(F
);
1374 // The outliner never deletes functions. If we don't have a MF here, then we
1375 // didn't have one prior to outlining either.
1379 std::string Fname
= F
.getName();
1380 unsigned FnCountAfter
= MF
->getInstructionCount();
1381 unsigned FnCountBefore
= 0;
1383 // Check if the function was recorded before.
1384 auto It
= FunctionToInstrCount
.find(Fname
);
1386 // Did we have a previously-recorded size? If yes, then set FnCountBefore
1388 if (It
!= FunctionToInstrCount
.end())
1389 FnCountBefore
= It
->second
;
1391 // Compute the delta and emit a remark if there was a change.
1392 int64_t FnDelta
= static_cast<int64_t>(FnCountAfter
) -
1393 static_cast<int64_t>(FnCountBefore
);
1397 MachineOptimizationRemarkEmitter
MORE(*MF
, nullptr);
1399 MachineOptimizationRemarkAnalysis
R("size-info", "FunctionMISizeChange",
1400 DiagnosticLocation(),
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 MachineModuleInfo
&MMI
= getAnalysis
<MachineModuleInfo
>();
1426 // If the user passed -enable-machine-outliner=always or
1427 // -enable-machine-outliner, the pass will run on all functions in the module.
1428 // Otherwise, if the target supports default outlining, it will run on all
1429 // functions deemed by the target to be worth outlining from by default. Tell
1430 // the user how the outliner is running.
1432 dbgs() << "Machine Outliner: Running on ";
1433 if (RunOnAllFunctions
)
1434 dbgs() << "all functions";
1436 dbgs() << "target-default functions";
1440 // If the user specifies that they want to outline from linkonceodrs, set
1442 OutlineFromLinkOnceODRs
= EnableLinkOnceODROutlining
;
1443 InstructionMapper Mapper
;
1445 // Prepare instruction mappings for the suffix tree.
1446 populateMapper(Mapper
, M
, MMI
);
1447 std::vector
<OutlinedFunction
> FunctionList
;
1449 // Find all of the outlining candidates.
1450 findCandidates(Mapper
, FunctionList
);
1452 // If we've requested size remarks, then collect the MI counts of every
1453 // function before outlining, and the MI counts after outlining.
1454 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1455 // the pass manager's responsibility.
1456 // This could pretty easily be placed in outline instead, but because we
1457 // really ultimately *don't* want this here, it's done like this for now
1460 // Check if we want size remarks.
1461 bool ShouldEmitSizeRemarks
= M
.shouldEmitInstrCountChangedRemark();
1462 StringMap
<unsigned> FunctionToInstrCount
;
1463 if (ShouldEmitSizeRemarks
)
1464 initSizeRemarkInfo(M
, MMI
, FunctionToInstrCount
);
1466 // Outline each of the candidates and return true if something was outlined.
1467 bool OutlinedSomething
= outline(M
, FunctionList
, Mapper
);
1469 // If we outlined something, we definitely changed the MI count of the
1470 // module. If we've asked for size remarks, then output them.
1471 // FIXME: This should be in the pass manager.
1472 if (ShouldEmitSizeRemarks
&& OutlinedSomething
)
1473 emitInstrCountChangedRemark(M
, MMI
, FunctionToInstrCount
);
1475 return OutlinedSomething
;