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 
ILPValueILPValue40   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 
ConnectionConnection96     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:
SchedDFSResult(bool IsBU,unsigned lim)116   SchedDFSResult(bool IsBU, unsigned lim)
117     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
118 
119   /// Get the node cutoff before subtrees are considered significant.
getSubtreeLimit()120   unsigned getSubtreeLimit() const { return SubtreeLimit; }
121 
122   /// Return true if this DFSResult is uninitialized.
123   ///
124   /// resize() initializes DFSResult, while compute() populates it.
empty()125   bool empty() const { return DFSNodeData.empty(); }
126 
127   /// Clear the results.
clear()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.
resize(unsigned NumSUnits)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.
getNumInstrs(const SUnit * SU)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.
getNumSubInstrs(unsigned SubtreeID)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.
getILP(const SUnit * SU)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.
getNumSubtrees()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.
getSubtreeID(const SUnit * SU)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.
getSubtreeLevel(unsigned SubtreeID)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