| //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// Contains all data structures shared between the outliner implemented in |
| /// MachineOutliner.cpp and target implementations of the outliner. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CODEGEN_MACHINEOUTLINER_H |
| #define LLVM_CODEGEN_MACHINEOUTLINER_H |
| |
| #include "llvm/CodeGen/LiveRegUnits.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include <initializer_list> |
| |
| 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 }; |
| |
| /// 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 = 0; |
| |
| /// The number of instructions in this \p Candidate. |
| unsigned Len = 0; |
| |
| // 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 = nullptr; |
| |
| /// Cost of calling an outlined function from this point as defined by the |
| /// target. |
| unsigned CallOverhead = 0; |
| |
| /// Liveness information for this Candidate. Tracks from the end of the |
| /// block containing this Candidate to the beginning of its sequence. |
| /// |
| /// Optional. Can be used to fine-tune the cost model, or fine-tune legality |
| /// decisions. |
| LiveRegUnits FromEndOfBlockToStartOfSeq; |
| |
| /// Liveness information restricted to this Candidate's instruction sequence. |
| /// |
| /// Optional. Can be used to fine-tune the cost model, or fine-tune legality |
| /// decisions. |
| LiveRegUnits InSeq; |
| |
| /// True if FromEndOfBlockToStartOfSeq has been initialized. |
| bool FromEndOfBlockToStartOfSeqWasSet = false; |
| |
| /// True if InSeq has been initialized. |
| bool InSeqWasSet = false; |
| |
| /// Populate FromEndOfBlockToStartOfSeq with liveness information. |
| void initFromEndOfBlockToStartOfSeq(const TargetRegisterInfo &TRI) { |
| assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
| "Candidate's Machine Function must track liveness"); |
| // Only initialize once. |
| if (FromEndOfBlockToStartOfSeqWasSet) |
| return; |
| FromEndOfBlockToStartOfSeqWasSet = true; |
| FromEndOfBlockToStartOfSeq.init(TRI); |
| FromEndOfBlockToStartOfSeq.addLiveOuts(*MBB); |
| // Compute liveness from the end of the block up to the beginning of the |
| // outlining candidate. |
| for (auto &MI : make_range(MBB->rbegin(), |
| (MachineBasicBlock::reverse_iterator)front())) |
| FromEndOfBlockToStartOfSeq.stepBackward(MI); |
| } |
| |
| /// Populate InSeq with liveness information. |
| void initInSeq(const TargetRegisterInfo &TRI) { |
| assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
| "Candidate's Machine Function must track liveness"); |
| // Only initialize once. |
| if (InSeqWasSet) |
| return; |
| InSeqWasSet = true; |
| InSeq.init(TRI); |
| for (auto &MI : make_range(front(), std::next(back()))) |
| InSeq.accumulate(MI); |
| } |
| |
| public: |
| /// The index of this \p Candidate's \p OutlinedFunction in the list of |
| /// \p OutlinedFunctions. |
| unsigned FunctionIdx = 0; |
| |
| /// Identifier denoting the instructions to emit to call an outlined function |
| /// from this point. Defined by the target. |
| unsigned CallConstructionID = 0; |
| |
| /// Target-specific flags for this Candidate's MBB. |
| unsigned Flags = 0x0; |
| |
| /// 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; } |
| |
| /// Set the CallConstructionID and CallOverhead of this candidate to CID and |
| /// CO respectively. |
| void setCallInfo(unsigned CID, unsigned CO) { |
| CallConstructionID = CID; |
| CallOverhead = CO; |
| } |
| |
| /// Returns the call overhead of this candidate if it is in the list. |
| unsigned getCallOverhead() const { return CallOverhead; } |
| |
| MachineBasicBlock::iterator &front() { return FirstInst; } |
| MachineBasicBlock::iterator &back() { return LastInst; } |
| MachineFunction *getMF() const { return MBB->getParent(); } |
| MachineBasicBlock *getMBB() const { return MBB; } |
| |
| /// \returns True if \p Reg is available from the end of the block to the |
| /// beginning of the sequence. |
| /// |
| /// This query considers the following range: |
| /// |
| /// in_seq_1 |
| /// in_seq_2 |
| /// ... |
| /// in_seq_n |
| /// not_in_seq_1 |
| /// ... |
| /// <end of block> |
| bool isAvailableAcrossAndOutOfSeq(Register Reg, |
| const TargetRegisterInfo &TRI) { |
| if (!FromEndOfBlockToStartOfSeqWasSet) |
| initFromEndOfBlockToStartOfSeq(TRI); |
| return FromEndOfBlockToStartOfSeq.available(Reg); |
| } |
| |
| /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register |
| /// in \p Regs. |
| bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs, |
| const TargetRegisterInfo &TRI) { |
| if (!FromEndOfBlockToStartOfSeqWasSet) |
| initFromEndOfBlockToStartOfSeq(TRI); |
| return any_of(Regs, [&](Register Reg) { |
| return !FromEndOfBlockToStartOfSeq.available(Reg); |
| }); |
| } |
| |
| /// \returns True if \p Reg is available within the sequence itself. |
| /// |
| /// This query considers the following range: |
| /// |
| /// in_seq_1 |
| /// in_seq_2 |
| /// ... |
| /// in_seq_n |
| bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI) { |
| if (!InSeqWasSet) |
| initInSeq(TRI); |
| return InSeq.available(Reg); |
| } |
| |
| /// 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, unsigned Flags) |
| : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), |
| MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} |
| Candidate() = default; |
| |
| /// 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 { |
| |
| public: |
| std::vector<Candidate> Candidates; |
| |
| /// The actual outlined function created. |
| /// This is initialized after we go through and create the actual function. |
| MachineFunction *MF = nullptr; |
| |
| /// 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 = 0; |
| |
| /// Target-defined overhead of constructing a frame for this function. |
| unsigned FrameOverhead = 0; |
| |
| /// Target-defined identifier for constructing a frame for this function. |
| unsigned FrameConstructionID = 0; |
| |
| /// Return the number of candidates for this \p OutlinedFunction. |
| unsigned getOccurrenceCount() const { return Candidates.size(); } |
| |
| /// Return the number of bytes it would take to outline this |
| /// function. |
| unsigned getOutliningCost() const { |
| unsigned CallOverhead = 0; |
| for (const Candidate &C : Candidates) |
| CallOverhead += C.getCallOverhead(); |
| return CallOverhead + SequenceSize + FrameOverhead; |
| } |
| |
| /// Return the size in bytes of the unoutlined sequences. |
| unsigned getNotOutlinedCost() const { |
| return getOccurrenceCount() * SequenceSize; |
| } |
| |
| /// Return the number of instructions that would be saved by outlining |
| /// this function. |
| unsigned getBenefit() const { |
| unsigned NotOutlinedCost = getNotOutlinedCost(); |
| unsigned OutlinedCost = getOutliningCost(); |
| return (NotOutlinedCost < OutlinedCost) ? 0 |
| : NotOutlinedCost - OutlinedCost; |
| } |
| |
| /// Return the number of instructions in this sequence. |
| unsigned getNumInstrs() const { return Candidates[0].getLength(); } |
| |
| OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize, |
| unsigned FrameOverhead, unsigned FrameConstructionID) |
| : Candidates(Candidates), SequenceSize(SequenceSize), |
| FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) { |
| const unsigned B = getBenefit(); |
| for (Candidate &C : Candidates) |
| C.Benefit = B; |
| } |
| |
| OutlinedFunction() = default; |
| }; |
| } // namespace outliner |
| } // namespace llvm |
| |
| #endif |