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 20951465 : void Reducer::Finalize() {}
27 :
28 3301866 : 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 6603728 : stack_(zone) {
35 3301893 : if (dead != nullptr) {
36 2875405 : NodeProperties::SetType(dead_, Type::None());
37 : }
38 3301893 : }
39 :
40 6603565 : GraphReducer::~GraphReducer() {}
41 :
42 :
43 16125661 : void GraphReducer::AddReducer(Reducer* reducer) {
44 16125661 : reducers_.push_back(reducer);
45 16125566 : }
46 :
47 :
48 8301754 : void GraphReducer::ReduceNode(Node* node) {
49 : DCHECK(stack_.empty());
50 : DCHECK(revisit_.empty());
51 8301754 : Push(node);
52 : for (;;) {
53 617500137 : 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 593583035 : ReduceTop();
57 23917102 : } else if (!revisit_.empty()) {
58 : // If the stack becomes empty, revisit any nodes in the revisit queue.
59 15580978 : Node* const node = revisit_.top();
60 : revisit_.pop();
61 15580837 : if (state_.Get(node) == State::kRevisit) {
62 : // state can change while in queue.
63 12360046 : Push(node);
64 : }
65 : } else {
66 : // Run all finalizers.
67 38093187 : for (Reducer* const reducer : reducers_) reducer->Finalize();
68 :
69 : // Check if we have new nodes to revisit.
70 8336147 : if (revisit_.empty()) break;
71 : }
72 : }
73 : DCHECK(revisit_.empty());
74 : DCHECK(stack_.empty());
75 8301813 : }
76 :
77 :
78 3277103 : void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
79 :
80 :
81 310042541 : Reduction GraphReducer::Reduce(Node* const node) {
82 : auto skip = reducers_.end();
83 2237149819 : for (auto i = reducers_.begin(); i != reducers_.end();) {
84 1624652279 : if (i != skip) {
85 1551952319 : Reduction reduction = (*i)->Reduce(node);
86 1552087776 : if (!reduction.Changed()) {
87 : // No change from this reducer.
88 80310627 : } 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 : skip = i;
93 : i = reducers_.begin();
94 : continue;
95 : } else {
96 : // {node} was replaced by another node.
97 7722999 : return reduction;
98 : }
99 : }
100 : ++i;
101 : }
102 302454999 : if (skip == reducers_.end()) {
103 : // No change from any reducer.
104 : return Reducer::NoChange();
105 : }
106 : // At least one reducer did some in-place reduction.
107 : return Reducer::Changed(node);
108 : }
109 :
110 :
111 903880609 : void GraphReducer::ReduceTop() {
112 : NodeState& entry = stack_.top();
113 593791259 : Node* node = entry.node;
114 : DCHECK(state_.Get(node) == State::kOnStack);
115 :
116 593791259 : if (node->IsDead()) return Pop(); // Node was killed while on stack.
117 :
118 : Node::Inputs node_inputs = node->inputs();
119 :
120 : // Recurse on an input if necessary.
121 593158933 : int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
122 1318557832 : for (int i = start; i < node_inputs.count(); ++i) {
123 : Node* input = node_inputs[i];
124 1008309038 : if (input != node && Recurse(input)) {
125 282933235 : entry.input_index = i + 1;
126 282933235 : return;
127 : }
128 : }
129 292467411 : for (int i = 0; i < start; ++i) {
130 : Node* input = node_inputs[i];
131 292626855 : if (input != node && Recurse(input)) {
132 146278 : entry.input_index = i + 1;
133 146278 : return;
134 : }
135 : }
136 :
137 : // Remember the max node id before reduction.
138 310089350 : NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
139 :
140 : // All inputs should be visited or on stack. Apply reductions to node.
141 310089350 : Reduction reduction = Reduce(node);
142 :
143 : // If there was no reduction, pop {node} and continue.
144 310162729 : if (!reduction.Changed()) return Pop();
145 :
146 : // Check if the reduction is an in-place update of the {node}.
147 : Node* const replacement = reduction.replacement();
148 68376108 : if (replacement == node) {
149 60657329 : if (FLAG_trace_turbo_reduction) {
150 0 : OFStream os(stdout);
151 0 : os << "- In-place update of " << *replacement << std::endl;
152 : }
153 : // In-place update of {node}, may need to recurse on an input.
154 : Node::Inputs node_inputs = node->inputs();
155 267292359 : for (int i = 0; i < node_inputs.count(); ++i) {
156 : Node* input = node_inputs[i];
157 209323071 : if (input != node && Recurse(input)) {
158 2685961 : entry.input_index = i + 1;
159 : return;
160 : }
161 : }
162 : }
163 :
164 : // After reducing the node, pop it off the stack.
165 65688067 : Pop();
166 :
167 : // Check if we have a new replacement.
168 65692340 : if (replacement != node) {
169 7722977 : Replace(node, replacement, max_id);
170 : } else {
171 : // Revisit all uses of the node.
172 245457157 : for (Node* const user : node->uses()) {
173 : // Don't revisit this node if it refers to itself.
174 187489635 : if (user != node) Revisit(user);
175 : }
176 : }
177 : }
178 :
179 :
180 1955328 : void GraphReducer::Replace(Node* node, Node* replacement) {
181 2051531 : Replace(node, replacement, std::numeric_limits<NodeId>::max());
182 1955331 : }
183 :
184 :
185 39097852 : void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
186 9774463 : if (FLAG_trace_turbo_reduction) {
187 0 : OFStream os(stdout);
188 0 : os << "- Replacing " << *node << " with " << *replacement << std::endl;
189 : }
190 9774463 : if (node == graph()->start()) graph()->SetStart(replacement);
191 9774463 : if (node == graph()->end()) graph()->SetEnd(replacement);
192 9774463 : if (replacement->id() <= max_id) {
193 : // {replacement} is an old node, so unlink {node} and assume that
194 : // {replacement} was already reduced and finish.
195 36282379 : for (Edge edge : node->use_edges()) {
196 : Node* const user = edge.from();
197 : Verifier::VerifyEdgeInputReplacement(edge, replacement);
198 14129241 : edge.UpdateTo(replacement);
199 : // Don't revisit this node if it refers to itself.
200 14129240 : if (user != node) Revisit(user);
201 : }
202 8023897 : node->Kill();
203 : } else {
204 : // Replace all old uses of {node} with {replacement}, but allow new nodes
205 : // created by this reduction to use {node}.
206 13577049 : for (Edge edge : node->use_edges()) {
207 5913244 : Node* const user = edge.from();
208 5913244 : if (user->id() <= max_id) {
209 5913244 : edge.UpdateTo(replacement);
210 : // Don't revisit this node if it refers to itself.
211 5913245 : if (user != node) Revisit(user);
212 : }
213 : }
214 : // Unlink {node} if it's no longer used.
215 1750561 : if (node->uses().empty()) node->Kill();
216 :
217 : // If there was a replacement, reduce it after popping {node}.
218 1750562 : Recurse(replacement);
219 : }
220 9774515 : }
221 :
222 :
223 4781156 : void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
224 : Node* control) {
225 4513366 : if (effect == nullptr && node->op()->EffectInputCount() > 0) {
226 1010634 : effect = NodeProperties::GetEffectInput(node);
227 : }
228 5048889 : if (control == nullptr && node->op()->ControlInputCount() > 0) {
229 1177088 : control = NodeProperties::GetControlInput(node);
230 : }
231 :
232 : // Requires distinguishing between value, effect and control edges.
233 23589940 : for (Edge edge : node->use_edges()) {
234 2296011 : Node* const user = edge.from();
235 : DCHECK(!user->IsDead());
236 10686818 : if (NodeProperties::IsControlEdge(edge)) {
237 2296011 : if (user->opcode() == IrOpcode::kIfSuccess) {
238 : Replace(user, control);
239 2199808 : } else if (user->opcode() == IrOpcode::kIfException) {
240 : DCHECK_NOT_NULL(dead_);
241 95919 : edge.UpdateTo(dead_);
242 95919 : Revisit(user);
243 : } else {
244 : DCHECK_NOT_NULL(control);
245 2103889 : edge.UpdateTo(control);
246 2103889 : Revisit(user);
247 : // TODO(jarin) Check that the node cannot throw (otherwise, it
248 : // would have to be connected via IfSuccess/IfException).
249 : }
250 8390751 : } else if (NodeProperties::IsEffectEdge(edge)) {
251 : DCHECK_NOT_NULL(effect);
252 2542986 : edge.UpdateTo(effect);
253 2543049 : Revisit(user);
254 : } else {
255 : DCHECK_NOT_NULL(value);
256 5848032 : edge.UpdateTo(value);
257 5848066 : Revisit(user);
258 : }
259 : }
260 2216304 : }
261 :
262 :
263 308011487 : void GraphReducer::Pop() {
264 308011487 : Node* node = stack_.top().node;
265 : state_.Set(node, State::kVisited);
266 : stack_.pop();
267 308026872 : }
268 :
269 :
270 308069804 : void GraphReducer::Push(Node* const node) {
271 : DCHECK(state_.Get(node) != State::kOnStack);
272 : state_.Set(node, State::kOnStack);
273 616234460 : stack_.push({node, 0});
274 308167291 : }
275 :
276 :
277 1510594321 : bool GraphReducer::Recurse(Node* node) {
278 1510650801 : if (state_.Get(node) > State::kRevisit) return false;
279 287460794 : Push(node);
280 287518343 : return true;
281 : }
282 :
283 :
284 218628965 : void GraphReducer::Revisit(Node* node) {
285 437257930 : if (state_.Get(node) == State::kVisited) {
286 : state_.Set(node, State::kRevisit);
287 : revisit_.push(node);
288 : }
289 218628753 : }
290 :
291 : } // namespace compiler
292 : } // namespace internal
293 : } // namespace v8
|
