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#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
61  void print(raw_ostream &OS) const;
62
63  void dump() const;
64#endif
65};
66
67/// \brief Compute the values of each DAG node for various metrics during DFS.
68class SchedDFSResult {
69  friend class SchedDFSImpl;
70
71  static const unsigned InvalidSubtreeID = ~0u;
72
73  /// \brief Per-SUnit data computed during DFS for various metrics.
74  ///
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
78  /// finalization.
79  struct NodeData {
80    unsigned InstrCount;
81    unsigned SubtreeID;
82
83    NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
84  };
85
86  /// \brief Per-Subtree data computed during DFS.
87  struct TreeData {
88    unsigned ParentTreeID;
89    unsigned SubInstrCount;
90
91    TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
92  };
93
94  /// \brief Record a connection between subtrees and the connection level.
95  struct Connection {
96    unsigned TreeID;
97    unsigned Level;
98
99    Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
100  };
101
102  bool IsBottomUp;
103  unsigned SubtreeLimit;
104  /// DFS results for each SUnit in this DAG.
105  std::vector<NodeData> DFSNodeData;
106
107  // Store per-tree data indexed on tree ID,
108  SmallVector<TreeData, 16> DFSTreeData;
109
110  // For each subtree discovered during DFS, record its connections to other
111  // subtrees.
112  std::vector<SmallVector<Connection, 4> > SubtreeConnections;
113
114  /// Cache the current connection level of each subtree.
115  /// This mutable array is updated during scheduling.
116  std::vector<unsigned> SubtreeConnectLevels;
117
118public:
119  SchedDFSResult(bool IsBU, unsigned lim)
120    : IsBottomUp(IsBU), SubtreeLimit(lim) {}
121
122  /// \brief Get the node cutoff before subtrees are considered significant.
123  unsigned getSubtreeLimit() const { return SubtreeLimit; }
124
125  /// \brief Return true if this DFSResult is uninitialized.
126  ///
127  /// resize() initializes DFSResult, while compute() populates it.
128  bool empty() const { return DFSNodeData.empty(); }
129
130  /// \brief Clear the results.
131  void clear() {
132    DFSNodeData.clear();
133    DFSTreeData.clear();
134    SubtreeConnections.clear();
135    SubtreeConnectLevels.clear();
136  }
137
138  /// \brief Initialize the result data with the size of the DAG.
139  void resize(unsigned NumSUnits) {
140    DFSNodeData.resize(NumSUnits);
141  }
142
143  /// \brief Compute various metrics for the DAG with given roots.
144  void compute(ArrayRef<SUnit> SUnits);
145
146  /// \brief Get the number of instructions in the given subtree and its
147  /// children.
148  unsigned getNumInstrs(const SUnit *SU) const {
149    return DFSNodeData[SU->NodeNum].InstrCount;
150  }
151
152  /// \brief Get the number of instructions in the given subtree not including
153  /// children.
154  unsigned getNumSubInstrs(unsigned SubtreeID) const {
155    return DFSTreeData[SubtreeID].SubInstrCount;
156  }
157
158  /// \brief Get the ILP value for a DAG node.
159  ///
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());
163  }
164
165  /// \brief The number of subtrees detected in this DAG.
166  unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
167
168  /// \brief Get the ID of the subtree the given DAG node belongs to.
169  ///
170  /// For convenience, if DFSResults have not been computed yet, give everything
171  /// tree ID 0.
172  unsigned getSubtreeID(const SUnit *SU) const {
173    if (empty())
174      return 0;
175    assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
176    return DFSNodeData[SU->NodeNum].SubtreeID;
177  }
178
179  /// \brief Get the connection level of a subtree.
180  ///
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];
185  }
186
187  /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
188  /// initially scheduled.
189  void scheduleTree(unsigned SubtreeID);
190};
191
192raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
193
194} // namespace llvm
195
196#endif
197