| 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 tree_ir.optimization; | 5 part of tree_ir.optimization; |
| 6 | 6 |
| 7 /// Eliminates moving assignments, such as w := v, by assigning directly to w | 7 /// Eliminates moving assignments, such as w := v, by assigning directly to w |
| 8 /// at the definition of v. | 8 /// at the definition of v. |
| 9 /// | 9 /// |
| 10 /// This compensates for suboptimal register allocation, and merges closure | 10 /// This compensates for suboptimal register allocation, and merges closure |
| 11 /// variables with local temporaries that were left behind when translating | 11 /// variables with local temporaries that were left behind when translating |
| 12 /// out of CPS (where closure variables live in a separate space). | 12 /// out of CPS (where closure variables live in a separate space). |
| 13 class CopyPropagator extends RecursiveVisitor implements Pass { | 13 class CopyPropagator extends RecursiveVisitor with PassMixin { |
| 14 | 14 |
| 15 /// After visitStatement returns, [move] maps a variable v to an | 15 /// After visitStatement returns, [move] maps a variable v to an |
| 16 /// assignment A of form w := v, under the following conditions: | 16 /// assignment A of form w := v, under the following conditions: |
| 17 /// - there are no uses of w before A | 17 /// - there are no uses of w before A |
| 18 /// - A is the only use of v | 18 /// - A is the only use of v |
| 19 Map<Variable, Assign> move = <Variable, Assign>{}; | 19 Map<Variable, Assign> move = <Variable, Assign>{}; |
| 20 | 20 |
| 21 /// Like [move], except w is the key instead of v. | 21 /// Like [move], except w is the key instead of v. |
| 22 Map<Variable, Assign> inverseMove = <Variable, Assign>{}; | 22 Map<Variable, Assign> inverseMove = <Variable, Assign>{}; |
| 23 | 23 |
| 24 /// The function currently being rewritten. | 24 ExecutableElement currentElement; |
| 25 FunctionElement functionElement; | |
| 26 | 25 |
| 27 void rewrite(FunctionDefinition function) { | 26 void rewriteExecutableDefinition(ExecutableDefinition root) { |
| 28 if (function.isAbstract) return; | 27 currentElement = root.element; |
| 29 | 28 root.body = visitStatement(root.body); |
| 30 functionElement = function.element; | |
| 31 visitFunctionDefinition(function); | |
| 32 } | 29 } |
| 33 | 30 |
| 34 void visitFunctionDefinition(FunctionDefinition function) { | 31 rewriteFunctionDefinition(FunctionDefinition function) { |
| 35 assert(functionElement == function.element); | 32 if (function.isAbstract) return; |
| 36 function.body = visitStatement(function.body); | 33 rewriteExecutableDefinition(function); |
| 37 | 34 |
| 38 // Try to propagate moving assignments into function parameters. | 35 // Try to propagate moving assignments into function parameters. |
| 39 // For example: | 36 // For example: |
| 40 // foo(x) { | 37 // foo(x) { |
| 41 // var v1 = x; | 38 // var v1 = x; |
| 42 // BODY | 39 // BODY |
| 43 // } | 40 // } |
| 44 // ==> | 41 // ==> |
| 45 // foo(v1) { | 42 // foo(v1) { |
| 46 // BODY | 43 // BODY |
| 47 // } | 44 // } |
| 48 | 45 |
| 49 // Variables must not occur more than once in the parameter list, so | 46 // Variables must not occur more than once in the parameter list, so |
| 50 // invalidate all moving assignments that would propagate a parameter | 47 // invalidate all moving assignments that would propagate a parameter |
| 51 // into another parameter. For example: | 48 // into another parameter. For example: |
| 52 // foo(x,y) { | 49 // foo(x,y) { |
| 53 // y = x; | 50 // y = x; |
| 54 // BODY | 51 // BODY |
| 55 // } | 52 // } |
| 56 // Cannot declare function as foo(x,x)! | 53 // Cannot declare function as foo(x,x)! |
| 57 function.parameters.forEach(visitVariable); | 54 function.parameters.forEach(visitVariable); |
| 58 | 55 |
| 59 // Now do the propagation. | 56 // Now do the propagation. |
| 60 for (int i=0; i<function.parameters.length; i++) { | 57 for (int i = 0; i < function.parameters.length; i++) { |
| 61 Variable param = function.parameters[i]; | 58 Variable param = function.parameters[i]; |
| 62 Variable replacement = copyPropagateVariable(param); | 59 Variable replacement = copyPropagateVariable(param); |
| 63 replacement.element = param.element; // Preserve parameter name. | 60 replacement.element = param.element; // Preserve parameter name. |
| 64 function.parameters[i] = replacement; | 61 function.parameters[i] = replacement; |
| 65 } | 62 } |
| 66 } | 63 } |
| 67 | 64 |
| 68 Statement visitBasicBlock(Statement node) { | 65 Statement visitBasicBlock(Statement node) { |
| 69 node = visitStatement(node); | 66 node = visitStatement(node); |
| 70 move.clear(); | 67 move.clear(); |
| (...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 124 node.variable = copyPropagateVariable(node.variable); | 121 node.variable = copyPropagateVariable(node.variable); |
| 125 visitExpression(node.definition); | 122 visitExpression(node.definition); |
| 126 visitVariable(node.variable); | 123 visitVariable(node.variable); |
| 127 | 124 |
| 128 // If this is a moving assignment w := v, with this being the only use of v, | 125 // If this is a moving assignment w := v, with this being the only use of v, |
| 129 // try to propagate it backwards. Do not propagate assignments where w | 126 // try to propagate it backwards. Do not propagate assignments where w |
| 130 // is from an outer function scope. | 127 // is from an outer function scope. |
| 131 if (node.definition is Variable) { | 128 if (node.definition is Variable) { |
| 132 Variable def = node.definition; | 129 Variable def = node.definition; |
| 133 if (def.readCount == 1 && | 130 if (def.readCount == 1 && |
| 134 node.variable.host.element == functionElement) { | 131 node.variable.host == currentElement) { |
| 135 move[node.definition] = node; | 132 move[node.definition] = node; |
| 136 inverseMove[node.variable] = node; | 133 inverseMove[node.variable] = node; |
| 137 } | 134 } |
| 138 } | 135 } |
| 139 | 136 |
| 140 return node; | 137 return node; |
| 141 } | 138 } |
| 142 | 139 |
| 143 Statement visitLabeledStatement(LabeledStatement node) { | 140 Statement visitLabeledStatement(LabeledStatement node) { |
| 144 node.next = visitBasicBlock(node.next); | 141 node.next = visitBasicBlock(node.next); |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 187 node.next = visitStatement(node.next); | 184 node.next = visitStatement(node.next); |
| 188 visitExpression(node.expression); | 185 visitExpression(node.expression); |
| 189 return node; | 186 return node; |
| 190 } | 187 } |
| 191 | 188 |
| 192 void visitFunctionExpression(FunctionExpression node) { | 189 void visitFunctionExpression(FunctionExpression node) { |
| 193 new CopyPropagator().rewrite(node.definition); | 190 new CopyPropagator().rewrite(node.definition); |
| 194 } | 191 } |
| 195 | 192 |
| 196 } | 193 } |
| OLD | NEW |