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