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/CodeGen/ScheduleDAG.h"
18#include "llvm/Support/DataTypes.h"
19#include <vector>
20
21namespace llvm {
22
23class raw_ostream;
24class IntEqClasses;
25class ScheduleDAGInstrs;
26class SUnit;
27
28/// \brief 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.
35struct 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  bool operator<(ILPValue RHS) const {
46    return (uint64_t)InstrCount * RHS.Length
47      < (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/// \brief Compute the values of each DAG node for various metrics during DFS.
66class SchedDFSResult {
67  friend class SchedDFSImpl;
68
69  static const unsigned InvalidSubtreeID = ~0u;
70
71  /// \brief 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;
79    unsigned SubtreeID;
80
81    NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
82  };
83
84  /// \brief Per-Subtree data computed during DFS.
85  struct TreeData {
86    unsigned ParentTreeID;
87    unsigned SubInstrCount;
88
89    TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
90  };
91
92  /// \brief Record a connection between subtrees and the connection level.
93  struct Connection {
94    unsigned TreeID;
95    unsigned Level;
96
97    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
116public:
117  SchedDFSResult(bool IsBU, unsigned lim)
118    : IsBottomUp(IsBU), SubtreeLimit(lim) {}
119
120  /// \brief Get the node cutoff before subtrees are considered significant.
121  unsigned getSubtreeLimit() const { return SubtreeLimit; }
122
123  /// \brief 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  /// \brief Clear the results.
129  void clear() {
130    DFSNodeData.clear();
131    DFSTreeData.clear();
132    SubtreeConnections.clear();
133    SubtreeConnectLevels.clear();
134  }
135
136  /// \brief Initialize the result data with the size of the DAG.
137  void resize(unsigned NumSUnits) {
138    DFSNodeData.resize(NumSUnits);
139  }
140
141  /// \brief Compute various metrics for the DAG with given roots.
142  void compute(ArrayRef<SUnit> SUnits);
143
144  /// \brief 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  /// \brief 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  /// \brief Get the ILP value for a DAG node.
157  ///
158  /// A leaf node has an ILP of 1/1.
159  ILPValue getILP(const SUnit *SU) const {
160    return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
161  }
162
163  /// \brief The number of subtrees detected in this DAG.
164  unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
165
166  /// \brief 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  unsigned getSubtreeID(const SUnit *SU) const {
171    if (empty())
172      return 0;
173    assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
174    return DFSNodeData[SU->NodeNum].SubtreeID;
175  }
176
177  /// \brief 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    return SubtreeConnectLevels[SubtreeID];
183  }
184
185  /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
186  /// initially scheduled.
187  void scheduleTree(unsigned SubtreeID);
188};
189
190raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
191
192} // namespace llvm
193
194#endif
195