contrib/llvm/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 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  61   void print(raw_ostream &OS) const;
  62
  63   void dump() const;
  64 #endif
  65 };
  66
  67 /// \brief Compute the values of each DAG node for various metrics during DFS.
  68 class SchedDFSResult {
  69   friend class SchedDFSImpl;
  70
  71   static const unsigned InvalidSubtreeID = ~0u;
  72
  73   /// \brief Per-SUnit data computed during DFS for various metrics.
  74   ///
  75   /// A node's SubtreeID is set to itself when it is visited to indicate that it
  76   /// is the root of a subtree. Later it is set to its parent to indicate an
  77   /// interior node. Finally, it is set to a representative subtree ID during
  78   /// finalization.
  79   struct NodeData {
  80     unsigned InstrCount;
  81     unsigned SubtreeID;
  82
  83     NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
  84   };
  85
  86   /// \brief Per-Subtree data computed during DFS.
  87   struct TreeData {
  88     unsigned ParentTreeID;
  89     unsigned SubInstrCount;
  90
  91     TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
  92   };
  93
  94   /// \brief Record a connection between subtrees and the connection level.
  95   struct Connection {
  96     unsigned TreeID;
  97     unsigned Level;
  98
  99     Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
 100   };
 101
 102   bool IsBottomUp;
 103   unsigned SubtreeLimit;
 104   /// DFS results for each SUnit in this DAG.
 105   std::vector<NodeData> DFSNodeData;
 106
 107   // Store per-tree data indexed on tree ID,
 108   SmallVector<TreeData, 16> DFSTreeData;
 109
 110   // For each subtree discovered during DFS, record its connections to other
 111   // subtrees.
 112   std::vector<SmallVector<Connection, 4> > SubtreeConnections;
 113
 114   /// Cache the current connection level of each subtree.
 115   /// This mutable array is updated during scheduling.
 116   std::vector<unsigned> SubtreeConnectLevels;
 117
 118 public:
 119   SchedDFSResult(bool IsBU, unsigned lim)
 120     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
 121
 122   /// \brief Get the node cutoff before subtrees are considered significant.
 123   unsigned getSubtreeLimit() const { return SubtreeLimit; }
 124
 125   /// \brief Return true if this DFSResult is uninitialized.
 126   ///
 127   /// resize() initializes DFSResult, while compute() populates it.
 128   bool empty() const { return DFSNodeData.empty(); }
 129
 130   /// \brief Clear the results.
 131   void clear() {
 132     DFSNodeData.clear();
 133     DFSTreeData.clear();
 134     SubtreeConnections.clear();
 135     SubtreeConnectLevels.clear();
 136   }
 137
 138   /// \brief Initialize the result data with the size of the DAG.
 139   void resize(unsigned NumSUnits) {
 140     DFSNodeData.resize(NumSUnits);
 141   }
 142
 143   /// \brief Compute various metrics for the DAG with given roots.
 144   void compute(ArrayRef<SUnit> SUnits);
 145
 146   /// \brief Get the number of instructions in the given subtree and its
 147   /// children.
 148   unsigned getNumInstrs(const SUnit *SU) const {
 149     return DFSNodeData[SU->NodeNum].InstrCount;
 150   }
 151
 152   /// \brief Get the number of instructions in the given subtree not including
 153   /// children.
 154   unsigned getNumSubInstrs(unsigned SubtreeID) const {
 155     return DFSTreeData[SubtreeID].SubInstrCount;
 156   }
 157
 158   /// \brief Get the ILP value for a DAG node.
 159   ///
 160   /// A leaf node has an ILP of 1/1.
 161   ILPValue getILP(const SUnit *SU) const {
 162     return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
 163   }
 164
 165   /// \brief The number of subtrees detected in this DAG.
 166   unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
 167
 168   /// \brief Get the ID of the subtree the given DAG node belongs to.
 169   ///
 170   /// For convenience, if DFSResults have not been computed yet, give everything
 171   /// tree ID 0.
 172   unsigned getSubtreeID(const SUnit *SU) const {
 173     if (empty())
 174       return 0;
 175     assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
 176     return DFSNodeData[SU->NodeNum].SubtreeID;
 177   }
 178
 179   /// \brief Get the connection level of a subtree.
 180   ///
 181   /// For bottom-up trees, the connection level is the latency depth (in cycles)
 182   /// of the deepest connection to another subtree.
 183   unsigned getSubtreeLevel(unsigned SubtreeID) const {
 184     return SubtreeConnectLevels[SubtreeID];
 185   }
 186
 187   /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
 188   /// initially scheduled.
 189   void scheduleTree(unsigned SubtreeID);
 190 };
 191
 192 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
 193
 194 } // namespace llvm
 195
 196 #endif