diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/MachineOutliner.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/MachineOutliner.cpp | 851 |
1 files changed, 491 insertions, 360 deletions
diff --git a/contrib/llvm/lib/CodeGen/MachineOutliner.cpp b/contrib/llvm/lib/CodeGen/MachineOutliner.cpp index fd6b2427891d..e4eb8802ac66 100644 --- a/contrib/llvm/lib/CodeGen/MachineOutliner.cpp +++ b/contrib/llvm/lib/CodeGen/MachineOutliner.cpp @@ -15,6 +15,23 @@ /// 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 +/// * insertOutlinerEpilogue +/// * insertOutlinedCall +/// * insertOutlinerPrologue +/// * 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 @@ -42,19 +59,17 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" -#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/IR/IRBuilder.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtargetInfo.h" #include <functional> #include <map> #include <sstream> @@ -64,6 +79,7 @@ #define DEBUG_TYPE "machine-outliner" using namespace llvm; +using namespace ore; STATISTIC(NumOutlined, "Number of candidates outlined"); STATISTIC(FunctionsCreated, "Number of functions created"); @@ -73,19 +89,32 @@ 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; - /// The start index of this \p Candidate. - size_t StartIdx; + /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of + /// \p OutlinedFunctions. + unsigned FunctionIdx; - /// The number of instructions in this \p Candidate. - size_t Len; + /// Contains all target-specific information for this \p Candidate. + TargetInstrInfo::MachineOutlinerInfo MInfo; - /// The index of this \p Candidate's \p OutlinedFunction in the list of - /// \p OutlinedFunctions. - size_t FunctionIdx; + /// 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. @@ -96,51 +125,79 @@ struct Candidate { /// for some given candidate. unsigned Benefit = 0; - Candidate(size_t StartIdx, size_t Len, size_t FunctionIdx) + 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 StartIdx > RHS.StartIdx; } + 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. - size_t Name; - - /// The number of candidates for this OutlinedFunction. - size_t OccurrenceCount = 0; + unsigned Name; /// \brief The sequence of integers corresponding to the instructions in this /// function. std::vector<unsigned> Sequence; - /// The number of instructions this function would save. - unsigned Benefit = 0; + /// 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 Set to true if candidates for this outlined function should be - /// replaced with tail calls to this OutlinedFunction. - bool IsTailCall = false; + /// \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(size_t Name, size_t OccurrenceCount, + OutlinedFunction(unsigned Name, unsigned OccurrenceCount, const std::vector<unsigned> &Sequence, - unsigned Benefit, bool IsTailCall) - : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence), - Benefit(Benefit), IsTailCall(IsTailCall) - {} + TargetInstrInfo::MachineOutlinerInfo &MInfo) + : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence), + MInfo(MInfo) {} }; /// Represents an undefined index in the suffix tree. -const size_t EmptyIdx = -1; +const unsigned EmptyIdx = -1; /// A node in a suffix tree which represents a substring or suffix. /// @@ -170,7 +227,7 @@ struct SuffixTreeNode { bool IsInTree = true; /// The start index of this node's substring in the main string. - size_t StartIdx = EmptyIdx; + unsigned StartIdx = EmptyIdx; /// The end index of this node's substring in the main string. /// @@ -178,24 +235,23 @@ struct SuffixTreeNode { /// step in the construction algorithm. To avoid having to update O(N) /// nodes individually at the end of every step, the end index is stored /// as a pointer. - size_t *EndIdx = nullptr; + unsigned *EndIdx = nullptr; /// For leaves, the start index of the suffix represented by this node. /// /// For all other nodes, this is ignored. - size_t SuffixIdx = EmptyIdx; + unsigned SuffixIdx = EmptyIdx; /// \brief For internal nodes, a pointer to the internal node representing /// the same sequence with the first character chopped off. /// - /// This has two major purposes in the suffix tree. The first is as a - /// shortcut in Ukkonen's construction algorithm. One of the things that + /// This acts as a shortcut in Ukkonen's algorithm. One of the things that /// Ukkonen's algorithm does to achieve linear-time construction is /// keep track of which node the next insert should be at. This makes each /// insert O(1), and there are a total of O(N) inserts. The suffix link /// helps with inserting children of internal nodes. /// - /// Say we add a child to an internal node with associated mapping S. The + /// Say we add a child to an internal node with associated mapping S. The /// next insertion must be at the node representing S - its first character. /// This is given by the way that we iteratively build the tree in Ukkonen's /// algorithm. The main idea is to look at the suffixes of each prefix in the @@ -204,27 +260,6 @@ struct SuffixTreeNode { /// move to the next insertion point in O(1) time. If we don't, then we'd /// have to query from the root, which takes O(N) time. This would make the /// construction algorithm O(N^2) rather than O(N). - /// - /// The suffix link is also used during the tree pruning process to let us - /// quickly throw out a bunch of potential overlaps. Say we have a sequence - /// S we want to outline. Then each of its suffixes contribute to at least - /// one overlapping case. Therefore, we can follow the suffix links - /// starting at the node associated with S to the root and "delete" those - /// nodes, save for the root. For each candidate, this removes - /// O(|candidate|) overlaps from the search space. We don't actually - /// completely invalidate these nodes though; doing that is far too - /// aggressive. Consider the following pathological string: - /// - /// 1 2 3 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 - /// - /// If we, for the sake of example, outlined 1 2 3, then we would throw - /// out all instances of 2 3. This isn't desirable. To get around this, - /// when we visit a link node, we decrement its occurrence count by the - /// number of sequences we outlined in the current step. In the pathological - /// example, the 2 3 node would have an occurrence count of 8, while the - /// 1 2 3 node would have an occurrence count of 2. Thus, the 2 3 node - /// would survive to the next round allowing us to outline the extra - /// instances of 2 3. SuffixTreeNode *Link = nullptr; /// The parent of this node. Every node except for the root has a parent. @@ -234,11 +269,11 @@ struct SuffixTreeNode { /// /// This is equal to the number of leaf children of the string. It represents /// the number of suffixes that the node's string is a prefix of. - size_t OccurrenceCount = 0; + unsigned OccurrenceCount = 0; /// The length of the string formed by concatenating the edge labels from the /// root to this node. - size_t ConcatLen = 0; + unsigned ConcatLen = 0; /// Returns true if this node is a leaf. bool isLeaf() const { return SuffixIdx != EmptyIdx; } @@ -260,7 +295,7 @@ struct SuffixTreeNode { return *EndIdx - StartIdx + 1; } - SuffixTreeNode(size_t StartIdx, size_t *EndIdx, SuffixTreeNode *Link, + SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link, SuffixTreeNode *Parent) : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {} @@ -290,10 +325,16 @@ struct SuffixTreeNode { /// /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf class SuffixTree { -private: +public: + /// Stores each leaf node in the tree. + /// + /// This is used for finding outlining candidates. + std::vector<SuffixTreeNode *> LeafVector; + /// Each element is an integer representing an instruction in the module. ArrayRef<unsigned> Str; +private: /// Maintains each node in the tree. SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator; @@ -303,11 +344,6 @@ private: /// \p NodeAllocator like every other node in the tree. SuffixTreeNode *Root = nullptr; - /// Stores each leaf node in the tree. - /// - /// This is used for finding outlining candidates. - std::vector<SuffixTreeNode *> LeafVector; - /// Maintains the end indices of the internal nodes in the tree. /// /// Each internal node is guaranteed to never have its end index change @@ -318,7 +354,7 @@ private: BumpPtrAllocator InternalEndIdxAllocator; /// The end index of each leaf in the tree. - size_t LeafEndIdx = -1; + unsigned LeafEndIdx = -1; /// \brief Helper struct which keeps track of the next insertion point in /// Ukkonen's algorithm. @@ -327,10 +363,10 @@ private: SuffixTreeNode *Node; /// The index of the first character in the substring currently being added. - size_t Idx = EmptyIdx; + unsigned Idx = EmptyIdx; /// The length of the substring we have to add at the current step. - size_t Len = 0; + unsigned Len = 0; }; /// \brief The point the next insertion will take place at in the @@ -344,15 +380,13 @@ private: /// \param Edge The label on the edge leaving \p Parent to this node. /// /// \returns A pointer to the allocated leaf node. - SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, size_t StartIdx, + SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx, unsigned Edge) { assert(StartIdx <= LeafEndIdx && "String can't start after it ends!"); - SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx, - &LeafEndIdx, - nullptr, - &Parent); + SuffixTreeNode *N = new (NodeAllocator.Allocate()) + SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent); Parent.Children[Edge] = N; return N; @@ -366,18 +400,16 @@ private: /// \param Edge The label on the edge leaving \p Parent to this node. /// /// \returns A pointer to the allocated internal node. - SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, size_t StartIdx, - size_t EndIdx, unsigned Edge) { + SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx, + unsigned EndIdx, unsigned Edge) { assert(StartIdx <= EndIdx && "String can't start after it ends!"); assert(!(!Parent && StartIdx != EmptyIdx) && - "Non-root internal nodes must have parents!"); + "Non-root internal nodes must have parents!"); - size_t *E = new (InternalEndIdxAllocator) size_t(EndIdx); - SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx, - E, - Root, - Parent); + unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx); + SuffixTreeNode *N = new (NodeAllocator.Allocate()) + SuffixTreeNode(StartIdx, E, Root, Parent); if (Parent) Parent->Children[Edge] = N; @@ -390,7 +422,7 @@ private: /// /// \param[in] CurrNode The node currently being visited. /// \param CurrIdx The current index of the string being visited. - void setSuffixIndices(SuffixTreeNode &CurrNode, size_t CurrIdx) { + void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) { bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot(); @@ -401,14 +433,13 @@ private: CurrNode.ConcatLen = CurrNode.size(); if (CurrNode.Parent) - CurrNode.ConcatLen += CurrNode.Parent->ConcatLen; + CurrNode.ConcatLen += CurrNode.Parent->ConcatLen; } // Traverse the tree depth-first. for (auto &ChildPair : CurrNode.Children) { assert(ChildPair.second && "Node had a null child!"); - setSuffixIndices(*ChildPair.second, - CurrIdx + ChildPair.second->size()); + setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size()); } // Is this node a leaf? @@ -437,11 +468,11 @@ private: /// /// \returns The number of suffixes that have not been added at the end of /// this step. - unsigned extend(size_t EndIdx, size_t SuffixesToAdd) { + unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) { SuffixTreeNode *NeedsLink = nullptr; while (SuffixesToAdd > 0) { - + // Are we waiting to add anything other than just the last character? if (Active.Len == 0) { // If not, then say the active index is the end index. @@ -469,7 +500,7 @@ private: // insert a new node. SuffixTreeNode *NextNode = Active.Node->Children[FirstChar]; - size_t SubstringLen = NextNode->size(); + unsigned SubstringLen = NextNode->size(); // Is the current suffix we're trying to insert longer than the size of // the child we want to move to? @@ -515,10 +546,8 @@ private: // The node s from the diagram SuffixTreeNode *SplitNode = - insertInternalNode(Active.Node, - NextNode->StartIdx, - NextNode->StartIdx + Active.Len - 1, - FirstChar); + insertInternalNode(Active.Node, NextNode->StartIdx, + NextNode->StartIdx + Active.Len - 1, FirstChar); // Insert the new node representing the new substring into the tree as // a child of the split node. This is the node l from the diagram. @@ -556,87 +585,6 @@ private: } public: - - /// Find all repeated substrings that satisfy \p BenefitFn. - /// - /// 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[out] CandidateList Filled with candidates representing each - /// beneficial substring. - /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each - /// type of candidate. - /// \param BenefitFn The function to satisfy. - /// - /// \returns The length of the longest candidate found. - size_t findCandidates(std::vector<Candidate> &CandidateList, - std::vector<OutlinedFunction> &FunctionList, - const std::function<unsigned(SuffixTreeNode &, size_t, unsigned)> - &BenefitFn) { - - CandidateList.clear(); - FunctionList.clear(); - size_t FnIdx = 0; - size_t MaxLen = 0; - - for (SuffixTreeNode* Leaf : LeafVector) { - assert(Leaf && "Leaves in LeafVector cannot be null!"); - if (!Leaf->IsInTree) - continue; - - assert(Leaf->Parent && "All leaves must have parents!"); - SuffixTreeNode &Parent = *(Leaf->Parent); - - // If it doesn't appear enough, or we already outlined from it, skip it. - if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree) - continue; - - size_t StringLen = Leaf->ConcatLen - Leaf->size(); - - // How many instructions would outlining this string save? - unsigned Benefit = BenefitFn(Parent, - StringLen, Str[Leaf->SuffixIdx + StringLen - 1]); - - // If it's not beneficial, skip it. - if (Benefit < 1) - continue; - - if (StringLen > MaxLen) - MaxLen = StringLen; - - unsigned OccurrenceCount = 0; - for (auto &ChildPair : Parent.Children) { - SuffixTreeNode *M = ChildPair.second; - - // Is it a leaf? If so, we have an occurrence of this candidate. - if (M && M->IsInTree && M->isLeaf()) { - OccurrenceCount++; - CandidateList.emplace_back(M->SuffixIdx, StringLen, FnIdx); - CandidateList.back().Benefit = Benefit; - M->IsInTree = false; - } - } - - // Save the function for the new candidate sequence. - std::vector<unsigned> CandidateSequence; - for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++) - CandidateSequence.push_back(Str[i]); - - FunctionList.emplace_back(FnIdx, OccurrenceCount, CandidateSequence, - Benefit, false); - - // Move to the next function. - FnIdx++; - Parent.IsInTree = false; - } - - return MaxLen; - } - /// Construct a suffix tree from a sequence of unsigned integers. /// /// \param Str The string to construct the suffix tree for. @@ -644,17 +592,18 @@ public: Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0); Root->IsInTree = true; Active.Node = Root; - LeafVector = std::vector<SuffixTreeNode*>(Str.size()); + LeafVector = std::vector<SuffixTreeNode *>(Str.size()); // Keep track of the number of suffixes we have to add of the current // prefix. - size_t SuffixesToAdd = 0; + unsigned SuffixesToAdd = 0; Active.Node = Root; // Construct the suffix tree iteratively on each prefix of the string. // PfxEndIdx is the end index of the current prefix. // End is one past the last element in the string. - for (size_t PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; PfxEndIdx++) { + for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; + PfxEndIdx++) { SuffixesToAdd++; LeafEndIdx = PfxEndIdx; // Extend each of the leaves. SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd); @@ -708,9 +657,9 @@ struct InstructionMapper { MachineInstr &MI = *It; bool WasInserted; DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator - ResultIt; + ResultIt; std::tie(ResultIt, WasInserted) = - InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber)); + InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber)); unsigned MINumber = ResultIt->second; // There was an insertion. @@ -725,10 +674,10 @@ struct InstructionMapper { 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."); + 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."); return MINumber; } @@ -748,13 +697,11 @@ struct InstructionMapper { assert(LegalInstrNumber < IllegalInstrNumber && "Instruction mapping overflow!"); - assert(IllegalInstrNumber != - DenseMapInfo<unsigned>::getEmptyKey() && - "IllegalInstrNumber cannot be DenseMap tombstone or empty key!"); + 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!"); + assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() && + "IllegalInstrNumber cannot be DenseMap tombstone or empty key!"); return MINumber; } @@ -777,17 +724,17 @@ struct InstructionMapper { It++) { // Keep track of where this instruction is in the module. - switch(TII.getOutliningType(*It)) { - case TargetInstrInfo::MachineOutlinerInstrType::Illegal: - mapToIllegalUnsigned(It); - break; + switch (TII.getOutliningType(*It)) { + case TargetInstrInfo::MachineOutlinerInstrType::Illegal: + mapToIllegalUnsigned(It); + break; - case TargetInstrInfo::MachineOutlinerInstrType::Legal: - mapToLegalUnsigned(It); - break; + case TargetInstrInfo::MachineOutlinerInstrType::Legal: + mapToLegalUnsigned(It); + break; - case TargetInstrInfo::MachineOutlinerInstrType::Invisible: - break; + case TargetInstrInfo::MachineOutlinerInstrType::Invisible: + break; } } @@ -804,9 +751,9 @@ struct 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!"); + "DenseMapInfo<unsigned>'s empty key isn't -1!"); assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 && - "DenseMapInfo<unsigned>'s tombstone key isn't -2!"); + "DenseMapInfo<unsigned>'s tombstone key isn't -2!"); } }; @@ -823,6 +770,10 @@ struct MachineOutliner : public ModulePass { static char ID; + /// \brief Set to true if the outliner should consider functions with + /// linkonceodr linkage. + bool OutlineFromLinkOnceODRs = false; + StringRef getPassName() const override { return "Machine Outliner"; } void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -832,10 +783,35 @@ struct MachineOutliner : public ModulePass { ModulePass::getAnalysisUsage(AU); } - MachineOutliner() : ModulePass(ID) { + MachineOutliner(bool OutlineFromLinkOnceODRs = false) + : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) { initializeMachineOutlinerPass(*PassRegistry::getPassRegistry()); } + /// 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. + /// + /// \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. + /// + /// \returns The length of the longest candidate found. + unsigned + findCandidates(SuffixTree &ST, const TargetInstrInfo &TII, + InstructionMapper &Mapper, + std::vector<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList); + /// \brief Replace the sequences of instructions represented by the /// \p Candidates in \p CandidateList with calls to \p MachineFunctions /// described in \p FunctionList. @@ -844,7 +820,8 @@ struct MachineOutliner : public ModulePass { /// \param CandidateList A list of candidates to be outlined. /// \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, const ArrayRef<Candidate> &CandidateList, + bool outline(Module &M, + const ArrayRef<std::shared_ptr<Candidate>> &CandidateList, std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper); @@ -865,11 +842,15 @@ struct MachineOutliner : public ModulePass { /// \param TII TargetInstrInfo for the module. /// /// \returns The length of the longest candidate found. 0 if there are none. - unsigned buildCandidateList(std::vector<Candidate> &CandidateList, - std::vector<OutlinedFunction> &FunctionList, - SuffixTree &ST, - InstructionMapper &Mapper, - const TargetInstrInfo &TII); + unsigned + buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList, + SuffixTree &ST, InstructionMapper &Mapper, + const TargetInstrInfo &TII); + + /// Helper function for pruneOverlaps. + /// 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 /// suffix tree's pruning method. @@ -881,11 +862,12 @@ struct MachineOutliner : public ModulePass { /// /// \param[in,out] CandidateList A list of outlining candidates. /// \param[in,out] FunctionList A list of functions to be outlined. + /// \param Mapper Contains instruction mapping info for outlining. /// \param MaxCandidateLen The length of the longest candidate. /// \param TII TargetInstrInfo for the module. - void pruneOverlaps(std::vector<Candidate> &CandidateList, + void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList, std::vector<OutlinedFunction> &FunctionList, - unsigned MaxCandidateLen, + InstructionMapper &Mapper, unsigned MaxCandidateLen, const TargetInstrInfo &TII); /// Construct a suffix tree on the instructions in \p M and outline repeated @@ -898,16 +880,223 @@ struct MachineOutliner : public ModulePass { char MachineOutliner::ID = 0; namespace llvm { -ModulePass *createMachineOutlinerPass() { return new MachineOutliner(); } +ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) { + return new MachineOutliner(OutlineFromLinkOnceODRs); +} + +} // namespace llvm + +INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, + false) + +unsigned MachineOutliner::findCandidates( + SuffixTree &ST, const TargetInstrInfo &TII, InstructionMapper &Mapper, + std::vector<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList) { + CandidateList.clear(); + FunctionList.clear(); + unsigned MaxLen = 0; + + // FIXME: Visit internal nodes instead of leaves. + for (SuffixTreeNode *Leaf : ST.LeafVector) { + assert(Leaf && "Leaves in LeafVector cannot be null!"); + if (!Leaf->IsInTree) + continue; + + assert(Leaf->Parent && "All leaves must have parents!"); + SuffixTreeNode &Parent = *(Leaf->Parent); + + // If it doesn't appear enough, or we already outlined from it, skip it. + if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree) + continue; + + // Figure out if this candidate is beneficial. + unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size(); + + // Too short to be beneficial; skip it. + // FIXME: This isn't necessarily true for, say, X86. If we factor in + // instruction lengths we need more information than this. + if (StringLen < 2) + continue; + + // If this is a beneficial class of candidate, then every one is stored in + // 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; + + if (M && M->IsInTree && M->isLeaf()) { + // Never visit this leaf again. + M->IsInTree = false; + unsigned StartIdx = M->SuffixIdx; + 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 (std::all_of(CandidatesForRepeatedSeq.begin(), + CandidatesForRepeatedSeq.end(), + [&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]. + MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; + MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; + + // Save the candidate and its location. + CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, + FunctionList.size()); + RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt)); + } + } + } + + // 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); + 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(); + + // 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. + 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); + } + + FunctionList.push_back(OF); + FunctionList.back().Candidates = CandidatesForFn; + + // Move to the next function. + Parent.IsInTree = false; + } + + return MaxLen; +} + +// Remove C from the candidate space, and update its OutlinedFunction. +void MachineOutliner::prune(Candidate &C, + std::vector<OutlinedFunction> &FunctionList) { + // Get the OutlinedFunction associated with this Candidate. + OutlinedFunction &F = FunctionList[C.FunctionIdx]; + + // Update C's associated function's occurrence count. + F.decrement(); + + // 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";); } -INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, - "Machine Function Outliner", false, false) +void MachineOutliner::pruneOverlaps( + std::vector<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper, + unsigned MaxCandidateLen, const TargetInstrInfo &TII) { + + // Return true if this candidate became unbeneficial for outlining in a + // previous step. + auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) { + + // Check if the candidate was removed in a previous step. + if (!C.InCandidateList) + return true; + + // C must be alive. Check if we should remove it. + if (FunctionList[C.FunctionIdx].getBenefit() < 1) { + prune(C, FunctionList); + return true; + } + + // C is in the list, and F is still beneficial. + return false; + }; -void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList, - std::vector<OutlinedFunction> &FunctionList, - unsigned MaxCandidateLen, - const TargetInstrInfo &TII) { // TODO: Experiment with interval trees or other interval-checking structures // to lower the time complexity of this function. // TODO: Can we do better than the simple greedy choice? @@ -915,56 +1104,35 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList, // This is O(MaxCandidateLen * CandidateList.size()). for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et; It++) { - Candidate &C1 = *It; - OutlinedFunction &F1 = FunctionList[C1.FunctionIdx]; + Candidate &C1 = **It; - // If we removed this candidate, skip it. - if (!C1.InCandidateList) + // If C1 was already pruned, or its function is no longer beneficial for + // outlining, move to the next candidate. + if (ShouldSkipCandidate(C1)) continue; - // Is it still worth it to outline C1? - if (F1.Benefit < 1 || F1.OccurrenceCount < 2) { - assert(F1.OccurrenceCount > 0 && - "Can't remove OutlinedFunction with no occurrences!"); - F1.OccurrenceCount--; - C1.InCandidateList = false; - continue; - } - // The minimum start index of any candidate that could overlap with this // one. unsigned FarthestPossibleIdx = 0; // Either the index is 0, or it's at most MaxCandidateLen indices away. - if (C1.StartIdx > MaxCandidateLen) - FarthestPossibleIdx = C1.StartIdx - MaxCandidateLen; + if (C1.getStartIdx() > MaxCandidateLen) + FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen; // Compare against the candidates in the list that start at at most // FarthestPossibleIdx indices away from C1. There are at most // MaxCandidateLen of these. for (auto Sit = It + 1; Sit != Et; Sit++) { - Candidate &C2 = *Sit; - OutlinedFunction &F2 = FunctionList[C2.FunctionIdx]; + Candidate &C2 = **Sit; // Is this candidate too far away to overlap? - if (C2.StartIdx < FarthestPossibleIdx) + if (C2.getStartIdx() < FarthestPossibleIdx) break; - // Did we already remove this candidate in a previous step? - if (!C2.InCandidateList) - continue; - - // Is the function beneficial to outline? - if (F2.OccurrenceCount < 2 || F2.Benefit < 1) { - // If not, remove this candidate and move to the next one. - assert(F2.OccurrenceCount > 0 && - "Can't remove OutlinedFunction with no occurrences!"); - F2.OccurrenceCount--; - C2.InCandidateList = false; + // If C2 was already pruned, or its function is no longer beneficial for + // outlining, move to the next candidate. + if (ShouldSkipCandidate(C2)) continue; - } - - size_t C2End = C2.StartIdx + C2.Len - 1; // Do C1 and C2 overlap? // @@ -974,7 +1142,7 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList, // We sorted our candidate list so C2Start <= C1Start. We know that // C2End > C2Start since each candidate has length >= 2. Therefore, all we // have to check is C2End < C2Start to see if we overlap. - if (C2End < C1.StartIdx) + if (C2.getEndIdx() < C1.getStartIdx()) continue; // C1 and C2 overlap. @@ -982,118 +1150,52 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList, // // Approximate this by picking the one which would have saved us the // most instructions before any pruning. - if (C1.Benefit >= C2.Benefit) { - - // C1 is better, so remove C2 and update C2's OutlinedFunction to - // reflect the removal. - assert(F2.OccurrenceCount > 0 && - "Can't remove OutlinedFunction with no occurrences!"); - F2.OccurrenceCount--; - F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(), - F2.OccurrenceCount, - F2.IsTailCall - ); - - C2.InCandidateList = false; - - DEBUG ( - dbgs() << "- Removed C2. \n"; - dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n"; - dbgs() << "--- C2's benefit: " << F2.Benefit << "\n"; - ); - } else { - // C2 is better, so remove C1 and update C1's OutlinedFunction to - // reflect the removal. - assert(F1.OccurrenceCount > 0 && - "Can't remove OutlinedFunction with no occurrences!"); - F1.OccurrenceCount--; - F1.Benefit = TII.getOutliningBenefit(F1.Sequence.size(), - F1.OccurrenceCount, - F1.IsTailCall - ); - C1.InCandidateList = false; - - DEBUG ( - dbgs() << "- Removed C1. \n"; - dbgs() << "--- Num fns left for C1: " << F1.OccurrenceCount << "\n"; - dbgs() << "--- C1's benefit: " << F1.Benefit << "\n"; - ); - - // C1 is out, so we don't have to compare it against anyone else. + // Is C2 a better candidate? + if (C2.Benefit > C1.Benefit) { + // Yes, so prune C1. Since C1 is dead, we don't have to compare it + // against anything anymore, so break. + prune(C1, FunctionList); break; } + + // Prune C2 and move on to the next candidate. + prune(C2, FunctionList); } } } -unsigned -MachineOutliner::buildCandidateList(std::vector<Candidate> &CandidateList, - std::vector<OutlinedFunction> &FunctionList, - SuffixTree &ST, - InstructionMapper &Mapper, - const TargetInstrInfo &TII) { +unsigned MachineOutliner::buildCandidateList( + std::vector<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST, + InstructionMapper &Mapper, const TargetInstrInfo &TII) { std::vector<unsigned> CandidateSequence; // Current outlining candidate. - size_t MaxCandidateLen = 0; // Length of the longest candidate. - - // Function for maximizing query in the suffix tree. - // This allows us to define more fine-grained types of things to outline in - // the target without putting target-specific info in the suffix tree. - auto BenefitFn = [&TII, &Mapper](const SuffixTreeNode &Curr, - size_t StringLen, unsigned EndVal) { - - // The root represents the empty string. - if (Curr.isRoot()) - return 0u; - - // Is this long enough to outline? - // TODO: Let the target decide how "long" a string is in terms of the sizes - // of the instructions in the string. For example, if a call instruction - // is smaller than a one instruction string, we should outline that string. - if (StringLen < 2) - return 0u; - - size_t Occurrences = Curr.OccurrenceCount; + unsigned MaxCandidateLen = 0; // Length of the longest candidate. - // Anything we want to outline has to appear at least twice. - if (Occurrences < 2) - return 0u; - - // Check if the last instruction in the sequence is a return. - MachineInstr *LastInstr = - Mapper.IntegerInstructionMap[EndVal]; - assert(LastInstr && "Last instruction in sequence was unmapped!"); - - // The only way a terminator could be mapped as legal is if it was safe to - // tail call. - bool IsTailCall = LastInstr->isTerminator(); - return TII.getOutliningBenefit(StringLen, Occurrences, IsTailCall); - }; - - MaxCandidateLen = ST.findCandidates(CandidateList, FunctionList, BenefitFn); - - for (auto &OF : FunctionList) - OF.IsTailCall = Mapper. - IntegerInstructionMap[OF.Sequence.back()]->isTerminator(); + MaxCandidateLen = + findCandidates(ST, TII, Mapper, CandidateList, FunctionList); // Sort the candidates in decending order. This will simplify the outlining // process when we have to remove the candidates from the mapping by // allowing us to cut them out without keeping track of an offset. - std::stable_sort(CandidateList.begin(), CandidateList.end()); + std::stable_sort( + CandidateList.begin(), CandidateList.end(), + [](const std::shared_ptr<Candidate> &LHS, + const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; }); return MaxCandidateLen; } MachineFunction * MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, - InstructionMapper &Mapper) { + InstructionMapper &Mapper) { // Create the function name. This should be unique. For now, just hash the // module name and include it in the function name plus the number of this // function. std::ostringstream NameStream; - NameStream << "OUTLINED_FUNCTION" << "_" << OF.Name; + NameStream << "OUTLINED_FUNCTION_" << OF.Name; // Create the function using an IR-level function. LLVMContext &C = M.getContext(); @@ -1119,7 +1221,7 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, // Insert the new function into the module. MF.insert(MF.begin(), &MBB); - TII.insertOutlinerPrologue(MBB, MF, OF.IsTailCall); + TII.insertOutlinerPrologue(MBB, MF, OF.MInfo); // Copy over the instructions for the function using the integer mappings in // its sequence. @@ -1134,21 +1236,19 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF, MBB.insert(MBB.end(), NewMI); } - TII.insertOutlinerEpilogue(MBB, MF, OF.IsTailCall); + TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo); return &MF; } -bool MachineOutliner::outline(Module &M, - const ArrayRef<Candidate> &CandidateList, - std::vector<OutlinedFunction> &FunctionList, - InstructionMapper &Mapper) { +bool MachineOutliner::outline( + Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList, + std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) { bool OutlinedSomething = false; - // Replace the candidates with calls to their respective outlined functions. - for (const Candidate &C : CandidateList) { - + for (const std::shared_ptr<Candidate> &Cptr : CandidateList) { + Candidate &C = *Cptr; // Was the candidate removed during pruneOverlaps? if (!C.InCandidateList) continue; @@ -1157,14 +1257,15 @@ bool MachineOutliner::outline(Module &M, OutlinedFunction &OF = FunctionList[C.FunctionIdx]; // Was its OutlinedFunction made unbeneficial during pruneOverlaps? - if (OF.OccurrenceCount < 2 || OF.Benefit < 1) + if (OF.getBenefit() < 1) continue; // If not, then outline it. - assert(C.StartIdx < Mapper.InstrList.size() && "Candidate out of bounds!"); - MachineBasicBlock *MBB = (*Mapper.InstrList[C.StartIdx]).getParent(); - MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.StartIdx]; - unsigned EndIdx = C.StartIdx + C.Len - 1; + 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]; @@ -1175,6 +1276,37 @@ bool MachineOutliner::outline(Module &M, // 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); FunctionsCreated++; } @@ -1183,8 +1315,8 @@ bool MachineOutliner::outline(Module &M, const TargetInstrInfo &TII = *STI.getInstrInfo(); // Insert a call to the new function and erase the old sequence. - TII.insertOutlinedCall(M, *MBB, StartIt, *MF, OF.IsTailCall); - StartIt = Mapper.InstrList[C.StartIdx]; + TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo); + StartIt = Mapper.InstrList[C.getStartIdx()]; MBB->erase(StartIt, EndIt); OutlinedSomething = true; @@ -1193,9 +1325,7 @@ bool MachineOutliner::outline(Module &M, NumOutlined++; } - DEBUG ( - dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n"; - ); + DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); return OutlinedSomething; } @@ -1207,8 +1337,8 @@ bool MachineOutliner::runOnModule(Module &M) { return false; MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>(); - const TargetSubtargetInfo &STI = MMI.getOrCreateMachineFunction(*M.begin()) - .getSubtarget(); + const TargetSubtargetInfo &STI = + MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget(); const TargetRegisterInfo *TRI = STI.getRegisterInfo(); const TargetInstrInfo *TII = STI.getInstrInfo(); @@ -1219,7 +1349,8 @@ bool MachineOutliner::runOnModule(Module &M) { MachineFunction &MF = MMI.getOrCreateMachineFunction(F); // Is the function empty? Safe to outline from? - if (F.empty() || !TII->isFunctionSafeToOutlineFrom(MF)) + if (F.empty() || + !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs)) continue; // If it is, look at each MachineBasicBlock in the function. @@ -1236,7 +1367,7 @@ bool MachineOutliner::runOnModule(Module &M) { // Construct a suffix tree, use it to find candidates, and then outline them. SuffixTree ST(Mapper.UnsignedVec); - std::vector<Candidate> CandidateList; + std::vector<std::shared_ptr<Candidate>> CandidateList; std::vector<OutlinedFunction> FunctionList; // Find all of the outlining candidates. @@ -1244,7 +1375,7 @@ bool MachineOutliner::runOnModule(Module &M) { buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII); // Remove candidates that overlap with other candidates. - pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII); + pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII); // Outline each of the candidates and return true if something was outlined. return outline(M, CandidateList, FunctionList, Mapper); |