llvm/CodeGen/ScheduleDFS.h

0001 //===- ScheduleDFS.h - ILP metric for ScheduleDAGInstrs ---------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Definition of an ILP metric for machine level instruction scheduling.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CODEGEN_SCHEDULEDFS_H
0014 #define LLVM_CODEGEN_SCHEDULEDFS_H
0015
0016 #include "llvm/ADT/SmallVector.h"
0017 #include "llvm/CodeGen/ScheduleDAG.h"
0018 #include <cassert>
0019 #include <cstdint>
0020 #include <vector>
0021
0022 namespace llvm {
0023
0024 template <typename T> class ArrayRef;
0025 class raw_ostream;
0026
0027 /// Represent the ILP of the subDAG rooted at a DAG node.
0028 ///
0029 /// ILPValues summarize the DAG subtree rooted at each node. ILPValues are
0030 /// valid for all nodes regardless of their subtree membership.
0031 ///
0032 /// When computed using bottom-up DFS, this metric assumes that the DAG is a
0033 /// forest of trees with roots at the bottom of the schedule branching upward.
0034 struct ILPValue {
0035   unsigned InstrCount;
0036   /// Length may either correspond to depth or height, depending on direction,
0037   /// and cycles or nodes depending on context.
0038   unsigned Length;
0039
0040   ILPValue(unsigned count, unsigned length):
0041     InstrCount(count), Length(length) {}
0042
0043   // Order by the ILP metric's value.
0044   bool operator<(ILPValue RHS) const {
0045     return (uint64_t)InstrCount * RHS.Length
0046       < (uint64_t)Length * RHS.InstrCount;
0047   }
0048   bool operator>(ILPValue RHS) const {
0049     return RHS < *this;
0050   }
0051   bool operator<=(ILPValue RHS) const {
0052     return (uint64_t)InstrCount * RHS.Length
0053       <= (uint64_t)Length * RHS.InstrCount;
0054   }
0055   bool operator>=(ILPValue RHS) const {
0056     return RHS <= *this;
0057   }
0058
0059   void print(raw_ostream &OS) const;
0060
0061   void dump() const;
0062 };
0063
0064 /// Compute the values of each DAG node for various metrics during DFS.
0065 class SchedDFSResult {
0066   friend class SchedDFSImpl;
0067
0068   static const unsigned InvalidSubtreeID = ~0u;
0069
0070   /// Per-SUnit data computed during DFS for various metrics.
0071   ///
0072   /// A node's SubtreeID is set to itself when it is visited to indicate that it
0073   /// is the root of a subtree. Later it is set to its parent to indicate an
0074   /// interior node. Finally, it is set to a representative subtree ID during
0075   /// finalization.
0076   struct NodeData {
0077     unsigned InstrCount = 0;
0078     unsigned SubtreeID = InvalidSubtreeID;
0079
0080     NodeData() = default;
0081   };
0082
0083   /// Per-Subtree data computed during DFS.
0084   struct TreeData {
0085     unsigned ParentTreeID = InvalidSubtreeID;
0086     unsigned SubInstrCount = 0;
0087
0088     TreeData() = default;
0089   };
0090
0091   /// Record a connection between subtrees and the connection level.
0092   struct Connection {
0093     unsigned TreeID;
0094     unsigned Level;
0095
0096     Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
0097   };
0098
0099   bool IsBottomUp;
0100   unsigned SubtreeLimit;
0101   /// DFS results for each SUnit in this DAG.
0102   std::vector<NodeData> DFSNodeData;
0103
0104   // Store per-tree data indexed on tree ID,
0105   SmallVector<TreeData, 16> DFSTreeData;
0106
0107   // For each subtree discovered during DFS, record its connections to other
0108   // subtrees.
0109   std::vector<SmallVector<Connection, 4>> SubtreeConnections;
0110
0111   /// Cache the current connection level of each subtree.
0112   /// This mutable array is updated during scheduling.
0113   std::vector<unsigned> SubtreeConnectLevels;
0114
0115 public:
0116   SchedDFSResult(bool IsBU, unsigned lim)
0117     : IsBottomUp(IsBU), SubtreeLimit(lim) {}
0118
0119   /// Get the node cutoff before subtrees are considered significant.
0120   unsigned getSubtreeLimit() const { return SubtreeLimit; }
0121
0122   /// Return true if this DFSResult is uninitialized.
0123   ///
0124   /// resize() initializes DFSResult, while compute() populates it.
0125   bool empty() const { return DFSNodeData.empty(); }
0126
0127   /// Clear the results.
0128   void clear() {
0129     DFSNodeData.clear();
0130     DFSTreeData.clear();
0131     SubtreeConnections.clear();
0132     SubtreeConnectLevels.clear();
0133   }
0134
0135   /// Initialize the result data with the size of the DAG.
0136   void resize(unsigned NumSUnits) {
0137     DFSNodeData.resize(NumSUnits);
0138   }
0139
0140   /// Compute various metrics for the DAG with given roots.
0141   void compute(ArrayRef<SUnit> SUnits);
0142
0143   /// Get the number of instructions in the given subtree and its
0144   /// children.
0145   unsigned getNumInstrs(const SUnit *SU) const {
0146     return DFSNodeData[SU->NodeNum].InstrCount;
0147   }
0148
0149   /// Get the number of instructions in the given subtree not including
0150   /// children.
0151   unsigned getNumSubInstrs(unsigned SubtreeID) const {
0152     return DFSTreeData[SubtreeID].SubInstrCount;
0153   }
0154
0155   /// Get the ILP value for a DAG node.
0156   ///
0157   /// A leaf node has an ILP of 1/1.
0158   ILPValue getILP(const SUnit *SU) const {
0159     return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
0160   }
0161
0162   /// The number of subtrees detected in this DAG.
0163   unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
0164
0165   /// Get the ID of the subtree the given DAG node belongs to.
0166   ///
0167   /// For convenience, if DFSResults have not been computed yet, give everything
0168   /// tree ID 0.
0169   unsigned getSubtreeID(const SUnit *SU) const {
0170     if (empty())
0171       return 0;
0172     assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
0173     return DFSNodeData[SU->NodeNum].SubtreeID;
0174   }
0175
0176   /// Get the connection level of a subtree.
0177   ///
0178   /// For bottom-up trees, the connection level is the latency depth (in cycles)
0179   /// of the deepest connection to another subtree.
0180   unsigned getSubtreeLevel(unsigned SubtreeID) const {
0181     return SubtreeConnectLevels[SubtreeID];
0182   }
0183
0184   /// Scheduler callback to update SubtreeConnectLevels when a tree is
0185   /// initially scheduled.
0186   void scheduleTree(unsigned SubtreeID);
0187 };
0188
0189 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
0190
0191 } // end namespace llvm
0192
0193 #endif // LLVM_CODEGEN_SCHEDULEDFS_H