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