Line data Source code
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 545454 : Node* replacement() const { return replacement_; }
35 184123 : 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 28791296 : class V8_EXPORT_PRIVATE Reducer {
48 : public:
49 28282634 : 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 39121531 : class AdvancedReducer : public Reducer {
72 : public:
73 : // Observe the actions of this reducer.
74 5810353 : class Editor {
75 : public:
76 5811946 : 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 19560875 : 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 1608669 : editor_->Replace(node, replacement);
99 : }
100 : void Revisit(Node* node) {
101 : DCHECK_NOT_NULL(editor_);
102 544113 : editor_->Revisit(node);
103 : }
104 : void ReplaceWithValue(Node* node, Node* value, Node* effect = nullptr,
105 : Node* control = nullptr) {
106 : DCHECK_NOT_NULL(editor_);
107 2212464 : 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 11621763 : 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_
|
