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
|
//===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Definition of an ILP metric for machine level instruction scheduling.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDULEDAGILP_H
#define LLVM_CODEGEN_SCHEDULEDAGILP_H
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Support/DataTypes.h"
#include <vector>
namespace llvm {
class raw_ostream;
class IntEqClasses;
class ScheduleDAGInstrs;
class SUnit;
/// \brief Represent the ILP of the subDAG rooted at a DAG node.
///
/// 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;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void print(raw_ostream &OS) const;
void dump() const;
#endif
};
/// \brief Compute the values of each DAG node for various metrics during DFS.
///
/// ILPValues summarize the DAG subtree rooted at each node up to
/// SubtreeLimit. ILPValues are also valid for interior nodes of a subtree, not
/// just the root.
class SchedDFSResult {
friend class SchedDFSImpl;
/// \brief Per-SUnit data computed during DFS for various metrics.
struct NodeData {
unsigned InstrCount;
unsigned SubtreeID;
NodeData(): InstrCount(0), SubtreeID(0) {}
};
/// \brief 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> DFSData;
// 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) {}
/// \brief Clear the results.
void clear() {
DFSData.clear();
SubtreeConnections.clear();
SubtreeConnectLevels.clear();
}
/// \brief Initialize the result data with the size of the DAG.
void resize(unsigned NumSUnits) {
DFSData.resize(NumSUnits);
}
/// \brief Compute various metrics for the DAG with given roots.
void compute(ArrayRef<SUnit *> Roots);
/// \brief Get the ILP value for a DAG node.
///
/// A leaf node has an ILP of 1/1.
ILPValue getILP(const SUnit *SU) {
return ILPValue(DFSData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
}
/// \brief The number of subtrees detected in this DAG.
unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
/// \brief Get the ID of the subtree the given DAG node belongs to.
unsigned getSubtreeID(const SUnit *SU) {
return DFSData[SU->NodeNum].SubtreeID;
}
/// \brief 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) {
return SubtreeConnectLevels[SubtreeID];
}
/// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
/// initially scheduled.
void scheduleTree(unsigned SubtreeID);
};
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
} // namespace llvm
#endif
|
