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#ifndef V8_COMPILER_GRAPH_REDUCER_H_
6#define V8_COMPILER_GRAPH_REDUCER_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/compiler/node-marker.h"
10#include "src/globals.h"
11#include "src/zone/zone-containers.h"
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17// Forward declarations.
18class Graph;
19class Node;
20
21
22// NodeIds are identifying numbers for nodes that can be used to index auxiliary
23// out-of-line data associated with each node.
24typedef uint32_t NodeId;
25
26
27// Represents the result of trying to reduce a node in the graph.
28class Reduction final {
29 public:
30  explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {}
31
32  Node* replacement() const { return replacement_; }
33  bool Changed() const { return replacement() != nullptr; }
34
35 private:
36  Node* replacement_;
37};
38
39
40// A reducer can reduce or simplify a given node based on its operator and
41// inputs. This class functions as an extension point for the graph reducer for
42// language-specific reductions (e.g. reduction based on types or constant
43// folding of low-level operators) can be integrated into the graph reduction
44// phase.
45class V8_EXPORT_PRIVATE Reducer {
46 public:
47  virtual ~Reducer() {}
48
49  // Try to reduce a node if possible.
50  virtual Reduction Reduce(Node* node) = 0;
51
52  // Invoked by the {GraphReducer} when all nodes are done.  Can be used to
53  // do additional reductions at the end, which in turn can cause a new round
54  // of reductions.
55  virtual void Finalize();
56
57  // Helper functions for subclasses to produce reductions for a node.
58  static Reduction NoChange() { return Reduction(); }
59  static Reduction Replace(Node* node) { return Reduction(node); }
60  static Reduction Changed(Node* node) { return Reduction(node); }
61};
62
63
64// An advanced reducer can also edit the graphs by changing and replacing nodes
65// other than the one currently being reduced.
66class AdvancedReducer : public Reducer {
67 public:
68  // Observe the actions of this reducer.
69  class Editor {
70   public:
71    virtual ~Editor() {}
72
73    // Replace {node} with {replacement}.
74    virtual void Replace(Node* node, Node* replacement) = 0;
75    // Revisit the {node} again later.
76    virtual void Revisit(Node* node) = 0;
77    // Replace value uses of {node} with {value} and effect uses of {node} with
78    // {effect}. If {effect == nullptr}, then use the effect input to {node}.
79    // All control uses will be relaxed assuming {node} cannot throw.
80    virtual void ReplaceWithValue(Node* node, Node* value, Node* effect,
81                                  Node* control) = 0;
82  };
83
84  explicit AdvancedReducer(Editor* editor) : editor_(editor) {}
85
86 protected:
87  // Helper functions for subclasses to produce reductions for a node.
88  static Reduction Replace(Node* node) { return Reducer::Replace(node); }
89
90  // Helper functions for subclasses to edit the graph.
91  void Replace(Node* node, Node* replacement) {
92    DCHECK_NOT_NULL(editor_);
93    editor_->Replace(node, replacement);
94  }
95  void Revisit(Node* node) {
96    DCHECK_NOT_NULL(editor_);
97    editor_->Revisit(node);
98  }
99  void ReplaceWithValue(Node* node, Node* value, Node* effect = nullptr,
100                        Node* control = nullptr) {
101    DCHECK_NOT_NULL(editor_);
102    editor_->ReplaceWithValue(node, value, effect, control);
103  }
104
105  // Relax the effects of {node} by immediately replacing effect and control
106  // uses of {node} with the effect and control input to {node}.
107  // TODO(turbofan): replace the effect input to {node} with {graph->start()}.
108  void RelaxEffectsAndControls(Node* node) {
109    ReplaceWithValue(node, node, nullptr, nullptr);
110  }
111
112  // Relax the control uses of {node} by immediately replacing them with the
113  // control input to {node}.
114  void RelaxControls(Node* node) {
115    ReplaceWithValue(node, node, node, nullptr);
116  }
117
118 private:
119  Editor* const editor_;
120};
121
122
123// Performs an iterative reduction of a node graph.
124class V8_EXPORT_PRIVATE GraphReducer
125    : public NON_EXPORTED_BASE(AdvancedReducer::Editor) {
126 public:
127  GraphReducer(Zone* zone, Graph* graph, Node* dead = nullptr);
128  ~GraphReducer();
129
130  Graph* graph() const { return graph_; }
131
132  void AddReducer(Reducer* reducer);
133
134  // Reduce a single node.
135  void ReduceNode(Node* const);
136  // Reduce the whole graph.
137  void ReduceGraph();
138
139 private:
140  enum class State : uint8_t;
141  struct NodeState {
142    Node* node;
143    int input_index;
144  };
145
146  // Reduce a single node.
147  Reduction Reduce(Node* const);
148  // Reduce the node on top of the stack.
149  void ReduceTop();
150
151  // Replace {node} with {replacement}.
152  void Replace(Node* node, Node* replacement) final;
153
154  // Replace value uses of {node} with {value} and effect uses of {node} with
155  // {effect}. If {effect == nullptr}, then use the effect input to {node}. All
156  // control uses will be relaxed assuming {node} cannot throw.
157  void ReplaceWithValue(Node* node, Node* value, Node* effect,
158                        Node* control) final;
159
160  // Replace all uses of {node} with {replacement} if the id of {replacement} is
161  // less than or equal to {max_id}. Otherwise, replace all uses of {node} whose
162  // id is less than or equal to {max_id} with the {replacement}.
163  void Replace(Node* node, Node* replacement, NodeId max_id);
164
165  // Node stack operations.
166  void Pop();
167  void Push(Node* node);
168
169  // Revisit queue operations.
170  bool Recurse(Node* node);
171  void Revisit(Node* node) final;
172
173  Graph* const graph_;
174  Node* const dead_;
175  NodeMarker<State> state_;
176  ZoneVector<Reducer*> reducers_;
177  ZoneStack<Node*> revisit_;
178  ZoneStack<NodeState> stack_;
179
180  DISALLOW_COPY_AND_ASSIGN(GraphReducer);
181};
182
183}  // namespace compiler
184}  // namespace internal
185}  // namespace v8
186
187#endif  // V8_COMPILER_GRAPH_REDUCER_H_
188