Index: include/llvm/CodeGen/MachineOutliner.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/MachineOutliner.h @@ -0,0 +1,194 @@ +//===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// Contains all data structures shared between the outliner implemented in +/// MachineOutliner.cpp and target implementations of the outliner. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_MACHINEOUTLINER_H +#define LLVM_MACHINEOUTLINER_H + +#include "llvm/CodeGen/MachineFunction.h" + +namespace outliner { + +using namespace llvm; + +/// Represents how an instruction should be mapped by the outliner. +/// \p Legal instructions are those which are safe to outline. +/// \p LegalTerminator instructions are safe to outline, but only as the +/// last instruction in a sequence. +/// \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 InstrType { Legal, LegalTerminator, Illegal, Invisible }; + +/// Describes the number of instructions that it will take to call and +/// construct a frame for a given outlining candidate. +struct TargetCostInfo { + /// Represents the size of a sequence in bytes. (Some instructions vary + /// widely in size, so just counting the instructions isn't very useful.) + unsigned SequenceSize; + + /// Number of instructions to call an outlined function for this candidate. + unsigned CallOverhead; + + /// Number of instructions to construct an outlined function frame + /// for this candidate. + unsigned FrameOverhead; + + /// Represents the specific instructions that must be emitted to + /// construct a call to this candidate. + unsigned CallConstructionID; + + /// Represents the specific instructions that must be emitted to + /// construct a frame for this candidate's outlined function. + unsigned FrameConstructionID; + + TargetCostInfo() {} + TargetCostInfo(unsigned SequenceSize, unsigned CallOverhead, + unsigned FrameOverhead, unsigned CallConstructionID, + unsigned FrameConstructionID) + : SequenceSize(SequenceSize), CallOverhead(CallOverhead), + FrameOverhead(FrameOverhead), CallConstructionID(CallConstructionID), + FrameConstructionID(FrameConstructionID) {} +}; + +/// An individual sequence of instructions to be replaced with a call to +/// an outlined function. +struct Candidate { +private: + /// The start index of this \p Candidate in the instruction list. + unsigned StartIdx; + + /// The number of instructions in this \p Candidate. + unsigned Len; + + // The first instruction in this \p Candidate. + MachineBasicBlock::iterator FirstInst; + + // The last instruction in this \p Candidate. + MachineBasicBlock::iterator LastInst; + + // The basic block that contains this Candidate. + MachineBasicBlock *MBB; + +public: + /// The index of this \p Candidate's \p OutlinedFunction in the list of + /// \p OutlinedFunctions. + unsigned FunctionIdx; + + /// Set to false if the candidate overlapped with another candidate. + bool InCandidateList = true; + + /// Contains all target-specific information for this \p Candidate. + TargetCostInfo TCI; + + /// Return the number of instructions in this Candidate. + unsigned getLength() const { return Len; } + + /// Return the start index of this candidate. + unsigned getStartIdx() const { return StartIdx; } + + /// Return the end index of this candidate. + unsigned getEndIdx() const { return StartIdx + Len - 1; } + + MachineBasicBlock::iterator &front() { return FirstInst; } + MachineBasicBlock::iterator &back() { return LastInst; } + MachineFunction *getMF() const { return MBB->getParent(); } + MachineBasicBlock *getMBB() const { return MBB; } + + /// The number of instructions that would be saved by outlining every + /// candidate of this type. + /// + /// This is a fixed value which is not updated during the candidate pruning + /// process. It is only used for deciding which candidate to keep if two + /// candidates overlap. The true benefit is stored in the OutlinedFunction + /// for some given candidate. + unsigned Benefit = 0; + + Candidate(unsigned StartIdx, unsigned Len, + MachineBasicBlock::iterator &FirstInst, + MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, + unsigned FunctionIdx) + : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), + MBB(MBB), FunctionIdx(FunctionIdx) {} + + /// Used to ensure that \p Candidates are outlined in an order that + /// preserves the start and end indices of other \p Candidates. + bool operator<(const Candidate &RHS) const { + return getStartIdx() > RHS.getStartIdx(); + } +}; + +/// The information necessary to create an outlined function for some +/// class of candidate. +struct OutlinedFunction { + +private: + /// The number of candidates for this \p OutlinedFunction. + unsigned OccurrenceCount = 0; + +public: + std::vector> Candidates; + + /// The actual outlined function created. + /// This is initialized after we go through and create the actual function. + MachineFunction *MF = nullptr; + + /// A number assigned to this function which appears at the end of its name. + unsigned Name; + + /// The sequence of integers corresponding to the instructions in this + /// function. + std::vector Sequence; + + /// Contains all target-specific information for this \p OutlinedFunction. + TargetCostInfo TCI; + + /// Return the number of candidates for this \p OutlinedFunction. + unsigned getOccurrenceCount() { return OccurrenceCount; } + + /// Decrement the occurrence count of this OutlinedFunction and return the + /// new count. + unsigned decrement() { + assert(OccurrenceCount > 0 && "Can't decrement an empty function!"); + OccurrenceCount--; + return getOccurrenceCount(); + } + + /// Return the number of bytes it would take to outline this + /// function. + unsigned getOutliningCost() { + return (OccurrenceCount * TCI.CallOverhead) + TCI.SequenceSize + + TCI.FrameOverhead; + } + + /// Return the size in bytes of the unoutlined sequences. + unsigned getNotOutlinedCost() { return OccurrenceCount * TCI.SequenceSize; } + + /// Return the number of instructions that would be saved by outlining + /// this function. + unsigned getBenefit() { + unsigned NotOutlinedCost = getNotOutlinedCost(); + unsigned OutlinedCost = getOutliningCost(); + return (NotOutlinedCost < OutlinedCost) ? 0 + : NotOutlinedCost - OutlinedCost; + } + + OutlinedFunction(unsigned Name, unsigned OccurrenceCount, + const std::vector &Sequence, TargetCostInfo &TCI) + : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence), + TCI(TCI) {} +}; +} // namespace outliner + +#endif Index: include/llvm/CodeGen/TargetInstrInfo.h =================================================================== --- include/llvm/CodeGen/TargetInstrInfo.h +++ include/llvm/CodeGen/TargetInstrInfo.h @@ -25,6 +25,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineOutliner.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/MC/MCInstrInfo.h" #include "llvm/Support/BranchProbability.h" @@ -1603,59 +1604,16 @@ /// Returns true if the target implements the MachineOutliner. virtual bool useMachineOutliner() const { return false; } - /// Describes the number of instructions that it will take to call and - /// construct a frame for a given outlining candidate. - struct MachineOutlinerInfo { - /// Represents the size of a sequence in bytes. (Some instructions vary - /// widely in size, so just counting the instructions isn't very useful.) - unsigned SequenceSize; - - /// Number of instructions to call an outlined function for this candidate. - unsigned CallOverhead; - - /// Number of instructions to construct an outlined function frame - /// for this candidate. - unsigned FrameOverhead; - - /// Represents the specific instructions that must be emitted to - /// construct a call to this candidate. - unsigned CallConstructionID; - - /// Represents the specific instructions that must be emitted to - /// construct a frame for this candidate's outlined function. - unsigned FrameConstructionID; - - MachineOutlinerInfo() {} - MachineOutlinerInfo(unsigned SequenceSize, unsigned CallOverhead, - unsigned FrameOverhead, unsigned CallConstructionID, - unsigned FrameConstructionID) - : SequenceSize(SequenceSize), CallOverhead(CallOverhead), - FrameOverhead(FrameOverhead), - CallConstructionID(CallConstructionID), - FrameConstructionID(FrameConstructionID) {} - }; - - /// Returns a \p MachineOutlinerInfo struct containing target-specific + /// Returns a \p outliner::TargetCostInfo struct containing target-specific /// information for a set of outlining candidates. - virtual MachineOutlinerInfo getOutlininingCandidateInfo( - std::vector< - std::pair> - &RepeatedSequenceLocs) const { + virtual outliner::TargetCostInfo getOutlininingCandidateInfo( + std::vector &RepeatedSequenceLocs) const { llvm_unreachable( "Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!"); } - /// Represents how an instruction should be mapped by the outliner. - /// \p Legal instructions are those which are safe to outline. - /// \p LegalTerminator instructions are safe to outline, but only as the - /// last instruction in a sequence. - /// \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, LegalTerminator, Illegal, Invisible }; - /// Returns how or if \p MI should be outlined. - virtual MachineOutlinerInstrType + virtual outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const { llvm_unreachable( "Target didn't implement TargetInstrInfo::getOutliningType!"); @@ -1672,7 +1630,7 @@ /// emitted. virtual void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const { + const outliner::TargetCostInfo &TCI) const { llvm_unreachable( "Target didn't implement TargetInstrInfo::insertOutlinerEpilogue!"); } @@ -1683,7 +1641,7 @@ virtual MachineBasicBlock::iterator insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const { + const outliner::TargetCostInfo &TCI) const { llvm_unreachable( "Target didn't implement TargetInstrInfo::insertOutlinedCall!"); } @@ -1692,7 +1650,7 @@ /// This may be empty, in which case no prologue will be emitted. virtual void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const { + const outliner::TargetCostInfo &TCI) const { llvm_unreachable( "Target didn't implement TargetInstrInfo::insertOutlinerPrologue!"); } Index: lib/CodeGen/MachineOutliner.cpp =================================================================== --- lib/CodeGen/MachineOutliner.cpp +++ lib/CodeGen/MachineOutliner.cpp @@ -56,6 +56,7 @@ /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf /// //===----------------------------------------------------------------------===// +#include "llvm/CodeGen/MachineOutliner.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" @@ -84,6 +85,7 @@ using namespace llvm; using namespace ore; +using namespace outliner; STATISTIC(NumOutlined, "Number of candidates outlined"); STATISTIC(FunctionsCreated, "Number of functions created"); @@ -101,143 +103,6 @@ namespace { -/// An individual sequence of instructions to be replaced with a call to -/// an outlined function. -struct Candidate { -private: - /// The start index of this \p Candidate in the instruction list. - unsigned StartIdx; - - /// The number of instructions in this \p Candidate. - unsigned Len; - - /// The MachineFunction containing this \p Candidate. - MachineFunction *MF = nullptr; - -public: - /// Set to false if the candidate overlapped with another candidate. - bool InCandidateList = true; - - /// The index of this \p Candidate's \p OutlinedFunction in the list of - /// \p OutlinedFunctions. - unsigned FunctionIdx; - - /// Contains all target-specific information for this \p Candidate. - TargetInstrInfo::MachineOutlinerInfo MInfo; - - /// If there is a DISubprogram associated with the function that this - /// Candidate lives in, return it. - DISubprogram *getSubprogramOrNull() const { - assert(MF && "Candidate has no MF!"); - if (DISubprogram *SP = MF->getFunction().getSubprogram()) - return SP; - return nullptr; - } - - /// Return the number of instructions in this Candidate. - unsigned getLength() const { return Len; } - - /// Return the start index of this candidate. - unsigned getStartIdx() const { return StartIdx; } - - // Return the end index of this candidate. - unsigned getEndIdx() const { return StartIdx + Len - 1; } - - /// The number of instructions that would be saved by outlining every - /// candidate of this type. - /// - /// This is a fixed value which is not updated during the candidate pruning - /// process. It is only used for deciding which candidate to keep if two - /// candidates overlap. The true benefit is stored in the OutlinedFunction - /// for some given candidate. - unsigned Benefit = 0; - - Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx, - MachineFunction *MF) - : StartIdx(StartIdx), Len(Len), MF(MF), FunctionIdx(FunctionIdx) {} - - Candidate() {} - - /// Used to ensure that \p Candidates are outlined in an order that - /// preserves the start and end indices of other \p Candidates. - bool operator<(const Candidate &RHS) const { - return getStartIdx() > RHS.getStartIdx(); - } -}; - -/// The information necessary to create an outlined function for some -/// class of candidate. -struct OutlinedFunction { - -private: - /// The number of candidates for this \p OutlinedFunction. - unsigned OccurrenceCount = 0; - -public: - std::vector> Candidates; - - /// The actual outlined function created. - /// This is initialized after we go through and create the actual function. - MachineFunction *MF = nullptr; - - /// A number assigned to this function which appears at the end of its name. - unsigned Name; - - /// The sequence of integers corresponding to the instructions in this - /// function. - std::vector Sequence; - - /// Contains all target-specific information for this \p OutlinedFunction. - TargetInstrInfo::MachineOutlinerInfo MInfo; - - /// If there is a DISubprogram for any Candidate for this outlined function, - /// then return it. Otherwise, return nullptr. - DISubprogram *getSubprogramOrNull() const { - for (const auto &C : Candidates) - if (DISubprogram *SP = C->getSubprogramOrNull()) - return SP; - return nullptr; - } - - /// Return the number of candidates for this \p OutlinedFunction. - unsigned getOccurrenceCount() { return OccurrenceCount; } - - /// Decrement the occurrence count of this OutlinedFunction and return the - /// new count. - unsigned decrement() { - assert(OccurrenceCount > 0 && "Can't decrement an empty function!"); - OccurrenceCount--; - return getOccurrenceCount(); - } - - /// Return the number of bytes it would take to outline this - /// function. - unsigned getOutliningCost() { - return (OccurrenceCount * MInfo.CallOverhead) + MInfo.SequenceSize + - MInfo.FrameOverhead; - } - - /// Return the size in bytes of the unoutlined sequences. - unsigned getNotOutlinedCost() { - return OccurrenceCount * MInfo.SequenceSize; - } - - /// Return the number of instructions that would be saved by outlining - /// this function. - unsigned getBenefit() { - unsigned NotOutlinedCost = getNotOutlinedCost(); - unsigned OutlinedCost = getOutliningCost(); - return (NotOutlinedCost < OutlinedCost) ? 0 - : NotOutlinedCost - OutlinedCost; - } - - OutlinedFunction(unsigned Name, unsigned OccurrenceCount, - const std::vector &Sequence, - TargetInstrInfo::MachineOutlinerInfo &MInfo) - : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence), - MInfo(MInfo) {} -}; - /// Represents an undefined index in the suffix tree. const unsigned EmptyIdx = -1; @@ -769,22 +634,22 @@ // Keep track of where this instruction is in the module. switch (TII.getOutliningType(It, Flags)) { - case TargetInstrInfo::MachineOutlinerInstrType::Illegal: + case InstrType::Illegal: mapToIllegalUnsigned(It); break; - case TargetInstrInfo::MachineOutlinerInstrType::Legal: + case InstrType::Legal: mapToLegalUnsigned(It); break; - case TargetInstrInfo::MachineOutlinerInstrType::LegalTerminator: + case InstrType::LegalTerminator: mapToLegalUnsigned(It); InstrList.push_back(It); UnsignedVec.push_back(IllegalInstrNumber); IllegalInstrNumber--; break; - case TargetInstrInfo::MachineOutlinerInstrType::Invisible: + case InstrType::Invisible: break; } } @@ -926,6 +791,16 @@ /// Construct a suffix tree on the instructions in \p M and outline repeated /// strings from that tree. bool runOnModule(Module &M) override; + + /// Return a DISubprogram for OF if one exists, and null otherwise. Helper + /// function for remark emission. + DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) { + DISubprogram *SP; + for (const std::shared_ptr &C : OF.Candidates) + if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram())) + return SP; + return nullptr; + } }; } // Anonymous namespace. @@ -976,14 +851,6 @@ // this vector. std::vector CandidatesForRepeatedSeq; - // Describes the start and end point of each candidate. This allows the - // target to infer some information about each occurrence of each repeated - // sequence. - // FIXME: CandidatesForRepeatedSeq and this should be combined. - std::vector< - std::pair> - RepeatedSequenceLocs; - // Figure out the call overhead for each instance of the sequence. for (auto &ChildPair : Parent.Children) { SuffixTreeNode *M = ChildPair.second; @@ -1019,21 +886,18 @@ CandidatesForRepeatedSeq.end(), [&StartIdx, &EndIdx](const Candidate &C) { return (EndIdx < C.getStartIdx() || - StartIdx > C.getEndIdx()); + 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]; - // Save the MachineFunction containing the Candidate. - MachineFunction *MF = StartIt->getParent()->getParent(); - assert(MF && "Candidate doesn't have a MF?"); - - // Save the candidate and its location. - CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, - FunctionList.size(), MF); - RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt)); + CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, + EndIt, StartIt->getParent(), + FunctionList.size()); } } } @@ -1041,13 +905,13 @@ // We've found something we might want to outline. // Create an OutlinedFunction to store it and check if it'd be beneficial // to outline. - TargetInstrInfo::MachineOutlinerInfo MInfo = - TII.getOutlininingCandidateInfo(RepeatedSequenceLocs); + TargetCostInfo TCI = + TII.getOutlininingCandidateInfo(CandidatesForRepeatedSeq); std::vector Seq; for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++) Seq.push_back(ST.Str[i]); OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(), - Seq, MInfo); + Seq, TCI); unsigned Benefit = OF.getBenefit(); // Is it better to outline this candidate than not? @@ -1055,16 +919,13 @@ // Outlining this candidate would take more instructions than not // outlining. // Emit a remark explaining why we didn't outline this candidate. - std::pair C = - RepeatedSequenceLocs[0]; - MachineOptimizationRemarkEmitter MORE( - *(C.first->getParent()->getParent()), nullptr); + Candidate &C = CandidatesForRepeatedSeq.front(); + MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr); MORE.emit([&]() { MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper", - C.first->getDebugLoc(), - C.first->getParent()); + C.front()->getDebugLoc(), C.getMBB()); R << "Did not outline " << NV("Length", StringLen) << " instructions" - << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size()) + << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size()) << " locations." << " Bytes from outlining all occurrences (" << NV("OutliningCost", OF.getOutliningCost()) << ")" @@ -1073,9 +934,9 @@ << " (Also found at: "; // Tell the user the other places the candidate was found. - for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) { + for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) { R << NV((Twine("OtherStartLoc") + Twine(i)).str(), - RepeatedSequenceLocs[i].first->getDebugLoc()); + CandidatesForRepeatedSeq[i].front()->getDebugLoc()); if (i != e - 1) R << ", "; } @@ -1096,7 +957,7 @@ std::vector> CandidatesForFn; for (Candidate &C : CandidatesForRepeatedSeq) { C.Benefit = Benefit; - C.MInfo = MInfo; + C.TCI = TCI; std::shared_ptr Cptr = std::make_shared(C); CandidateList.push_back(Cptr); CandidatesForFn.push_back(Cptr); @@ -1289,7 +1150,7 @@ // Insert the new function into the module. MF.insert(MF.begin(), &MBB); - TII.insertOutlinerPrologue(MBB, MF, OF.MInfo); + TII.insertOutlinerPrologue(MBB, MF, OF.TCI); // Copy over the instructions for the function using the integer mappings in // its sequence. @@ -1303,11 +1164,11 @@ MBB.insert(MBB.end(), NewMI); } - TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo); + TII.insertOutlinerEpilogue(MBB, MF, OF.TCI); // If there's a DISubprogram associated with this outlined function, then // emit debug info for the outlined function. - if (DISubprogram *SP = OF.getSubprogramOrNull()) { + if (DISubprogram *SP = getSubprogramOrNull(OF)) { // We have a DISubprogram. Get its DICompileUnit. DICompileUnit *CU = SP->getUnit(); DIBuilder DB(M, true, CU); @@ -1368,17 +1229,6 @@ if (OF.getBenefit() < 1) continue; - // If not, then outline it. - assert(C.getStartIdx() < Mapper.InstrList.size() && - "Candidate out of bounds!"); - MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent(); - MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()]; - unsigned EndIdx = C.getEndIdx(); - - assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!"); - MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; - assert(EndIt != MBB->end() && "EndIt out of bounds!"); - // Does this candidate have a function yet? if (!OF.MF) { OF.MF = createOutlinedFunction(M, OF, Mapper); @@ -1405,7 +1255,7 @@ R << NV( (Twine("StartLoc") + Twine(i)).str(), - Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc()); + OF.Candidates[i]->front()->getDebugLoc()); if (i != e - 1) R << ", "; } @@ -1417,19 +1267,24 @@ } 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, *MF, C.MInfo); - StartIt = Mapper.InstrList[C.getStartIdx()]; + auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.MF, C.TCI); // 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( + if (MBB.getParent()->getProperties().hasProperty( MachineFunctionProperties::Property::TracksLiveness)) { // Helper lambda for adding implicit def operands to the call instruction. auto CopyDefs = [&CallInst](MachineInstr &MI) { @@ -1453,8 +1308,10 @@ std::for_each(CallInst, EndIt, CopyDefs); } - EndIt++; // Erase needs one past the end index. - MBB->erase(StartIt, 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; // Statistics. Index: lib/Target/AArch64/AArch64InstrInfo.h =================================================================== --- lib/Target/AArch64/AArch64InstrInfo.h +++ lib/Target/AArch64/AArch64InstrInfo.h @@ -243,21 +243,19 @@ canOutlineWithoutLRSave(MachineBasicBlock::iterator &CallInsertionPt) const; bool isFunctionSafeToOutlineFrom(MachineFunction &MF, bool OutlineFromLinkOnceODRs) const override; - MachineOutlinerInfo getOutlininingCandidateInfo( - std::vector< - std::pair> - &RepeatedSequenceLocs) const override; - AArch64GenInstrInfo::MachineOutlinerInstrType + outliner::TargetCostInfo getOutlininingCandidateInfo( + std::vector &RepeatedSequenceLocs) const override; + outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const override; unsigned getMachineOutlinerMBBFlags(MachineBasicBlock &MBB) const override; void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; MachineBasicBlock::iterator insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; /// Returns true if the instruction sets to an immediate value that can be /// executed more efficiently. bool isExynosResetFast(const MachineInstr &MI) const; Index: lib/Target/AArch64/AArch64InstrInfo.cpp =================================================================== --- lib/Target/AArch64/AArch64InstrInfo.cpp +++ lib/Target/AArch64/AArch64InstrInfo.cpp @@ -4947,11 +4947,9 @@ return LRU.available(AArch64::LR); } -AArch64GenInstrInfo::MachineOutlinerInfo +outliner::TargetCostInfo AArch64InstrInfo::getOutlininingCandidateInfo( - std::vector< - std::pair> - &RepeatedSequenceLocs) const { + std::vector &RepeatedSequenceLocs) const { unsigned SequenceSize = std::accumulate( RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second), 0, [this](unsigned Sum, const MachineInstr &MI) { @@ -4962,15 +4960,14 @@ unsigned NumBytesForCall = 12; unsigned NumBytesToCreateFrame = 4; - auto DoesntNeedLRSave = - [this](std::pair - &I) { return canOutlineWithoutLRSave(I.second); }; + auto DoesntNeedLRSave = + [this](outliner::Candidate &I) {return canOutlineWithoutLRSave(I.back());}; - unsigned LastInstrOpcode = RepeatedSequenceLocs[0].second->getOpcode(); + unsigned LastInstrOpcode = RepeatedSequenceLocs[0].back()->getOpcode(); // If the last instruction in any candidate is a terminator, then we should // tail call all of the candidates. - if (RepeatedSequenceLocs[0].second->isTerminator()) { + if (RepeatedSequenceLocs[0].back()->isTerminator()) { CallID = MachineOutlinerTailCall; FrameID = MachineOutlinerTailCall; NumBytesForCall = 4; @@ -4995,7 +4992,8 @@ // Check if the range contains a call. These require a save + restore of the // link register. - if (std::any_of(RepeatedSequenceLocs[0].first, RepeatedSequenceLocs[0].second, + if (std::any_of(RepeatedSequenceLocs[0].front(), + RepeatedSequenceLocs[0].back(), [](const MachineInstr &MI) { return MI.isCall(); })) NumBytesToCreateFrame += 8; // Save + restore the link register. @@ -5005,10 +5003,10 @@ // it being valid to tail call this sequence. We should consider this as well. else if (FrameID != MachineOutlinerThunk && FrameID != MachineOutlinerTailCall && - RepeatedSequenceLocs[0].second->isCall()) + RepeatedSequenceLocs[0].back()->isCall()) NumBytesToCreateFrame += 8; - return MachineOutlinerInfo(SequenceSize, NumBytesForCall, + return outliner::TargetCostInfo(SequenceSize, NumBytesForCall, NumBytesToCreateFrame, CallID, FrameID); } @@ -5062,7 +5060,7 @@ return Flags; } -AArch64GenInstrInfo::MachineOutlinerInstrType +outliner::InstrType AArch64InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const { MachineInstr &MI = *MIT; @@ -5072,45 +5070,45 @@ // Don't outline LOHs. if (FuncInfo->getLOHRelated().count(&MI)) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Don't allow debug values to impact outlining type. if (MI.isDebugInstr() || MI.isIndirectDebugValue()) - return MachineOutlinerInstrType::Invisible; + return outliner::InstrType::Invisible; // At this point, KILL instructions don't really tell us much so we can go // ahead and skip over them. if (MI.isKill()) - return MachineOutlinerInstrType::Invisible; + return outliner::InstrType::Invisible; // Is this a terminator for a basic block? if (MI.isTerminator()) { // Is this the end of a function? if (MI.getParent()->succ_empty()) - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; // It's not, so don't outline it. - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; } // Make sure none of the operands are un-outlinable. for (const MachineOperand &MOP : MI.operands()) { if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() || MOP.isTargetIndex()) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // If it uses LR or W30 explicitly, then don't touch it. if (MOP.isReg() && !MOP.isImplicit() && (MOP.getReg() == AArch64::LR || MOP.getReg() == AArch64::W30)) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; } // Special cases for instructions that can always be outlined, but will fail // the later tests. e.g, ADRPs, which are PC-relative use LR, but can always // be outlined because they don't require a *specific* value to be in LR. if (MI.getOpcode() == AArch64::ADRP) - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; // If MI is a call we might be able to outline it. We don't want to outline // any calls that rely on the position of items on the stack. When we outline @@ -5139,15 +5137,15 @@ // Never outline calls to mcount. There isn't any rule that would require // this, but the Linux kernel's "ftrace" feature depends on it. if (Callee && Callee->getName() == "\01_mcount") - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // If we don't know anything about the callee, assume it depends on the // stack layout of the caller. In that case, it's only legal to outline // as a tail-call. Whitelist the call instructions we know about so we // don't get unexpected results with call pseudo-instructions. - auto UnknownCallOutlineType = MachineOutlinerInstrType::Illegal; + auto UnknownCallOutlineType = outliner::InstrType::Illegal; if (MI.getOpcode() == AArch64::BLR || MI.getOpcode() == AArch64::BL) - UnknownCallOutlineType = MachineOutlinerInstrType::LegalTerminator; + UnknownCallOutlineType = outliner::InstrType::LegalTerminator; if (!Callee) return UnknownCallOutlineType; @@ -5170,17 +5168,17 @@ // At this point, we can say that CalleeMF ought to not pass anything on the // stack. Therefore, we can outline it. - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; } // Don't outline positions. if (MI.isPosition()) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Don't touch the link register or W30. if (MI.readsRegister(AArch64::W30, &getRegisterInfo()) || MI.modifiesRegister(AArch64::W30, &getRegisterInfo())) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Does this use the stack? if (MI.modifiesRegister(AArch64::SP, &RI) || @@ -5229,13 +5227,13 @@ // SUBXris are extremely common in prologue/epilogue code, so supporting // them in the outliner can be a pretty big win! if (!MightNeedStackFixUp) - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; // Any modification of SP will break our code to save/restore LR. // FIXME: We could handle some instructions which add a constant offset to // SP, with a bit more work. if (MI.modifiesRegister(AArch64::SP, &RI)) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // At this point, we have a stack instruction that we might need to fix // up. We'll handle it if it's a load or store. @@ -5247,7 +5245,7 @@ // Does it allow us to offset the base register and is the base SP? if (!getMemOpBaseRegImmOfsWidth(MI, Base, Offset, DummyWidth, &RI) || Base != AArch64::SP) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Find the minimum/maximum offset for this instruction and check if // fixing it up would be in range. @@ -5260,19 +5258,19 @@ // to a MIR test, it really ought to be checked. Offset += 16; // Update the offset to what it would be if we outlined. if (Offset < MinOffset * Scale || Offset > MaxOffset * Scale) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // It's in range, so we can outline it. - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; } // FIXME: Add handling for instructions like "add x0, sp, #8". // We can't fix it up, so don't outline it. - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; } - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; } void AArch64InstrInfo::fixupPostOutline(MachineBasicBlock &MBB) const { @@ -5305,10 +5303,10 @@ void AArch64InstrInfo::insertOutlinerEpilogue( MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const { + const outliner::TargetCostInfo &TCI) const { // For thunk outlining, rewrite the last instruction from a call to a // tail-call. - if (MInfo.FrameConstructionID == MachineOutlinerThunk) { + if (TCI.FrameConstructionID == MachineOutlinerThunk) { MachineInstr *Call = &*--MBB.instr_end(); unsigned TailOpcode; if (Call->getOpcode() == AArch64::BL) { @@ -5331,7 +5329,7 @@ if (std::any_of(MBB.instr_begin(), MBB.instr_end(), IsNonTailCall)) { // Fix up the instructions in the range, since we're going to modify the // stack. - assert(MInfo.FrameConstructionID != MachineOutlinerDefault && + assert(TCI.FrameConstructionID != MachineOutlinerDefault && "Can only fix up stack references once"); fixupPostOutline(MBB); @@ -5341,8 +5339,8 @@ MachineBasicBlock::iterator It = MBB.begin(); MachineBasicBlock::iterator Et = MBB.end(); - if (MInfo.FrameConstructionID == MachineOutlinerTailCall || - MInfo.FrameConstructionID == MachineOutlinerThunk) + if (TCI.FrameConstructionID == MachineOutlinerTailCall || + TCI.FrameConstructionID == MachineOutlinerThunk) Et = std::prev(MBB.end()); // Insert a save before the outlined region @@ -5382,8 +5380,8 @@ } // If this is a tail call outlined function, then there's already a return. - if (MInfo.FrameConstructionID == MachineOutlinerTailCall || - MInfo.FrameConstructionID == MachineOutlinerThunk) + if (TCI.FrameConstructionID == MachineOutlinerTailCall || + TCI.FrameConstructionID == MachineOutlinerThunk) return; // It's not a tail call, so we have to insert the return ourselves. @@ -5392,7 +5390,7 @@ MBB.insert(MBB.end(), ret); // Did we have to modify the stack by saving the link register? - if (MInfo.FrameConstructionID == MachineOutlinerNoLRSave) + if (TCI.FrameConstructionID == MachineOutlinerNoLRSave) return; // We modified the stack. @@ -5402,14 +5400,14 @@ void AArch64InstrInfo::insertOutlinerPrologue( MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const {} + const outliner::TargetCostInfo &TCI) const {} MachineBasicBlock::iterator AArch64InstrInfo::insertOutlinedCall( Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, - MachineFunction &MF, const MachineOutlinerInfo &MInfo) const { + MachineFunction &MF, const outliner::TargetCostInfo &TCI) const { // Are we tail calling? - if (MInfo.CallConstructionID == MachineOutlinerTailCall) { + if (TCI.CallConstructionID == MachineOutlinerTailCall) { // If yes, then we can just branch to the label. It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(AArch64::TCRETURNdi)) .addGlobalAddress(M.getNamedValue(MF.getName())) @@ -5418,8 +5416,8 @@ } // Are we saving the link register? - if (MInfo.CallConstructionID == MachineOutlinerNoLRSave || - MInfo.CallConstructionID == MachineOutlinerThunk) { + if (TCI.CallConstructionID == MachineOutlinerNoLRSave || + TCI.CallConstructionID == MachineOutlinerThunk) { // No, so just insert the call. It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(AArch64::BL)) .addGlobalAddress(M.getNamedValue(MF.getName()))); Index: lib/Target/X86/X86InstrInfo.h =================================================================== --- lib/Target/X86/X86InstrInfo.h +++ lib/Target/X86/X86InstrInfo.h @@ -593,27 +593,25 @@ /// X86 supports the MachineOutliner. bool useMachineOutliner() const override { return true; } - virtual MachineOutlinerInfo getOutlininingCandidateInfo( - std::vector< - std::pair> - &RepeatedSequenceLocs) const override; + virtual outliner::TargetCostInfo getOutlininingCandidateInfo( + std::vector &RepeatedSequenceLocs) const override; bool isFunctionSafeToOutlineFrom(MachineFunction &MF, bool OutlineFromLinkOnceODRs) const override; - llvm::X86GenInstrInfo::MachineOutlinerInstrType + outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const override; void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; MachineBasicBlock::iterator insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const override; + const outliner::TargetCostInfo &TCI) const override; protected: /// Commutes the operands in the given instruction by changing the operands Index: lib/Target/X86/X86InstrInfo.cpp =================================================================== --- lib/Target/X86/X86InstrInfo.cpp +++ lib/Target/X86/X86InstrInfo.cpp @@ -11139,13 +11139,11 @@ MachineOutlinerTailCall }; -X86GenInstrInfo::MachineOutlinerInfo +outliner::TargetCostInfo X86InstrInfo::getOutlininingCandidateInfo( - std::vector< - std::pair> - &RepeatedSequenceLocs) const { + std::vector &RepeatedSequenceLocs) const { unsigned SequenceSize = std::accumulate( - RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second), + RepeatedSequenceLocs[0].front(), std::next(RepeatedSequenceLocs[0].back()), 0, [](unsigned Sum, const MachineInstr &MI) { // FIXME: x86 doesn't implement getInstSizeInBytes, so we can't // tell the cost. Just assume each instruction is one byte. @@ -11155,15 +11153,15 @@ }); // FIXME: Use real size in bytes for call and ret instructions. - if (RepeatedSequenceLocs[0].second->isTerminator()) - return MachineOutlinerInfo(SequenceSize, + if (RepeatedSequenceLocs[0].back()->isTerminator()) + return outliner::TargetCostInfo(SequenceSize, 1, // Number of bytes to emit call. 0, // Number of bytes to emit frame. MachineOutlinerTailCall, // Type of call. MachineOutlinerTailCall // Type of frame. ); - return MachineOutlinerInfo(SequenceSize, 1, 1, MachineOutlinerDefault, + return outliner::TargetCostInfo(SequenceSize, 1, 1, MachineOutlinerDefault, MachineOutlinerDefault); } @@ -11189,31 +11187,31 @@ return true; } -X86GenInstrInfo::MachineOutlinerInstrType +outliner::InstrType X86InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const { MachineInstr &MI = *MIT; // Don't allow debug values to impact outlining type. if (MI.isDebugInstr() || MI.isIndirectDebugValue()) - return MachineOutlinerInstrType::Invisible; + return outliner::InstrType::Invisible; // At this point, KILL instructions don't really tell us much so we can go // ahead and skip over them. if (MI.isKill()) - return MachineOutlinerInstrType::Invisible; + return outliner::InstrType::Invisible; // Is this a tail call? If yes, we can outline as a tail call. if (isTailCall(MI)) - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; // Is this the terminator of a basic block? if (MI.isTerminator() || MI.isReturn()) { // Does its parent have any successors in its MachineFunction? if (MI.getParent()->succ_empty()) - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; // It does, so we can't tail call it. - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; } // Don't outline anything that modifies or reads from the stack pointer. @@ -11228,33 +11226,33 @@ if (MI.modifiesRegister(X86::RSP, &RI) || MI.readsRegister(X86::RSP, &RI) || MI.getDesc().hasImplicitUseOfPhysReg(X86::RSP) || MI.getDesc().hasImplicitDefOfPhysReg(X86::RSP)) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Outlined calls change the instruction pointer, so don't read from it. if (MI.readsRegister(X86::RIP, &RI) || MI.getDesc().hasImplicitUseOfPhysReg(X86::RIP) || MI.getDesc().hasImplicitDefOfPhysReg(X86::RIP)) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Positions can't safely be outlined. if (MI.isPosition()) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; // Make sure none of the operands of this instruction do anything tricky. for (const MachineOperand &MOP : MI.operands()) if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() || MOP.isTargetIndex()) - return MachineOutlinerInstrType::Illegal; + return outliner::InstrType::Illegal; - return MachineOutlinerInstrType::Legal; + return outliner::InstrType::Legal; } void X86InstrInfo::insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) + const outliner::TargetCostInfo &TCI) const { // If we're a tail call, we already have a return, so don't do anything. - if (MInfo.FrameConstructionID == MachineOutlinerTailCall) + if (TCI.FrameConstructionID == MachineOutlinerTailCall) return; // We're a normal call, so our sequence doesn't have a return instruction. @@ -11265,16 +11263,16 @@ void X86InstrInfo::insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) + const outliner::TargetCostInfo &TCI) const {} MachineBasicBlock::iterator X86InstrInfo::insertOutlinedCall(Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It, MachineFunction &MF, - const MachineOutlinerInfo &MInfo) const { + const outliner::TargetCostInfo &TCI) const { // Is it a tail call? - if (MInfo.CallConstructionID == MachineOutlinerTailCall) { + if (TCI.CallConstructionID == MachineOutlinerTailCall) { // Yes, just insert a JMP. It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(X86::JMP_1))