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 : #include <functional>
6 : #include <limits>
7 :
8 : #include "src/compiler/graph.h"
9 : #include "src/compiler/graph-reducer.h"
10 : #include "src/compiler/node.h"
11 : #include "src/compiler/node-properties.h"
12 : #include "src/compiler/verifier.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : enum class GraphReducer::State : uint8_t {
19 : kUnvisited,
20 : kRevisit,
21 : kOnStack,
22 : kVisited
23 : };
24 :
25 :
26 32498987 : void Reducer::Finalize() {}
27 :
28 5706050 : GraphReducer::GraphReducer(Zone* zone, Graph* graph, Node* dead)
29 : : graph_(graph),
30 : dead_(dead),
31 : state_(graph, 4),
32 : reducers_(zone),
33 : revisit_(zone),
34 11412058 : stack_(zone) {
35 5706192 : if (dead != nullptr) {
36 5232353 : NodeProperties::SetType(dead_, Type::None());
37 : }
38 5706192 : }
39 :
40 : GraphReducer::~GraphReducer() = default;
41 :
42 :
43 21427293 : void GraphReducer::AddReducer(Reducer* reducer) {
44 21427293 : reducers_.push_back(reducer);
45 21427282 : }
46 :
47 :
48 17813468 : void GraphReducer::ReduceNode(Node* node) {
49 : DCHECK(stack_.empty());
50 : DCHECK(revisit_.empty());
51 17813468 : Push(node);
52 : for (;;) {
53 806149361 : if (!stack_.empty()) {
54 : // Process the node on the top of the stack, potentially pushing more or
55 : // popping the node off the stack.
56 768888482 : ReduceTop();
57 37260879 : } else if (!revisit_.empty()) {
58 : // If the stack becomes empty, revisit any nodes in the revisit queue.
59 19392974 : Node* const node = revisit_.front();
60 : revisit_.pop();
61 19392661 : if (state_.Get(node) == State::kRevisit) {
62 : // state can change while in queue.
63 13885317 : Push(node);
64 : }
65 : } else {
66 : // Run all finalizers.
67 69709961 : for (Reducer* const reducer : reducers_) reducer->Finalize();
68 :
69 : // Check if we have new nodes to revisit.
70 17867657 : if (revisit_.empty()) break;
71 : }
72 : }
73 : DCHECK(revisit_.empty());
74 : DCHECK(stack_.empty());
75 17813556 : }
76 :
77 :
78 5688498 : void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
79 :
80 :
81 402981998 : Reduction GraphReducer::Reduce(Node* const node) {
82 : auto skip = reducers_.end();
83 2645931919 : for (auto i = reducers_.begin(); i != reducers_.end();) {
84 1848104101 : if (i != skip) {
85 1767162467 : Reduction reduction = (*i)->Reduce(node);
86 1767532899 : if (!reduction.Changed()) {
87 : // No change from this reducer.
88 89398910 : } else if (reduction.replacement() == node) {
89 : // {replacement} == {node} represents an in-place reduction. Rerun
90 : // all the other reducers for this node, as now there may be more
91 : // opportunities for reduction.
92 80892300 : if (FLAG_trace_turbo_reduction) {
93 0 : StdoutStream{} << "- In-place update of " << *node << " by reducer "
94 0 : << (*i)->reducer_name() << std::endl;
95 : }
96 : skip = i;
97 : i = reducers_.begin();
98 : continue;
99 : } else {
100 : // {node} was replaced by another node.
101 8506610 : if (FLAG_trace_turbo_reduction) {
102 0 : StdoutStream{} << "- Replacement of " << *node << " with "
103 0 : << *(reduction.replacement()) << " by reducer "
104 0 : << (*i)->reducer_name() << std::endl;
105 : }
106 8506610 : return reduction;
107 : }
108 : }
109 : ++i;
110 : }
111 394845820 : if (skip == reducers_.end()) {
112 : // No change from any reducer.
113 : return Reducer::NoChange();
114 : }
115 : // At least one reducer did some in-place reduction.
116 : return Reducer::Changed(node);
117 : }
118 :
119 :
120 1171095507 : void GraphReducer::ReduceTop() {
121 : NodeState& entry = stack_.top();
122 767931967 : Node* node = entry.node;
123 : DCHECK_EQ(State::kOnStack, state_.Get(node));
124 :
125 767931967 : if (node->IsDead()) return Pop(); // Node was killed while on stack.
126 :
127 : Node::Inputs node_inputs = node->inputs();
128 :
129 : // Recurse on an input if necessary.
130 767378744 : int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
131 1686020374 : for (int i = start; i < node_inputs.count(); ++i) {
132 : Node* input = node_inputs[i];
133 1282678071 : if (input != node && Recurse(input)) {
134 365100202 : entry.input_index = i + 1;
135 365100202 : return;
136 : }
137 : }
138 349004927 : for (int i = 0; i < start; ++i) {
139 : Node* input = node_inputs[i];
140 349183690 : if (input != node && Recurse(input)) {
141 198316 : entry.input_index = i + 1;
142 198316 : return;
143 : }
144 : }
145 :
146 : // Remember the max node id before reduction.
147 403163540 : NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
148 :
149 : // All inputs should be visited or on stack. Apply reductions to node.
150 403163540 : Reduction reduction = Reduce(node);
151 :
152 : // If there was no reduction, pop {node} and continue.
153 403338942 : if (!reduction.Changed()) return Pop();
154 :
155 : // Check if the reduction is an in-place update of the {node}.
156 : Node* const replacement = reduction.replacement();
157 76138107 : if (replacement == node) {
158 : // In-place update of {node}, may need to recurse on an input.
159 : Node::Inputs node_inputs = node->inputs();
160 292369558 : for (int i = 0; i < node_inputs.count(); ++i) {
161 : Node* input = node_inputs[i];
162 227499246 : if (input != node && Recurse(input)) {
163 2762051 : entry.input_index = i + 1;
164 : return;
165 : }
166 : }
167 : }
168 :
169 : // After reducing the node, pop it off the stack.
170 73384775 : Pop();
171 :
172 : // Check if we have a new replacement.
173 73376881 : if (replacement != node) {
174 8506554 : Replace(node, replacement, max_id);
175 : } else {
176 : // Revisit all uses of the node.
177 346580996 : for (Node* const user : node->uses()) {
178 : // Don't revisit this node if it refers to itself.
179 216840183 : if (user != node) Revisit(user);
180 : }
181 : }
182 : }
183 :
184 :
185 1624936 : void GraphReducer::Replace(Node* node, Node* replacement) {
186 1688015 : Replace(node, replacement, std::numeric_limits<NodeId>::max());
187 1624938 : }
188 :
189 :
190 30583677 : void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
191 10194559 : if (node == graph()->start()) graph()->SetStart(replacement);
192 10194559 : if (node == graph()->end()) graph()->SetEnd(replacement);
193 10194559 : if (replacement->id() <= max_id) {
194 : // {replacement} is an old node, so unlink {node} and assume that
195 : // {replacement} was already reduced and finish.
196 42484433 : for (Edge edge : node->use_edges()) {
197 : Node* const user = edge.from();
198 : Verifier::VerifyEdgeInputReplacement(edge, replacement);
199 12505562 : edge.UpdateTo(replacement);
200 : // Don't revisit this node if it refers to itself.
201 12505578 : if (user != node) Revisit(user);
202 : }
203 8736670 : node->Kill();
204 : } else {
205 : // Replace all old uses of {node} with {replacement}, but allow new nodes
206 : // created by this reduction to use {node}.
207 16657824 : for (Edge edge : node->use_edges()) {
208 6870983 : Node* const user = edge.from();
209 6870983 : if (user->id() <= max_id) {
210 6870928 : edge.UpdateTo(replacement);
211 : // Don't revisit this node if it refers to itself.
212 6870936 : if (user != node) Revisit(user);
213 : }
214 : }
215 : // Unlink {node} if it's no longer used.
216 1457938 : if (node->uses().empty()) node->Kill();
217 :
218 : // If there was a replacement, reduce it after popping {node}.
219 1457932 : Recurse(replacement);
220 : }
221 10194738 : }
222 :
223 :
224 6064242 : void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
225 : Node* control) {
226 5715922 : if (effect == nullptr && node->op()->EffectInputCount() > 0) {
227 1268877 : effect = NodeProperties::GetEffectInput(node);
228 : }
229 6412548 : if (control == nullptr && node->op()->ControlInputCount() > 0) {
230 1620046 : control = NodeProperties::GetControlInput(node);
231 : }
232 :
233 : // Requires distinguishing between value, effect and control edges.
234 28879765 : for (Edge edge : node->use_edges()) {
235 2885286 : Node* const user = edge.from();
236 : DCHECK(!user->IsDead());
237 11665838 : if (NodeProperties::IsControlEdge(edge)) {
238 2885286 : if (user->opcode() == IrOpcode::kIfSuccess) {
239 : Replace(user, control);
240 2822207 : } else if (user->opcode() == IrOpcode::kIfException) {
241 : DCHECK_NOT_NULL(dead_);
242 62573 : edge.UpdateTo(dead_);
243 62573 : Revisit(user);
244 : } else {
245 : DCHECK_NOT_NULL(control);
246 2759634 : edge.UpdateTo(control);
247 2759635 : Revisit(user);
248 : }
249 8780496 : } else if (NodeProperties::IsEffectEdge(edge)) {
250 : DCHECK_NOT_NULL(effect);
251 2907594 : edge.UpdateTo(effect);
252 2907623 : Revisit(user);
253 : } else {
254 : DCHECK_NOT_NULL(value);
255 5873209 : edge.UpdateTo(value);
256 5873228 : Revisit(user);
257 : }
258 : }
259 2774041 : }
260 :
261 :
262 401041791 : void GraphReducer::Pop() {
263 401041791 : Node* node = stack_.top().node;
264 : state_.Set(node, State::kVisited);
265 : stack_.pop();
266 401047820 : }
267 :
268 :
269 401091885 : void GraphReducer::Push(Node* const node) {
270 : DCHECK_NE(State::kOnStack, state_.Get(node));
271 : state_.Set(node, State::kOnStack);
272 802310185 : stack_.push({node, 0});
273 401224490 : }
274 :
275 :
276 1860638296 : bool GraphReducer::Recurse(Node* node) {
277 1860596942 : if (state_.Get(node) > State::kRevisit) return false;
278 369443809 : Push(node);
279 369532314 : return true;
280 : }
281 :
282 :
283 248306924 : void GraphReducer::Revisit(Node* node) {
284 496612232 : if (state_.Get(node) == State::kVisited) {
285 : state_.Set(node, State::kRevisit);
286 : revisit_.push(node);
287 : }
288 248305202 : }
289 :
290 : } // namespace compiler
291 : } // namespace internal
292 183867 : } // namespace v8
|
