| OLD | NEW |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, 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 library tree_ir.optimization.variable_merger; | 5 library tree_ir.optimization.variable_merger; |
| 6 | 6 |
| 7 import 'optimization.dart' show Pass; | 7 import 'optimization.dart' show Pass; |
| 8 import '../tree_ir_nodes.dart'; | 8 import '../tree_ir_nodes.dart'; |
| 9 | 9 |
| 10 /// Merges variables based on liveness and source variable information. | 10 /// Merges variables based on liveness and source variable information. |
| 11 /// | 11 /// |
| 12 /// This phase cleans up artifacts introduced by the translation through CPS, | 12 /// This phase cleans up artifacts introduced by the translation through CPS, |
| 13 /// where each source variable is translated into several copies. The copies | 13 /// where each source variable is translated into several copies. The copies |
| 14 /// are merged again when they are not live simultaneously. | 14 /// are merged again when they are not live simultaneously. |
| 15 class VariableMerger extends RecursiveVisitor implements Pass { | 15 class VariableMerger extends RecursiveVisitor implements Pass { |
| 16 String get passName => 'Variable merger'; | 16 String get passName => 'Variable merger'; |
| 17 | 17 |
| 18 void rewrite(RootNode node) { | 18 void rewrite(FunctionDefinition node) { |
| 19 rewriteFunction(node); | 19 rewriteFunction(node); |
| 20 node.forEachBody(visitStatement); | 20 visitStatement(node.body); |
| 21 } | 21 } |
| 22 | 22 |
| 23 @override | 23 @override |
| 24 void visitInnerFunction(FunctionDefinition node) { | 24 void visitInnerFunction(FunctionDefinition node) { |
| 25 rewriteFunction(node); | 25 rewriteFunction(node); |
| 26 } | 26 } |
| 27 | 27 |
| 28 /// Rewrites the given function. | 28 /// Rewrites the given function. |
| 29 /// This is called for the outermost function and inner functions. | 29 /// This is called for the outermost function and inner functions. |
| 30 void rewriteFunction(RootNode node) { | 30 void rewriteFunction(FunctionDefinition node) { |
| 31 node.forEachBody((Statement body) { | 31 BlockGraphBuilder builder = new BlockGraphBuilder(); |
| 32 BlockGraphBuilder builder = new BlockGraphBuilder(); | 32 builder.build(node); |
| 33 builder.build(node.parameters, body); | 33 _computeLiveness(builder.blocks); |
| 34 _computeLiveness(builder.blocks); | 34 Map<Variable, Variable> subst = |
| 35 Map<Variable, Variable> subst = | 35 _computeRegisterAllocation(builder.blocks, node.parameters); |
| 36 _computeRegisterAllocation(builder.blocks, node.parameters); | 36 new SubstituteVariables(subst).apply(node); |
| 37 new SubstituteVariables(subst).apply(node); | |
| 38 }); | |
| 39 } | 37 } |
| 40 } | 38 } |
| 41 | 39 |
| 42 /// A read or write access to a variable. | 40 /// A read or write access to a variable. |
| 43 class VariableAccess { | 41 class VariableAccess { |
| 44 Variable variable; | 42 Variable variable; |
| 45 bool isRead; | 43 bool isRead; |
| 46 bool get isWrite => !isRead; | 44 bool get isWrite => !isRead; |
| 47 | 45 |
| 48 VariableAccess.read(this.variable) : isRead = true; | 46 VariableAccess.read(this.variable) : isRead = true; |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 101 Map<Label, Block> _jumpTarget = <Label, Block>{}; | 99 Map<Label, Block> _jumpTarget = <Label, Block>{}; |
| 102 Block _currentBlock; | 100 Block _currentBlock; |
| 103 List<Block> blocks = <Block>[]; | 101 List<Block> blocks = <Block>[]; |
| 104 | 102 |
| 105 /// Variables with an assignment that should be treated as final. | 103 /// Variables with an assignment that should be treated as final. |
| 106 /// | 104 /// |
| 107 /// Such variables cannot be merged with any other variables, so we exclude | 105 /// Such variables cannot be merged with any other variables, so we exclude |
| 108 /// them from the control-flow graph entirely. | 106 /// them from the control-flow graph entirely. |
| 109 Set<Variable> _ignoredVariables = new Set<Variable>(); | 107 Set<Variable> _ignoredVariables = new Set<Variable>(); |
| 110 | 108 |
| 111 void build(List<Variable> parameters, Statement body) { | 109 void build(FunctionDefinition node) { |
| 112 _currentBlock = newBlock(); | 110 _currentBlock = newBlock(); |
| 113 parameters.forEach(write); | 111 node.parameters.forEach(write); |
| 114 visitStatement(body); | 112 visitStatement(node.body); |
| 115 } | 113 } |
| 116 | 114 |
| 117 @override | 115 @override |
| 118 void visitInnerFunction(FunctionDefinition node) { | 116 void visitInnerFunction(FunctionDefinition node) { |
| 119 // Do nothing. Inner functions are traversed in VariableMerger. | 117 // Do nothing. Inner functions are traversed in VariableMerger. |
| 120 } | 118 } |
| 121 | 119 |
| 122 /// Creates a new block with the current exception handler or [catchBlock] | 120 /// Creates a new block with the current exception handler or [catchBlock] |
| 123 /// if provided. | 121 /// if provided. |
| 124 Block newBlock({Block catchBlock}) { | 122 Block newBlock({Block catchBlock}) { |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 157 /// be excluded from the control-flow graph. | 155 /// be excluded from the control-flow graph. |
| 158 /// Subsequent calls to [read] and [write] will ignore it. | 156 /// Subsequent calls to [read] and [write] will ignore it. |
| 159 void ignoreVariable(Variable variable) { | 157 void ignoreVariable(Variable variable) { |
| 160 _ignoredVariables.add(variable); | 158 _ignoredVariables.add(variable); |
| 161 } | 159 } |
| 162 | 160 |
| 163 visitVariableUse(VariableUse node) { | 161 visitVariableUse(VariableUse node) { |
| 164 read(node.variable); | 162 read(node.variable); |
| 165 } | 163 } |
| 166 | 164 |
| 167 visitVariableDeclaration(VariableDeclaration node) { | |
| 168 assert(node.variable.isCaptured); | |
| 169 visitStatement(node.next); | |
| 170 } | |
| 171 | |
| 172 visitAssign(Assign node) { | 165 visitAssign(Assign node) { |
| 173 visitExpression(node.value); | 166 visitExpression(node.value); |
| 174 write(node.variable); | 167 write(node.variable); |
| 175 } | 168 } |
| 176 | 169 |
| 177 visitIf(If node) { | 170 visitIf(If node) { |
| 178 visitExpression(node.condition); | 171 visitExpression(node.condition); |
| 179 Block afterCondition = _currentBlock; | 172 Block afterCondition = _currentBlock; |
| 180 branchFrom(afterCondition); | 173 branchFrom(afterCondition); |
| 181 visitStatement(node.thenStatement); | 174 visitStatement(node.thenStatement); |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 236 branchFrom(afterCondition); | 229 branchFrom(afterCondition); |
| 237 visitExpression(node.elseExpression); | 230 visitExpression(node.elseExpression); |
| 238 } | 231 } |
| 239 | 232 |
| 240 visitLogicalOperator(LogicalOperator node) { | 233 visitLogicalOperator(LogicalOperator node) { |
| 241 visitExpression(node.left); | 234 visitExpression(node.left); |
| 242 Block afterCondition = _currentBlock; | 235 Block afterCondition = _currentBlock; |
| 243 branchFrom(afterCondition); | 236 branchFrom(afterCondition); |
| 244 visitExpression(node.right); | 237 visitExpression(node.right); |
| 245 } | 238 } |
| 246 | |
| 247 visitFunctionDeclaration(FunctionDeclaration node) { | |
| 248 // The function variable is final, hence cannot be merged. | |
| 249 ignoreVariable(node.variable); | |
| 250 visitStatement(node.next); | |
| 251 } | |
| 252 } | 239 } |
| 253 | 240 |
| 254 /// Computes liveness information of the given control-flow graph. | 241 /// Computes liveness information of the given control-flow graph. |
| 255 /// | 242 /// |
| 256 /// The results are stored in [Block.liveIn] and [Block.liveOut]. | 243 /// The results are stored in [Block.liveIn] and [Block.liveOut]. |
| 257 void _computeLiveness(List<Block> blocks) { | 244 void _computeLiveness(List<Block> blocks) { |
| 258 // We use a LIFO queue as worklist. Blocks are given in AST order, so by | 245 // We use a LIFO queue as worklist. Blocks are given in AST order, so by |
| 259 // inserting them in this order, we initially visit them backwards, which | 246 // inserting them in this order, we initially visit them backwards, which |
| 260 // is a good ordering. | 247 // is a good ordering. |
| 261 // The choice of LIFO for re-inserted blocks is currently arbitrary, | 248 // The choice of LIFO for re-inserted blocks is currently arbitrary, |
| (...skipping 223 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 485 } | 472 } |
| 486 | 473 |
| 487 Variable replaceWrite(Variable variable) { | 474 Variable replaceWrite(Variable variable) { |
| 488 Variable w = mapping[variable]; | 475 Variable w = mapping[variable]; |
| 489 if (w == null) return variable; // Skip ignored variables. | 476 if (w == null) return variable; // Skip ignored variables. |
| 490 w.writeCount++; | 477 w.writeCount++; |
| 491 variable.writeCount--; | 478 variable.writeCount--; |
| 492 return w; | 479 return w; |
| 493 } | 480 } |
| 494 | 481 |
| 495 void apply(RootNode node) { | 482 void apply(FunctionDefinition node) { |
| 496 for (int i = 0; i < node.parameters.length; ++i) { | 483 for (int i = 0; i < node.parameters.length; ++i) { |
| 497 node.parameters[i] = replaceWrite(node.parameters[i]); | 484 node.parameters[i] = replaceWrite(node.parameters[i]); |
| 498 } | 485 } |
| 499 node.replaceEachBody(visitStatement); | 486 node.body = visitStatement(node.body); |
| 500 } | 487 } |
| 501 | 488 |
| 502 @override | 489 @override |
| 503 void visitInnerFunction(FunctionDefinition node) { | 490 void visitInnerFunction(FunctionDefinition node) { |
| 504 // Do nothing. Inner functions are traversed in VariableMerger. | 491 // Do nothing. Inner functions are traversed in VariableMerger. |
| 505 } | 492 } |
| 506 | 493 |
| 507 Expression visitVariableUse(VariableUse node) { | 494 Expression visitVariableUse(VariableUse node) { |
| 508 node.variable = replaceRead(node.variable); | 495 node.variable = replaceRead(node.variable); |
| 509 return node; | 496 return node; |
| (...skipping 18 matching lines...) Expand all Loading... |
| 528 Statement visitExpressionStatement(ExpressionStatement node) { | 515 Statement visitExpressionStatement(ExpressionStatement node) { |
| 529 node.expression = visitExpression(node.expression); | 516 node.expression = visitExpression(node.expression); |
| 530 node.next = visitStatement(node.next); | 517 node.next = visitStatement(node.next); |
| 531 if (node.expression is VariableUse) { | 518 if (node.expression is VariableUse) { |
| 532 VariableUse use = node.expression; | 519 VariableUse use = node.expression; |
| 533 --use.variable.readCount; | 520 --use.variable.readCount; |
| 534 return node.next; | 521 return node.next; |
| 535 } | 522 } |
| 536 return node; | 523 return node; |
| 537 } | 524 } |
| 538 | |
| 539 Statement visitVariableDeclaration(VariableDeclaration node) { | |
| 540 // VariableDeclaration is only used for captured variables, which are never | |
| 541 // merged, so this is not strictly necessary. But it's nicer if this class | |
| 542 // works for arbitrary substitution maps. | |
| 543 node.variable = replaceWrite(node.variable); | |
| 544 node.value = visitExpression(node.value); | |
| 545 node.next = visitStatement(node.next); | |
| 546 return node; | |
| 547 } | |
| 548 | |
| 549 } | 525 } |
| OLD | NEW |