ScheduleDFS.h revision 8b1496c922b6a21296f7d42172df45bf205d5419 
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_SCHEDULEDAGILP_H
15#define LLVM_CODEGEN_SCHEDULEDAGILP_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/// When computed using bottom-up DFS, this metric assumes that the DAG is a
31/// forest of trees with roots at the bottom of the schedule branching upward.
32struct ILPValue {
33  unsigned InstrCount;
34  /// Length may either correspond to depth or height, depending on direction,
35  /// and cycles or nodes depending on context.
36  unsigned Length;
37
38  ILPValue(unsigned count, unsigned length):
39    InstrCount(count), Length(length) {}
40
41  // Order by the ILP metric's value.
42  bool operator<(ILPValue RHS) const {
43    return (uint64_t)InstrCount * RHS.Length
44      < (uint64_t)Length * RHS.InstrCount;
45  }
46  bool operator>(ILPValue RHS) const {
47    return RHS < *this;
48  }
49  bool operator<=(ILPValue RHS) const {
50    return (uint64_t)InstrCount * RHS.Length
51      <= (uint64_t)Length * RHS.InstrCount;
52  }
53  bool operator>=(ILPValue RHS) const {
54    return RHS <= *this;
55  }
56
57#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
58  void print(raw_ostream &OS) const;
59
60  void dump() const;
61#endif
62};
63
64/// \brief Compute the values of each DAG node for various metrics during DFS.
65///
66/// ILPValues summarize the DAG subtree rooted at each node up to
67/// SubtreeLimit. ILPValues are also valid for interior nodes of a subtree, not
68/// just the root.
69class SchedDFSResult {
70  friend class SchedDFSImpl;
71
72  /// \brief Per-SUnit data computed during DFS for various metrics.
73  struct NodeData {
74    unsigned InstrCount;
75    unsigned SubtreeID;
76
77    NodeData(): InstrCount(0), SubtreeID(0) {}
78  };
79
80  /// \brief Record a connection between subtrees and the connection level.
81  struct Connection {
82    unsigned TreeID;
83    unsigned Level;
84
85    Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
86  };
87
88  bool IsBottomUp;
89  unsigned SubtreeLimit;
90  /// DFS results for each SUnit in this DAG.
91  std::vector<NodeData> DFSData;
92
93  // For each subtree discovered during DFS, record its connections to other
94  // subtrees.
95  std::vector<SmallVector<Connection, 4> > SubtreeConnections;
96
97  /// Cache the current connection level of each subtree.
98  /// This mutable array is updated during scheduling.
99  std::vector<unsigned> SubtreeConnectLevels;
100
101public:
102  SchedDFSResult(bool IsBU, unsigned lim)
103    : IsBottomUp(IsBU), SubtreeLimit(lim) {}
104
105  /// \brief Clear the results.
106  void clear() {
107    DFSData.clear();
108    SubtreeConnections.clear();
109    SubtreeConnectLevels.clear();
110  }
111
112  /// \brief Initialize the result data with the size of the DAG.
113  void resize(unsigned NumSUnits) {
114    DFSData.resize(NumSUnits);
115  }
116
117  /// \brief Compute various metrics for the DAG with given roots.
118  void compute(ArrayRef<SUnit *> Roots);
119
120  /// \brief Get the ILP value for a DAG node.
121  ///
122  /// A leaf node has an ILP of 1/1.
123  ILPValue getILP(const SUnit *SU) {
124    return ILPValue(DFSData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
125  }
126
127  /// \brief The number of subtrees detected in this DAG.
128  unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
129
130  /// \brief Get the ID of the subtree the given DAG node belongs to.
131  unsigned getSubtreeID(const SUnit *SU) {
132    return DFSData[SU->NodeNum].SubtreeID;
133  }
134
135  /// \brief Get the connection level of a subtree.
136  ///
137  /// For bottom-up trees, the connection level is the latency depth (in cycles)
138  /// of the deepest connection to another subtree.
139  unsigned getSubtreeLevel(unsigned SubtreeID) {
140    return SubtreeConnectLevels[SubtreeID];
141  }
142
143  /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
144  /// initially scheduled.
145  void scheduleTree(unsigned SubtreeID);
146};
147
148raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
149
150} // namespace llvm
151
152#endif
153