Index: llvm/trunk/include/llvm/CodeGen/Passes.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/Passes.h +++ llvm/trunk/include/llvm/CodeGen/Passes.h @@ -402,6 +402,10 @@ /// This pass frees the memory occupied by the MachineFunction. FunctionPass *createFreeMachineFunctionPass(); + + /// This pass performs outlining on machine instructions directly before + /// printing assembly. + ModulePass *createMachineOutlinerPass(); } // End llvm namespace /// Target machine pass initializer for passes with dependencies. Use with Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -236,6 +236,7 @@ void initializeMachineLoopInfoPass(PassRegistry&); void initializeMachineModuleInfoPass(PassRegistry&); void initializeMachineOptimizationRemarkEmitterPassPass(PassRegistry&); +void initializeMachineOutlinerPass(PassRegistry&); void initializeMachinePipelinerPass(PassRegistry&); void initializeMachinePostDominatorTreePass(PassRegistry&); void initializeMachineRegionInfoPassPass(PassRegistry&); Index: llvm/trunk/include/llvm/Target/TargetInstrInfo.h =================================================================== --- llvm/trunk/include/llvm/Target/TargetInstrInfo.h +++ llvm/trunk/include/llvm/Target/TargetInstrInfo.h @@ -1508,6 +1508,63 @@ return false; } + /// \brief Return how many instructions would be saved by outlining a + /// sequence containing \p SequenceSize instructions that appears + /// \p Occurrences times in a module. + virtual unsigned getOutliningBenefit(size_t SequenceSize, size_t Occurrences) + const { + llvm_unreachable( + "Target didn't implement TargetInstrInfo::getOutliningBenefit!"); + } + + /// Represents how an instruction should be mapped by the outliner. + /// \p Legal instructions are those which are safe to outline. + /// \p Illegal instructions are those which cannot be outlined. + /// \p Invisible instructions are instructions which can be outlined, but + /// shouldn't actually impact the outlining result. + enum MachineOutlinerInstrType {Legal, Illegal, Invisible}; + + /// Return true if the instruction is legal to outline. + virtual MachineOutlinerInstrType getOutliningType(MachineInstr &MI) const { + llvm_unreachable( + "Target didn't implement TargetInstrInfo::getOutliningType!"); + } + + /// Insert a custom epilogue for outlined functions. + /// This may be empty, in which case no epilogue or return statement will be + /// emitted. + virtual void insertOutlinerEpilogue(MachineBasicBlock &MBB, + MachineFunction &MF) const { + llvm_unreachable( + "Target didn't implement TargetInstrInfo::insertOutlinerEpilogue!"); + } + + /// Insert a call to an outlined function into the program. + /// Returns an iterator to the spot where we inserted the call. This must be + /// implemented by the target. + virtual MachineBasicBlock::iterator + insertOutlinedCall(Module &M, MachineBasicBlock &MBB, + MachineBasicBlock::iterator &It, MachineFunction &MF) + const { + llvm_unreachable( + "Target didn't implement TargetInstrInfo::insertOutlinedCall!"); + } + + /// Insert a custom prologue for outlined functions. + /// This may be empty, in which case no prologue will be emitted. + virtual void insertOutlinerPrologue(MachineBasicBlock &MBB, + MachineFunction &MF) const { + llvm_unreachable( + "Target didn't implement TargetInstrInfo::insertOutlinerPrologue!"); + } + + /// Return true if the function can safely be outlined from. + /// By default, this means that the function has no red zone. + virtual bool isFunctionSafeToOutlineFrom(MachineFunction &F) const { + llvm_unreachable("Target didn't implement " + "TargetInstrInfo::isFunctionSafeToOutlineFrom!"); + } + private: unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode; unsigned CatchRetOpcode; Index: llvm/trunk/lib/CodeGen/CMakeLists.txt =================================================================== --- llvm/trunk/lib/CodeGen/CMakeLists.txt +++ llvm/trunk/lib/CodeGen/CMakeLists.txt @@ -74,6 +74,7 @@ MachineModuleInfo.cpp MachineModuleInfoImpls.cpp MachineOptimizationRemarkEmitter.cpp + MachineOutliner.cpp MachinePassRegistry.cpp MachinePipeliner.cpp MachinePostDominators.cpp Index: llvm/trunk/lib/CodeGen/CodeGen.cpp =================================================================== --- llvm/trunk/lib/CodeGen/CodeGen.cpp +++ llvm/trunk/lib/CodeGen/CodeGen.cpp @@ -57,6 +57,7 @@ initializeMachineLoopInfoPass(Registry); initializeMachineModuleInfoPass(Registry); initializeMachineOptimizationRemarkEmitterPassPass(Registry); + initializeMachineOutlinerPass(Registry); initializeMachinePipelinerPass(Registry); initializeMachinePostDominatorTreePass(Registry); initializeMachineRegionInfoPassPass(Registry); Index: llvm/trunk/lib/CodeGen/MachineOutliner.cpp =================================================================== --- llvm/trunk/lib/CodeGen/MachineOutliner.cpp +++ llvm/trunk/lib/CodeGen/MachineOutliner.cpp @@ -0,0 +1,1399 @@ +//===---- 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. +/// +/// 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/Passes.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 +#include +#include +#include +#include + +#define DEBUG_TYPE "machine-outliner" + +using namespace llvm; + +STATISTIC(NumOutlined, "Number of candidates outlined"); +STATISTIC(FunctionsCreated, "Number of functions created"); + +namespace { + +/// Represents an undefined index in the suffix tree. +const size_t 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 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. + size_t 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. + size_t *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; + + /// \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 + /// 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). + /// + /// 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. + 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. + size_t OccurrenceCount = 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(size_t StartIdx, size_t *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 { +private: + /// Each element is an integer representing an instruction in the module. + ArrayRef Str; + + /// Maintains each node in the tree. + BumpPtrAllocator 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; + + /// Stores each leaf in the tree for better pruning. + std::vector LeafVector; + + /// 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. + size_t 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. + size_t Idx = EmptyIdx; + + /// The length of the substring we have to add at the current step. + size_t 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, size_t StartIdx, + unsigned Edge) { + + assert(StartIdx <= LeafEndIdx && "String can't start after it ends!"); + + SuffixTreeNode *N = new (NodeAllocator) 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, size_t StartIdx, + size_t EndIdx, unsigned Edge) { + + assert(StartIdx <= EndIdx && "String can't start after it ends!"); + assert(!(!Parent && StartIdx != EmptyIdx) && + "Non-root internal nodes must have parents!"); + + size_t *E = new (InternalEndIdxAllocator) size_t(EndIdx); + SuffixTreeNode *N = new (NodeAllocator) 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, size_t CurrIdx) { + + bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot(); + + // 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(size_t EndIdx, size_t 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]; + + size_t 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; + } + + /// \brief Return the start index and length of a string which maximizes a + /// benefit function by traversing the tree depth-first. + /// + /// Helper function for \p bestRepeatedSubstring. + /// + /// \param CurrNode The node currently being visited. + /// \param CurrLen Length of the current string. + /// \param[out] BestLen Length of the most beneficial substring. + /// \param[out] MaxBenefit Benefit of the most beneficial substring. + /// \param[out] BestStartIdx Start index of the most beneficial substring. + /// \param BenefitFn The function the query should return a maximum string + /// for. + void findBest(SuffixTreeNode &CurrNode, size_t CurrLen, size_t &BestLen, + size_t &MaxBenefit, size_t &BestStartIdx, + const std::function + &BenefitFn) { + + if (!CurrNode.IsInTree) + return; + + // Can we traverse further down the tree? + if (!CurrNode.isLeaf()) { + // If yes, continue the traversal. + for (auto &ChildPair : CurrNode.Children) { + if (ChildPair.second && ChildPair.second->IsInTree) + findBest(*ChildPair.second, CurrLen + ChildPair.second->size(), + BestLen, MaxBenefit, BestStartIdx, BenefitFn); + } + } else { + // We hit a leaf. + size_t StringLen = CurrLen - CurrNode.size(); + unsigned Benefit = BenefitFn(CurrNode, StringLen); + + // Did we do better than in the last step? + if (Benefit <= MaxBenefit) + return; + + // We did better, so update the best string. + MaxBenefit = Benefit; + BestStartIdx = CurrNode.SuffixIdx; + BestLen = StringLen; + } + } + +public: + + /// \brief Return a substring of the tree with maximum benefit if such a + /// substring exists. + /// + /// Clears the input vector and fills it with a maximum substring or empty. + /// + /// \param[in,out] Best The most beneficial substring in the tree. Empty + /// if it does not exist. + /// \param BenefitFn The function the query should return a maximum string + /// for. + void bestRepeatedSubstring(std::vector &Best, + const std::function + &BenefitFn) { + Best.clear(); + size_t Length = 0; // Becomes the length of the best substring. + size_t Benefit = 0; // Becomes the benefit of the best substring. + size_t StartIdx = 0; // Becomes the start index of the best substring. + findBest(*Root, 0, Length, Benefit, StartIdx, BenefitFn); + + for (size_t Idx = 0; Idx < Length; Idx++) + Best.push_back(Str[Idx + StartIdx]); + } + + /// Perform a depth-first search for \p QueryString on the suffix tree. + /// + /// \param QueryString The string to search for. + /// \param CurrIdx The current index in \p QueryString that is being matched + /// against. + /// \param CurrNode The suffix tree node being searched in. + /// + /// \returns A \p SuffixTreeNode that \p QueryString appears in if such a + /// node exists, and \p nullptr otherwise. + SuffixTreeNode *findString(const std::vector &QueryString, + size_t &CurrIdx, SuffixTreeNode *CurrNode) { + + // The search ended at a nonexistent or pruned node. Quit. + if (!CurrNode || !CurrNode->IsInTree) + return nullptr; + + unsigned Edge = QueryString[CurrIdx]; // The edge we want to move on. + SuffixTreeNode *NextNode = CurrNode->Children[Edge]; // Next node in query. + + if (CurrNode->isRoot()) { + // If we're at the root we have to check if there's a child, and move to + // that child. Don't consume the character since \p Root represents the + // empty string. + if (NextNode && NextNode->IsInTree) + return findString(QueryString, CurrIdx, NextNode); + return nullptr; + } + + size_t StrIdx = CurrNode->StartIdx; + size_t MaxIdx = QueryString.size(); + bool ContinueSearching = false; + + // Match as far as possible into the string. If there's a mismatch, quit. + for (; CurrIdx < MaxIdx; CurrIdx++, StrIdx++) { + Edge = QueryString[CurrIdx]; + + // We matched perfectly, but still have a remainder to search. + if (StrIdx > *(CurrNode->EndIdx)) { + ContinueSearching = true; + break; + } + + if (Edge != Str[StrIdx]) + return nullptr; + } + + NextNode = CurrNode->Children[Edge]; + + // Move to the node which matches what we're looking for and continue + // searching. + if (ContinueSearching) + return findString(QueryString, CurrIdx, NextNode); + + // We matched perfectly so we're done. + return CurrNode; + } + + /// \brief Remove a node from a tree and all nodes representing proper + /// suffixes of that node's string. + /// + /// This is used in the outlining algorithm to reduce the number of + /// overlapping candidates + /// + /// \param N The suffix tree node to start pruning from. + /// \param Len The length of the string to be pruned. + /// + /// \returns True if this candidate didn't overlap with a previously chosen + /// candidate. + bool prune(SuffixTreeNode *N, size_t Len) { + + bool NoOverlap = true; + std::vector IndicesToPrune; + + // Look at each of N's children. + for (auto &ChildPair : N->Children) { + SuffixTreeNode *M = ChildPair.second; + + // Is this a leaf child? + if (M && M->IsInTree && M->isLeaf()) { + // Save each leaf child's suffix indices and remove them from the tree. + IndicesToPrune.push_back(M->SuffixIdx); + M->IsInTree = false; + } + } + + // Remove each suffix we have to prune from the tree. Each of these will be + // I + some offset for I in IndicesToPrune and some offset < Len. + unsigned Offset = 1; + for (unsigned CurrentSuffix = 1; CurrentSuffix < Len; CurrentSuffix++) { + for (unsigned I : IndicesToPrune) { + + unsigned PruneIdx = I + Offset; + + // Is this index actually in the string? + if (PruneIdx < LeafVector.size()) { + // If yes, we have to try and prune it. + // Was the current leaf already pruned by another candidate? + if (LeafVector[PruneIdx]->IsInTree) { + // If not, prune it. + LeafVector[PruneIdx]->IsInTree = false; + } else { + // If yes, signify that we've found an overlap, but keep pruning. + NoOverlap = false; + } + + // Update the parent of the current leaf's occurrence count. + SuffixTreeNode *Parent = LeafVector[PruneIdx]->Parent; + + // Is the parent still in the tree? + if (Parent->OccurrenceCount > 0) { + Parent->OccurrenceCount--; + Parent->IsInTree = (Parent->OccurrenceCount > 1); + } + } + } + + // Move to the next character in the string. + Offset++; + } + + // We know we can never outline anything which starts one index back from + // the indices we want to outline. This is because our minimum outlining + // length is always 2. + for (unsigned I : IndicesToPrune) { + if (I > 0) { + + unsigned PruneIdx = I-1; + SuffixTreeNode *Parent = LeafVector[PruneIdx]->Parent; + + // Was the leaf one index back from I already pruned? + if (LeafVector[PruneIdx]->IsInTree) { + // If not, prune it. + LeafVector[PruneIdx]->IsInTree = false; + } else { + // If yes, signify that we've found an overlap, but keep pruning. + NoOverlap = false; + } + + // Update the parent of the current leaf's occurrence count. + if (Parent->OccurrenceCount > 0) { + Parent->OccurrenceCount--; + Parent->IsInTree = (Parent->OccurrenceCount > 1); + } + } + } + + // Finally, remove N from the tree and set its occurrence count to 0. + N->IsInTree = false; + N->OccurrenceCount = 0; + + return NoOverlap; + } + + /// \brief Find each occurrence of of a string in \p QueryString and prune + /// their nodes. + /// + /// \param QueryString The string to search for. + /// \param[out] Occurrences The start indices of each occurrence. + /// + /// \returns Whether or not the occurrence overlaps with a previous candidate. + bool findOccurrencesAndPrune(const std::vector &QueryString, + std::vector &Occurrences) { + size_t Dummy = 0; + SuffixTreeNode *N = findString(QueryString, Dummy, Root); + + if (!N || !N->IsInTree) + return false; + + // If this is an internal node, occurrences are the number of leaf children + // of the node. + for (auto &ChildPair : N->Children) { + SuffixTreeNode *M = ChildPair.second; + + // Is it a leaf? If so, we have an occurrence. + if (M && M->IsInTree && M->isLeaf()) + Occurrences.push_back(M->SuffixIdx); + } + + // If we're in a leaf, then this node is the only occurrence. + if (N->isLeaf()) + Occurrences.push_back(N->SuffixIdx); + + return prune(N, QueryString.size()); + } + + /// Construct a suffix tree from a sequence of unsigned integers. + /// + /// \param Str The string to construct the suffix tree for. + SuffixTree(const std::vector &Str) : Str(Str) { + Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0); + Root->IsInTree = true; + Active.Node = Root; + LeafVector.reserve(Str.size()); + + // Keep track of the number of suffixes we have to add of the current + // prefix. + size_t 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++) { + 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 An individual sequence of instructions to be replaced with a call to +/// an outlined function. +struct Candidate { + + /// Set to false if the candidate overlapped with another candidate. + bool InCandidateList = true; + + /// The start index of this \p Candidate. + size_t StartIdx; + + /// The number of instructions in this \p Candidate. + size_t Len; + + /// The index of this \p Candidate's \p OutlinedFunction in the list of + /// \p OutlinedFunctions. + size_t FunctionIdx; + + Candidate(size_t StartIdx, size_t Len, size_t 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; } +}; + +/// \brief The information necessary to create an outlined function for some +/// class of candidate. +struct OutlinedFunction { + + /// 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 times that this function has appeared. + size_t OccurrenceCount = 0; + + /// \brief The sequence of integers corresponding to the instructions in this + /// function. + std::vector Sequence; + + /// The number of instructions this function would save. + unsigned Benefit = 0; + + OutlinedFunction(size_t Name, size_t OccurrenceCount, + const std::vector &Sequence, + unsigned Benefit) + : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence), + Benefit(Benefit) + {} +}; + +/// \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 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 + InstructionIntegerMap; + + /// Corresponcence from unsigned integers to \p MachineInstrs. + /// Inverse of \p InstructionIntegerMap. + DenseMap IntegerInstructionMap; + + /// The vector of unsigned integers that the module is mapped to. + std::vector UnsignedVec; + + /// \brief Stores the location of the instruction associated with the integer + /// at index i in \p UnsignedVec for each index i. + std::vector 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::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::getEmptyKey() + && "Tried to assign DenseMap tombstone or empty key to instruction."); + assert(LegalInstrNumber != DenseMapInfo::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::getEmptyKey() && + "IllegalInstrNumber cannot be DenseMap tombstone or empty key!"); + + assert(IllegalInstrNumber != + DenseMapInfo::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 hasn't + // changed. + assert(DenseMapInfo::getEmptyKey() == (unsigned)-1 && + "DenseMapInfo's empty key isn't -1!"); + assert(DenseMapInfo::getTombstoneKey() == (unsigned)-2 && + "DenseMapInfo'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; + + StringRef getPassName() const override { return "Machine Outliner"; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addPreserved(); + AU.setPreservesAll(); + ModulePass::getAnalysisUsage(AU); + } + + MachineOutliner() : ModulePass(ID) { + initializeMachineOutlinerPass(*PassRegistry::getPassRegistry()); + } + + /// \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 &CandidateList, + std::vector &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 &CandidateList, + std::vector &FunctionList, + SuffixTree &ST, const TargetInstrInfo &TII); + + /// \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 MaxCandidateLen The length of the longest candidate. + /// \param TII TargetInstrInfo for the module. + void pruneOverlaps(std::vector &CandidateList, + std::vector &FunctionList, + 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() { return new MachineOutliner(); } +} + +INITIALIZE_PASS(MachineOutliner, "machine-outliner", + "Machine Function Outliner", false, false) + +void MachineOutliner::pruneOverlaps(std::vector &CandidateList, + std::vector &FunctionList, + unsigned MaxCandidateLen, + const TargetInstrInfo &TII) { + + // Check for overlaps in the range. This is O(n^2) worst case, but we can + // alleviate that somewhat by bounding our search space using the start + // index of our first candidate and the maximum distance an overlapping + // candidate could have from the first candidate. + for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et; + It++) { + Candidate &C1 = *It; + OutlinedFunction &F1 = FunctionList[C1.FunctionIdx]; + + // If we removed this candidate, skip it. + if (!C1.InCandidateList) + continue; + + // If the candidate's function isn't good to outline anymore, then + // remove the candidate and skip it. + if (F1.OccurrenceCount < 2 || F1.Benefit < 1) { + 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; + + // Compare against the other candidates in the list. + // This is at most MaxCandidateLen/2 other candidates. + // This is because each candidate has to be at least 2 indices away. + // = O(n * MaxCandidateLen/2) comparisons + // + // On average, the maximum length of a candidate is quite small; a fraction + // of the total module length in terms of instructions. If the maximum + // candidate length is large, then there are fewer possible candidates to + // compare against in the first place. + for (auto Sit = It + 1; Sit != Et; Sit++) { + Candidate &C2 = *Sit; + OutlinedFunction &F2 = FunctionList[C2.FunctionIdx]; + + // Is this candidate too far away to overlap? + // NOTE: This will be true in + // O(max(FarthestPossibleIdx/2, #Candidates remaining)) steps + // for every candidate. + if (C2.StartIdx < 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. + C2.InCandidateList = false; + continue; + } + + size_t C2End = C2.StartIdx + C2.Len - 1; + + // 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 (C2End < C1.StartIdx) + continue; + + // C2 overlaps with C1. Because we pruned the tree already, the only way + // this can happen is if C1 is a proper suffix of C2. Thus, we must have + // found C1 first during our query, so it must have benefit greater or + // equal to C2. Greedily pick C1 as the candidate to keep and toss out C2. + DEBUG ( + size_t C1End = C1.StartIdx + C1.Len - 1; + dbgs() << "- Found an overlap to purge.\n"; + dbgs() << "--- C1 :[" << C1.StartIdx << ", " << C1End << "]\n"; + dbgs() << "--- C2 :[" << C2.StartIdx << ", " << C2End << "]\n"; + ); + + // Update the function's occurrence count and benefit to reflec that C2 + // is being removed. + F2.OccurrenceCount--; + F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(), + F2.OccurrenceCount + ); + + // Mark C2 as not in the list. + C2.InCandidateList = false; + + DEBUG ( + dbgs() << "- Removed C2. \n"; + dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n"; + dbgs() << "--- C2's benefit: " << F2.Benefit << "\n"; + ); + } + } +} + +unsigned +MachineOutliner::buildCandidateList(std::vector &CandidateList, + std::vector &FunctionList, + SuffixTree &ST, + const TargetInstrInfo &TII) { + + std::vector CandidateSequence; // Current outlining candidate. + unsigned 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](const SuffixTreeNode &Curr, size_t StringLen) { + + // Any leaf whose parent is the root only has one occurrence. + if (Curr.Parent->isRoot()) + return 0u; + + // Anything with length < 2 will never be beneficial on any target. + if (StringLen < 2) + return 0u; + + size_t Occurrences = Curr.Parent->OccurrenceCount; + + // Anything with fewer than 2 occurrences will never be beneficial on any + // target. + if (Occurrences < 2) + return 0u; + + return TII.getOutliningBenefit(StringLen, Occurrences); + }; + + // Repeatedly query the suffix tree for the substring that maximizes + // BenefitFn. Find the occurrences of that string, prune the tree, and store + // each occurrence as a candidate. + for (ST.bestRepeatedSubstring(CandidateSequence, BenefitFn); + CandidateSequence.size() > 1; + ST.bestRepeatedSubstring(CandidateSequence, BenefitFn)) { + + std::vector Occurrences; + + bool GotNonOverlappingCandidate = + ST.findOccurrencesAndPrune(CandidateSequence, Occurrences); + + // Is the candidate we found known to overlap with something we already + // outlined? + if (!GotNonOverlappingCandidate) + continue; + + // Is this candidate the longest so far? + if (CandidateSequence.size() > MaxCandidateLen) + MaxCandidateLen = CandidateSequence.size(); + + // Keep track of the benefit of outlining this candidate in its + // OutlinedFunction. + unsigned FnBenefit = TII.getOutliningBenefit(CandidateSequence.size(), + Occurrences.size() + ); + + assert(FnBenefit > 0 && "Function cannot be unbeneficial!"); + + // Save an OutlinedFunction for this candidate. + FunctionList.emplace_back( + FunctionList.size(), // Number of this function. + Occurrences.size(), // Number of occurrences. + CandidateSequence, // Sequence to outline. + FnBenefit // Instructions saved by outlining this function. + ); + + // Save each of the occurrences of the candidate so we can outline them. + for (size_t &Occ : Occurrences) + CandidateList.emplace_back( + Occ, // Starting idx in that MBB. + CandidateSequence.size(), // Candidate length. + FunctionList.size() - 1 // Idx of the corresponding function. + ); + + FunctionsCreated++; + } + + // 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()); + + 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( + M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C), NULL)); + 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(); + MachineFunction &MF = MMI.getMachineFunction(*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); + + // 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); + + return &MF; +} + +bool MachineOutliner::outline(Module &M, + const ArrayRef &CandidateList, + std::vector &FunctionList, + InstructionMapper &Mapper) { + + bool OutlinedSomething = false; + + // Replace the candidates with calls to their respective outlined functions. + for (const Candidate &C : CandidateList) { + + // 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.OccurrenceCount < 2 || OF.Benefit < 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(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); + + 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); + StartIt = Mapper.InstrList[C.StartIdx]; + 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(); + const TargetSubtargetInfo &STI = MMI.getMachineFunction(*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.getMachineFunction(F); + + // Is the function empty? Safe to outline from? + if (F.empty() || !TII->isFunctionSafeToOutlineFrom(MF)) + 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 CandidateList; + std::vector FunctionList; + + unsigned MaxCandidateLen = + buildCandidateList(CandidateList, FunctionList, ST, *TII); + + pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII); + return outline(M, CandidateList, FunctionList, Mapper); +} Index: llvm/trunk/lib/CodeGen/TargetPassConfig.cpp =================================================================== --- llvm/trunk/lib/CodeGen/TargetPassConfig.cpp +++ llvm/trunk/lib/CodeGen/TargetPassConfig.cpp @@ -92,6 +92,9 @@ cl::desc("Verify generated machine code"), cl::init(false), cl::ZeroOrMore); +static cl::opt EnableMachineOutliner("enable-machine-outliner", + cl::Hidden, + cl::desc("Enable machine outliner")); static cl::opt PrintMachineInstrs("print-machineinstrs", cl::ValueOptional, @@ -674,6 +677,9 @@ addPass(&XRayInstrumentationID, false); addPass(&PatchableFunctionID, false); + if (EnableMachineOutliner) + PM->add(createMachineOutlinerPass()); + AddingMachinePasses = false; } Index: llvm/trunk/lib/Target/X86/X86InstrInfo.h =================================================================== --- llvm/trunk/lib/Target/X86/X86InstrInfo.h +++ llvm/trunk/lib/Target/X86/X86InstrInfo.h @@ -545,6 +545,27 @@ bool isTailCall(const MachineInstr &Inst) const override; + unsigned getOutliningBenefit(size_t SequenceSize, + size_t Occurrences) const override; + + bool isFunctionSafeToOutlineFrom(MachineFunction &MF) const override; + + llvm::X86GenInstrInfo::MachineOutlinerInstrType + getOutliningType(MachineInstr &MI) const override; + + bool isFixablePostOutline(MachineInstr &MI) const; + + void insertOutlinerEpilogue(MachineBasicBlock &MBB, + MachineFunction &MF) const override; + + void insertOutlinerPrologue(MachineBasicBlock &MBB, + MachineFunction &MF) const override; + + MachineBasicBlock::iterator + insertOutlinedCall(Module &M, MachineBasicBlock &MBB, + MachineBasicBlock::iterator &It, + MachineFunction &MF) const override; + protected: /// Commutes the operands in the given instruction by changing the operands /// order and/or changing the instruction's opcode and/or the immediate value Index: llvm/trunk/lib/Target/X86/X86InstrInfo.cpp =================================================================== --- llvm/trunk/lib/Target/X86/X86InstrInfo.cpp +++ llvm/trunk/lib/Target/X86/X86InstrInfo.cpp @@ -10383,3 +10383,83 @@ char LDTLSCleanup::ID = 0; FunctionPass* llvm::createCleanupLocalDynamicTLSPass() { return new LDTLSCleanup(); } + +unsigned X86InstrInfo::getOutliningBenefit(size_t SequenceSize, + size_t Occurrences) const { + unsigned NotOutlinedSize = SequenceSize * Occurrences; + + // Sequence appears once in outlined function (Sequence.size()) + // One return instruction (+1) + // One call per occurrence (Occurrences) + unsigned OutlinedSize = (SequenceSize + 1) + Occurrences; + + // Return the number of instructions saved by outlining this sequence. + return NotOutlinedSize > OutlinedSize ? NotOutlinedSize - OutlinedSize : 0; +} + +bool X86InstrInfo::isFunctionSafeToOutlineFrom(MachineFunction &MF) const { + return MF.getFunction()->hasFnAttribute(Attribute::NoRedZone); +} + +X86GenInstrInfo::MachineOutlinerInstrType +X86InstrInfo::getOutliningType(MachineInstr &MI) const { + + // Don't outline returns or basic block terminators. + if (MI.isReturn() || MI.isTerminator()) + return MachineOutlinerInstrType::Illegal; + + // Don't outline anything that modifies or reads from the stack pointer. + // + // FIXME: There are instructions which are being manually built without + // explicit uses/defs so we also have to check the MCInstrDesc. We should be + // able to remove the extra checks once those are fixed up. For example, + // sometimes we might get something like %RAX = POP64r 1. This won't be + // caught by modifiesRegister or readsRegister even though the instruction + // really ought to be formed so that modifiesRegister/readsRegister would + // catch it. + if (MI.modifiesRegister(X86::RSP, &RI) || MI.readsRegister(X86::RSP, &RI) || + MI.getDesc().hasImplicitUseOfPhysReg(X86::RSP) || + MI.getDesc().hasImplicitDefOfPhysReg(X86::RSP)) + return MachineOutlinerInstrType::Illegal; + + if (MI.readsRegister(X86::RIP, &RI) || + MI.getDesc().hasImplicitUseOfPhysReg(X86::RIP) || + MI.getDesc().hasImplicitDefOfPhysReg(X86::RIP)) + return MachineOutlinerInstrType::Illegal; + + if (MI.isPosition()) + return MachineOutlinerInstrType::Illegal; + + for (const MachineOperand &MOP : MI.operands()) + if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() || + MOP.isTargetIndex()) + return MachineOutlinerInstrType::Illegal; + + // Don't allow debug values to impact outlining type. + if (MI.isDebugValue() || MI.isIndirectDebugValue()) + return MachineOutlinerInstrType::Invisible; + + return MachineOutlinerInstrType::Legal; +} + +void X86InstrInfo::insertOutlinerEpilogue(MachineBasicBlock &MBB, + MachineFunction &MF) const { + + MachineInstr *retq = BuildMI(MF, DebugLoc(), get(X86::RETQ)); + MBB.insert(MBB.end(), retq); +} + +void X86InstrInfo::insertOutlinerPrologue(MachineBasicBlock &MBB, + MachineFunction &MF) const { + return; +} + +MachineBasicBlock::iterator +X86InstrInfo::insertOutlinedCall(Module &M, MachineBasicBlock &MBB, + MachineBasicBlock::iterator &It, + MachineFunction &MF) const { + It = MBB.insert(It, + BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32)) + .addGlobalAddress(M.getNamedValue(MF.getName()))); + return It; +} Index: llvm/trunk/test/CodeGen/X86/machine-outliner-debuginfo.ll =================================================================== --- llvm/trunk/test/CodeGen/X86/machine-outliner-debuginfo.ll +++ llvm/trunk/test/CodeGen/X86/machine-outliner-debuginfo.ll @@ -0,0 +1,75 @@ +; RUN: llc -enable-machine-outliner -mtriple=x86_64-apple-darwin < %s | FileCheck %s + +@x = global i32 0, align 4, !dbg !0 + +define i32 @main() #0 !dbg !11 { + ; CHECK-LABEL: _main: + %1 = alloca i32, align 4 + %2 = alloca i32, align 4 + %3 = alloca i32, align 4 + %4 = alloca i32, align 4 + %5 = alloca i32, align 4 + ; There is a debug value in the middle of this section, make sure debug values are ignored. + ; CHECK: callq l_OUTLINED_FUNCTION_0 + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + call void @llvm.dbg.value(metadata i32 10, i64 0, metadata !15, metadata !16), !dbg !17 + store i32 4, i32* %5, align 4 + store i32 0, i32* @x, align 4, !dbg !24 + ; This is the same sequence of instructions without a debug value. It should be outlined + ; in the same way. + ; CHECK: callq l_OUTLINED_FUNCTION_0 + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + store i32 4, i32* %5, align 4 + store i32 1, i32* @x, align 4, !dbg !14 + ret i32 0, !dbg !25 +} + +; CHECK-LABEL: l_OUTLINED_FUNCTION_0: +; CHECK-NOT: .loc {{[0-9]+}} {{[0-9]+}} {{[0-9]+}} {{^(is_stmt)}} +; CHECK-NOT: ##DEBUG_VALUE: main:{{[a-z]}} <- {{[0-9]+}} +; CHECK: movl $1, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $2, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $3, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $4, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: retq + +declare void @llvm.dbg.declare(metadata, metadata, metadata) #1 + +declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #1 + +attributes #0 = { noredzone nounwind ssp uwtable "no-frame-pointer-elim"="true" } + +!llvm.dbg.cu = !{!2} +!llvm.module.flags = !{!7, !8, !9} +!llvm.ident = !{!10} + +!0 = !DIGlobalVariableExpression(var: !1) +!1 = distinct !DIGlobalVariable(name: "x", scope: !2, file: !3, line: 2, type: !6, isLocal: false, isDefinition: true) +!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 5.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5) +!3 = !DIFile(filename: "debug-test.c", directory: "dir") +!4 = !{} +!5 = !{!0} +!6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!7 = !{i32 2, !"Dwarf Version", i32 4} +!8 = !{i32 2, !"Debug Info Version", i32 3} +!9 = !{i32 1, !"PIC Level", i32 2} +!10 = !{!"clang version 5.0.0"} +!11 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 4, type: !12, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: false, unit: !2, variables: !4) +!12 = !DISubroutineType(types: !13) +!13 = !{!6} +!14 = !DILocation(line: 7, column: 4, scope: !11) +!15 = !DILocalVariable(name: "a", scope: !11, file: !3, line: 5, type: !6) +!16 = !DIExpression() +!17 = !DILocation(line: 5, column: 6, scope: !11) +!18 = !DILocalVariable(name: "b", scope: !11, file: !3, line: 5, type: !6) +!19 = !DILocation(line: 5, column: 9, scope: !11) +!20 = !DILocalVariable(name: "c", scope: !11, file: !3, line: 5, type: !6) +!21 = !DILocation(line: 5, column: 12, scope: !11) +!22 = !DILocalVariable(name: "d", scope: !11, file: !3, line: 5, type: !6) +!23 = !DILocation(line: 5, column: 15, scope: !11) +!24 = !DILocation(line: 14, column: 4, scope: !11) +!25 = !DILocation(line: 21, column: 2, scope: !11) Index: llvm/trunk/test/CodeGen/X86/machine-outliner.ll =================================================================== --- llvm/trunk/test/CodeGen/X86/machine-outliner.ll +++ llvm/trunk/test/CodeGen/X86/machine-outliner.ll @@ -0,0 +1,110 @@ +; RUN: llc -enable-machine-outliner -mtriple=x86_64-apple-darwin < %s | FileCheck %s + +@x = global i32 0, align 4 + +define i32 @check_boundaries() #0 { + ; CHECK-LABEL: _check_boundaries: + %1 = alloca i32, align 4 + %2 = alloca i32, align 4 + %3 = alloca i32, align 4 + %4 = alloca i32, align 4 + %5 = alloca i32, align 4 + store i32 0, i32* %1, align 4 + store i32 0, i32* %2, align 4 + %6 = load i32, i32* %2, align 4 + %7 = icmp ne i32 %6, 0 + br i1 %7, label %9, label %8 + + ; CHECK: callq l_OUTLINED_FUNCTION_1 + ; CHECK: cmpl $0, -{{[0-9]+}}(%rbp) + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + store i32 4, i32* %5, align 4 + br label %10 + + store i32 1, i32* %4, align 4 + br label %10 + + %11 = load i32, i32* %2, align 4 + %12 = icmp ne i32 %11, 0 + br i1 %12, label %14, label %13 + + ; CHECK: callq l_OUTLINED_FUNCTION_1 + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + store i32 4, i32* %5, align 4 + br label %15 + + store i32 1, i32* %4, align 4 + br label %15 + + ret i32 0 +} + +define i32 @empty_1() #0 { + ; CHECK-LABEL: _empty_1: + ; CHECK-NOT: callq l_OUTLINED_FUNCTION_{{[0-9]+}} + ret i32 1 +} + +define i32 @empty_2() #0 { + ; CHECK-LABEL: _empty_2 + ; CHECK-NOT: callq l_OUTLINED_FUNCTION_{{[0-9]+}} + ret i32 1 +} + +define i32 @no_empty_outlining() #0 { + ; CHECK-LABEL: _no_empty_outlining: + %1 = alloca i32, align 4 + store i32 0, i32* %1, align 4 + ; CHECK-NOT: callq l_OUTLINED_FUNCTION_{{[0-9]+}} + %2 = call i32 @empty_1() #1 + %3 = call i32 @empty_2() #1 + %4 = call i32 @empty_1() #1 + %5 = call i32 @empty_2() #1 + %6 = call i32 @empty_1() #1 + %7 = call i32 @empty_2() #1 + ret i32 0 +} + +define i32 @main() #0 { + ; CHECK-LABEL: _main: + %1 = alloca i32, align 4 + %2 = alloca i32, align 4 + %3 = alloca i32, align 4 + %4 = alloca i32, align 4 + %5 = alloca i32, align 4 + + store i32 0, i32* %1, align 4 + store i32 0, i32* @x, align 4 + ; CHECK: callq l_OUTLINED_FUNCTION_0 + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + store i32 4, i32* %5, align 4 + store i32 1, i32* @x, align 4 + ; CHECK: callq l_OUTLINED_FUNCTION_0 + store i32 1, i32* %2, align 4 + store i32 2, i32* %3, align 4 + store i32 3, i32* %4, align 4 + store i32 4, i32* %5, align 4 + ret i32 0 +} + +attributes #0 = { noredzone nounwind ssp uwtable "no-frame-pointer-elim"="true" } + +; CHECK-LABEL: l_OUTLINED_FUNCTION_0: +; CHECK: movl $1, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $2, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $3, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $4, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: retq + +; CHECK-LABEL: l_OUTLINED_FUNCTION_1: +; CHECK: movl $1, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $2, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $3, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: movl $4, -{{[0-9]+}}(%rbp) +; CHECK-NEXT: retq