Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(162)

Side by Side Diff: pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart

Issue 1155463005: dart2js cps: Remove dart2dart from cps pipeline and clean up. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Created 5 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698