1 | //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// |
9 | /// \file |
10 | /// Replaces repeated sequences of instructions with function calls. |
11 | /// |
12 | /// This works by placing every instruction from every basic block in a |
13 | /// suffix tree, and repeatedly querying that tree for repeated sequences of |
14 | /// instructions. If a sequence of instructions appears often, then it ought |
15 | /// to be beneficial to pull out into a function. |
16 | /// |
17 | /// The MachineOutliner communicates with a given target using hooks defined in |
18 | /// TargetInstrInfo.h. The target supplies the outliner with information on how |
19 | /// a specific sequence of instructions should be outlined. This information |
20 | /// is used to deduce the number of instructions necessary to |
21 | /// |
22 | /// * Create an outlined function |
23 | /// * Call that outlined function |
24 | /// |
25 | /// Targets must implement |
26 | /// * getOutliningCandidateInfo |
27 | /// * buildOutlinedFrame |
28 | /// * insertOutlinedCall |
29 | /// * isFunctionSafeToOutlineFrom |
30 | /// |
31 | /// in order to make use of the MachineOutliner. |
32 | /// |
33 | /// This was originally presented at the 2016 LLVM Developers' Meeting in the |
34 | /// talk "Reducing Code Size Using Outlining". For a high-level overview of |
35 | /// how this pass works, the talk is available on YouTube at |
36 | /// |
37 | /// https://www.youtube.com/watch?v=yorld-WSOeU |
38 | /// |
39 | /// The slides for the talk are available at |
40 | /// |
41 | /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf |
42 | /// |
43 | /// The talk provides an overview of how the outliner finds candidates and |
44 | /// ultimately outlines them. It describes how the main data structure for this |
45 | /// pass, the suffix tree, is queried and purged for candidates. It also gives |
46 | /// a simplified suffix tree construction algorithm for suffix trees based off |
47 | /// of the algorithm actually used here, Ukkonen's algorithm. |
48 | /// |
49 | /// For the original RFC for this pass, please see |
50 | /// |
51 | /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html |
52 | /// |
53 | /// For more information on the suffix tree data structure, please see |
54 | /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf |
55 | /// |
56 | //===----------------------------------------------------------------------===// |
57 | #include "llvm/CodeGen/MachineOutliner.h" |
58 | #include "llvm/ADT/DenseMap.h" |
59 | #include "llvm/ADT/SmallSet.h" |
60 | #include "llvm/ADT/Statistic.h" |
61 | #include "llvm/ADT/Twine.h" |
62 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
63 | #include "llvm/CodeGen/LivePhysRegs.h" |
64 | #include "llvm/CodeGen/MachineModuleInfo.h" |
65 | #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.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/InitializePasses.h" |
73 | #include "llvm/Support/CommandLine.h" |
74 | #include "llvm/Support/Debug.h" |
75 | #include "llvm/Support/SuffixTree.h" |
76 | #include "llvm/Support/raw_ostream.h" |
77 | #include <functional> |
78 | #include <tuple> |
79 | #include <vector> |
80 | |
81 | #define DEBUG_TYPE "machine-outliner" |
82 | |
83 | using namespace llvm; |
84 | using namespace ore; |
85 | using namespace outliner; |
86 | |
87 | // Statistics for outlined functions. |
88 | STATISTIC(NumOutlined, "Number of candidates outlined" ); |
89 | STATISTIC(FunctionsCreated, "Number of functions created" ); |
90 | |
91 | // Statistics for instruction mapping. |
92 | STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped" ); |
93 | STATISTIC(NumIllegalInUnsignedVec, |
94 | "Unoutlinable instructions mapped + number of sentinel values" ); |
95 | STATISTIC(NumSentinels, "Sentinel values inserted during mapping" ); |
96 | STATISTIC(NumInvisible, |
97 | "Invisible instructions skipped during mapping" ); |
98 | STATISTIC(UnsignedVecSize, |
99 | "Total number of instructions mapped and saved to mapping vector" ); |
100 | |
101 | // Set to true if the user wants the outliner to run on linkonceodr linkage |
102 | // functions. This is false by default because the linker can dedupe linkonceodr |
103 | // functions. Since the outliner is confined to a single module (modulo LTO), |
104 | // this is off by default. It should, however, be the default behaviour in |
105 | // LTO. |
106 | static cl::opt<bool> EnableLinkOnceODROutlining( |
107 | "enable-linkonceodr-outlining" , cl::Hidden, |
108 | cl::desc("Enable the machine outliner on linkonceodr functions" ), |
109 | cl::init(Val: false)); |
110 | |
111 | /// Number of times to re-run the outliner. This is not the total number of runs |
112 | /// as the outliner will run at least one time. The default value is set to 0, |
113 | /// meaning the outliner will run one time and rerun zero times after that. |
114 | static cl::opt<unsigned> OutlinerReruns( |
115 | "machine-outliner-reruns" , cl::init(Val: 0), cl::Hidden, |
116 | cl::desc( |
117 | "Number of times to rerun the outliner after the initial outline" )); |
118 | |
119 | static cl::opt<unsigned> OutlinerBenefitThreshold( |
120 | "outliner-benefit-threshold" , cl::init(Val: 1), cl::Hidden, |
121 | cl::desc( |
122 | "The minimum size in bytes before an outlining candidate is accepted" )); |
123 | |
124 | namespace { |
125 | |
126 | /// Maps \p MachineInstrs to unsigned integers and stores the mappings. |
127 | struct InstructionMapper { |
128 | |
129 | /// The next available integer to assign to a \p MachineInstr that |
130 | /// cannot be outlined. |
131 | /// |
132 | /// Set to -3 for compatability with \p DenseMapInfo<unsigned>. |
133 | unsigned IllegalInstrNumber = -3; |
134 | |
135 | /// The next available integer to assign to a \p MachineInstr that can |
136 | /// be outlined. |
137 | unsigned LegalInstrNumber = 0; |
138 | |
139 | /// Correspondence from \p MachineInstrs to unsigned integers. |
140 | DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait> |
141 | InstructionIntegerMap; |
142 | |
143 | /// Correspondence between \p MachineBasicBlocks and target-defined flags. |
144 | DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap; |
145 | |
146 | /// The vector of unsigned integers that the module is mapped to. |
147 | SmallVector<unsigned> UnsignedVec; |
148 | |
149 | /// Stores the location of the instruction associated with the integer |
150 | /// at index i in \p UnsignedVec for each index i. |
151 | SmallVector<MachineBasicBlock::iterator> InstrList; |
152 | |
153 | // Set if we added an illegal number in the previous step. |
154 | // Since each illegal number is unique, we only need one of them between |
155 | // each range of legal numbers. This lets us make sure we don't add more |
156 | // than one illegal number per range. |
157 | bool AddedIllegalLastTime = false; |
158 | |
159 | /// Maps \p *It to a legal integer. |
160 | /// |
161 | /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB, |
162 | /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber. |
163 | /// |
164 | /// \returns The integer that \p *It was mapped to. |
165 | unsigned mapToLegalUnsigned( |
166 | MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
167 | bool &HaveLegalRange, unsigned &NumLegalInBlock, |
168 | SmallVector<unsigned> &UnsignedVecForMBB, |
169 | SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { |
170 | // We added something legal, so we should unset the AddedLegalLastTime |
171 | // flag. |
172 | AddedIllegalLastTime = false; |
173 | |
174 | // If we have at least two adjacent legal instructions (which may have |
175 | // invisible instructions in between), remember that. |
176 | if (CanOutlineWithPrevInstr) |
177 | HaveLegalRange = true; |
178 | CanOutlineWithPrevInstr = true; |
179 | |
180 | // Keep track of the number of legal instructions we insert. |
181 | NumLegalInBlock++; |
182 | |
183 | // Get the integer for this instruction or give it the current |
184 | // LegalInstrNumber. |
185 | InstrListForMBB.push_back(Elt: It); |
186 | MachineInstr &MI = *It; |
187 | bool WasInserted; |
188 | DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator |
189 | ResultIt; |
190 | std::tie(args&: ResultIt, args&: WasInserted) = |
191 | InstructionIntegerMap.insert(KV: std::make_pair(x: &MI, y&: LegalInstrNumber)); |
192 | unsigned MINumber = ResultIt->second; |
193 | |
194 | // There was an insertion. |
195 | if (WasInserted) |
196 | LegalInstrNumber++; |
197 | |
198 | UnsignedVecForMBB.push_back(Elt: MINumber); |
199 | |
200 | // Make sure we don't overflow or use any integers reserved by the DenseMap. |
201 | if (LegalInstrNumber >= IllegalInstrNumber) |
202 | report_fatal_error(reason: "Instruction mapping overflow!" ); |
203 | |
204 | assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() && |
205 | "Tried to assign DenseMap tombstone or empty key to instruction." ); |
206 | assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() && |
207 | "Tried to assign DenseMap tombstone or empty key to instruction." ); |
208 | |
209 | // Statistics. |
210 | ++NumLegalInUnsignedVec; |
211 | return MINumber; |
212 | } |
213 | |
214 | /// Maps \p *It to an illegal integer. |
215 | /// |
216 | /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p |
217 | /// IllegalInstrNumber. |
218 | /// |
219 | /// \returns The integer that \p *It was mapped to. |
220 | unsigned mapToIllegalUnsigned( |
221 | MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
222 | SmallVector<unsigned> &UnsignedVecForMBB, |
223 | SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { |
224 | // Can't outline an illegal instruction. Set the flag. |
225 | CanOutlineWithPrevInstr = false; |
226 | |
227 | // Only add one illegal number per range of legal numbers. |
228 | if (AddedIllegalLastTime) |
229 | return IllegalInstrNumber; |
230 | |
231 | // Remember that we added an illegal number last time. |
232 | AddedIllegalLastTime = true; |
233 | unsigned MINumber = IllegalInstrNumber; |
234 | |
235 | InstrListForMBB.push_back(Elt: It); |
236 | UnsignedVecForMBB.push_back(Elt: IllegalInstrNumber); |
237 | IllegalInstrNumber--; |
238 | // Statistics. |
239 | ++NumIllegalInUnsignedVec; |
240 | |
241 | assert(LegalInstrNumber < IllegalInstrNumber && |
242 | "Instruction mapping overflow!" ); |
243 | |
244 | assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() && |
245 | "IllegalInstrNumber cannot be DenseMap tombstone or empty key!" ); |
246 | |
247 | assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() && |
248 | "IllegalInstrNumber cannot be DenseMap tombstone or empty key!" ); |
249 | |
250 | return MINumber; |
251 | } |
252 | |
253 | /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds |
254 | /// and appends it to \p UnsignedVec and \p InstrList. |
255 | /// |
256 | /// Two instructions are assigned the same integer if they are identical. |
257 | /// If an instruction is deemed unsafe to outline, then it will be assigned an |
258 | /// unique integer. The resulting mapping is placed into a suffix tree and |
259 | /// queried for candidates. |
260 | /// |
261 | /// \param MBB The \p MachineBasicBlock to be translated into integers. |
262 | /// \param TII \p TargetInstrInfo for the function. |
263 | void convertToUnsignedVec(MachineBasicBlock &MBB, |
264 | const TargetInstrInfo &TII) { |
265 | LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName() |
266 | << "' to unsigned vector ***\n" ); |
267 | unsigned Flags = 0; |
268 | |
269 | // Don't even map in this case. |
270 | if (!TII.isMBBSafeToOutlineFrom(MBB, Flags)) |
271 | return; |
272 | |
273 | auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags); |
274 | LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size() |
275 | << " outlinable range(s)\n" ); |
276 | if (OutlinableRanges.empty()) |
277 | return; |
278 | |
279 | // Store info for the MBB for later outlining. |
280 | MBBFlagsMap[&MBB] = Flags; |
281 | |
282 | MachineBasicBlock::iterator It = MBB.begin(); |
283 | |
284 | // The number of instructions in this block that will be considered for |
285 | // outlining. |
286 | unsigned NumLegalInBlock = 0; |
287 | |
288 | // True if we have at least two legal instructions which aren't separated |
289 | // by an illegal instruction. |
290 | bool HaveLegalRange = false; |
291 | |
292 | // True if we can perform outlining given the last mapped (non-invisible) |
293 | // instruction. This lets us know if we have a legal range. |
294 | bool CanOutlineWithPrevInstr = false; |
295 | |
296 | // FIXME: Should this all just be handled in the target, rather than using |
297 | // repeated calls to getOutliningType? |
298 | SmallVector<unsigned> UnsignedVecForMBB; |
299 | SmallVector<MachineBasicBlock::iterator> InstrListForMBB; |
300 | |
301 | LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n" ); |
302 | for (auto &OutlinableRange : OutlinableRanges) { |
303 | auto OutlinableRangeBegin = OutlinableRange.first; |
304 | auto OutlinableRangeEnd = OutlinableRange.second; |
305 | #ifndef NDEBUG |
306 | LLVM_DEBUG( |
307 | dbgs() << "Mapping " |
308 | << std::distance(OutlinableRangeBegin, OutlinableRangeEnd) |
309 | << " instruction range\n" ); |
310 | // Everything outside of an outlinable range is illegal. |
311 | unsigned NumSkippedInRange = 0; |
312 | #endif |
313 | for (; It != OutlinableRangeBegin; ++It) { |
314 | #ifndef NDEBUG |
315 | ++NumSkippedInRange; |
316 | #endif |
317 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
318 | InstrListForMBB); |
319 | } |
320 | #ifndef NDEBUG |
321 | LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange |
322 | << " instructions outside outlinable range\n" ); |
323 | #endif |
324 | assert(It != MBB.end() && "Should still have instructions?" ); |
325 | // `It` is now positioned at the beginning of a range of instructions |
326 | // which may be outlinable. Check if each instruction is known to be safe. |
327 | for (; It != OutlinableRangeEnd; ++It) { |
328 | // Keep track of where this instruction is in the module. |
329 | switch (TII.getOutliningType(MIT&: It, Flags)) { |
330 | case InstrType::Illegal: |
331 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
332 | InstrListForMBB); |
333 | break; |
334 | |
335 | case InstrType::Legal: |
336 | mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
337 | NumLegalInBlock, UnsignedVecForMBB, |
338 | InstrListForMBB); |
339 | break; |
340 | |
341 | case InstrType::LegalTerminator: |
342 | mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
343 | NumLegalInBlock, UnsignedVecForMBB, |
344 | InstrListForMBB); |
345 | // The instruction also acts as a terminator, so we have to record |
346 | // that in the string. |
347 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
348 | InstrListForMBB); |
349 | break; |
350 | |
351 | case InstrType::Invisible: |
352 | // Normally this is set by mapTo(Blah)Unsigned, but we just want to |
353 | // skip this instruction. So, unset the flag here. |
354 | ++NumInvisible; |
355 | AddedIllegalLastTime = false; |
356 | break; |
357 | } |
358 | } |
359 | } |
360 | |
361 | LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n" ); |
362 | |
363 | // Are there enough legal instructions in the block for outlining to be |
364 | // possible? |
365 | if (HaveLegalRange) { |
366 | // After we're done every insertion, uniquely terminate this part of the |
367 | // "string". This makes sure we won't match across basic block or function |
368 | // boundaries since the "end" is encoded uniquely and thus appears in no |
369 | // repeated substring. |
370 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
371 | InstrListForMBB); |
372 | ++NumSentinels; |
373 | append_range(C&: InstrList, R&: InstrListForMBB); |
374 | append_range(C&: UnsignedVec, R&: UnsignedVecForMBB); |
375 | } |
376 | } |
377 | |
378 | InstructionMapper() { |
379 | // Make sure that the implementation of DenseMapInfo<unsigned> hasn't |
380 | // changed. |
381 | assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 && |
382 | "DenseMapInfo<unsigned>'s empty key isn't -1!" ); |
383 | assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 && |
384 | "DenseMapInfo<unsigned>'s tombstone key isn't -2!" ); |
385 | } |
386 | }; |
387 | |
388 | /// An interprocedural pass which finds repeated sequences of |
389 | /// instructions and replaces them with calls to functions. |
390 | /// |
391 | /// Each instruction is mapped to an unsigned integer and placed in a string. |
392 | /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree |
393 | /// is then repeatedly queried for repeated sequences of instructions. Each |
394 | /// non-overlapping repeated sequence is then placed in its own |
395 | /// \p MachineFunction and each instance is then replaced with a call to that |
396 | /// function. |
397 | struct MachineOutliner : public ModulePass { |
398 | |
399 | static char ID; |
400 | |
401 | /// Set to true if the outliner should consider functions with |
402 | /// linkonceodr linkage. |
403 | bool OutlineFromLinkOnceODRs = false; |
404 | |
405 | /// The current repeat number of machine outlining. |
406 | unsigned OutlineRepeatedNum = 0; |
407 | |
408 | /// Set to true if the outliner should run on all functions in the module |
409 | /// considered safe for outlining. |
410 | /// Set to true by default for compatibility with llc's -run-pass option. |
411 | /// Set when the pass is constructed in TargetPassConfig. |
412 | bool RunOnAllFunctions = true; |
413 | |
414 | StringRef getPassName() const override { return "Machine Outliner" ; } |
415 | |
416 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
417 | AU.addRequired<MachineModuleInfoWrapperPass>(); |
418 | AU.addPreserved<MachineModuleInfoWrapperPass>(); |
419 | AU.setPreservesAll(); |
420 | ModulePass::getAnalysisUsage(AU); |
421 | } |
422 | |
423 | MachineOutliner() : ModulePass(ID) { |
424 | initializeMachineOutlinerPass(*PassRegistry::getPassRegistry()); |
425 | } |
426 | |
427 | /// Remark output explaining that not outlining a set of candidates would be |
428 | /// better than outlining that set. |
429 | void emitNotOutliningCheaperRemark( |
430 | unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
431 | OutlinedFunction &OF); |
432 | |
433 | /// Remark output explaining that a function was outlined. |
434 | void emitOutlinedFunctionRemark(OutlinedFunction &OF); |
435 | |
436 | /// Find all repeated substrings that satisfy the outlining cost model by |
437 | /// constructing a suffix tree. |
438 | /// |
439 | /// If a substring appears at least twice, then it must be represented by |
440 | /// an internal node which appears in at least two suffixes. Each suffix |
441 | /// is represented by a leaf node. To do this, we visit each internal node |
442 | /// in the tree, using the leaf children of each internal node. If an |
443 | /// internal node represents a beneficial substring, then we use each of |
444 | /// its leaf children to find the locations of its substring. |
445 | /// |
446 | /// \param Mapper Contains outlining mapping information. |
447 | /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions |
448 | /// each type of candidate. |
449 | void findCandidates(InstructionMapper &Mapper, |
450 | std::vector<OutlinedFunction> &FunctionList); |
451 | |
452 | /// Replace the sequences of instructions represented by \p OutlinedFunctions |
453 | /// with calls to functions. |
454 | /// |
455 | /// \param M The module we are outlining from. |
456 | /// \param FunctionList A list of functions to be inserted into the module. |
457 | /// \param Mapper Contains the instruction mappings for the module. |
458 | bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList, |
459 | InstructionMapper &Mapper, unsigned &OutlinedFunctionNum); |
460 | |
461 | /// Creates a function for \p OF and inserts it into the module. |
462 | MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF, |
463 | InstructionMapper &Mapper, |
464 | unsigned Name); |
465 | |
466 | /// Calls 'doOutline()' 1 + OutlinerReruns times. |
467 | bool runOnModule(Module &M) override; |
468 | |
469 | /// Construct a suffix tree on the instructions in \p M and outline repeated |
470 | /// strings from that tree. |
471 | bool doOutline(Module &M, unsigned &OutlinedFunctionNum); |
472 | |
473 | /// Return a DISubprogram for OF if one exists, and null otherwise. Helper |
474 | /// function for remark emission. |
475 | DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) { |
476 | for (const Candidate &C : OF.Candidates) |
477 | if (MachineFunction *MF = C.getMF()) |
478 | if (DISubprogram *SP = MF->getFunction().getSubprogram()) |
479 | return SP; |
480 | return nullptr; |
481 | } |
482 | |
483 | /// Populate and \p InstructionMapper with instruction-to-integer mappings. |
484 | /// These are used to construct a suffix tree. |
485 | void populateMapper(InstructionMapper &Mapper, Module &M, |
486 | MachineModuleInfo &MMI); |
487 | |
488 | /// Initialize information necessary to output a size remark. |
489 | /// FIXME: This should be handled by the pass manager, not the outliner. |
490 | /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy |
491 | /// pass manager. |
492 | void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI, |
493 | StringMap<unsigned> &FunctionToInstrCount); |
494 | |
495 | /// Emit the remark. |
496 | // FIXME: This should be handled by the pass manager, not the outliner. |
497 | void |
498 | emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI, |
499 | const StringMap<unsigned> &FunctionToInstrCount); |
500 | }; |
501 | } // Anonymous namespace. |
502 | |
503 | char MachineOutliner::ID = 0; |
504 | |
505 | namespace llvm { |
506 | ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) { |
507 | MachineOutliner *OL = new MachineOutliner(); |
508 | OL->RunOnAllFunctions = RunOnAllFunctions; |
509 | return OL; |
510 | } |
511 | |
512 | } // namespace llvm |
513 | |
514 | INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner" , false, |
515 | false) |
516 | |
517 | void MachineOutliner::emitNotOutliningCheaperRemark( |
518 | unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
519 | OutlinedFunction &OF) { |
520 | // FIXME: Right now, we arbitrarily choose some Candidate from the |
521 | // OutlinedFunction. This isn't necessarily fixed, nor does it have to be. |
522 | // We should probably sort these by function name or something to make sure |
523 | // the remarks are stable. |
524 | Candidate &C = CandidatesForRepeatedSeq.front(); |
525 | MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr); |
526 | MORE.emit(RemarkBuilder: [&]() { |
527 | MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper" , |
528 | C.front().getDebugLoc(), C.getMBB()); |
529 | R << "Did not outline " << NV("Length" , StringLen) << " instructions" |
530 | << " from " << NV("NumOccurrences" , CandidatesForRepeatedSeq.size()) |
531 | << " locations." |
532 | << " Bytes from outlining all occurrences (" |
533 | << NV("OutliningCost" , OF.getOutliningCost()) << ")" |
534 | << " >= Unoutlined instruction bytes (" |
535 | << NV("NotOutliningCost" , OF.getNotOutlinedCost()) << ")" |
536 | << " (Also found at: " ; |
537 | |
538 | // Tell the user the other places the candidate was found. |
539 | for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) { |
540 | R << NV((Twine("OtherStartLoc" ) + Twine(i)).str(), |
541 | CandidatesForRepeatedSeq[i].front().getDebugLoc()); |
542 | if (i != e - 1) |
543 | R << ", " ; |
544 | } |
545 | |
546 | R << ")" ; |
547 | return R; |
548 | }); |
549 | } |
550 | |
551 | void MachineOutliner::(OutlinedFunction &OF) { |
552 | MachineBasicBlock *MBB = &*OF.MF->begin(); |
553 | MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr); |
554 | MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction" , |
555 | MBB->findDebugLoc(MBBI: MBB->begin()), MBB); |
556 | R << "Saved " << NV("OutliningBenefit" , OF.getBenefit()) << " bytes by " |
557 | << "outlining " << NV("Length" , OF.getNumInstrs()) << " instructions " |
558 | << "from " << NV("NumOccurrences" , OF.getOccurrenceCount()) |
559 | << " locations. " |
560 | << "(Found at: " ; |
561 | |
562 | // Tell the user the other places the candidate was found. |
563 | for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) { |
564 | |
565 | R << NV((Twine("StartLoc" ) + Twine(i)).str(), |
566 | OF.Candidates[i].front().getDebugLoc()); |
567 | if (i != e - 1) |
568 | R << ", " ; |
569 | } |
570 | |
571 | R << ")" ; |
572 | |
573 | MORE.emit(OptDiag&: R); |
574 | } |
575 | |
576 | void MachineOutliner::findCandidates( |
577 | InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) { |
578 | FunctionList.clear(); |
579 | SuffixTree ST(Mapper.UnsignedVec); |
580 | |
581 | // First, find all of the repeated substrings in the tree of minimum length |
582 | // 2. |
583 | std::vector<Candidate> CandidatesForRepeatedSeq; |
584 | LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n" ); |
585 | LLVM_DEBUG( |
586 | dbgs() << "Searching for overlaps in all repeated sequences...\n" ); |
587 | for (const SuffixTree::RepeatedSubstring &RS : ST) { |
588 | CandidatesForRepeatedSeq.clear(); |
589 | unsigned StringLen = RS.Length; |
590 | LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n" ); |
591 | // Debug code to keep track of how many candidates we removed. |
592 | #ifndef NDEBUG |
593 | unsigned NumDiscarded = 0; |
594 | unsigned NumKept = 0; |
595 | #endif |
596 | for (const unsigned &StartIdx : RS.StartIndices) { |
597 | // Trick: Discard some candidates that would be incompatible with the |
598 | // ones we've already found for this sequence. This will save us some |
599 | // work in candidate selection. |
600 | // |
601 | // If two candidates overlap, then we can't outline them both. This |
602 | // happens when we have candidates that look like, say |
603 | // |
604 | // AA (where each "A" is an instruction). |
605 | // |
606 | // We might have some portion of the module that looks like this: |
607 | // AAAAAA (6 A's) |
608 | // |
609 | // In this case, there are 5 different copies of "AA" in this range, but |
610 | // at most 3 can be outlined. If only outlining 3 of these is going to |
611 | // be unbeneficial, then we ought to not bother. |
612 | // |
613 | // Note that two things DON'T overlap when they look like this: |
614 | // start1...end1 .... start2...end2 |
615 | // That is, one must either |
616 | // * End before the other starts |
617 | // * Start after the other ends |
618 | unsigned EndIdx = StartIdx + StringLen - 1; |
619 | auto FirstOverlap = find_if( |
620 | Range&: CandidatesForRepeatedSeq, P: [StartIdx, EndIdx](const Candidate &C) { |
621 | return EndIdx >= C.getStartIdx() && StartIdx <= C.getEndIdx(); |
622 | }); |
623 | if (FirstOverlap != CandidatesForRepeatedSeq.end()) { |
624 | #ifndef NDEBUG |
625 | ++NumDiscarded; |
626 | LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx |
627 | << ", " << EndIdx << "]; overlaps with candidate @ [" |
628 | << FirstOverlap->getStartIdx() << ", " |
629 | << FirstOverlap->getEndIdx() << "]\n" ); |
630 | #endif |
631 | continue; |
632 | } |
633 | // It doesn't overlap with anything, so we can outline it. |
634 | // Each sequence is over [StartIt, EndIt]. |
635 | // Save the candidate and its location. |
636 | #ifndef NDEBUG |
637 | ++NumKept; |
638 | #endif |
639 | MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; |
640 | MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; |
641 | MachineBasicBlock *MBB = StartIt->getParent(); |
642 | CandidatesForRepeatedSeq.emplace_back(args: StartIdx, args&: StringLen, args&: StartIt, args&: EndIt, |
643 | args&: MBB, args: FunctionList.size(), |
644 | args&: Mapper.MBBFlagsMap[MBB]); |
645 | } |
646 | #ifndef NDEBUG |
647 | LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded |
648 | << "\n" ); |
649 | LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n" ); |
650 | #endif |
651 | |
652 | // We've found something we might want to outline. |
653 | // Create an OutlinedFunction to store it and check if it'd be beneficial |
654 | // to outline. |
655 | if (CandidatesForRepeatedSeq.size() < 2) |
656 | continue; |
657 | |
658 | // Arbitrarily choose a TII from the first candidate. |
659 | // FIXME: Should getOutliningCandidateInfo move to TargetMachine? |
660 | const TargetInstrInfo *TII = |
661 | CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo(); |
662 | |
663 | std::optional<OutlinedFunction> OF = |
664 | TII->getOutliningCandidateInfo(RepeatedSequenceLocs&: CandidatesForRepeatedSeq); |
665 | |
666 | // If we deleted too many candidates, then there's nothing worth outlining. |
667 | // FIXME: This should take target-specified instruction sizes into account. |
668 | if (!OF || OF->Candidates.size() < 2) |
669 | continue; |
670 | |
671 | // Is it better to outline this candidate than not? |
672 | if (OF->getBenefit() < OutlinerBenefitThreshold) { |
673 | emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF&: *OF); |
674 | continue; |
675 | } |
676 | |
677 | FunctionList.push_back(x: *OF); |
678 | } |
679 | } |
680 | |
681 | MachineFunction *MachineOutliner::createOutlinedFunction( |
682 | Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) { |
683 | |
684 | // Create the function name. This should be unique. |
685 | // FIXME: We should have a better naming scheme. This should be stable, |
686 | // regardless of changes to the outliner's cost model/traversal order. |
687 | std::string FunctionName = "OUTLINED_FUNCTION_" ; |
688 | if (OutlineRepeatedNum > 0) |
689 | FunctionName += std::to_string(val: OutlineRepeatedNum + 1) + "_" ; |
690 | FunctionName += std::to_string(val: Name); |
691 | LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n" ); |
692 | |
693 | // Create the function using an IR-level function. |
694 | LLVMContext &C = M.getContext(); |
695 | Function *F = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false), |
696 | Linkage: Function::ExternalLinkage, N: FunctionName, M); |
697 | |
698 | // NOTE: If this is linkonceodr, then we can take advantage of linker deduping |
699 | // which gives us better results when we outline from linkonceodr functions. |
700 | F->setLinkage(GlobalValue::InternalLinkage); |
701 | F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); |
702 | |
703 | // Set optsize/minsize, so we don't insert padding between outlined |
704 | // functions. |
705 | F->addFnAttr(Attribute::OptimizeForSize); |
706 | F->addFnAttr(Attribute::MinSize); |
707 | |
708 | Candidate &FirstCand = OF.Candidates.front(); |
709 | const TargetInstrInfo &TII = |
710 | *FirstCand.getMF()->getSubtarget().getInstrInfo(); |
711 | |
712 | TII.mergeOutliningCandidateAttributes(F&: *F, Candidates&: OF.Candidates); |
713 | |
714 | // Set uwtable, so we generate eh_frame. |
715 | UWTableKind UW = std::accumulate( |
716 | first: OF.Candidates.cbegin(), last: OF.Candidates.cend(), init: UWTableKind::None, |
717 | binary_op: [](UWTableKind K, const outliner::Candidate &C) { |
718 | return std::max(a: K, b: C.getMF()->getFunction().getUWTableKind()); |
719 | }); |
720 | if (UW != UWTableKind::None) |
721 | F->setUWTableKind(UW); |
722 | |
723 | BasicBlock *EntryBB = BasicBlock::Create(Context&: C, Name: "entry" , Parent: F); |
724 | IRBuilder<> Builder(EntryBB); |
725 | Builder.CreateRetVoid(); |
726 | |
727 | MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
728 | MachineFunction &MF = MMI.getOrCreateMachineFunction(F&: *F); |
729 | MF.setIsOutlined(true); |
730 | MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock(); |
731 | |
732 | // Insert the new function into the module. |
733 | MF.insert(MBBI: MF.begin(), MBB: &MBB); |
734 | |
735 | MachineFunction *OriginalMF = FirstCand.front().getMF(); |
736 | const std::vector<MCCFIInstruction> &Instrs = |
737 | OriginalMF->getFrameInstructions(); |
738 | for (auto &MI : FirstCand) { |
739 | if (MI.isDebugInstr()) |
740 | continue; |
741 | |
742 | // Don't keep debug information for outlined instructions. |
743 | auto DL = DebugLoc(); |
744 | if (MI.isCFIInstruction()) { |
745 | unsigned CFIIndex = MI.getOperand(i: 0).getCFIIndex(); |
746 | MCCFIInstruction CFI = Instrs[CFIIndex]; |
747 | BuildMI(BB&: MBB, I: MBB.end(), MIMD: DL, MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION)) |
748 | .addCFIIndex(CFIIndex: MF.addFrameInst(Inst: CFI)); |
749 | } else { |
750 | MachineInstr *NewMI = MF.CloneMachineInstr(Orig: &MI); |
751 | NewMI->dropMemRefs(MF); |
752 | NewMI->setDebugLoc(DL); |
753 | MBB.insert(I: MBB.end(), MI: NewMI); |
754 | } |
755 | } |
756 | |
757 | // Set normal properties for a late MachineFunction. |
758 | MF.getProperties().reset(P: MachineFunctionProperties::Property::IsSSA); |
759 | MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs); |
760 | MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); |
761 | MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness); |
762 | MF.getRegInfo().freezeReservedRegs(MF); |
763 | |
764 | // Compute live-in set for outlined fn |
765 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
766 | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
767 | LivePhysRegs LiveIns(TRI); |
768 | for (auto &Cand : OF.Candidates) { |
769 | // Figure out live-ins at the first instruction. |
770 | MachineBasicBlock &OutlineBB = *Cand.front().getParent(); |
771 | LivePhysRegs CandLiveIns(TRI); |
772 | CandLiveIns.addLiveOuts(MBB: OutlineBB); |
773 | for (const MachineInstr &MI : |
774 | reverse(C: make_range(x: Cand.begin(), y: OutlineBB.end()))) |
775 | CandLiveIns.stepBackward(MI); |
776 | |
777 | // The live-in set for the outlined function is the union of the live-ins |
778 | // from all the outlining points. |
779 | for (MCPhysReg Reg : CandLiveIns) |
780 | LiveIns.addReg(Reg); |
781 | } |
782 | addLiveIns(MBB, LiveRegs: LiveIns); |
783 | |
784 | TII.buildOutlinedFrame(MBB, MF, OF); |
785 | |
786 | // If there's a DISubprogram associated with this outlined function, then |
787 | // emit debug info for the outlined function. |
788 | if (DISubprogram *SP = getSubprogramOrNull(OF)) { |
789 | // We have a DISubprogram. Get its DICompileUnit. |
790 | DICompileUnit *CU = SP->getUnit(); |
791 | DIBuilder DB(M, true, CU); |
792 | DIFile *Unit = SP->getFile(); |
793 | Mangler Mg; |
794 | // Get the mangled name of the function for the linkage name. |
795 | std::string Dummy; |
796 | raw_string_ostream MangledNameStream(Dummy); |
797 | Mg.getNameWithPrefix(OS&: MangledNameStream, GV: F, CannotUsePrivateLabel: false); |
798 | |
799 | DISubprogram *OutlinedSP = DB.createFunction( |
800 | Scope: Unit /* Context */, Name: F->getName(), LinkageName: StringRef(MangledNameStream.str()), |
801 | File: Unit /* File */, |
802 | LineNo: 0 /* Line 0 is reserved for compiler-generated code. */, |
803 | Ty: DB.createSubroutineType( |
804 | ParameterTypes: DB.getOrCreateTypeArray(Elements: std::nullopt)), /* void type */ |
805 | ScopeLine: 0, /* Line 0 is reserved for compiler-generated code. */ |
806 | Flags: DINode::DIFlags::FlagArtificial /* Compiler-generated code. */, |
807 | /* Outlined code is optimized code by definition. */ |
808 | SPFlags: DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized); |
809 | |
810 | // Don't add any new variables to the subprogram. |
811 | DB.finalizeSubprogram(SP: OutlinedSP); |
812 | |
813 | // Attach subprogram to the function. |
814 | F->setSubprogram(OutlinedSP); |
815 | // We're done with the DIBuilder. |
816 | DB.finalize(); |
817 | } |
818 | |
819 | return &MF; |
820 | } |
821 | |
822 | bool MachineOutliner::outline(Module &M, |
823 | std::vector<OutlinedFunction> &FunctionList, |
824 | InstructionMapper &Mapper, |
825 | unsigned &OutlinedFunctionNum) { |
826 | LLVM_DEBUG(dbgs() << "*** Outlining ***\n" ); |
827 | LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size() |
828 | << "\n" ); |
829 | bool OutlinedSomething = false; |
830 | |
831 | // Sort by benefit. The most beneficial functions should be outlined first. |
832 | stable_sort(Range&: FunctionList, |
833 | C: [](const OutlinedFunction &LHS, const OutlinedFunction &RHS) { |
834 | return LHS.getBenefit() > RHS.getBenefit(); |
835 | }); |
836 | |
837 | // Walk over each function, outlining them as we go along. Functions are |
838 | // outlined greedily, based off the sort above. |
839 | auto *UnsignedVecBegin = Mapper.UnsignedVec.begin(); |
840 | LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n" ); |
841 | for (OutlinedFunction &OF : FunctionList) { |
842 | #ifndef NDEBUG |
843 | auto NumCandidatesBefore = OF.Candidates.size(); |
844 | #endif |
845 | // If we outlined something that overlapped with a candidate in a previous |
846 | // step, then we can't outline from it. |
847 | erase_if(C&: OF.Candidates, P: [&UnsignedVecBegin](Candidate &C) { |
848 | return std::any_of(first: UnsignedVecBegin + C.getStartIdx(), |
849 | last: UnsignedVecBegin + C.getEndIdx() + 1, pred: [](unsigned I) { |
850 | return I == static_cast<unsigned>(-1); |
851 | }); |
852 | }); |
853 | |
854 | #ifndef NDEBUG |
855 | auto NumCandidatesAfter = OF.Candidates.size(); |
856 | LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter |
857 | << "/" << NumCandidatesBefore << " candidates\n" ); |
858 | #endif |
859 | |
860 | // If we made it unbeneficial to outline this function, skip it. |
861 | if (OF.getBenefit() < OutlinerBenefitThreshold) { |
862 | LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF.getBenefit() |
863 | << " B) < threshold (" << OutlinerBenefitThreshold |
864 | << " B)\n" ); |
865 | continue; |
866 | } |
867 | |
868 | LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF.getBenefit() |
869 | << " B) > threshold (" << OutlinerBenefitThreshold |
870 | << " B)\n" ); |
871 | |
872 | // It's beneficial. Create the function and outline its sequence's |
873 | // occurrences. |
874 | OF.MF = createOutlinedFunction(M, OF, Mapper, Name: OutlinedFunctionNum); |
875 | emitOutlinedFunctionRemark(OF); |
876 | FunctionsCreated++; |
877 | OutlinedFunctionNum++; // Created a function, move to the next name. |
878 | MachineFunction *MF = OF.MF; |
879 | const TargetSubtargetInfo &STI = MF->getSubtarget(); |
880 | const TargetInstrInfo &TII = *STI.getInstrInfo(); |
881 | |
882 | // Replace occurrences of the sequence with calls to the new function. |
883 | LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n" ); |
884 | for (Candidate &C : OF.Candidates) { |
885 | MachineBasicBlock &MBB = *C.getMBB(); |
886 | MachineBasicBlock::iterator StartIt = C.begin(); |
887 | MachineBasicBlock::iterator EndIt = std::prev(x: C.end()); |
888 | |
889 | // Insert the call. |
890 | auto CallInst = TII.insertOutlinedCall(M, MBB, It&: StartIt, MF&: *MF, C); |
891 | // Insert the call. |
892 | #ifndef NDEBUG |
893 | auto MBBBeingOutlinedFromName = |
894 | MBB.getName().empty() ? "<unknown>" : MBB.getName().str(); |
895 | auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty() |
896 | ? "<unknown>" |
897 | : MBB.getParent()->getName().str(); |
898 | LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in " |
899 | << MFBeingOutlinedFromName << ":" |
900 | << MBBBeingOutlinedFromName << "\n" ); |
901 | LLVM_DEBUG(dbgs() << " .. " << *CallInst); |
902 | #endif |
903 | |
904 | // If the caller tracks liveness, then we need to make sure that |
905 | // anything we outline doesn't break liveness assumptions. The outlined |
906 | // functions themselves currently don't track liveness, but we should |
907 | // make sure that the ranges we yank things out of aren't wrong. |
908 | if (MBB.getParent()->getProperties().hasProperty( |
909 | P: MachineFunctionProperties::Property::TracksLiveness)) { |
910 | // The following code is to add implicit def operands to the call |
911 | // instruction. It also updates call site information for moved |
912 | // code. |
913 | SmallSet<Register, 2> UseRegs, DefRegs; |
914 | // Copy over the defs in the outlined range. |
915 | // First inst in outlined range <-- Anything that's defined in this |
916 | // ... .. range has to be added as an |
917 | // implicit Last inst in outlined range <-- def to the call |
918 | // instruction. Also remove call site information for outlined block |
919 | // of code. The exposed uses need to be copied in the outlined range. |
920 | for (MachineBasicBlock::reverse_iterator |
921 | Iter = EndIt.getReverse(), |
922 | Last = std::next(x: CallInst.getReverse()); |
923 | Iter != Last; Iter++) { |
924 | MachineInstr *MI = &*Iter; |
925 | SmallSet<Register, 2> InstrUseRegs; |
926 | for (MachineOperand &MOP : MI->operands()) { |
927 | // Skip over anything that isn't a register. |
928 | if (!MOP.isReg()) |
929 | continue; |
930 | |
931 | if (MOP.isDef()) { |
932 | // Introduce DefRegs set to skip the redundant register. |
933 | DefRegs.insert(V: MOP.getReg()); |
934 | if (UseRegs.count(V: MOP.getReg()) && |
935 | !InstrUseRegs.count(V: MOP.getReg())) |
936 | // Since the regiester is modeled as defined, |
937 | // it is not necessary to be put in use register set. |
938 | UseRegs.erase(V: MOP.getReg()); |
939 | } else if (!MOP.isUndef()) { |
940 | // Any register which is not undefined should |
941 | // be put in the use register set. |
942 | UseRegs.insert(V: MOP.getReg()); |
943 | InstrUseRegs.insert(V: MOP.getReg()); |
944 | } |
945 | } |
946 | if (MI->isCandidateForCallSiteEntry()) |
947 | MI->getMF()->eraseCallSiteInfo(MI); |
948 | } |
949 | |
950 | for (const Register &I : DefRegs) |
951 | // If it's a def, add it to the call instruction. |
952 | CallInst->addOperand( |
953 | Op: MachineOperand::CreateReg(Reg: I, isDef: true, /* isDef = true */ |
954 | isImp: true /* isImp = true */)); |
955 | |
956 | for (const Register &I : UseRegs) |
957 | // If it's a exposed use, add it to the call instruction. |
958 | CallInst->addOperand( |
959 | Op: MachineOperand::CreateReg(Reg: I, isDef: false, /* isDef = false */ |
960 | isImp: true /* isImp = true */)); |
961 | } |
962 | |
963 | // Erase from the point after where the call was inserted up to, and |
964 | // including, the final instruction in the sequence. |
965 | // Erase needs one past the end, so we need std::next there too. |
966 | MBB.erase(I: std::next(x: StartIt), E: std::next(x: EndIt)); |
967 | |
968 | // Keep track of what we removed by marking them all as -1. |
969 | for (unsigned &I : make_range(x: UnsignedVecBegin + C.getStartIdx(), |
970 | y: UnsignedVecBegin + C.getEndIdx() + 1)) |
971 | I = static_cast<unsigned>(-1); |
972 | OutlinedSomething = true; |
973 | |
974 | // Statistics. |
975 | NumOutlined++; |
976 | } |
977 | } |
978 | |
979 | LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n" ;); |
980 | return OutlinedSomething; |
981 | } |
982 | |
983 | void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M, |
984 | MachineModuleInfo &MMI) { |
985 | // Build instruction mappings for each function in the module. Start by |
986 | // iterating over each Function in M. |
987 | LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n" ); |
988 | for (Function &F : M) { |
989 | LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n" ); |
990 | |
991 | if (F.hasFnAttribute(Kind: "nooutline" )) { |
992 | LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n" ); |
993 | continue; |
994 | } |
995 | |
996 | // There's something in F. Check if it has a MachineFunction associated with |
997 | // it. |
998 | MachineFunction *MF = MMI.getMachineFunction(F); |
999 | |
1000 | // If it doesn't, then there's nothing to outline from. Move to the next |
1001 | // Function. |
1002 | if (!MF) { |
1003 | LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n" ); |
1004 | continue; |
1005 | } |
1006 | |
1007 | const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); |
1008 | if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) { |
1009 | LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from " |
1010 | "function by default\n" ); |
1011 | continue; |
1012 | } |
1013 | |
1014 | // We have a MachineFunction. Ask the target if it's suitable for outlining. |
1015 | // If it isn't, then move on to the next Function in the module. |
1016 | if (!TII->isFunctionSafeToOutlineFrom(MF&: *MF, OutlineFromLinkOnceODRs)) { |
1017 | LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName() |
1018 | << ": unsafe to outline from\n" ); |
1019 | continue; |
1020 | } |
1021 | |
1022 | // We have a function suitable for outlining. Iterate over every |
1023 | // MachineBasicBlock in MF and try to map its instructions to a list of |
1024 | // unsigned integers. |
1025 | const unsigned MinMBBSize = 2; |
1026 | |
1027 | for (MachineBasicBlock &MBB : *MF) { |
1028 | LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n" ); |
1029 | // If there isn't anything in MBB, then there's no point in outlining from |
1030 | // it. |
1031 | // If there are fewer than 2 instructions in the MBB, then it can't ever |
1032 | // contain something worth outlining. |
1033 | // FIXME: This should be based off of the maximum size in B of an outlined |
1034 | // call versus the size in B of the MBB. |
1035 | if (MBB.size() < MinMBBSize) { |
1036 | LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of " |
1037 | << MinMBBSize << "\n" ); |
1038 | continue; |
1039 | } |
1040 | |
1041 | // Check if MBB could be the target of an indirect branch. If it is, then |
1042 | // we don't want to outline from it. |
1043 | if (MBB.hasAddressTaken()) { |
1044 | LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n" ); |
1045 | continue; |
1046 | } |
1047 | |
1048 | // MBB is suitable for outlining. Map it to a list of unsigneds. |
1049 | Mapper.convertToUnsignedVec(MBB, TII: *TII); |
1050 | } |
1051 | } |
1052 | // Statistics. |
1053 | UnsignedVecSize = Mapper.UnsignedVec.size(); |
1054 | } |
1055 | |
1056 | void MachineOutliner::( |
1057 | const Module &M, const MachineModuleInfo &MMI, |
1058 | StringMap<unsigned> &FunctionToInstrCount) { |
1059 | // Collect instruction counts for every function. We'll use this to emit |
1060 | // per-function size remarks later. |
1061 | for (const Function &F : M) { |
1062 | MachineFunction *MF = MMI.getMachineFunction(F); |
1063 | |
1064 | // We only care about MI counts here. If there's no MachineFunction at this |
1065 | // point, then there won't be after the outliner runs, so let's move on. |
1066 | if (!MF) |
1067 | continue; |
1068 | FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount(); |
1069 | } |
1070 | } |
1071 | |
1072 | void MachineOutliner::( |
1073 | const Module &M, const MachineModuleInfo &MMI, |
1074 | const StringMap<unsigned> &FunctionToInstrCount) { |
1075 | // Iterate over each function in the module and emit remarks. |
1076 | // Note that we won't miss anything by doing this, because the outliner never |
1077 | // deletes functions. |
1078 | for (const Function &F : M) { |
1079 | MachineFunction *MF = MMI.getMachineFunction(F); |
1080 | |
1081 | // The outliner never deletes functions. If we don't have a MF here, then we |
1082 | // didn't have one prior to outlining either. |
1083 | if (!MF) |
1084 | continue; |
1085 | |
1086 | std::string Fname = std::string(F.getName()); |
1087 | unsigned FnCountAfter = MF->getInstructionCount(); |
1088 | unsigned FnCountBefore = 0; |
1089 | |
1090 | // Check if the function was recorded before. |
1091 | auto It = FunctionToInstrCount.find(Key: Fname); |
1092 | |
1093 | // Did we have a previously-recorded size? If yes, then set FnCountBefore |
1094 | // to that. |
1095 | if (It != FunctionToInstrCount.end()) |
1096 | FnCountBefore = It->second; |
1097 | |
1098 | // Compute the delta and emit a remark if there was a change. |
1099 | int64_t FnDelta = static_cast<int64_t>(FnCountAfter) - |
1100 | static_cast<int64_t>(FnCountBefore); |
1101 | if (FnDelta == 0) |
1102 | continue; |
1103 | |
1104 | MachineOptimizationRemarkEmitter MORE(*MF, nullptr); |
1105 | MORE.emit(RemarkBuilder: [&]() { |
1106 | MachineOptimizationRemarkAnalysis R("size-info" , "FunctionMISizeChange" , |
1107 | DiagnosticLocation(), &MF->front()); |
1108 | R << DiagnosticInfoOptimizationBase::Argument("Pass" , "Machine Outliner" ) |
1109 | << ": Function: " |
1110 | << DiagnosticInfoOptimizationBase::Argument("Function" , F.getName()) |
1111 | << ": MI instruction count changed from " |
1112 | << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore" , |
1113 | FnCountBefore) |
1114 | << " to " |
1115 | << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter" , |
1116 | FnCountAfter) |
1117 | << "; Delta: " |
1118 | << DiagnosticInfoOptimizationBase::Argument("Delta" , FnDelta); |
1119 | return R; |
1120 | }); |
1121 | } |
1122 | } |
1123 | |
1124 | bool MachineOutliner::runOnModule(Module &M) { |
1125 | // Check if there's anything in the module. If it's empty, then there's |
1126 | // nothing to outline. |
1127 | if (M.empty()) |
1128 | return false; |
1129 | |
1130 | // Number to append to the current outlined function. |
1131 | unsigned OutlinedFunctionNum = 0; |
1132 | |
1133 | OutlineRepeatedNum = 0; |
1134 | if (!doOutline(M, OutlinedFunctionNum)) |
1135 | return false; |
1136 | |
1137 | for (unsigned I = 0; I < OutlinerReruns; ++I) { |
1138 | OutlinedFunctionNum = 0; |
1139 | OutlineRepeatedNum++; |
1140 | if (!doOutline(M, OutlinedFunctionNum)) { |
1141 | LLVM_DEBUG({ |
1142 | dbgs() << "Did not outline on iteration " << I + 2 << " out of " |
1143 | << OutlinerReruns + 1 << "\n" ; |
1144 | }); |
1145 | break; |
1146 | } |
1147 | } |
1148 | |
1149 | return true; |
1150 | } |
1151 | |
1152 | bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) { |
1153 | MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
1154 | |
1155 | // If the user passed -enable-machine-outliner=always or |
1156 | // -enable-machine-outliner, the pass will run on all functions in the module. |
1157 | // Otherwise, if the target supports default outlining, it will run on all |
1158 | // functions deemed by the target to be worth outlining from by default. Tell |
1159 | // the user how the outliner is running. |
1160 | LLVM_DEBUG({ |
1161 | dbgs() << "Machine Outliner: Running on " ; |
1162 | if (RunOnAllFunctions) |
1163 | dbgs() << "all functions" ; |
1164 | else |
1165 | dbgs() << "target-default functions" ; |
1166 | dbgs() << "\n" ; |
1167 | }); |
1168 | |
1169 | // If the user specifies that they want to outline from linkonceodrs, set |
1170 | // it here. |
1171 | OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining; |
1172 | InstructionMapper Mapper; |
1173 | |
1174 | // Prepare instruction mappings for the suffix tree. |
1175 | populateMapper(Mapper, M, MMI); |
1176 | std::vector<OutlinedFunction> FunctionList; |
1177 | |
1178 | // Find all of the outlining candidates. |
1179 | findCandidates(Mapper, FunctionList); |
1180 | |
1181 | // If we've requested size remarks, then collect the MI counts of every |
1182 | // function before outlining, and the MI counts after outlining. |
1183 | // FIXME: This shouldn't be in the outliner at all; it should ultimately be |
1184 | // the pass manager's responsibility. |
1185 | // This could pretty easily be placed in outline instead, but because we |
1186 | // really ultimately *don't* want this here, it's done like this for now |
1187 | // instead. |
1188 | |
1189 | // Check if we want size remarks. |
1190 | bool = M.shouldEmitInstrCountChangedRemark(); |
1191 | StringMap<unsigned> FunctionToInstrCount; |
1192 | if (ShouldEmitSizeRemarks) |
1193 | initSizeRemarkInfo(M, MMI, FunctionToInstrCount); |
1194 | |
1195 | // Outline each of the candidates and return true if something was outlined. |
1196 | bool OutlinedSomething = |
1197 | outline(M, FunctionList, Mapper, OutlinedFunctionNum); |
1198 | |
1199 | // If we outlined something, we definitely changed the MI count of the |
1200 | // module. If we've asked for size remarks, then output them. |
1201 | // FIXME: This should be in the pass manager. |
1202 | if (ShouldEmitSizeRemarks && OutlinedSomething) |
1203 | emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount); |
1204 | |
1205 | LLVM_DEBUG({ |
1206 | if (!OutlinedSomething) |
1207 | dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum |
1208 | << " because no changes were found.\n" ; |
1209 | }); |
1210 | |
1211 | return OutlinedSomething; |
1212 | } |
1213 | |