| 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 with PassMixin { | 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 reads or writes of w before A | 17 /// - there are no reads or writes 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 ExecutableElement currentElement; | 24 ExecutableElement currentElement; |
| 25 | 25 |
| 26 /// Number of try blocks enclosing the currently visited node. |
| 27 int enclosingTrys = 0; |
| 28 |
| 26 void rewriteExecutableDefinition(ExecutableDefinition root) { | 29 void rewriteExecutableDefinition(ExecutableDefinition root) { |
| 27 currentElement = root.element; | 30 currentElement = root.element; |
| 28 root.body = visitStatement(root.body); | 31 root.body = visitStatement(root.body); |
| 29 } | 32 } |
| 30 | 33 |
| 31 rewriteFunctionDefinition(FunctionDefinition node) { | 34 rewriteFunctionDefinition(FunctionDefinition node) { |
| 32 if (node.isAbstract) return; | 35 if (node.isAbstract) return; |
| 33 rewriteExecutableDefinition(node); | 36 rewriteExecutableDefinition(node); |
| 34 | 37 |
| 35 // Try to propagate moving assignments into function parameters. | 38 // Try to propagate moving assignments into function parameters. |
| (...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 104 node = visitStatement(node); | 107 node = visitStatement(node); |
| 105 move.clear(); | 108 move.clear(); |
| 106 inverseMove.clear(); | 109 inverseMove.clear(); |
| 107 return node; | 110 return node; |
| 108 } | 111 } |
| 109 | 112 |
| 110 /// Remove an assignment of form [w] := v from the move maps. | 113 /// Remove an assignment of form [w] := v from the move maps. |
| 111 void invalidateMovingAssignment(Variable w) { | 114 void invalidateMovingAssignment(Variable w) { |
| 112 Assign movingAssignment = inverseMove.remove(w); | 115 Assign movingAssignment = inverseMove.remove(w); |
| 113 if (movingAssignment != null) { | 116 if (movingAssignment != null) { |
| 114 VariableUse def = movingAssignment.definition; | 117 VariableUse value = movingAssignment.value; |
| 115 move.remove(def.variable); | 118 move.remove(value.variable); |
| 116 } | 119 } |
| 117 } | 120 } |
| 118 | 121 |
| 119 visitVariableUse(VariableUse node) { | 122 visitVariableUse(VariableUse node) { |
| 120 // We found a use of w; we can't propagate assignments across this use. | 123 // We found a use of w; we can't propagate assignments across this use. |
| 121 invalidateMovingAssignment(node.variable); | 124 invalidateMovingAssignment(node.variable); |
| 122 } | 125 } |
| 123 | 126 |
| 124 /** | 127 /** |
| 125 * Called when a definition of [v] is encountered. | 128 * Called when a definition of [v] is encountered. |
| (...skipping 11 matching lines...) Expand all Loading... |
| 137 // | 140 // |
| 138 // Rewrite to: | 141 // Rewrite to: |
| 139 // w := EXPR | 142 // w := EXPR |
| 140 // BLOCK | 143 // BLOCK |
| 141 // w := w (to be removed later) | 144 // w := w (to be removed later) |
| 142 Variable w = movingAssign.variable; | 145 Variable w = movingAssign.variable; |
| 143 | 146 |
| 144 // Make w := w. | 147 // Make w := w. |
| 145 // We can't remove the statement from here because we don't have | 148 // We can't remove the statement from here because we don't have |
| 146 // parent pointers. So just make it a no-op so it can be removed later. | 149 // parent pointers. So just make it a no-op so it can be removed later. |
| 147 movingAssign.definition = new VariableUse(w); | 150 movingAssign.value = new VariableUse(w); |
| 148 | 151 |
| 149 // The intermediate variable 'v' should now be orphaned, so don't bother | 152 // The intermediate variable 'v' should now be orphaned, so don't bother |
| 150 // updating its read/write counters. | 153 // updating its read/write counters. |
| 151 | 154 |
| 152 // Make w := EXPR | 155 // Make w := EXPR |
| 153 ++w.writeCount; | 156 ++w.writeCount; |
| 154 return w; | 157 return w; |
| 155 } | 158 } |
| 156 return v; | 159 return v; |
| 157 } | 160 } |
| 158 | 161 |
| 159 Statement visitAssign(Assign node) { | 162 Statement visitAssign(Assign node) { |
| 160 node.next = visitStatement(node.next); | 163 node.next = visitStatement(node.next); |
| 161 node.variable = copyPropagateVariable(node.variable); | 164 node.variable = copyPropagateVariable(node.variable); |
| 162 | 165 |
| 163 // If a moving assignment w := v exists later, and we assign to w here, | 166 // If a moving assignment w := v exists later, and we assign to w here, |
| 164 // the moving assignment is no longer a candidate for copy propagation. | 167 // the moving assignment is no longer a candidate for copy propagation. |
| 165 invalidateMovingAssignment(node.variable); | 168 invalidateMovingAssignment(node.variable); |
| 166 | 169 |
| 167 visitExpression(node.definition); | 170 visitExpression(node.value); |
| 168 | 171 |
| 169 // If this is a moving assignment w := v, with this being the only use of v, | 172 // If this is a moving assignment w := v, with this being the only use of v, |
| 170 // try to propagate it backwards. Do not propagate assignments where w | 173 // try to propagate it backwards. |
| 171 // is from an outer function scope. | 174 // Do not propagate assignments where w is captured or if where are inside a |
| 172 if (node.definition is VariableUse) { | 175 // try block, because then we can't isolate the uses of w to a single block. |
| 173 VariableUse definition = node.definition; | 176 // We currently do not support propagation if the assignment is a |
| 174 if (definition.variable.readCount == 1 && | 177 // declaration. To support this we would need to ensure that the target |
| 175 node.variable.host == currentElement) { | 178 // assignment is turned into a declaration as well. |
| 176 move[definition.variable] = node; | 179 if (node.value is VariableUse && |
| 180 !node.variable.isCaptured && |
| 181 enclosingTrys == 0 && |
| 182 !node.isDeclaration) { |
| 183 VariableUse value = node.value; |
| 184 if (value.variable.readCount == 1) { |
| 185 move[value.variable] = node; |
| 177 inverseMove[node.variable] = node; | 186 inverseMove[node.variable] = node; |
| 178 } | 187 } |
| 179 } | 188 } |
| 180 | 189 |
| 181 return node; | 190 return node; |
| 182 } | 191 } |
| 183 | 192 |
| 184 Statement visitLabeledStatement(LabeledStatement node) { | 193 Statement visitLabeledStatement(LabeledStatement node) { |
| 185 node.next = visitBasicBlock(node.next); | 194 node.next = visitBasicBlock(node.next); |
| 186 node.body = visitStatement(node.body); | 195 node.body = visitStatement(node.body); |
| (...skipping 23 matching lines...) Expand all Loading... |
| 210 Statement visitWhileTrue(WhileTrue node) { | 219 Statement visitWhileTrue(WhileTrue node) { |
| 211 node.body = visitBasicBlock(node.body); | 220 node.body = visitBasicBlock(node.body); |
| 212 return node; | 221 return node; |
| 213 } | 222 } |
| 214 | 223 |
| 215 Statement visitWhileCondition(WhileCondition node) { | 224 Statement visitWhileCondition(WhileCondition node) { |
| 216 throw "WhileCondition before LoopRewriter"; | 225 throw "WhileCondition before LoopRewriter"; |
| 217 } | 226 } |
| 218 | 227 |
| 219 Statement visitTry(Try node) { | 228 Statement visitTry(Try node) { |
| 229 enclosingTrys++; |
| 220 node.tryBody = visitBasicBlock(node.tryBody); | 230 node.tryBody = visitBasicBlock(node.tryBody); |
| 231 enclosingTrys--; |
| 221 node.catchBody = visitBasicBlock(node.catchBody); | 232 node.catchBody = visitBasicBlock(node.catchBody); |
| 222 return node; | 233 return node; |
| 223 } | 234 } |
| 224 | 235 |
| 225 Statement visitFunctionDeclaration(FunctionDeclaration node) { | 236 Statement visitFunctionDeclaration(FunctionDeclaration node) { |
| 226 // Unlike var declarations, function declarations are not hoisted, so we | 237 // Unlike var declarations, function declarations are not hoisted, so we |
| 227 // can't do copy propagation of the variable. | 238 // can't do copy propagation of the variable. |
| 228 new CopyPropagator().rewrite(node.definition); | 239 new CopyPropagator().rewrite(node.definition); |
| 229 node.next = visitStatement(node.next); | 240 node.next = visitStatement(node.next); |
| 230 return node; | 241 return node; |
| (...skipping 14 matching lines...) Expand all Loading... |
| 245 | 256 |
| 246 void visitFunctionExpression(FunctionExpression node) { | 257 void visitFunctionExpression(FunctionExpression node) { |
| 247 new CopyPropagator().rewrite(node.definition); | 258 new CopyPropagator().rewrite(node.definition); |
| 248 } | 259 } |
| 249 | 260 |
| 250 void visitFieldInitializer(FieldInitializer node) { | 261 void visitFieldInitializer(FieldInitializer node) { |
| 251 visitStatement(node.body); | 262 visitStatement(node.body); |
| 252 } | 263 } |
| 253 | 264 |
| 254 } | 265 } |
| OLD | NEW |