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 /// When computed using bottom-up DFS, this metric assumes that the DAG is a
  31 /// forest of trees with roots at the bottom of the schedule branching upward.
  32 struct ILPValue {
  33   unsigned InstrCount;
  34   /// Length may either correspond to depth or height, depending on direction,
  35   /// and cycles or nodes depending on context.
  36   unsigned Length;
  37
  38   ILPValue(unsigned count, unsigned length):
  39     InstrCount(count), Length(length) {}
  40
  41   // Order by the ILP metric's value.
  42   bool operator<(ILPValue RHS) const {
  43     return (uint64_t)InstrCount * RHS.Length
  44       < (uint64_t)Length * RHS.InstrCount;
  45   }
  46   bool operator>(ILPValue RHS) const {
  47     return RHS < *this;
  48   }
  49   bool operator<=(ILPValue RHS) const {
  50     return (uint64_t)InstrCount * RHS.Length
  51       <= (uint64_t)Length * RHS.InstrCount;
  52   }
  53   bool operator>=(ILPValue RHS) const {
  54     return RHS <= *this;
  55   }
  56
  57 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  58   void print(raw_ostream &OS) const;
  59
  60   void dump() const;
  61 #endif
  62 };
  63
  64 /// \brief Compute the values of each DAG node for various metrics during DFS.
  65 ///
  66 /// ILPValues summarize the DAG subtree rooted at each node up to
  67 /// SubtreeLimit. ILPValues are also valid for interior nodes of a subtree, not
  68 /// just the root.
  69 class SchedDFSResult {
  70   friend class SchedDFSImpl;
  71
  72   /// \brief Per-SUnit data computed during DFS for various metrics.
  73   struct NodeData {
  74     unsigned InstrCount;
  75     unsigned SubtreeID;
  76
  77     NodeData(): InstrCount(0), SubtreeID(0) {}
  78   };
  79
  80   /// \brief Record a connection between subtrees and the connection level.
  81   struct Connection {
  82     unsigned TreeID;
  83     unsigned Level;
  84
  85     Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
  86   };
  87
  88   bool IsBottomUp;
  89   unsigned SubtreeLimit;
  90   /// DFS results for each SUnit in this DAG.
  91   std::vector<NodeData> DFSData;
  92
  93   // For each subtree discovered during DFS, record its connections to other
  94   // subtrees.
  95   std::vector<SmallVector<Connection, 4> > SubtreeConnections;
  96
  97   /// Cache the current connection level of each subtree.
  98   /// This mutable array is updated during scheduling.
  99   std::vector<unsigned> SubtreeConnectLevels;
 100
 101 public:
 102   SchedDFSResult(bool IsBU, unsigned lim)
 103     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
 104
 105   /// \brief Clear the results.
 106   void clear() {
 107     DFSData.clear();
 108     SubtreeConnections.clear();
 109     SubtreeConnectLevels.clear();
 110   }
 111
 112   /// \brief Initialize the result data with the size of the DAG.
 113   void resize(unsigned NumSUnits) {
 114     DFSData.resize(NumSUnits);
 115   }
 116
 117   /// \brief Compute various metrics for the DAG with given roots.
 118   void compute(ArrayRef<SUnit *> Roots);
 119
 120   /// \brief Get the ILP value for a DAG node.
 121   ///
 122   /// A leaf node has an ILP of 1/1.
 123   ILPValue getILP(const SUnit *SU) {
 124     return ILPValue(DFSData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
 125   }
 126
 127   /// \brief The number of subtrees detected in this DAG.
 128   unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
 129
 130   /// \brief Get the ID of the subtree the given DAG node belongs to.
 131   unsigned getSubtreeID(const SUnit *SU) {
 132     return DFSData[SU->NodeNum].SubtreeID;
 133   }
 134
 135   /// \brief Get the connection level of a subtree.
 136   ///
 137   /// For bottom-up trees, the connection level is the latency depth (in cycles)
 138   /// of the deepest connection to another subtree.
 139   unsigned getSubtreeLevel(unsigned SubtreeID) {
 140     return SubtreeConnectLevels[SubtreeID];
 141   }
 142
 143   /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
 144   /// initially scheduled.
 145   void scheduleTree(unsigned SubtreeID);
 146 };
 147
 148 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
 149
 150 } // namespace llvm
 151
 152 #endif