| //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \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 |
| /// * 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 |
| /// |
| /// 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/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/IR/IRBuilder.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Target/TargetMachine.h" |
| #include "llvm/Target/TargetRegisterInfo.h" |
| #include "llvm/Target/TargetSubtargetInfo.h" |
| #include <functional> |
| #include <map> |
| #include <sstream> |
| #include <tuple> |
| #include <vector> |
| |
| #define DEBUG_TYPE "machine-outliner" |
| |
| using namespace llvm; |
| using namespace ore; |
| |
| 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; |
| |
| /// \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) {} |
| }; |
| |
| /// Represents an undefined index in the suffix tree. |
| const unsigned EmptyIdx = -1; |
| |
| /// A node in a suffix tree which represents a substring or suffix. |
| /// |
| /// Each node has either no children or at least two children, with the root |
| /// being a exception in the empty tree. |
| /// |
| /// Children are represented as a map between unsigned integers and nodes. If |
| /// a node N has a child M on unsigned integer k, then the mapping represented |
| /// by N is a proper prefix of the mapping represented by M. Note that this, |
| /// although similar to a trie is somewhat different: each node stores a full |
| /// substring of the full mapping rather than a single character state. |
| /// |
| /// Each internal node contains a pointer to the internal node representing |
| /// the same string, but with the first character chopped off. This is stored |
| /// in \p Link. Each leaf node stores the start index of its respective |
| /// suffix in \p SuffixIdx. |
| struct SuffixTreeNode { |
| |
| /// The children of this node. |
| /// |
| /// A child existing on an unsigned integer implies that from the mapping |
| /// represented by the current node, there is a way to reach another |
| /// mapping by tacking that character on the end of the current string. |
| DenseMap<unsigned, SuffixTreeNode *> Children; |
| |
| /// A flag set to false if the node has been pruned from the tree. |
| bool IsInTree = true; |
| |
| /// The start index of this node's substring in the main string. |
| unsigned StartIdx = EmptyIdx; |
| |
| /// The end index of this node's substring in the main string. |
| /// |
| /// Every leaf node must have its \p EndIdx incremented at the end of every |
| /// 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. |
| unsigned *EndIdx = nullptr; |
| |
| /// For leaves, the start index of the suffix represented by this node. |
| /// |
| /// For all other nodes, this is ignored. |
| unsigned SuffixIdx = EmptyIdx; |
| |
| /// \brief 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 |
| /// 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 |
| /// 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 |
| /// string, starting with the longest suffix of the prefix, and ending with |
| /// the shortest. Therefore, if we keep pointers between such nodes, we can |
| /// 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). |
| SuffixTreeNode *Link = nullptr; |
| |
| /// The parent of this node. Every node except for the root has a parent. |
| SuffixTreeNode *Parent = nullptr; |
| |
| /// The number of times this node's string appears in the tree. |
| /// |
| /// 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. |
| unsigned OccurrenceCount = 0; |
| |
| /// The length of the string formed by concatenating the edge labels from the |
| /// root to this node. |
| unsigned ConcatLen = 0; |
| |
| /// Returns true if this node is a leaf. |
| bool isLeaf() const { return SuffixIdx != EmptyIdx; } |
| |
| /// Returns true if this node is the root of its owning \p SuffixTree. |
| bool isRoot() const { return StartIdx == EmptyIdx; } |
| |
| /// Return the number of elements in the substring associated with this node. |
| size_t size() const { |
| |
| // Is it the root? If so, it's the empty string so return 0. |
| if (isRoot()) |
| return 0; |
| |
| assert(*EndIdx != EmptyIdx && "EndIdx is undefined!"); |
| |
| // Size = the number of elements in the string. |
| // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1. |
| return *EndIdx - StartIdx + 1; |
| } |
| |
| SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link, |
| SuffixTreeNode *Parent) |
| : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {} |
| |
| SuffixTreeNode() {} |
| }; |
| |
| /// A data structure for fast substring queries. |
| /// |
| /// Suffix trees represent the suffixes of their input strings in their leaves. |
| /// A suffix tree is a type of compressed trie structure where each node |
| /// represents an entire substring rather than a single character. Each leaf |
| /// of the tree is a suffix. |
| /// |
| /// A suffix tree can be seen as a type of state machine where each state is a |
| /// substring of the full string. The tree is structured so that, for a string |
| /// of length N, there are exactly N leaves in the tree. This structure allows |
| /// us to quickly find repeated substrings of the input string. |
| /// |
| /// In this implementation, a "string" is a vector of unsigned integers. |
| /// These integers may result from hashing some data type. A suffix tree can |
| /// contain 1 or many strings, which can then be queried as one large string. |
| /// |
| /// The suffix tree is implemented using Ukkonen's algorithm for linear-time |
| /// suffix tree construction. Ukkonen's algorithm is explained in more detail |
| /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The |
| /// paper is available at |
| /// |
| /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf |
| class SuffixTree { |
| 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; |
| |
| /// The root of the suffix tree. |
| /// |
| /// The root represents the empty string. It is maintained by the |
| /// \p NodeAllocator like every other node in the tree. |
| SuffixTreeNode *Root = nullptr; |
| |
| /// Maintains the end indices of the internal nodes in the tree. |
| /// |
| /// Each internal node is guaranteed to never have its end index change |
| /// during the construction algorithm; however, leaves must be updated at |
| /// every step. Therefore, we need to store leaf end indices by reference |
| /// to avoid updating O(N) leaves at every step of construction. Thus, |
| /// every internal node must be allocated its own end index. |
| BumpPtrAllocator InternalEndIdxAllocator; |
| |
| /// The end index of each leaf in the tree. |
| unsigned LeafEndIdx = -1; |
| |
| /// \brief Helper struct which keeps track of the next insertion point in |
| /// Ukkonen's algorithm. |
| struct ActiveState { |
| /// The next node to insert at. |
| SuffixTreeNode *Node; |
| |
| /// The index of the first character in the substring currently being added. |
| unsigned Idx = EmptyIdx; |
| |
| /// The length of the substring we have to add at the current step. |
| unsigned Len = 0; |
| }; |
| |
| /// \brief The point the next insertion will take place at in the |
| /// construction algorithm. |
| ActiveState Active; |
| |
| /// Allocate a leaf node and add it to the tree. |
| /// |
| /// \param Parent The parent of this node. |
| /// \param StartIdx The start index of this node's associated string. |
| /// \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, unsigned StartIdx, |
| unsigned Edge) { |
| |
| assert(StartIdx <= LeafEndIdx && "String can't start after it ends!"); |
| |
| SuffixTreeNode *N = new (NodeAllocator.Allocate()) |
| SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent); |
| Parent.Children[Edge] = N; |
| |
| return N; |
| } |
| |
| /// Allocate an internal node and add it to the tree. |
| /// |
| /// \param Parent The parent of this node. Only null when allocating the root. |
| /// \param StartIdx The start index of this node's associated string. |
| /// \param EndIdx The end index of this node's associated string. |
| /// \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, 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!"); |
| |
| unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx); |
| SuffixTreeNode *N = new (NodeAllocator.Allocate()) |
| SuffixTreeNode(StartIdx, E, Root, Parent); |
| if (Parent) |
| Parent->Children[Edge] = N; |
| |
| return N; |
| } |
| |
| /// \brief 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. |
| /// |
| /// \param[in] CurrNode The node currently being visited. |
| /// \param CurrIdx The current index of the string being visited. |
| void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) { |
| |
| bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot(); |
| |
| // Store the length of the concatenation of all strings from the root to |
| // this node. |
| if (!CurrNode.isRoot()) { |
| if (CurrNode.ConcatLen == 0) |
| CurrNode.ConcatLen = CurrNode.size(); |
| |
| if (CurrNode.Parent) |
| 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()); |
| } |
| |
| // Is this node a leaf? |
| if (IsLeaf) { |
| // If yes, give it a suffix index and bump its parent's occurrence count. |
| CurrNode.SuffixIdx = Str.size() - CurrIdx; |
| assert(CurrNode.Parent && "CurrNode had no parent!"); |
| CurrNode.Parent->OccurrenceCount++; |
| |
| // Store the leaf in the leaf vector for pruning later. |
| LeafVector[CurrNode.SuffixIdx] = &CurrNode; |
| } |
| } |
| |
| /// \brief 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 |
| /// step, the constructed suffix tree is either a valid suffix tree, or a |
| /// suffix tree with implicit suffixes. At the end of the final step, the |
| /// suffix tree is a valid tree. |
| /// |
| /// \param EndIdx The end index of the current prefix in the main string. |
| /// \param SuffixesToAdd The number of suffixes that must be added |
| /// to complete the suffix tree at the current phase. |
| /// |
| /// \returns The number of suffixes that have not been added at the end of |
| /// this step. |
| 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. |
| Active.Idx = EndIdx; |
| } |
| |
| assert(Active.Idx <= EndIdx && "Start index can't be after end index!"); |
| |
| // The first character in the current substring we're looking at. |
| unsigned FirstChar = Str[Active.Idx]; |
| |
| // Have we inserted anything starting with FirstChar at the current node? |
| if (Active.Node->Children.count(FirstChar) == 0) { |
| // If not, then we can just insert a leaf and move too the next step. |
| insertLeaf(*Active.Node, EndIdx, FirstChar); |
| |
| // The active node is an internal node, and we visited it, so it must |
| // need a link if it doesn't have one. |
| if (NeedsLink) { |
| NeedsLink->Link = Active.Node; |
| NeedsLink = nullptr; |
| } |
| } else { |
| // There's a match with FirstChar, so look for the point in the tree to |
| // insert a new node. |
| SuffixTreeNode *NextNode = Active.Node->Children[FirstChar]; |
| |
| 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? |
| if (Active.Len >= SubstringLen) { |
| // If yes, then consume the characters we've seen and move to the next |
| // node. |
| Active.Idx += SubstringLen; |
| Active.Len -= SubstringLen; |
| Active.Node = NextNode; |
| continue; |
| } |
| |
| // Otherwise, the suffix we're trying to insert must be contained in the |
| // next node we want to move to. |
| unsigned LastChar = Str[EndIdx]; |
| |
| // Is the string we're trying to insert a substring of the next node? |
| if (Str[NextNode->StartIdx + Active.Len] == LastChar) { |
| // If yes, then we're done for this step. Remember our insertion point |
| // and move to the next end index. At this point, we have an implicit |
| // suffix tree. |
| if (NeedsLink && !Active.Node->isRoot()) { |
| NeedsLink->Link = Active.Node; |
| NeedsLink = nullptr; |
| } |
| |
| Active.Len++; |
| break; |
| } |
| |
| // The string we're trying to insert isn't a substring of the next node, |
| // but matches up to a point. Split the node. |
| // |
| // For example, say we ended our search at a node n and we're trying to |
| // insert ABD. Then we'll create a new node s for AB, reduce n to just |
| // representing C, and insert a new leaf node l to represent d. This |
| // allows us to ensure that if n was a leaf, it remains a leaf. |
| // |
| // | ABC ---split---> | AB |
| // n s |
| // C / \ D |
| // n l |
| |
| // The node s from the diagram |
| SuffixTreeNode *SplitNode = |
| 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. |
| insertLeaf(*SplitNode, EndIdx, LastChar); |
| |
| // Make the old node a child of the split node and update its start |
| // index. This is the node n from the diagram. |
| NextNode->StartIdx += Active.Len; |
| NextNode->Parent = SplitNode; |
| SplitNode->Children[Str[NextNode->StartIdx]] = NextNode; |
| |
| // SplitNode is an internal node, update the suffix link. |
| if (NeedsLink) |
| NeedsLink->Link = SplitNode; |
| |
| NeedsLink = SplitNode; |
| } |
| |
| // We've added something new to the tree, so there's one less suffix to |
| // add. |
| SuffixesToAdd--; |
| |
| if (Active.Node->isRoot()) { |
| if (Active.Len > 0) { |
| Active.Len--; |
| Active.Idx = EndIdx - SuffixesToAdd + 1; |
| } |
| } else { |
| // Start the next phase at the next smallest suffix. |
| Active.Node = Active.Node->Link; |
| } |
| } |
| |
| return SuffixesToAdd; |
| } |
| |
| public: |
| /// Construct a suffix tree from a sequence of unsigned integers. |
| /// |
| /// \param Str The string to construct the suffix tree for. |
| SuffixTree(const std::vector<unsigned> &Str) : Str(Str) { |
| Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0); |
| Root->IsInTree = true; |
| Active.Node = Root; |
| LeafVector = std::vector<SuffixTreeNode *>(Str.size()); |
| |
| // Keep track of the number of suffixes we have to add of the current |
| // prefix. |
| 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 (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; |
| PfxEndIdx++) { |
| SuffixesToAdd++; |
| LeafEndIdx = PfxEndIdx; // Extend each of the leaves. |
| SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd); |
| } |
| |
| // Set the suffix indices of each leaf. |
| assert(Root && "Root node can't be nullptr!"); |
| setSuffixIndices(*Root, 0); |
| } |
| }; |
| |
| /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings. |
| struct InstructionMapper { |
| |
| /// \brief 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 |
| /// be outlined. |
| unsigned LegalInstrNumber = 0; |
| |
| /// Correspondence from \p MachineInstrs to unsigned integers. |
| DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait> |
| InstructionIntegerMap; |
| |
| /// Corresponcence from unsigned integers to \p MachineInstrs. |
| /// Inverse of \p InstructionIntegerMap. |
| DenseMap<unsigned, MachineInstr *> IntegerInstructionMap; |
| |
| /// 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 |
| /// at index i in \p UnsignedVec for each index i. |
| std::vector<MachineBasicBlock::iterator> InstrList; |
| |
| /// \brief Maps \p *It to a legal integer. |
| /// |
| /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap, |
| /// \p IntegerInstructionMap, and \p LegalInstrNumber. |
| /// |
| /// \returns The integer that \p *It was mapped to. |
| unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) { |
| |
| // Get the integer for this instruction or give it the current |
| // LegalInstrNumber. |
| InstrList.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++; |
| IntegerInstructionMap.insert(std::make_pair(MINumber, &MI)); |
| } |
| |
| UnsignedVec.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."); |
| |
| return MINumber; |
| } |
| |
| /// Maps \p *It to an illegal integer. |
| /// |
| /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber. |
| /// |
| /// \returns The integer that \p *It was mapped to. |
| unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) { |
| unsigned MINumber = IllegalInstrNumber; |
| |
| InstrList.push_back(It); |
| UnsignedVec.push_back(IllegalInstrNumber); |
| IllegalInstrNumber--; |
| |
| 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; |
| } |
| |
| /// \brief 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 TRI \p TargetRegisterInfo for the module. |
| /// \param TII \p TargetInstrInfo for the module. |
| void convertToUnsignedVec(MachineBasicBlock &MBB, |
| const TargetRegisterInfo &TRI, |
| const TargetInstrInfo &TII) { |
| 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: |
| mapToIllegalUnsigned(It); |
| break; |
| |
| case TargetInstrInfo::MachineOutlinerInstrType::Legal: |
| mapToLegalUnsigned(It); |
| break; |
| |
| case TargetInstrInfo::MachineOutlinerInstrType::Invisible: |
| break; |
| } |
| } |
| |
| // 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. |
| InstrList.push_back(MBB.end()); |
| UnsignedVec.push_back(IllegalInstrNumber); |
| IllegalInstrNumber--; |
| } |
| |
| 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!"); |
| } |
| }; |
| |
| /// \brief 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; |
| |
| /// \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 { |
| AU.addRequired<MachineModuleInfo>(); |
| AU.addPreserved<MachineModuleInfo>(); |
| AU.setPreservesAll(); |
| ModulePass::getAnalysisUsage(AU); |
| } |
| |
| 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. |
| /// |
| /// \param M The module we are outlining from. |
| /// \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<std::shared_ptr<Candidate>> &CandidateList, |
| std::vector<OutlinedFunction> &FunctionList, |
| InstructionMapper &Mapper); |
| |
| /// Creates a function for \p OF and inserts it into the module. |
| MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF, |
| InstructionMapper &Mapper); |
| |
| /// Find potential outlining candidates and store them in \p CandidateList. |
| /// |
| /// For each type of potential candidate, also build an \p OutlinedFunction |
| /// struct containing the information to build the function for that |
| /// candidate. |
| /// |
| /// \param[out] CandidateList Filled with outlining candidates for the module. |
| /// \param[out] FunctionList Filled with functions corresponding to each type |
| /// of \p Candidate. |
| /// \param ST The suffix tree for the module. |
| /// \param TII TargetInstrInfo for the module. |
| /// |
| /// \returns The length of the longest candidate found. 0 if there are none. |
| 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. |
| /// |
| /// Pruning from the suffix tree doesn't necessarily remove all overlaps. |
| /// If a short candidate is chosen for outlining, then a longer candidate |
| /// which has that short candidate as a suffix is chosen, the tree's pruning |
| /// method will not find it. Thus, we need to prune before outlining as well. |
| /// |
| /// \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<std::shared_ptr<Candidate>> &CandidateList, |
| std::vector<OutlinedFunction> &FunctionList, |
| InstructionMapper &Mapper, unsigned MaxCandidateLen, |
| const TargetInstrInfo &TII); |
| |
| /// Construct a suffix tree on the instructions in \p M and outline repeated |
| /// strings from that tree. |
| bool runOnModule(Module &M) override; |
| }; |
| |
| } // Anonymous namespace. |
| |
| char MachineOutliner::ID = 0; |
| |
| namespace llvm { |
| 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()) { |
| // Each sequence is over [StartIt, EndIt]. |
| MachineBasicBlock::iterator StartIt = Mapper.InstrList[M->SuffixIdx]; |
| MachineBasicBlock::iterator EndIt = |
| Mapper.InstrList[M->SuffixIdx + StringLen - 1]; |
| |
| CandidatesForRepeatedSeq.emplace_back(M->SuffixIdx, StringLen, |
| FunctionList.size()); |
| RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt)); |
| |
| // Never visit this leaf again. |
| M->IsInTree = false; |
| } |
| } |
| |
| // 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(), Parent.OccurrenceCount, 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";); |
| } |
| |
| 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; |
| }; |
| |
| // 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? |
| // Check for overlaps in the range. |
| // This is O(MaxCandidateLen * CandidateList.size()). |
| for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et; |
| It++) { |
| Candidate &C1 = **It; |
| |
| // If C1 was already pruned, or its function is no longer beneficial for |
| // outlining, move to the next candidate. |
| if (ShouldSkipCandidate(C1)) |
| 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.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; |
| |
| // Is this candidate too far away to overlap? |
| if (C2.getStartIdx() < FarthestPossibleIdx) |
| break; |
| |
| // If C2 was already pruned, or its function is no longer beneficial for |
| // outlining, move to the next candidate. |
| if (ShouldSkipCandidate(C2)) |
| continue; |
| |
| // Do C1 and C2 overlap? |
| // |
| // Not overlapping: |
| // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices |
| // |
| // 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 (C2.getEndIdx() < C1.getStartIdx()) |
| continue; |
| |
| // C1 and C2 overlap. |
| // We need to choose the better of the two. |
| // |
| // Approximate this by picking the one which would have saved us the |
| // most instructions before any pruning. |
| |
| // 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<std::shared_ptr<Candidate>> &CandidateList, |
| std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST, |
| InstructionMapper &Mapper, const TargetInstrInfo &TII) { |
| |
| std::vector<unsigned> CandidateSequence; // Current outlining candidate. |
| unsigned MaxCandidateLen = 0; // Length of the longest candidate. |
| |
| 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(), |
| [](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) { |
| |
| // 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; |
| |
| // Create the function using an IR-level function. |
| LLVMContext &C = M.getContext(); |
| Function *F = dyn_cast<Function>( |
| M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C))); |
| assert(F && "Function was null!"); |
| |
| // 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->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); |
| |
| BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F); |
| IRBuilder<> Builder(EntryBB); |
| Builder.CreateRetVoid(); |
| |
| MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>(); |
| MachineFunction &MF = MMI.getOrCreateMachineFunction(*F); |
| MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock(); |
| const TargetSubtargetInfo &STI = MF.getSubtarget(); |
| const TargetInstrInfo &TII = *STI.getInstrInfo(); |
| |
| // 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) { |
| MachineInstr *NewMI = |
| MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second); |
| 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); |
| |
| return &MF; |
| } |
| |
| 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 std::shared_ptr<Candidate> &Cptr : CandidateList) { |
| Candidate &C = *Cptr; |
| // Was the candidate removed during pruneOverlaps? |
| if (!C.InCandidateList) |
| continue; |
| |
| // If not, then look at its OutlinedFunction. |
| OutlinedFunction &OF = FunctionList[C.FunctionIdx]; |
| |
| // Was its OutlinedFunction made unbeneficial during pruneOverlaps? |
| 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); |
| FunctionsCreated++; |
| } |
| |
| MachineFunction *MF = OF.MF; |
| 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); |
| |
| OutlinedSomething = true; |
| |
| // Statistics. |
| NumOutlined++; |
| } |
| |
| DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); |
| |
| return OutlinedSomething; |
| } |
| |
| bool MachineOutliner::runOnModule(Module &M) { |
| |
| // Is there anything in the module at all? |
| if (M.empty()) |
| return false; |
| |
| MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>(); |
| const TargetSubtargetInfo &STI = |
| MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget(); |
| const TargetRegisterInfo *TRI = STI.getRegisterInfo(); |
| const TargetInstrInfo *TII = STI.getInstrInfo(); |
| |
| InstructionMapper Mapper; |
| |
| // Build instruction mappings for each function in the module. |
| for (Function &F : M) { |
| MachineFunction &MF = MMI.getOrCreateMachineFunction(F); |
| |
| // Is the function empty? Safe to outline from? |
| if (F.empty() || |
| !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs)) |
| continue; |
| |
| // If it is, look at each MachineBasicBlock in the function. |
| for (MachineBasicBlock &MBB : MF) { |
| |
| // Is there anything in MBB? |
| if (MBB.empty()) |
| continue; |
| |
| // If yes, map it. |
| Mapper.convertToUnsignedVec(MBB, *TRI, *TII); |
| } |
| } |
| |
| // Construct a suffix tree, use it to find candidates, and then outline them. |
| SuffixTree ST(Mapper.UnsignedVec); |
| std::vector<std::shared_ptr<Candidate>> CandidateList; |
| std::vector<OutlinedFunction> FunctionList; |
| |
| // Find all of the outlining candidates. |
| unsigned MaxCandidateLen = |
| buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII); |
| |
| // Remove candidates that overlap with other candidates. |
| pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII); |
| |
| // Outline each of the candidates and return true if something was outlined. |
| return outline(M, CandidateList, FunctionList, Mapper); |
| } |