Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 1 | //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===// |
| 2 | // |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// Contains all data structures shared between the outliner implemented in |
| 11 | /// MachineOutliner.cpp and target implementations of the outliner. |
| 12 | /// |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef LLVM_MACHINEOUTLINER_H |
| 16 | #define LLVM_MACHINEOUTLINER_H |
| 17 | |
| 18 | #include "llvm/CodeGen/LiveRegUnits.h" |
| 19 | #include "llvm/CodeGen/MachineFunction.h" |
| 20 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
| 21 | #include "llvm/CodeGen/LivePhysRegs.h" |
| 22 | |
| 23 | namespace llvm { |
| 24 | namespace outliner { |
| 25 | |
| 26 | /// Represents how an instruction should be mapped by the outliner. |
| 27 | /// \p Legal instructions are those which are safe to outline. |
| 28 | /// \p LegalTerminator instructions are safe to outline, but only as the |
| 29 | /// last instruction in a sequence. |
| 30 | /// \p Illegal instructions are those which cannot be outlined. |
| 31 | /// \p Invisible instructions are instructions which can be outlined, but |
| 32 | /// shouldn't actually impact the outlining result. |
| 33 | enum InstrType { Legal, LegalTerminator, Illegal, Invisible }; |
| 34 | |
| 35 | /// An individual sequence of instructions to be replaced with a call to |
| 36 | /// an outlined function. |
| 37 | struct Candidate { |
| 38 | private: |
| 39 | /// The start index of this \p Candidate in the instruction list. |
| 40 | unsigned StartIdx; |
| 41 | |
| 42 | /// The number of instructions in this \p Candidate. |
| 43 | unsigned Len; |
| 44 | |
| 45 | // The first instruction in this \p Candidate. |
| 46 | MachineBasicBlock::iterator FirstInst; |
| 47 | |
| 48 | // The last instruction in this \p Candidate. |
| 49 | MachineBasicBlock::iterator LastInst; |
| 50 | |
| 51 | // The basic block that contains this Candidate. |
| 52 | MachineBasicBlock *MBB; |
| 53 | |
| 54 | /// Cost of calling an outlined function from this point as defined by the |
| 55 | /// target. |
| 56 | unsigned CallOverhead; |
| 57 | |
| 58 | public: |
| 59 | /// The index of this \p Candidate's \p OutlinedFunction in the list of |
| 60 | /// \p OutlinedFunctions. |
| 61 | unsigned FunctionIdx; |
| 62 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 63 | /// Identifier denoting the instructions to emit to call an outlined function |
| 64 | /// from this point. Defined by the target. |
| 65 | unsigned CallConstructionID; |
| 66 | |
| 67 | /// Contains physical register liveness information for the MBB containing |
| 68 | /// this \p Candidate. |
| 69 | /// |
| 70 | /// This is optionally used by the target to calculate more fine-grained |
| 71 | /// cost model information. |
| 72 | LiveRegUnits LRU; |
| 73 | |
| 74 | /// Contains the accumulated register liveness information for the |
| 75 | /// instructions in this \p Candidate. |
| 76 | /// |
| 77 | /// This is optionally used by the target to determine which registers have |
| 78 | /// been used across the sequence. |
| 79 | LiveRegUnits UsedInSequence; |
| 80 | |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 81 | /// Target-specific flags for this Candidate's MBB. |
| 82 | unsigned Flags = 0x0; |
| 83 | |
| 84 | /// True if initLRU has been called on this Candidate. |
| 85 | bool LRUWasSet = false; |
| 86 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 87 | /// Return the number of instructions in this Candidate. |
| 88 | unsigned getLength() const { return Len; } |
| 89 | |
| 90 | /// Return the start index of this candidate. |
| 91 | unsigned getStartIdx() const { return StartIdx; } |
| 92 | |
| 93 | /// Return the end index of this candidate. |
| 94 | unsigned getEndIdx() const { return StartIdx + Len - 1; } |
| 95 | |
| 96 | /// Set the CallConstructionID and CallOverhead of this candidate to CID and |
| 97 | /// CO respectively. |
| 98 | void setCallInfo(unsigned CID, unsigned CO) { |
| 99 | CallConstructionID = CID; |
| 100 | CallOverhead = CO; |
| 101 | } |
| 102 | |
| 103 | /// Returns the call overhead of this candidate if it is in the list. |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 104 | unsigned getCallOverhead() const { return CallOverhead; } |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 105 | |
| 106 | MachineBasicBlock::iterator &front() { return FirstInst; } |
| 107 | MachineBasicBlock::iterator &back() { return LastInst; } |
| 108 | MachineFunction *getMF() const { return MBB->getParent(); } |
| 109 | MachineBasicBlock *getMBB() const { return MBB; } |
| 110 | |
| 111 | /// The number of instructions that would be saved by outlining every |
| 112 | /// candidate of this type. |
| 113 | /// |
| 114 | /// This is a fixed value which is not updated during the candidate pruning |
| 115 | /// process. It is only used for deciding which candidate to keep if two |
| 116 | /// candidates overlap. The true benefit is stored in the OutlinedFunction |
| 117 | /// for some given candidate. |
| 118 | unsigned Benefit = 0; |
| 119 | |
| 120 | Candidate(unsigned StartIdx, unsigned Len, |
| 121 | MachineBasicBlock::iterator &FirstInst, |
| 122 | MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 123 | unsigned FunctionIdx, unsigned Flags) |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 124 | : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 125 | MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 126 | Candidate() {} |
| 127 | |
| 128 | /// Used to ensure that \p Candidates are outlined in an order that |
| 129 | /// preserves the start and end indices of other \p Candidates. |
| 130 | bool operator<(const Candidate &RHS) const { |
| 131 | return getStartIdx() > RHS.getStartIdx(); |
| 132 | } |
| 133 | |
| 134 | /// Compute the registers that are live across this Candidate. |
| 135 | /// Used by targets that need this information for cost model calculation. |
| 136 | /// If a target does not need this information, then this should not be |
| 137 | /// called. |
| 138 | void initLRU(const TargetRegisterInfo &TRI) { |
| 139 | assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
| 140 | "Candidate's Machine Function must track liveness"); |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 141 | // Only initialize once. |
| 142 | if (LRUWasSet) |
| 143 | return; |
| 144 | LRUWasSet = true; |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 145 | LRU.init(TRI); |
| 146 | LRU.addLiveOuts(*MBB); |
| 147 | |
| 148 | // Compute liveness from the end of the block up to the beginning of the |
| 149 | // outlining candidate. |
| 150 | std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(), |
| 151 | [this](MachineInstr &MI) { LRU.stepBackward(MI); }); |
| 152 | |
| 153 | // Walk over the sequence itself and figure out which registers were used |
| 154 | // in the sequence. |
| 155 | UsedInSequence.init(TRI); |
| 156 | std::for_each(front(), std::next(back()), |
| 157 | [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); }); |
| 158 | } |
| 159 | }; |
| 160 | |
| 161 | /// The information necessary to create an outlined function for some |
| 162 | /// class of candidate. |
| 163 | struct OutlinedFunction { |
| 164 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 165 | public: |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 166 | std::vector<Candidate> Candidates; |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 167 | |
| 168 | /// The actual outlined function created. |
| 169 | /// This is initialized after we go through and create the actual function. |
| 170 | MachineFunction *MF = nullptr; |
| 171 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 172 | /// Represents the size of a sequence in bytes. (Some instructions vary |
| 173 | /// widely in size, so just counting the instructions isn't very useful.) |
| 174 | unsigned SequenceSize; |
| 175 | |
| 176 | /// Target-defined overhead of constructing a frame for this function. |
| 177 | unsigned FrameOverhead; |
| 178 | |
| 179 | /// Target-defined identifier for constructing a frame for this function. |
| 180 | unsigned FrameConstructionID; |
| 181 | |
| 182 | /// Return the number of candidates for this \p OutlinedFunction. |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 183 | unsigned getOccurrenceCount() const { return Candidates.size(); } |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 184 | |
| 185 | /// Return the number of bytes it would take to outline this |
| 186 | /// function. |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 187 | unsigned getOutliningCost() const { |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 188 | unsigned CallOverhead = 0; |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 189 | for (const Candidate &C : Candidates) |
| 190 | CallOverhead += C.getCallOverhead(); |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 191 | return CallOverhead + SequenceSize + FrameOverhead; |
| 192 | } |
| 193 | |
| 194 | /// Return the size in bytes of the unoutlined sequences. |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 195 | unsigned getNotOutlinedCost() const { |
| 196 | return getOccurrenceCount() * SequenceSize; |
| 197 | } |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 198 | |
| 199 | /// Return the number of instructions that would be saved by outlining |
| 200 | /// this function. |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 201 | unsigned getBenefit() const { |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 202 | unsigned NotOutlinedCost = getNotOutlinedCost(); |
| 203 | unsigned OutlinedCost = getOutliningCost(); |
| 204 | return (NotOutlinedCost < OutlinedCost) ? 0 |
| 205 | : NotOutlinedCost - OutlinedCost; |
| 206 | } |
| 207 | |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 208 | /// Return the number of instructions in this sequence. |
| 209 | unsigned getNumInstrs() const { return Candidates[0].getLength(); } |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 210 | |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 211 | OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize, |
| 212 | unsigned FrameOverhead, unsigned FrameConstructionID) |
| 213 | : Candidates(Candidates), SequenceSize(SequenceSize), |
| 214 | FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) { |
| 215 | const unsigned B = getBenefit(); |
| 216 | for (Candidate &C : Candidates) |
| 217 | C.Benefit = B; |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 218 | } |
| 219 | |
| 220 | OutlinedFunction() {} |
| 221 | }; |
| 222 | } // namespace outliner |
| 223 | } // namespace llvm |
| 224 | |
| 225 | #endif |