include/llvm/CodeGen/ScheduleDFS.h

   1 //===- ScheduleDFS.h - ILP metric for ScheduleDAGInstrs ---------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Definition of an ILP metric for machine level instruction scheduling.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_CODEGEN_SCHEDULEDFS_H
  14 #define LLVM_CODEGEN_SCHEDULEDFS_H
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include <cassert>
  20 #include <cstdint>
  21 #include <vector>
  22
  23 namespace llvm {
  24
  25 class raw_ostream;
  26
  27 /// Represent the ILP of the subDAG rooted at a DAG node.
  28 ///
  29 /// ILPValues summarize the DAG subtree rooted at each node. ILPValues are
  30 /// valid for all nodes regardless of their subtree membership.
  31 ///
  32 /// When computed using bottom-up DFS, this metric assumes that the DAG is a
  33 /// forest of trees with roots at the bottom of the schedule branching upward.
  34 struct ILPValue {
  35   unsigned InstrCount;
  36   /// Length may either correspond to depth or height, depending on direction,
  37   /// and cycles or nodes depending on context.
  38   unsigned Length;
  39
  40   ILPValue(unsigned count, unsigned length):
  41     InstrCount(count), Length(length) {}
  42
  43   // Order by the ILP metric's value.
  44   bool operator<(ILPValue RHS) const {
  45     return (uint64_t)InstrCount * RHS.Length
  46       < (uint64_t)Length * RHS.InstrCount;
  47   }
  48   bool operator>(ILPValue RHS) const {
  49     return RHS < *this;
  50   }
  51   bool operator<=(ILPValue RHS) const {
  52     return (uint64_t)InstrCount * RHS.Length
  53       <= (uint64_t)Length * RHS.InstrCount;
  54   }
  55   bool operator>=(ILPValue RHS) const {
  56     return RHS <= *this;
  57   }
  58
  59   void print(raw_ostream &OS) const;
  60
  61   void dump() const;
  62 };
  63
  64 /// Compute the values of each DAG node for various metrics during DFS.
  65 class SchedDFSResult {
  66   friend class SchedDFSImpl;
  67
  68   static const unsigned InvalidSubtreeID = ~0u;
  69
  70   /// Per-SUnit data computed during DFS for various metrics.
  71   ///
  72   /// A node's SubtreeID is set to itself when it is visited to indicate that it
  73   /// is the root of a subtree. Later it is set to its parent to indicate an
  74   /// interior node. Finally, it is set to a representative subtree ID during
  75   /// finalization.
  76   struct NodeData {
  77     unsigned InstrCount = 0;
  78     unsigned SubtreeID = InvalidSubtreeID;
  79
  80     NodeData() = default;
  81   };
  82
  83   /// Per-Subtree data computed during DFS.
  84   struct TreeData {
  85     unsigned ParentTreeID = InvalidSubtreeID;
  86     unsigned SubInstrCount = 0;
  87
  88     TreeData() = default;
  89   };
  90
  91   /// Record a connection between subtrees and the connection level.
  92   struct Connection {
  93     unsigned TreeID;
  94     unsigned Level;
  95
  96     Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
  97   };
  98
  99   bool IsBottomUp;
 100   unsigned SubtreeLimit;
 101   /// DFS results for each SUnit in this DAG.
 102   std::vector<NodeData> DFSNodeData;
 103
 104   // Store per-tree data indexed on tree ID,
 105   SmallVector<TreeData, 16> DFSTreeData;
 106
 107   // For each subtree discovered during DFS, record its connections to other
 108   // subtrees.
 109   std::vector<SmallVector<Connection, 4>> SubtreeConnections;
 110
 111   /// Cache the current connection level of each subtree.
 112   /// This mutable array is updated during scheduling.
 113   std::vector<unsigned> SubtreeConnectLevels;
 114
 115 public:
 116   SchedDFSResult(bool IsBU, unsigned lim)
 117     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
 118
 119   /// Get the node cutoff before subtrees are considered significant.
 120   unsigned getSubtreeLimit() const { return SubtreeLimit; }
 121
 122   /// Return true if this DFSResult is uninitialized.
 123   ///
 124   /// resize() initializes DFSResult, while compute() populates it.
 125   bool empty() const { return DFSNodeData.empty(); }
 126
 127   /// Clear the results.
 128   void clear() {
 129     DFSNodeData.clear();
 130     DFSTreeData.clear();
 131     SubtreeConnections.clear();
 132     SubtreeConnectLevels.clear();
 133   }
 134
 135   /// Initialize the result data with the size of the DAG.
 136   void resize(unsigned NumSUnits) {
 137     DFSNodeData.resize(NumSUnits);
 138   }
 139
 140   /// Compute various metrics for the DAG with given roots.
 141   void compute(ArrayRef<SUnit> SUnits);
 142
 143   /// Get the number of instructions in the given subtree and its
 144   /// children.
 145   unsigned getNumInstrs(const SUnit *SU) const {
 146     return DFSNodeData[SU->NodeNum].InstrCount;
 147   }
 148
 149   /// Get the number of instructions in the given subtree not including
 150   /// children.
 151   unsigned getNumSubInstrs(unsigned SubtreeID) const {
 152     return DFSTreeData[SubtreeID].SubInstrCount;
 153   }
 154
 155   /// Get the ILP value for a DAG node.
 156   ///
 157   /// A leaf node has an ILP of 1/1.
 158   ILPValue getILP(const SUnit *SU) const {
 159     return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
 160   }
 161
 162   /// The number of subtrees detected in this DAG.
 163   unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
 164
 165   /// Get the ID of the subtree the given DAG node belongs to.
 166   ///
 167   /// For convenience, if DFSResults have not been computed yet, give everything
 168   /// tree ID 0.
 169   unsigned getSubtreeID(const SUnit *SU) const {
 170     if (empty())
 171       return 0;
 172     assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
 173     return DFSNodeData[SU->NodeNum].SubtreeID;
 174   }
 175
 176   /// Get the connection level of a subtree.
 177   ///
 178   /// For bottom-up trees, the connection level is the latency depth (in cycles)
 179   /// of the deepest connection to another subtree.
 180   unsigned getSubtreeLevel(unsigned SubtreeID) const {
 181     return SubtreeConnectLevels[SubtreeID];
 182   }
 183
 184   /// Scheduler callback to update SubtreeConnectLevels when a tree is
 185   /// initially scheduled.
 186   void scheduleTree(unsigned SubtreeID);
 187 };
 188
 189 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
 190
 191 } // end namespace llvm
 192
 193 #endif // LLVM_CODEGEN_SCHEDULEDFS_H