OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of dart2js.optimizers; | 5 part of dart2js.optimizers; |
6 | 6 |
7 /** | 7 /** |
8 * [[ShrinkingReducer]] applies shrinking reductions to CPS terms as described | 8 * [[ShrinkingReducer]] applies shrinking reductions to CPS terms as described |
9 * in 'Compiling with Continuations, Continued' by Andrew Kennedy. | 9 * in 'Compiling with Continuations, Continued' by Andrew Kennedy. |
10 */ | 10 */ |
11 class ShrinkingReducer implements Pass { | 11 class ShrinkingReducer extends Pass { |
12 _RedexVisitor _redexVisitor; | 12 _RedexVisitor _redexVisitor; |
13 Set<_ReductionTask> _worklist; | 13 Set<_ReductionTask> _worklist; |
14 | 14 |
15 static final _DeletedNode _DELETED = new _DeletedNode(); | 15 static final _DeletedNode _DELETED = new _DeletedNode(); |
16 | 16 |
17 /// Applies shrinking reductions to root, mutating root in the process. | 17 void rewriteExecutableDefinition(ExecutableDefinition root) { |
18 void rewrite(FunctionDefinition root) { | |
19 if (root.isAbstract) return; | |
20 | |
21 _worklist = new Set<_ReductionTask>(); | 18 _worklist = new Set<_ReductionTask>(); |
22 _redexVisitor = new _RedexVisitor(_worklist); | 19 _redexVisitor = new _RedexVisitor(_worklist); |
23 | 20 |
24 // Set all parent pointers. | 21 // Set all parent pointers. |
25 new ParentVisitor().visit(root); | 22 new ParentVisitor().visit(root); |
26 | 23 |
27 // Sweep over the term, collecting redexes into the worklist. | 24 // Sweep over the term, collecting redexes into the worklist. |
28 _redexVisitor.visitFunctionDefinition(root); | 25 _redexVisitor.visit(root); |
29 | 26 |
30 // Process the worklist. | 27 // Process the worklist. |
31 while (_worklist.isNotEmpty) { | 28 while (_worklist.isNotEmpty) { |
32 _ReductionTask task = _worklist.first; | 29 _ReductionTask task = _worklist.first; |
33 _worklist.remove(task); | 30 _worklist.remove(task); |
34 _processTask(task); | 31 _processTask(task); |
35 } | 32 } |
36 } | 33 } |
37 | 34 |
| 35 /// Applies shrinking reductions to root, mutating root in the process. |
| 36 void rewriteFieldDefinition(FieldDefinition root) { |
| 37 rewriteExecutableDefinition(root); |
| 38 } |
| 39 |
| 40 /// Applies shrinking reductions to root, mutating root in the process. |
| 41 void rewriteFunctionDefinition(FunctionDefinition root) { |
| 42 if (root.isAbstract) return; |
| 43 rewriteExecutableDefinition(root); |
| 44 } |
| 45 |
38 /// Removes the given node from the CPS graph, replacing it with its body | 46 /// Removes the given node from the CPS graph, replacing it with its body |
39 /// and marking it as deleted. The node's parent must be a [[InteriorNode]]. | 47 /// and marking it as deleted. The node's parent must be a [[InteriorNode]]. |
40 void _removeNode(InteriorNode node) { | 48 void _removeNode(InteriorNode node) { |
41 Node body = node.body; | 49 Node body = node.body; |
42 InteriorNode parent = node.parent; | 50 InteriorNode parent = node.parent; |
43 assert(parent.body == node); | 51 assert(parent.body == node); |
44 | 52 |
45 body.parent = parent; | 53 body.parent = parent; |
46 parent.body = body; | 54 parent.body = body; |
47 node.parent = _DELETED; | 55 node.parent = _DELETED; |
(...skipping 240 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
288 if (parent is LetCont && _isDeadCont(parent)) { | 296 if (parent is LetCont && _isDeadCont(parent)) { |
289 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent)); | 297 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent)); |
290 } | 298 } |
291 } | 299 } |
292 } | 300 } |
293 } | 301 } |
294 | 302 |
295 /// Traverses the CPS term and sets node.parent for each visited node. | 303 /// Traverses the CPS term and sets node.parent for each visited node. |
296 class ParentVisitor extends RecursiveVisitor { | 304 class ParentVisitor extends RecursiveVisitor { |
297 | 305 |
| 306 processFieldDefinition(FieldDefinition node) { |
| 307 node.body.parent = node; |
| 308 } |
| 309 |
298 processFunctionDefinition(FunctionDefinition node) { | 310 processFunctionDefinition(FunctionDefinition node) { |
299 node.body.parent = node; | 311 node.body.parent = node; |
300 node.parameters.forEach((Parameter p) => p.parent = node); | 312 node.parameters.forEach((Parameter p) => p.parent = node); |
301 } | 313 } |
302 | 314 |
303 // Expressions. | 315 // Expressions. |
304 | 316 |
305 processLetPrim(LetPrim node) { | 317 processLetPrim(LetPrim node) { |
306 node.primitive.parent = node; | 318 node.primitive.parent = node; |
307 node.body.parent = node; | 319 node.body.parent = node; |
(...skipping 129 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
437 } | 449 } |
438 | 450 |
439 String toString() => "$kind: $node"; | 451 String toString() => "$kind: $node"; |
440 } | 452 } |
441 | 453 |
442 /// A dummy class used solely to mark nodes as deleted once they are removed | 454 /// A dummy class used solely to mark nodes as deleted once they are removed |
443 /// from a term. | 455 /// from a term. |
444 class _DeletedNode extends Node { | 456 class _DeletedNode extends Node { |
445 accept(_) => null; | 457 accept(_) => null; |
446 } | 458 } |
OLD | NEW |