Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/ScheduleDFS.h
Line
Count
Source (jump to first uncovered line)
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
/// 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
426
    InstrCount(count), Length(length) {}
43
44
  // Order by the ILP metric's value.
45
213
  bool operator<(ILPValue RHS) const {
46
213
    return (uint64_t)InstrCount * RHS.Length
47
213
      < (uint64_t)Length * RHS.InstrCount;
48
213
  }
49
88
  bool operator>(ILPValue RHS) const {
50
88
    return RHS < *this;
51
88
  }
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
/// 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
  /// 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
  /// 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
  /// 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
8
    : IsBottomUp(IsBU), SubtreeLimit(lim) {}
119
120
  /// Get the node cutoff before subtrees are considered significant.
121
  unsigned getSubtreeLimit() const { return SubtreeLimit; }
122
123
  /// Return true if this DFSResult is uninitialized.
124
  ///
125
  /// resize() initializes DFSResult, while compute() populates it.
126
828
  bool empty() const { return DFSNodeData.empty(); }
127
128
  /// Clear the results.
129
10
  void clear() {
130
10
    DFSNodeData.clear();
131
10
    DFSTreeData.clear();
132
10
    SubtreeConnections.clear();
133
10
    SubtreeConnectLevels.clear();
134
10
  }
135
136
  /// Initialize the result data with the size of the DAG.
137
10
  void resize(unsigned NumSUnits) {
138
10
    DFSNodeData.resize(NumSUnits);
139
10
  }
140
141
  /// Compute various metrics for the DAG with given roots.
142
  void compute(ArrayRef<SUnit> SUnits);
143
144
  /// 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
  /// 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
  /// Get the ILP value for a DAG node.
157
  ///
158
  /// A leaf node has an ILP of 1/1.
159
426
  ILPValue getILP(const SUnit *SU) const {
160
426
    return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
161
426
  }
162
163
  /// The number of subtrees detected in this DAG.
164
10
  unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
165
166
  /// 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
828
  unsigned getSubtreeID(const SUnit *SU) const {
171
828
    if (empty())
172
0
      return 0;
173
828
    assert(SU->NodeNum < DFSNodeData.size() &&  "New Node");
174
828
    return DFSNodeData[SU->NodeNum].SubtreeID;
175
828
  }
176
177
  /// 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
122
  unsigned getSubtreeLevel(unsigned SubtreeID) const {
182
122
    return SubtreeConnectLevels[SubtreeID];
183
122
  }
184
185
  /// 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