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 * Propagates constants throughout the IR, and replaces branches with fixed | 8 * Propagates constants throughout the IR, and replaces branches with fixed |
9 * jumps as well as side-effect free expressions with known constant results. | 9 * jumps as well as side-effect free expressions with known constant results. |
10 * Should be followed by the [ShrinkingReducer] pass. | 10 * Should be followed by the [ShrinkingReducer] pass. |
11 * | 11 * |
12 * Implemented according to 'Constant Propagation with Conditional Branches' | 12 * Implemented according to 'Constant Propagation with Conditional Branches' |
13 * by Wegman, Zadeck. | 13 * by Wegman, Zadeck. |
14 */ | 14 */ |
15 class ConstantPropagator implements Pass { | 15 class ConstantPropagator extends Pass { |
16 | 16 |
17 // Required for type determination in analysis of TypeOperator expressions. | 17 // Required for type determination in analysis of TypeOperator expressions. |
18 final dart2js.Compiler _compiler; | 18 final dart2js.Compiler _compiler; |
19 | 19 |
20 // The constant system is used for evaluation of expressions with constant | 20 // The constant system is used for evaluation of expressions with constant |
21 // arguments. | 21 // arguments. |
22 final dart2js.ConstantSystem _constantSystem; | 22 final dart2js.ConstantSystem _constantSystem; |
23 | 23 |
24 ConstantPropagator(this._compiler, this._constantSystem); | 24 ConstantPropagator(this._compiler, this._constantSystem); |
25 | 25 |
26 void rewrite(FunctionDefinition root) { | 26 void _rewriteExecutableDefinition(ExecutableDefinition root) { |
27 if (root.isAbstract) return; | |
28 | |
29 // Set all parent pointers. | 27 // Set all parent pointers. |
30 | |
31 new ParentVisitor().visit(root); | 28 new ParentVisitor().visit(root); |
32 | 29 |
33 // Analyze. In this phase, the entire term is analyzed for reachability | 30 // Analyze. In this phase, the entire term is analyzed for reachability |
34 // and the constant status of each expression. | 31 // and the constant status of each expression. |
35 | 32 |
36 _ConstPropagationVisitor analyzer = | 33 _ConstPropagationVisitor analyzer = |
37 new _ConstPropagationVisitor(_compiler, _constantSystem); | 34 new _ConstPropagationVisitor(_compiler, _constantSystem); |
38 analyzer.analyze(root); | 35 analyzer.analyze(root); |
39 | 36 |
40 // Transform. Uses the data acquired in the previous analysis phase to | 37 // Transform. Uses the data acquired in the previous analysis phase to |
41 // replace branches with fixed targets and side-effect-free expressions | 38 // replace branches with fixed targets and side-effect-free expressions |
42 // with constant results. | 39 // with constant results. |
43 | 40 |
44 _TransformingVisitor transformer = new _TransformingVisitor( | 41 _TransformingVisitor transformer = new _TransformingVisitor( |
45 analyzer.reachableNodes, analyzer.node2value); | 42 analyzer.reachableNodes, analyzer.node2value); |
46 transformer.transform(root); | 43 transformer.transform(root); |
47 } | 44 } |
| 45 |
| 46 void rewriteFunctionDefinition(FunctionDefinition root) { |
| 47 if (root.isAbstract) return; |
| 48 _rewriteExecutableDefinition(root); |
| 49 } |
| 50 |
| 51 void rewriteFieldDefinition(FieldDefinition root) { |
| 52 _rewriteExecutableDefinition(root); |
| 53 } |
| 54 |
48 } | 55 } |
49 | 56 |
50 /** | 57 /** |
51 * Uses the information from a preceding analysis pass in order to perform the | 58 * Uses the information from a preceding analysis pass in order to perform the |
52 * actual transformations on the CPS graph. | 59 * actual transformations on the CPS graph. |
53 */ | 60 */ |
54 class _TransformingVisitor extends RecursiveVisitor { | 61 class _TransformingVisitor extends RecursiveVisitor { |
55 | 62 |
56 final Set<Node> reachable; | 63 final Set<Node> reachable; |
57 final Map<Node, _ConstnessLattice> node2value; | 64 final Map<Node, _ConstnessLattice> node2value; |
58 | 65 |
59 _TransformingVisitor(this.reachable, this.node2value); | 66 _TransformingVisitor(this.reachable, this.node2value); |
60 | 67 |
61 void transform(FunctionDefinition root) { | 68 void transform(ExecutableDefinition root) { |
62 visitFunctionDefinition(root); | 69 visit(root); |
63 } | 70 } |
64 | 71 |
65 /// Given an expression with a known constant result and a continuation, | 72 /// Given an expression with a known constant result and a continuation, |
66 /// replaces the expression by a new LetPrim / InvokeContinuation construct. | 73 /// replaces the expression by a new LetPrim / InvokeContinuation construct. |
67 /// `unlink` is a closure responsible for unlinking all removed references. | 74 /// `unlink` is a closure responsible for unlinking all removed references. |
68 LetPrim constifyExpression(Expression node, | 75 LetPrim constifyExpression(Expression node, |
69 Continuation continuation, | 76 Continuation continuation, |
70 void unlink()) { | 77 void unlink()) { |
71 _ConstnessLattice cell = node2value[node]; | 78 _ConstnessLattice cell = node2value[node]; |
72 if (cell == null || !cell.isConstant) { | 79 if (cell == null || !cell.isConstant) { |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
219 final dart2js.Compiler compiler; | 226 final dart2js.Compiler compiler; |
220 final dart2js.ConstantSystem constantSystem; | 227 final dart2js.ConstantSystem constantSystem; |
221 | 228 |
222 // Stores the current lattice value for nodes. Note that it contains not only | 229 // Stores the current lattice value for nodes. Note that it contains not only |
223 // definitions as keys, but also expressions such as method invokes. | 230 // definitions as keys, but also expressions such as method invokes. |
224 // Access through [getValue] and [setValue]. | 231 // Access through [getValue] and [setValue]. |
225 final Map<Node, _ConstnessLattice> node2value = <Node, _ConstnessLattice>{}; | 232 final Map<Node, _ConstnessLattice> node2value = <Node, _ConstnessLattice>{}; |
226 | 233 |
227 _ConstPropagationVisitor(this.compiler, this.constantSystem); | 234 _ConstPropagationVisitor(this.compiler, this.constantSystem); |
228 | 235 |
229 void analyze(FunctionDefinition root) { | 236 void analyze(ExecutableDefinition root) { |
230 reachableNodes.clear(); | 237 reachableNodes.clear(); |
231 defWorkset.clear(); | 238 defWorkset.clear(); |
232 nodeWorklist.clear(); | 239 nodeWorklist.clear(); |
233 | 240 |
234 // Initially, only the root node is reachable. | 241 // Initially, only the root node is reachable. |
235 setReachable(root); | 242 setReachable(root); |
236 | 243 |
237 while (true) { | 244 while (true) { |
238 if (nodeWorklist.isNotEmpty) { | 245 if (nodeWorklist.isNotEmpty) { |
239 // Process a new reachable expression. | 246 // Process a new reachable expression. |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
297 void visitNode(Node node) { | 304 void visitNode(Node node) { |
298 compiler.internalError(NO_LOCATION_SPANNABLE, | 305 compiler.internalError(NO_LOCATION_SPANNABLE, |
299 "_ConstPropagationVisitor is stale, add missing visit overrides"); | 306 "_ConstPropagationVisitor is stale, add missing visit overrides"); |
300 } | 307 } |
301 | 308 |
302 void visitFunctionDefinition(FunctionDefinition node) { | 309 void visitFunctionDefinition(FunctionDefinition node) { |
303 node.parameters.forEach(visitParameter); | 310 node.parameters.forEach(visitParameter); |
304 setReachable(node.body); | 311 setReachable(node.body); |
305 } | 312 } |
306 | 313 |
| 314 void visitFieldDefinition(FieldDefinition node) { |
| 315 setReachable(node.body); |
| 316 } |
| 317 |
307 // Expressions. | 318 // Expressions. |
308 | 319 |
309 void visitLetPrim(LetPrim node) { | 320 void visitLetPrim(LetPrim node) { |
310 visit(node.primitive); // No reason to delay visits to primitives. | 321 visit(node.primitive); // No reason to delay visits to primitives. |
311 setReachable(node.body); | 322 setReachable(node.body); |
312 } | 323 } |
313 | 324 |
314 void visitLetCont(LetCont node) { | 325 void visitLetCont(LetCont node) { |
315 // The continuation is only marked as reachable on use. | 326 // The continuation is only marked as reachable on use. |
316 setReachable(node.body); | 327 setReachable(node.body); |
(...skipping 362 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
679 return that; | 690 return that; |
680 } | 691 } |
681 | 692 |
682 if (this.constant == that.constant) { | 693 if (this.constant == that.constant) { |
683 return this; | 694 return this; |
684 } | 695 } |
685 | 696 |
686 return NonConst; | 697 return NonConst; |
687 } | 698 } |
688 } | 699 } |
OLD | NEW |