1 //===- ScheduleDFS.h - ILP metric for ScheduleDAGInstrs ---------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Definition of an ILP metric for machine level instruction scheduling. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CODEGEN_SCHEDULEDFS_H 14 #define LLVM_CODEGEN_SCHEDULEDFS_H 15 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/CodeGen/ScheduleDAG.h" 18 #include <cassert> 19 #include <cstdint> 20 #include <vector> 21 22 namespace llvm { 23 24 template <typename T> class ArrayRef; 25 class raw_ostream; 26 27 /// Represent the ILP of the subDAG rooted at a DAG node. 28 /// 29 /// ILPValues summarize the DAG subtree rooted at each node. ILPValues are 30 /// valid for all nodes regardless of their subtree membership. 31 /// 32 /// When computed using bottom-up DFS, this metric assumes that the DAG is a 33 /// forest of trees with roots at the bottom of the schedule branching upward. 34 struct ILPValue { 35 unsigned InstrCount; 36 /// Length may either correspond to depth or height, depending on direction, 37 /// and cycles or nodes depending on context. 38 unsigned Length; 39 40 ILPValue(unsigned count, unsigned length): 41 InstrCount(count), Length(length) {} 42 43 // Order by the ILP metric's value. 44 bool operator<(ILPValue RHS) const { 45 return (uint64_t)InstrCount * RHS.Length 46 < (uint64_t)Length * RHS.InstrCount; 47 } 48 bool operator>(ILPValue RHS) const { 49 return RHS < *this; 50 } 51 bool operator<=(ILPValue RHS) const { 52 return (uint64_t)InstrCount * RHS.Length 53 <= (uint64_t)Length * RHS.InstrCount; 54 } 55 bool operator>=(ILPValue RHS) const { 56 return RHS <= *this; 57 } 58 59 void print(raw_ostream &OS) const; 60 61 void dump() const; 62 }; 63 64 /// Compute the values of each DAG node for various metrics during DFS. 65 class SchedDFSResult { 66 friend class SchedDFSImpl; 67 68 static const unsigned InvalidSubtreeID = ~0u; 69 70 /// Per-SUnit data computed during DFS for various metrics. 71 /// 72 /// A node's SubtreeID is set to itself when it is visited to indicate that it 73 /// is the root of a subtree. Later it is set to its parent to indicate an 74 /// interior node. Finally, it is set to a representative subtree ID during 75 /// finalization. 76 struct NodeData { 77 unsigned InstrCount = 0; 78 unsigned SubtreeID = InvalidSubtreeID; 79 80 NodeData() = default; 81 }; 82 83 /// Per-Subtree data computed during DFS. 84 struct TreeData { 85 unsigned ParentTreeID = InvalidSubtreeID; 86 unsigned SubInstrCount = 0; 87 88 TreeData() = default; 89 }; 90 91 /// Record a connection between subtrees and the connection level. 92 struct Connection { 93 unsigned TreeID; 94 unsigned Level; 95 96 Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {} 97 }; 98 99 bool IsBottomUp; 100 unsigned SubtreeLimit; 101 /// DFS results for each SUnit in this DAG. 102 std::vector<NodeData> DFSNodeData; 103 104 // Store per-tree data indexed on tree ID, 105 SmallVector<TreeData, 16> DFSTreeData; 106 107 // For each subtree discovered during DFS, record its connections to other 108 // subtrees. 109 std::vector<SmallVector<Connection, 4>> SubtreeConnections; 110 111 /// Cache the current connection level of each subtree. 112 /// This mutable array is updated during scheduling. 113 std::vector<unsigned> SubtreeConnectLevels; 114 115 public: 116 SchedDFSResult(bool IsBU, unsigned lim) 117 : IsBottomUp(IsBU), SubtreeLimit(lim) {} 118 119 /// Get the node cutoff before subtrees are considered significant. 120 unsigned getSubtreeLimit() const { return SubtreeLimit; } 121 122 /// Return true if this DFSResult is uninitialized. 123 /// 124 /// resize() initializes DFSResult, while compute() populates it. 125 bool empty() const { return DFSNodeData.empty(); } 126 127 /// Clear the results. 128 void clear() { 129 DFSNodeData.clear(); 130 DFSTreeData.clear(); 131 SubtreeConnections.clear(); 132 SubtreeConnectLevels.clear(); 133 } 134 135 /// Initialize the result data with the size of the DAG. 136 void resize(unsigned NumSUnits) { 137 DFSNodeData.resize(NumSUnits); 138 } 139 140 /// Compute various metrics for the DAG with given roots. 141 void compute(ArrayRef<SUnit> SUnits); 142 143 /// Get the number of instructions in the given subtree and its 144 /// children. 145 unsigned getNumInstrs(const SUnit *SU) const { 146 return DFSNodeData[SU->NodeNum].InstrCount; 147 } 148 149 /// Get the number of instructions in the given subtree not including 150 /// children. 151 unsigned getNumSubInstrs(unsigned SubtreeID) const { 152 return DFSTreeData[SubtreeID].SubInstrCount; 153 } 154 155 /// Get the ILP value for a DAG node. 156 /// 157 /// A leaf node has an ILP of 1/1. 158 ILPValue getILP(const SUnit *SU) const { 159 return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth()); 160 } 161 162 /// The number of subtrees detected in this DAG. 163 unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } 164 165 /// Get the ID of the subtree the given DAG node belongs to. 166 /// 167 /// For convenience, if DFSResults have not been computed yet, give everything 168 /// tree ID 0. 169 unsigned getSubtreeID(const SUnit *SU) const { 170 if (empty()) 171 return 0; 172 assert(SU->NodeNum < DFSNodeData.size() && "New Node"); 173 return DFSNodeData[SU->NodeNum].SubtreeID; 174 } 175 176 /// Get the connection level of a subtree. 177 /// 178 /// For bottom-up trees, the connection level is the latency depth (in cycles) 179 /// of the deepest connection to another subtree. 180 unsigned getSubtreeLevel(unsigned SubtreeID) const { 181 return SubtreeConnectLevels[SubtreeID]; 182 } 183 184 /// Scheduler callback to update SubtreeConnectLevels when a tree is 185 /// initially scheduled. 186 void scheduleTree(unsigned SubtreeID); 187 }; 188 189 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); 190 191 } // end namespace llvm 192 193 #endif // LLVM_CODEGEN_SCHEDULEDFS_H 194