| //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// Replaces repeated sequences of instructions with function calls. |
| /// |
| /// This works by placing every instruction from every basic block in a |
| /// suffix tree, and repeatedly querying that tree for repeated sequences of |
| /// instructions. If a sequence of instructions appears often, then it ought |
| /// to be beneficial to pull out into a function. |
| /// |
| /// The MachineOutliner communicates with a given target using hooks defined in |
| /// TargetInstrInfo.h. The target supplies the outliner with information on how |
| /// a specific sequence of instructions should be outlined. This information |
| /// is used to deduce the number of instructions necessary to |
| /// |
| /// * Create an outlined function |
| /// * Call that outlined function |
| /// |
| /// Targets must implement |
| /// * getOutliningCandidateInfo |
| /// * buildOutlinedFrame |
| /// * insertOutlinedCall |
| /// * isFunctionSafeToOutlineFrom |
| /// |
| /// in order to make use of the MachineOutliner. |
| /// |
| /// This was originally presented at the 2016 LLVM Developers' Meeting in the |
| /// talk "Reducing Code Size Using Outlining". For a high-level overview of |
| /// how this pass works, the talk is available on YouTube at |
| /// |
| /// https://www.youtube.com/watch?v=yorld-WSOeU |
| /// |
| /// The slides for the talk are available at |
| /// |
| /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf |
| /// |
| /// The talk provides an overview of how the outliner finds candidates and |
| /// ultimately outlines them. It describes how the main data structure for this |
| /// pass, the suffix tree, is queried and purged for candidates. It also gives |
| /// a simplified suffix tree construction algorithm for suffix trees based off |
| /// of the algorithm actually used here, Ukkonen's algorithm. |
| /// |
| /// For the original RFC for this pass, please see |
| /// |
| /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html |
| /// |
| /// For more information on the suffix tree data structure, please see |
| /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf |
| /// |
| //===----------------------------------------------------------------------===// |
| #include "llvm/CodeGen/MachineOutliner.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/Twine.h" |
| #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
| #include "llvm/CodeGen/LivePhysRegs.h" |
| #include "llvm/CodeGen/MachineModuleInfo.h" |
| #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" |
| #include "llvm/CodeGen/Passes.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/IR/DIBuilder.h" |
| #include "llvm/IR/IRBuilder.h" |
| #include "llvm/IR/Mangler.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/SuffixTree.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <functional> |
| #include <tuple> |
| #include <vector> |
| |
| #define DEBUG_TYPE "machine-outliner" |
| |
| using namespace llvm; |
| using namespace ore; |
| using namespace outliner; |
| |
| // Statistics for outlined functions. |
| STATISTIC(NumOutlined, "Number of candidates outlined"); |
| STATISTIC(FunctionsCreated, "Number of functions created"); |
| |
| // Statistics for instruction mapping. |
| STATISTIC(NumLegalInUnsignedVec, "Number of legal instrs in unsigned vector"); |
| STATISTIC(NumIllegalInUnsignedVec, |
| "Number of illegal instrs in unsigned vector"); |
| STATISTIC(NumInvisible, "Number of invisible instrs in unsigned vector"); |
| STATISTIC(UnsignedVecSize, "Size of unsigned vector"); |
| |
| // Set to true if the user wants the outliner to run on linkonceodr linkage |
| // functions. This is false by default because the linker can dedupe linkonceodr |
| // functions. Since the outliner is confined to a single module (modulo LTO), |
| // this is off by default. It should, however, be the default behaviour in |
| // LTO. |
| static cl::opt<bool> EnableLinkOnceODROutlining( |
| "enable-linkonceodr-outlining", cl::Hidden, |
| cl::desc("Enable the machine outliner on linkonceodr functions"), |
| cl::init(false)); |
| |
| /// Number of times to re-run the outliner. This is not the total number of runs |
| /// as the outliner will run at least one time. The default value is set to 0, |
| /// meaning the outliner will run one time and rerun zero times after that. |
| static cl::opt<unsigned> OutlinerReruns( |
| "machine-outliner-reruns", cl::init(0), cl::Hidden, |
| cl::desc( |
| "Number of times to rerun the outliner after the initial outline")); |
| |
| namespace { |
| |
| /// Maps \p MachineInstrs to unsigned integers and stores the mappings. |
| struct InstructionMapper { |
| |
| /// The next available integer to assign to a \p MachineInstr that |
| /// cannot be outlined. |
| /// |
| /// Set to -3 for compatability with \p DenseMapInfo<unsigned>. |
| unsigned IllegalInstrNumber = -3; |
| |
| /// The next available integer to assign to a \p MachineInstr that can |
| /// be outlined. |
| unsigned LegalInstrNumber = 0; |
| |
| /// Correspondence from \p MachineInstrs to unsigned integers. |
| DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait> |
| InstructionIntegerMap; |
| |
| /// Correspondence between \p MachineBasicBlocks and target-defined flags. |
| DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap; |
| |
| /// The vector of unsigned integers that the module is mapped to. |
| std::vector<unsigned> UnsignedVec; |
| |
| /// Stores the location of the instruction associated with the integer |
| /// at index i in \p UnsignedVec for each index i. |
| std::vector<MachineBasicBlock::iterator> InstrList; |
| |
| // Set if we added an illegal number in the previous step. |
| // Since each illegal number is unique, we only need one of them between |
| // each range of legal numbers. This lets us make sure we don't add more |
| // than one illegal number per range. |
| bool AddedIllegalLastTime = false; |
| |
| /// Maps \p *It to a legal integer. |
| /// |
| /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB, |
| /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber. |
| /// |
| /// \returns The integer that \p *It was mapped to. |
| unsigned mapToLegalUnsigned( |
| MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
| bool &HaveLegalRange, unsigned &NumLegalInBlock, |
| std::vector<unsigned> &UnsignedVecForMBB, |
| std::vector<MachineBasicBlock::iterator> &InstrListForMBB) { |
| // We added something legal, so we should unset the AddedLegalLastTime |
| // flag. |
| AddedIllegalLastTime = false; |
| |
| // If we have at least two adjacent legal instructions (which may have |
| // invisible instructions in between), remember that. |
| if (CanOutlineWithPrevInstr) |
| HaveLegalRange = true; |
| CanOutlineWithPrevInstr = true; |
| |
| // Keep track of the number of legal instructions we insert. |
| NumLegalInBlock++; |
| |
| // Get the integer for this instruction or give it the current |
| // LegalInstrNumber. |
| InstrListForMBB.push_back(It); |
| MachineInstr &MI = *It; |
| bool WasInserted; |
| DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator |
| ResultIt; |
| std::tie(ResultIt, WasInserted) = |
| InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber)); |
| unsigned MINumber = ResultIt->second; |
| |
| // There was an insertion. |
| if (WasInserted) |
| LegalInstrNumber++; |
| |
| UnsignedVecForMBB.push_back(MINumber); |
| |
| // Make sure we don't overflow or use any integers reserved by the DenseMap. |
| if (LegalInstrNumber >= IllegalInstrNumber) |
| report_fatal_error("Instruction mapping overflow!"); |
| |
| assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() && |
| "Tried to assign DenseMap tombstone or empty key to instruction."); |
| assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() && |
| "Tried to assign DenseMap tombstone or empty key to instruction."); |
| |
| // Statistics. |
| ++NumLegalInUnsignedVec; |
| return MINumber; |
| } |
| |
| /// Maps \p *It to an illegal integer. |
| /// |
| /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p |
| /// IllegalInstrNumber. |
| /// |
| /// \returns The integer that \p *It was mapped to. |
| unsigned mapToIllegalUnsigned( |
| MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
| std::vector<unsigned> &UnsignedVecForMBB, |
| std::vector<MachineBasicBlock::iterator> &InstrListForMBB) { |
| // Can't outline an illegal instruction. Set the flag. |
| CanOutlineWithPrevInstr = false; |
| |
| // Only add one illegal number per range of legal numbers. |
| if (AddedIllegalLastTime) |
| return IllegalInstrNumber; |
| |
| // Remember that we added an illegal number last time. |
| AddedIllegalLastTime = true; |
| unsigned MINumber = IllegalInstrNumber; |
| |
| InstrListForMBB.push_back(It); |
| UnsignedVecForMBB.push_back(IllegalInstrNumber); |
| IllegalInstrNumber--; |
| // Statistics. |
| ++NumIllegalInUnsignedVec; |
| |
| assert(LegalInstrNumber < IllegalInstrNumber && |
| "Instruction mapping overflow!"); |
| |
| assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() && |
| "IllegalInstrNumber cannot be DenseMap tombstone or empty key!"); |
| |
| assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() && |
| "IllegalInstrNumber cannot be DenseMap tombstone or empty key!"); |
| |
| return MINumber; |
| } |
| |
| /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds |
| /// and appends it to \p UnsignedVec and \p InstrList. |
| /// |
| /// Two instructions are assigned the same integer if they are identical. |
| /// If an instruction is deemed unsafe to outline, then it will be assigned an |
| /// unique integer. The resulting mapping is placed into a suffix tree and |
| /// queried for candidates. |
| /// |
| /// \param MBB The \p MachineBasicBlock to be translated into integers. |
| /// \param TII \p TargetInstrInfo for the function. |
| void convertToUnsignedVec(MachineBasicBlock &MBB, |
| const TargetInstrInfo &TII) { |
| unsigned Flags = 0; |
| |
| // Don't even map in this case. |
| if (!TII.isMBBSafeToOutlineFrom(MBB, Flags)) |
| return; |
| |
| // Store info for the MBB for later outlining. |
| MBBFlagsMap[&MBB] = Flags; |
| |
| MachineBasicBlock::iterator It = MBB.begin(); |
| |
| // The number of instructions in this block that will be considered for |
| // outlining. |
| unsigned NumLegalInBlock = 0; |
| |
| // True if we have at least two legal instructions which aren't separated |
| // by an illegal instruction. |
| bool HaveLegalRange = false; |
| |
| // True if we can perform outlining given the last mapped (non-invisible) |
| // instruction. This lets us know if we have a legal range. |
| bool CanOutlineWithPrevInstr = false; |
| |
| // FIXME: Should this all just be handled in the target, rather than using |
| // repeated calls to getOutliningType? |
| std::vector<unsigned> UnsignedVecForMBB; |
| std::vector<MachineBasicBlock::iterator> InstrListForMBB; |
| |
| for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; ++It) { |
| // Keep track of where this instruction is in the module. |
| switch (TII.getOutliningType(It, Flags)) { |
| case InstrType::Illegal: |
| mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| InstrListForMBB); |
| break; |
| |
| case InstrType::Legal: |
| mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
| NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB); |
| break; |
| |
| case InstrType::LegalTerminator: |
| mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
| NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB); |
| // The instruction also acts as a terminator, so we have to record that |
| // in the string. |
| mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| InstrListForMBB); |
| break; |
| |
| case InstrType::Invisible: |
| // Normally this is set by mapTo(Blah)Unsigned, but we just want to |
| // skip this instruction. So, unset the flag here. |
| ++NumInvisible; |
| AddedIllegalLastTime = false; |
| break; |
| } |
| } |
| |
| // Are there enough legal instructions in the block for outlining to be |
| // possible? |
| if (HaveLegalRange) { |
| // After we're done every insertion, uniquely terminate this part of the |
| // "string". This makes sure we won't match across basic block or function |
| // boundaries since the "end" is encoded uniquely and thus appears in no |
| // repeated substring. |
| mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| InstrListForMBB); |
| llvm::append_range(InstrList, InstrListForMBB); |
| llvm::append_range(UnsignedVec, UnsignedVecForMBB); |
| } |
| } |
| |
| InstructionMapper() { |
| // Make sure that the implementation of DenseMapInfo<unsigned> hasn't |
| // changed. |
| assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 && |
| "DenseMapInfo<unsigned>'s empty key isn't -1!"); |
| assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 && |
| "DenseMapInfo<unsigned>'s tombstone key isn't -2!"); |
| } |
| }; |
| |
| /// An interprocedural pass which finds repeated sequences of |
| /// instructions and replaces them with calls to functions. |
| /// |
| /// Each instruction is mapped to an unsigned integer and placed in a string. |
| /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree |
| /// is then repeatedly queried for repeated sequences of instructions. Each |
| /// non-overlapping repeated sequence is then placed in its own |
| /// \p MachineFunction and each instance is then replaced with a call to that |
| /// function. |
| struct MachineOutliner : public ModulePass { |
| |
| static char ID; |
| |
| /// Set to true if the outliner should consider functions with |
| /// linkonceodr linkage. |
| bool OutlineFromLinkOnceODRs = false; |
| |
| /// The current repeat number of machine outlining. |
| unsigned OutlineRepeatedNum = 0; |
| |
| /// Set to true if the outliner should run on all functions in the module |
| /// considered safe for outlining. |
| /// Set to true by default for compatibility with llc's -run-pass option. |
| /// Set when the pass is constructed in TargetPassConfig. |
| bool RunOnAllFunctions = true; |
| |
| StringRef getPassName() const override { return "Machine Outliner"; } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.addRequired<MachineModuleInfoWrapperPass>(); |
| AU.addPreserved<MachineModuleInfoWrapperPass>(); |
| AU.setPreservesAll(); |
| ModulePass::getAnalysisUsage(AU); |
| } |
| |
| MachineOutliner() : ModulePass(ID) { |
| initializeMachineOutlinerPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| /// Remark output explaining that not outlining a set of candidates would be |
| /// better than outlining that set. |
| void emitNotOutliningCheaperRemark( |
| unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
| OutlinedFunction &OF); |
| |
| /// Remark output explaining that a function was outlined. |
| void emitOutlinedFunctionRemark(OutlinedFunction &OF); |
| |
| /// Find all repeated substrings that satisfy the outlining cost model by |
| /// constructing a suffix tree. |
| /// |
| /// If a substring appears at least twice, then it must be represented by |
| /// an internal node which appears in at least two suffixes. Each suffix |
| /// is represented by a leaf node. To do this, we visit each internal node |
| /// in the tree, using the leaf children of each internal node. If an |
| /// internal node represents a beneficial substring, then we use each of |
| /// its leaf children to find the locations of its substring. |
| /// |
| /// \param Mapper Contains outlining mapping information. |
| /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions |
| /// each type of candidate. |
| void findCandidates(InstructionMapper &Mapper, |
| std::vector<OutlinedFunction> &FunctionList); |
| |
| /// Replace the sequences of instructions represented by \p OutlinedFunctions |
| /// with calls to functions. |
| /// |
| /// \param M The module we are outlining from. |
| /// \param FunctionList A list of functions to be inserted into the module. |
| /// \param Mapper Contains the instruction mappings for the module. |
| bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList, |
| InstructionMapper &Mapper, unsigned &OutlinedFunctionNum); |
| |
| /// Creates a function for \p OF and inserts it into the module. |
| MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF, |
| InstructionMapper &Mapper, |
| unsigned Name); |
| |
| /// Calls 'doOutline()' 1 + OutlinerReruns times. |
| bool runOnModule(Module &M) override; |
| |
| /// Construct a suffix tree on the instructions in \p M and outline repeated |
| /// strings from that tree. |
| bool doOutline(Module &M, unsigned &OutlinedFunctionNum); |
| |
| /// Return a DISubprogram for OF if one exists, and null otherwise. Helper |
| /// function for remark emission. |
| DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) { |
| for (const Candidate &C : OF.Candidates) |
| if (MachineFunction *MF = C.getMF()) |
| if (DISubprogram *SP = MF->getFunction().getSubprogram()) |
| return SP; |
| return nullptr; |
| } |
| |
| /// Populate and \p InstructionMapper with instruction-to-integer mappings. |
| /// These are used to construct a suffix tree. |
| void populateMapper(InstructionMapper &Mapper, Module &M, |
| MachineModuleInfo &MMI); |
| |
| /// Initialize information necessary to output a size remark. |
| /// FIXME: This should be handled by the pass manager, not the outliner. |
| /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy |
| /// pass manager. |
| void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI, |
| StringMap<unsigned> &FunctionToInstrCount); |
| |
| /// Emit the remark. |
| // FIXME: This should be handled by the pass manager, not the outliner. |
| void |
| emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI, |
| const StringMap<unsigned> &FunctionToInstrCount); |
| }; |
| } // Anonymous namespace. |
| |
| char MachineOutliner::ID = 0; |
| |
| namespace llvm { |
| ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) { |
| MachineOutliner *OL = new MachineOutliner(); |
| OL->RunOnAllFunctions = RunOnAllFunctions; |
| return OL; |
| } |
| |
| } // namespace llvm |
| |
| INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, |
| false) |
| |
| void MachineOutliner::emitNotOutliningCheaperRemark( |
| unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
| OutlinedFunction &OF) { |
| // FIXME: Right now, we arbitrarily choose some Candidate from the |
| // OutlinedFunction. This isn't necessarily fixed, nor does it have to be. |
| // We should probably sort these by function name or something to make sure |
| // the remarks are stable. |
| Candidate &C = CandidatesForRepeatedSeq.front(); |
| MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr); |
| MORE.emit([&]() { |
| MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper", |
| C.front()->getDebugLoc(), C.getMBB()); |
| R << "Did not outline " << NV("Length", StringLen) << " instructions" |
| << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size()) |
| << " locations." |
| << " Bytes from outlining all occurrences (" |
| << NV("OutliningCost", OF.getOutliningCost()) << ")" |
| << " >= Unoutlined instruction bytes (" |
| << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")" |
| << " (Also found at: "; |
| |
| // Tell the user the other places the candidate was found. |
| for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) { |
| R << NV((Twine("OtherStartLoc") + Twine(i)).str(), |
| CandidatesForRepeatedSeq[i].front()->getDebugLoc()); |
| if (i != e - 1) |
| R << ", "; |
| } |
| |
| R << ")"; |
| return R; |
| }); |
| } |
| |
| void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) { |
| MachineBasicBlock *MBB = &*OF.MF->begin(); |
| MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr); |
| MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction", |
| MBB->findDebugLoc(MBB->begin()), MBB); |
| R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by " |
| << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions " |
| << "from " << NV("NumOccurrences", OF.getOccurrenceCount()) |
| << " locations. " |
| << "(Found at: "; |
| |
| // Tell the user the other places the candidate was found. |
| for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) { |
| |
| R << NV((Twine("StartLoc") + Twine(i)).str(), |
| OF.Candidates[i].front()->getDebugLoc()); |
| if (i != e - 1) |
| R << ", "; |
| } |
| |
| R << ")"; |
| |
| MORE.emit(R); |
| } |
| |
| void MachineOutliner::findCandidates( |
| InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) { |
| FunctionList.clear(); |
| SuffixTree ST(Mapper.UnsignedVec); |
| |
| // First, find all of the repeated substrings in the tree of minimum length |
| // 2. |
| std::vector<Candidate> CandidatesForRepeatedSeq; |
| for (const SuffixTree::RepeatedSubstring &RS : ST) { |
| CandidatesForRepeatedSeq.clear(); |
| unsigned StringLen = RS.Length; |
| for (const unsigned &StartIdx : RS.StartIndices) { |
| unsigned EndIdx = StartIdx + StringLen - 1; |
| // Trick: Discard some candidates that would be incompatible with the |
| // ones we've already found for this sequence. This will save us some |
| // work in candidate selection. |
| // |
| // If two candidates overlap, then we can't outline them both. This |
| // happens when we have candidates that look like, say |
| // |
| // AA (where each "A" is an instruction). |
| // |
| // We might have some portion of the module that looks like this: |
| // AAAAAA (6 A's) |
| // |
| // In this case, there are 5 different copies of "AA" in this range, but |
| // at most 3 can be outlined. If only outlining 3 of these is going to |
| // be unbeneficial, then we ought to not bother. |
| // |
| // Note that two things DON'T overlap when they look like this: |
| // start1...end1 .... start2...end2 |
| // That is, one must either |
| // * End before the other starts |
| // * Start after the other ends |
| if (llvm::all_of(CandidatesForRepeatedSeq, [&StartIdx, |
| &EndIdx](const Candidate &C) { |
| return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx()); |
| })) { |
| // It doesn't overlap with anything, so we can outline it. |
| // Each sequence is over [StartIt, EndIt]. |
| // Save the candidate and its location. |
| |
| MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; |
| MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; |
| MachineBasicBlock *MBB = StartIt->getParent(); |
| |
| CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, |
| EndIt, MBB, FunctionList.size(), |
| Mapper.MBBFlagsMap[MBB]); |
| } |
| } |
| |
| // We've found something we might want to outline. |
| // Create an OutlinedFunction to store it and check if it'd be beneficial |
| // to outline. |
| if (CandidatesForRepeatedSeq.size() < 2) |
| continue; |
| |
| // Arbitrarily choose a TII from the first candidate. |
| // FIXME: Should getOutliningCandidateInfo move to TargetMachine? |
| const TargetInstrInfo *TII = |
| CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo(); |
| |
| OutlinedFunction OF = |
| TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq); |
| |
| // If we deleted too many candidates, then there's nothing worth outlining. |
| // FIXME: This should take target-specified instruction sizes into account. |
| if (OF.Candidates.size() < 2) |
| continue; |
| |
| // Is it better to outline this candidate than not? |
| if (OF.getBenefit() < 1) { |
| emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF); |
| continue; |
| } |
| |
| FunctionList.push_back(OF); |
| } |
| } |
| |
| MachineFunction *MachineOutliner::createOutlinedFunction( |
| Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) { |
| |
| // Create the function name. This should be unique. |
| // FIXME: We should have a better naming scheme. This should be stable, |
| // regardless of changes to the outliner's cost model/traversal order. |
| std::string FunctionName = "OUTLINED_FUNCTION_"; |
| if (OutlineRepeatedNum > 0) |
| FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_"; |
| FunctionName += std::to_string(Name); |
| |
| // Create the function using an IR-level function. |
| LLVMContext &C = M.getContext(); |
| Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false), |
| Function::ExternalLinkage, FunctionName, M); |
| |
| // NOTE: If this is linkonceodr, then we can take advantage of linker deduping |
| // which gives us better results when we outline from linkonceodr functions. |
| F->setLinkage(GlobalValue::InternalLinkage); |
| F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); |
| |
| // Set optsize/minsize, so we don't insert padding between outlined |
| // functions. |
| F->addFnAttr(Attribute::OptimizeForSize); |
| F->addFnAttr(Attribute::MinSize); |
| |
| Candidate &FirstCand = OF.Candidates.front(); |
| const TargetInstrInfo &TII = |
| *FirstCand.getMF()->getSubtarget().getInstrInfo(); |
| |
| TII.mergeOutliningCandidateAttributes(*F, OF.Candidates); |
| |
| // Set uwtable, so we generate eh_frame. |
| UWTableKind UW = std::accumulate( |
| OF.Candidates.cbegin(), OF.Candidates.cend(), UWTableKind::None, |
| [](UWTableKind K, const outliner::Candidate &C) { |
| return std::max(K, C.getMF()->getFunction().getUWTableKind()); |
| }); |
| if (UW != UWTableKind::None) |
| F->setUWTableKind(UW); |
| |
| BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F); |
| IRBuilder<> Builder(EntryBB); |
| Builder.CreateRetVoid(); |
| |
| MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
| MachineFunction &MF = MMI.getOrCreateMachineFunction(*F); |
| MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock(); |
| |
| // Insert the new function into the module. |
| MF.insert(MF.begin(), &MBB); |
| |
| MachineFunction *OriginalMF = FirstCand.front()->getMF(); |
| const std::vector<MCCFIInstruction> &Instrs = |
| OriginalMF->getFrameInstructions(); |
| for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E; |
| ++I) { |
| if (I->isDebugInstr()) |
| continue; |
| |
| // Don't keep debug information for outlined instructions. |
| auto DL = DebugLoc(); |
| if (I->isCFIInstruction()) { |
| unsigned CFIIndex = I->getOperand(0).getCFIIndex(); |
| MCCFIInstruction CFI = Instrs[CFIIndex]; |
| BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(MF.addFrameInst(CFI)); |
| } else { |
| MachineInstr *NewMI = MF.CloneMachineInstr(&*I); |
| NewMI->dropMemRefs(MF); |
| NewMI->setDebugLoc(DL); |
| MBB.insert(MBB.end(), NewMI); |
| } |
| } |
| |
| // Set normal properties for a late MachineFunction. |
| MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA); |
| MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs); |
| MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); |
| MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness); |
| MF.getRegInfo().freezeReservedRegs(MF); |
| |
| // Compute live-in set for outlined fn |
| const MachineRegisterInfo &MRI = MF.getRegInfo(); |
| const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
| LivePhysRegs LiveIns(TRI); |
| for (auto &Cand : OF.Candidates) { |
| // Figure out live-ins at the first instruction. |
| MachineBasicBlock &OutlineBB = *Cand.front()->getParent(); |
| LivePhysRegs CandLiveIns(TRI); |
| CandLiveIns.addLiveOuts(OutlineBB); |
| for (const MachineInstr &MI : |
| reverse(make_range(Cand.front(), OutlineBB.end()))) |
| CandLiveIns.stepBackward(MI); |
| |
| // The live-in set for the outlined function is the union of the live-ins |
| // from all the outlining points. |
| for (MCPhysReg Reg : CandLiveIns) |
| LiveIns.addReg(Reg); |
| } |
| addLiveIns(MBB, LiveIns); |
| |
| TII.buildOutlinedFrame(MBB, MF, OF); |
| |
| // If there's a DISubprogram associated with this outlined function, then |
| // emit debug info for the outlined function. |
| if (DISubprogram *SP = getSubprogramOrNull(OF)) { |
| // We have a DISubprogram. Get its DICompileUnit. |
| DICompileUnit *CU = SP->getUnit(); |
| DIBuilder DB(M, true, CU); |
| DIFile *Unit = SP->getFile(); |
| Mangler Mg; |
| // Get the mangled name of the function for the linkage name. |
| std::string Dummy; |
| llvm::raw_string_ostream MangledNameStream(Dummy); |
| Mg.getNameWithPrefix(MangledNameStream, F, false); |
| |
| DISubprogram *OutlinedSP = DB.createFunction( |
| Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()), |
| Unit /* File */, |
| 0 /* Line 0 is reserved for compiler-generated code. */, |
| DB.createSubroutineType( |
| DB.getOrCreateTypeArray(std::nullopt)), /* void type */ |
| 0, /* Line 0 is reserved for compiler-generated code. */ |
| DINode::DIFlags::FlagArtificial /* Compiler-generated code. */, |
| /* Outlined code is optimized code by definition. */ |
| DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized); |
| |
| // Don't add any new variables to the subprogram. |
| DB.finalizeSubprogram(OutlinedSP); |
| |
| // Attach subprogram to the function. |
| F->setSubprogram(OutlinedSP); |
| // We're done with the DIBuilder. |
| DB.finalize(); |
| } |
| |
| return &MF; |
| } |
| |
| bool MachineOutliner::outline(Module &M, |
| std::vector<OutlinedFunction> &FunctionList, |
| InstructionMapper &Mapper, |
| unsigned &OutlinedFunctionNum) { |
| |
| bool OutlinedSomething = false; |
| |
| // Sort by benefit. The most beneficial functions should be outlined first. |
| llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS, |
| const OutlinedFunction &RHS) { |
| return LHS.getBenefit() > RHS.getBenefit(); |
| }); |
| |
| // Walk over each function, outlining them as we go along. Functions are |
| // outlined greedily, based off the sort above. |
| for (OutlinedFunction &OF : FunctionList) { |
| // If we outlined something that overlapped with a candidate in a previous |
| // step, then we can't outline from it. |
| erase_if(OF.Candidates, [&Mapper](Candidate &C) { |
| return std::any_of( |
| Mapper.UnsignedVec.begin() + C.getStartIdx(), |
| Mapper.UnsignedVec.begin() + C.getEndIdx() + 1, |
| [](unsigned I) { return (I == static_cast<unsigned>(-1)); }); |
| }); |
| |
| // If we made it unbeneficial to outline this function, skip it. |
| if (OF.getBenefit() < 1) |
| continue; |
| |
| // It's beneficial. Create the function and outline its sequence's |
| // occurrences. |
| OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum); |
| emitOutlinedFunctionRemark(OF); |
| FunctionsCreated++; |
| OutlinedFunctionNum++; // Created a function, move to the next name. |
| MachineFunction *MF = OF.MF; |
| const TargetSubtargetInfo &STI = MF->getSubtarget(); |
| const TargetInstrInfo &TII = *STI.getInstrInfo(); |
| |
| // Replace occurrences of the sequence with calls to the new function. |
| for (Candidate &C : OF.Candidates) { |
| MachineBasicBlock &MBB = *C.getMBB(); |
| MachineBasicBlock::iterator StartIt = C.front(); |
| MachineBasicBlock::iterator EndIt = C.back(); |
| |
| // Insert the call. |
| auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C); |
| |
| // If the caller tracks liveness, then we need to make sure that |
| // anything we outline doesn't break liveness assumptions. The outlined |
| // functions themselves currently don't track liveness, but we should |
| // make sure that the ranges we yank things out of aren't wrong. |
| if (MBB.getParent()->getProperties().hasProperty( |
| MachineFunctionProperties::Property::TracksLiveness)) { |
| // The following code is to add implicit def operands to the call |
| // instruction. It also updates call site information for moved |
| // code. |
| SmallSet<Register, 2> UseRegs, DefRegs; |
| // Copy over the defs in the outlined range. |
| // First inst in outlined range <-- Anything that's defined in this |
| // ... .. range has to be added as an |
| // implicit Last inst in outlined range <-- def to the call |
| // instruction. Also remove call site information for outlined block |
| // of code. The exposed uses need to be copied in the outlined range. |
| for (MachineBasicBlock::reverse_iterator |
| Iter = EndIt.getReverse(), |
| Last = std::next(CallInst.getReverse()); |
| Iter != Last; Iter++) { |
| MachineInstr *MI = &*Iter; |
| SmallSet<Register, 2> InstrUseRegs; |
| for (MachineOperand &MOP : MI->operands()) { |
| // Skip over anything that isn't a register. |
| if (!MOP.isReg()) |
| continue; |
| |
| if (MOP.isDef()) { |
| // Introduce DefRegs set to skip the redundant register. |
| DefRegs.insert(MOP.getReg()); |
| if (UseRegs.count(MOP.getReg()) && |
| !InstrUseRegs.count(MOP.getReg())) |
| // Since the regiester is modeled as defined, |
| // it is not necessary to be put in use register set. |
| UseRegs.erase(MOP.getReg()); |
| } else if (!MOP.isUndef()) { |
| // Any register which is not undefined should |
| // be put in the use register set. |
| UseRegs.insert(MOP.getReg()); |
| InstrUseRegs.insert(MOP.getReg()); |
| } |
| } |
| if (MI->isCandidateForCallSiteEntry()) |
| MI->getMF()->eraseCallSiteInfo(MI); |
| } |
| |
| for (const Register &I : DefRegs) |
| // If it's a def, add it to the call instruction. |
| CallInst->addOperand( |
| MachineOperand::CreateReg(I, true, /* isDef = true */ |
| true /* isImp = true */)); |
| |
| for (const Register &I : UseRegs) |
| // If it's a exposed use, add it to the call instruction. |
| CallInst->addOperand( |
| MachineOperand::CreateReg(I, false, /* isDef = false */ |
| true /* isImp = true */)); |
| } |
| |
| // Erase from the point after where the call was inserted up to, and |
| // including, the final instruction in the sequence. |
| // Erase needs one past the end, so we need std::next there too. |
| MBB.erase(std::next(StartIt), std::next(EndIt)); |
| |
| // Keep track of what we removed by marking them all as -1. |
| for (unsigned &I : |
| llvm::make_range(Mapper.UnsignedVec.begin() + C.getStartIdx(), |
| Mapper.UnsignedVec.begin() + C.getEndIdx() + 1)) |
| I = static_cast<unsigned>(-1); |
| OutlinedSomething = true; |
| |
| // Statistics. |
| NumOutlined++; |
| } |
| } |
| |
| LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); |
| return OutlinedSomething; |
| } |
| |
| void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M, |
| MachineModuleInfo &MMI) { |
| // Build instruction mappings for each function in the module. Start by |
| // iterating over each Function in M. |
| for (Function &F : M) { |
| |
| if (F.hasFnAttribute("nooutline")) { |
| LLVM_DEBUG({ |
| dbgs() << "... Skipping function with nooutline attribute: " |
| << F.getName() << "\n"; |
| }); |
| continue; |
| } |
| |
| // There's something in F. Check if it has a MachineFunction associated with |
| // it. |
| MachineFunction *MF = MMI.getMachineFunction(F); |
| |
| // If it doesn't, then there's nothing to outline from. Move to the next |
| // Function. |
| if (!MF) |
| continue; |
| |
| const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); |
| |
| if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF)) |
| continue; |
| |
| // We have a MachineFunction. Ask the target if it's suitable for outlining. |
| // If it isn't, then move on to the next Function in the module. |
| if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) |
| continue; |
| |
| // We have a function suitable for outlining. Iterate over every |
| // MachineBasicBlock in MF and try to map its instructions to a list of |
| // unsigned integers. |
| for (MachineBasicBlock &MBB : *MF) { |
| // If there isn't anything in MBB, then there's no point in outlining from |
| // it. |
| // If there are fewer than 2 instructions in the MBB, then it can't ever |
| // contain something worth outlining. |
| // FIXME: This should be based off of the maximum size in B of an outlined |
| // call versus the size in B of the MBB. |
| if (MBB.empty() || MBB.size() < 2) |
| continue; |
| |
| // Check if MBB could be the target of an indirect branch. If it is, then |
| // we don't want to outline from it. |
| if (MBB.hasAddressTaken()) |
| continue; |
| |
| // MBB is suitable for outlining. Map it to a list of unsigneds. |
| Mapper.convertToUnsignedVec(MBB, *TII); |
| } |
| |
| // Statistics. |
| UnsignedVecSize = Mapper.UnsignedVec.size(); |
| } |
| } |
| |
| void MachineOutliner::initSizeRemarkInfo( |
| const Module &M, const MachineModuleInfo &MMI, |
| StringMap<unsigned> &FunctionToInstrCount) { |
| // Collect instruction counts for every function. We'll use this to emit |
| // per-function size remarks later. |
| for (const Function &F : M) { |
| MachineFunction *MF = MMI.getMachineFunction(F); |
| |
| // We only care about MI counts here. If there's no MachineFunction at this |
| // point, then there won't be after the outliner runs, so let's move on. |
| if (!MF) |
| continue; |
| FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount(); |
| } |
| } |
| |
| void MachineOutliner::emitInstrCountChangedRemark( |
| const Module &M, const MachineModuleInfo &MMI, |
| const StringMap<unsigned> &FunctionToInstrCount) { |
| // Iterate over each function in the module and emit remarks. |
| // Note that we won't miss anything by doing this, because the outliner never |
| // deletes functions. |
| for (const Function &F : M) { |
| MachineFunction *MF = MMI.getMachineFunction(F); |
| |
| // The outliner never deletes functions. If we don't have a MF here, then we |
| // didn't have one prior to outlining either. |
| if (!MF) |
| continue; |
| |
| std::string Fname = std::string(F.getName()); |
| unsigned FnCountAfter = MF->getInstructionCount(); |
| unsigned FnCountBefore = 0; |
| |
| // Check if the function was recorded before. |
| auto It = FunctionToInstrCount.find(Fname); |
| |
| // Did we have a previously-recorded size? If yes, then set FnCountBefore |
| // to that. |
| if (It != FunctionToInstrCount.end()) |
| FnCountBefore = It->second; |
| |
| // Compute the delta and emit a remark if there was a change. |
| int64_t FnDelta = static_cast<int64_t>(FnCountAfter) - |
| static_cast<int64_t>(FnCountBefore); |
| if (FnDelta == 0) |
| continue; |
| |
| MachineOptimizationRemarkEmitter MORE(*MF, nullptr); |
| MORE.emit([&]() { |
| MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange", |
| DiagnosticLocation(), &MF->front()); |
| R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner") |
| << ": Function: " |
| << DiagnosticInfoOptimizationBase::Argument("Function", F.getName()) |
| << ": MI instruction count changed from " |
| << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore", |
| FnCountBefore) |
| << " to " |
| << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter", |
| FnCountAfter) |
| << "; Delta: " |
| << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta); |
| return R; |
| }); |
| } |
| } |
| |
| bool MachineOutliner::runOnModule(Module &M) { |
| // Check if there's anything in the module. If it's empty, then there's |
| // nothing to outline. |
| if (M.empty()) |
| return false; |
| |
| // Number to append to the current outlined function. |
| unsigned OutlinedFunctionNum = 0; |
| |
| OutlineRepeatedNum = 0; |
| if (!doOutline(M, OutlinedFunctionNum)) |
| return false; |
| |
| for (unsigned I = 0; I < OutlinerReruns; ++I) { |
| OutlinedFunctionNum = 0; |
| OutlineRepeatedNum++; |
| if (!doOutline(M, OutlinedFunctionNum)) { |
| LLVM_DEBUG({ |
| dbgs() << "Did not outline on iteration " << I + 2 << " out of " |
| << OutlinerReruns + 1 << "\n"; |
| }); |
| break; |
| } |
| } |
| |
| return true; |
| } |
| |
| bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) { |
| MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
| |
| // If the user passed -enable-machine-outliner=always or |
| // -enable-machine-outliner, the pass will run on all functions in the module. |
| // Otherwise, if the target supports default outlining, it will run on all |
| // functions deemed by the target to be worth outlining from by default. Tell |
| // the user how the outliner is running. |
| LLVM_DEBUG({ |
| dbgs() << "Machine Outliner: Running on "; |
| if (RunOnAllFunctions) |
| dbgs() << "all functions"; |
| else |
| dbgs() << "target-default functions"; |
| dbgs() << "\n"; |
| }); |
| |
| // If the user specifies that they want to outline from linkonceodrs, set |
| // it here. |
| OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining; |
| InstructionMapper Mapper; |
| |
| // Prepare instruction mappings for the suffix tree. |
| populateMapper(Mapper, M, MMI); |
| std::vector<OutlinedFunction> FunctionList; |
| |
| // Find all of the outlining candidates. |
| findCandidates(Mapper, FunctionList); |
| |
| // If we've requested size remarks, then collect the MI counts of every |
| // function before outlining, and the MI counts after outlining. |
| // FIXME: This shouldn't be in the outliner at all; it should ultimately be |
| // the pass manager's responsibility. |
| // This could pretty easily be placed in outline instead, but because we |
| // really ultimately *don't* want this here, it's done like this for now |
| // instead. |
| |
| // Check if we want size remarks. |
| bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark(); |
| StringMap<unsigned> FunctionToInstrCount; |
| if (ShouldEmitSizeRemarks) |
| initSizeRemarkInfo(M, MMI, FunctionToInstrCount); |
| |
| // Outline each of the candidates and return true if something was outlined. |
| bool OutlinedSomething = |
| outline(M, FunctionList, Mapper, OutlinedFunctionNum); |
| |
| // If we outlined something, we definitely changed the MI count of the |
| // module. If we've asked for size remarks, then output them. |
| // FIXME: This should be in the pass manager. |
| if (ShouldEmitSizeRemarks && OutlinedSomething) |
| emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount); |
| |
| LLVM_DEBUG({ |
| if (!OutlinedSomething) |
| dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum |
| << " because no changes were found.\n"; |
| }); |
| |
| return OutlinedSomething; |
| } |
