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
14namespace v8 {
15namespace internal {
16namespace compiler {
17
18enum class GraphReducer::State : uint8_t {
19  kUnvisited,
20  kRevisit,
21  kOnStack,
22  kVisited
23};
24
25
26void Reducer::Finalize() {}
27
28GraphReducer::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
40GraphReducer::~GraphReducer() {}
41
42
43void GraphReducer::AddReducer(Reducer* reducer) {
44  reducers_.push_back(reducer);
45}
46
47
48void 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_.top();
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
78void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
79
80
81Reduction 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        skip = i;
93        i = reducers_.begin();
94        continue;
95      } else {
96        // {node} was replaced by another node.
97        return reduction;
98      }
99    }
100    ++i;
101  }
102  if (skip == reducers_.end()) {
103    // No change from any reducer.
104    return Reducer::NoChange();
105  }
106  // At least one reducer did some in-place reduction.
107  return Reducer::Changed(node);
108}
109
110
111void GraphReducer::ReduceTop() {
112  NodeState& entry = stack_.top();
113  Node* node = entry.node;
114  DCHECK(state_.Get(node) == State::kOnStack);
115
116  if (node->IsDead()) return Pop();  // Node was killed while on stack.
117
118  Node::Inputs node_inputs = node->inputs();
119
120  // Recurse on an input if necessary.
121  int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
122  for (int i = start; i < node_inputs.count(); ++i) {
123    Node* input = node_inputs[i];
124    if (input != node && Recurse(input)) {
125      entry.input_index = i + 1;
126      return;
127    }
128  }
129  for (int i = 0; i < start; ++i) {
130    Node* input = node_inputs[i];
131    if (input != node && Recurse(input)) {
132      entry.input_index = i + 1;
133      return;
134    }
135  }
136
137  // Remember the max node id before reduction.
138  NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
139
140  // All inputs should be visited or on stack. Apply reductions to node.
141  Reduction reduction = Reduce(node);
142
143  // If there was no reduction, pop {node} and continue.
144  if (!reduction.Changed()) return Pop();
145
146  // Check if the reduction is an in-place update of the {node}.
147  Node* const replacement = reduction.replacement();
148  if (replacement == node) {
149    // In-place update of {node}, may need to recurse on an input.
150    Node::Inputs node_inputs = node->inputs();
151    for (int i = 0; i < node_inputs.count(); ++i) {
152      Node* input = node_inputs[i];
153      if (input != node && Recurse(input)) {
154        entry.input_index = i + 1;
155        return;
156      }
157    }
158  }
159
160  // After reducing the node, pop it off the stack.
161  Pop();
162
163  // Check if we have a new replacement.
164  if (replacement != node) {
165    Replace(node, replacement, max_id);
166  } else {
167    // Revisit all uses of the node.
168    for (Node* const user : node->uses()) {
169      // Don't revisit this node if it refers to itself.
170      if (user != node) Revisit(user);
171    }
172  }
173}
174
175
176void GraphReducer::Replace(Node* node, Node* replacement) {
177  Replace(node, replacement, std::numeric_limits<NodeId>::max());
178}
179
180
181void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
182  if (FLAG_trace_turbo_reduction) {
183    OFStream os(stdout);
184    os << "- Replacing " << *node << " with " << *replacement << std::endl;
185  }
186  if (node == graph()->start()) graph()->SetStart(replacement);
187  if (node == graph()->end()) graph()->SetEnd(replacement);
188  if (replacement->id() <= max_id) {
189    // {replacement} is an old node, so unlink {node} and assume that
190    // {replacement} was already reduced and finish.
191    for (Edge edge : node->use_edges()) {
192      Node* const user = edge.from();
193      Verifier::VerifyEdgeInputReplacement(edge, replacement);
194      edge.UpdateTo(replacement);
195      // Don't revisit this node if it refers to itself.
196      if (user != node) Revisit(user);
197    }
198    node->Kill();
199  } else {
200    // Replace all old uses of {node} with {replacement}, but allow new nodes
201    // created by this reduction to use {node}.
202    for (Edge edge : node->use_edges()) {
203      Node* const user = edge.from();
204      if (user->id() <= max_id) {
205        edge.UpdateTo(replacement);
206        // Don't revisit this node if it refers to itself.
207        if (user != node) Revisit(user);
208      }
209    }
210    // Unlink {node} if it's no longer used.
211    if (node->uses().empty()) node->Kill();
212
213    // If there was a replacement, reduce it after popping {node}.
214    Recurse(replacement);
215  }
216}
217
218
219void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
220                                    Node* control) {
221  if (effect == nullptr && node->op()->EffectInputCount() > 0) {
222    effect = NodeProperties::GetEffectInput(node);
223  }
224  if (control == nullptr && node->op()->ControlInputCount() > 0) {
225    control = NodeProperties::GetControlInput(node);
226  }
227
228  // Requires distinguishing between value, effect and control edges.
229  for (Edge edge : node->use_edges()) {
230    Node* const user = edge.from();
231    DCHECK(!user->IsDead());
232    if (NodeProperties::IsControlEdge(edge)) {
233      if (user->opcode() == IrOpcode::kIfSuccess) {
234        Replace(user, control);
235      } else if (user->opcode() == IrOpcode::kIfException) {
236        DCHECK_NOT_NULL(dead_);
237        edge.UpdateTo(dead_);
238        Revisit(user);
239      } else {
240        DCHECK_NOT_NULL(control);
241        edge.UpdateTo(control);
242        Revisit(user);
243        // TODO(jarin) Check that the node cannot throw (otherwise, it
244        // would have to be connected via IfSuccess/IfException).
245      }
246    } else if (NodeProperties::IsEffectEdge(edge)) {
247      DCHECK_NOT_NULL(effect);
248      edge.UpdateTo(effect);
249      Revisit(user);
250    } else {
251      DCHECK_NOT_NULL(value);
252      edge.UpdateTo(value);
253      Revisit(user);
254    }
255  }
256}
257
258
259void GraphReducer::Pop() {
260  Node* node = stack_.top().node;
261  state_.Set(node, State::kVisited);
262  stack_.pop();
263}
264
265
266void GraphReducer::Push(Node* const node) {
267  DCHECK(state_.Get(node) != State::kOnStack);
268  state_.Set(node, State::kOnStack);
269  stack_.push({node, 0});
270}
271
272
273bool GraphReducer::Recurse(Node* node) {
274  if (state_.Get(node) > State::kRevisit) return false;
275  Push(node);
276  return true;
277}
278
279
280void GraphReducer::Revisit(Node* node) {
281  if (state_.Get(node) == State::kVisited) {
282    state_.Set(node, State::kRevisit);
283    revisit_.push(node);
284  }
285}
286
287}  // namespace compiler
288}  // namespace internal
289}  // namespace v8
290