1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_COMPILER_GRAPH_REDUCER_H_
#define V8_COMPILER_GRAPH_REDUCER_H_
#include "src/base/compiler-specific.h"
#include "src/common/globals.h"
#include "src/compiler/node-marker.h"
#include "src/zone/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
// Forward declarations.
class Graph;
class Node;
// NodeIds are identifying numbers for nodes that can be used to index auxiliary
// out-of-line data associated with each node.
using NodeId = uint32_t;
// Possible outcomes for decisions.
enum class Decision : uint8_t { kUnknown, kTrue, kFalse };
// Represents the result of trying to reduce a node in the graph.
class Reduction final {
public:
explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {}
Node* replacement() const { return replacement_; }
bool Changed() const { return replacement() != nullptr; }
private:
Node* replacement_;
};
// A reducer can reduce or simplify a given node based on its operator and
// inputs. This class functions as an extension point for the graph reducer for
// language-specific reductions (e.g. reduction based on types or constant
// folding of low-level operators) can be integrated into the graph reduction
// phase.
class V8_EXPORT_PRIVATE Reducer {
public:
virtual ~Reducer() = default;
// Only used for tracing, when using the --trace_turbo_reduction flag.
virtual const char* reducer_name() const = 0;
// Try to reduce a node if possible.
virtual Reduction Reduce(Node* node) = 0;
// Invoked by the {GraphReducer} when all nodes are done. Can be used to
// do additional reductions at the end, which in turn can cause a new round
// of reductions.
virtual void Finalize();
// Helper functions for subclasses to produce reductions for a node.
static Reduction NoChange() { return Reduction(); }
static Reduction Replace(Node* node) { return Reduction(node); }
static Reduction Changed(Node* node) { return Reduction(node); }
};
// An advanced reducer can also edit the graphs by changing and replacing nodes
// other than the one currently being reduced.
class AdvancedReducer : public Reducer {
public:
// Observe the actions of this reducer.
class Editor {
public:
virtual ~Editor() = default;
// Replace {node} with {replacement}.
virtual void Replace(Node* node, Node* replacement) = 0;
// Revisit the {node} again later.
virtual void Revisit(Node* node) = 0;
// Replace value uses of {node} with {value} and effect uses of {node} with
// {effect}. If {effect == nullptr}, then use the effect input to {node}.
// All control uses will be relaxed assuming {node} cannot throw.
virtual void ReplaceWithValue(Node* node, Node* value, Node* effect,
Node* control) = 0;
};
explicit AdvancedReducer(Editor* editor) : editor_(editor) {}
protected:
// Helper functions for subclasses to produce reductions for a node.
static Reduction Replace(Node* node) { return Reducer::Replace(node); }
// Helper functions for subclasses to edit the graph.
void Replace(Node* node, Node* replacement) {
DCHECK_NOT_NULL(editor_);
editor_->Replace(node, replacement);
}
void Revisit(Node* node) {
DCHECK_NOT_NULL(editor_);
editor_->Revisit(node);
}
void ReplaceWithValue(Node* node, Node* value, Node* effect = nullptr,
Node* control = nullptr) {
DCHECK_NOT_NULL(editor_);
editor_->ReplaceWithValue(node, value, effect, control);
}
// Relax the effects of {node} by immediately replacing effect and control
// uses of {node} with the effect and control input to {node}.
// TODO(turbofan): replace the effect input to {node} with {graph->start()}.
void RelaxEffectsAndControls(Node* node) {
ReplaceWithValue(node, node, nullptr, nullptr);
}
// Relax the control uses of {node} by immediately replacing them with the
// control input to {node}.
void RelaxControls(Node* node) {
ReplaceWithValue(node, node, node, nullptr);
}
private:
Editor* const editor_;
};
// Performs an iterative reduction of a node graph.
class V8_EXPORT_PRIVATE GraphReducer
: public NON_EXPORTED_BASE(AdvancedReducer::Editor) {
public:
GraphReducer(Zone* zone, Graph* graph, Node* dead = nullptr);
~GraphReducer() override;
Graph* graph() const { return graph_; }
void AddReducer(Reducer* reducer);
// Reduce a single node.
void ReduceNode(Node* const);
// Reduce the whole graph.
void ReduceGraph();
private:
enum class State : uint8_t;
struct NodeState {
Node* node;
int input_index;
};
// Reduce a single node.
Reduction Reduce(Node* const);
// Reduce the node on top of the stack.
void ReduceTop();
// Replace {node} with {replacement}.
void Replace(Node* node, Node* replacement) final;
// Replace value uses of {node} with {value} and effect uses of {node} with
// {effect}. If {effect == nullptr}, then use the effect input to {node}. All
// control uses will be relaxed assuming {node} cannot throw.
void ReplaceWithValue(Node* node, Node* value, Node* effect,
Node* control) final;
// Replace all uses of {node} with {replacement} if the id of {replacement} is
// less than or equal to {max_id}. Otherwise, replace all uses of {node} whose
// id is less than or equal to {max_id} with the {replacement}.
void Replace(Node* node, Node* replacement, NodeId max_id);
// Node stack operations.
void Pop();
void Push(Node* node);
// Revisit queue operations.
bool Recurse(Node* node);
void Revisit(Node* node) final;
Graph* const graph_;
Node* const dead_;
NodeMarker<State> state_;
ZoneVector<Reducer*> reducers_;
ZoneQueue<Node*> revisit_;
ZoneStack<NodeState> stack_;
DISALLOW_COPY_AND_ASSIGN(GraphReducer);
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COMPILER_GRAPH_REDUCER_H_
|
