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