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
9#include "src/compiler/graph-inl.h"
10
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15GraphReducer::GraphReducer(Graph* graph)
16    : graph_(graph), reducers_(graph->zone()) {}
17
18
19static bool NodeIdIsLessThan(const Node* node, NodeId id) {
20  return node->id() < id;
21}
22
23
24void GraphReducer::ReduceNode(Node* node) {
25  ZoneVector<Reducer*>::iterator skip = reducers_.end();
26  static const unsigned kMaxAttempts = 16;
27  bool reduce = true;
28  for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) {
29    if (!reduce) return;
30    reduce = false;  // Assume we don't need to rerun any reducers.
31    int before = graph_->NodeCount();
32    for (ZoneVector<Reducer*>::iterator i = reducers_.begin();
33         i != reducers_.end(); ++i) {
34      if (i == skip) continue;  // Skip this reducer.
35      Reduction reduction = (*i)->Reduce(node);
36      Node* replacement = reduction.replacement();
37      if (replacement == NULL) {
38        // No change from this reducer.
39      } else if (replacement == node) {
40        // {replacement == node} represents an in-place reduction.
41        // Rerun all the reducers except the current one for this node,
42        // as now there may be more opportunities for reduction.
43        reduce = true;
44        skip = i;
45        break;
46      } else {
47        if (node == graph_->start()) graph_->SetStart(replacement);
48        if (node == graph_->end()) graph_->SetEnd(replacement);
49        // If {node} was replaced by an old node, unlink {node} and assume that
50        // {replacement} was already reduced and finish.
51        if (replacement->id() < before) {
52          node->ReplaceUses(replacement);
53          node->Kill();
54          return;
55        }
56        // Otherwise, {node} was replaced by a new node. Replace all old uses of
57        // {node} with {replacement}. New nodes created by this reduction can
58        // use {node}.
59        node->ReplaceUsesIf(
60            std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement);
61        // Unlink {node} if it's no longer used.
62        if (node->uses().empty()) {
63          node->Kill();
64        }
65        // Rerun all the reductions on the {replacement}.
66        skip = reducers_.end();
67        node = replacement;
68        reduce = true;
69        break;
70      }
71    }
72  }
73}
74
75
76// A helper class to reuse the node traversal algorithm.
77struct GraphReducerVisitor FINAL : public NullNodeVisitor {
78  explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {}
79  GenericGraphVisit::Control Post(Node* node) {
80    reducer_->ReduceNode(node);
81    return GenericGraphVisit::CONTINUE;
82  }
83  GraphReducer* reducer_;
84};
85
86
87void GraphReducer::ReduceGraph() {
88  GraphReducerVisitor visitor(this);
89  // Perform a post-order reduction of all nodes starting from the end.
90  graph()->VisitNodeInputsFromEnd(&visitor);
91}
92
93
94// TODO(titzer): partial graph reductions.
95
96}  // namespace compiler
97}  // namespace internal
98}  // namespace v8
99