diff options
Diffstat (limited to 'lib/CodeGen/MachineOutliner.cpp')
| -rw-r--r-- | lib/CodeGen/MachineOutliner.cpp | 600 |
1 files changed, 323 insertions, 277 deletions
diff --git a/lib/CodeGen/MachineOutliner.cpp b/lib/CodeGen/MachineOutliner.cpp index e4eb8802ac66..28e4e2c6c87a 100644 --- a/lib/CodeGen/MachineOutliner.cpp +++ b/lib/CodeGen/MachineOutliner.cpp @@ -25,9 +25,8 @@ /// /// Targets must implement /// * getOutliningCandidateInfo -/// * insertOutlinerEpilogue +/// * buildOutlinedFrame /// * insertOutlinedCall -/// * insertOutlinerPrologue /// * isFunctionSafeToOutlineFrom /// /// in order to make use of the MachineOutliner. @@ -56,18 +55,22 @@ /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf /// //===----------------------------------------------------------------------===// +#include "llvm/CodeGen/MachineOutliner.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/TargetInstrInfo.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/IR/DIBuilder.h" #include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Mangler.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <functional> @@ -80,121 +83,23 @@ using namespace llvm; using namespace ore; +using namespace outliner; STATISTIC(NumOutlined, "Number of candidates outlined"); STATISTIC(FunctionsCreated, "Number of functions created"); -namespace { - -/// \brief An individual sequence of instructions to be replaced with a call to -/// an outlined function. -struct Candidate { -private: - /// The start index of this \p Candidate in the instruction list. - unsigned StartIdx; - - /// The number of instructions in this \p Candidate. - unsigned Len; - -public: - /// Set to false if the candidate overlapped with another candidate. - bool InCandidateList = true; - - /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of - /// \p OutlinedFunctions. - unsigned FunctionIdx; - - /// Contains all target-specific information for this \p Candidate. - TargetInstrInfo::MachineOutlinerInfo MInfo; - - /// Return the number of instructions in this Candidate. - unsigned getLength() const { return Len; } - - /// Return the start index of this candidate. - unsigned getStartIdx() const { return StartIdx; } - - // Return the end index of this candidate. - unsigned getEndIdx() const { return StartIdx + Len - 1; } - - /// \brief The number of instructions that would be saved by outlining every - /// candidate of this type. - /// - /// This is a fixed value which is not updated during the candidate pruning - /// process. It is only used for deciding which candidate to keep if two - /// candidates overlap. The true benefit is stored in the OutlinedFunction - /// for some given candidate. - unsigned Benefit = 0; - - Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx) - : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {} - - Candidate() {} - - /// \brief Used to ensure that \p Candidates are outlined in an order that - /// preserves the start and end indices of other \p Candidates. - bool operator<(const Candidate &RHS) const { - return getStartIdx() > RHS.getStartIdx(); - } -}; - -/// \brief The information necessary to create an outlined function for some -/// class of candidate. -struct OutlinedFunction { - -private: - /// The number of candidates for this \p OutlinedFunction. - unsigned OccurrenceCount = 0; - -public: - std::vector<std::shared_ptr<Candidate>> Candidates; - - /// The actual outlined function created. - /// This is initialized after we go through and create the actual function. - MachineFunction *MF = nullptr; - - /// A number assigned to this function which appears at the end of its name. - unsigned Name; +// 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)); - /// \brief The sequence of integers corresponding to the instructions in this - /// function. - std::vector<unsigned> Sequence; - - /// Contains all target-specific information for this \p OutlinedFunction. - TargetInstrInfo::MachineOutlinerInfo MInfo; - - /// Return the number of candidates for this \p OutlinedFunction. - unsigned getOccurrenceCount() { return OccurrenceCount; } - - /// Decrement the occurrence count of this OutlinedFunction and return the - /// new count. - unsigned decrement() { - assert(OccurrenceCount > 0 && "Can't decrement an empty function!"); - OccurrenceCount--; - return getOccurrenceCount(); - } - - /// \brief Return the number of instructions it would take to outline this - /// function. - unsigned getOutliningCost() { - return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() + - MInfo.FrameOverhead; - } - - /// \brief Return the number of instructions that would be saved by outlining - /// this function. - unsigned getBenefit() { - unsigned NotOutlinedCost = OccurrenceCount * Sequence.size(); - unsigned OutlinedCost = getOutliningCost(); - return (NotOutlinedCost < OutlinedCost) ? 0 - : NotOutlinedCost - OutlinedCost; - } - - OutlinedFunction(unsigned Name, unsigned OccurrenceCount, - const std::vector<unsigned> &Sequence, - TargetInstrInfo::MachineOutlinerInfo &MInfo) - : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence), - MInfo(MInfo) {} -}; +namespace { /// Represents an undefined index in the suffix tree. const unsigned EmptyIdx = -1; @@ -242,7 +147,7 @@ struct SuffixTreeNode { /// For all other nodes, this is ignored. unsigned SuffixIdx = EmptyIdx; - /// \brief For internal nodes, a pointer to the internal node representing + /// For internal nodes, a pointer to the internal node representing /// the same sequence with the first character chopped off. /// /// This acts as a shortcut in Ukkonen's algorithm. One of the things that @@ -356,7 +261,7 @@ private: /// The end index of each leaf in the tree. unsigned LeafEndIdx = -1; - /// \brief Helper struct which keeps track of the next insertion point in + /// Helper struct which keeps track of the next insertion point in /// Ukkonen's algorithm. struct ActiveState { /// The next node to insert at. @@ -369,7 +274,7 @@ private: unsigned Len = 0; }; - /// \brief The point the next insertion will take place at in the + /// The point the next insertion will take place at in the /// construction algorithm. ActiveState Active; @@ -416,7 +321,7 @@ private: return N; } - /// \brief Set the suffix indices of the leaves to the start indices of their + /// Set the suffix indices of the leaves to the start indices of their /// respective suffixes. Also stores each leaf in \p LeafVector at its /// respective suffix index. /// @@ -454,7 +359,7 @@ private: } } - /// \brief Construct the suffix tree for the prefix of the input ending at + /// Construct the suffix tree for the prefix of the input ending at /// \p EndIdx. /// /// Used to construct the full suffix tree iteratively. At the end of each @@ -615,16 +520,16 @@ public: } }; -/// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings. +/// Maps \p MachineInstrs to unsigned integers and stores the mappings. struct InstructionMapper { - /// \brief The next available integer to assign to a \p MachineInstr that + /// 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; - /// \brief The next available integer to assign to a \p MachineInstr that can + /// The next available integer to assign to a \p MachineInstr that can /// be outlined. unsigned LegalInstrNumber = 0; @@ -639,11 +544,11 @@ struct InstructionMapper { /// The vector of unsigned integers that the module is mapped to. std::vector<unsigned> UnsignedVec; - /// \brief Stores the location of the instruction associated with the integer + /// 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; - /// \brief Maps \p *It to a legal integer. + /// Maps \p *It to a legal integer. /// /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap, /// \p IntegerInstructionMap, and \p LegalInstrNumber. @@ -706,7 +611,7 @@ struct InstructionMapper { return MINumber; } - /// \brief Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds + /// 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. @@ -720,20 +625,29 @@ struct InstructionMapper { void convertToUnsignedVec(MachineBasicBlock &MBB, const TargetRegisterInfo &TRI, const TargetInstrInfo &TII) { + unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB); + for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et; It++) { // Keep track of where this instruction is in the module. - switch (TII.getOutliningType(*It)) { - case TargetInstrInfo::MachineOutlinerInstrType::Illegal: + switch (TII.getOutliningType(It, Flags)) { + case InstrType::Illegal: mapToIllegalUnsigned(It); break; - case TargetInstrInfo::MachineOutlinerInstrType::Legal: + case InstrType::Legal: mapToLegalUnsigned(It); break; - case TargetInstrInfo::MachineOutlinerInstrType::Invisible: + case InstrType::LegalTerminator: + mapToLegalUnsigned(It); + InstrList.push_back(It); + UnsignedVec.push_back(IllegalInstrNumber); + IllegalInstrNumber--; + break; + + case InstrType::Invisible: break; } } @@ -757,7 +671,7 @@ struct InstructionMapper { } }; -/// \brief An interprocedural pass which finds repeated sequences of +/// 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. @@ -770,10 +684,19 @@ struct MachineOutliner : public ModulePass { static char ID; - /// \brief Set to true if the outliner should consider functions with + /// Set to true if the outliner should consider functions with /// linkonceodr linkage. bool OutlineFromLinkOnceODRs = false; + /// 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; + + // Collection of IR functions created by the outliner. + std::vector<Function *> CreatedIRFunctions; + StringRef getPassName() const override { return "Machine Outliner"; } void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -783,27 +706,35 @@ struct MachineOutliner : public ModulePass { ModulePass::getAnalysisUsage(AU); } - MachineOutliner(bool OutlineFromLinkOnceODRs = false) - : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) { + 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. /// /// 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. + /// 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 ST A suffix tree to query. /// \param TII TargetInstrInfo for the target. /// \param Mapper Contains outlining mapping information. /// \param[out] CandidateList Filled with candidates representing each /// beneficial substring. - /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each - /// type of candidate. + /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions + /// each type of candidate. /// /// \returns The length of the longest candidate found. unsigned @@ -812,7 +743,7 @@ struct MachineOutliner : public ModulePass { std::vector<std::shared_ptr<Candidate>> &CandidateList, std::vector<OutlinedFunction> &FunctionList); - /// \brief Replace the sequences of instructions represented by the + /// Replace the sequences of instructions represented by the /// \p Candidates in \p CandidateList with calls to \p MachineFunctions /// described in \p FunctionList. /// @@ -852,7 +783,7 @@ struct MachineOutliner : public ModulePass { /// Removes \p C from the candidate list, and updates its \p OutlinedFunction. void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList); - /// \brief Remove any overlapping candidates that weren't handled by the + /// Remove any overlapping candidates that weren't handled by the /// suffix tree's pruning method. /// /// Pruning from the suffix tree doesn't necessarily remove all overlaps. @@ -873,6 +804,16 @@ struct MachineOutliner : public ModulePass { /// Construct a suffix tree on the instructions in \p M and outline repeated /// strings from that tree. bool runOnModule(Module &M) override; + + /// Return a DISubprogram for OF if one exists, and null otherwise. Helper + /// function for remark emission. + DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) { + DISubprogram *SP; + for (const std::shared_ptr<Candidate> &C : OF.Candidates) + if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram())) + return SP; + return nullptr; + } }; } // Anonymous namespace. @@ -880,8 +821,10 @@ struct MachineOutliner : public ModulePass { char MachineOutliner::ID = 0; namespace llvm { -ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) { - return new MachineOutliner(OutlineFromLinkOnceODRs); +ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) { + MachineOutliner *OL = new MachineOutliner(); + OL->RunOnAllFunctions = RunOnAllFunctions; + return OL; } } // namespace llvm @@ -889,6 +832,65 @@ ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) { INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) +void MachineOutliner::emitNotOutliningCheaperRemark( + unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, + OutlinedFunction &OF) { + 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.Sequence.size()) << " 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++) { + + // Skip over things that were pruned. + if (!OF.Candidates[i]->InCandidateList) + continue; + + R << NV((Twine("StartLoc") + Twine(i)).str(), + OF.Candidates[i]->front()->getDebugLoc()); + if (i != e - 1) + R << ", "; + } + + R << ")"; + + MORE.emit(R); +} + unsigned MachineOutliner::findCandidates( SuffixTree &ST, const TargetInstrInfo &TII, InstructionMapper &Mapper, std::vector<std::shared_ptr<Candidate>> &CandidateList, @@ -923,14 +925,6 @@ unsigned MachineOutliner::findCandidates( // this vector. std::vector<Candidate> CandidatesForRepeatedSeq; - // Describes the start and end point of each candidate. This allows the - // target to infer some information about each occurrence of each repeated - // sequence. - // FIXME: CandidatesForRepeatedSeq and this should be combined. - std::vector< - std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>> - RepeatedSequenceLocs; - // Figure out the call overhead for each instance of the sequence. for (auto &ChildPair : Parent.Children) { SuffixTreeNode *M = ChildPair.second; @@ -966,17 +960,18 @@ unsigned MachineOutliner::findCandidates( CandidatesForRepeatedSeq.end(), [&StartIdx, &EndIdx](const Candidate &C) { return (EndIdx < C.getStartIdx() || - StartIdx > C.getEndIdx()); + 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]; - // Save the candidate and its location. - CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, + CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, + EndIt, StartIt->getParent(), FunctionList.size()); - RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt)); } } } @@ -984,69 +979,33 @@ unsigned MachineOutliner::findCandidates( // We've found something we might want to outline. // Create an OutlinedFunction to store it and check if it'd be beneficial // to outline. - TargetInstrInfo::MachineOutlinerInfo MInfo = - TII.getOutlininingCandidateInfo(RepeatedSequenceLocs); + OutlinedFunction OF = + TII.getOutliningCandidateInfo(CandidatesForRepeatedSeq); + + // If we deleted every candidate, then there's nothing to outline. + if (OF.Candidates.empty()) + continue; + std::vector<unsigned> Seq; for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++) Seq.push_back(ST.Str[i]); - OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(), - Seq, MInfo); - unsigned Benefit = OF.getBenefit(); + OF.Sequence = Seq; + OF.Name = FunctionList.size(); // Is it better to outline this candidate than not? - if (Benefit < 1) { - // Outlining this candidate would take more instructions than not - // outlining. - // Emit a remark explaining why we didn't outline this candidate. - std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C = - RepeatedSequenceLocs[0]; - MachineOptimizationRemarkEmitter MORE( - *(C.first->getParent()->getParent()), nullptr); - MORE.emit([&]() { - MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper", - C.first->getDebugLoc(), - C.first->getParent()); - R << "Did not outline " << NV("Length", StringLen) << " instructions" - << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size()) - << " locations." - << " Instructions from outlining all occurrences (" - << NV("OutliningCost", OF.getOutliningCost()) << ")" - << " >= Unoutlined instruction count (" - << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")" - << " (Also found at: "; - - // Tell the user the other places the candidate was found. - for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) { - R << NV((Twine("OtherStartLoc") + Twine(i)).str(), - RepeatedSequenceLocs[i].first->getDebugLoc()); - if (i != e - 1) - R << ", "; - } - - R << ")"; - return R; - }); - - // Move to the next candidate. + if (OF.getBenefit() < 1) { + emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF); continue; } if (StringLen > MaxLen) MaxLen = StringLen; - // At this point, the candidate class is seen as beneficial. Set their - // benefit values and save them in the candidate list. - std::vector<std::shared_ptr<Candidate>> CandidatesForFn; - for (Candidate &C : CandidatesForRepeatedSeq) { - C.Benefit = Benefit; - C.MInfo = MInfo; - std::shared_ptr<Candidate> Cptr = std::make_shared<Candidate>(C); - CandidateList.push_back(Cptr); - CandidatesForFn.push_back(Cptr); - } - + // The function is beneficial. Save its candidates to the candidate list + // for pruning. + for (std::shared_ptr<Candidate> &C : OF.Candidates) + CandidateList.push_back(C); FunctionList.push_back(OF); - FunctionList.back().Candidates = CandidatesForFn; // Move to the next function. Parent.IsInTree = false; @@ -1067,11 +1026,11 @@ void MachineOutliner::prune(Candidate &C, // Remove C from the CandidateList. C.InCandidateList = false; - DEBUG(dbgs() << "- Removed a Candidate \n"; - dbgs() << "--- Num fns left for candidate: " << F.getOccurrenceCount() - << "\n"; - dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit() - << "\n";); + LLVM_DEBUG(dbgs() << "- Removed a Candidate \n"; + dbgs() << "--- Num fns left for candidate: " + << F.getOccurrenceCount() << "\n"; + dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit() + << "\n";); } void MachineOutliner::pruneOverlaps( @@ -1119,7 +1078,7 @@ void MachineOutliner::pruneOverlaps( if (C1.getStartIdx() > MaxCandidateLen) FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen; - // Compare against the candidates in the list that start at at most + // Compare against the candidates in the list that start at most // FarthestPossibleIdx indices away from C1. There are at most // MaxCandidateLen of these. for (auto Sit = It + 1; Sit != Et; Sit++) { @@ -1205,9 +1164,20 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, // 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::PrivateLinkage); + F->setLinkage(GlobalValue::InternalLinkage); F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); + // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's + // necessary. + + // Set optsize/minsize, so we don't insert padding between outlined + // functions. + F->addFnAttr(Attribute::OptimizeForSize); + F->addFnAttr(Attribute::MinSize); + + // Save F so that we can add debug info later if we need to. + CreatedIRFunctions.push_back(F); + BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F); IRBuilder<> Builder(EntryBB); Builder.CreateRetVoid(); @@ -1221,8 +1191,6 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, // Insert the new function into the module. MF.insert(MF.begin(), &MBB); - TII.insertOutlinerPrologue(MBB, MF, OF.MInfo); - // Copy over the instructions for the function using the integer mappings in // its sequence. for (unsigned Str : OF.Sequence) { @@ -1231,13 +1199,53 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, NewMI->dropMemRefs(); // Don't keep debug information for outlined instructions. - // FIXME: This means outlined functions are currently undebuggable. NewMI->setDebugLoc(DebugLoc()); MBB.insert(MBB.end(), NewMI); } - TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo); + 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; + + // Walk over each IR function we created in the outliner and create + // DISubprograms for each function. + for (Function *F : CreatedIRFunctions) { + // 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 *SP = DB.createFunction( + Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()), + Unit /* File */, + 0 /* Line 0 is reserved for compiler-generated code. */, + DB.createSubroutineType( + DB.getOrCreateTypeArray(None)), /* void type */ + false, true, 0, /* Line 0 is reserved for compiler-generated code. */ + DINode::DIFlags::FlagArtificial /* Compiler-generated code. */, + true /* Outlined code is optimized code by definition. */); + + // Don't add any new variables to the subprogram. + DB.finalizeSubprogram(SP); + + // Attach subprogram to the function. + F->setSubprogram(SP); + } + + // We're done with the DIBuilder. + DB.finalize(); + } + // Outlined functions shouldn't preserve liveness. + MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness); + MF.getRegInfo().freezeReservedRegs(MF); return &MF; } @@ -1260,79 +1268,73 @@ bool MachineOutliner::outline( if (OF.getBenefit() < 1) continue; - // If not, then outline it. - assert(C.getStartIdx() < Mapper.InstrList.size() && - "Candidate out of bounds!"); - MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent(); - MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()]; - unsigned EndIdx = C.getEndIdx(); - - assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!"); - MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; - assert(EndIt != MBB->end() && "EndIt out of bounds!"); - - EndIt++; // Erase needs one past the end index. - // Does this candidate have a function yet? if (!OF.MF) { OF.MF = createOutlinedFunction(M, OF, Mapper); - MachineBasicBlock *MBB = &*OF.MF->begin(); - - // Output a remark telling the user that an outlined function was created, - // and explaining where it came from. - MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr); - MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction", - MBB->findDebugLoc(MBB->begin()), MBB); - R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) - << " instructions by " - << "outlining " << NV("Length", OF.Sequence.size()) << " 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++) { - - // Skip over things that were pruned. - if (!OF.Candidates[i]->InCandidateList) - continue; - - R << NV( - (Twine("StartLoc") + Twine(i)).str(), - Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc()); - if (i != e - 1) - R << ", "; - } - - R << ")"; - - MORE.emit(R); + emitOutlinedFunctionRemark(OF); FunctionsCreated++; } MachineFunction *MF = OF.MF; + MachineBasicBlock &MBB = *C.getMBB(); + MachineBasicBlock::iterator StartIt = C.front(); + MachineBasicBlock::iterator EndIt = C.back(); + assert(StartIt != C.getMBB()->end() && "StartIt out of bounds!"); + assert(EndIt != C.getMBB()->end() && "EndIt out of bounds!"); + const TargetSubtargetInfo &STI = MF->getSubtarget(); const TargetInstrInfo &TII = *STI.getInstrInfo(); // Insert a call to the new function and erase the old sequence. - TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo); - StartIt = Mapper.InstrList[C.getStartIdx()]; - MBB->erase(StartIt, EndIt); + auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.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)) { + // Helper lambda for adding implicit def operands to the call instruction. + auto CopyDefs = [&CallInst](MachineInstr &MI) { + for (MachineOperand &MOP : MI.operands()) { + // Skip over anything that isn't a register. + if (!MOP.isReg()) + continue; + + // If it's a def, add it to the call instruction. + if (MOP.isDef()) + CallInst->addOperand( + MachineOperand::CreateReg(MOP.getReg(), true, /* isDef = true */ + true /* isImp = true */)); + } + }; + + // 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. + std::for_each(CallInst, std::next(EndIt), CopyDefs); + } + // 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)); OutlinedSomething = true; // Statistics. NumOutlined++; } - DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); + LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); return OutlinedSomething; } bool MachineOutliner::runOnModule(Module &M) { - - // Is there anything in the module at all? + // Check if there's anything in the module. If it's empty, then there's + // nothing to outline. if (M.empty()) return false; @@ -1342,25 +1344,67 @@ bool MachineOutliner::runOnModule(Module &M) { const TargetRegisterInfo *TRI = STI.getRegisterInfo(); const TargetInstrInfo *TII = STI.getInstrInfo(); + // 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; - // Build instruction mappings for each function in the module. + // Build instruction mappings for each function in the module. Start by + // iterating over each Function in M. for (Function &F : M) { - MachineFunction &MF = MMI.getOrCreateMachineFunction(F); - // Is the function empty? Safe to outline from? - if (F.empty() || - !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs)) + // If there's nothing in F, then there's no reason to try and outline from + // it. + if (F.empty()) + 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; + + if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF)) continue; - // If it is, look at each MachineBasicBlock in the function. - for (MachineBasicBlock &MBB : MF) { + // 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; - // Is there anything in MBB? + // 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 (MBB.empty()) continue; - // If yes, map it. + // 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, *TRI, *TII); } } @@ -1378,5 +1422,7 @@ bool MachineOutliner::runOnModule(Module &M) { pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII); // Outline each of the candidates and return true if something was outlined. - return outline(M, CandidateList, FunctionList, Mapper); + bool OutlinedSomething = outline(M, CandidateList, FunctionList, Mapper); + + return OutlinedSomething; } |