include/llvm/CodeGen/ScheduleDFS.h

   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/CodeGen/ScheduleDAG.h"
  18 #include "llvm/Support/DataTypes.h"
  19 #include <vector>
  20
  21 namespace llvm {
  22
  23 class raw_ostream;
  24 class IntEqClasses;
  25 class ScheduleDAGInstrs;
  26 class SUnit;
  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;
  79     unsigned SubtreeID;
  80
  81     NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
  82   };
  83
  84   /// \brief Per-Subtree data computed during DFS.
  85   struct TreeData {
  86     unsigned ParentTreeID;
  87     unsigned SubInstrCount;
  88
  89     TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
  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 } // namespace llvm
 193
 194 #endif