Line data Source code
1 : //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : ///
10 : /// \file
11 : /// Replaces repeated sequences of instructions with function calls.
12 : ///
13 : /// This works by placing every instruction from every basic block in a
14 : /// suffix tree, and repeatedly querying that tree for repeated sequences of
15 : /// instructions. If a sequence of instructions appears often, then it ought
16 : /// to be beneficial to pull out into a function.
17 : ///
18 : /// The MachineOutliner communicates with a given target using hooks defined in
19 : /// TargetInstrInfo.h. The target supplies the outliner with information on how
20 : /// a specific sequence of instructions should be outlined. This information
21 : /// is used to deduce the number of instructions necessary to
22 : ///
23 : /// * Create an outlined function
24 : /// * Call that outlined function
25 : ///
26 : /// Targets must implement
27 : /// * getOutliningCandidateInfo
28 : /// * buildOutlinedFrame
29 : /// * insertOutlinedCall
30 : /// * isFunctionSafeToOutlineFrom
31 : ///
32 : /// in order to make use of the MachineOutliner.
33 : ///
34 : /// This was originally presented at the 2016 LLVM Developers' Meeting in the
35 : /// talk "Reducing Code Size Using Outlining". For a high-level overview of
36 : /// how this pass works, the talk is available on YouTube at
37 : ///
38 : /// https://www.youtube.com/watch?v=yorld-WSOeU
39 : ///
40 : /// The slides for the talk are available at
41 : ///
42 : /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
43 : ///
44 : /// The talk provides an overview of how the outliner finds candidates and
45 : /// ultimately outlines them. It describes how the main data structure for this
46 : /// pass, the suffix tree, is queried and purged for candidates. It also gives
47 : /// a simplified suffix tree construction algorithm for suffix trees based off
48 : /// of the algorithm actually used here, Ukkonen's algorithm.
49 : ///
50 : /// For the original RFC for this pass, please see
51 : ///
52 : /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
53 : ///
54 : /// For more information on the suffix tree data structure, please see
55 : /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
56 : ///
57 : //===----------------------------------------------------------------------===//
58 : #include "llvm/CodeGen/MachineOutliner.h"
59 : #include "llvm/ADT/DenseMap.h"
60 : #include "llvm/ADT/Statistic.h"
61 : #include "llvm/ADT/Twine.h"
62 : #include "llvm/CodeGen/MachineFunction.h"
63 : #include "llvm/CodeGen/MachineModuleInfo.h"
64 : #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
65 : #include "llvm/CodeGen/MachineRegisterInfo.h"
66 : #include "llvm/CodeGen/Passes.h"
67 : #include "llvm/CodeGen/TargetInstrInfo.h"
68 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
69 : #include "llvm/IR/DIBuilder.h"
70 : #include "llvm/IR/IRBuilder.h"
71 : #include "llvm/IR/Mangler.h"
72 : #include "llvm/Support/Allocator.h"
73 : #include "llvm/Support/CommandLine.h"
74 : #include "llvm/Support/Debug.h"
75 : #include "llvm/Support/raw_ostream.h"
76 : #include <functional>
77 : #include <map>
78 : #include <sstream>
79 : #include <tuple>
80 : #include <vector>
81 :
82 : #define DEBUG_TYPE "machine-outliner"
83 :
84 : using namespace llvm;
85 : using namespace ore;
86 : using namespace outliner;
87 :
88 : STATISTIC(NumOutlined, "Number of candidates outlined");
89 : STATISTIC(FunctionsCreated, "Number of functions created");
90 :
91 : // Set to true if the user wants the outliner to run on linkonceodr linkage
92 : // functions. This is false by default because the linker can dedupe linkonceodr
93 : // functions. Since the outliner is confined to a single module (modulo LTO),
94 : // this is off by default. It should, however, be the default behaviour in
95 : // LTO.
96 : static cl::opt<bool> EnableLinkOnceODROutlining(
97 : "enable-linkonceodr-outlining",
98 : cl::Hidden,
99 : cl::desc("Enable the machine outliner on linkonceodr functions"),
100 : cl::init(false));
101 :
102 : namespace {
103 :
104 : /// Represents an undefined index in the suffix tree.
105 : const unsigned EmptyIdx = -1;
106 :
107 : /// A node in a suffix tree which represents a substring or suffix.
108 : ///
109 : /// Each node has either no children or at least two children, with the root
110 : /// being a exception in the empty tree.
111 : ///
112 : /// Children are represented as a map between unsigned integers and nodes. If
113 : /// a node N has a child M on unsigned integer k, then the mapping represented
114 : /// by N is a proper prefix of the mapping represented by M. Note that this,
115 : /// although similar to a trie is somewhat different: each node stores a full
116 : /// substring of the full mapping rather than a single character state.
117 : ///
118 : /// Each internal node contains a pointer to the internal node representing
119 : /// the same string, but with the first character chopped off. This is stored
120 : /// in \p Link. Each leaf node stores the start index of its respective
121 : /// suffix in \p SuffixIdx.
122 2988 : struct SuffixTreeNode {
123 :
124 : /// The children of this node.
125 : ///
126 : /// A child existing on an unsigned integer implies that from the mapping
127 : /// represented by the current node, there is a way to reach another
128 : /// mapping by tacking that character on the end of the current string.
129 : DenseMap<unsigned, SuffixTreeNode *> Children;
130 :
131 : /// A flag set to false if the node has been pruned from the tree.
132 : bool IsInTree = true;
133 :
134 : /// The start index of this node's substring in the main string.
135 : unsigned StartIdx = EmptyIdx;
136 :
137 : /// The end index of this node's substring in the main string.
138 : ///
139 : /// Every leaf node must have its \p EndIdx incremented at the end of every
140 : /// step in the construction algorithm. To avoid having to update O(N)
141 : /// nodes individually at the end of every step, the end index is stored
142 : /// as a pointer.
143 : unsigned *EndIdx = nullptr;
144 :
145 : /// For leaves, the start index of the suffix represented by this node.
146 : ///
147 : /// For all other nodes, this is ignored.
148 : unsigned SuffixIdx = EmptyIdx;
149 :
150 : /// For internal nodes, a pointer to the internal node representing
151 : /// the same sequence with the first character chopped off.
152 : ///
153 : /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
154 : /// Ukkonen's algorithm does to achieve linear-time construction is
155 : /// keep track of which node the next insert should be at. This makes each
156 : /// insert O(1), and there are a total of O(N) inserts. The suffix link
157 : /// helps with inserting children of internal nodes.
158 : ///
159 : /// Say we add a child to an internal node with associated mapping S. The
160 : /// next insertion must be at the node representing S - its first character.
161 : /// This is given by the way that we iteratively build the tree in Ukkonen's
162 : /// algorithm. The main idea is to look at the suffixes of each prefix in the
163 : /// string, starting with the longest suffix of the prefix, and ending with
164 : /// the shortest. Therefore, if we keep pointers between such nodes, we can
165 : /// move to the next insertion point in O(1) time. If we don't, then we'd
166 : /// have to query from the root, which takes O(N) time. This would make the
167 : /// construction algorithm O(N^2) rather than O(N).
168 : SuffixTreeNode *Link = nullptr;
169 :
170 : /// The parent of this node. Every node except for the root has a parent.
171 : SuffixTreeNode *Parent = nullptr;
172 :
173 : /// The number of times this node's string appears in the tree.
174 : ///
175 : /// This is equal to the number of leaf children of the string. It represents
176 : /// the number of suffixes that the node's string is a prefix of.
177 : unsigned OccurrenceCount = 0;
178 :
179 : /// The length of the string formed by concatenating the edge labels from the
180 : /// root to this node.
181 : unsigned ConcatLen = 0;
182 :
183 : /// Returns true if this node is a leaf.
184 0 : bool isLeaf() const { return SuffixIdx != EmptyIdx; }
185 :
186 : /// Returns true if this node is the root of its owning \p SuffixTree.
187 0 : bool isRoot() const { return StartIdx == EmptyIdx; }
188 :
189 : /// Return the number of elements in the substring associated with this node.
190 : size_t size() const {
191 :
192 : // Is it the root? If so, it's the empty string so return 0.
193 3047 : if (isRoot())
194 : return 0;
195 :
196 : assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
197 :
198 : // Size = the number of elements in the string.
199 : // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
200 3047 : return *EndIdx - StartIdx + 1;
201 : }
202 :
203 : SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
204 : SuffixTreeNode *Parent)
205 5976 : : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
206 :
207 : SuffixTreeNode() {}
208 : };
209 :
210 : /// A data structure for fast substring queries.
211 : ///
212 : /// Suffix trees represent the suffixes of their input strings in their leaves.
213 : /// A suffix tree is a type of compressed trie structure where each node
214 : /// represents an entire substring rather than a single character. Each leaf
215 : /// of the tree is a suffix.
216 : ///
217 : /// A suffix tree can be seen as a type of state machine where each state is a
218 : /// substring of the full string. The tree is structured so that, for a string
219 : /// of length N, there are exactly N leaves in the tree. This structure allows
220 : /// us to quickly find repeated substrings of the input string.
221 : ///
222 : /// In this implementation, a "string" is a vector of unsigned integers.
223 : /// These integers may result from hashing some data type. A suffix tree can
224 : /// contain 1 or many strings, which can then be queried as one large string.
225 : ///
226 : /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
227 : /// suffix tree construction. Ukkonen's algorithm is explained in more detail
228 : /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
229 : /// paper is available at
230 : ///
231 : /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
232 : class SuffixTree {
233 : public:
234 : /// Stores each leaf node in the tree.
235 : ///
236 : /// This is used for finding outlining candidates.
237 : std::vector<SuffixTreeNode *> LeafVector;
238 :
239 : /// Each element is an integer representing an instruction in the module.
240 : ArrayRef<unsigned> Str;
241 :
242 : private:
243 : /// Maintains each node in the tree.
244 : SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
245 :
246 : /// The root of the suffix tree.
247 : ///
248 : /// The root represents the empty string. It is maintained by the
249 : /// \p NodeAllocator like every other node in the tree.
250 : SuffixTreeNode *Root = nullptr;
251 :
252 : /// Maintains the end indices of the internal nodes in the tree.
253 : ///
254 : /// Each internal node is guaranteed to never have its end index change
255 : /// during the construction algorithm; however, leaves must be updated at
256 : /// every step. Therefore, we need to store leaf end indices by reference
257 : /// to avoid updating O(N) leaves at every step of construction. Thus,
258 : /// every internal node must be allocated its own end index.
259 : BumpPtrAllocator InternalEndIdxAllocator;
260 :
261 : /// The end index of each leaf in the tree.
262 : unsigned LeafEndIdx = -1;
263 :
264 : /// Helper struct which keeps track of the next insertion point in
265 : /// Ukkonen's algorithm.
266 1098 : struct ActiveState {
267 : /// The next node to insert at.
268 : SuffixTreeNode *Node;
269 :
270 : /// The index of the first character in the substring currently being added.
271 : unsigned Idx = EmptyIdx;
272 :
273 : /// The length of the substring we have to add at the current step.
274 : unsigned Len = 0;
275 : };
276 :
277 : /// The point the next insertion will take place at in the
278 : /// construction algorithm.
279 : ActiveState Active;
280 :
281 : /// Allocate a leaf node and add it to the tree.
282 : ///
283 : /// \param Parent The parent of this node.
284 : /// \param StartIdx The start index of this node's associated string.
285 : /// \param Edge The label on the edge leaving \p Parent to this node.
286 : ///
287 : /// \returns A pointer to the allocated leaf node.
288 1522 : SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
289 : unsigned Edge) {
290 :
291 : assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
292 :
293 : SuffixTreeNode *N = new (NodeAllocator.Allocate())
294 1522 : SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
295 1522 : Parent.Children[Edge] = N;
296 :
297 1522 : return N;
298 : }
299 :
300 : /// Allocate an internal node and add it to the tree.
301 : ///
302 : /// \param Parent The parent of this node. Only null when allocating the root.
303 : /// \param StartIdx The start index of this node's associated string.
304 : /// \param EndIdx The end index of this node's associated string.
305 : /// \param Edge The label on the edge leaving \p Parent to this node.
306 : ///
307 : /// \returns A pointer to the allocated internal node.
308 1466 : SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
309 : unsigned EndIdx, unsigned Edge) {
310 :
311 : assert(StartIdx <= EndIdx && "String can't start after it ends!");
312 : assert(!(!Parent && StartIdx != EmptyIdx) &&
313 : "Non-root internal nodes must have parents!");
314 :
315 1466 : unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
316 : SuffixTreeNode *N = new (NodeAllocator.Allocate())
317 1466 : SuffixTreeNode(StartIdx, E, Root, Parent);
318 1466 : if (Parent)
319 368 : Parent->Children[Edge] = N;
320 :
321 1466 : return N;
322 : }
323 :
324 : /// Set the suffix indices of the leaves to the start indices of their
325 : /// respective suffixes. Also stores each leaf in \p LeafVector at its
326 : /// respective suffix index.
327 : ///
328 : /// \param[in] CurrNode The node currently being visited.
329 : /// \param CurrIdx The current index of the string being visited.
330 2988 : void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
331 :
332 2988 : bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
333 :
334 : // Store the length of the concatenation of all strings from the root to
335 : // this node.
336 2988 : if (!CurrNode.isRoot()) {
337 1890 : if (CurrNode.ConcatLen == 0)
338 1890 : CurrNode.ConcatLen = CurrNode.size();
339 :
340 1890 : if (CurrNode.Parent)
341 1890 : CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
342 : }
343 :
344 : // Traverse the tree depth-first.
345 4878 : for (auto &ChildPair : CurrNode.Children) {
346 : assert(ChildPair.second && "Node had a null child!");
347 3780 : setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
348 : }
349 :
350 : // Is this node a leaf?
351 2988 : if (IsLeaf) {
352 : // If yes, give it a suffix index and bump its parent's occurrence count.
353 1522 : CurrNode.SuffixIdx = Str.size() - CurrIdx;
354 : assert(CurrNode.Parent && "CurrNode had no parent!");
355 1522 : CurrNode.Parent->OccurrenceCount++;
356 :
357 : // Store the leaf in the leaf vector for pruning later.
358 3044 : LeafVector[CurrNode.SuffixIdx] = &CurrNode;
359 : }
360 2988 : }
361 :
362 : /// Construct the suffix tree for the prefix of the input ending at
363 : /// \p EndIdx.
364 : ///
365 : /// Used to construct the full suffix tree iteratively. At the end of each
366 : /// step, the constructed suffix tree is either a valid suffix tree, or a
367 : /// suffix tree with implicit suffixes. At the end of the final step, the
368 : /// suffix tree is a valid tree.
369 : ///
370 : /// \param EndIdx The end index of the current prefix in the main string.
371 : /// \param SuffixesToAdd The number of suffixes that must be added
372 : /// to complete the suffix tree at the current phase.
373 : ///
374 : /// \returns The number of suffixes that have not been added at the end of
375 : /// this step.
376 1522 : unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
377 : SuffixTreeNode *NeedsLink = nullptr;
378 :
379 3236 : while (SuffixesToAdd > 0) {
380 :
381 : // Are we waiting to add anything other than just the last character?
382 2311 : if (Active.Len == 0) {
383 : // If not, then say the active index is the end index.
384 1459 : Active.Idx = EndIdx;
385 : }
386 :
387 : assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
388 :
389 : // The first character in the current substring we're looking at.
390 2311 : unsigned FirstChar = Str[Active.Idx];
391 :
392 : // Have we inserted anything starting with FirstChar at the current node?
393 2311 : if (Active.Node->Children.count(FirstChar) == 0) {
394 : // If not, then we can just insert a leaf and move too the next step.
395 1154 : insertLeaf(*Active.Node, EndIdx, FirstChar);
396 :
397 : // The active node is an internal node, and we visited it, so it must
398 : // need a link if it doesn't have one.
399 1154 : if (NeedsLink) {
400 131 : NeedsLink->Link = Active.Node;
401 : NeedsLink = nullptr;
402 : }
403 : } else {
404 : // There's a match with FirstChar, so look for the point in the tree to
405 : // insert a new node.
406 1157 : SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
407 :
408 1157 : unsigned SubstringLen = NextNode->size();
409 :
410 : // Is the current suffix we're trying to insert longer than the size of
411 : // the child we want to move to?
412 1157 : if (Active.Len >= SubstringLen) {
413 : // If yes, then consume the characters we've seen and move to the next
414 : // node.
415 192 : Active.Idx += SubstringLen;
416 192 : Active.Len -= SubstringLen;
417 192 : Active.Node = NextNode;
418 192 : continue;
419 : }
420 :
421 : // Otherwise, the suffix we're trying to insert must be contained in the
422 : // next node we want to move to.
423 965 : unsigned LastChar = Str[EndIdx];
424 :
425 : // Is the string we're trying to insert a substring of the next node?
426 1930 : if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
427 : // If yes, then we're done for this step. Remember our insertion point
428 : // and move to the next end index. At this point, we have an implicit
429 : // suffix tree.
430 597 : if (NeedsLink && !Active.Node->isRoot()) {
431 0 : NeedsLink->Link = Active.Node;
432 : NeedsLink = nullptr;
433 : }
434 :
435 597 : Active.Len++;
436 597 : break;
437 : }
438 :
439 : // The string we're trying to insert isn't a substring of the next node,
440 : // but matches up to a point. Split the node.
441 : //
442 : // For example, say we ended our search at a node n and we're trying to
443 : // insert ABD. Then we'll create a new node s for AB, reduce n to just
444 : // representing C, and insert a new leaf node l to represent d. This
445 : // allows us to ensure that if n was a leaf, it remains a leaf.
446 : //
447 : // | ABC ---split---> | AB
448 : // n s
449 : // C / \ D
450 : // n l
451 :
452 : // The node s from the diagram
453 : SuffixTreeNode *SplitNode =
454 368 : insertInternalNode(Active.Node, NextNode->StartIdx,
455 : NextNode->StartIdx + Active.Len - 1, FirstChar);
456 :
457 : // Insert the new node representing the new substring into the tree as
458 : // a child of the split node. This is the node l from the diagram.
459 368 : insertLeaf(*SplitNode, EndIdx, LastChar);
460 :
461 : // Make the old node a child of the split node and update its start
462 : // index. This is the node n from the diagram.
463 368 : NextNode->StartIdx += Active.Len;
464 368 : NextNode->Parent = SplitNode;
465 736 : SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
466 :
467 : // SplitNode is an internal node, update the suffix link.
468 368 : if (NeedsLink)
469 217 : NeedsLink->Link = SplitNode;
470 :
471 : NeedsLink = SplitNode;
472 : }
473 :
474 : // We've added something new to the tree, so there's one less suffix to
475 : // add.
476 1522 : SuffixesToAdd--;
477 :
478 1522 : if (Active.Node->isRoot()) {
479 1241 : if (Active.Len > 0) {
480 316 : Active.Len--;
481 316 : Active.Idx = EndIdx - SuffixesToAdd + 1;
482 : }
483 : } else {
484 : // Start the next phase at the next smallest suffix.
485 281 : Active.Node = Active.Node->Link;
486 : }
487 : }
488 :
489 1522 : return SuffixesToAdd;
490 : }
491 :
492 : public:
493 : /// Construct a suffix tree from a sequence of unsigned integers.
494 : ///
495 : /// \param Str The string to construct the suffix tree for.
496 2196 : SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
497 1098 : Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
498 1098 : Root->IsInTree = true;
499 1098 : Active.Node = Root;
500 2196 : LeafVector = std::vector<SuffixTreeNode *>(Str.size());
501 :
502 : // Keep track of the number of suffixes we have to add of the current
503 : // prefix.
504 : unsigned SuffixesToAdd = 0;
505 1098 : Active.Node = Root;
506 :
507 : // Construct the suffix tree iteratively on each prefix of the string.
508 : // PfxEndIdx is the end index of the current prefix.
509 : // End is one past the last element in the string.
510 3718 : for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
511 : PfxEndIdx++) {
512 1522 : SuffixesToAdd++;
513 1522 : LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
514 1522 : SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
515 : }
516 :
517 : // Set the suffix indices of each leaf.
518 : assert(Root && "Root node can't be nullptr!");
519 1098 : setSuffixIndices(*Root, 0);
520 1098 : }
521 : };
522 :
523 : /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
524 : struct InstructionMapper {
525 :
526 : /// The next available integer to assign to a \p MachineInstr that
527 : /// cannot be outlined.
528 : ///
529 : /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
530 : unsigned IllegalInstrNumber = -3;
531 :
532 : /// The next available integer to assign to a \p MachineInstr that can
533 : /// be outlined.
534 : unsigned LegalInstrNumber = 0;
535 :
536 : /// Correspondence from \p MachineInstrs to unsigned integers.
537 : DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
538 : InstructionIntegerMap;
539 :
540 : /// Corresponcence from unsigned integers to \p MachineInstrs.
541 : /// Inverse of \p InstructionIntegerMap.
542 : DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
543 :
544 : /// The vector of unsigned integers that the module is mapped to.
545 : std::vector<unsigned> UnsignedVec;
546 :
547 : /// Stores the location of the instruction associated with the integer
548 : /// at index i in \p UnsignedVec for each index i.
549 : std::vector<MachineBasicBlock::iterator> InstrList;
550 :
551 : /// Maps \p *It to a legal integer.
552 : ///
553 : /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
554 : /// \p IntegerInstructionMap, and \p LegalInstrNumber.
555 : ///
556 : /// \returns The integer that \p *It was mapped to.
557 1231 : unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
558 :
559 : // Get the integer for this instruction or give it the current
560 : // LegalInstrNumber.
561 1231 : InstrList.push_back(It);
562 : MachineInstr &MI = *It;
563 : bool WasInserted;
564 : DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
565 : ResultIt;
566 : std::tie(ResultIt, WasInserted) =
567 1231 : InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
568 1231 : unsigned MINumber = ResultIt->second;
569 :
570 : // There was an insertion.
571 1231 : if (WasInserted) {
572 634 : LegalInstrNumber++;
573 634 : IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
574 : }
575 :
576 1231 : UnsignedVec.push_back(MINumber);
577 :
578 : // Make sure we don't overflow or use any integers reserved by the DenseMap.
579 1231 : if (LegalInstrNumber >= IllegalInstrNumber)
580 0 : report_fatal_error("Instruction mapping overflow!");
581 :
582 : assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
583 : "Tried to assign DenseMap tombstone or empty key to instruction.");
584 : assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
585 : "Tried to assign DenseMap tombstone or empty key to instruction.");
586 :
587 1231 : return MINumber;
588 : }
589 :
590 : /// Maps \p *It to an illegal integer.
591 : ///
592 : /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
593 : ///
594 : /// \returns The integer that \p *It was mapped to.
595 125 : unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
596 125 : unsigned MINumber = IllegalInstrNumber;
597 :
598 125 : InstrList.push_back(It);
599 125 : UnsignedVec.push_back(IllegalInstrNumber);
600 125 : IllegalInstrNumber--;
601 :
602 : assert(LegalInstrNumber < IllegalInstrNumber &&
603 : "Instruction mapping overflow!");
604 :
605 : assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
606 : "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
607 :
608 : assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
609 : "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
610 :
611 125 : return MINumber;
612 : }
613 :
614 : /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
615 : /// and appends it to \p UnsignedVec and \p InstrList.
616 : ///
617 : /// Two instructions are assigned the same integer if they are identical.
618 : /// If an instruction is deemed unsafe to outline, then it will be assigned an
619 : /// unique integer. The resulting mapping is placed into a suffix tree and
620 : /// queried for candidates.
621 : ///
622 : /// \param MBB The \p MachineBasicBlock to be translated into integers.
623 : /// \param TII \p TargetInstrInfo for the function.
624 153 : void convertToUnsignedVec(MachineBasicBlock &MBB,
625 : const TargetInstrInfo &TII) {
626 153 : unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB);
627 :
628 : // Set to true whenever we map an illegal number.
629 : bool AddedIllegalLastTime = false;
630 1697 : for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
631 : It++) {
632 :
633 : // Keep track of where this instruction is in the module.
634 1544 : switch (TII.getOutliningType(It, Flags)) {
635 311 : case InstrType::Illegal:
636 : // If we added an illegal number last time, then don't add more of them.
637 : // One number is all that is necessary to prevent matches on illegal
638 : // instructions.
639 311 : if (AddedIllegalLastTime)
640 : break;
641 : AddedIllegalLastTime = true;
642 125 : mapToIllegalUnsigned(It);
643 125 : break;
644 :
645 1218 : case InstrType::Legal:
646 : AddedIllegalLastTime = false;
647 1218 : mapToLegalUnsigned(It);
648 1218 : break;
649 :
650 13 : case InstrType::LegalTerminator:
651 13 : mapToLegalUnsigned(It);
652 13 : InstrList.push_back(It);
653 : AddedIllegalLastTime = true;
654 13 : UnsignedVec.push_back(IllegalInstrNumber);
655 13 : IllegalInstrNumber--;
656 13 : break;
657 :
658 2 : case InstrType::Invisible:
659 : AddedIllegalLastTime = false;
660 2 : break;
661 : }
662 : }
663 :
664 : // After we're done every insertion, uniquely terminate this part of the
665 : // "string". This makes sure we won't match across basic block or function
666 : // boundaries since the "end" is encoded uniquely and thus appears in no
667 : // repeated substring.
668 153 : InstrList.push_back(MBB.end());
669 153 : UnsignedVec.push_back(IllegalInstrNumber);
670 153 : IllegalInstrNumber--;
671 153 : }
672 :
673 1098 : InstructionMapper() {
674 : // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
675 : // changed.
676 : assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
677 : "DenseMapInfo<unsigned>'s empty key isn't -1!");
678 : assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
679 : "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
680 1098 : }
681 : };
682 :
683 : /// An interprocedural pass which finds repeated sequences of
684 : /// instructions and replaces them with calls to functions.
685 : ///
686 : /// Each instruction is mapped to an unsigned integer and placed in a string.
687 : /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
688 : /// is then repeatedly queried for repeated sequences of instructions. Each
689 : /// non-overlapping repeated sequence is then placed in its own
690 : /// \p MachineFunction and each instance is then replaced with a call to that
691 : /// function.
692 : struct MachineOutliner : public ModulePass {
693 :
694 : static char ID;
695 :
696 : /// Set to true if the outliner should consider functions with
697 : /// linkonceodr linkage.
698 : bool OutlineFromLinkOnceODRs = false;
699 :
700 : /// Set to true if the outliner should run on all functions in the module
701 : /// considered safe for outlining.
702 : /// Set to true by default for compatibility with llc's -run-pass option.
703 : /// Set when the pass is constructed in TargetPassConfig.
704 : bool RunOnAllFunctions = true;
705 :
706 1126 : StringRef getPassName() const override { return "Machine Outliner"; }
707 :
708 1116 : void getAnalysisUsage(AnalysisUsage &AU) const override {
709 : AU.addRequired<MachineModuleInfo>();
710 : AU.addPreserved<MachineModuleInfo>();
711 : AU.setPreservesAll();
712 1116 : ModulePass::getAnalysisUsage(AU);
713 1116 : }
714 :
715 1130 : MachineOutliner() : ModulePass(ID) {
716 1130 : initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
717 1130 : }
718 :
719 : /// Remark output explaining that not outlining a set of candidates would be
720 : /// better than outlining that set.
721 : void emitNotOutliningCheaperRemark(
722 : unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
723 : OutlinedFunction &OF);
724 :
725 : /// Remark output explaining that a function was outlined.
726 : void emitOutlinedFunctionRemark(OutlinedFunction &OF);
727 :
728 : /// Find all repeated substrings that satisfy the outlining cost model.
729 : ///
730 : /// If a substring appears at least twice, then it must be represented by
731 : /// an internal node which appears in at least two suffixes. Each suffix
732 : /// is represented by a leaf node. To do this, we visit each internal node
733 : /// in the tree, using the leaf children of each internal node. If an
734 : /// internal node represents a beneficial substring, then we use each of
735 : /// its leaf children to find the locations of its substring.
736 : ///
737 : /// \param ST A suffix tree to query.
738 : /// \param Mapper Contains outlining mapping information.
739 : /// \param[out] CandidateList Filled with candidates representing each
740 : /// beneficial substring.
741 : /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
742 : /// each type of candidate.
743 : ///
744 : /// \returns The length of the longest candidate found.
745 : unsigned
746 : findCandidates(SuffixTree &ST,
747 : InstructionMapper &Mapper,
748 : std::vector<std::shared_ptr<Candidate>> &CandidateList,
749 : std::vector<OutlinedFunction> &FunctionList);
750 :
751 : /// Replace the sequences of instructions represented by the
752 : /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
753 : /// described in \p FunctionList.
754 : ///
755 : /// \param M The module we are outlining from.
756 : /// \param CandidateList A list of candidates to be outlined.
757 : /// \param FunctionList A list of functions to be inserted into the module.
758 : /// \param Mapper Contains the instruction mappings for the module.
759 : bool outline(Module &M,
760 : const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
761 : std::vector<OutlinedFunction> &FunctionList,
762 : InstructionMapper &Mapper);
763 :
764 : /// Creates a function for \p OF and inserts it into the module.
765 : MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
766 : InstructionMapper &Mapper);
767 :
768 : /// Find potential outlining candidates and store them in \p CandidateList.
769 : ///
770 : /// For each type of potential candidate, also build an \p OutlinedFunction
771 : /// struct containing the information to build the function for that
772 : /// candidate.
773 : ///
774 : /// \param[out] CandidateList Filled with outlining candidates for the module.
775 : /// \param[out] FunctionList Filled with functions corresponding to each type
776 : /// of \p Candidate.
777 : /// \param ST The suffix tree for the module.
778 : ///
779 : /// \returns The length of the longest candidate found. 0 if there are none.
780 : unsigned
781 : buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
782 : std::vector<OutlinedFunction> &FunctionList,
783 : SuffixTree &ST, InstructionMapper &Mapper);
784 :
785 : /// Helper function for pruneOverlaps.
786 : /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
787 : void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
788 :
789 : /// Remove any overlapping candidates that weren't handled by the
790 : /// suffix tree's pruning method.
791 : ///
792 : /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
793 : /// If a short candidate is chosen for outlining, then a longer candidate
794 : /// which has that short candidate as a suffix is chosen, the tree's pruning
795 : /// method will not find it. Thus, we need to prune before outlining as well.
796 : ///
797 : /// \param[in,out] CandidateList A list of outlining candidates.
798 : /// \param[in,out] FunctionList A list of functions to be outlined.
799 : /// \param Mapper Contains instruction mapping info for outlining.
800 : /// \param MaxCandidateLen The length of the longest candidate.
801 : void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
802 : std::vector<OutlinedFunction> &FunctionList,
803 : InstructionMapper &Mapper, unsigned MaxCandidateLen);
804 :
805 : /// Construct a suffix tree on the instructions in \p M and outline repeated
806 : /// strings from that tree.
807 : bool runOnModule(Module &M) override;
808 :
809 : /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
810 : /// function for remark emission.
811 0 : DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
812 : DISubprogram *SP;
813 0 : for (const std::shared_ptr<Candidate> &C : OF.Candidates)
814 0 : if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram()))
815 0 : return SP;
816 : return nullptr;
817 : }
818 :
819 : /// Populate and \p InstructionMapper with instruction-to-integer mappings.
820 : /// These are used to construct a suffix tree.
821 : void populateMapper(InstructionMapper &Mapper, Module &M,
822 : MachineModuleInfo &MMI);
823 :
824 : /// Initialize information necessary to output a size remark.
825 : /// FIXME: This should be handled by the pass manager, not the outliner.
826 : /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
827 : /// pass manager.
828 : void initSizeRemarkInfo(
829 : const Module &M, const MachineModuleInfo &MMI,
830 : StringMap<unsigned> &FunctionToInstrCount);
831 :
832 : /// Emit the remark.
833 : // FIXME: This should be handled by the pass manager, not the outliner.
834 : void emitInstrCountChangedRemark(
835 : const Module &M, const MachineModuleInfo &MMI,
836 : const StringMap<unsigned> &FunctionToInstrCount);
837 : };
838 : } // Anonymous namespace.
839 :
840 : char MachineOutliner::ID = 0;
841 :
842 : namespace llvm {
843 1121 : ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
844 1121 : MachineOutliner *OL = new MachineOutliner();
845 1121 : OL->RunOnAllFunctions = RunOnAllFunctions;
846 1121 : return OL;
847 : }
848 :
849 : } // namespace llvm
850 :
851 86277 : INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
852 : false)
853 :
854 0 : void MachineOutliner::emitNotOutliningCheaperRemark(
855 : unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
856 : OutlinedFunction &OF) {
857 : Candidate &C = CandidatesForRepeatedSeq.front();
858 0 : MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
859 0 : MORE.emit([&]() {
860 : MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
861 : C.front()->getDebugLoc(), C.getMBB());
862 : R << "Did not outline " << NV("Length", StringLen) << " instructions"
863 : << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
864 : << " locations."
865 : << " Bytes from outlining all occurrences ("
866 : << NV("OutliningCost", OF.getOutliningCost()) << ")"
867 : << " >= Unoutlined instruction bytes ("
868 : << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
869 : << " (Also found at: ";
870 :
871 : // Tell the user the other places the candidate was found.
872 : for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
873 : R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
874 : CandidatesForRepeatedSeq[i].front()->getDebugLoc());
875 : if (i != e - 1)
876 : R << ", ";
877 : }
878 :
879 : R << ")";
880 : return R;
881 : });
882 0 : }
883 :
884 0 : void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
885 0 : MachineBasicBlock *MBB = &*OF.MF->begin();
886 : MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
887 : MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
888 0 : MBB->findDebugLoc(MBB->begin()), MBB);
889 0 : R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
890 0 : << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
891 0 : << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
892 : << " locations. "
893 0 : << "(Found at: ";
894 :
895 : // Tell the user the other places the candidate was found.
896 0 : for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
897 :
898 : // Skip over things that were pruned.
899 0 : if (!OF.Candidates[i]->InCandidateList)
900 0 : continue;
901 :
902 0 : R << NV((Twine("StartLoc") + Twine(i)).str(),
903 0 : OF.Candidates[i]->front()->getDebugLoc());
904 0 : if (i != e - 1)
905 0 : R << ", ";
906 : }
907 :
908 0 : R << ")";
909 :
910 0 : MORE.emit(R);
911 0 : }
912 :
913 0 : unsigned MachineOutliner::findCandidates(
914 : SuffixTree &ST, InstructionMapper &Mapper,
915 : std::vector<std::shared_ptr<Candidate>> &CandidateList,
916 : std::vector<OutlinedFunction> &FunctionList) {
917 : CandidateList.clear();
918 : FunctionList.clear();
919 : unsigned MaxLen = 0;
920 :
921 : // FIXME: Visit internal nodes instead of leaves.
922 0 : for (SuffixTreeNode *Leaf : ST.LeafVector) {
923 : assert(Leaf && "Leaves in LeafVector cannot be null!");
924 0 : if (!Leaf->IsInTree)
925 0 : continue;
926 :
927 : assert(Leaf->Parent && "All leaves must have parents!");
928 0 : SuffixTreeNode &Parent = *(Leaf->Parent);
929 :
930 : // If it doesn't appear enough, or we already outlined from it, skip it.
931 0 : if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
932 0 : continue;
933 :
934 : // Figure out if this candidate is beneficial.
935 0 : unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
936 :
937 : // Too short to be beneficial; skip it.
938 : // FIXME: This isn't necessarily true for, say, X86. If we factor in
939 : // instruction lengths we need more information than this.
940 0 : if (StringLen < 2)
941 0 : continue;
942 :
943 : // If this is a beneficial class of candidate, then every one is stored in
944 : // this vector.
945 0 : std::vector<Candidate> CandidatesForRepeatedSeq;
946 :
947 : // Figure out the call overhead for each instance of the sequence.
948 0 : for (auto &ChildPair : Parent.Children) {
949 0 : SuffixTreeNode *M = ChildPair.second;
950 :
951 0 : if (M && M->IsInTree && M->isLeaf()) {
952 : // Never visit this leaf again.
953 0 : M->IsInTree = false;
954 0 : unsigned StartIdx = M->SuffixIdx;
955 0 : unsigned EndIdx = StartIdx + StringLen - 1;
956 :
957 : // Trick: Discard some candidates that would be incompatible with the
958 : // ones we've already found for this sequence. This will save us some
959 : // work in candidate selection.
960 : //
961 : // If two candidates overlap, then we can't outline them both. This
962 : // happens when we have candidates that look like, say
963 : //
964 : // AA (where each "A" is an instruction).
965 : //
966 : // We might have some portion of the module that looks like this:
967 : // AAAAAA (6 A's)
968 : //
969 : // In this case, there are 5 different copies of "AA" in this range, but
970 : // at most 3 can be outlined. If only outlining 3 of these is going to
971 : // be unbeneficial, then we ought to not bother.
972 : //
973 : // Note that two things DON'T overlap when they look like this:
974 : // start1...end1 .... start2...end2
975 : // That is, one must either
976 : // * End before the other starts
977 : // * Start after the other ends
978 0 : if (std::all_of(CandidatesForRepeatedSeq.begin(),
979 : CandidatesForRepeatedSeq.end(),
980 : [&StartIdx, &EndIdx](const Candidate &C) {
981 0 : return (EndIdx < C.getStartIdx() ||
982 0 : StartIdx > C.getEndIdx());
983 : })) {
984 : // It doesn't overlap with anything, so we can outline it.
985 : // Each sequence is over [StartIt, EndIt].
986 : // Save the candidate and its location.
987 :
988 0 : MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
989 0 : MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
990 :
991 0 : CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
992 0 : EndIt, StartIt->getParent(),
993 0 : FunctionList.size());
994 : }
995 : }
996 : }
997 :
998 : // We've found something we might want to outline.
999 : // Create an OutlinedFunction to store it and check if it'd be beneficial
1000 : // to outline.
1001 0 : if (CandidatesForRepeatedSeq.empty())
1002 0 : continue;
1003 :
1004 : // Arbitrarily choose a TII from the first candidate.
1005 : // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
1006 : const TargetInstrInfo *TII =
1007 0 : CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
1008 :
1009 : OutlinedFunction OF =
1010 0 : TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
1011 :
1012 : // If we deleted every candidate, then there's nothing to outline.
1013 0 : if (OF.Candidates.empty())
1014 0 : continue;
1015 :
1016 : std::vector<unsigned> Seq;
1017 0 : for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
1018 0 : Seq.push_back(ST.Str[i]);
1019 0 : OF.Sequence = Seq;
1020 0 : OF.Name = FunctionList.size();
1021 :
1022 : // Is it better to outline this candidate than not?
1023 0 : if (OF.getBenefit() < 1) {
1024 0 : emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
1025 : continue;
1026 : }
1027 :
1028 0 : if (StringLen > MaxLen)
1029 : MaxLen = StringLen;
1030 :
1031 : // The function is beneficial. Save its candidates to the candidate list
1032 : // for pruning.
1033 0 : for (std::shared_ptr<Candidate> &C : OF.Candidates)
1034 0 : CandidateList.push_back(C);
1035 0 : FunctionList.push_back(OF);
1036 :
1037 : // Move to the next function.
1038 0 : Parent.IsInTree = false;
1039 : }
1040 :
1041 0 : return MaxLen;
1042 : }
1043 :
1044 : // Remove C from the candidate space, and update its OutlinedFunction.
1045 0 : void MachineOutliner::prune(Candidate &C,
1046 : std::vector<OutlinedFunction> &FunctionList) {
1047 : // Get the OutlinedFunction associated with this Candidate.
1048 0 : OutlinedFunction &F = FunctionList[C.FunctionIdx];
1049 :
1050 : // Update C's associated function's occurrence count.
1051 : F.decrement();
1052 :
1053 : // Remove C from the CandidateList.
1054 0 : C.InCandidateList = false;
1055 :
1056 : LLVM_DEBUG(dbgs() << "- Removed a Candidate \n";
1057 : dbgs() << "--- Num fns left for candidate: "
1058 : << F.getOccurrenceCount() << "\n";
1059 : dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
1060 : << "\n";);
1061 0 : }
1062 :
1063 0 : void MachineOutliner::pruneOverlaps(
1064 : std::vector<std::shared_ptr<Candidate>> &CandidateList,
1065 : std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
1066 : unsigned MaxCandidateLen) {
1067 :
1068 : // Return true if this candidate became unbeneficial for outlining in a
1069 : // previous step.
1070 : auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
1071 :
1072 : // Check if the candidate was removed in a previous step.
1073 : if (!C.InCandidateList)
1074 : return true;
1075 :
1076 : // C must be alive. Check if we should remove it.
1077 : if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
1078 : prune(C, FunctionList);
1079 : return true;
1080 : }
1081 :
1082 : // C is in the list, and F is still beneficial.
1083 : return false;
1084 0 : };
1085 :
1086 : // TODO: Experiment with interval trees or other interval-checking structures
1087 : // to lower the time complexity of this function.
1088 : // TODO: Can we do better than the simple greedy choice?
1089 : // Check for overlaps in the range.
1090 : // This is O(MaxCandidateLen * CandidateList.size()).
1091 0 : for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
1092 : It++) {
1093 : Candidate &C1 = **It;
1094 :
1095 : // If C1 was already pruned, or its function is no longer beneficial for
1096 : // outlining, move to the next candidate.
1097 0 : if (ShouldSkipCandidate(C1))
1098 0 : continue;
1099 :
1100 : // The minimum start index of any candidate that could overlap with this
1101 : // one.
1102 : unsigned FarthestPossibleIdx = 0;
1103 :
1104 : // Either the index is 0, or it's at most MaxCandidateLen indices away.
1105 0 : if (C1.getStartIdx() > MaxCandidateLen)
1106 0 : FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
1107 :
1108 : // Compare against the candidates in the list that start at most
1109 : // FarthestPossibleIdx indices away from C1. There are at most
1110 : // MaxCandidateLen of these.
1111 0 : for (auto Sit = It + 1; Sit != Et; Sit++) {
1112 : Candidate &C2 = **Sit;
1113 :
1114 : // Is this candidate too far away to overlap?
1115 0 : if (C2.getStartIdx() < FarthestPossibleIdx)
1116 : break;
1117 :
1118 : // If C2 was already pruned, or its function is no longer beneficial for
1119 : // outlining, move to the next candidate.
1120 0 : if (ShouldSkipCandidate(C2))
1121 0 : continue;
1122 :
1123 : // Do C1 and C2 overlap?
1124 : //
1125 : // Not overlapping:
1126 : // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
1127 : //
1128 : // We sorted our candidate list so C2Start <= C1Start. We know that
1129 : // C2End > C2Start since each candidate has length >= 2. Therefore, all we
1130 : // have to check is C2End < C2Start to see if we overlap.
1131 0 : if (C2.getEndIdx() < C1.getStartIdx())
1132 0 : continue;
1133 :
1134 : // C1 and C2 overlap.
1135 : // We need to choose the better of the two.
1136 : //
1137 : // Approximate this by picking the one which would have saved us the
1138 : // most instructions before any pruning.
1139 :
1140 : // Is C2 a better candidate?
1141 0 : if (C2.Benefit > C1.Benefit) {
1142 : // Yes, so prune C1. Since C1 is dead, we don't have to compare it
1143 : // against anything anymore, so break.
1144 0 : prune(C1, FunctionList);
1145 : break;
1146 : }
1147 :
1148 : // Prune C2 and move on to the next candidate.
1149 0 : prune(C2, FunctionList);
1150 : }
1151 : }
1152 0 : }
1153 :
1154 0 : unsigned MachineOutliner::buildCandidateList(
1155 : std::vector<std::shared_ptr<Candidate>> &CandidateList,
1156 : std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
1157 : InstructionMapper &Mapper) {
1158 :
1159 : std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1160 : unsigned MaxCandidateLen = 0; // Length of the longest candidate.
1161 :
1162 : MaxCandidateLen =
1163 0 : findCandidates(ST, Mapper, CandidateList, FunctionList);
1164 :
1165 : // Sort the candidates in decending order. This will simplify the outlining
1166 : // process when we have to remove the candidates from the mapping by
1167 : // allowing us to cut them out without keeping track of an offset.
1168 0 : std::stable_sort(
1169 : CandidateList.begin(), CandidateList.end(),
1170 : [](const std::shared_ptr<Candidate> &LHS,
1171 : const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
1172 :
1173 0 : return MaxCandidateLen;
1174 : }
1175 :
1176 : MachineFunction *
1177 33 : MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1178 : InstructionMapper &Mapper) {
1179 :
1180 : // Create the function name. This should be unique. For now, just hash the
1181 : // module name and include it in the function name plus the number of this
1182 : // function.
1183 66 : std::ostringstream NameStream;
1184 33 : NameStream << "OUTLINED_FUNCTION_" << OF.Name;
1185 :
1186 : // Create the function using an IR-level function.
1187 33 : LLVMContext &C = M.getContext();
1188 66 : Function *F = dyn_cast<Function>(
1189 33 : M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1190 : assert(F && "Function was null!");
1191 :
1192 : // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1193 : // which gives us better results when we outline from linkonceodr functions.
1194 : F->setLinkage(GlobalValue::InternalLinkage);
1195 : F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1196 :
1197 : // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's
1198 : // necessary.
1199 :
1200 : // Set optsize/minsize, so we don't insert padding between outlined
1201 : // functions.
1202 : F->addFnAttr(Attribute::OptimizeForSize);
1203 : F->addFnAttr(Attribute::MinSize);
1204 :
1205 33 : BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1206 : IRBuilder<> Builder(EntryBB);
1207 33 : Builder.CreateRetVoid();
1208 :
1209 33 : MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1210 33 : MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
1211 33 : MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1212 33 : const TargetSubtargetInfo &STI = MF.getSubtarget();
1213 33 : const TargetInstrInfo &TII = *STI.getInstrInfo();
1214 :
1215 : // Insert the new function into the module.
1216 : MF.insert(MF.begin(), &MBB);
1217 :
1218 : // Copy over the instructions for the function using the integer mappings in
1219 : // its sequence.
1220 228 : for (unsigned Str : OF.Sequence) {
1221 : MachineInstr *NewMI =
1222 195 : MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1223 195 : NewMI->dropMemRefs(MF);
1224 :
1225 : // Don't keep debug information for outlined instructions.
1226 390 : NewMI->setDebugLoc(DebugLoc());
1227 : MBB.insert(MBB.end(), NewMI);
1228 : }
1229 :
1230 33 : TII.buildOutlinedFrame(MBB, MF, OF);
1231 :
1232 : // Outlined functions shouldn't preserve liveness.
1233 : MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness);
1234 33 : MF.getRegInfo().freezeReservedRegs(MF);
1235 :
1236 : // If there's a DISubprogram associated with this outlined function, then
1237 : // emit debug info for the outlined function.
1238 33 : if (DISubprogram *SP = getSubprogramOrNull(OF)) {
1239 : // We have a DISubprogram. Get its DICompileUnit.
1240 : DICompileUnit *CU = SP->getUnit();
1241 12 : DIBuilder DB(M, true, CU);
1242 : DIFile *Unit = SP->getFile();
1243 : Mangler Mg;
1244 : // Get the mangled name of the function for the linkage name.
1245 : std::string Dummy;
1246 6 : llvm::raw_string_ostream MangledNameStream(Dummy);
1247 6 : Mg.getNameWithPrefix(MangledNameStream, F, false);
1248 :
1249 12 : DISubprogram *OutlinedSP = DB.createFunction(
1250 : Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
1251 : Unit /* File */,
1252 : 0 /* Line 0 is reserved for compiler-generated code. */,
1253 : DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
1254 : false, true, 0, /* Line 0 is reserved for compiler-generated code. */
1255 : DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
1256 : true /* Outlined code is optimized code by definition. */);
1257 :
1258 : // Don't add any new variables to the subprogram.
1259 6 : DB.finalizeSubprogram(OutlinedSP);
1260 :
1261 : // Attach subprogram to the function.
1262 6 : F->setSubprogram(OutlinedSP);
1263 : // We're done with the DIBuilder.
1264 6 : DB.finalize();
1265 : }
1266 :
1267 33 : return &MF;
1268 : }
1269 :
1270 1098 : bool MachineOutliner::outline(
1271 : Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
1272 : std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
1273 :
1274 : bool OutlinedSomething = false;
1275 : // Replace the candidates with calls to their respective outlined functions.
1276 1353 : for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
1277 : Candidate &C = *Cptr;
1278 : // Was the candidate removed during pruneOverlaps?
1279 255 : if (!C.InCandidateList)
1280 164 : continue;
1281 :
1282 : // If not, then look at its OutlinedFunction.
1283 91 : OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1284 :
1285 : // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1286 91 : if (OF.getBenefit() < 1)
1287 : continue;
1288 :
1289 : // Does this candidate have a function yet?
1290 91 : if (!OF.MF) {
1291 33 : OF.MF = createOutlinedFunction(M, OF, Mapper);
1292 33 : emitOutlinedFunctionRemark(OF);
1293 : FunctionsCreated++;
1294 : }
1295 :
1296 91 : MachineFunction *MF = OF.MF;
1297 91 : MachineBasicBlock &MBB = *C.getMBB();
1298 91 : MachineBasicBlock::iterator StartIt = C.front();
1299 91 : MachineBasicBlock::iterator EndIt = C.back();
1300 : assert(StartIt != C.getMBB()->end() && "StartIt out of bounds!");
1301 : assert(EndIt != C.getMBB()->end() && "EndIt out of bounds!");
1302 :
1303 91 : const TargetSubtargetInfo &STI = MF->getSubtarget();
1304 91 : const TargetInstrInfo &TII = *STI.getInstrInfo();
1305 :
1306 : // Insert a call to the new function and erase the old sequence.
1307 91 : auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.MF, C);
1308 :
1309 : // If the caller tracks liveness, then we need to make sure that anything
1310 : // we outline doesn't break liveness assumptions.
1311 : // The outlined functions themselves currently don't track liveness, but
1312 : // we should make sure that the ranges we yank things out of aren't
1313 : // wrong.
1314 182 : if (MBB.getParent()->getProperties().hasProperty(
1315 : MachineFunctionProperties::Property::TracksLiveness)) {
1316 : // Helper lambda for adding implicit def operands to the call instruction.
1317 : auto CopyDefs = [&CallInst](MachineInstr &MI) {
1318 : for (MachineOperand &MOP : MI.operands()) {
1319 : // Skip over anything that isn't a register.
1320 : if (!MOP.isReg())
1321 : continue;
1322 :
1323 : // If it's a def, add it to the call instruction.
1324 : if (MOP.isDef())
1325 : CallInst->addOperand(
1326 : MachineOperand::CreateReg(MOP.getReg(), true, /* isDef = true */
1327 : true /* isImp = true */));
1328 : }
1329 91 : };
1330 :
1331 : // Copy over the defs in the outlined range.
1332 : // First inst in outlined range <-- Anything that's defined in this
1333 : // ... .. range has to be added as an implicit
1334 : // Last inst in outlined range <-- def to the call instruction.
1335 91 : std::for_each(CallInst, std::next(EndIt), CopyDefs);
1336 : }
1337 :
1338 : // Erase from the point after where the call was inserted up to, and
1339 : // including, the final instruction in the sequence.
1340 : // Erase needs one past the end, so we need std::next there too.
1341 91 : MBB.erase(std::next(StartIt), std::next(EndIt));
1342 : OutlinedSomething = true;
1343 :
1344 : // Statistics.
1345 : NumOutlined++;
1346 : }
1347 :
1348 : LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1349 :
1350 1098 : return OutlinedSomething;
1351 : }
1352 :
1353 0 : void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
1354 : MachineModuleInfo &MMI) {
1355 : // Build instruction mappings for each function in the module. Start by
1356 : // iterating over each Function in M.
1357 0 : for (Function &F : M) {
1358 :
1359 : // If there's nothing in F, then there's no reason to try and outline from
1360 : // it.
1361 0 : if (F.empty())
1362 0 : continue;
1363 :
1364 : // There's something in F. Check if it has a MachineFunction associated with
1365 : // it.
1366 0 : MachineFunction *MF = MMI.getMachineFunction(F);
1367 :
1368 : // If it doesn't, then there's nothing to outline from. Move to the next
1369 : // Function.
1370 0 : if (!MF)
1371 0 : continue;
1372 :
1373 0 : const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1374 :
1375 0 : if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
1376 0 : continue;
1377 :
1378 : // We have a MachineFunction. Ask the target if it's suitable for outlining.
1379 : // If it isn't, then move on to the next Function in the module.
1380 0 : if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
1381 0 : continue;
1382 :
1383 : // We have a function suitable for outlining. Iterate over every
1384 : // MachineBasicBlock in MF and try to map its instructions to a list of
1385 : // unsigned integers.
1386 0 : for (MachineBasicBlock &MBB : *MF) {
1387 : // If there isn't anything in MBB, then there's no point in outlining from
1388 : // it.
1389 : // If there are fewer than 2 instructions in the MBB, then it can't ever
1390 : // contain something worth outlining.
1391 : // FIXME: This should be based off of the maximum size in B of an outlined
1392 : // call versus the size in B of the MBB.
1393 0 : if (MBB.empty() || MBB.size() < 2)
1394 0 : continue;
1395 :
1396 : // Check if MBB could be the target of an indirect branch. If it is, then
1397 : // we don't want to outline from it.
1398 0 : if (MBB.hasAddressTaken())
1399 0 : continue;
1400 :
1401 : // MBB is suitable for outlining. Map it to a list of unsigneds.
1402 0 : Mapper.convertToUnsignedVec(MBB, *TII);
1403 : }
1404 : }
1405 0 : }
1406 :
1407 0 : void MachineOutliner::initSizeRemarkInfo(
1408 : const Module &M, const MachineModuleInfo &MMI,
1409 : StringMap<unsigned> &FunctionToInstrCount) {
1410 : // Collect instruction counts for every function. We'll use this to emit
1411 : // per-function size remarks later.
1412 0 : for (const Function &F : M) {
1413 0 : MachineFunction *MF = MMI.getMachineFunction(F);
1414 :
1415 : // We only care about MI counts here. If there's no MachineFunction at this
1416 : // point, then there won't be after the outliner runs, so let's move on.
1417 0 : if (!MF)
1418 0 : continue;
1419 0 : FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
1420 : }
1421 0 : }
1422 :
1423 0 : void MachineOutliner::emitInstrCountChangedRemark(
1424 : const Module &M, const MachineModuleInfo &MMI,
1425 : const StringMap<unsigned> &FunctionToInstrCount) {
1426 : // Iterate over each function in the module and emit remarks.
1427 : // Note that we won't miss anything by doing this, because the outliner never
1428 : // deletes functions.
1429 0 : for (const Function &F : M) {
1430 0 : MachineFunction *MF = MMI.getMachineFunction(F);
1431 :
1432 : // The outliner never deletes functions. If we don't have a MF here, then we
1433 : // didn't have one prior to outlining either.
1434 0 : if (!MF)
1435 0 : continue;
1436 :
1437 0 : std::string Fname = F.getName();
1438 0 : unsigned FnCountAfter = MF->getInstructionCount();
1439 0 : unsigned FnCountBefore = 0;
1440 :
1441 : // Check if the function was recorded before.
1442 0 : auto It = FunctionToInstrCount.find(Fname);
1443 :
1444 : // Did we have a previously-recorded size? If yes, then set FnCountBefore
1445 : // to that.
1446 0 : if (It != FunctionToInstrCount.end())
1447 0 : FnCountBefore = It->second;
1448 :
1449 : // Compute the delta and emit a remark if there was a change.
1450 0 : int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
1451 0 : static_cast<int64_t>(FnCountBefore);
1452 0 : if (FnDelta == 0)
1453 : continue;
1454 :
1455 0 : MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
1456 0 : MORE.emit([&]() {
1457 : MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
1458 : DiagnosticLocation(),
1459 : &MF->front());
1460 : R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
1461 : << ": Function: "
1462 : << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
1463 : << ": MI instruction count changed from "
1464 : << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
1465 : FnCountBefore)
1466 : << " to "
1467 : << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
1468 : FnCountAfter)
1469 : << "; Delta: "
1470 : << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
1471 : return R;
1472 : });
1473 : }
1474 0 : }
1475 :
1476 1107 : bool MachineOutliner::runOnModule(Module &M) {
1477 : // Check if there's anything in the module. If it's empty, then there's
1478 : // nothing to outline.
1479 1107 : if (M.empty())
1480 : return false;
1481 :
1482 1098 : MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1483 :
1484 : // If the user passed -enable-machine-outliner=always or
1485 : // -enable-machine-outliner, the pass will run on all functions in the module.
1486 : // Otherwise, if the target supports default outlining, it will run on all
1487 : // functions deemed by the target to be worth outlining from by default. Tell
1488 : // the user how the outliner is running.
1489 : LLVM_DEBUG(
1490 : dbgs() << "Machine Outliner: Running on ";
1491 : if (RunOnAllFunctions)
1492 : dbgs() << "all functions";
1493 : else
1494 : dbgs() << "target-default functions";
1495 : dbgs() << "\n"
1496 : );
1497 :
1498 : // If the user specifies that they want to outline from linkonceodrs, set
1499 : // it here.
1500 1098 : OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1501 2196 : InstructionMapper Mapper;
1502 :
1503 : // Prepare instruction mappings for the suffix tree.
1504 1098 : populateMapper(Mapper, M, MMI);
1505 :
1506 : // Construct a suffix tree, use it to find candidates, and then outline them.
1507 2196 : SuffixTree ST(Mapper.UnsignedVec);
1508 1098 : std::vector<std::shared_ptr<Candidate>> CandidateList;
1509 1098 : std::vector<OutlinedFunction> FunctionList;
1510 :
1511 : // Find all of the outlining candidates.
1512 : unsigned MaxCandidateLen =
1513 1098 : buildCandidateList(CandidateList, FunctionList, ST, Mapper);
1514 :
1515 : // Remove candidates that overlap with other candidates.
1516 1098 : pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen);
1517 :
1518 : // If we've requested size remarks, then collect the MI counts of every
1519 : // function before outlining, and the MI counts after outlining.
1520 : // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1521 : // the pass manager's responsibility.
1522 : // This could pretty easily be placed in outline instead, but because we
1523 : // really ultimately *don't* want this here, it's done like this for now
1524 : // instead.
1525 :
1526 : // Check if we want size remarks.
1527 1098 : bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1528 1098 : StringMap<unsigned> FunctionToInstrCount;
1529 1098 : if (ShouldEmitSizeRemarks)
1530 1 : initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1531 :
1532 : // Outline each of the candidates and return true if something was outlined.
1533 1098 : bool OutlinedSomething = outline(M, CandidateList, FunctionList, Mapper);
1534 :
1535 : // If we outlined something, we definitely changed the MI count of the
1536 : // module. If we've asked for size remarks, then output them.
1537 : // FIXME: This should be in the pass manager.
1538 1098 : if (ShouldEmitSizeRemarks && OutlinedSomething)
1539 1 : emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1540 :
1541 : return OutlinedSomething;
1542 : }
|
