Coverage Report

Created: 2018-07-19 03:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/MachineOutliner.h
Line
Count
Source (jump to first uncovered line)
1
//===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
///
10
/// \file
11
/// Contains all data structures shared between the outliner implemented in
12
/// MachineOutliner.cpp and target implementations of the outliner.
13
///
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_MACHINEOUTLINER_H
17
#define LLVM_MACHINEOUTLINER_H
18
19
#include "llvm/CodeGen/LiveRegUnits.h"
20
#include "llvm/CodeGen/MachineFunction.h"
21
#include "llvm/CodeGen/TargetRegisterInfo.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
/// Describes the number of instructions that it will take to call and
36
/// construct a frame for a given outlining candidate.
37
struct TargetCostInfo {
38
  /// Represents the size of a sequence in bytes. (Some instructions vary
39
  /// widely in size, so just counting the instructions isn't very useful.)
40
  unsigned SequenceSize;
41
42
  /// Number of instructions to call an outlined function for this candidate.
43
  unsigned CallOverhead;
44
45
  /// Number of instructions to construct an outlined function frame
46
  /// for this candidate.
47
  unsigned FrameOverhead;
48
49
  /// Represents the specific instructions that must be emitted to
50
  /// construct a call to this candidate.
51
  unsigned CallConstructionID;
52
53
  /// Represents the specific instructions that must be emitted to
54
  /// construct a frame for this candidate's outlined function.
55
  unsigned FrameConstructionID;
56
57
318
  TargetCostInfo() {}
58
  TargetCostInfo(unsigned SequenceSize, unsigned CallOverhead,
59
                 unsigned FrameOverhead, unsigned CallConstructionID,
60
                 unsigned FrameConstructionID)
61
      : SequenceSize(SequenceSize), CallOverhead(CallOverhead),
62
        FrameOverhead(FrameOverhead), CallConstructionID(CallConstructionID),
63
133
        FrameConstructionID(FrameConstructionID) {}
64
};
65
66
/// An individual sequence of instructions to be replaced with a call to
67
/// an outlined function.
68
struct Candidate {
69
private:
70
  /// The start index of this \p Candidate in the instruction list.
71
  unsigned StartIdx;
72
73
  /// The number of instructions in this \p Candidate.
74
  unsigned Len;
75
76
  // The first instruction in this \p Candidate.
77
  MachineBasicBlock::iterator FirstInst;
78
79
  // The last instruction in this \p Candidate.
80
  MachineBasicBlock::iterator LastInst;
81
82
  // The basic block that contains this Candidate.
83
  MachineBasicBlock *MBB;
84
85
public:
86
  /// The index of this \p Candidate's \p OutlinedFunction in the list of
87
  /// \p OutlinedFunctions.
88
  unsigned FunctionIdx;
89
90
  /// Set to false if the candidate overlapped with another candidate.
91
  bool InCandidateList = true;
92
93
  /// Contains all target-specific information for this \p Candidate.
94
  TargetCostInfo TCI;
95
96
  /// Contains physical register liveness information for the MBB containing
97
  /// this \p Candidate.
98
  ///
99
  /// This is optionally used by the target to calculate more fine-grained
100
  /// cost model information.
101
  LiveRegUnits LRU;
102
103
  /// Return the number of instructions in this Candidate.
104
0
  unsigned getLength() const { return Len; }
105
106
  /// Return the start index of this candidate.
107
1.56k
  unsigned getStartIdx() const { return StartIdx; }
108
109
  /// Return the end index of this candidate.
110
219
  unsigned getEndIdx() const { return StartIdx + Len - 1; }
111
112
649
  MachineBasicBlock::iterator &front() { return FirstInst; }
113
624
  MachineBasicBlock::iterator &back() { return LastInst; }
114
161
  MachineFunction *getMF() const { return MBB->getParent(); }
115
70
  MachineBasicBlock *getMBB() const { return MBB; }
116
117
  /// The number of instructions that would be saved by outlining every
118
  /// candidate of this type.
119
  ///
120
  /// This is a fixed value which is not updated during the candidate pruning
121
  /// process. It is only used for deciding which candidate to keep if two
122
  /// candidates overlap. The true benefit is stored in the OutlinedFunction
123
  /// for some given candidate.
124
  unsigned Benefit = 0;
125
126
  Candidate(unsigned StartIdx, unsigned Len,
127
            MachineBasicBlock::iterator &FirstInst,
128
            MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
129
            unsigned FunctionIdx)
130
      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
131
318
        MBB(MBB), FunctionIdx(FunctionIdx) {}
132
  Candidate() {}
133
134
  /// Used to ensure that \p Candidates are outlined in an order that
135
  /// preserves the start and end indices of other \p Candidates.
136
429
  bool operator<(const Candidate &RHS) const {
137
429
    return getStartIdx() > RHS.getStartIdx();
138
429
  }
139
140
  /// Compute the registers that are live across this Candidate.
141
  /// Used by targets that need this information for cost model calculation.
142
  /// If a target does not need this information, then this should not be
143
  /// called.
144
266
  void initLRU(const TargetRegisterInfo &TRI) {
145
266
    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
146
266
           "Candidate's Machine Function must track liveness");
147
266
    LRU.init(TRI);
148
266
    LRU.addLiveOuts(*MBB);
149
266
150
266
    // Compute liveness from the end of the block up to the beginning of the
151
266
    // outlining candidate.
152
266
    std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
153
2.67k
                  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
154
266
  }
155
};
156
157
/// The information necessary to create an outlined function for some
158
/// class of candidate.
159
struct OutlinedFunction {
160
161
private:
162
  /// The number of candidates for this \p OutlinedFunction.
163
  unsigned OccurrenceCount = 0;
164
165
public:
166
  std::vector<std::shared_ptr<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
  /// A number assigned to this function which appears at the end of its name.
173
  unsigned Name;
174
175
  /// The sequence of integers corresponding to the instructions in this
176
  /// function.
177
  std::vector<unsigned> Sequence;
178
179
  /// Contains all target-specific information for this \p OutlinedFunction.
180
  TargetCostInfo TCI;
181
182
  /// Return the number of candidates for this \p OutlinedFunction.
183
133
  unsigned getOccurrenceCount() { return OccurrenceCount; }
184
185
  /// Decrement the occurrence count of this OutlinedFunction and return the
186
  /// new count.
187
110
  unsigned decrement() {
188
110
    assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
189
110
    OccurrenceCount--;
190
110
    return getOccurrenceCount();
191
110
  }
192
193
  /// Return the number of bytes it would take to outline this
194
  /// function.
195
450
  unsigned getOutliningCost() {
196
450
    return (OccurrenceCount * TCI.CallOverhead) + TCI.SequenceSize +
197
450
           TCI.FrameOverhead;
198
450
  }
199
200
  /// Return the size in bytes of the unoutlined sequences.
201
450
  unsigned getNotOutlinedCost() { return OccurrenceCount * TCI.SequenceSize; }
202
203
  /// Return the number of instructions that would be saved by outlining
204
  /// this function.
205
436
  unsigned getBenefit() {
206
436
    unsigned NotOutlinedCost = getNotOutlinedCost();
207
436
    unsigned OutlinedCost = getOutliningCost();
208
436
    return (NotOutlinedCost < OutlinedCost) ? 
092
209
436
                                            : 
NotOutlinedCost - OutlinedCost344
;
210
436
  }
211
212
  OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
213
                   const std::vector<unsigned> &Sequence, TargetCostInfo &TCI)
214
      : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
215
133
        TCI(TCI) {}
216
};
217
} // namespace outliner
218
} // namespace llvm
219
220
#endif