diff options
Diffstat (limited to 'llvm/lib/CodeGen/MachineOutliner.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/MachineOutliner.cpp | 658 |
1 files changed, 121 insertions, 537 deletions
diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp index 3a9104bda0d1a..f9d099e029956 100644 --- a/llvm/lib/CodeGen/MachineOutliner.cpp +++ b/llvm/lib/CodeGen/MachineOutliner.cpp @@ -56,6 +56,7 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/MachineOutliner.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" #include "llvm/CodeGen/MachineFunction.h" @@ -69,9 +70,9 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Mangler.h" #include "llvm/InitializePasses.h" -#include "llvm/Support/Allocator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/SuffixTree.h" #include "llvm/Support/raw_ostream.h" #include <functional> #include <tuple> @@ -96,514 +97,15 @@ static cl::opt<bool> EnableLinkOnceODROutlining( cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false)); -namespace { - -/// 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; - - /// 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; - - /// 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 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) - : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link) {} - - 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: - /// Each element is an integer representing an instruction in the module. - ArrayRef<unsigned> Str; - - /// A repeated substring in the tree. - struct RepeatedSubstring { - /// The length of the string. - unsigned Length; - - /// The start indices of each occurrence. - std::vector<unsigned> StartIndices; - }; - -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; - - /// Helper struct which keeps track of the next insertion point in - /// Ukkonen's algorithm. - struct ActiveState { - /// The next node to insert at. - SuffixTreeNode *Node = nullptr; - - /// 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; - }; - - /// 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.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); - if (Parent) - Parent->Children[Edge] = N; - - return N; - } - - /// Set the suffix indices of the leaves to the start indices of their - /// respective suffixes. - void setSuffixIndices() { - // List of nodes we need to visit along with the current length of the - // string. - std::vector<std::pair<SuffixTreeNode *, unsigned>> ToVisit; - - // Current node being visited. - SuffixTreeNode *CurrNode = Root; - - // Sum of the lengths of the nodes down the path to the current one. - unsigned CurrNodeLen = 0; - ToVisit.push_back({CurrNode, CurrNodeLen}); - while (!ToVisit.empty()) { - std::tie(CurrNode, CurrNodeLen) = ToVisit.back(); - ToVisit.pop_back(); - CurrNode->ConcatLen = CurrNodeLen; - for (auto &ChildPair : CurrNode->Children) { - assert(ChildPair.second && "Node had a null child!"); - ToVisit.push_back( - {ChildPair.second, CurrNodeLen + ChildPair.second->size()}); - } - - // No children, so we are at the end of the string. - if (CurrNode->Children.size() == 0 && !CurrNode->isRoot()) - CurrNode->SuffixIdx = Str.size() - CurrNodeLen; - } - } - - /// 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; - } +/// Number of times to re-run the outliner. This is not the total number of runs +/// as the outliner will run at least one time. The default value is set to 0, +/// meaning the outliner will run one time and rerun zero times after that. +static cl::opt<unsigned> OutlinerReruns( + "machine-outliner-reruns", cl::init(0), cl::Hidden, + cl::desc( + "Number of times to rerun the outliner after the initial outline")); - 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; - 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); - Active.Node = Root; - - // Keep track of the number of suffixes we have to add of the current - // prefix. - unsigned SuffixesToAdd = 0; - - // 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(); - } - - /// Iterator for finding all repeated substrings in the suffix tree. - struct RepeatedSubstringIterator { - private: - /// The current node we're visiting. - SuffixTreeNode *N = nullptr; - - /// The repeated substring associated with this node. - RepeatedSubstring RS; - - /// The nodes left to visit. - std::vector<SuffixTreeNode *> ToVisit; - - /// The minimum length of a repeated substring to find. - /// Since we're outlining, we want at least two instructions in the range. - /// FIXME: This may not be true for targets like X86 which support many - /// instruction lengths. - const unsigned MinLength = 2; - - /// Move the iterator to the next repeated substring. - void advance() { - // Clear the current state. If we're at the end of the range, then this - // is the state we want to be in. - RS = RepeatedSubstring(); - N = nullptr; - - // Each leaf node represents a repeat of a string. - std::vector<SuffixTreeNode *> LeafChildren; - - // Continue visiting nodes until we find one which repeats more than once. - while (!ToVisit.empty()) { - SuffixTreeNode *Curr = ToVisit.back(); - ToVisit.pop_back(); - LeafChildren.clear(); - - // Keep track of the length of the string associated with the node. If - // it's too short, we'll quit. - unsigned Length = Curr->ConcatLen; - - // Iterate over each child, saving internal nodes for visiting, and - // leaf nodes in LeafChildren. Internal nodes represent individual - // strings, which may repeat. - for (auto &ChildPair : Curr->Children) { - // Save all of this node's children for processing. - if (!ChildPair.second->isLeaf()) - ToVisit.push_back(ChildPair.second); - - // It's not an internal node, so it must be a leaf. If we have a - // long enough string, then save the leaf children. - else if (Length >= MinLength) - LeafChildren.push_back(ChildPair.second); - } - - // The root never represents a repeated substring. If we're looking at - // that, then skip it. - if (Curr->isRoot()) - continue; - - // Do we have any repeated substrings? - if (LeafChildren.size() >= 2) { - // Yes. Update the state to reflect this, and then bail out. - N = Curr; - RS.Length = Length; - for (SuffixTreeNode *Leaf : LeafChildren) - RS.StartIndices.push_back(Leaf->SuffixIdx); - break; - } - } - - // At this point, either NewRS is an empty RepeatedSubstring, or it was - // set in the above loop. Similarly, N is either nullptr, or the node - // associated with NewRS. - } - - public: - /// Return the current repeated substring. - RepeatedSubstring &operator*() { return RS; } - - RepeatedSubstringIterator &operator++() { - advance(); - return *this; - } - - RepeatedSubstringIterator operator++(int I) { - RepeatedSubstringIterator It(*this); - advance(); - return It; - } - - bool operator==(const RepeatedSubstringIterator &Other) { - return N == Other.N; - } - bool operator!=(const RepeatedSubstringIterator &Other) { - return !(*this == Other); - } - - RepeatedSubstringIterator(SuffixTreeNode *N) : N(N) { - // Do we have a non-null node? - if (N) { - // Yes. At the first step, we need to visit all of N's children. - // Note: This means that we visit N last. - ToVisit.push_back(N); - advance(); - } - } - }; - - typedef RepeatedSubstringIterator iterator; - iterator begin() { return iterator(Root); } - iterator end() { return iterator(nullptr); } -}; +namespace { /// Maps \p MachineInstrs to unsigned integers and stores the mappings. struct InstructionMapper { @@ -841,6 +343,9 @@ struct MachineOutliner : public ModulePass { /// linkonceodr linkage. bool OutlineFromLinkOnceODRs = false; + /// The current repeat number of machine outlining. + unsigned OutlineRepeatedNum = 0; + /// Set to true if the outliner should run on all functions in the module /// considered safe for outlining. /// Set to true by default for compatibility with llc's -run-pass option. @@ -899,7 +404,7 @@ struct MachineOutliner : public ModulePass { InstructionMapper &Mapper, unsigned Name); - /// Calls 'doOutline()'. + /// Calls 'doOutline()' 1 + OutlinerReruns times. bool runOnModule(Module &M) override; /// Construct a suffix tree on the instructions in \p M and outline repeated @@ -1098,7 +603,10 @@ MachineFunction *MachineOutliner::createOutlinedFunction( // Create the function name. This should be unique. // FIXME: We should have a better naming scheme. This should be stable, // regardless of changes to the outliner's cost model/traversal order. - std::string FunctionName = ("OUTLINED_FUNCTION_" + Twine(Name)).str(); + std::string FunctionName = "OUTLINED_FUNCTION_"; + if (OutlineRepeatedNum > 0) + FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_"; + FunctionName += std::to_string(Name); // Create the function using an IR-level function. LLVMContext &C = M.getContext(); @@ -1110,9 +618,6 @@ MachineFunction *MachineOutliner::createOutlinedFunction( F->setLinkage(GlobalValue::InternalLinkage); F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); - // FIXME: Set nounwind, so we don't generate eh_frame? Haven't verified it's - // necessary. - // Set optsize/minsize, so we don't insert padding between outlined // functions. F->addFnAttr(Attribute::OptimizeForSize); @@ -1127,6 +632,12 @@ MachineFunction *MachineOutliner::createOutlinedFunction( if (ParentFn.hasFnAttribute("target-features")) F->addFnAttr(ParentFn.getFnAttribute("target-features")); + // Set nounwind, so we don't generate eh_frame. + if (llvm::all_of(OF.Candidates, [](const outliner::Candidate &C) { + return C.getMF()->getFunction().hasFnAttribute(Attribute::NoUnwind); + })) + F->addFnAttr(Attribute::NoUnwind); + BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F); IRBuilder<> Builder(EntryBB); Builder.CreateRetVoid(); @@ -1140,9 +651,17 @@ MachineFunction *MachineOutliner::createOutlinedFunction( // Insert the new function into the module. MF.insert(MF.begin(), &MBB); + MachineFunction *OriginalMF = FirstCand.front()->getMF(); + const std::vector<MCCFIInstruction> &Instrs = + OriginalMF->getFrameInstructions(); for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E; ++I) { MachineInstr *NewMI = MF.CloneMachineInstr(&*I); + if (I->isCFIInstruction()) { + unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex(); + MCCFIInstruction CFI = Instrs[CFIIndex]; + (void)MF.addFrameInst(CFI); + } NewMI->dropMemRefs(MF); // Don't keep debug information for outlined instructions. @@ -1150,12 +669,35 @@ MachineFunction *MachineOutliner::createOutlinedFunction( MBB.insert(MBB.end(), NewMI); } - TII.buildOutlinedFrame(MBB, MF, OF); - - // Outlined functions shouldn't preserve liveness. - MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness); + // Set normal properties for a late MachineFunction. + MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA); + MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs); + MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); + MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness); MF.getRegInfo().freezeReservedRegs(MF); + // Compute live-in set for outlined fn + const MachineRegisterInfo &MRI = MF.getRegInfo(); + const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); + LivePhysRegs LiveIns(TRI); + for (auto &Cand : OF.Candidates) { + // Figure out live-ins at the first instruction. + MachineBasicBlock &OutlineBB = *Cand.front()->getParent(); + LivePhysRegs CandLiveIns(TRI); + CandLiveIns.addLiveOuts(OutlineBB); + for (const MachineInstr &MI : + reverse(make_range(Cand.front(), OutlineBB.end()))) + CandLiveIns.stepBackward(MI); + + // The live-in set for the outlined function is the union of the live-ins + // from all the outlining points. + for (MCPhysReg Reg : make_range(CandLiveIns.begin(), CandLiveIns.end())) + LiveIns.addReg(Reg); + } + addLiveIns(MBB, LiveIns); + + TII.buildOutlinedFrame(MBB, MF, OF); + // If there's a DISubprogram associated with this outlined function, then // emit debug info for the outlined function. if (DISubprogram *SP = getSubprogramOrNull(OF)) { @@ -1245,31 +787,54 @@ bool MachineOutliner::outline(Module &M, // make sure that the ranges we yank things out of aren't wrong. if (MBB.getParent()->getProperties().hasProperty( MachineFunctionProperties::Property::TracksLiveness)) { - // Helper lambda for adding implicit def operands to the call + // The following code is to add implicit def operands to the call // instruction. It also updates call site information for moved // code. - auto CopyDefsAndUpdateCalls = [&CallInst](MachineInstr &MI) { - for (MachineOperand &MOP : MI.operands()) { - // Skip over anything that isn't a register. - if (!MOP.isReg()) - continue; - - // If it's a def, add it to the call instruction. - if (MOP.isDef()) - CallInst->addOperand(MachineOperand::CreateReg( - MOP.getReg(), true, /* isDef = true */ - true /* isImp = true */)); - } - if (MI.isCall()) - MI.getMF()->eraseCallSiteInfo(&MI); - }; + SmallSet<Register, 2> UseRegs, DefRegs; // Copy over the defs in the outlined range. // First inst in outlined range <-- Anything that's defined in this // ... .. range has to be added as an // implicit Last inst in outlined range <-- def to the call // instruction. Also remove call site information for outlined block - // of code. - std::for_each(CallInst, std::next(EndIt), CopyDefsAndUpdateCalls); + // of code. The exposed uses need to be copied in the outlined range. + for (MachineBasicBlock::reverse_iterator + Iter = EndIt.getReverse(), + Last = std::next(CallInst.getReverse()); + Iter != Last; Iter++) { + MachineInstr *MI = &*Iter; + for (MachineOperand &MOP : MI->operands()) { + // Skip over anything that isn't a register. + if (!MOP.isReg()) + continue; + + if (MOP.isDef()) { + // Introduce DefRegs set to skip the redundant register. + DefRegs.insert(MOP.getReg()); + if (UseRegs.count(MOP.getReg())) + // Since the regiester is modeled as defined, + // it is not necessary to be put in use register set. + UseRegs.erase(MOP.getReg()); + } else if (!MOP.isUndef()) { + // Any register which is not undefined should + // be put in the use register set. + UseRegs.insert(MOP.getReg()); + } + } + if (MI->isCandidateForCallSiteEntry()) + MI->getMF()->eraseCallSiteInfo(MI); + } + + for (const Register &I : DefRegs) + // If it's a def, add it to the call instruction. + CallInst->addOperand( + MachineOperand::CreateReg(I, true, /* isDef = true */ + true /* isImp = true */)); + + for (const Register &I : UseRegs) + // If it's a exposed use, add it to the call instruction. + CallInst->addOperand( + MachineOperand::CreateReg(I, false, /* isDef = false */ + true /* isImp = true */)); } // Erase from the point after where the call was inserted up to, and @@ -1289,7 +854,6 @@ bool MachineOutliner::outline(Module &M, } LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";); - return OutlinedSomething; } @@ -1377,7 +941,7 @@ void MachineOutliner::emitInstrCountChangedRemark( if (!MF) continue; - std::string Fname = F.getName(); + std::string Fname = std::string(F.getName()); unsigned FnCountAfter = MF->getInstructionCount(); unsigned FnCountBefore = 0; @@ -1424,8 +988,22 @@ bool MachineOutliner::runOnModule(Module &M) { // Number to append to the current outlined function. unsigned OutlinedFunctionNum = 0; + OutlineRepeatedNum = 0; if (!doOutline(M, OutlinedFunctionNum)) return false; + + for (unsigned I = 0; I < OutlinerReruns; ++I) { + OutlinedFunctionNum = 0; + OutlineRepeatedNum++; + if (!doOutline(M, OutlinedFunctionNum)) { + LLVM_DEBUG({ + dbgs() << "Did not outline on iteration " << I + 2 << " out of " + << OutlinerReruns + 1 << "\n"; + }); + break; + } + } + return true; } @@ -1482,5 +1060,11 @@ bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) { if (ShouldEmitSizeRemarks && OutlinedSomething) emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount); + LLVM_DEBUG({ + if (!OutlinedSomething) + dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum + << " because no changes were found.\n"; + }); + return OutlinedSomething; } |