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 |