1 //===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Definition of an ILP metric for machine level instruction scheduling.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_SCHEDULEDFS_H
15 #define LLVM_CODEGEN_SCHEDULEDFS_H
17 #include "llvm/CodeGen/ScheduleDAG.h"
18 #include "llvm/Support/DataTypes.h"
25 class ScheduleDAGInstrs;
28 /// \brief Represent the ILP of the subDAG rooted at a DAG node.
30 /// ILPValues summarize the DAG subtree rooted at each node. ILPValues are
31 /// valid for all nodes regardless of their subtree membership.
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.
37 /// Length may either correspond to depth or height, depending on direction,
38 /// and cycles or nodes depending on context.
41 ILPValue(unsigned count, unsigned length):
42 InstrCount(count), Length(length) {}
44 // Order by the ILP metric's value.
45 bool operator<(ILPValue RHS) const {
46 return (uint64_t)InstrCount * RHS.Length
47 < (uint64_t)Length * RHS.InstrCount;
49 bool operator>(ILPValue RHS) const {
52 bool operator<=(ILPValue RHS) const {
53 return (uint64_t)InstrCount * RHS.Length
54 <= (uint64_t)Length * RHS.InstrCount;
56 bool operator>=(ILPValue RHS) const {
60 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
61 void print(raw_ostream &OS) const;
67 /// \brief Compute the values of each DAG node for various metrics during DFS.
68 class SchedDFSResult {
69 friend class SchedDFSImpl;
71 static const unsigned InvalidSubtreeID = ~0u;
73 /// \brief Per-SUnit data computed during DFS for various metrics.
75 /// A node's SubtreeID is set to itself when it is visited to indicate that it
76 /// is the root of a subtree. Later it is set to its parent to indicate an
77 /// interior node. Finally, it is set to a representative subtree ID during
83 NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
86 /// \brief Per-Subtree data computed during DFS.
88 unsigned ParentTreeID;
89 unsigned SubInstrCount;
91 TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
94 /// \brief Record a connection between subtrees and the connection level.
99 Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
103 unsigned SubtreeLimit;
104 /// DFS results for each SUnit in this DAG.
105 std::vector<NodeData> DFSNodeData;
107 // Store per-tree data indexed on tree ID,
108 SmallVector<TreeData, 16> DFSTreeData;
110 // For each subtree discovered during DFS, record its connections to other
112 std::vector<SmallVector<Connection, 4> > SubtreeConnections;
114 /// Cache the current connection level of each subtree.
115 /// This mutable array is updated during scheduling.
116 std::vector<unsigned> SubtreeConnectLevels;
119 SchedDFSResult(bool IsBU, unsigned lim)
120 : IsBottomUp(IsBU), SubtreeLimit(lim) {}
122 /// \brief Get the node cutoff before subtrees are considered significant.
123 unsigned getSubtreeLimit() const { return SubtreeLimit; }
125 /// \brief Return true if this DFSResult is uninitialized.
127 /// resize() initializes DFSResult, while compute() populates it.
128 bool empty() const { return DFSNodeData.empty(); }
130 /// \brief Clear the results.
134 SubtreeConnections.clear();
135 SubtreeConnectLevels.clear();
138 /// \brief Initialize the result data with the size of the DAG.
139 void resize(unsigned NumSUnits) {
140 DFSNodeData.resize(NumSUnits);
143 /// \brief Compute various metrics for the DAG with given roots.
144 void compute(ArrayRef<SUnit> SUnits);
146 /// \brief Get the number of instructions in the given subtree and its
148 unsigned getNumInstrs(const SUnit *SU) const {
149 return DFSNodeData[SU->NodeNum].InstrCount;
152 /// \brief Get the number of instructions in the given subtree not including
154 unsigned getNumSubInstrs(unsigned SubtreeID) const {
155 return DFSTreeData[SubtreeID].SubInstrCount;
158 /// \brief Get the ILP value for a DAG node.
160 /// A leaf node has an ILP of 1/1.
161 ILPValue getILP(const SUnit *SU) const {
162 return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
165 /// \brief The number of subtrees detected in this DAG.
166 unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
168 /// \brief Get the ID of the subtree the given DAG node belongs to.
170 /// For convenience, if DFSResults have not been computed yet, give everything
172 unsigned getSubtreeID(const SUnit *SU) const {
175 assert(SU->NodeNum < DFSNodeData.size() && "New Node");
176 return DFSNodeData[SU->NodeNum].SubtreeID;
179 /// \brief Get the connection level of a subtree.
181 /// For bottom-up trees, the connection level is the latency depth (in cycles)
182 /// of the deepest connection to another subtree.
183 unsigned getSubtreeLevel(unsigned SubtreeID) const {
184 return SubtreeConnectLevels[SubtreeID];
187 /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
188 /// initially scheduled.
189 void scheduleTree(unsigned SubtreeID);
192 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);