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
18namespace v8 {
19namespace internal {
20namespace compiler {
21
22enum class GraphReducer::State : uint8_t {
23  kUnvisited,
24  kRevisit,
25  kOnStack,
26  kVisited
27};
28
29
30void Reducer::Finalize() {}
31
32Reduction 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
42GraphReducer::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
59GraphReducer::~GraphReducer() = default;
60
61
62void GraphReducer::AddReducer(Reducer* reducer) {
63  reducers_.push_back(reducer);
64}
65
66
67void 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
97void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
98
99
100Reduction 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
148void 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
212void GraphReducer::Replace(Node* node, Node* replacement) {
213  Replace(node, replacement, std::numeric_limits<NodeId>::max());
214}
215
216
217void 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
251void 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
289void GraphReducer::Pop() {
290  Node* node = stack_.top().node;
291  state_.Set(node, State::kVisited);
292  stack_.pop();
293}
294
295
296void 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
303bool GraphReducer::Recurse(Node* node) {
304  if (state_.Get(node) > State::kRevisit) return false;
305  Push(node);
306  return true;
307}
308
309
310void 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