1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <functional>
6 #include <limits>
7
8 #include "src/compiler/graph.h"
9 #include "src/compiler/graph-reducer.h"
10 #include "src/compiler/node.h"
11 #include "src/compiler/node-properties.h"
12 #include "src/compiler/verifier.h"
13
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17
18 enum class GraphReducer::State : uint8_t {
19 kUnvisited,
20 kRevisit,
21 kOnStack,
22 kVisited
23 };
24
25
Finalize()26 void Reducer::Finalize() {}
27
GraphReducer(Zone * zone,Graph * graph,Node * dead)28 GraphReducer::GraphReducer(Zone* zone, Graph* graph, Node* dead)
29 : graph_(graph),
30 dead_(dead),
31 state_(graph, 4),
32 reducers_(zone),
33 revisit_(zone),
34 stack_(zone) {
35 if (dead != nullptr) {
36 NodeProperties::SetType(dead_, Type::None());
37 }
38 }
39
~GraphReducer()40 GraphReducer::~GraphReducer() {}
41
42
AddReducer(Reducer * reducer)43 void GraphReducer::AddReducer(Reducer* reducer) {
44 reducers_.push_back(reducer);
45 }
46
47
ReduceNode(Node * node)48 void GraphReducer::ReduceNode(Node* node) {
49 DCHECK(stack_.empty());
50 DCHECK(revisit_.empty());
51 Push(node);
52 for (;;) {
53 if (!stack_.empty()) {
54 // Process the node on the top of the stack, potentially pushing more or
55 // popping the node off the stack.
56 ReduceTop();
57 } else if (!revisit_.empty()) {
58 // If the stack becomes empty, revisit any nodes in the revisit queue.
59 Node* const node = revisit_.front();
60 revisit_.pop();
61 if (state_.Get(node) == State::kRevisit) {
62 // state can change while in queue.
63 Push(node);
64 }
65 } else {
66 // Run all finalizers.
67 for (Reducer* const reducer : reducers_) reducer->Finalize();
68
69 // Check if we have new nodes to revisit.
70 if (revisit_.empty()) break;
71 }
72 }
73 DCHECK(revisit_.empty());
74 DCHECK(stack_.empty());
75 }
76
77
ReduceGraph()78 void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
79
80
Reduce(Node * const node)81 Reduction GraphReducer::Reduce(Node* const node) {
82 auto skip = reducers_.end();
83 for (auto i = reducers_.begin(); i != reducers_.end();) {
84 if (i != skip) {
85 Reduction reduction = (*i)->Reduce(node);
86 if (!reduction.Changed()) {
87 // No change from this reducer.
88 } else if (reduction.replacement() == node) {
89 // {replacement} == {node} represents an in-place reduction. Rerun
90 // all the other reducers for this node, as now there may be more
91 // opportunities for reduction.
92 if (FLAG_trace_turbo_reduction) {
93 StdoutStream{} << "- In-place update of " << *node << " by reducer "
94 << (*i)->reducer_name() << std::endl;
95 }
96 skip = i;
97 i = reducers_.begin();
98 continue;
99 } else {
100 // {node} was replaced by another node.
101 if (FLAG_trace_turbo_reduction) {
102 StdoutStream{} << "- Replacement of " << *node << " with "
103 << *(reduction.replacement()) << " by reducer "
104 << (*i)->reducer_name() << std::endl;
105 }
106 return reduction;
107 }
108 }
109 ++i;
110 }
111 if (skip == reducers_.end()) {
112 // No change from any reducer.
113 return Reducer::NoChange();
114 }
115 // At least one reducer did some in-place reduction.
116 return Reducer::Changed(node);
117 }
118
119
ReduceTop()120 void GraphReducer::ReduceTop() {
121 NodeState& entry = stack_.top();
122 Node* node = entry.node;
123 DCHECK_EQ(State::kOnStack, state_.Get(node));
124
125 if (node->IsDead()) return Pop(); // Node was killed while on stack.
126
127 Node::Inputs node_inputs = node->inputs();
128
129 // Recurse on an input if necessary.
130 int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
131 for (int i = start; i < node_inputs.count(); ++i) {
132 Node* input = node_inputs[i];
133 if (input != node && Recurse(input)) {
134 entry.input_index = i + 1;
135 return;
136 }
137 }
138 for (int i = 0; i < start; ++i) {
139 Node* input = node_inputs[i];
140 if (input != node && Recurse(input)) {
141 entry.input_index = i + 1;
142 return;
143 }
144 }
145
146 // Remember the max node id before reduction.
147 NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
148
149 // All inputs should be visited or on stack. Apply reductions to node.
150 Reduction reduction = Reduce(node);
151
152 // If there was no reduction, pop {node} and continue.
153 if (!reduction.Changed()) return Pop();
154
155 // Check if the reduction is an in-place update of the {node}.
156 Node* const replacement = reduction.replacement();
157 if (replacement == node) {
158 // In-place update of {node}, may need to recurse on an input.
159 Node::Inputs node_inputs = node->inputs();
160 for (int i = 0; i < node_inputs.count(); ++i) {
161 Node* input = node_inputs[i];
162 if (input != node && Recurse(input)) {
163 entry.input_index = i + 1;
164 return;
165 }
166 }
167 }
168
169 // After reducing the node, pop it off the stack.
170 Pop();
171
172 // Check if we have a new replacement.
173 if (replacement != node) {
174 Replace(node, replacement, max_id);
175 } else {
176 // Revisit all uses of the node.
177 for (Node* const user : node->uses()) {
178 // Don't revisit this node if it refers to itself.
179 if (user != node) Revisit(user);
180 }
181 }
182 }
183
184
Replace(Node * node,Node * replacement)185 void GraphReducer::Replace(Node* node, Node* replacement) {
186 Replace(node, replacement, std::numeric_limits<NodeId>::max());
187 }
188
189
Replace(Node * node,Node * replacement,NodeId max_id)190 void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
191 if (node == graph()->start()) graph()->SetStart(replacement);
192 if (node == graph()->end()) graph()->SetEnd(replacement);
193 if (replacement->id() <= max_id) {
194 // {replacement} is an old node, so unlink {node} and assume that
195 // {replacement} was already reduced and finish.
196 for (Edge edge : node->use_edges()) {
197 Node* const user = edge.from();
198 Verifier::VerifyEdgeInputReplacement(edge, replacement);
199 edge.UpdateTo(replacement);
200 // Don't revisit this node if it refers to itself.
201 if (user != node) Revisit(user);
202 }
203 node->Kill();
204 } else {
205 // Replace all old uses of {node} with {replacement}, but allow new nodes
206 // created by this reduction to use {node}.
207 for (Edge edge : node->use_edges()) {
208 Node* const user = edge.from();
209 if (user->id() <= max_id) {
210 edge.UpdateTo(replacement);
211 // Don't revisit this node if it refers to itself.
212 if (user != node) Revisit(user);
213 }
214 }
215 // Unlink {node} if it's no longer used.
216 if (node->uses().empty()) node->Kill();
217
218 // If there was a replacement, reduce it after popping {node}.
219 Recurse(replacement);
220 }
221 }
222
223
ReplaceWithValue(Node * node,Node * value,Node * effect,Node * control)224 void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
225 Node* control) {
226 if (effect == nullptr && node->op()->EffectInputCount() > 0) {
227 effect = NodeProperties::GetEffectInput(node);
228 }
229 if (control == nullptr && node->op()->ControlInputCount() > 0) {
230 control = NodeProperties::GetControlInput(node);
231 }
232
233 // Requires distinguishing between value, effect and control edges.
234 for (Edge edge : node->use_edges()) {
235 Node* const user = edge.from();
236 DCHECK(!user->IsDead());
237 if (NodeProperties::IsControlEdge(edge)) {
238 if (user->opcode() == IrOpcode::kIfSuccess) {
239 Replace(user, control);
240 } else if (user->opcode() == IrOpcode::kIfException) {
241 DCHECK_NOT_NULL(dead_);
242 edge.UpdateTo(dead_);
243 Revisit(user);
244 } else {
245 DCHECK_NOT_NULL(control);
246 edge.UpdateTo(control);
247 Revisit(user);
248 }
249 } else if (NodeProperties::IsEffectEdge(edge)) {
250 DCHECK_NOT_NULL(effect);
251 edge.UpdateTo(effect);
252 Revisit(user);
253 } else {
254 DCHECK_NOT_NULL(value);
255 edge.UpdateTo(value);
256 Revisit(user);
257 }
258 }
259 }
260
261
Pop()262 void GraphReducer::Pop() {
263 Node* node = stack_.top().node;
264 state_.Set(node, State::kVisited);
265 stack_.pop();
266 }
267
268
Push(Node * const node)269 void GraphReducer::Push(Node* const node) {
270 DCHECK_NE(State::kOnStack, state_.Get(node));
271 state_.Set(node, State::kOnStack);
272 stack_.push({node, 0});
273 }
274
275
Recurse(Node * node)276 bool GraphReducer::Recurse(Node* node) {
277 if (state_.Get(node) > State::kRevisit) return false;
278 Push(node);
279 return true;
280 }
281
282
Revisit(Node * node)283 void GraphReducer::Revisit(Node* node) {
284 if (state_.Get(node) == State::kVisited) {
285 state_.Set(node, State::kRevisit);
286 revisit_.push(node);
287 }
288 }
289
290 } // namespace compiler
291 } // namespace internal
292 } // namespace v8
293