1249259Sdim//===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// Definition of an ILP metric for machine level instruction scheduling. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#ifndef LLVM_CODEGEN_SCHEDULEDFS_H 15249259Sdim#define LLVM_CODEGEN_SCHEDULEDFS_H 16249259Sdim 17249259Sdim#include "llvm/CodeGen/ScheduleDAG.h" 18249259Sdim#include "llvm/Support/DataTypes.h" 19249259Sdim#include <vector> 20249259Sdim 21249259Sdimnamespace llvm { 22249259Sdim 23249259Sdimclass raw_ostream; 24249259Sdimclass IntEqClasses; 25249259Sdimclass ScheduleDAGInstrs; 26249259Sdimclass SUnit; 27249259Sdim 28249259Sdim/// \brief Represent the ILP of the subDAG rooted at a DAG node. 29249259Sdim/// 30249259Sdim/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are 31249259Sdim/// valid for all nodes regardless of their subtree membership. 32249259Sdim/// 33249259Sdim/// When computed using bottom-up DFS, this metric assumes that the DAG is a 34249259Sdim/// forest of trees with roots at the bottom of the schedule branching upward. 35249259Sdimstruct ILPValue { 36249259Sdim unsigned InstrCount; 37249259Sdim /// Length may either correspond to depth or height, depending on direction, 38249259Sdim /// and cycles or nodes depending on context. 39249259Sdim unsigned Length; 40249259Sdim 41249259Sdim ILPValue(unsigned count, unsigned length): 42249259Sdim InstrCount(count), Length(length) {} 43249259Sdim 44249259Sdim // Order by the ILP metric's value. 45249259Sdim bool operator<(ILPValue RHS) const { 46249259Sdim return (uint64_t)InstrCount * RHS.Length 47249259Sdim < (uint64_t)Length * RHS.InstrCount; 48249259Sdim } 49249259Sdim bool operator>(ILPValue RHS) const { 50249259Sdim return RHS < *this; 51249259Sdim } 52249259Sdim bool operator<=(ILPValue RHS) const { 53249259Sdim return (uint64_t)InstrCount * RHS.Length 54249259Sdim <= (uint64_t)Length * RHS.InstrCount; 55249259Sdim } 56249259Sdim bool operator>=(ILPValue RHS) const { 57249259Sdim return RHS <= *this; 58249259Sdim } 59249259Sdim 60249259Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 61249259Sdim void print(raw_ostream &OS) const; 62249259Sdim 63249259Sdim void dump() const; 64249259Sdim#endif 65249259Sdim}; 66249259Sdim 67249259Sdim/// \brief Compute the values of each DAG node for various metrics during DFS. 68249259Sdimclass SchedDFSResult { 69249259Sdim friend class SchedDFSImpl; 70249259Sdim 71249259Sdim static const unsigned InvalidSubtreeID = ~0u; 72249259Sdim 73249259Sdim /// \brief Per-SUnit data computed during DFS for various metrics. 74249259Sdim /// 75249259Sdim /// A node's SubtreeID is set to itself when it is visited to indicate that it 76249259Sdim /// is the root of a subtree. Later it is set to its parent to indicate an 77249259Sdim /// interior node. Finally, it is set to a representative subtree ID during 78249259Sdim /// finalization. 79249259Sdim struct NodeData { 80249259Sdim unsigned InstrCount; 81249259Sdim unsigned SubtreeID; 82249259Sdim 83249259Sdim NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {} 84249259Sdim }; 85249259Sdim 86249259Sdim /// \brief Per-Subtree data computed during DFS. 87249259Sdim struct TreeData { 88249259Sdim unsigned ParentTreeID; 89249259Sdim unsigned SubInstrCount; 90249259Sdim 91249259Sdim TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {} 92249259Sdim }; 93249259Sdim 94249259Sdim /// \brief Record a connection between subtrees and the connection level. 95249259Sdim struct Connection { 96249259Sdim unsigned TreeID; 97249259Sdim unsigned Level; 98249259Sdim 99249259Sdim Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {} 100249259Sdim }; 101249259Sdim 102249259Sdim bool IsBottomUp; 103249259Sdim unsigned SubtreeLimit; 104249259Sdim /// DFS results for each SUnit in this DAG. 105249259Sdim std::vector<NodeData> DFSNodeData; 106249259Sdim 107249259Sdim // Store per-tree data indexed on tree ID, 108249259Sdim SmallVector<TreeData, 16> DFSTreeData; 109249259Sdim 110249259Sdim // For each subtree discovered during DFS, record its connections to other 111249259Sdim // subtrees. 112249259Sdim std::vector<SmallVector<Connection, 4> > SubtreeConnections; 113249259Sdim 114249259Sdim /// Cache the current connection level of each subtree. 115249259Sdim /// This mutable array is updated during scheduling. 116249259Sdim std::vector<unsigned> SubtreeConnectLevels; 117249259Sdim 118249259Sdimpublic: 119249259Sdim SchedDFSResult(bool IsBU, unsigned lim) 120249259Sdim : IsBottomUp(IsBU), SubtreeLimit(lim) {} 121249259Sdim 122249259Sdim /// \brief Get the node cutoff before subtrees are considered significant. 123249259Sdim unsigned getSubtreeLimit() const { return SubtreeLimit; } 124249259Sdim 125249259Sdim /// \brief Return true if this DFSResult is uninitialized. 126249259Sdim /// 127249259Sdim /// resize() initializes DFSResult, while compute() populates it. 128249259Sdim bool empty() const { return DFSNodeData.empty(); } 129249259Sdim 130249259Sdim /// \brief Clear the results. 131249259Sdim void clear() { 132249259Sdim DFSNodeData.clear(); 133249259Sdim DFSTreeData.clear(); 134249259Sdim SubtreeConnections.clear(); 135249259Sdim SubtreeConnectLevels.clear(); 136249259Sdim } 137249259Sdim 138249259Sdim /// \brief Initialize the result data with the size of the DAG. 139249259Sdim void resize(unsigned NumSUnits) { 140249259Sdim DFSNodeData.resize(NumSUnits); 141249259Sdim } 142249259Sdim 143249259Sdim /// \brief Compute various metrics for the DAG with given roots. 144249259Sdim void compute(ArrayRef<SUnit> SUnits); 145249259Sdim 146249259Sdim /// \brief Get the number of instructions in the given subtree and its 147249259Sdim /// children. 148249259Sdim unsigned getNumInstrs(const SUnit *SU) const { 149249259Sdim return DFSNodeData[SU->NodeNum].InstrCount; 150249259Sdim } 151249259Sdim 152249259Sdim /// \brief Get the number of instructions in the given subtree not including 153249259Sdim /// children. 154249259Sdim unsigned getNumSubInstrs(unsigned SubtreeID) const { 155249259Sdim return DFSTreeData[SubtreeID].SubInstrCount; 156249259Sdim } 157249259Sdim 158249259Sdim /// \brief Get the ILP value for a DAG node. 159249259Sdim /// 160249259Sdim /// A leaf node has an ILP of 1/1. 161249259Sdim ILPValue getILP(const SUnit *SU) const { 162249259Sdim return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth()); 163249259Sdim } 164249259Sdim 165249259Sdim /// \brief The number of subtrees detected in this DAG. 166249259Sdim unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } 167249259Sdim 168249259Sdim /// \brief Get the ID of the subtree the given DAG node belongs to. 169249259Sdim /// 170249259Sdim /// For convenience, if DFSResults have not been computed yet, give everything 171249259Sdim /// tree ID 0. 172249259Sdim unsigned getSubtreeID(const SUnit *SU) const { 173249259Sdim if (empty()) 174249259Sdim return 0; 175249259Sdim assert(SU->NodeNum < DFSNodeData.size() && "New Node"); 176249259Sdim return DFSNodeData[SU->NodeNum].SubtreeID; 177249259Sdim } 178249259Sdim 179249259Sdim /// \brief Get the connection level of a subtree. 180249259Sdim /// 181249259Sdim /// For bottom-up trees, the connection level is the latency depth (in cycles) 182249259Sdim /// of the deepest connection to another subtree. 183249259Sdim unsigned getSubtreeLevel(unsigned SubtreeID) const { 184249259Sdim return SubtreeConnectLevels[SubtreeID]; 185249259Sdim } 186249259Sdim 187249259Sdim /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is 188249259Sdim /// initially scheduled. 189249259Sdim void scheduleTree(unsigned SubtreeID); 190249259Sdim}; 191249259Sdim 192249259Sdimraw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); 193249259Sdim 194249259Sdim} // namespace llvm 195249259Sdim 196249259Sdim#endif 197