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