LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - ScheduleDFS.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 20 20 100.0 %
Date: 2017-09-14 15:23:50 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/ADT/ArrayRef.h"
      18             : #include "llvm/ADT/SmallVector.h"
      19             : #include "llvm/CodeGen/ScheduleDAG.h"
      20             : #include <cassert>
      21             : #include <cstdint>
      22             : #include <vector>
      23             : 
      24             : namespace llvm {
      25             : 
      26             : class raw_ostream;
      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         199 :     return (uint64_t)InstrCount * RHS.Length
      47         199 :       < (uint64_t)Length * RHS.InstrCount;
      48             :   }
      49             :   bool operator>(ILPValue RHS) const {
      50          83 :     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          32 : 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 = 0;
      79             :     unsigned SubtreeID = InvalidSubtreeID;
      80             : 
      81         176 :     NodeData() = default;
      82             :   };
      83             : 
      84             :   /// \brief Per-Subtree data computed during DFS.
      85             :   struct TreeData {
      86             :     unsigned ParentTreeID = InvalidSubtreeID;
      87             :     unsigned SubInstrCount = 0;
      88             : 
      89          38 :     TreeData() = default;
      90             :   };
      91             : 
      92             :   /// \brief Record a connection between subtrees and the connection level.
      93             :   struct Connection {
      94             :     unsigned TreeID;
      95             :     unsigned Level;
      96             : 
      97           2 :     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          40 :     : 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        1552 :   bool empty() const { return DFSNodeData.empty(); }
     127             : 
     128             :   /// \brief Clear the results.
     129             :   void clear() {
     130          20 :     DFSNodeData.clear();
     131          20 :     DFSTreeData.clear();
     132          10 :     SubtreeConnections.clear();
     133          20 :     SubtreeConnectLevels.clear();
     134             :   }
     135             : 
     136             :   /// \brief Initialize the result data with the size of the DAG.
     137             :   void resize(unsigned NumSUnits) {
     138          10 :     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         398 :   ILPValue getILP(const SUnit *SU) const {
     160         796 :     return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
     161             :   }
     162             : 
     163             :   /// \brief The number of subtrees detected in this DAG.
     164          20 :   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         776 :     if (empty())
     172             :       return 0;
     173             :     assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
     174        1552 :     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         232 :     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             : } // end namespace llvm
     193             : 
     194             : #endif // LLVM_CODEGEN_SCHEDULEDFS_H

Generated by: LCOV version 1.13