| //===---- 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/LiveRegUnits.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| |
| namespace llvm { |
| namespace outliner { |
| |
| /// 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; |
| |
| /// Contains physical register liveness information for the MBB containing |
| /// this \p Candidate. |
| /// |
| /// This is optionally used by the target to calculate more fine-grained |
| /// cost model information. |
| LiveRegUnits LRU; |
| |
| /// 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) {} |
| 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(); |
| } |
| |
| /// Compute the registers that are live across this Candidate. |
| /// Used by targets that need this information for cost model calculation. |
| /// If a target does not need this information, then this should not be |
| /// called. |
| void initLRU(const TargetRegisterInfo &TRI) { |
| assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
| "Candidate's Machine Function must track liveness"); |
| LRU.init(TRI); |
| LRU.addLiveOuts(*MBB); |
| |
| // Compute liveness from the end of the block up to the beginning of the |
| // outlining candidate. |
| std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(), |
| [this](MachineInstr &MI) { LRU.stepBackward(MI); }); |
| } |
| }; |
| |
| /// The information necessary to create an outlined function for some |
| /// class of candidate. |
| struct OutlinedFunction { |
| |
| private: |
| /// The number of candidates for this \p OutlinedFunction. |
| unsigned OccurrenceCount = 0; |
| |
| public: |
| std::vector<std::shared_ptr<Candidate>> Candidates; |
| |
| /// The actual outlined function created. |
| /// This is initialized after we go through and create the actual function. |
| MachineFunction *MF = nullptr; |
| |
| /// A number assigned to this function which appears at the end of its name. |
| unsigned Name; |
| |
| /// The sequence of integers corresponding to the instructions in this |
| /// function. |
| std::vector<unsigned> 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<unsigned> &Sequence, TargetCostInfo &TCI) |
| : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence), |
| TCI(TCI) {} |
| }; |
| } // namespace outliner |
| } // namespace llvm |
| |
| #endif |