1//===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
2//
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
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_CODEGEN_MACHINEOUTLINER_H
16#define LLVM_CODEGEN_MACHINEOUTLINER_H
17
18#include "llvm/CodeGen/LiveRegUnits.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include <initializer_list>
22
23namespace llvm {
24namespace 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.
33enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
34
35/// An individual sequence of instructions to be replaced with a call to
36/// an outlined function.
37struct Candidate {
38private:
39  /// The start index of this \p Candidate in the instruction list.
40  unsigned StartIdx = 0;
41
42  /// The number of instructions in this \p Candidate.
43  unsigned Len = 0;
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 = nullptr;
53
54  /// Cost of calling an outlined function from this point as defined by the
55  /// target.
56  unsigned CallOverhead = 0;
57
58  /// Liveness information for this Candidate. Tracks from the end of the
59  /// block containing this Candidate to the beginning of its sequence.
60  ///
61  /// Optional. Can be used to fine-tune the cost model, or fine-tune legality
62  /// decisions.
63  LiveRegUnits FromEndOfBlockToStartOfSeq;
64
65  /// Liveness information restricted to this Candidate's instruction sequence.
66  ///
67  /// Optional. Can be used to fine-tune the cost model, or fine-tune legality
68  /// decisions.
69  LiveRegUnits InSeq;
70
71  /// True if FromEndOfBlockToStartOfSeq has been initialized.
72  bool FromEndOfBlockToStartOfSeqWasSet = false;
73
74  /// True if InSeq has been initialized.
75  bool InSeqWasSet = false;
76
77  /// Populate FromEndOfBlockToStartOfSeq with liveness information.
78  void initFromEndOfBlockToStartOfSeq(const TargetRegisterInfo &TRI) {
79    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
80           "Candidate's Machine Function must track liveness");
81    // Only initialize once.
82    if (FromEndOfBlockToStartOfSeqWasSet)
83      return;
84    FromEndOfBlockToStartOfSeqWasSet = true;
85    FromEndOfBlockToStartOfSeq.init(TRI);
86    FromEndOfBlockToStartOfSeq.addLiveOuts(*MBB);
87    // Compute liveness from the end of the block up to the beginning of the
88    // outlining candidate.
89    for (auto &MI : make_range(MBB->rbegin(),
90                               (MachineBasicBlock::reverse_iterator)front()))
91      FromEndOfBlockToStartOfSeq.stepBackward(MI);
92  }
93
94  /// Populate InSeq with liveness information.
95  void initInSeq(const TargetRegisterInfo &TRI) {
96    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
97           "Candidate's Machine Function must track liveness");
98    // Only initialize once.
99    if (InSeqWasSet)
100      return;
101    InSeqWasSet = true;
102    InSeq.init(TRI);
103    for (auto &MI : make_range(front(), std::next(back())))
104      InSeq.accumulate(MI);
105  }
106
107public:
108  /// The index of this \p Candidate's \p OutlinedFunction in the list of
109  /// \p OutlinedFunctions.
110  unsigned FunctionIdx = 0;
111
112  /// Identifier denoting the instructions to emit to call an outlined function
113  /// from this point. Defined by the target.
114  unsigned CallConstructionID = 0;
115
116  /// Target-specific flags for this Candidate's MBB.
117  unsigned Flags = 0x0;
118
119  /// Return the number of instructions in this Candidate.
120  unsigned getLength() const { return Len; }
121
122  /// Return the start index of this candidate.
123  unsigned getStartIdx() const { return StartIdx; }
124
125  /// Return the end index of this candidate.
126  unsigned getEndIdx() const { return StartIdx + Len - 1; }
127
128  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
129  /// CO respectively.
130  void setCallInfo(unsigned CID, unsigned CO) {
131    CallConstructionID = CID;
132    CallOverhead = CO;
133  }
134
135  /// Returns the call overhead of this candidate if it is in the list.
136  unsigned getCallOverhead() const { return CallOverhead; }
137
138  MachineBasicBlock::iterator &front() { return FirstInst; }
139  MachineBasicBlock::iterator &back() { return LastInst; }
140  MachineFunction *getMF() const { return MBB->getParent(); }
141  MachineBasicBlock *getMBB() const { return MBB; }
142
143  /// \returns True if \p Reg is available from the end of the block to the
144  /// beginning of the sequence.
145  ///
146  /// This query considers the following range:
147  ///
148  /// in_seq_1
149  /// in_seq_2
150  /// ...
151  /// in_seq_n
152  /// not_in_seq_1
153  /// ...
154  /// <end of block>
155  bool isAvailableAcrossAndOutOfSeq(Register Reg,
156                                    const TargetRegisterInfo &TRI) {
157    if (!FromEndOfBlockToStartOfSeqWasSet)
158      initFromEndOfBlockToStartOfSeq(TRI);
159    return FromEndOfBlockToStartOfSeq.available(Reg);
160  }
161
162  /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register
163  /// in \p Regs.
164  bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs,
165                                        const TargetRegisterInfo &TRI) {
166    if (!FromEndOfBlockToStartOfSeqWasSet)
167      initFromEndOfBlockToStartOfSeq(TRI);
168    return any_of(Regs, [&](Register Reg) {
169      return !FromEndOfBlockToStartOfSeq.available(Reg);
170    });
171  }
172
173  /// \returns True if \p Reg is available within the sequence itself.
174  ///
175  /// This query considers the following range:
176  ///
177  /// in_seq_1
178  /// in_seq_2
179  /// ...
180  /// in_seq_n
181  bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI) {
182    if (!InSeqWasSet)
183      initInSeq(TRI);
184    return InSeq.available(Reg);
185  }
186
187  /// The number of instructions that would be saved by outlining every
188  /// candidate of this type.
189  ///
190  /// This is a fixed value which is not updated during the candidate pruning
191  /// process. It is only used for deciding which candidate to keep if two
192  /// candidates overlap. The true benefit is stored in the OutlinedFunction
193  /// for some given candidate.
194  unsigned Benefit = 0;
195
196  Candidate(unsigned StartIdx, unsigned Len,
197            MachineBasicBlock::iterator &FirstInst,
198            MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
199            unsigned FunctionIdx, unsigned Flags)
200      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
201        MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
202  Candidate() = default;
203
204  /// Used to ensure that \p Candidates are outlined in an order that
205  /// preserves the start and end indices of other \p Candidates.
206  bool operator<(const Candidate &RHS) const {
207    return getStartIdx() > RHS.getStartIdx();
208  }
209
210};
211
212/// The information necessary to create an outlined function for some
213/// class of candidate.
214struct OutlinedFunction {
215
216public:
217  std::vector<Candidate> Candidates;
218
219  /// The actual outlined function created.
220  /// This is initialized after we go through and create the actual function.
221  MachineFunction *MF = nullptr;
222
223  /// Represents the size of a sequence in bytes. (Some instructions vary
224  /// widely in size, so just counting the instructions isn't very useful.)
225  unsigned SequenceSize = 0;
226
227  /// Target-defined overhead of constructing a frame for this function.
228  unsigned FrameOverhead = 0;
229
230  /// Target-defined identifier for constructing a frame for this function.
231  unsigned FrameConstructionID = 0;
232
233  /// Return the number of candidates for this \p OutlinedFunction.
234  unsigned getOccurrenceCount() const { return Candidates.size(); }
235
236  /// Return the number of bytes it would take to outline this
237  /// function.
238  unsigned getOutliningCost() const {
239    unsigned CallOverhead = 0;
240    for (const Candidate &C : Candidates)
241      CallOverhead += C.getCallOverhead();
242    return CallOverhead + SequenceSize + FrameOverhead;
243  }
244
245  /// Return the size in bytes of the unoutlined sequences.
246  unsigned getNotOutlinedCost() const {
247    return getOccurrenceCount() * SequenceSize;
248  }
249
250  /// Return the number of instructions that would be saved by outlining
251  /// this function.
252  unsigned getBenefit() const {
253    unsigned NotOutlinedCost = getNotOutlinedCost();
254    unsigned OutlinedCost = getOutliningCost();
255    return (NotOutlinedCost < OutlinedCost) ? 0
256                                            : NotOutlinedCost - OutlinedCost;
257  }
258
259  /// Return the number of instructions in this sequence.
260  unsigned getNumInstrs() const { return Candidates[0].getLength(); }
261
262  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
263                   unsigned FrameOverhead, unsigned FrameConstructionID)
264      : Candidates(Candidates), SequenceSize(SequenceSize),
265        FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) {
266    const unsigned B = getBenefit();
267    for (Candidate &C : Candidates)
268      C.Benefit = B;
269  }
270
271  OutlinedFunction() = default;
272};
273} // namespace outliner
274} // namespace llvm
275
276#endif
277