LLVM  10.0.0svn
ScheduleDFS.h
Go to the documentation of this file.
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"
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.
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
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
Definition: ScheduleDFS.h:145
void clear()
Clear the results.
Definition: ScheduleDFS.h:128
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:398
Represent the ILP of the subDAG rooted at a DAG node.
Definition: ScheduleDFS.h:34
bool operator<(ILPValue RHS) const
Definition: ScheduleDFS.h:44
unsigned getNumSubInstrs(unsigned SubtreeID) const
Get the number of instructions in the given subtree not including children.
Definition: ScheduleDFS.h:151
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:65
void print(raw_ostream &OS) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
Definition: ScheduleDFS.h:169
ILPValue(unsigned count, unsigned length)
Definition: ScheduleDFS.h:40
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
Definition: ScheduleDFS.h:163
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:1231
void resize(unsigned NumSUnits)
Initialize the result data with the size of the DAG.
Definition: ScheduleDFS.h:136
bool operator<=(ILPValue RHS) const
Definition: ScheduleDFS.h:51
bool empty() const
Return true if this DFSResult is uninitialized.
Definition: ScheduleDFS.h:125
Internal state used to compute SchedDFSResult.
unsigned InstrCount
Definition: ScheduleDFS.h:35
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
unsigned Length
Length may either correspond to depth or height, depending on direction, and cycles or nodes dependin...
Definition: ScheduleDFS.h:38
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
Definition: ScheduleDFS.h:180
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
bool operator>=(ILPValue RHS) const
Definition: ScheduleDFS.h:55
SchedDFSResult(bool IsBU, unsigned lim)
Definition: ScheduleDFS.h:116
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:45
bool operator>(ILPValue RHS) const
Definition: ScheduleDFS.h:48
unsigned getSubtreeLimit() const
Get the node cutoff before subtrees are considered significant.
Definition: ScheduleDFS.h:120
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
Definition: ScheduleDFS.h:158