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