Coverage Report

Created: 2019-02-20 07:29

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/MachineOutliner.h
Line
Count
Source
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_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
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
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
87
  /// Return the number of instructions in this Candidate.
88
46
  unsigned getLength() const { return Len; }
89
90
  /// Return the start index of this candidate.
91
1.13k
  unsigned getStartIdx() const { return StartIdx; }
92
93
  /// Return the end index of this candidate.
94
793
  unsigned getEndIdx() const { return StartIdx + Len - 1; }
95
96
  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
97
  /// CO respectively.
98
636
  void setCallInfo(unsigned CID, unsigned CO) {
99
636
    CallConstructionID = CID;
100
636
    CallOverhead = CO;
101
636
  }
102
103
  /// Returns the call overhead of this candidate if it is in the list.
104
3.33k
  unsigned getCallOverhead() const { return CallOverhead; }
105
106
1.54k
  MachineBasicBlock::iterator &front() { return FirstInst; }
107
1.56k
  MachineBasicBlock::iterator &back() { return LastInst; }
108
1.38k
  MachineFunction *getMF() const { return MBB->getParent(); }
109
135
  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,
123
            unsigned FunctionIdx, unsigned Flags)
124
      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
125
657
        MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
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
371
  void initLRU(const TargetRegisterInfo &TRI) {
139
371
    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
140
371
           "Candidate's Machine Function must track liveness");
141
371
    // Only initialize once.
142
371
    if (LRUWasSet)
143
35
      return;
144
336
    LRUWasSet = true;
145
336
    LRU.init(TRI);
146
336
    LRU.addLiveOuts(*MBB);
147
336
148
336
    // Compute liveness from the end of the block up to the beginning of the
149
336
    // outlining candidate.
150
336
    std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
151
2.42k
                  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
152
336
153
336
    // Walk over the sequence itself and figure out which registers were used
154
336
    // in the sequence.
155
336
    UsedInSequence.init(TRI);
156
336
    std::for_each(front(), std::next(back()),
157
1.29k
                  [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
158
336
  }
159
};
160
161
/// The information necessary to create an outlined function for some
162
/// class of candidate.
163
struct OutlinedFunction {
164
165
public:
166
  std::vector<Candidate> Candidates;
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
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.
183
1.54k
  unsigned getOccurrenceCount() const { return Candidates.size(); }
184
185
  /// Return the number of bytes it would take to outline this
186
  /// function.
187
1.49k
  unsigned getOutliningCost() const {
188
1.49k
    unsigned CallOverhead = 0;
189
1.49k
    for (const Candidate &C : Candidates)
190
3.33k
      CallOverhead += C.getCallOverhead();
191
1.49k
    return CallOverhead + SequenceSize + FrameOverhead;
192
1.49k
  }
193
194
  /// Return the size in bytes of the unoutlined sequences.
195
1.49k
  unsigned getNotOutlinedCost() const {
196
1.49k
    return getOccurrenceCount() * SequenceSize;
197
1.49k
  }
198
199
  /// Return the number of instructions that would be saved by outlining
200
  /// this function.
201
1.48k
  unsigned getBenefit() const {
202
1.48k
    unsigned NotOutlinedCost = getNotOutlinedCost();
203
1.48k
    unsigned OutlinedCost = getOutliningCost();
204
1.48k
    return (NotOutlinedCost < OutlinedCost) ? 
0217
205
1.48k
                                            : 
NotOutlinedCost - OutlinedCost1.27k
;
206
1.48k
  }
207
208
  /// Return the number of instructions in this sequence.
209
46
  unsigned getNumInstrs() const { return Candidates[0].getLength(); }
210
211
  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
212
                   unsigned FrameOverhead, unsigned FrameConstructionID)
213
      : Candidates(Candidates), SequenceSize(SequenceSize),
214
259
        FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) {
215
259
    const unsigned B = getBenefit();
216
259
    for (Candidate &C : Candidates)
217
632
      C.Benefit = B;
218
259
  }
219
220
7
  OutlinedFunction() {}
221
};
222
} // namespace outliner
223
} // namespace llvm
224
225
#endif