1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
| //===- ScheduleDFS.h - ILP metric for ScheduleDAGInstrs ---------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Definition of an ILP metric for machine level instruction scheduling.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDULEDFS_H
#define LLVM_CODEGEN_SCHEDULEDFS_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include <cassert>
#include <cstdint>
#include <vector>
namespace llvm {
class raw_ostream;
/// Represent the ILP of the subDAG rooted at a DAG node.
///
/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are
/// valid for all nodes regardless of their subtree membership.
///
/// When computed using bottom-up DFS, this metric assumes that the DAG is a
/// forest of trees with roots at the bottom of the schedule branching upward.
struct ILPValue {
unsigned InstrCount;
/// Length may either correspond to depth or height, depending on direction,
/// and cycles or nodes depending on context.
unsigned Length;
ILPValue(unsigned count, unsigned length):
InstrCount(count), Length(length) {}
// Order by the ILP metric's value.
bool operator<(ILPValue RHS) const {
return (uint64_t)InstrCount * RHS.Length
< (uint64_t)Length * RHS.InstrCount;
}
bool operator>(ILPValue RHS) const {
return RHS < *this;
}
bool operator<=(ILPValue RHS) const {
return (uint64_t)InstrCount * RHS.Length
<= (uint64_t)Length * RHS.InstrCount;
}
bool operator>=(ILPValue RHS) const {
return RHS <= *this;
}
void print(raw_ostream &OS) const;
void dump() const;
};
/// Compute the values of each DAG node for various metrics during DFS.
class SchedDFSResult {
friend class SchedDFSImpl;
static const unsigned InvalidSubtreeID = ~0u;
/// Per-SUnit data computed during DFS for various metrics.
///
/// A node's SubtreeID is set to itself when it is visited to indicate that it
/// is the root of a subtree. Later it is set to its parent to indicate an
/// interior node. Finally, it is set to a representative subtree ID during
/// finalization.
struct NodeData {
unsigned InstrCount = 0;
unsigned SubtreeID = InvalidSubtreeID;
NodeData() = default;
};
/// Per-Subtree data computed during DFS.
struct TreeData {
unsigned ParentTreeID = InvalidSubtreeID;
unsigned SubInstrCount = 0;
TreeData() = default;
};
/// Record a connection between subtrees and the connection level.
struct Connection {
unsigned TreeID;
unsigned Level;
Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
};
bool IsBottomUp;
unsigned SubtreeLimit;
/// DFS results for each SUnit in this DAG.
std::vector<NodeData> DFSNodeData;
// Store per-tree data indexed on tree ID,
SmallVector<TreeData, 16> DFSTreeData;
// For each subtree discovered during DFS, record its connections to other
// subtrees.
std::vector<SmallVector<Connection, 4>> SubtreeConnections;
/// Cache the current connection level of each subtree.
/// This mutable array is updated during scheduling.
std::vector<unsigned> SubtreeConnectLevels;
public:
SchedDFSResult(bool IsBU, unsigned lim)
: IsBottomUp(IsBU), SubtreeLimit(lim) {}
/// Get the node cutoff before subtrees are considered significant.
unsigned getSubtreeLimit() const { return SubtreeLimit; }
/// Return true if this DFSResult is uninitialized.
///
/// resize() initializes DFSResult, while compute() populates it.
bool empty() const { return DFSNodeData.empty(); }
/// Clear the results.
void clear() {
DFSNodeData.clear();
DFSTreeData.clear();
SubtreeConnections.clear();
SubtreeConnectLevels.clear();
}
/// Initialize the result data with the size of the DAG.
void resize(unsigned NumSUnits) {
DFSNodeData.resize(NumSUnits);
}
/// Compute various metrics for the DAG with given roots.
void compute(ArrayRef<SUnit> SUnits);
/// Get the number of instructions in the given subtree and its
/// children.
unsigned getNumInstrs(const SUnit *SU) const {
return DFSNodeData[SU->NodeNum].InstrCount;
}
/// Get the number of instructions in the given subtree not including
/// children.
unsigned getNumSubInstrs(unsigned SubtreeID) const {
return DFSTreeData[SubtreeID].SubInstrCount;
}
/// Get the ILP value for a DAG node.
///
/// A leaf node has an ILP of 1/1.
ILPValue getILP(const SUnit *SU) const {
return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
}
/// The number of subtrees detected in this DAG.
unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
/// Get the ID of the subtree the given DAG node belongs to.
///
/// For convenience, if DFSResults have not been computed yet, give everything
/// tree ID 0.
unsigned getSubtreeID(const SUnit *SU) const {
if (empty())
return 0;
assert(SU->NodeNum < DFSNodeData.size() && "New Node");
return DFSNodeData[SU->NodeNum].SubtreeID;
}
/// Get the connection level of a subtree.
///
/// For bottom-up trees, the connection level is the latency depth (in cycles)
/// of the deepest connection to another subtree.
unsigned getSubtreeLevel(unsigned SubtreeID) const {
return SubtreeConnectLevels[SubtreeID];
}
/// Scheduler callback to update SubtreeConnectLevels when a tree is
/// initially scheduled.
void scheduleTree(unsigned SubtreeID);
};
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
} // end namespace llvm
#endif // LLVM_CODEGEN_SCHEDULEDFS_H
|