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/ADT/ArrayRef.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/CodeGen/ScheduleDAG.h" 20 #include <cassert> 21 #include <cstdint> 22 #include <vector> 23 24 namespace llvm { 25 26 class raw_ostream; 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. 35 struct 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. 66 class 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 = 0; 79 unsigned SubtreeID = InvalidSubtreeID; 80 81 NodeData() = default; 82 }; 83 84 /// \brief Per-Subtree data computed during DFS. 85 struct TreeData { 86 unsigned ParentTreeID = InvalidSubtreeID; 87 unsigned SubInstrCount = 0; 88 89 TreeData() = default; 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 116 public: 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 190 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); 191 192 } // end namespace llvm 193 194 #endif // LLVM_CODEGEN_SCHEDULEDFS_H 195
