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/CodeGen/MachineFunction.h"
63 #include "llvm/CodeGen/MachineModuleInfo.h"
64 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
65 #include "llvm/CodeGen/MachineRegisterInfo.h"
66 #include "llvm/CodeGen/Passes.h"
67 #include "llvm/CodeGen/TargetInstrInfo.h"
68 #include "llvm/CodeGen/TargetSubtargetInfo.h"
69 #include "llvm/IR/DIBuilder.h"
70 #include "llvm/IR/IRBuilder.h"
71 #include "llvm/IR/Mangler.h"
72 #include "llvm/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 STATISTIC(NumOutlined, "Number of candidates outlined");
88 STATISTIC(FunctionsCreated, "Number of functions created");
89
90 // Set to true if the user wants the outliner to run on linkonceodr linkage
91 // functions. This is false by default because the linker can dedupe linkonceodr
92 // functions. Since the outliner is confined to a single module (modulo LTO),
93 // this is off by default. It should, however, be the default behaviour in
94 // LTO.
95 static cl::opt<bool> EnableLinkOnceODROutlining(
96 "enable-linkonceodr-outlining", cl::Hidden,
97 cl::desc("Enable the machine outliner on linkonceodr functions"),
98 cl::init(false));
99
100 /// Number of times to re-run the outliner. This is not the total number of runs
101 /// as the outliner will run at least one time. The default value is set to 0,
102 /// meaning the outliner will run one time and rerun zero times after that.
103 static cl::opt<unsigned> OutlinerReruns(
104 "machine-outliner-reruns", cl::init(0), cl::Hidden,
105 cl::desc(
106 "Number of times to rerun the outliner after the initial outline"));
107
108 namespace {
109
110 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
111 struct InstructionMapper {
112
113 /// The next available integer to assign to a \p MachineInstr that
114 /// cannot be outlined.
115 ///
116 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
117 unsigned IllegalInstrNumber = -3;
118
119 /// The next available integer to assign to a \p MachineInstr that can
120 /// be outlined.
121 unsigned LegalInstrNumber = 0;
122
123 /// Correspondence from \p MachineInstrs to unsigned integers.
124 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
125 InstructionIntegerMap;
126
127 /// Correspondence between \p MachineBasicBlocks and target-defined flags.
128 DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
129
130 /// The vector of unsigned integers that the module is mapped to.
131 std::vector<unsigned> UnsignedVec;
132
133 /// Stores the location of the instruction associated with the integer
134 /// at index i in \p UnsignedVec for each index i.
135 std::vector<MachineBasicBlock::iterator> InstrList;
136
137 // Set if we added an illegal number in the previous step.
138 // Since each illegal number is unique, we only need one of them between
139 // each range of legal numbers. This lets us make sure we don't add more
140 // than one illegal number per range.
141 bool AddedIllegalLastTime = false;
142
143 /// Maps \p *It to a legal integer.
144 ///
145 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
146 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
147 ///
148 /// \returns The integer that \p *It was mapped to.
mapToLegalUnsigned__anon110fcd690111::InstructionMapper149 unsigned mapToLegalUnsigned(
150 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
151 bool &HaveLegalRange, unsigned &NumLegalInBlock,
152 std::vector<unsigned> &UnsignedVecForMBB,
153 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
154 // We added something legal, so we should unset the AddedLegalLastTime
155 // flag.
156 AddedIllegalLastTime = false;
157
158 // If we have at least two adjacent legal instructions (which may have
159 // invisible instructions in between), remember that.
160 if (CanOutlineWithPrevInstr)
161 HaveLegalRange = true;
162 CanOutlineWithPrevInstr = true;
163
164 // Keep track of the number of legal instructions we insert.
165 NumLegalInBlock++;
166
167 // Get the integer for this instruction or give it the current
168 // LegalInstrNumber.
169 InstrListForMBB.push_back(It);
170 MachineInstr &MI = *It;
171 bool WasInserted;
172 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
173 ResultIt;
174 std::tie(ResultIt, WasInserted) =
175 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
176 unsigned MINumber = ResultIt->second;
177
178 // There was an insertion.
179 if (WasInserted)
180 LegalInstrNumber++;
181
182 UnsignedVecForMBB.push_back(MINumber);
183
184 // Make sure we don't overflow or use any integers reserved by the DenseMap.
185 if (LegalInstrNumber >= IllegalInstrNumber)
186 report_fatal_error("Instruction mapping overflow!");
187
188 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
189 "Tried to assign DenseMap tombstone or empty key to instruction.");
190 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
191 "Tried to assign DenseMap tombstone or empty key to instruction.");
192
193 return MINumber;
194 }
195
196 /// Maps \p *It to an illegal integer.
197 ///
198 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
199 /// IllegalInstrNumber.
200 ///
201 /// \returns The integer that \p *It was mapped to.
mapToIllegalUnsigned__anon110fcd690111::InstructionMapper202 unsigned mapToIllegalUnsigned(
203 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
204 std::vector<unsigned> &UnsignedVecForMBB,
205 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
206 // Can't outline an illegal instruction. Set the flag.
207 CanOutlineWithPrevInstr = false;
208
209 // Only add one illegal number per range of legal numbers.
210 if (AddedIllegalLastTime)
211 return IllegalInstrNumber;
212
213 // Remember that we added an illegal number last time.
214 AddedIllegalLastTime = true;
215 unsigned MINumber = IllegalInstrNumber;
216
217 InstrListForMBB.push_back(It);
218 UnsignedVecForMBB.push_back(IllegalInstrNumber);
219 IllegalInstrNumber--;
220
221 assert(LegalInstrNumber < IllegalInstrNumber &&
222 "Instruction mapping overflow!");
223
224 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
225 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
226
227 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
228 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
229
230 return MINumber;
231 }
232
233 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
234 /// and appends it to \p UnsignedVec and \p InstrList.
235 ///
236 /// Two instructions are assigned the same integer if they are identical.
237 /// If an instruction is deemed unsafe to outline, then it will be assigned an
238 /// unique integer. The resulting mapping is placed into a suffix tree and
239 /// queried for candidates.
240 ///
241 /// \param MBB The \p MachineBasicBlock to be translated into integers.
242 /// \param TII \p TargetInstrInfo for the function.
convertToUnsignedVec__anon110fcd690111::InstructionMapper243 void convertToUnsignedVec(MachineBasicBlock &MBB,
244 const TargetInstrInfo &TII) {
245 unsigned Flags = 0;
246
247 // Don't even map in this case.
248 if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
249 return;
250
251 // Store info for the MBB for later outlining.
252 MBBFlagsMap[&MBB] = Flags;
253
254 MachineBasicBlock::iterator It = MBB.begin();
255
256 // The number of instructions in this block that will be considered for
257 // outlining.
258 unsigned NumLegalInBlock = 0;
259
260 // True if we have at least two legal instructions which aren't separated
261 // by an illegal instruction.
262 bool HaveLegalRange = false;
263
264 // True if we can perform outlining given the last mapped (non-invisible)
265 // instruction. This lets us know if we have a legal range.
266 bool CanOutlineWithPrevInstr = false;
267
268 // FIXME: Should this all just be handled in the target, rather than using
269 // repeated calls to getOutliningType?
270 std::vector<unsigned> UnsignedVecForMBB;
271 std::vector<MachineBasicBlock::iterator> InstrListForMBB;
272
273 for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; ++It) {
274 // Keep track of where this instruction is in the module.
275 switch (TII.getOutliningType(It, Flags)) {
276 case InstrType::Illegal:
277 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
278 InstrListForMBB);
279 break;
280
281 case InstrType::Legal:
282 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
283 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
284 break;
285
286 case InstrType::LegalTerminator:
287 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
288 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
289 // The instruction also acts as a terminator, so we have to record that
290 // in the string.
291 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
292 InstrListForMBB);
293 break;
294
295 case InstrType::Invisible:
296 // Normally this is set by mapTo(Blah)Unsigned, but we just want to
297 // skip this instruction. So, unset the flag here.
298 AddedIllegalLastTime = false;
299 break;
300 }
301 }
302
303 // Are there enough legal instructions in the block for outlining to be
304 // possible?
305 if (HaveLegalRange) {
306 // After we're done every insertion, uniquely terminate this part of the
307 // "string". This makes sure we won't match across basic block or function
308 // boundaries since the "end" is encoded uniquely and thus appears in no
309 // repeated substring.
310 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
311 InstrListForMBB);
312 InstrList.insert(InstrList.end(), InstrListForMBB.begin(),
313 InstrListForMBB.end());
314 UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForMBB.begin(),
315 UnsignedVecForMBB.end());
316 }
317 }
318
InstructionMapper__anon110fcd690111::InstructionMapper319 InstructionMapper() {
320 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
321 // changed.
322 assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
323 "DenseMapInfo<unsigned>'s empty key isn't -1!");
324 assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
325 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
326 }
327 };
328
329 /// An interprocedural pass which finds repeated sequences of
330 /// instructions and replaces them with calls to functions.
331 ///
332 /// Each instruction is mapped to an unsigned integer and placed in a string.
333 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
334 /// is then repeatedly queried for repeated sequences of instructions. Each
335 /// non-overlapping repeated sequence is then placed in its own
336 /// \p MachineFunction and each instance is then replaced with a call to that
337 /// function.
338 struct MachineOutliner : public ModulePass {
339
340 static char ID;
341
342 /// Set to true if the outliner should consider functions with
343 /// linkonceodr linkage.
344 bool OutlineFromLinkOnceODRs = false;
345
346 /// The current repeat number of machine outlining.
347 unsigned OutlineRepeatedNum = 0;
348
349 /// Set to true if the outliner should run on all functions in the module
350 /// considered safe for outlining.
351 /// Set to true by default for compatibility with llc's -run-pass option.
352 /// Set when the pass is constructed in TargetPassConfig.
353 bool RunOnAllFunctions = true;
354
getPassName__anon110fcd690111::MachineOutliner355 StringRef getPassName() const override { return "Machine Outliner"; }
356
getAnalysisUsage__anon110fcd690111::MachineOutliner357 void getAnalysisUsage(AnalysisUsage &AU) const override {
358 AU.addRequired<MachineModuleInfoWrapperPass>();
359 AU.addPreserved<MachineModuleInfoWrapperPass>();
360 AU.setPreservesAll();
361 ModulePass::getAnalysisUsage(AU);
362 }
363
MachineOutliner__anon110fcd690111::MachineOutliner364 MachineOutliner() : ModulePass(ID) {
365 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
366 }
367
368 /// Remark output explaining that not outlining a set of candidates would be
369 /// better than outlining that set.
370 void emitNotOutliningCheaperRemark(
371 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
372 OutlinedFunction &OF);
373
374 /// Remark output explaining that a function was outlined.
375 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
376
377 /// Find all repeated substrings that satisfy the outlining cost model by
378 /// constructing a suffix tree.
379 ///
380 /// If a substring appears at least twice, then it must be represented by
381 /// an internal node which appears in at least two suffixes. Each suffix
382 /// is represented by a leaf node. To do this, we visit each internal node
383 /// in the tree, using the leaf children of each internal node. If an
384 /// internal node represents a beneficial substring, then we use each of
385 /// its leaf children to find the locations of its substring.
386 ///
387 /// \param Mapper Contains outlining mapping information.
388 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
389 /// each type of candidate.
390 void findCandidates(InstructionMapper &Mapper,
391 std::vector<OutlinedFunction> &FunctionList);
392
393 /// Replace the sequences of instructions represented by \p OutlinedFunctions
394 /// with calls to functions.
395 ///
396 /// \param M The module we are outlining from.
397 /// \param FunctionList A list of functions to be inserted into the module.
398 /// \param Mapper Contains the instruction mappings for the module.
399 bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
400 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
401
402 /// Creates a function for \p OF and inserts it into the module.
403 MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
404 InstructionMapper &Mapper,
405 unsigned Name);
406
407 /// Calls 'doOutline()' 1 + OutlinerReruns times.
408 bool runOnModule(Module &M) override;
409
410 /// Construct a suffix tree on the instructions in \p M and outline repeated
411 /// strings from that tree.
412 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
413
414 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
415 /// function for remark emission.
getSubprogramOrNull__anon110fcd690111::MachineOutliner416 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
417 for (const Candidate &C : OF.Candidates)
418 if (MachineFunction *MF = C.getMF())
419 if (DISubprogram *SP = MF->getFunction().getSubprogram())
420 return SP;
421 return nullptr;
422 }
423
424 /// Populate and \p InstructionMapper with instruction-to-integer mappings.
425 /// These are used to construct a suffix tree.
426 void populateMapper(InstructionMapper &Mapper, Module &M,
427 MachineModuleInfo &MMI);
428
429 /// Initialize information necessary to output a size remark.
430 /// FIXME: This should be handled by the pass manager, not the outliner.
431 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
432 /// pass manager.
433 void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI,
434 StringMap<unsigned> &FunctionToInstrCount);
435
436 /// Emit the remark.
437 // FIXME: This should be handled by the pass manager, not the outliner.
438 void
439 emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
440 const StringMap<unsigned> &FunctionToInstrCount);
441 };
442 } // Anonymous namespace.
443
444 char MachineOutliner::ID = 0;
445
446 namespace llvm {
createMachineOutlinerPass(bool RunOnAllFunctions)447 ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
448 MachineOutliner *OL = new MachineOutliner();
449 OL->RunOnAllFunctions = RunOnAllFunctions;
450 return OL;
451 }
452
453 } // namespace llvm
454
455 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
456 false)
457
emitNotOutliningCheaperRemark(unsigned StringLen,std::vector<Candidate> & CandidatesForRepeatedSeq,OutlinedFunction & OF)458 void MachineOutliner::emitNotOutliningCheaperRemark(
459 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
460 OutlinedFunction &OF) {
461 // FIXME: Right now, we arbitrarily choose some Candidate from the
462 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
463 // We should probably sort these by function name or something to make sure
464 // the remarks are stable.
465 Candidate &C = CandidatesForRepeatedSeq.front();
466 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
467 MORE.emit([&]() {
468 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
469 C.front()->getDebugLoc(), C.getMBB());
470 R << "Did not outline " << NV("Length", StringLen) << " instructions"
471 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
472 << " locations."
473 << " Bytes from outlining all occurrences ("
474 << NV("OutliningCost", OF.getOutliningCost()) << ")"
475 << " >= Unoutlined instruction bytes ("
476 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
477 << " (Also found at: ";
478
479 // Tell the user the other places the candidate was found.
480 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
481 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
482 CandidatesForRepeatedSeq[i].front()->getDebugLoc());
483 if (i != e - 1)
484 R << ", ";
485 }
486
487 R << ")";
488 return R;
489 });
490 }
491
emitOutlinedFunctionRemark(OutlinedFunction & OF)492 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
493 MachineBasicBlock *MBB = &*OF.MF->begin();
494 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
495 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
496 MBB->findDebugLoc(MBB->begin()), MBB);
497 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
498 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
499 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
500 << " locations. "
501 << "(Found at: ";
502
503 // Tell the user the other places the candidate was found.
504 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
505
506 R << NV((Twine("StartLoc") + Twine(i)).str(),
507 OF.Candidates[i].front()->getDebugLoc());
508 if (i != e - 1)
509 R << ", ";
510 }
511
512 R << ")";
513
514 MORE.emit(R);
515 }
516
findCandidates(InstructionMapper & Mapper,std::vector<OutlinedFunction> & FunctionList)517 void MachineOutliner::findCandidates(
518 InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
519 FunctionList.clear();
520 SuffixTree ST(Mapper.UnsignedVec);
521
522 // First, find all of the repeated substrings in the tree of minimum length
523 // 2.
524 std::vector<Candidate> CandidatesForRepeatedSeq;
525 for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
526 CandidatesForRepeatedSeq.clear();
527 SuffixTree::RepeatedSubstring RS = *It;
528 unsigned StringLen = RS.Length;
529 for (const unsigned &StartIdx : RS.StartIndices) {
530 unsigned EndIdx = StartIdx + StringLen - 1;
531 // Trick: Discard some candidates that would be incompatible with the
532 // ones we've already found for this sequence. This will save us some
533 // work in candidate selection.
534 //
535 // If two candidates overlap, then we can't outline them both. This
536 // happens when we have candidates that look like, say
537 //
538 // AA (where each "A" is an instruction).
539 //
540 // We might have some portion of the module that looks like this:
541 // AAAAAA (6 A's)
542 //
543 // In this case, there are 5 different copies of "AA" in this range, but
544 // at most 3 can be outlined. If only outlining 3 of these is going to
545 // be unbeneficial, then we ought to not bother.
546 //
547 // Note that two things DON'T overlap when they look like this:
548 // start1...end1 .... start2...end2
549 // That is, one must either
550 // * End before the other starts
551 // * Start after the other ends
552 if (std::all_of(
553 CandidatesForRepeatedSeq.begin(), CandidatesForRepeatedSeq.end(),
554 [&StartIdx, &EndIdx](const Candidate &C) {
555 return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx());
556 })) {
557 // It doesn't overlap with anything, so we can outline it.
558 // Each sequence is over [StartIt, EndIt].
559 // Save the candidate and its location.
560
561 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
562 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
563 MachineBasicBlock *MBB = StartIt->getParent();
564
565 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
566 EndIt, MBB, FunctionList.size(),
567 Mapper.MBBFlagsMap[MBB]);
568 }
569 }
570
571 // We've found something we might want to outline.
572 // Create an OutlinedFunction to store it and check if it'd be beneficial
573 // to outline.
574 if (CandidatesForRepeatedSeq.size() < 2)
575 continue;
576
577 // Arbitrarily choose a TII from the first candidate.
578 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
579 const TargetInstrInfo *TII =
580 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
581
582 OutlinedFunction OF =
583 TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
584
585 // If we deleted too many candidates, then there's nothing worth outlining.
586 // FIXME: This should take target-specified instruction sizes into account.
587 if (OF.Candidates.size() < 2)
588 continue;
589
590 // Is it better to outline this candidate than not?
591 if (OF.getBenefit() < 1) {
592 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
593 continue;
594 }
595
596 FunctionList.push_back(OF);
597 }
598 }
599
createOutlinedFunction(Module & M,OutlinedFunction & OF,InstructionMapper & Mapper,unsigned Name)600 MachineFunction *MachineOutliner::createOutlinedFunction(
601 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
602
603 // Create the function name. This should be unique.
604 // FIXME: We should have a better naming scheme. This should be stable,
605 // regardless of changes to the outliner's cost model/traversal order.
606 std::string FunctionName = "OUTLINED_FUNCTION_";
607 if (OutlineRepeatedNum > 0)
608 FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";
609 FunctionName += std::to_string(Name);
610
611 // Create the function using an IR-level function.
612 LLVMContext &C = M.getContext();
613 Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),
614 Function::ExternalLinkage, FunctionName, M);
615
616 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
617 // which gives us better results when we outline from linkonceodr functions.
618 F->setLinkage(GlobalValue::InternalLinkage);
619 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
620
621 // Set optsize/minsize, so we don't insert padding between outlined
622 // functions.
623 F->addFnAttr(Attribute::OptimizeForSize);
624 F->addFnAttr(Attribute::MinSize);
625
626 // Include target features from an arbitrary candidate for the outlined
627 // function. This makes sure the outlined function knows what kinds of
628 // instructions are going into it. This is fine, since all parent functions
629 // must necessarily support the instructions that are in the outlined region.
630 Candidate &FirstCand = OF.Candidates.front();
631 const Function &ParentFn = FirstCand.getMF()->getFunction();
632 if (ParentFn.hasFnAttribute("target-features"))
633 F->addFnAttr(ParentFn.getFnAttribute("target-features"));
634
635 // Set nounwind, so we don't generate eh_frame.
636 if (llvm::all_of(OF.Candidates, [](const outliner::Candidate &C) {
637 return C.getMF()->getFunction().hasFnAttribute(Attribute::NoUnwind);
638 }))
639 F->addFnAttr(Attribute::NoUnwind);
640
641 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
642 IRBuilder<> Builder(EntryBB);
643 Builder.CreateRetVoid();
644
645 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
646 MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
647 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
648 const TargetSubtargetInfo &STI = MF.getSubtarget();
649 const TargetInstrInfo &TII = *STI.getInstrInfo();
650
651 // Insert the new function into the module.
652 MF.insert(MF.begin(), &MBB);
653
654 MachineFunction *OriginalMF = FirstCand.front()->getMF();
655 const std::vector<MCCFIInstruction> &Instrs =
656 OriginalMF->getFrameInstructions();
657 for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
658 ++I) {
659 MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
660 if (I->isCFIInstruction()) {
661 unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
662 MCCFIInstruction CFI = Instrs[CFIIndex];
663 (void)MF.addFrameInst(CFI);
664 }
665 NewMI->dropMemRefs(MF);
666
667 // Don't keep debug information for outlined instructions.
668 NewMI->setDebugLoc(DebugLoc());
669 MBB.insert(MBB.end(), NewMI);
670 }
671
672 // Set normal properties for a late MachineFunction.
673 MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
674 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
675 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
676 MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
677 MF.getRegInfo().freezeReservedRegs(MF);
678
679 // Compute live-in set for outlined fn
680 const MachineRegisterInfo &MRI = MF.getRegInfo();
681 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
682 LivePhysRegs LiveIns(TRI);
683 for (auto &Cand : OF.Candidates) {
684 // Figure out live-ins at the first instruction.
685 MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
686 LivePhysRegs CandLiveIns(TRI);
687 CandLiveIns.addLiveOuts(OutlineBB);
688 for (const MachineInstr &MI :
689 reverse(make_range(Cand.front(), OutlineBB.end())))
690 CandLiveIns.stepBackward(MI);
691
692 // The live-in set for the outlined function is the union of the live-ins
693 // from all the outlining points.
694 for (MCPhysReg Reg : make_range(CandLiveIns.begin(), CandLiveIns.end()))
695 LiveIns.addReg(Reg);
696 }
697 addLiveIns(MBB, LiveIns);
698
699 TII.buildOutlinedFrame(MBB, MF, OF);
700
701 // If there's a DISubprogram associated with this outlined function, then
702 // emit debug info for the outlined function.
703 if (DISubprogram *SP = getSubprogramOrNull(OF)) {
704 // We have a DISubprogram. Get its DICompileUnit.
705 DICompileUnit *CU = SP->getUnit();
706 DIBuilder DB(M, true, CU);
707 DIFile *Unit = SP->getFile();
708 Mangler Mg;
709 // Get the mangled name of the function for the linkage name.
710 std::string Dummy;
711 llvm::raw_string_ostream MangledNameStream(Dummy);
712 Mg.getNameWithPrefix(MangledNameStream, F, false);
713
714 DISubprogram *OutlinedSP = DB.createFunction(
715 Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
716 Unit /* File */,
717 0 /* Line 0 is reserved for compiler-generated code. */,
718 DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
719 0, /* Line 0 is reserved for compiler-generated code. */
720 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
721 /* Outlined code is optimized code by definition. */
722 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
723
724 // Don't add any new variables to the subprogram.
725 DB.finalizeSubprogram(OutlinedSP);
726
727 // Attach subprogram to the function.
728 F->setSubprogram(OutlinedSP);
729 // We're done with the DIBuilder.
730 DB.finalize();
731 }
732
733 return &MF;
734 }
735
outline(Module & M,std::vector<OutlinedFunction> & FunctionList,InstructionMapper & Mapper,unsigned & OutlinedFunctionNum)736 bool MachineOutliner::outline(Module &M,
737 std::vector<OutlinedFunction> &FunctionList,
738 InstructionMapper &Mapper,
739 unsigned &OutlinedFunctionNum) {
740
741 bool OutlinedSomething = false;
742
743 // Sort by benefit. The most beneficial functions should be outlined first.
744 llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
745 const OutlinedFunction &RHS) {
746 return LHS.getBenefit() > RHS.getBenefit();
747 });
748
749 // Walk over each function, outlining them as we go along. Functions are
750 // outlined greedily, based off the sort above.
751 for (OutlinedFunction &OF : FunctionList) {
752 // If we outlined something that overlapped with a candidate in a previous
753 // step, then we can't outline from it.
754 erase_if(OF.Candidates, [&Mapper](Candidate &C) {
755 return std::any_of(
756 Mapper.UnsignedVec.begin() + C.getStartIdx(),
757 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
758 [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
759 });
760
761 // If we made it unbeneficial to outline this function, skip it.
762 if (OF.getBenefit() < 1)
763 continue;
764
765 // It's beneficial. Create the function and outline its sequence's
766 // occurrences.
767 OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
768 emitOutlinedFunctionRemark(OF);
769 FunctionsCreated++;
770 OutlinedFunctionNum++; // Created a function, move to the next name.
771 MachineFunction *MF = OF.MF;
772 const TargetSubtargetInfo &STI = MF->getSubtarget();
773 const TargetInstrInfo &TII = *STI.getInstrInfo();
774
775 // Replace occurrences of the sequence with calls to the new function.
776 for (Candidate &C : OF.Candidates) {
777 MachineBasicBlock &MBB = *C.getMBB();
778 MachineBasicBlock::iterator StartIt = C.front();
779 MachineBasicBlock::iterator EndIt = C.back();
780
781 // Insert the call.
782 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
783
784 // If the caller tracks liveness, then we need to make sure that
785 // anything we outline doesn't break liveness assumptions. The outlined
786 // functions themselves currently don't track liveness, but we should
787 // make sure that the ranges we yank things out of aren't wrong.
788 if (MBB.getParent()->getProperties().hasProperty(
789 MachineFunctionProperties::Property::TracksLiveness)) {
790 // The following code is to add implicit def operands to the call
791 // instruction. It also updates call site information for moved
792 // code.
793 SmallSet<Register, 2> UseRegs, DefRegs;
794 // Copy over the defs in the outlined range.
795 // First inst in outlined range <-- Anything that's defined in this
796 // ... .. range has to be added as an
797 // implicit Last inst in outlined range <-- def to the call
798 // instruction. Also remove call site information for outlined block
799 // of code. The exposed uses need to be copied in the outlined range.
800 for (MachineBasicBlock::reverse_iterator
801 Iter = EndIt.getReverse(),
802 Last = std::next(CallInst.getReverse());
803 Iter != Last; Iter++) {
804 MachineInstr *MI = &*Iter;
805 for (MachineOperand &MOP : MI->operands()) {
806 // Skip over anything that isn't a register.
807 if (!MOP.isReg())
808 continue;
809
810 if (MOP.isDef()) {
811 // Introduce DefRegs set to skip the redundant register.
812 DefRegs.insert(MOP.getReg());
813 if (UseRegs.count(MOP.getReg()))
814 // Since the regiester is modeled as defined,
815 // it is not necessary to be put in use register set.
816 UseRegs.erase(MOP.getReg());
817 } else if (!MOP.isUndef()) {
818 // Any register which is not undefined should
819 // be put in the use register set.
820 UseRegs.insert(MOP.getReg());
821 }
822 }
823 if (MI->isCandidateForCallSiteEntry())
824 MI->getMF()->eraseCallSiteInfo(MI);
825 }
826
827 for (const Register &I : DefRegs)
828 // If it's a def, add it to the call instruction.
829 CallInst->addOperand(
830 MachineOperand::CreateReg(I, true, /* isDef = true */
831 true /* isImp = true */));
832
833 for (const Register &I : UseRegs)
834 // If it's a exposed use, add it to the call instruction.
835 CallInst->addOperand(
836 MachineOperand::CreateReg(I, false, /* isDef = false */
837 true /* isImp = true */));
838 }
839
840 // Erase from the point after where the call was inserted up to, and
841 // including, the final instruction in the sequence.
842 // Erase needs one past the end, so we need std::next there too.
843 MBB.erase(std::next(StartIt), std::next(EndIt));
844
845 // Keep track of what we removed by marking them all as -1.
846 std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
847 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
848 [](unsigned &I) { I = static_cast<unsigned>(-1); });
849 OutlinedSomething = true;
850
851 // Statistics.
852 NumOutlined++;
853 }
854 }
855
856 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
857 return OutlinedSomething;
858 }
859
populateMapper(InstructionMapper & Mapper,Module & M,MachineModuleInfo & MMI)860 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
861 MachineModuleInfo &MMI) {
862 // Build instruction mappings for each function in the module. Start by
863 // iterating over each Function in M.
864 for (Function &F : M) {
865
866 // If there's nothing in F, then there's no reason to try and outline from
867 // it.
868 if (F.empty())
869 continue;
870
871 // There's something in F. Check if it has a MachineFunction associated with
872 // it.
873 MachineFunction *MF = MMI.getMachineFunction(F);
874
875 // If it doesn't, then there's nothing to outline from. Move to the next
876 // Function.
877 if (!MF)
878 continue;
879
880 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
881
882 if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
883 continue;
884
885 // We have a MachineFunction. Ask the target if it's suitable for outlining.
886 // If it isn't, then move on to the next Function in the module.
887 if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
888 continue;
889
890 // We have a function suitable for outlining. Iterate over every
891 // MachineBasicBlock in MF and try to map its instructions to a list of
892 // unsigned integers.
893 for (MachineBasicBlock &MBB : *MF) {
894 // If there isn't anything in MBB, then there's no point in outlining from
895 // it.
896 // If there are fewer than 2 instructions in the MBB, then it can't ever
897 // contain something worth outlining.
898 // FIXME: This should be based off of the maximum size in B of an outlined
899 // call versus the size in B of the MBB.
900 if (MBB.empty() || MBB.size() < 2)
901 continue;
902
903 // Check if MBB could be the target of an indirect branch. If it is, then
904 // we don't want to outline from it.
905 if (MBB.hasAddressTaken())
906 continue;
907
908 // MBB is suitable for outlining. Map it to a list of unsigneds.
909 Mapper.convertToUnsignedVec(MBB, *TII);
910 }
911 }
912 }
913
initSizeRemarkInfo(const Module & M,const MachineModuleInfo & MMI,StringMap<unsigned> & FunctionToInstrCount)914 void MachineOutliner::initSizeRemarkInfo(
915 const Module &M, const MachineModuleInfo &MMI,
916 StringMap<unsigned> &FunctionToInstrCount) {
917 // Collect instruction counts for every function. We'll use this to emit
918 // per-function size remarks later.
919 for (const Function &F : M) {
920 MachineFunction *MF = MMI.getMachineFunction(F);
921
922 // We only care about MI counts here. If there's no MachineFunction at this
923 // point, then there won't be after the outliner runs, so let's move on.
924 if (!MF)
925 continue;
926 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
927 }
928 }
929
emitInstrCountChangedRemark(const Module & M,const MachineModuleInfo & MMI,const StringMap<unsigned> & FunctionToInstrCount)930 void MachineOutliner::emitInstrCountChangedRemark(
931 const Module &M, const MachineModuleInfo &MMI,
932 const StringMap<unsigned> &FunctionToInstrCount) {
933 // Iterate over each function in the module and emit remarks.
934 // Note that we won't miss anything by doing this, because the outliner never
935 // deletes functions.
936 for (const Function &F : M) {
937 MachineFunction *MF = MMI.getMachineFunction(F);
938
939 // The outliner never deletes functions. If we don't have a MF here, then we
940 // didn't have one prior to outlining either.
941 if (!MF)
942 continue;
943
944 std::string Fname = std::string(F.getName());
945 unsigned FnCountAfter = MF->getInstructionCount();
946 unsigned FnCountBefore = 0;
947
948 // Check if the function was recorded before.
949 auto It = FunctionToInstrCount.find(Fname);
950
951 // Did we have a previously-recorded size? If yes, then set FnCountBefore
952 // to that.
953 if (It != FunctionToInstrCount.end())
954 FnCountBefore = It->second;
955
956 // Compute the delta and emit a remark if there was a change.
957 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
958 static_cast<int64_t>(FnCountBefore);
959 if (FnDelta == 0)
960 continue;
961
962 MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
963 MORE.emit([&]() {
964 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
965 DiagnosticLocation(), &MF->front());
966 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
967 << ": Function: "
968 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
969 << ": MI instruction count changed from "
970 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
971 FnCountBefore)
972 << " to "
973 << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
974 FnCountAfter)
975 << "; Delta: "
976 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
977 return R;
978 });
979 }
980 }
981
runOnModule(Module & M)982 bool MachineOutliner::runOnModule(Module &M) {
983 // Check if there's anything in the module. If it's empty, then there's
984 // nothing to outline.
985 if (M.empty())
986 return false;
987
988 // Number to append to the current outlined function.
989 unsigned OutlinedFunctionNum = 0;
990
991 OutlineRepeatedNum = 0;
992 if (!doOutline(M, OutlinedFunctionNum))
993 return false;
994
995 for (unsigned I = 0; I < OutlinerReruns; ++I) {
996 OutlinedFunctionNum = 0;
997 OutlineRepeatedNum++;
998 if (!doOutline(M, OutlinedFunctionNum)) {
999 LLVM_DEBUG({
1000 dbgs() << "Did not outline on iteration " << I + 2 << " out of "
1001 << OutlinerReruns + 1 << "\n";
1002 });
1003 break;
1004 }
1005 }
1006
1007 return true;
1008 }
1009
doOutline(Module & M,unsigned & OutlinedFunctionNum)1010 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
1011 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
1012
1013 // If the user passed -enable-machine-outliner=always or
1014 // -enable-machine-outliner, the pass will run on all functions in the module.
1015 // Otherwise, if the target supports default outlining, it will run on all
1016 // functions deemed by the target to be worth outlining from by default. Tell
1017 // the user how the outliner is running.
1018 LLVM_DEBUG({
1019 dbgs() << "Machine Outliner: Running on ";
1020 if (RunOnAllFunctions)
1021 dbgs() << "all functions";
1022 else
1023 dbgs() << "target-default functions";
1024 dbgs() << "\n";
1025 });
1026
1027 // If the user specifies that they want to outline from linkonceodrs, set
1028 // it here.
1029 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
1030 InstructionMapper Mapper;
1031
1032 // Prepare instruction mappings for the suffix tree.
1033 populateMapper(Mapper, M, MMI);
1034 std::vector<OutlinedFunction> FunctionList;
1035
1036 // Find all of the outlining candidates.
1037 findCandidates(Mapper, FunctionList);
1038
1039 // If we've requested size remarks, then collect the MI counts of every
1040 // function before outlining, and the MI counts after outlining.
1041 // FIXME: This shouldn't be in the outliner at all; it should ultimately be
1042 // the pass manager's responsibility.
1043 // This could pretty easily be placed in outline instead, but because we
1044 // really ultimately *don't* want this here, it's done like this for now
1045 // instead.
1046
1047 // Check if we want size remarks.
1048 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
1049 StringMap<unsigned> FunctionToInstrCount;
1050 if (ShouldEmitSizeRemarks)
1051 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1052
1053 // Outline each of the candidates and return true if something was outlined.
1054 bool OutlinedSomething =
1055 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1056
1057 // If we outlined something, we definitely changed the MI count of the
1058 // module. If we've asked for size remarks, then output them.
1059 // FIXME: This should be in the pass manager.
1060 if (ShouldEmitSizeRemarks && OutlinedSomething)
1061 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1062
1063 LLVM_DEBUG({
1064 if (!OutlinedSomething)
1065 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
1066 << " because no changes were found.\n";
1067 });
1068
1069 return OutlinedSomething;
1070 }
1071