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