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