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.
24using NodeId = uint32_t;
25
26// Possible outcomes for decisions.
27enum class Decision : uint8_t { kUnknown, kTrue, kFalse };
28
29// Represents the result of trying to reduce a node in the graph.
30class 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.
47class 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.
71class 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.
129class 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_
193