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 | using NodeId = uint32_t; |
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_ |
193 | |