| 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 |