Coverage Report

Created: 2018-11-16 02:38

/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
//                     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
#include "llvm/CodeGen/LivePhysRegs.h"
23
24
namespace llvm {
25
namespace outliner {
26
27
/// Represents how an instruction should be mapped by the outliner.
28
/// \p Legal instructions are those which are safe to outline.
29
/// \p LegalTerminator instructions are safe to outline, but only as the
30
/// last instruction in a sequence.
31
/// \p Illegal instructions are those which cannot be outlined.
32
/// \p Invisible instructions are instructions which can be outlined, but
33
/// shouldn't actually impact the outlining result.
34
enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
35
36
/// An individual sequence of instructions to be replaced with a call to
37
/// an outlined function.
38
struct Candidate {
39
private:
40
  /// The start index of this \p Candidate in the instruction list.
41
  unsigned StartIdx;
42
43
  /// The number of instructions in this \p Candidate.
44
  unsigned Len;
45
46
  // The first instruction in this \p Candidate.
47
  MachineBasicBlock::iterator FirstInst;
48
49
  // The last instruction in this \p Candidate.
50
  MachineBasicBlock::iterator LastInst;
51
52
  // The basic block that contains this Candidate.
53
  MachineBasicBlock *MBB;
54
55
  /// Cost of calling an outlined function from this point as defined by the
56
  /// target.
57
  unsigned CallOverhead;
58
59
public:
60
  /// The index of this \p Candidate's \p OutlinedFunction in the list of
61
  /// \p OutlinedFunctions.
62
  unsigned FunctionIdx;
63
64
  /// Set to false if the candidate overlapped with another candidate.
65
  bool InCandidateList = true;
66
67
  /// Identifier denoting the instructions to emit to call an outlined function
68
  /// from this point. Defined by the target.
69
  unsigned CallConstructionID;
70
71
  /// Contains physical register liveness information for the MBB containing
72
  /// this \p Candidate.
73
  ///
74
  /// This is optionally used by the target to calculate more fine-grained
75
  /// cost model information.
76
  LiveRegUnits LRU;
77
78
  /// Contains the accumulated register liveness information for the
79
  /// instructions in this \p Candidate.
80
  ///
81
  /// This is optionally used by the target to determine which registers have
82
  /// been used across the sequence.
83
  LiveRegUnits UsedInSequence;
84
85
  /// Target-specific flags for this Candidate's MBB.
86
  unsigned Flags = 0x0;
87
88
  /// True if initLRU has been called on this Candidate.
89
  bool LRUWasSet = false;
90
91
  /// Return the number of instructions in this Candidate.
92
  unsigned getLength() const { return Len; }
93
94
  /// Return the start index of this candidate.
95
2.47k
  unsigned getStartIdx() const { return StartIdx; }
96
97
  /// Return the end index of this candidate.
98
289
  unsigned getEndIdx() const { return StartIdx + Len - 1; }
99
100
  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
101
  /// CO respectively.
102
503
  void setCallInfo(unsigned CID, unsigned CO) {
103
503
    CallConstructionID = CID;
104
503
    CallOverhead = CO;
105
503
  }
106
107
  /// Returns the call overhead of this candidate if it is in the list.
108
2.44k
  unsigned getCallOverhead() const {
109
2.44k
    return InCandidateList ? 
CallOverhead2.28k
:
0159
;
110
2.44k
  }
111
112
1.23k
  MachineBasicBlock::iterator &front() { return FirstInst; }
113
1.12k
  MachineBasicBlock::iterator &back() { return LastInst; }
114
1.25k
  MachineFunction *getMF() const { return MBB->getParent(); }
115
465
  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, unsigned Flags)
130
      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
131
516
        MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
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
754
  bool operator<(const Candidate &RHS) const {
137
754
    return getStartIdx() > RHS.getStartIdx();
138
754
  }
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
560
  void initLRU(const TargetRegisterInfo &TRI) {
145
560
    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
146
560
           "Candidate's Machine Function must track liveness");
147
560
    // Only initialize once.
148
560
    if (LRUWasSet)
149
184
      return;
150
376
    LRUWasSet = true;
151
376
    LRU.init(TRI);
152
376
    LRU.addLiveOuts(*MBB);
153
376
154
376
    // Compute liveness from the end of the block up to the beginning of the
155
376
    // outlining candidate.
156
376
    std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
157
3.71k
                  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
158
376
159
376
    // Walk over the sequence itself and figure out which registers were used
160
376
    // in the sequence.
161
376
    UsedInSequence.init(TRI);
162
376
    std::for_each(front(), std::next(back()),
163
1.93k
                  [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
164
376
  }
165
};
166
167
/// The information necessary to create an outlined function for some
168
/// class of candidate.
169
struct OutlinedFunction {
170
171
private:
172
  /// The number of candidates for this \p OutlinedFunction.
173
  unsigned OccurrenceCount = 0;
174
175
public:
176
  std::vector<std::shared_ptr<Candidate>> Candidates;
177
178
  /// The actual outlined function created.
179
  /// This is initialized after we go through and create the actual function.
180
  MachineFunction *MF = nullptr;
181
182
  /// The sequence of integers corresponding to the instructions in this
183
  /// function.
184
  std::vector<unsigned> Sequence;
185
186
  /// Represents the size of a sequence in bytes. (Some instructions vary
187
  /// widely in size, so just counting the instructions isn't very useful.)
188
  unsigned SequenceSize;
189
190
  /// Target-defined overhead of constructing a frame for this function.
191
  unsigned FrameOverhead;
192
193
  /// Target-defined identifier for constructing a frame for this function.
194
  unsigned FrameConstructionID;
195
196
  /// Return the number of candidates for this \p OutlinedFunction.
197
206
  unsigned getOccurrenceCount() { return OccurrenceCount; }
198
199
  /// Decrement the occurrence count of this OutlinedFunction and return the
200
  /// new count.
201
172
  unsigned decrement() {
202
172
    assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
203
172
    OccurrenceCount--;
204
172
    return getOccurrenceCount();
205
172
  }
206
207
  /// Return the number of bytes it would take to outline this
208
  /// function.
209
908
  unsigned getOutliningCost() {
210
908
    unsigned CallOverhead = 0;
211
908
    for (std::shared_ptr<Candidate> &C : Candidates)
212
2.44k
      CallOverhead += C->getCallOverhead();
213
908
    return CallOverhead + SequenceSize + FrameOverhead;
214
908
  }
215
216
  /// Return the size in bytes of the unoutlined sequences.
217
908
  unsigned getNotOutlinedCost() { return OccurrenceCount * SequenceSize; }
218
219
  /// Return the number of instructions that would be saved by outlining
220
  /// this function.
221
890
  unsigned getBenefit() {
222
890
    unsigned NotOutlinedCost = getNotOutlinedCost();
223
890
    unsigned OutlinedCost = getOutliningCost();
224
890
    return (NotOutlinedCost < OutlinedCost) ? 
0221
225
890
                                            : 
NotOutlinedCost - OutlinedCost669
;
226
890
  }
227
228
  OutlinedFunction(std::vector<Candidate> &Cands,
229
                   unsigned SequenceSize, unsigned FrameOverhead,
230
                   unsigned FrameConstructionID)
231
      : SequenceSize(SequenceSize), FrameOverhead(FrameOverhead),
232
211
        FrameConstructionID(FrameConstructionID) {
233
211
    OccurrenceCount = Cands.size();
234
211
    for (Candidate &C : Cands)
235
503
      Candidates.push_back(std::make_shared<outliner::Candidate>(C));
236
211
237
211
    unsigned B = getBenefit();
238
211
    for (std::shared_ptr<Candidate> &C : Candidates)
239
503
      C->Benefit = B;
240
211
  }
241
242
5
  OutlinedFunction() {}
243
};
244
} // namespace outliner
245
} // namespace llvm
246
247
#endif