1564 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// Replaces repeated sequences of instructions with function calls.11///12/// This works by placing every instruction from every basic block in a13/// suffix tree, and repeatedly querying that tree for repeated sequences of14/// instructions. If a sequence of instructions appears often, then it ought15/// to be beneficial to pull out into a function.16///17/// The MachineOutliner communicates with a given target using hooks defined in18/// TargetInstrInfo.h. The target supplies the outliner with information on how19/// a specific sequence of instructions should be outlined. This information20/// is used to deduce the number of instructions necessary to21///22/// * Create an outlined function23/// * Call that outlined function24///25/// Targets must implement26/// * getOutliningCandidateInfo27/// * buildOutlinedFrame28/// * insertOutlinedCall29/// * isFunctionSafeToOutlineFrom30///31/// in order to make use of the MachineOutliner.32///33/// This was originally presented at the 2016 LLVM Developers' Meeting in the34/// talk "Reducing Code Size Using Outlining". For a high-level overview of35/// how this pass works, the talk is available on YouTube at36///37/// https://www.youtube.com/watch?v=yorld-WSOeU38///39/// The slides for the talk are available at40///41/// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf42///43/// The talk provides an overview of how the outliner finds candidates and44/// ultimately outlines them. It describes how the main data structure for this45/// pass, the suffix tree, is queried and purged for candidates. It also gives46/// a simplified suffix tree construction algorithm for suffix trees based off47/// of the algorithm actually used here, Ukkonen's algorithm.48///49/// For the original RFC for this pass, please see50///51/// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html52///53/// For more information on the suffix tree data structure, please see54/// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf55///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/BlockFrequencyInfo.h"63#include "llvm/Analysis/ModuleSummaryAnalysis.h"64#include "llvm/Analysis/OptimizationRemarkEmitter.h"65#include "llvm/Analysis/ProfileSummaryInfo.h"66#include "llvm/CGData/CodeGenDataReader.h"67#include "llvm/CodeGen/LivePhysRegs.h"68#include "llvm/CodeGen/MachineModuleInfo.h"69#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"70#include "llvm/CodeGen/Passes.h"71#include "llvm/CodeGen/TargetInstrInfo.h"72#include "llvm/CodeGen/TargetPassConfig.h"73#include "llvm/CodeGen/TargetSubtargetInfo.h"74#include "llvm/IR/DIBuilder.h"75#include "llvm/IR/IRBuilder.h"76#include "llvm/IR/Mangler.h"77#include "llvm/IR/Module.h"78#include "llvm/InitializePasses.h"79#include "llvm/Support/CommandLine.h"80#include "llvm/Support/Debug.h"81#include "llvm/Support/SuffixTree.h"82#include "llvm/Support/raw_ostream.h"83#include "llvm/Target/TargetMachine.h"84#include "llvm/Transforms/Utils/ModuleUtils.h"85#include <tuple>86#include <vector>87 88#define DEBUG_TYPE "machine-outliner"89 90using namespace llvm;91using namespace ore;92using namespace outliner;93 94// Statistics for outlined functions.95STATISTIC(NumOutlined, "Number of candidates outlined");96STATISTIC(FunctionsCreated, "Number of functions created");97 98// Statistics for instruction mapping.99STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped");100STATISTIC(NumIllegalInUnsignedVec,101 "Unoutlinable instructions mapped + number of sentinel values");102STATISTIC(NumSentinels, "Sentinel values inserted during mapping");103STATISTIC(NumInvisible,104 "Invisible instructions skipped during mapping");105STATISTIC(UnsignedVecSize,106 "Total number of instructions mapped and saved to mapping vector");107STATISTIC(StableHashAttempts,108 "Count of hashing attempts made for outlined functions");109STATISTIC(StableHashDropped,110 "Count of unsuccessful hashing attempts for outlined functions");111STATISTIC(NumRemovedLOHs, "Total number of Linker Optimization Hints removed");112STATISTIC(NumPGOBlockedOutlined,113 "Number of times outlining was blocked by PGO");114STATISTIC(NumPGOAllowedCold,115 "Number of times outlining was allowed from cold functions");116STATISTIC(NumPGOConservativeBlockedOutlined,117 "Number of times outlining was blocked conservatively when profile "118 "counts were missing");119STATISTIC(NumPGOOptimisticOutlined,120 "Number of times outlining was allowed optimistically when profile "121 "counts were missing");122 123// Set to true if the user wants the outliner to run on linkonceodr linkage124// functions. This is false by default because the linker can dedupe linkonceodr125// functions. Since the outliner is confined to a single module (modulo LTO),126// this is off by default. It should, however, be the default behaviour in127// LTO.128static cl::opt<bool> EnableLinkOnceODROutlining(129 "enable-linkonceodr-outlining", cl::Hidden,130 cl::desc("Enable the machine outliner on linkonceodr functions"),131 cl::init(false));132 133/// Number of times to re-run the outliner. This is not the total number of runs134/// as the outliner will run at least one time. The default value is set to 0,135/// meaning the outliner will run one time and rerun zero times after that.136static cl::opt<unsigned> OutlinerReruns(137 "machine-outliner-reruns", cl::init(0), cl::Hidden,138 cl::desc(139 "Number of times to rerun the outliner after the initial outline"));140 141static cl::opt<unsigned> OutlinerBenefitThreshold(142 "outliner-benefit-threshold", cl::init(1), cl::Hidden,143 cl::desc(144 "The minimum size in bytes before an outlining candidate is accepted"));145 146static cl::opt<bool> OutlinerLeafDescendants(147 "outliner-leaf-descendants", cl::init(true), cl::Hidden,148 cl::desc("Consider all leaf descendants of internal nodes of the suffix "149 "tree as candidates for outlining (if false, only leaf children "150 "are considered)"));151 152static cl::opt<bool>153 DisableGlobalOutlining("disable-global-outlining", cl::Hidden,154 cl::desc("Disable global outlining only by ignoring "155 "the codegen data generation or use"),156 cl::init(false));157 158static cl::opt<bool> AppendContentHashToOutlinedName(159 "append-content-hash-outlined-name", cl::Hidden,160 cl::desc("This appends the content hash to the globally outlined function "161 "name. It's beneficial for enhancing the precision of the stable "162 "hash and for ordering the outlined functions."),163 cl::init(true));164 165namespace {166 167/// Maps \p MachineInstrs to unsigned integers and stores the mappings.168struct InstructionMapper {169 const MachineModuleInfo &MMI;170 171 /// The next available integer to assign to a \p MachineInstr that172 /// cannot be outlined.173 ///174 /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.175 unsigned IllegalInstrNumber = -3;176 177 /// The next available integer to assign to a \p MachineInstr that can178 /// be outlined.179 unsigned LegalInstrNumber = 0;180 181 /// Correspondence from \p MachineInstrs to unsigned integers.182 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>183 InstructionIntegerMap;184 185 /// Correspondence between \p MachineBasicBlocks and target-defined flags.186 DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;187 188 /// The vector of unsigned integers that the module is mapped to.189 SmallVector<unsigned> UnsignedVec;190 191 /// Stores the location of the instruction associated with the integer192 /// at index i in \p UnsignedVec for each index i.193 SmallVector<MachineBasicBlock::iterator> InstrList;194 195 // Set if we added an illegal number in the previous step.196 // Since each illegal number is unique, we only need one of them between197 // each range of legal numbers. This lets us make sure we don't add more198 // than one illegal number per range.199 bool AddedIllegalLastTime = false;200 201 /// Maps \p *It to a legal integer.202 ///203 /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,204 /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.205 ///206 /// \returns The integer that \p *It was mapped to.207 unsigned mapToLegalUnsigned(208 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,209 bool &HaveLegalRange, unsigned &NumLegalInBlock,210 SmallVector<unsigned> &UnsignedVecForMBB,211 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {212 // We added something legal, so we should unset the AddedLegalLastTime213 // flag.214 AddedIllegalLastTime = false;215 216 // If we have at least two adjacent legal instructions (which may have217 // invisible instructions in between), remember that.218 if (CanOutlineWithPrevInstr)219 HaveLegalRange = true;220 CanOutlineWithPrevInstr = true;221 222 // Keep track of the number of legal instructions we insert.223 NumLegalInBlock++;224 225 // Get the integer for this instruction or give it the current226 // LegalInstrNumber.227 InstrListForMBB.push_back(It);228 MachineInstr &MI = *It;229 bool WasInserted;230 DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator231 ResultIt;232 std::tie(ResultIt, WasInserted) =233 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));234 unsigned MINumber = ResultIt->second;235 236 // There was an insertion.237 if (WasInserted)238 LegalInstrNumber++;239 240 UnsignedVecForMBB.push_back(MINumber);241 242 // Make sure we don't overflow or use any integers reserved by the DenseMap.243 if (LegalInstrNumber >= IllegalInstrNumber)244 report_fatal_error("Instruction mapping overflow!");245 246 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&247 "Tried to assign DenseMap tombstone or empty key to instruction.");248 assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&249 "Tried to assign DenseMap tombstone or empty key to instruction.");250 251 // Statistics.252 ++NumLegalInUnsignedVec;253 return MINumber;254 }255 256 /// Maps \p *It to an illegal integer.257 ///258 /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p259 /// IllegalInstrNumber.260 ///261 /// \returns The integer that \p *It was mapped to.262 unsigned mapToIllegalUnsigned(263 MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,264 SmallVector<unsigned> &UnsignedVecForMBB,265 SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) {266 // Can't outline an illegal instruction. Set the flag.267 CanOutlineWithPrevInstr = false;268 269 // Only add one illegal number per range of legal numbers.270 if (AddedIllegalLastTime)271 return IllegalInstrNumber;272 273 // Remember that we added an illegal number last time.274 AddedIllegalLastTime = true;275 unsigned MINumber = IllegalInstrNumber;276 277 InstrListForMBB.push_back(It);278 UnsignedVecForMBB.push_back(IllegalInstrNumber);279 IllegalInstrNumber--;280 // Statistics.281 ++NumIllegalInUnsignedVec;282 283 assert(LegalInstrNumber < IllegalInstrNumber &&284 "Instruction mapping overflow!");285 286 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&287 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");288 289 assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&290 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");291 292 return MINumber;293 }294 295 /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds296 /// and appends it to \p UnsignedVec and \p InstrList.297 ///298 /// Two instructions are assigned the same integer if they are identical.299 /// If an instruction is deemed unsafe to outline, then it will be assigned an300 /// unique integer. The resulting mapping is placed into a suffix tree and301 /// queried for candidates.302 ///303 /// \param MBB The \p MachineBasicBlock to be translated into integers.304 /// \param TII \p TargetInstrInfo for the function.305 void convertToUnsignedVec(MachineBasicBlock &MBB,306 const TargetInstrInfo &TII) {307 LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName()308 << "' to unsigned vector ***\n");309 unsigned Flags = 0;310 311 // Don't even map in this case.312 if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))313 return;314 315 auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags);316 LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size()317 << " outlinable range(s)\n");318 if (OutlinableRanges.empty())319 return;320 321 // Store info for the MBB for later outlining.322 MBBFlagsMap[&MBB] = Flags;323 324 MachineBasicBlock::iterator It = MBB.begin();325 326 // The number of instructions in this block that will be considered for327 // outlining.328 unsigned NumLegalInBlock = 0;329 330 // True if we have at least two legal instructions which aren't separated331 // by an illegal instruction.332 bool HaveLegalRange = false;333 334 // True if we can perform outlining given the last mapped (non-invisible)335 // instruction. This lets us know if we have a legal range.336 bool CanOutlineWithPrevInstr = false;337 338 // FIXME: Should this all just be handled in the target, rather than using339 // repeated calls to getOutliningType?340 SmallVector<unsigned> UnsignedVecForMBB;341 SmallVector<MachineBasicBlock::iterator> InstrListForMBB;342 343 LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n");344 for (auto &OutlinableRange : OutlinableRanges) {345 auto OutlinableRangeBegin = OutlinableRange.first;346 auto OutlinableRangeEnd = OutlinableRange.second;347#ifndef NDEBUG348 LLVM_DEBUG(349 dbgs() << "Mapping "350 << std::distance(OutlinableRangeBegin, OutlinableRangeEnd)351 << " instruction range\n");352 // Everything outside of an outlinable range is illegal.353 unsigned NumSkippedInRange = 0;354#endif355 for (; It != OutlinableRangeBegin; ++It) {356#ifndef NDEBUG357 ++NumSkippedInRange;358#endif359 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,360 InstrListForMBB);361 }362#ifndef NDEBUG363 LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange364 << " instructions outside outlinable range\n");365#endif366 assert(It != MBB.end() && "Should still have instructions?");367 // `It` is now positioned at the beginning of a range of instructions368 // which may be outlinable. Check if each instruction is known to be safe.369 for (; It != OutlinableRangeEnd; ++It) {370 // Keep track of where this instruction is in the module.371 switch (TII.getOutliningType(MMI, It, Flags)) {372 case InstrType::Illegal:373 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,374 InstrListForMBB);375 break;376 377 case InstrType::Legal:378 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,379 NumLegalInBlock, UnsignedVecForMBB,380 InstrListForMBB);381 break;382 383 case InstrType::LegalTerminator:384 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,385 NumLegalInBlock, UnsignedVecForMBB,386 InstrListForMBB);387 // The instruction also acts as a terminator, so we have to record388 // that in the string.389 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,390 InstrListForMBB);391 break;392 393 case InstrType::Invisible:394 // Normally this is set by mapTo(Blah)Unsigned, but we just want to395 // skip this instruction. So, unset the flag here.396 ++NumInvisible;397 AddedIllegalLastTime = false;398 break;399 }400 }401 }402 403 LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n");404 405 // Are there enough legal instructions in the block for outlining to be406 // possible?407 if (HaveLegalRange) {408 // After we're done every insertion, uniquely terminate this part of the409 // "string". This makes sure we won't match across basic block or function410 // boundaries since the "end" is encoded uniquely and thus appears in no411 // repeated substring.412 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,413 InstrListForMBB);414 ++NumSentinels;415 append_range(InstrList, InstrListForMBB);416 append_range(UnsignedVec, UnsignedVecForMBB);417 }418 }419 420 InstructionMapper(const MachineModuleInfo &MMI_) : MMI(MMI_) {421 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't422 // changed.423 static_assert(DenseMapInfo<unsigned>::getEmptyKey() ==424 static_cast<unsigned>(-1));425 static_assert(DenseMapInfo<unsigned>::getTombstoneKey() ==426 static_cast<unsigned>(-2));427 }428};429 430/// An interprocedural pass which finds repeated sequences of431/// instructions and replaces them with calls to functions.432///433/// Each instruction is mapped to an unsigned integer and placed in a string.434/// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree435/// is then repeatedly queried for repeated sequences of instructions. Each436/// non-overlapping repeated sequence is then placed in its own437/// \p MachineFunction and each instance is then replaced with a call to that438/// function.439struct MachineOutliner : public ModulePass {440 441 static char ID;442 443 MachineModuleInfo *MMI = nullptr;444 const TargetMachine *TM = nullptr;445 446 /// Set to true if the outliner should consider functions with447 /// linkonceodr linkage.448 bool OutlineFromLinkOnceODRs = false;449 450 /// The current repeat number of machine outlining.451 unsigned OutlineRepeatedNum = 0;452 453 /// The mode for whether to run the outliner454 /// Set to always-outline by default for compatibility with llc's -run-pass455 /// option.456 RunOutliner RunOutlinerMode = RunOutliner::AlwaysOutline;457 458 /// This is a compact representation of hash sequences of outlined functions.459 /// It is used when OutlinerMode = CGDataMode::Write.460 /// The resulting hash tree will be emitted into __llvm_outlined section461 /// which will be dead-stripped not going to the final binary.462 /// A post-process using llvm-cgdata, lld, or ThinLTO can merge them into463 /// a global oulined hash tree for the subsequent codegen.464 std::unique_ptr<OutlinedHashTree> LocalHashTree;465 466 /// The mode of the outliner.467 /// When is's CGDataMode::None, candidates are populated with the suffix tree468 /// within a module and outlined.469 /// When it's CGDataMode::Write, in addition to CGDataMode::None, the hash470 /// sequences of outlined functions are published into LocalHashTree.471 /// When it's CGDataMode::Read, candidates are populated with the global472 /// outlined hash tree that has been built by the previous codegen.473 CGDataMode OutlinerMode = CGDataMode::None;474 475 StringRef getPassName() const override { return "Machine Outliner"; }476 477 void getAnalysisUsage(AnalysisUsage &AU) const override {478 AU.addRequired<MachineModuleInfoWrapperPass>();479 AU.addRequired<TargetPassConfig>();480 AU.addPreserved<MachineModuleInfoWrapperPass>();481 AU.addUsedIfAvailable<ImmutableModuleSummaryIndexWrapperPass>();482 if (RunOutlinerMode == RunOutliner::OptimisticPGO ||483 RunOutlinerMode == RunOutliner::ConservativePGO) {484 AU.addRequired<BlockFrequencyInfoWrapperPass>();485 AU.addRequired<ProfileSummaryInfoWrapperPass>();486 }487 AU.setPreservesAll();488 ModulePass::getAnalysisUsage(AU);489 }490 491 MachineOutliner() : ModulePass(ID) {492 initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());493 }494 495 /// Remark output explaining that not outlining a set of candidates would be496 /// better than outlining that set.497 void emitNotOutliningCheaperRemark(498 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,499 OutlinedFunction &OF);500 501 /// Remark output explaining that a function was outlined.502 void emitOutlinedFunctionRemark(OutlinedFunction &OF);503 504 /// Find all repeated substrings that satisfy the outlining cost model by505 /// constructing a suffix tree.506 ///507 /// If a substring appears at least twice, then it must be represented by508 /// an internal node which appears in at least two suffixes. Each suffix509 /// is represented by a leaf node. To do this, we visit each internal node510 /// in the tree, using the leaf children of each internal node. If an511 /// internal node represents a beneficial substring, then we use each of512 /// its leaf children to find the locations of its substring.513 ///514 /// \param Mapper Contains outlining mapping information.515 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions516 /// each type of candidate.517 void518 findCandidates(InstructionMapper &Mapper,519 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList);520 521 /// Find all repeated substrings that match in the global outlined hash522 /// tree built from the previous codegen.523 ///524 /// \param Mapper Contains outlining mapping information.525 /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions526 /// each type of candidate.527 void findGlobalCandidates(528 InstructionMapper &Mapper,529 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList);530 531 /// Replace the sequences of instructions represented by \p OutlinedFunctions532 /// with calls to functions.533 ///534 /// \param M The module we are outlining from.535 /// \param FunctionList A list of functions to be inserted into the module.536 /// \param Mapper Contains the instruction mappings for the module.537 /// \param[out] OutlinedFunctionNum The outlined function number.538 bool outline(Module &M,539 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList,540 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);541 542 /// Creates a function for \p OF and inserts it into the module.543 MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,544 InstructionMapper &Mapper,545 unsigned Name);546 547 /// Compute and publish the stable hash sequence of instructions in the548 /// outlined function, \p MF. The parameter \p CandSize represents the number549 /// of candidates that have identical instruction sequences to \p MF.550 void computeAndPublishHashSequence(MachineFunction &MF, unsigned CandSize);551 552 /// Initialize the outliner mode.553 void initializeOutlinerMode(const Module &M);554 555 /// Emit the outlined hash tree into __llvm_outline section.556 void emitOutlinedHashTree(Module &M);557 558 /// Calls 'doOutline()' 1 + OutlinerReruns times.559 bool runOnModule(Module &M) override;560 561 /// Construct a suffix tree on the instructions in \p M and outline repeated562 /// strings from that tree.563 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);564 565 /// Return a DISubprogram for OF if one exists, and null otherwise. Helper566 /// function for remark emission.567 DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {568 for (const Candidate &C : OF.Candidates)569 if (MachineFunction *MF = C.getMF())570 if (DISubprogram *SP = MF->getFunction().getSubprogram())571 return SP;572 return nullptr;573 }574 575 /// Populate and \p InstructionMapper with instruction-to-integer mappings.576 /// These are used to construct a suffix tree.577 void populateMapper(InstructionMapper &Mapper, Module &M);578 579 /// Initialize information necessary to output a size remark.580 /// FIXME: This should be handled by the pass manager, not the outliner.581 /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy582 /// pass manager.583 void initSizeRemarkInfo(const Module &M,584 StringMap<unsigned> &FunctionToInstrCount);585 586 /// Emit the remark.587 // FIXME: This should be handled by the pass manager, not the outliner.588 void589 emitInstrCountChangedRemark(const Module &M,590 const StringMap<unsigned> &FunctionToInstrCount);591};592} // Anonymous namespace.593 594char MachineOutliner::ID = 0;595 596ModulePass *llvm::createMachineOutlinerPass(RunOutliner RunOutlinerMode) {597 MachineOutliner *OL = new MachineOutliner();598 OL->RunOutlinerMode = RunOutlinerMode;599 return OL;600}601 602INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,603 false)604 605void MachineOutliner::emitNotOutliningCheaperRemark(606 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,607 OutlinedFunction &OF) {608 // FIXME: Right now, we arbitrarily choose some Candidate from the609 // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.610 // We should probably sort these by function name or something to make sure611 // the remarks are stable.612 Candidate &C = CandidatesForRepeatedSeq.front();613 MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);614 MORE.emit([&]() {615 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",616 C.front().getDebugLoc(), C.getMBB());617 R << "Did not outline " << NV("Length", StringLen) << " instructions"618 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())619 << " locations."620 << " Bytes from outlining all occurrences ("621 << NV("OutliningCost", OF.getOutliningCost()) << ")"622 << " >= Unoutlined instruction bytes ("623 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"624 << " (Also found at: ";625 626 // Tell the user the other places the candidate was found.627 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {628 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),629 CandidatesForRepeatedSeq[i].front().getDebugLoc());630 if (i != e - 1)631 R << ", ";632 }633 634 R << ")";635 return R;636 });637}638 639void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {640 MachineBasicBlock *MBB = &*OF.MF->begin();641 MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);642 MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",643 MBB->findDebugLoc(MBB->begin()), MBB);644 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "645 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "646 << "from " << NV("NumOccurrences", OF.getOccurrenceCount())647 << " locations. "648 << "(Found at: ";649 650 // Tell the user the other places the candidate was found.651 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {652 653 R << NV((Twine("StartLoc") + Twine(i)).str(),654 OF.Candidates[i].front().getDebugLoc());655 if (i != e - 1)656 R << ", ";657 }658 659 R << ")";660 661 MORE.emit(R);662}663 664struct MatchedEntry {665 unsigned StartIdx;666 unsigned EndIdx;667 unsigned Count;668 MatchedEntry(unsigned StartIdx, unsigned EndIdx, unsigned Count)669 : StartIdx(StartIdx), EndIdx(EndIdx), Count(Count) {}670 MatchedEntry() = delete;671};672 673// Find all matches in the global outlined hash tree.674// It's quadratic complexity in theory, but it's nearly linear in practice675// since the length of outlined sequences are small within a block.676static SmallVector<MatchedEntry> getMatchedEntries(InstructionMapper &Mapper) {677 auto &InstrList = Mapper.InstrList;678 auto &UnsignedVec = Mapper.UnsignedVec;679 680 SmallVector<MatchedEntry> MatchedEntries;681 auto Size = UnsignedVec.size();682 683 // Get the global outlined hash tree built from the previous run.684 assert(cgdata::hasOutlinedHashTree());685 const auto *RootNode = cgdata::getOutlinedHashTree()->getRoot();686 687 auto getValidInstr = [&](unsigned Index) -> const MachineInstr * {688 if (UnsignedVec[Index] >= Mapper.LegalInstrNumber)689 return nullptr;690 return &(*InstrList[Index]);691 };692 693 auto getStableHashAndFollow =694 [](const MachineInstr &MI, const HashNode *CurrNode) -> const HashNode * {695 stable_hash StableHash = stableHashValue(MI);696 if (!StableHash)697 return nullptr;698 auto It = CurrNode->Successors.find(StableHash);699 return (It == CurrNode->Successors.end()) ? nullptr : It->second.get();700 };701 702 for (unsigned I = 0; I < Size; ++I) {703 const MachineInstr *MI = getValidInstr(I);704 if (!MI || MI->isDebugInstr())705 continue;706 const HashNode *CurrNode = getStableHashAndFollow(*MI, RootNode);707 if (!CurrNode)708 continue;709 710 for (unsigned J = I + 1; J < Size; ++J) {711 const MachineInstr *MJ = getValidInstr(J);712 if (!MJ)713 break;714 // Skip debug instructions as we did for the outlined function.715 if (MJ->isDebugInstr())716 continue;717 CurrNode = getStableHashAndFollow(*MJ, CurrNode);718 if (!CurrNode)719 break;720 // Even with a match ending with a terminal, we continue finding721 // matches to populate all candidates.722 if (auto Count = CurrNode->Terminals)723 MatchedEntries.emplace_back(I, J, *Count);724 }725 }726 727 return MatchedEntries;728}729 730void MachineOutliner::findGlobalCandidates(731 InstructionMapper &Mapper,732 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) {733 FunctionList.clear();734 auto &InstrList = Mapper.InstrList;735 auto &MBBFlagsMap = Mapper.MBBFlagsMap;736 737 std::vector<Candidate> CandidatesForRepeatedSeq;738 for (auto &ME : getMatchedEntries(Mapper)) {739 CandidatesForRepeatedSeq.clear();740 MachineBasicBlock::iterator StartIt = InstrList[ME.StartIdx];741 MachineBasicBlock::iterator EndIt = InstrList[ME.EndIdx];742 auto Length = ME.EndIdx - ME.StartIdx + 1;743 MachineBasicBlock *MBB = StartIt->getParent();744 CandidatesForRepeatedSeq.emplace_back(ME.StartIdx, Length, StartIt, EndIt,745 MBB, FunctionList.size(),746 MBBFlagsMap[MBB]);747 const TargetInstrInfo *TII =748 MBB->getParent()->getSubtarget().getInstrInfo();749 unsigned MinRepeats = 1;750 std::optional<std::unique_ptr<OutlinedFunction>> OF =751 TII->getOutliningCandidateInfo(*MMI, CandidatesForRepeatedSeq,752 MinRepeats);753 if (!OF.has_value() || OF.value()->Candidates.empty())754 continue;755 // We create a global candidate for each match.756 assert(OF.value()->Candidates.size() == MinRepeats);757 FunctionList.emplace_back(std::make_unique<GlobalOutlinedFunction>(758 std::move(OF.value()), ME.Count));759 }760}761 762void MachineOutliner::findCandidates(763 InstructionMapper &Mapper,764 std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) {765 FunctionList.clear();766 SuffixTree ST(Mapper.UnsignedVec, OutlinerLeafDescendants);767 768 // First, find all of the repeated substrings in the tree of minimum length769 // 2.770 std::vector<Candidate> CandidatesForRepeatedSeq;771 LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n");772 LLVM_DEBUG(773 dbgs() << "Searching for overlaps in all repeated sequences...\n");774 for (SuffixTree::RepeatedSubstring &RS : ST) {775 CandidatesForRepeatedSeq.clear();776 unsigned StringLen = RS.Length;777 LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n");778 // Debug code to keep track of how many candidates we removed.779#ifndef NDEBUG780 unsigned NumDiscarded = 0;781 unsigned NumKept = 0;782#endif783 // Sort the start indices so that we can efficiently check if candidates784 // overlap with the ones we've already found for this sequence.785 llvm::sort(RS.StartIndices);786 for (const unsigned &StartIdx : RS.StartIndices) {787 // Trick: Discard some candidates that would be incompatible with the788 // ones we've already found for this sequence. This will save us some789 // work in candidate selection.790 //791 // If two candidates overlap, then we can't outline them both. This792 // happens when we have candidates that look like, say793 //794 // AA (where each "A" is an instruction).795 //796 // We might have some portion of the module that looks like this:797 // AAAAAA (6 A's)798 //799 // In this case, there are 5 different copies of "AA" in this range, but800 // at most 3 can be outlined. If only outlining 3 of these is going to801 // be unbeneficial, then we ought to not bother.802 //803 // Note that two things DON'T overlap when they look like this:804 // start1...end1 .... start2...end2805 // That is, one must either806 // * End before the other starts807 // * Start after the other ends808 unsigned EndIdx = StartIdx + StringLen - 1;809 if (!CandidatesForRepeatedSeq.empty() &&810 StartIdx <= CandidatesForRepeatedSeq.back().getEndIdx()) {811#ifndef NDEBUG812 ++NumDiscarded;813 LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx << ", "814 << EndIdx << "]; overlaps with candidate @ ["815 << CandidatesForRepeatedSeq.back().getStartIdx()816 << ", " << CandidatesForRepeatedSeq.back().getEndIdx()817 << "]\n");818#endif819 continue;820 }821 // It doesn't overlap with anything, so we can outline it.822 // Each sequence is over [StartIt, EndIt].823 // Save the candidate and its location.824#ifndef NDEBUG825 ++NumKept;826#endif827 MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];828 MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];829 MachineBasicBlock *MBB = StartIt->getParent();830 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, EndIt,831 MBB, FunctionList.size(),832 Mapper.MBBFlagsMap[MBB]);833 }834#ifndef NDEBUG835 LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded836 << "\n");837 LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n");838#endif839 unsigned MinRepeats = 2;840 841 // We've found something we might want to outline.842 // Create an OutlinedFunction to store it and check if it'd be beneficial843 // to outline.844 if (CandidatesForRepeatedSeq.size() < MinRepeats)845 continue;846 847 // Arbitrarily choose a TII from the first candidate.848 // FIXME: Should getOutliningCandidateInfo move to TargetMachine?849 const TargetInstrInfo *TII =850 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();851 852 std::optional<std::unique_ptr<OutlinedFunction>> OF =853 TII->getOutliningCandidateInfo(*MMI, CandidatesForRepeatedSeq,854 MinRepeats);855 856 // If we deleted too many candidates, then there's nothing worth outlining.857 // FIXME: This should take target-specified instruction sizes into account.858 if (!OF.has_value() || OF.value()->Candidates.size() < MinRepeats)859 continue;860 861 // Is it better to outline this candidate than not?862 if (OF.value()->getBenefit() < OutlinerBenefitThreshold) {863 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq,864 *OF.value());865 continue;866 }867 868 FunctionList.emplace_back(std::move(OF.value()));869 }870}871 872void MachineOutliner::computeAndPublishHashSequence(MachineFunction &MF,873 unsigned CandSize) {874 // Compute the hash sequence for the outlined function.875 SmallVector<stable_hash> OutlinedHashSequence;876 for (auto &MBB : MF) {877 for (auto &NewMI : MBB) {878 stable_hash Hash = stableHashValue(NewMI);879 if (!Hash) {880 OutlinedHashSequence.clear();881 break;882 }883 OutlinedHashSequence.push_back(Hash);884 }885 }886 887 // Append a unique name based on the non-empty hash sequence.888 if (AppendContentHashToOutlinedName && !OutlinedHashSequence.empty()) {889 auto CombinedHash = stable_hash_combine(OutlinedHashSequence);890 auto NewName =891 MF.getName().str() + ".content." + std::to_string(CombinedHash);892 MF.getFunction().setName(NewName);893 }894 895 // Publish the non-empty hash sequence to the local hash tree.896 if (OutlinerMode == CGDataMode::Write) {897 StableHashAttempts++;898 if (!OutlinedHashSequence.empty())899 LocalHashTree->insert({OutlinedHashSequence, CandSize});900 else901 StableHashDropped++;902 }903}904 905MachineFunction *MachineOutliner::createOutlinedFunction(906 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {907 908 // Create the function name. This should be unique.909 // FIXME: We should have a better naming scheme. This should be stable,910 // regardless of changes to the outliner's cost model/traversal order.911 std::string FunctionName = "OUTLINED_FUNCTION_";912 if (OutlineRepeatedNum > 0)913 FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";914 FunctionName += std::to_string(Name);915 LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n");916 917 // Create the function using an IR-level function.918 LLVMContext &C = M.getContext();919 Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),920 Function::ExternalLinkage, FunctionName, M);921 922 // NOTE: If this is linkonceodr, then we can take advantage of linker deduping923 // which gives us better results when we outline from linkonceodr functions.924 F->setLinkage(GlobalValue::InternalLinkage);925 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);926 927 // Set optsize/minsize, so we don't insert padding between outlined928 // functions.929 F->addFnAttr(Attribute::OptimizeForSize);930 F->addFnAttr(Attribute::MinSize);931 932 Candidate &FirstCand = OF.Candidates.front();933 const TargetInstrInfo &TII =934 *FirstCand.getMF()->getSubtarget().getInstrInfo();935 936 TII.mergeOutliningCandidateAttributes(*F, OF.Candidates);937 938 // Set uwtable, so we generate eh_frame.939 UWTableKind UW = std::accumulate(940 OF.Candidates.cbegin(), OF.Candidates.cend(), UWTableKind::None,941 [](UWTableKind K, const outliner::Candidate &C) {942 return std::max(K, C.getMF()->getFunction().getUWTableKind());943 });944 F->setUWTableKind(UW);945 946 BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);947 IRBuilder<> Builder(EntryBB);948 Builder.CreateRetVoid();949 950 MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();951 MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);952 MF.setIsOutlined(true);953 MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();954 955 // Insert the new function into the module.956 MF.insert(MF.begin(), &MBB);957 958 MachineFunction *OriginalMF = FirstCand.front().getMF();959 const std::vector<MCCFIInstruction> &Instrs =960 OriginalMF->getFrameInstructions();961 for (auto &MI : FirstCand) {962 if (MI.isDebugInstr())963 continue;964 965 // Don't keep debug information for outlined instructions.966 auto DL = DebugLoc();967 if (MI.isCFIInstruction()) {968 unsigned CFIIndex = MI.getOperand(0).getCFIIndex();969 MCCFIInstruction CFI = Instrs[CFIIndex];970 BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))971 .addCFIIndex(MF.addFrameInst(CFI));972 } else {973 MachineInstr &NewMI = TII.duplicate(MBB, MBB.end(), MI);974 NewMI.dropMemRefs(MF);975 NewMI.setDebugLoc(DL);976 }977 }978 979 if (OutlinerMode != CGDataMode::None)980 computeAndPublishHashSequence(MF, OF.Candidates.size());981 982 // Set normal properties for a late MachineFunction.983 MF.getProperties().resetIsSSA();984 MF.getProperties().setNoPHIs();985 MF.getProperties().setNoVRegs();986 MF.getProperties().setTracksLiveness();987 MF.getRegInfo().freezeReservedRegs();988 989 // Compute live-in set for outlined fn990 const MachineRegisterInfo &MRI = MF.getRegInfo();991 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();992 LivePhysRegs LiveIns(TRI);993 for (auto &Cand : OF.Candidates) {994 // Figure out live-ins at the first instruction.995 MachineBasicBlock &OutlineBB = *Cand.front().getParent();996 LivePhysRegs CandLiveIns(TRI);997 CandLiveIns.addLiveOuts(OutlineBB);998 for (const MachineInstr &MI :999 reverse(make_range(Cand.begin(), OutlineBB.end())))1000 CandLiveIns.stepBackward(MI);1001 1002 // The live-in set for the outlined function is the union of the live-ins1003 // from all the outlining points.1004 for (MCPhysReg Reg : CandLiveIns)1005 LiveIns.addReg(Reg);1006 }1007 addLiveIns(MBB, LiveIns);1008 1009 TII.buildOutlinedFrame(MBB, MF, OF);1010 1011 // If there's a DISubprogram associated with this outlined function, then1012 // emit debug info for the outlined function.1013 if (DISubprogram *SP = getSubprogramOrNull(OF)) {1014 // We have a DISubprogram. Get its DICompileUnit.1015 DICompileUnit *CU = SP->getUnit();1016 DIBuilder DB(M, true, CU);1017 DIFile *Unit = SP->getFile();1018 Mangler Mg;1019 // Get the mangled name of the function for the linkage name.1020 std::string Dummy;1021 raw_string_ostream MangledNameStream(Dummy);1022 Mg.getNameWithPrefix(MangledNameStream, F, false);1023 1024 DISubprogram *OutlinedSP = DB.createFunction(1025 Unit /* Context */, F->getName(), StringRef(Dummy), Unit /* File */,1026 0 /* Line 0 is reserved for compiler-generated code. */,1027 DB.createSubroutineType(DB.getOrCreateTypeArray({})), /* void type */1028 0, /* Line 0 is reserved for compiler-generated code. */1029 DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,1030 /* Outlined code is optimized code by definition. */1031 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);1032 1033 // Attach subprogram to the function.1034 F->setSubprogram(OutlinedSP);1035 // We're done with the DIBuilder.1036 DB.finalize();1037 }1038 1039 return &MF;1040}1041 1042bool MachineOutliner::outline(1043 Module &M, std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList,1044 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) {1045 LLVM_DEBUG(dbgs() << "*** Outlining ***\n");1046 LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size()1047 << "\n");1048 bool OutlinedSomething = false;1049 1050 // Sort by priority where priority := getNotOutlinedCost / getOutliningCost.1051 // The function with highest priority should be outlined first.1052 stable_sort(FunctionList, [](const std::unique_ptr<OutlinedFunction> &LHS,1053 const std::unique_ptr<OutlinedFunction> &RHS) {1054 return LHS->getNotOutlinedCost() * RHS->getOutliningCost() >1055 RHS->getNotOutlinedCost() * LHS->getOutliningCost();1056 });1057 1058 // Walk over each function, outlining them as we go along. Functions are1059 // outlined greedily, based off the sort above.1060 auto *UnsignedVecBegin = Mapper.UnsignedVec.begin();1061 LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n");1062 for (auto &OF : FunctionList) {1063#ifndef NDEBUG1064 auto NumCandidatesBefore = OF->Candidates.size();1065#endif1066 // If we outlined something that overlapped with a candidate in a previous1067 // step, then we can't outline from it.1068 erase_if(OF->Candidates, [&UnsignedVecBegin](Candidate &C) {1069 return std::any_of(UnsignedVecBegin + C.getStartIdx(),1070 UnsignedVecBegin + C.getEndIdx() + 1, [](unsigned I) {1071 return I == static_cast<unsigned>(-1);1072 });1073 });1074 1075#ifndef NDEBUG1076 auto NumCandidatesAfter = OF->Candidates.size();1077 LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter1078 << "/" << NumCandidatesBefore << " candidates\n");1079#endif1080 1081 // If we made it unbeneficial to outline this function, skip it.1082 if (OF->getBenefit() < OutlinerBenefitThreshold) {1083 LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF->getBenefit()1084 << " B) < threshold (" << OutlinerBenefitThreshold1085 << " B)\n");1086 continue;1087 }1088 1089 LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF->getBenefit()1090 << " B) > threshold (" << OutlinerBenefitThreshold1091 << " B)\n");1092 1093 // Remove all Linker Optimization Hints from the candidates.1094 // TODO: The intersection of the LOHs from all candidates should be legal in1095 // the outlined function.1096 SmallPtrSet<MachineInstr *, 2> MIs;1097 for (Candidate &C : OF->Candidates) {1098 for (MachineInstr &MI : C)1099 MIs.insert(&MI);1100 NumRemovedLOHs += TM->clearLinkerOptimizationHints(MIs);1101 MIs.clear();1102 }1103 1104 // It's beneficial. Create the function and outline its sequence's1105 // occurrences.1106 OF->MF = createOutlinedFunction(M, *OF, Mapper, OutlinedFunctionNum);1107 emitOutlinedFunctionRemark(*OF);1108 FunctionsCreated++;1109 OutlinedFunctionNum++; // Created a function, move to the next name.1110 MachineFunction *MF = OF->MF;1111 const TargetSubtargetInfo &STI = MF->getSubtarget();1112 const TargetInstrInfo &TII = *STI.getInstrInfo();1113 1114 // Replace occurrences of the sequence with calls to the new function.1115 LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n");1116 for (Candidate &C : OF->Candidates) {1117 MachineBasicBlock &MBB = *C.getMBB();1118 MachineBasicBlock::iterator StartIt = C.begin();1119 MachineBasicBlock::iterator EndIt = std::prev(C.end());1120 1121 // Insert the call.1122 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);1123// Insert the call.1124#ifndef NDEBUG1125 auto MBBBeingOutlinedFromName =1126 MBB.getName().empty() ? "<unknown>" : MBB.getName().str();1127 auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty()1128 ? "<unknown>"1129 : MBB.getParent()->getName().str();1130 LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in "1131 << MFBeingOutlinedFromName << ":"1132 << MBBBeingOutlinedFromName << "\n");1133 LLVM_DEBUG(dbgs() << " .. " << *CallInst);1134#endif1135 1136 // If the caller tracks liveness, then we need to make sure that1137 // anything we outline doesn't break liveness assumptions. The outlined1138 // functions themselves currently don't track liveness, but we should1139 // make sure that the ranges we yank things out of aren't wrong.1140 if (MBB.getParent()->getProperties().hasTracksLiveness()) {1141 // The following code is to add implicit def operands to the call1142 // instruction. It also updates call site information for moved1143 // code.1144 SmallSet<Register, 2> UseRegs, DefRegs;1145 // Copy over the defs in the outlined range.1146 // First inst in outlined range <-- Anything that's defined in this1147 // ... .. range has to be added as an1148 // implicit Last inst in outlined range <-- def to the call1149 // instruction. Also remove call site information for outlined block1150 // of code. The exposed uses need to be copied in the outlined range.1151 for (MachineBasicBlock::reverse_iterator1152 Iter = EndIt.getReverse(),1153 Last = std::next(CallInst.getReverse());1154 Iter != Last; Iter++) {1155 MachineInstr *MI = &*Iter;1156 SmallSet<Register, 2> InstrUseRegs;1157 for (MachineOperand &MOP : MI->operands()) {1158 // Skip over anything that isn't a register.1159 if (!MOP.isReg())1160 continue;1161 1162 if (MOP.isDef()) {1163 // Introduce DefRegs set to skip the redundant register.1164 DefRegs.insert(MOP.getReg());1165 if (UseRegs.count(MOP.getReg()) &&1166 !InstrUseRegs.count(MOP.getReg()))1167 // Since the regiester is modeled as defined,1168 // it is not necessary to be put in use register set.1169 UseRegs.erase(MOP.getReg());1170 } else if (!MOP.isUndef()) {1171 // Any register which is not undefined should1172 // be put in the use register set.1173 UseRegs.insert(MOP.getReg());1174 InstrUseRegs.insert(MOP.getReg());1175 }1176 }1177 if (MI->isCandidateForAdditionalCallInfo())1178 MI->getMF()->eraseAdditionalCallInfo(MI);1179 }1180 1181 for (const Register &I : DefRegs)1182 // If it's a def, add it to the call instruction.1183 CallInst->addOperand(1184 MachineOperand::CreateReg(I, true, /* isDef = true */1185 true /* isImp = true */));1186 1187 for (const Register &I : UseRegs)1188 // If it's a exposed use, add it to the call instruction.1189 CallInst->addOperand(1190 MachineOperand::CreateReg(I, false, /* isDef = false */1191 true /* isImp = true */));1192 }1193 1194 // Erase from the point after where the call was inserted up to, and1195 // including, the final instruction in the sequence.1196 // Erase needs one past the end, so we need std::next there too.1197 MBB.erase(std::next(StartIt), std::next(EndIt));1198 1199 // Keep track of what we removed by marking them all as -1.1200 for (unsigned &I : make_range(UnsignedVecBegin + C.getStartIdx(),1201 UnsignedVecBegin + C.getEndIdx() + 1))1202 I = static_cast<unsigned>(-1);1203 OutlinedSomething = true;1204 1205 // Statistics.1206 NumOutlined++;1207 }1208 }1209 1210 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n");1211 return OutlinedSomething;1212}1213 1214static bool allowPGOOutlining(RunOutliner RunOutlinerMode,1215 const ProfileSummaryInfo *PSI,1216 const BlockFrequencyInfo *BFI,1217 MachineBasicBlock &MBB) {1218 if (RunOutlinerMode != RunOutliner::OptimisticPGO &&1219 RunOutlinerMode != RunOutliner::ConservativePGO)1220 return true;1221 auto *MF = MBB.getParent();1222 if (MF->getFunction().hasFnAttribute(Attribute::Cold)) {1223 ++NumPGOAllowedCold;1224 return true;1225 }1226 1227 auto *BB = MBB.getBasicBlock();1228 if (BB && PSI && BFI)1229 if (auto Count = BFI->getBlockProfileCount(BB))1230 return *Count <= PSI->getOrCompColdCountThreshold();1231 1232 if (RunOutlinerMode == RunOutliner::OptimisticPGO) {1233 auto *TII = MF->getSubtarget().getInstrInfo();1234 if (TII->shouldOutlineFromFunctionByDefault(*MF)) {1235 // Profile data is unavailable, but we optimistically allow outlining1236 ++NumPGOOptimisticOutlined;1237 return true;1238 }1239 return false;1240 }1241 assert(RunOutlinerMode == RunOutliner::ConservativePGO);1242 // Profile data is unavailable, so we conservatively block outlining1243 ++NumPGOConservativeBlockedOutlined;1244 return false;1245}1246 1247void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M) {1248 // Build instruction mappings for each function in the module. Start by1249 // iterating over each Function in M.1250 LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n");1251 bool EnableProfileGuidedOutlining =1252 RunOutlinerMode == RunOutliner::OptimisticPGO ||1253 RunOutlinerMode == RunOutliner::ConservativePGO;1254 ProfileSummaryInfo *PSI = nullptr;1255 if (EnableProfileGuidedOutlining)1256 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();1257 for (Function &F : M) {1258 LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n");1259 1260 if (F.hasFnAttribute("nooutline")) {1261 LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n");1262 continue;1263 }1264 1265 // There's something in F. Check if it has a MachineFunction associated with1266 // it.1267 MachineFunction *MF = MMI->getMachineFunction(F);1268 1269 // If it doesn't, then there's nothing to outline from. Move to the next1270 // Function.1271 if (!MF) {1272 LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n");1273 continue;1274 }1275 1276 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();1277 BlockFrequencyInfo *BFI = nullptr;1278 if (EnableProfileGuidedOutlining && F.hasProfileData())1279 BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();1280 if (RunOutlinerMode == RunOutliner::TargetDefault &&1281 !TII->shouldOutlineFromFunctionByDefault(*MF)) {1282 LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from "1283 "function by default\n");1284 continue;1285 }1286 1287 // We have a MachineFunction. Ask the target if it's suitable for outlining.1288 // If it isn't, then move on to the next Function in the module.1289 if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) {1290 LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName()1291 << ": unsafe to outline from\n");1292 continue;1293 }1294 1295 // We have a function suitable for outlining. Iterate over every1296 // MachineBasicBlock in MF and try to map its instructions to a list of1297 // unsigned integers.1298 const unsigned MinMBBSize = 2;1299 1300 for (MachineBasicBlock &MBB : *MF) {1301 LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n");1302 // If there isn't anything in MBB, then there's no point in outlining from1303 // it.1304 // If there are fewer than 2 instructions in the MBB, then it can't ever1305 // contain something worth outlining.1306 // FIXME: This should be based off of the maximum size in B of an outlined1307 // call versus the size in B of the MBB.1308 if (MBB.size() < MinMBBSize) {1309 LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of "1310 << MinMBBSize << "\n");1311 continue;1312 }1313 1314 // Check if MBB could be the target of an indirect branch. If it is, then1315 // we don't want to outline from it.1316 if (MBB.hasAddressTaken()) {1317 LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n");1318 continue;1319 }1320 1321 if (!allowPGOOutlining(RunOutlinerMode, PSI, BFI, MBB)) {1322 ++NumPGOBlockedOutlined;1323 continue;1324 }1325 1326 // MBB is suitable for outlining. Map it to a list of unsigneds.1327 Mapper.convertToUnsignedVec(MBB, *TII);1328 }1329 }1330 // Statistics.1331 UnsignedVecSize = Mapper.UnsignedVec.size();1332}1333 1334void MachineOutliner::initSizeRemarkInfo(1335 const Module &M, StringMap<unsigned> &FunctionToInstrCount) {1336 // Collect instruction counts for every function. We'll use this to emit1337 // per-function size remarks later.1338 for (const Function &F : M) {1339 MachineFunction *MF = MMI->getMachineFunction(F);1340 1341 // We only care about MI counts here. If there's no MachineFunction at this1342 // point, then there won't be after the outliner runs, so let's move on.1343 if (!MF)1344 continue;1345 FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();1346 }1347}1348 1349void MachineOutliner::emitInstrCountChangedRemark(1350 const Module &M, const StringMap<unsigned> &FunctionToInstrCount) {1351 // Iterate over each function in the module and emit remarks.1352 // Note that we won't miss anything by doing this, because the outliner never1353 // deletes functions.1354 for (const Function &F : M) {1355 MachineFunction *MF = MMI->getMachineFunction(F);1356 1357 // The outliner never deletes functions. If we don't have a MF here, then we1358 // didn't have one prior to outlining either.1359 if (!MF)1360 continue;1361 1362 std::string Fname = std::string(F.getName());1363 unsigned FnCountAfter = MF->getInstructionCount();1364 unsigned FnCountBefore = 0;1365 1366 // Check if the function was recorded before.1367 auto It = FunctionToInstrCount.find(Fname);1368 1369 // Did we have a previously-recorded size? If yes, then set FnCountBefore1370 // to that.1371 if (It != FunctionToInstrCount.end())1372 FnCountBefore = It->second;1373 1374 // Compute the delta and emit a remark if there was a change.1375 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -1376 static_cast<int64_t>(FnCountBefore);1377 if (FnDelta == 0)1378 continue;1379 1380 MachineOptimizationRemarkEmitter MORE(*MF, nullptr);1381 MORE.emit([&]() {1382 MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",1383 DiagnosticLocation(), &MF->front());1384 R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")1385 << ": Function: "1386 << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())1387 << ": MI instruction count changed from "1388 << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",1389 FnCountBefore)1390 << " to "1391 << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",1392 FnCountAfter)1393 << "; Delta: "1394 << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);1395 return R;1396 });1397 }1398}1399 1400void MachineOutliner::initializeOutlinerMode(const Module &M) {1401 if (DisableGlobalOutlining)1402 return;1403 1404 if (auto *IndexWrapperPass =1405 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>()) {1406 auto *TheIndex = IndexWrapperPass->getIndex();1407 // (Full)LTO module does not have functions added to the index.1408 // In this case, we run the outliner without using codegen data as usual.1409 if (TheIndex && !TheIndex->hasExportedFunctions(M))1410 return;1411 }1412 1413 // When codegen data write is enabled, we want to write the local outlined1414 // hash tree to the custom section, `__llvm_outline`.1415 // When the outlined hash tree is available from the previous codegen data,1416 // we want to read it to optimistically create global outlining candidates.1417 if (cgdata::emitCGData()) {1418 OutlinerMode = CGDataMode::Write;1419 // Create a local outlined hash tree to be published.1420 LocalHashTree = std::make_unique<OutlinedHashTree>();1421 // We don't need to read the outlined hash tree from the previous codegen1422 } else if (cgdata::hasOutlinedHashTree())1423 OutlinerMode = CGDataMode::Read;1424}1425 1426void MachineOutliner::emitOutlinedHashTree(Module &M) {1427 assert(LocalHashTree);1428 if (!LocalHashTree->empty()) {1429 LLVM_DEBUG({1430 dbgs() << "Emit outlined hash tree. Size: " << LocalHashTree->size()1431 << "\n";1432 });1433 SmallVector<char> Buf;1434 raw_svector_ostream OS(Buf);1435 1436 OutlinedHashTreeRecord HTR(std::move(LocalHashTree));1437 HTR.serialize(OS);1438 1439 llvm::StringRef Data(Buf.data(), Buf.size());1440 std::unique_ptr<MemoryBuffer> Buffer =1441 MemoryBuffer::getMemBuffer(Data, "in-memory outlined hash tree", false);1442 1443 Triple TT(M.getTargetTriple());1444 embedBufferInModule(1445 M, *Buffer,1446 getCodeGenDataSectionName(CG_outline, TT.getObjectFormat()));1447 }1448}1449 1450bool MachineOutliner::runOnModule(Module &M) {1451 if (skipModule(M))1452 return false;1453 1454 // Check if there's anything in the module. If it's empty, then there's1455 // nothing to outline.1456 if (M.empty())1457 return false;1458 1459 // Initialize the outliner mode.1460 initializeOutlinerMode(M);1461 1462 MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI();1463 TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();1464 1465 // Number to append to the current outlined function.1466 unsigned OutlinedFunctionNum = 0;1467 1468 OutlineRepeatedNum = 0;1469 if (!doOutline(M, OutlinedFunctionNum))1470 return false;1471 1472 for (unsigned I = 0; I < OutlinerReruns; ++I) {1473 OutlinedFunctionNum = 0;1474 OutlineRepeatedNum++;1475 if (!doOutline(M, OutlinedFunctionNum)) {1476 LLVM_DEBUG({1477 dbgs() << "Did not outline on iteration " << I + 2 << " out of "1478 << OutlinerReruns + 1 << "\n";1479 });1480 break;1481 }1482 }1483 1484 if (OutlinerMode == CGDataMode::Write)1485 emitOutlinedHashTree(M);1486 1487 return true;1488}1489 1490bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {1491 // If the user passed -enable-machine-outliner=always or1492 // -enable-machine-outliner, the pass will run on all functions in the module.1493 // Otherwise, if the target supports default outlining, it will run on all1494 // functions deemed by the target to be worth outlining from by default. Tell1495 // the user how the outliner is running.1496 LLVM_DEBUG({1497 dbgs() << "Machine Outliner: Running on ";1498 switch (RunOutlinerMode) {1499 case RunOutliner::AlwaysOutline:1500 dbgs() << "all functions";1501 break;1502 case RunOutliner::OptimisticPGO:1503 dbgs() << "optimistically cold functions";1504 break;1505 case RunOutliner::ConservativePGO:1506 dbgs() << "conservatively cold functions";1507 break;1508 case RunOutliner::TargetDefault:1509 dbgs() << "target-default functions";1510 break;1511 case RunOutliner::NeverOutline:1512 llvm_unreachable("should not outline");1513 }1514 dbgs() << "\n";1515 });1516 1517 // If the user specifies that they want to outline from linkonceodrs, set1518 // it here.1519 OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;1520 InstructionMapper Mapper(*MMI);1521 1522 // Prepare instruction mappings for the suffix tree.1523 populateMapper(Mapper, M);1524 std::vector<std::unique_ptr<OutlinedFunction>> FunctionList;1525 1526 // Find all of the outlining candidates.1527 if (OutlinerMode == CGDataMode::Read)1528 findGlobalCandidates(Mapper, FunctionList);1529 else1530 findCandidates(Mapper, FunctionList);1531 1532 // If we've requested size remarks, then collect the MI counts of every1533 // function before outlining, and the MI counts after outlining.1534 // FIXME: This shouldn't be in the outliner at all; it should ultimately be1535 // the pass manager's responsibility.1536 // This could pretty easily be placed in outline instead, but because we1537 // really ultimately *don't* want this here, it's done like this for now1538 // instead.1539 1540 // Check if we want size remarks.1541 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();1542 StringMap<unsigned> FunctionToInstrCount;1543 if (ShouldEmitSizeRemarks)1544 initSizeRemarkInfo(M, FunctionToInstrCount);1545 1546 // Outline each of the candidates and return true if something was outlined.1547 bool OutlinedSomething =1548 outline(M, FunctionList, Mapper, OutlinedFunctionNum);1549 1550 // If we outlined something, we definitely changed the MI count of the1551 // module. If we've asked for size remarks, then output them.1552 // FIXME: This should be in the pass manager.1553 if (ShouldEmitSizeRemarks && OutlinedSomething)1554 emitInstrCountChangedRemark(M, FunctionToInstrCount);1555 1556 LLVM_DEBUG({1557 if (!OutlinedSomething)1558 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum1559 << " because no changes were found.\n";1560 });1561 1562 return OutlinedSomething;1563}1564