LLVM  6.0.0svn
ScheduleDFS.h
Go to the documentation of this file.
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"
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  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.
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  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  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  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 } // end namespace llvm
193 
194 #endif // LLVM_CODEGEN_SCHEDULEDFS_H
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
Definition: ScheduleDFS.h:146
void clear()
Clear the results.
Definition: ScheduleDFS.h:129
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:403
Represent the ILP of the subDAG rooted at a DAG node.
Definition: ScheduleDFS.h:35
bool operator<(ILPValue RHS) const
Definition: ScheduleDFS.h:45
unsigned getNumSubInstrs(unsigned SubtreeID) const
Get the number of instructions in the given subtree not including children.
Definition: ScheduleDFS.h:152
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:66
void print(raw_ostream &OS) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
Definition: ScheduleDFS.h:170
ILPValue(unsigned count, unsigned length)
Definition: ScheduleDFS.h:41
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
Definition: ScheduleDFS.h:164
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:874
void resize(unsigned NumSUnits)
Initialize the result data with the size of the DAG.
Definition: ScheduleDFS.h:137
bool operator<=(ILPValue RHS) const
Definition: ScheduleDFS.h:52
bool empty() const
Return true if this DFSResult is uninitialized.
Definition: ScheduleDFS.h:126
Internal state used to compute SchedDFSResult.
unsigned InstrCount
Definition: ScheduleDFS.h:36
unsigned Length
Length may either correspond to depth or height, depending on direction, and cycles or nodes dependin...
Definition: ScheduleDFS.h:39
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
Definition: ScheduleDFS.h:181
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:269
bool operator>=(ILPValue RHS) const
Definition: ScheduleDFS.h:56
SchedDFSResult(bool IsBU, unsigned lim)
Definition: ScheduleDFS.h:117
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool operator>(ILPValue RHS) const
Definition: ScheduleDFS.h:49
unsigned getSubtreeLimit() const
Get the node cutoff before subtrees are considered significant.
Definition: ScheduleDFS.h:121
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:247
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
Definition: ScheduleDFS.h:159