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 SubInstrCount;
  82     unsigned SubtreeID;
  83
  84     NodeData(): InstrCount(0), SubInstrCount(0), SubtreeID(InvalidSubtreeID) {}
  85   };
  86
  87   /// \brief Record a connection between subtrees and the connection level.
  88   struct Connection {
  89     unsigned TreeID;
  90     unsigned Level;
  91
  92     Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
  93   };
  94
  95   bool IsBottomUp;
  96   unsigned SubtreeLimit;
  97   /// DFS results for each SUnit in this DAG.
  98   std::vector<NodeData> DFSData;
  99
 100   // For each subtree discovered during DFS, record its connections to other
 101   // subtrees.
 102   std::vector<SmallVector<Connection, 4> > SubtreeConnections;
 103
 104   /// Cache the current connection level of each subtree.
 105   /// This mutable array is updated during scheduling.
 106   std::vector<unsigned> SubtreeConnectLevels;
 107
 108 public:
 109   SchedDFSResult(bool IsBU, unsigned lim)
 110     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
 111
 112   /// \brief Return true if this DFSResult is uninitialized.
 113   ///
 114   /// resize() initializes DFSResult, while compute() populates it.
 115   bool empty() const { return DFSData.empty(); }
 116
 117   /// \brief Clear the results.
 118   void clear() {
 119     DFSData.clear();
 120     SubtreeConnections.clear();
 121     SubtreeConnectLevels.clear();
 122   }
 123
 124   /// \brief Initialize the result data with the size of the DAG.
 125   void resize(unsigned NumSUnits) {
 126     DFSData.resize(NumSUnits);
 127   }
 128
 129   /// \brief Compute various metrics for the DAG with given roots.
 130   void compute(ArrayRef<SUnit> SUnits);
 131
 132   /// \brief Get the ILP value for a DAG node.
 133   ///
 134   /// A leaf node has an ILP of 1/1.
 135   ILPValue getILP(const SUnit *SU) const {
 136     return ILPValue(DFSData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
 137   }
 138
 139   /// \brief The number of subtrees detected in this DAG.
 140   unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
 141
 142   /// \brief Get the ID of the subtree the given DAG node belongs to.
 143   ///
 144   /// For convenience, if DFSResults have not been computed yet, give everything
 145   /// tree ID 0.
 146   unsigned getSubtreeID(const SUnit *SU) const {
 147     if (empty())
 148       return 0;
 149     assert(SU->NodeNum < DFSData.size() &&  "New Node");
 150     return DFSData[SU->NodeNum].SubtreeID;
 151   }
 152
 153   /// \brief Get the connection level of a subtree.
 154   ///
 155   /// For bottom-up trees, the connection level is the latency depth (in cycles)
 156   /// of the deepest connection to another subtree.
 157   unsigned getSubtreeLevel(unsigned SubtreeID) const {
 158     return SubtreeConnectLevels[SubtreeID];
 159   }
 160
 161   /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
 162   /// initially scheduled.
 163   void scheduleTree(unsigned SubtreeID);
 164 };
 165
 166 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
 167
 168 } // namespace llvm
 169
 170 #endif