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 22230902 : void Reducer::Finalize() {}
27 :
28 4023680 : 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 8047360 : stack_(zone) {
35 4023689 : if (dead != nullptr) {
36 3558538 : NodeProperties::SetType(dead_, Type::None());
37 : }
38 4023689 : }
39 :
40 8047366 : GraphReducer::~GraphReducer() {}
41 :
42 :
43 17781770 : void GraphReducer::AddReducer(Reducer* reducer) {
44 17781770 : reducers_.push_back(reducer);
45 17781771 : }
46 :
47 :
48 9485913 : void GraphReducer::ReduceNode(Node* node) {
49 : DCHECK(stack_.empty());
50 : DCHECK(revisit_.empty());
51 9485913 : Push(node);
52 : for (;;) {
53 660164734 : 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 638088552 : ReduceTop();
57 22076182 : } else if (!revisit_.empty()) {
58 : // If the stack becomes empty, revisit any nodes in the revisit queue.
59 12539477 : Node* const node = revisit_.front();
60 : revisit_.pop();
61 12539370 : if (state_.Get(node) == State::kRevisit) {
62 : // state can change while in queue.
63 8825765 : Push(node);
64 : }
65 : } else {
66 : // Run all finalizers.
67 42734537 : for (Reducer* const reducer : reducers_) reducer->Finalize();
68 :
69 : // Check if we have new nodes to revisit.
70 9536727 : if (revisit_.empty()) break;
71 : }
72 : }
73 : DCHECK(revisit_.empty());
74 : DCHECK(stack_.empty());
75 9485912 : }
76 :
77 :
78 4002349 : void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
79 :
80 :
81 331567149 : Reduction GraphReducer::Reduce(Node* const node) {
82 : auto skip = reducers_.end();
83 2263284222 : for (auto i = reducers_.begin(); i != reducers_.end();) {
84 1606878745 : if (i != skip) {
85 1530935318 : Reduction reduction = (*i)->Reduce(node);
86 1531199823 : if (!reduction.Changed()) {
87 : // No change from this reducer.
88 82877552 : } 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 75884226 : if (FLAG_trace_turbo_reduction) {
93 0 : OFStream os(stdout);
94 0 : os << "- In-place update of " << *node << " by reducer "
95 0 : << (*i)->reducer_name() << std::endl;
96 : }
97 : skip = i;
98 : i = reducers_.begin();
99 : continue;
100 : } else {
101 : // {node} was replaced by another node.
102 6993326 : if (FLAG_trace_turbo_reduction) {
103 0 : OFStream os(stdout);
104 0 : os << "- Replacement of " << *node << " with "
105 0 : << *(reduction.replacement()) << " by reducer "
106 0 : << (*i)->reducer_name() << std::endl;
107 : }
108 6993326 : return reduction;
109 : }
110 : }
111 : ++i;
112 : }
113 324838328 : if (skip == reducers_.end()) {
114 : // No change from any reducer.
115 : return Reducer::NoChange();
116 : }
117 : // At least one reducer did some in-place reduction.
118 : return Reducer::Changed(node);
119 : }
120 :
121 :
122 969231772 : void GraphReducer::ReduceTop() {
123 : NodeState& entry = stack_.top();
124 637566617 : Node* node = entry.node;
125 : DCHECK_EQ(State::kOnStack, state_.Get(node));
126 :
127 637566617 : if (node->IsDead()) return Pop(); // Node was killed while on stack.
128 :
129 : Node::Inputs node_inputs = node->inputs();
130 :
131 : // Recurse on an input if necessary.
132 637007264 : int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
133 1419299333 : for (int i = start; i < node_inputs.count(); ++i) {
134 : Node* input = node_inputs[i];
135 1087496259 : if (input != node && Recurse(input)) {
136 305834576 : entry.input_index = i + 1;
137 305834576 : return;
138 : }
139 : }
140 312454794 : for (int i = 0; i < start; ++i) {
141 : Node* input = node_inputs[i];
142 312592713 : if (input != node && Recurse(input)) {
143 151157 : entry.input_index = i + 1;
144 151157 : return;
145 : }
146 : }
147 :
148 : // Remember the max node id before reduction.
149 331665155 : NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
150 :
151 : // All inputs should be visited or on stack. Apply reductions to node.
152 331665155 : Reduction reduction = Reduce(node);
153 :
154 : // If there was no reduction, pop {node} and continue.
155 331827119 : if (!reduction.Changed()) return Pop();
156 :
157 : // Check if the reduction is an in-place update of the {node}.
158 : Node* const replacement = reduction.replacement();
159 69278336 : if (replacement == node) {
160 : // In-place update of {node}, may need to recurse on an input.
161 : Node::Inputs node_inputs = node->inputs();
162 279951602 : for (int i = 0; i < node_inputs.count(); ++i) {
163 : Node* input = node_inputs[i];
164 220969171 : if (input != node && Recurse(input)) {
165 3305418 : entry.input_index = i + 1;
166 : return;
167 : }
168 : }
169 : }
170 :
171 : // After reducing the node, pop it off the stack.
172 65986288 : Pop();
173 :
174 : // Check if we have a new replacement.
175 65975711 : if (replacement != node) {
176 6993313 : Replace(node, replacement, max_id);
177 : } else {
178 : // Revisit all uses of the node.
179 266182018 : for (Node* const user : node->uses()) {
180 : // Don't revisit this node if it refers to itself.
181 207198172 : if (user != node) Revisit(user);
182 : }
183 : }
184 : }
185 :
186 :
187 1562512 : void GraphReducer::Replace(Node* node, Node* replacement) {
188 1620982 : Replace(node, replacement, std::numeric_limits<NodeId>::max());
189 1562511 : }
190 :
191 :
192 25842678 : void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
193 8614226 : if (node == graph()->start()) graph()->SetStart(replacement);
194 8614226 : if (node == graph()->end()) graph()->SetEnd(replacement);
195 8614226 : if (replacement->id() <= max_id) {
196 : // {replacement} is an old node, so unlink {node} and assume that
197 : // {replacement} was already reduced and finish.
198 28907959 : for (Edge edge : node->use_edges()) {
199 : Node* const user = edge.from();
200 : Verifier::VerifyEdgeInputReplacement(edge, replacement);
201 10920468 : edge.UpdateTo(replacement);
202 : // Don't revisit this node if it refers to itself.
203 10920470 : if (user != node) Revisit(user);
204 : }
205 7067023 : node->Kill();
206 : } else {
207 : // Replace all old uses of {node} with {replacement}, but allow new nodes
208 : // created by this reduction to use {node}.
209 15072358 : for (Edge edge : node->use_edges()) {
210 6762572 : Node* const user = edge.from();
211 6762572 : if (user->id() <= max_id) {
212 6762575 : edge.UpdateTo(replacement);
213 : // Don't revisit this node if it refers to itself.
214 6762579 : if (user != node) Revisit(user);
215 : }
216 : }
217 : // Unlink {node} if it's no longer used.
218 1547214 : if (node->uses().empty()) node->Kill();
219 :
220 : // If there was a replacement, reduce it after popping {node}.
221 1547210 : Recurse(replacement);
222 : }
223 8614246 : }
224 :
225 :
226 4923410 : void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
227 : Node* control) {
228 4639607 : if (effect == nullptr && node->op()->EffectInputCount() > 0) {
229 996893 : effect = NodeProperties::GetEffectInput(node);
230 : }
231 5207086 : if (control == nullptr && node->op()->ControlInputCount() > 0) {
232 1190551 : control = NodeProperties::GetControlInput(node);
233 : }
234 :
235 : // Requires distinguishing between value, effect and control edges.
236 23602231 : for (Edge edge : node->use_edges()) {
237 2436908 : Node* const user = edge.from();
238 : DCHECK(!user->IsDead());
239 10617155 : if (NodeProperties::IsControlEdge(edge)) {
240 2436908 : if (user->opcode() == IrOpcode::kIfSuccess) {
241 : Replace(user, control);
242 2378438 : } else if (user->opcode() == IrOpcode::kIfException) {
243 : DCHECK_NOT_NULL(dead_);
244 58254 : edge.UpdateTo(dead_);
245 58254 : Revisit(user);
246 : } else {
247 : DCHECK_NOT_NULL(control);
248 2320184 : edge.UpdateTo(control);
249 2320184 : Revisit(user);
250 : }
251 8180234 : } else if (NodeProperties::IsEffectEdge(edge)) {
252 : DCHECK_NOT_NULL(effect);
253 2550940 : edge.UpdateTo(effect);
254 2551011 : Revisit(user);
255 : } else {
256 : DCHECK_NOT_NULL(value);
257 5629559 : edge.UpdateTo(value);
258 5629606 : Revisit(user);
259 : }
260 : }
261 2367921 : }
262 :
263 :
264 328998442 : void GraphReducer::Pop() {
265 328998442 : Node* node = stack_.top().node;
266 : state_.Set(node, State::kVisited);
267 : stack_.pop();
268 329012411 : }
269 :
270 :
271 329035146 : void GraphReducer::Push(Node* const node) {
272 : DCHECK_NE(State::kOnStack, state_.Get(node));
273 : state_.Set(node, State::kOnStack);
274 658179808 : stack_.push({node, 0});
275 329147173 : }
276 :
277 :
278 1621996737 : bool GraphReducer::Recurse(Node* node) {
279 1621986439 : if (state_.Get(node) > State::kRevisit) return false;
280 310768535 : Push(node);
281 310841551 : return true;
282 : }
283 :
284 :
285 235831608 : void GraphReducer::Revisit(Node* node) {
286 471662647 : if (state_.Get(node) == State::kVisited) {
287 : state_.Set(node, State::kRevisit);
288 : revisit_.push(node);
289 : }
290 235831023 : }
291 :
292 : } // namespace compiler
293 : } // namespace internal
294 : } // namespace v8
|
