summaryrefslogtreecommitdiff
path: root/lib/CodeGen/MachineOutliner.cpp
diff options
context:
space:
mode:
authorDimitry Andric <dim@FreeBSD.org>2019-01-19 10:01:25 +0000
committerDimitry Andric <dim@FreeBSD.org>2019-01-19 10:01:25 +0000
commitd8e91e46262bc44006913e6796843909f1ac7bcd (patch)
tree7d0c143d9b38190e0fa0180805389da22cd834c5 /lib/CodeGen/MachineOutliner.cpp
parentb7eb8e35e481a74962664b63dfb09483b200209a (diff)
Notes
Diffstat (limited to 'lib/CodeGen/MachineOutliner.cpp')
-rw-r--r--lib/CodeGen/MachineOutliner.cpp1101
1 files changed, 577 insertions, 524 deletions
diff --git a/lib/CodeGen/MachineOutliner.cpp b/lib/CodeGen/MachineOutliner.cpp
index a712afec0959..ad96c0e579e4 100644
--- a/lib/CodeGen/MachineOutliner.cpp
+++ b/lib/CodeGen/MachineOutliner.cpp
@@ -128,9 +128,6 @@ struct SuffixTreeNode {
/// mapping by tacking that character on the end of the current string.
DenseMap<unsigned, SuffixTreeNode *> Children;
- /// A flag set to false if the node has been pruned from the tree.
- bool IsInTree = true;
-
/// The start index of this node's substring in the main string.
unsigned StartIdx = EmptyIdx;
@@ -167,15 +164,6 @@ struct SuffixTreeNode {
/// construction algorithm O(N^2) rather than O(N).
SuffixTreeNode *Link = nullptr;
- /// The parent of this node. Every node except for the root has a parent.
- SuffixTreeNode *Parent = nullptr;
-
- /// The number of times this node's string appears in the tree.
- ///
- /// This is equal to the number of leaf children of the string. It represents
- /// the number of suffixes that the node's string is a prefix of.
- unsigned OccurrenceCount = 0;
-
/// The length of the string formed by concatenating the edge labels from the
/// root to this node.
unsigned ConcatLen = 0;
@@ -200,9 +188,8 @@ struct SuffixTreeNode {
return *EndIdx - StartIdx + 1;
}
- SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
- SuffixTreeNode *Parent)
- : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
+ SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link)
+ : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link) {}
SuffixTreeNode() {}
};
@@ -231,14 +218,18 @@ struct SuffixTreeNode {
/// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
class SuffixTree {
public:
- /// Stores each leaf node in the tree.
- ///
- /// This is used for finding outlining candidates.
- std::vector<SuffixTreeNode *> LeafVector;
-
/// Each element is an integer representing an instruction in the module.
ArrayRef<unsigned> Str;
+ /// 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;
@@ -291,7 +282,7 @@ private:
assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
SuffixTreeNode *N = new (NodeAllocator.Allocate())
- SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
+ SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr);
Parent.Children[Edge] = N;
return N;
@@ -314,7 +305,7 @@ private:
unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
SuffixTreeNode *N = new (NodeAllocator.Allocate())
- SuffixTreeNode(StartIdx, E, Root, Parent);
+ SuffixTreeNode(StartIdx, E, Root);
if (Parent)
Parent->Children[Edge] = N;
@@ -322,41 +313,27 @@ private:
}
/// 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.
+ /// respective suffixes.
///
/// \param[in] CurrNode The node currently being visited.
- /// \param CurrIdx The current index of the string being visited.
- void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
+ /// \param CurrNodeLen The concatenation of all node sizes from the root to
+ /// this node. Used to produce suffix indices.
+ void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrNodeLen) {
bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
- // Store the length of the concatenation of all strings from the root to
- // this node.
- if (!CurrNode.isRoot()) {
- if (CurrNode.ConcatLen == 0)
- CurrNode.ConcatLen = CurrNode.size();
-
- if (CurrNode.Parent)
- CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
- }
-
+ // Store the concatenation of lengths down from the root.
+ CurrNode.ConcatLen = CurrNodeLen;
// Traverse the tree depth-first.
for (auto &ChildPair : CurrNode.Children) {
assert(ChildPair.second && "Node had a null child!");
- setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
+ setSuffixIndices(*ChildPair.second,
+ CurrNodeLen + 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;
- }
+ // Is this node a leaf? If it is, give it a suffix index.
+ if (IsLeaf)
+ CurrNode.SuffixIdx = Str.size() - CurrNodeLen;
}
/// Construct the suffix tree for the prefix of the input ending at
@@ -461,7 +438,6 @@ private:
// 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.
@@ -495,9 +471,7 @@ public:
/// \param Str The string to construct the suffix tree for.
SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
- Root->IsInTree = true;
Active.Node = Root;
- LeafVector = std::vector<SuffixTreeNode *>(Str.size());
// Keep track of the number of suffixes we have to add of the current
// prefix.
@@ -518,6 +492,117 @@ public:
assert(Root && "Root node can't be nullptr!");
setSuffixIndices(*Root, 0);
}
+
+
+ /// 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); }
};
/// Maps \p MachineInstrs to unsigned integers and stores the mappings.
@@ -537,9 +622,8 @@ struct InstructionMapper {
DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
InstructionIntegerMap;
- /// Corresponcence from unsigned integers to \p MachineInstrs.
- /// Inverse of \p InstructionIntegerMap.
- DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
+ /// Correspondence between \p MachineBasicBlocks and target-defined flags.
+ DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
/// The vector of unsigned integers that the module is mapped to.
std::vector<unsigned> UnsignedVec;
@@ -548,17 +632,39 @@ struct InstructionMapper {
/// at index i in \p UnsignedVec for each index i.
std::vector<MachineBasicBlock::iterator> InstrList;
+ // Set if we added an illegal number in the previous step.
+ // Since each illegal number is unique, we only need one of them between
+ // each range of legal numbers. This lets us make sure we don't add more
+ // than one illegal number per range.
+ bool AddedIllegalLastTime = false;
+
/// Maps \p *It to a legal integer.
///
- /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
- /// \p IntegerInstructionMap, and \p LegalInstrNumber.
+ /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
+ /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
///
/// \returns The integer that \p *It was mapped to.
- unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
+ unsigned mapToLegalUnsigned(
+ MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
+ bool &HaveLegalRange, unsigned &NumLegalInBlock,
+ std::vector<unsigned> &UnsignedVecForMBB,
+ std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
+ // We added something legal, so we should unset the AddedLegalLastTime
+ // flag.
+ AddedIllegalLastTime = false;
+
+ // If we have at least two adjacent legal instructions (which may have
+ // invisible instructions in between), remember that.
+ if (CanOutlineWithPrevInstr)
+ HaveLegalRange = true;
+ CanOutlineWithPrevInstr = true;
+
+ // Keep track of the number of legal instructions we insert.
+ NumLegalInBlock++;
// Get the integer for this instruction or give it the current
// LegalInstrNumber.
- InstrList.push_back(It);
+ InstrListForMBB.push_back(It);
MachineInstr &MI = *It;
bool WasInserted;
DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
@@ -568,12 +674,10 @@ struct InstructionMapper {
unsigned MINumber = ResultIt->second;
// There was an insertion.
- if (WasInserted) {
+ if (WasInserted)
LegalInstrNumber++;
- IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
- }
- UnsignedVec.push_back(MINumber);
+ UnsignedVecForMBB.push_back(MINumber);
// Make sure we don't overflow or use any integers reserved by the DenseMap.
if (LegalInstrNumber >= IllegalInstrNumber)
@@ -589,14 +693,26 @@ struct InstructionMapper {
/// Maps \p *It to an illegal integer.
///
- /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
+ /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
+ /// IllegalInstrNumber.
///
/// \returns The integer that \p *It was mapped to.
- unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
+ unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It,
+ bool &CanOutlineWithPrevInstr, std::vector<unsigned> &UnsignedVecForMBB,
+ std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
+ // Can't outline an illegal instruction. Set the flag.
+ CanOutlineWithPrevInstr = false;
+
+ // Only add one illegal number per range of legal numbers.
+ if (AddedIllegalLastTime)
+ return IllegalInstrNumber;
+
+ // Remember that we added an illegal number last time.
+ AddedIllegalLastTime = true;
unsigned MINumber = IllegalInstrNumber;
- InstrList.push_back(It);
- UnsignedVec.push_back(IllegalInstrNumber);
+ InstrListForMBB.push_back(It);
+ UnsignedVecForMBB.push_back(IllegalInstrNumber);
IllegalInstrNumber--;
assert(LegalInstrNumber < IllegalInstrNumber &&
@@ -623,40 +739,78 @@ struct InstructionMapper {
/// \param TII \p TargetInstrInfo for the function.
void convertToUnsignedVec(MachineBasicBlock &MBB,
const TargetInstrInfo &TII) {
- unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB);
+ unsigned Flags = 0;
+
+ // Don't even map in this case.
+ if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
+ return;
+
+ // Store info for the MBB for later outlining.
+ MBBFlagsMap[&MBB] = Flags;
+
+ MachineBasicBlock::iterator It = MBB.begin();
- for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
- It++) {
+ // The number of instructions in this block that will be considered for
+ // outlining.
+ unsigned NumLegalInBlock = 0;
+ // True if we have at least two legal instructions which aren't separated
+ // by an illegal instruction.
+ bool HaveLegalRange = false;
+
+ // True if we can perform outlining given the last mapped (non-invisible)
+ // instruction. This lets us know if we have a legal range.
+ bool CanOutlineWithPrevInstr = false;
+
+ // FIXME: Should this all just be handled in the target, rather than using
+ // repeated calls to getOutliningType?
+ std::vector<unsigned> UnsignedVecForMBB;
+ std::vector<MachineBasicBlock::iterator> InstrListForMBB;
+
+ for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; It++) {
// Keep track of where this instruction is in the module.
switch (TII.getOutliningType(It, Flags)) {
case InstrType::Illegal:
- mapToIllegalUnsigned(It);
+ mapToIllegalUnsigned(It, CanOutlineWithPrevInstr,
+ UnsignedVecForMBB, InstrListForMBB);
break;
case InstrType::Legal:
- mapToLegalUnsigned(It);
+ mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
+ NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
break;
case InstrType::LegalTerminator:
- mapToLegalUnsigned(It);
- InstrList.push_back(It);
- UnsignedVec.push_back(IllegalInstrNumber);
- IllegalInstrNumber--;
+ mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
+ NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
+ // The instruction also acts as a terminator, so we have to record that
+ // in the string.
+ mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
+ InstrListForMBB);
break;
case InstrType::Invisible:
+ // Normally this is set by mapTo(Blah)Unsigned, but we just want to
+ // skip this instruction. So, unset the flag here.
+ AddedIllegalLastTime = false;
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--;
+ // Are there enough legal instructions in the block for outlining to be
+ // possible?
+ if (HaveLegalRange) {
+ // 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.
+ mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
+ InstrListForMBB);
+ InstrList.insert(InstrList.end(), InstrListForMBB.begin(),
+ InstrListForMBB.end());
+ UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForMBB.begin(),
+ UnsignedVecForMBB.end());
+ }
}
InstructionMapper() {
@@ -692,9 +846,6 @@ struct MachineOutliner : public ModulePass {
/// Set when the pass is constructed in TargetPassConfig.
bool RunOnAllFunctions = true;
- // Collection of IR functions created by the outliner.
- std::vector<Function *> CreatedIRFunctions;
-
StringRef getPassName() const override { return "Machine Outliner"; }
void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -717,7 +868,8 @@ struct MachineOutliner : public ModulePass {
/// Remark output explaining that a function was outlined.
void emitOutlinedFunctionRemark(OutlinedFunction &OF);
- /// Find all repeated substrings that satisfy the outlining cost model.
+ /// Find all repeated substrings that satisfy the outlining cost model by
+ /// constructing a suffix tree.
///
/// If a substring appears at least twice, then it must be represented by
/// an internal node which appears in at least two suffixes. Each suffix
@@ -726,73 +878,25 @@ struct MachineOutliner : public ModulePass {
/// internal node represents a beneficial substring, then we use each of
/// its leaf children to find the locations of its substring.
///
- /// \param ST A suffix tree to query.
/// \param Mapper Contains outlining mapping information.
- /// \param[out] CandidateList Filled with candidates representing each
- /// beneficial substring.
/// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
/// each type of candidate.
- ///
- /// \returns The length of the longest candidate found.
- unsigned
- findCandidates(SuffixTree &ST,
- InstructionMapper &Mapper,
- std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList);
-
- /// Replace the sequences of instructions represented by the
- /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
- /// described in \p FunctionList.
+ void findCandidates(InstructionMapper &Mapper,
+ std::vector<OutlinedFunction> &FunctionList);
+
+ /// Replace the sequences of instructions represented by \p OutlinedFunctions
+ /// with calls to functions.
///
/// \param M The module we are outlining from.
- /// \param CandidateList A list of candidates to be outlined.
/// \param FunctionList A list of functions to be inserted into the module.
/// \param Mapper Contains the instruction mappings for the module.
- bool outline(Module &M,
- const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList,
+ bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
InstructionMapper &Mapper);
/// Creates a function for \p OF and inserts it into the module.
- MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
- InstructionMapper &Mapper);
-
- /// Find potential outlining candidates and store them in \p CandidateList.
- ///
- /// For each type of potential candidate, also build an \p OutlinedFunction
- /// struct containing the information to build the function for that
- /// candidate.
- ///
- /// \param[out] CandidateList Filled with outlining candidates for the module.
- /// \param[out] FunctionList Filled with functions corresponding to each type
- /// of \p Candidate.
- /// \param ST The suffix tree for the module.
- ///
- /// \returns The length of the longest candidate found. 0 if there are none.
- unsigned
- buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList,
- SuffixTree &ST, InstructionMapper &Mapper);
-
- /// Helper function for pruneOverlaps.
- /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
- void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
-
- /// Remove any overlapping candidates that weren't handled by the
- /// suffix tree's pruning method.
- ///
- /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
- /// If a short candidate is chosen for outlining, then a longer candidate
- /// which has that short candidate as a suffix is chosen, the tree's pruning
- /// method will not find it. Thus, we need to prune before outlining as well.
- ///
- /// \param[in,out] CandidateList A list of outlining candidates.
- /// \param[in,out] FunctionList A list of functions to be outlined.
- /// \param Mapper Contains instruction mapping info for outlining.
- /// \param MaxCandidateLen The length of the longest candidate.
- void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList,
- InstructionMapper &Mapper, unsigned MaxCandidateLen);
+ MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
+ InstructionMapper &Mapper,
+ unsigned Name);
/// Construct a suffix tree on the instructions in \p M and outline repeated
/// strings from that tree.
@@ -802,13 +906,31 @@ struct MachineOutliner : public ModulePass {
/// function for remark emission.
DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
DISubprogram *SP;
- for (const std::shared_ptr<Candidate> &C : OF.Candidates)
- if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram()))
+ for (const Candidate &C : OF.Candidates)
+ if (C.getMF() && (SP = C.getMF()->getFunction().getSubprogram()))
return SP;
return nullptr;
}
-};
+ /// Populate and \p InstructionMapper with instruction-to-integer mappings.
+ /// These are used to construct a suffix tree.
+ void populateMapper(InstructionMapper &Mapper, Module &M,
+ MachineModuleInfo &MMI);
+
+ /// Initialize information necessary to output a size remark.
+ /// FIXME: This should be handled by the pass manager, not the outliner.
+ /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
+ /// pass manager.
+ void initSizeRemarkInfo(
+ const Module &M, const MachineModuleInfo &MMI,
+ StringMap<unsigned> &FunctionToInstrCount);
+
+ /// Emit the remark.
+ // FIXME: This should be handled by the pass manager, not the outliner.
+ void emitInstrCountChangedRemark(
+ const Module &M, const MachineModuleInfo &MMI,
+ const StringMap<unsigned> &FunctionToInstrCount);
+};
} // Anonymous namespace.
char MachineOutliner::ID = 0;
@@ -828,6 +950,10 @@ INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
void MachineOutliner::emitNotOutliningCheaperRemark(
unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
OutlinedFunction &OF) {
+ // FIXME: Right now, we arbitrarily choose some Candidate from the
+ // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
+ // We should probably sort these by function name or something to make sure
+ // the remarks are stable.
Candidate &C = CandidatesForRepeatedSeq.front();
MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
MORE.emit([&]() {
@@ -861,7 +987,7 @@ void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
MBB->findDebugLoc(MBB->begin()), MBB);
R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
- << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
+ << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
<< "from " << NV("NumOccurrences", OF.getOccurrenceCount())
<< " locations. "
<< "(Found at: ";
@@ -869,12 +995,8 @@ void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
// Tell the user the other places the candidate was found.
for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
- // Skip over things that were pruned.
- if (!OF.Candidates[i]->InCandidateList)
- continue;
-
R << NV((Twine("StartLoc") + Twine(i)).str(),
- OF.Candidates[i]->front()->getDebugLoc());
+ OF.Candidates[i].front()->getDebugLoc());
if (i != e - 1)
R << ", ";
}
@@ -884,95 +1006,65 @@ void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
MORE.emit(R);
}
-unsigned MachineOutliner::findCandidates(
- SuffixTree &ST, InstructionMapper &Mapper,
- std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList) {
- CandidateList.clear();
+void
+MachineOutliner::findCandidates(InstructionMapper &Mapper,
+ std::vector<OutlinedFunction> &FunctionList) {
FunctionList.clear();
- unsigned MaxLen = 0;
-
- // FIXME: Visit internal nodes instead of leaves.
- for (SuffixTreeNode *Leaf : ST.LeafVector) {
- assert(Leaf && "Leaves in LeafVector cannot be null!");
- if (!Leaf->IsInTree)
- continue;
-
- assert(Leaf->Parent && "All leaves must have parents!");
- SuffixTreeNode &Parent = *(Leaf->Parent);
-
- // If it doesn't appear enough, or we already outlined from it, skip it.
- if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
- continue;
-
- // Figure out if this candidate is beneficial.
- unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
-
- // Too short to be beneficial; skip it.
- // FIXME: This isn't necessarily true for, say, X86. If we factor in
- // instruction lengths we need more information than this.
- if (StringLen < 2)
- continue;
-
- // If this is a beneficial class of candidate, then every one is stored in
- // this vector.
- std::vector<Candidate> CandidatesForRepeatedSeq;
-
- // Figure out the call overhead for each instance of the sequence.
- for (auto &ChildPair : Parent.Children) {
- SuffixTreeNode *M = ChildPair.second;
-
- if (M && M->IsInTree && M->isLeaf()) {
- // Never visit this leaf again.
- M->IsInTree = false;
- unsigned StartIdx = M->SuffixIdx;
- unsigned EndIdx = StartIdx + StringLen - 1;
+ SuffixTree ST(Mapper.UnsignedVec);
- // Trick: Discard some candidates that would be incompatible with the
- // ones we've already found for this sequence. This will save us some
- // work in candidate selection.
- //
- // If two candidates overlap, then we can't outline them both. This
- // happens when we have candidates that look like, say
- //
- // AA (where each "A" is an instruction).
- //
- // We might have some portion of the module that looks like this:
- // AAAAAA (6 A's)
- //
- // In this case, there are 5 different copies of "AA" in this range, but
- // at most 3 can be outlined. If only outlining 3 of these is going to
- // be unbeneficial, then we ought to not bother.
- //
- // Note that two things DON'T overlap when they look like this:
- // start1...end1 .... start2...end2
- // That is, one must either
- // * End before the other starts
- // * Start after the other ends
- if (std::all_of(CandidatesForRepeatedSeq.begin(),
- CandidatesForRepeatedSeq.end(),
- [&StartIdx, &EndIdx](const Candidate &C) {
- return (EndIdx < C.getStartIdx() ||
- StartIdx > C.getEndIdx());
- })) {
- // It doesn't overlap with anything, so we can outline it.
- // Each sequence is over [StartIt, EndIt].
- // Save the candidate and its location.
-
- MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
- MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
-
- CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
- EndIt, StartIt->getParent(),
- FunctionList.size());
- }
+ // First, find dall of the repeated substrings in the tree of minimum length
+ // 2.
+ std::vector<Candidate> CandidatesForRepeatedSeq;
+ for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
+ CandidatesForRepeatedSeq.clear();
+ SuffixTree::RepeatedSubstring RS = *It;
+ unsigned StringLen = RS.Length;
+ for (const unsigned &StartIdx : RS.StartIndices) {
+ unsigned EndIdx = StartIdx + StringLen - 1;
+ // Trick: Discard some candidates that would be incompatible with the
+ // ones we've already found for this sequence. This will save us some
+ // work in candidate selection.
+ //
+ // If two candidates overlap, then we can't outline them both. This
+ // happens when we have candidates that look like, say
+ //
+ // AA (where each "A" is an instruction).
+ //
+ // We might have some portion of the module that looks like this:
+ // AAAAAA (6 A's)
+ //
+ // In this case, there are 5 different copies of "AA" in this range, but
+ // at most 3 can be outlined. If only outlining 3 of these is going to
+ // be unbeneficial, then we ought to not bother.
+ //
+ // Note that two things DON'T overlap when they look like this:
+ // start1...end1 .... start2...end2
+ // That is, one must either
+ // * End before the other starts
+ // * Start after the other ends
+ if (std::all_of(
+ CandidatesForRepeatedSeq.begin(), CandidatesForRepeatedSeq.end(),
+ [&StartIdx, &EndIdx](const Candidate &C) {
+ return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx());
+ })) {
+ // It doesn't overlap with anything, so we can outline it.
+ // Each sequence is over [StartIt, EndIt].
+ // Save the candidate and its location.
+
+ MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
+ MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
+ MachineBasicBlock *MBB = StartIt->getParent();
+
+ CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
+ EndIt, MBB, FunctionList.size(),
+ Mapper.MBBFlagsMap[MBB]);
}
}
// We've found something we might want to outline.
// Create an OutlinedFunction to store it and check if it'd be beneficial
// to outline.
- if (CandidatesForRepeatedSeq.empty())
+ if (CandidatesForRepeatedSeq.size() < 2)
continue;
// Arbitrarily choose a TII from the first candidate.
@@ -983,179 +1075,33 @@ unsigned MachineOutliner::findCandidates(
OutlinedFunction OF =
TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
- // If we deleted every candidate, then there's nothing to outline.
- if (OF.Candidates.empty())
+ // If we deleted too many candidates, then there's nothing worth outlining.
+ // FIXME: This should take target-specified instruction sizes into account.
+ if (OF.Candidates.size() < 2)
continue;
- std::vector<unsigned> Seq;
- for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
- Seq.push_back(ST.Str[i]);
- OF.Sequence = Seq;
- OF.Name = FunctionList.size();
-
// Is it better to outline this candidate than not?
if (OF.getBenefit() < 1) {
emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
continue;
}
- if (StringLen > MaxLen)
- MaxLen = StringLen;
-
- // The function is beneficial. Save its candidates to the candidate list
- // for pruning.
- for (std::shared_ptr<Candidate> &C : OF.Candidates)
- CandidateList.push_back(C);
FunctionList.push_back(OF);
-
- // Move to the next function.
- Parent.IsInTree = false;
- }
-
- return MaxLen;
-}
-
-// Remove C from the candidate space, and update its OutlinedFunction.
-void MachineOutliner::prune(Candidate &C,
- std::vector<OutlinedFunction> &FunctionList) {
- // Get the OutlinedFunction associated with this Candidate.
- OutlinedFunction &F = FunctionList[C.FunctionIdx];
-
- // Update C's associated function's occurrence count.
- F.decrement();
-
- // Remove C from the CandidateList.
- C.InCandidateList = false;
-
- LLVM_DEBUG(dbgs() << "- Removed a Candidate \n";
- dbgs() << "--- Num fns left for candidate: "
- << F.getOccurrenceCount() << "\n";
- dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
- << "\n";);
-}
-
-void MachineOutliner::pruneOverlaps(
- std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
- unsigned MaxCandidateLen) {
-
- // Return true if this candidate became unbeneficial for outlining in a
- // previous step.
- auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
-
- // Check if the candidate was removed in a previous step.
- if (!C.InCandidateList)
- return true;
-
- // C must be alive. Check if we should remove it.
- if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
- prune(C, FunctionList);
- return true;
- }
-
- // C is in the list, and F is still beneficial.
- return false;
- };
-
- // TODO: Experiment with interval trees or other interval-checking structures
- // to lower the time complexity of this function.
- // TODO: Can we do better than the simple greedy choice?
- // Check for overlaps in the range.
- // This is O(MaxCandidateLen * CandidateList.size()).
- for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
- It++) {
- Candidate &C1 = **It;
-
- // If C1 was already pruned, or its function is no longer beneficial for
- // outlining, move to the next candidate.
- if (ShouldSkipCandidate(C1))
- continue;
-
- // The minimum start index of any candidate that could overlap with this
- // one.
- unsigned FarthestPossibleIdx = 0;
-
- // Either the index is 0, or it's at most MaxCandidateLen indices away.
- if (C1.getStartIdx() > MaxCandidateLen)
- FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
-
- // Compare against the candidates in the list that start at most
- // FarthestPossibleIdx indices away from C1. There are at most
- // MaxCandidateLen of these.
- for (auto Sit = It + 1; Sit != Et; Sit++) {
- Candidate &C2 = **Sit;
-
- // Is this candidate too far away to overlap?
- if (C2.getStartIdx() < FarthestPossibleIdx)
- break;
-
- // If C2 was already pruned, or its function is no longer beneficial for
- // outlining, move to the next candidate.
- if (ShouldSkipCandidate(C2))
- continue;
-
- // Do C1 and C2 overlap?
- //
- // Not overlapping:
- // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
- //
- // We sorted our candidate list so C2Start <= C1Start. We know that
- // C2End > C2Start since each candidate has length >= 2. Therefore, all we
- // have to check is C2End < C2Start to see if we overlap.
- if (C2.getEndIdx() < C1.getStartIdx())
- continue;
-
- // C1 and C2 overlap.
- // We need to choose the better of the two.
- //
- // Approximate this by picking the one which would have saved us the
- // most instructions before any pruning.
-
- // Is C2 a better candidate?
- if (C2.Benefit > C1.Benefit) {
- // Yes, so prune C1. Since C1 is dead, we don't have to compare it
- // against anything anymore, so break.
- prune(C1, FunctionList);
- break;
- }
-
- // Prune C2 and move on to the next candidate.
- prune(C2, FunctionList);
- }
}
}
-unsigned MachineOutliner::buildCandidateList(
- std::vector<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
- InstructionMapper &Mapper) {
-
- std::vector<unsigned> CandidateSequence; // Current outlining candidate.
- unsigned MaxCandidateLen = 0; // Length of the longest candidate.
-
- MaxCandidateLen =
- findCandidates(ST, Mapper, CandidateList, FunctionList);
-
- // Sort the candidates in decending order. This will simplify the outlining
- // process when we have to remove the candidates from the mapping by
- // allowing us to cut them out without keeping track of an offset.
- std::stable_sort(
- CandidateList.begin(), CandidateList.end(),
- [](const std::shared_ptr<Candidate> &LHS,
- const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
-
- return MaxCandidateLen;
-}
-
MachineFunction *
-MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
- InstructionMapper &Mapper) {
+MachineOutliner::createOutlinedFunction(Module &M, OutlinedFunction &OF,
+ InstructionMapper &Mapper,
+ unsigned Name) {
// 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;
+ // FIXME: We should have a better naming scheme. This should be stable,
+ // regardless of changes to the outliner's cost model/traversal order.
+ NameStream << "OUTLINED_FUNCTION_" << Name;
// Create the function using an IR-level function.
LLVMContext &C = M.getContext();
@@ -1176,8 +1122,14 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
F->addFnAttr(Attribute::OptimizeForSize);
F->addFnAttr(Attribute::MinSize);
- // Save F so that we can add debug info later if we need to.
- CreatedIRFunctions.push_back(F);
+ // Include target features from an arbitrary candidate for the outlined
+ // function. This makes sure the outlined function knows what kinds of
+ // instructions are going into it. This is fine, since all parent functions
+ // must necessarily support the instructions that are in the outlined region.
+ Candidate &FirstCand = OF.Candidates.front();
+ const Function &ParentFn = FirstCand.getMF()->getFunction();
+ if (ParentFn.hasFnAttribute("target-features"))
+ F->addFnAttr(ParentFn.getFnAttribute("target-features"));
BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
IRBuilder<> Builder(EntryBB);
@@ -1192,12 +1144,10 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
// Insert the new function into the module.
MF.insert(MF.begin(), &MBB);
- // 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();
+ for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
+ ++I) {
+ MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
+ NewMI->dropMemRefs(MF);
// Don't keep debug information for outlined instructions.
NewMI->setDebugLoc(DebugLoc());
@@ -1206,6 +1156,10 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
TII.buildOutlinedFrame(MBB, MF, OF);
+ // Outlined functions shouldn't preserve liveness.
+ MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness);
+ MF.getRegInfo().freezeReservedRegs(MF);
+
// If there's a DISubprogram associated with this outlined function, then
// emit debug info for the outlined function.
if (DISubprogram *SP = getSubprogramOrNull(OF)) {
@@ -1214,118 +1168,127 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
DIBuilder DB(M, true, CU);
DIFile *Unit = SP->getFile();
Mangler Mg;
-
- // Walk over each IR function we created in the outliner and create
- // DISubprograms for each function.
- for (Function *F : CreatedIRFunctions) {
- // Get the mangled name of the function for the linkage name.
- std::string Dummy;
- llvm::raw_string_ostream MangledNameStream(Dummy);
- Mg.getNameWithPrefix(MangledNameStream, F, false);
-
- DISubprogram *SP = DB.createFunction(
- Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
- Unit /* File */,
- 0 /* Line 0 is reserved for compiler-generated code. */,
- DB.createSubroutineType(
- DB.getOrCreateTypeArray(None)), /* void type */
- false, true, 0, /* Line 0 is reserved for compiler-generated code. */
- DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
- true /* Outlined code is optimized code by definition. */);
-
- // Don't add any new variables to the subprogram.
- DB.finalizeSubprogram(SP);
-
- // Attach subprogram to the function.
- F->setSubprogram(SP);
- }
-
+ // Get the mangled name of the function for the linkage name.
+ std::string Dummy;
+ llvm::raw_string_ostream MangledNameStream(Dummy);
+ Mg.getNameWithPrefix(MangledNameStream, F, false);
+
+ DISubprogram *OutlinedSP = DB.createFunction(
+ Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
+ Unit /* File */,
+ 0 /* Line 0 is reserved for compiler-generated code. */,
+ DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
+ 0, /* Line 0 is reserved for compiler-generated code. */
+ DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
+ /* Outlined code is optimized code by definition. */
+ DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
+
+ // Don't add any new variables to the subprogram.
+ DB.finalizeSubprogram(OutlinedSP);
+
+ // Attach subprogram to the function.
+ F->setSubprogram(OutlinedSP);
// We're done with the DIBuilder.
DB.finalize();
}
- // Outlined functions shouldn't preserve liveness.
- MF.getProperties().reset(MachineFunctionProperties::Property::TracksLiveness);
- MF.getRegInfo().freezeReservedRegs(MF);
return &MF;
}
-bool MachineOutliner::outline(
- Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
- std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
+bool MachineOutliner::outline(Module &M,
+ std::vector<OutlinedFunction> &FunctionList,
+ InstructionMapper &Mapper) {
bool OutlinedSomething = false;
- // Replace the candidates with calls to their respective outlined functions.
- for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
- Candidate &C = *Cptr;
- // Was the candidate removed during pruneOverlaps?
- if (!C.InCandidateList)
- continue;
- // If not, then look at its OutlinedFunction.
- OutlinedFunction &OF = FunctionList[C.FunctionIdx];
+ // Number to append to the current outlined function.
+ unsigned OutlinedFunctionNum = 0;
- // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
+ // Sort by benefit. The most beneficial functions should be outlined first.
+ std::stable_sort(
+ FunctionList.begin(), FunctionList.end(),
+ [](const OutlinedFunction &LHS, const OutlinedFunction &RHS) {
+ return LHS.getBenefit() > RHS.getBenefit();
+ });
+
+ // Walk over each function, outlining them as we go along. Functions are
+ // outlined greedily, based off the sort above.
+ for (OutlinedFunction &OF : FunctionList) {
+ // If we outlined something that overlapped with a candidate in a previous
+ // step, then we can't outline from it.
+ erase_if(OF.Candidates, [&Mapper](Candidate &C) {
+ return std::any_of(
+ Mapper.UnsignedVec.begin() + C.getStartIdx(),
+ Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
+ [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
+ });
+
+ // If we made it unbeneficial to outline this function, skip it.
if (OF.getBenefit() < 1)
continue;
- // Does this candidate have a function yet?
- if (!OF.MF) {
- OF.MF = createOutlinedFunction(M, OF, Mapper);
- emitOutlinedFunctionRemark(OF);
- FunctionsCreated++;
- }
-
+ // It's beneficial. Create the function and outline its sequence's
+ // occurrences.
+ OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
+ emitOutlinedFunctionRemark(OF);
+ FunctionsCreated++;
+ OutlinedFunctionNum++; // Created a function, move to the next name.
MachineFunction *MF = OF.MF;
- MachineBasicBlock &MBB = *C.getMBB();
- MachineBasicBlock::iterator StartIt = C.front();
- MachineBasicBlock::iterator EndIt = C.back();
- assert(StartIt != C.getMBB()->end() && "StartIt out of bounds!");
- assert(EndIt != C.getMBB()->end() && "EndIt out of bounds!");
-
const TargetSubtargetInfo &STI = MF->getSubtarget();
const TargetInstrInfo &TII = *STI.getInstrInfo();
- // Insert a call to the new function and erase the old sequence.
- auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.MF, C);
-
- // If the caller tracks liveness, then we need to make sure that anything
- // we outline doesn't break liveness assumptions.
- // The outlined functions themselves currently don't track liveness, but
- // we should make sure that the ranges we yank things out of aren't
- // wrong.
- if (MBB.getParent()->getProperties().hasProperty(
- MachineFunctionProperties::Property::TracksLiveness)) {
- // Helper lambda for adding implicit def operands to the call instruction.
- auto CopyDefs = [&CallInst](MachineInstr &MI) {
- for (MachineOperand &MOP : MI.operands()) {
- // Skip over anything that isn't a register.
- if (!MOP.isReg())
- continue;
-
- // If it's a def, add it to the call instruction.
- if (MOP.isDef())
- CallInst->addOperand(
- MachineOperand::CreateReg(MOP.getReg(), true, /* isDef = true */
- true /* isImp = true */));
- }
- };
+ // Replace occurrences of the sequence with calls to the new function.
+ for (Candidate &C : OF.Candidates) {
+ MachineBasicBlock &MBB = *C.getMBB();
+ MachineBasicBlock::iterator StartIt = C.front();
+ MachineBasicBlock::iterator EndIt = C.back();
+
+ // Insert the call.
+ auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
+
+ // If the caller tracks liveness, then we need to make sure that
+ // anything we outline doesn't break liveness assumptions. The outlined
+ // functions themselves currently don't track liveness, but we should
+ // make sure that the ranges we yank things out of aren't wrong.
+ if (MBB.getParent()->getProperties().hasProperty(
+ MachineFunctionProperties::Property::TracksLiveness)) {
+ // Helper lambda for adding implicit def operands to the call
+ // instruction.
+ auto CopyDefs = [&CallInst](MachineInstr &MI) {
+ for (MachineOperand &MOP : MI.operands()) {
+ // Skip over anything that isn't a register.
+ if (!MOP.isReg())
+ continue;
+
+ // If it's a def, add it to the call instruction.
+ if (MOP.isDef())
+ CallInst->addOperand(MachineOperand::CreateReg(
+ MOP.getReg(), true, /* isDef = true */
+ true /* isImp = true */));
+ }
+ };
+ // Copy over the defs in the outlined range.
+ // First inst in outlined range <-- Anything that's defined in this
+ // ... .. range has to be added as an
+ // implicit Last inst in outlined range <-- def to the call
+ // instruction.
+ std::for_each(CallInst, std::next(EndIt), CopyDefs);
+ }
- // Copy over the defs in the outlined range.
- // First inst in outlined range <-- Anything that's defined in this
- // ... .. range has to be added as an implicit
- // Last inst in outlined range <-- def to the call instruction.
- std::for_each(CallInst, std::next(EndIt), CopyDefs);
- }
+ // Erase from the point after where the call was inserted up to, and
+ // including, the final instruction in the sequence.
+ // Erase needs one past the end, so we need std::next there too.
+ MBB.erase(std::next(StartIt), std::next(EndIt));
- // Erase from the point after where the call was inserted up to, and
- // including, the final instruction in the sequence.
- // Erase needs one past the end, so we need std::next there too.
- MBB.erase(std::next(StartIt), std::next(EndIt));
- OutlinedSomething = true;
+ // Keep track of what we removed by marking them all as -1.
+ std::for_each(Mapper.UnsignedVec.begin() + C.getStartIdx(),
+ Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
+ [](unsigned &I) { I = static_cast<unsigned>(-1); });
+ OutlinedSomething = true;
- // Statistics.
- NumOutlined++;
+ // Statistics.
+ NumOutlined++;
+ }
}
LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
@@ -1333,34 +1296,8 @@ bool MachineOutliner::outline(
return OutlinedSomething;
}
-bool MachineOutliner::runOnModule(Module &M) {
- // Check if there's anything in the module. If it's empty, then there's
- // nothing to outline.
- if (M.empty())
- return false;
-
- MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
-
- // If the user passed -enable-machine-outliner=always or
- // -enable-machine-outliner, the pass will run on all functions in the module.
- // Otherwise, if the target supports default outlining, it will run on all
- // functions deemed by the target to be worth outlining from by default. Tell
- // the user how the outliner is running.
- LLVM_DEBUG(
- dbgs() << "Machine Outliner: Running on ";
- if (RunOnAllFunctions)
- dbgs() << "all functions";
- else
- dbgs() << "target-default functions";
- dbgs() << "\n"
- );
-
- // If the user specifies that they want to outline from linkonceodrs, set
- // it here.
- OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
-
- InstructionMapper Mapper;
-
+void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
+ MachineModuleInfo &MMI) {
// Build instruction mappings for each function in the module. Start by
// iterating over each Function in M.
for (Function &F : M) {
@@ -1395,7 +1332,11 @@ bool MachineOutliner::runOnModule(Module &M) {
for (MachineBasicBlock &MBB : *MF) {
// If there isn't anything in MBB, then there's no point in outlining from
// it.
- if (MBB.empty())
+ // If there are fewer than 2 instructions in the MBB, then it can't ever
+ // contain something worth outlining.
+ // FIXME: This should be based off of the maximum size in B of an outlined
+ // call versus the size in B of the MBB.
+ if (MBB.empty() || MBB.size() < 2)
continue;
// Check if MBB could be the target of an indirect branch. If it is, then
@@ -1407,21 +1348,133 @@ bool MachineOutliner::runOnModule(Module &M) {
Mapper.convertToUnsignedVec(MBB, *TII);
}
}
+}
- // Construct a suffix tree, use it to find candidates, and then outline them.
- SuffixTree ST(Mapper.UnsignedVec);
- std::vector<std::shared_ptr<Candidate>> CandidateList;
+void MachineOutliner::initSizeRemarkInfo(
+ const Module &M, const MachineModuleInfo &MMI,
+ StringMap<unsigned> &FunctionToInstrCount) {
+ // Collect instruction counts for every function. We'll use this to emit
+ // per-function size remarks later.
+ for (const Function &F : M) {
+ MachineFunction *MF = MMI.getMachineFunction(F);
+
+ // We only care about MI counts here. If there's no MachineFunction at this
+ // point, then there won't be after the outliner runs, so let's move on.
+ if (!MF)
+ continue;
+ FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
+ }
+}
+
+void MachineOutliner::emitInstrCountChangedRemark(
+ const Module &M, const MachineModuleInfo &MMI,
+ const StringMap<unsigned> &FunctionToInstrCount) {
+ // Iterate over each function in the module and emit remarks.
+ // Note that we won't miss anything by doing this, because the outliner never
+ // deletes functions.
+ for (const Function &F : M) {
+ MachineFunction *MF = MMI.getMachineFunction(F);
+
+ // The outliner never deletes functions. If we don't have a MF here, then we
+ // didn't have one prior to outlining either.
+ if (!MF)
+ continue;
+
+ std::string Fname = F.getName();
+ unsigned FnCountAfter = MF->getInstructionCount();
+ unsigned FnCountBefore = 0;
+
+ // Check if the function was recorded before.
+ auto It = FunctionToInstrCount.find(Fname);
+
+ // Did we have a previously-recorded size? If yes, then set FnCountBefore
+ // to that.
+ if (It != FunctionToInstrCount.end())
+ FnCountBefore = It->second;
+
+ // Compute the delta and emit a remark if there was a change.
+ int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
+ static_cast<int64_t>(FnCountBefore);
+ if (FnDelta == 0)
+ continue;
+
+ MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
+ MORE.emit([&]() {
+ MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
+ DiagnosticLocation(),
+ &MF->front());
+ R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
+ << ": Function: "
+ << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
+ << ": MI instruction count changed from "
+ << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
+ FnCountBefore)
+ << " to "
+ << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
+ FnCountAfter)
+ << "; Delta: "
+ << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
+ return R;
+ });
+ }
+}
+
+bool MachineOutliner::runOnModule(Module &M) {
+ // Check if there's anything in the module. If it's empty, then there's
+ // nothing to outline.
+ if (M.empty())
+ return false;
+
+ MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
+
+ // If the user passed -enable-machine-outliner=always or
+ // -enable-machine-outliner, the pass will run on all functions in the module.
+ // Otherwise, if the target supports default outlining, it will run on all
+ // functions deemed by the target to be worth outlining from by default. Tell
+ // the user how the outliner is running.
+ LLVM_DEBUG(
+ dbgs() << "Machine Outliner: Running on ";
+ if (RunOnAllFunctions)
+ dbgs() << "all functions";
+ else
+ dbgs() << "target-default functions";
+ dbgs() << "\n"
+ );
+
+ // If the user specifies that they want to outline from linkonceodrs, set
+ // it here.
+ OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
+ InstructionMapper Mapper;
+
+ // Prepare instruction mappings for the suffix tree.
+ populateMapper(Mapper, M, MMI);
std::vector<OutlinedFunction> FunctionList;
// Find all of the outlining candidates.
- unsigned MaxCandidateLen =
- buildCandidateList(CandidateList, FunctionList, ST, Mapper);
-
- // Remove candidates that overlap with other candidates.
- pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen);
+ findCandidates(Mapper, FunctionList);
+
+ // If we've requested size remarks, then collect the MI counts of every
+ // function before outlining, and the MI counts after outlining.
+ // FIXME: This shouldn't be in the outliner at all; it should ultimately be
+ // the pass manager's responsibility.
+ // This could pretty easily be placed in outline instead, but because we
+ // really ultimately *don't* want this here, it's done like this for now
+ // instead.
+
+ // Check if we want size remarks.
+ bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
+ StringMap<unsigned> FunctionToInstrCount;
+ if (ShouldEmitSizeRemarks)
+ initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
// Outline each of the candidates and return true if something was outlined.
- bool OutlinedSomething = outline(M, CandidateList, FunctionList, Mapper);
+ bool OutlinedSomething = outline(M, FunctionList, Mapper);
+
+ // If we outlined something, we definitely changed the MI count of the
+ // module. If we've asked for size remarks, then output them.
+ // FIXME: This should be in the pass manager.
+ if (ShouldEmitSizeRemarks && OutlinedSomething)
+ emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
return OutlinedSomething;
}