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_SCHEDULEDAGILP_H
15 #define LLVM_CODEGEN_SCHEDULEDAGILP_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 /// 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.
34 /// Length may either correspond to depth or height, depending on direction,
35 /// and cycles or nodes depending on context.
38 ILPValue(unsigned count, unsigned length):
39 InstrCount(count), Length(length) {}
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;
46 bool operator>(ILPValue RHS) const {
49 bool operator<=(ILPValue RHS) const {
50 return (uint64_t)InstrCount * RHS.Length
51 <= (uint64_t)Length * RHS.InstrCount;
53 bool operator>=(ILPValue RHS) const {
57 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
58 void print(raw_ostream &OS) const;
64 /// \brief Compute the values of each DAG node for various metrics during DFS.
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
69 class SchedDFSResult {
70 friend class SchedDFSImpl;
72 /// \brief Per-SUnit data computed during DFS for various metrics.
77 NodeData(): InstrCount(0), SubtreeID(0) {}
80 /// \brief Record a connection between subtrees and the connection level.
85 Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
89 unsigned SubtreeLimit;
90 /// DFS results for each SUnit in this DAG.
91 std::vector<NodeData> DFSData;
93 // For each subtree discovered during DFS, record its connections to other
95 std::vector<SmallVector<Connection, 4> > SubtreeConnections;
97 /// Cache the current connection level of each subtree.
98 /// This mutable array is updated during scheduling.
99 std::vector<unsigned> SubtreeConnectLevels;
102 SchedDFSResult(bool IsBU, unsigned lim)
103 : IsBottomUp(IsBU), SubtreeLimit(lim) {}
105 /// \brief Clear the results.
108 SubtreeConnections.clear();
109 SubtreeConnectLevels.clear();
112 /// \brief Initialize the result data with the size of the DAG.
113 void resize(unsigned NumSUnits) {
114 DFSData.resize(NumSUnits);
117 /// \brief Compute various metrics for the DAG with given roots.
118 void compute(ArrayRef<SUnit *> Roots);
120 /// \brief Get the ILP value for a DAG node.
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());
127 /// \brief The number of subtrees detected in this DAG.
128 unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
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;
135 /// \brief Get the connection level of a subtree.
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];
143 /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
144 /// initially scheduled.
145 void scheduleTree(unsigned SubtreeID);
148 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);