Coverage Report

Created: 2019-02-21 13:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/ScheduleDFS.h
Line
Count
Source (jump to first uncovered line)
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"
18
#include "llvm/CodeGen/ScheduleDAG.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
426
    InstrCount(count), Length(length) {}
42
43
  // Order by the ILP metric's value.
44
213
  bool operator<(ILPValue RHS) const {
45
213
    return (uint64_t)InstrCount * RHS.Length
46
213
      < (uint64_t)Length * RHS.InstrCount;
47
213
  }
48
88
  bool operator>(ILPValue RHS) const {
49
88
    return RHS < *this;
50
88
  }
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.
65
class SchedDFSResult {
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
176
    NodeData() = default;
81
  };
82
83
  /// Per-Subtree data computed during DFS.
84
  struct TreeData {
85
    unsigned ParentTreeID = InvalidSubtreeID;
86
    unsigned SubInstrCount = 0;
87
88
38
    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
2
    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
8
    : 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
828
  bool empty() const { return DFSNodeData.empty(); }
126
127
  /// Clear the results.
128
10
  void clear() {
129
10
    DFSNodeData.clear();
130
10
    DFSTreeData.clear();
131
10
    SubtreeConnections.clear();
132
10
    SubtreeConnectLevels.clear();
133
10
  }
134
135
  /// Initialize the result data with the size of the DAG.
136
10
  void resize(unsigned NumSUnits) {
137
10
    DFSNodeData.resize(NumSUnits);
138
10
  }
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
426
  ILPValue getILP(const SUnit *SU) const {
159
426
    return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
160
426
  }
161
162
  /// The number of subtrees detected in this DAG.
163
10
  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
828
  unsigned getSubtreeID(const SUnit *SU) const {
170
828
    if (empty())
171
0
      return 0;
172
828
    assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
173
828
    return DFSNodeData[SU->NodeNum].SubtreeID;
174
828
  }
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
122
  unsigned getSubtreeLevel(unsigned SubtreeID) const {
181
122
    return SubtreeConnectLevels[SubtreeID];
182
122
  }
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