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