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