LLVM 19.0.0git
ScheduleDFS.h
Go to the documentation of this file.
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
18#include <cassert>
19#include <cstdint>
20#include <vector>
21
22namespace llvm {
23
24template <typename T> class ArrayRef;
25class 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.
34struct 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.
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
115public:
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(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
189raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
190
191} // end namespace llvm
192
193#endif // LLVM_CODEGEN_SCHEDULEDFS_H
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallVector class.
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
Internal state used to compute SchedDFSResult.
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:65
unsigned getNumSubInstrs(unsigned SubtreeID) const
Get the number of instructions in the given subtree not including children.
Definition: ScheduleDFS.h:151
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
Definition: ScheduleDFS.h:145
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
Definition: ScheduleDFS.h:169
SchedDFSResult(bool IsBU, unsigned lim)
Definition: ScheduleDFS.h:116
void clear()
Clear the results.
Definition: ScheduleDFS.h:128
unsigned getSubtreeLimit() const
Get the node cutoff before subtrees are considered significant.
Definition: ScheduleDFS.h:120
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
Definition: ScheduleDFS.h:158
bool empty() const
Return true if this DFSResult is uninitialized.
Definition: ScheduleDFS.h:125
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
Definition: ScheduleDFS.h:163
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
Definition: ScheduleDFS.h:180
void resize(unsigned NumSUnits)
Initialize the result data with the size of the DAG.
Definition: ScheduleDFS.h:136
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1923
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
ArrayRef(const T &OneElt) -> ArrayRef< T >
Represent the ILP of the subDAG rooted at a DAG node.
Definition: ScheduleDFS.h:34
bool operator<(ILPValue RHS) const
Definition: ScheduleDFS.h:44
unsigned Length
Length may either correspond to depth or height, depending on direction, and cycles or nodes dependin...
Definition: ScheduleDFS.h:38
bool operator<=(ILPValue RHS) const
Definition: ScheduleDFS.h:51
bool operator>=(ILPValue RHS) const
Definition: ScheduleDFS.h:55
ILPValue(unsigned count, unsigned length)
Definition: ScheduleDFS.h:40
void print(raw_ostream &OS) const
bool operator>(ILPValue RHS) const
Definition: ScheduleDFS.h:48
unsigned InstrCount
Definition: ScheduleDFS.h:35