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

Side by Side Diff: pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart

Issue 1251083002: dart2js cps: Avoid deep recursion using trampolines and basic blocks. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Fix a comment Created 5 years, 5 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) 2013, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2013, 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 library dart2js.ir_nodes; 4 library dart2js.ir_nodes;
5 5
6 import '../constants/values.dart' as values show ConstantValue; 6 import '../constants/values.dart' as values show ConstantValue;
7 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType; 7 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
8 import '../elements/elements.dart'; 8 import '../elements/elements.dart';
9 import '../io/source_information.dart' show SourceInformation; 9 import '../io/source_information.dart' show SourceInformation;
10 import '../types/types.dart' show TypeMask; 10 import '../types/types.dart' show TypeMask;
(...skipping 1124 matching lines...) Expand 10 before | Expand all | Expand 10 after
1135 T visitGetIndex(GetIndex node); 1135 T visitGetIndex(GetIndex node);
1136 T visitSetIndex(SetIndex node); 1136 T visitSetIndex(SetIndex node);
1137 1137
1138 // Conditions. 1138 // Conditions.
1139 T visitIsTrue(IsTrue node); 1139 T visitIsTrue(IsTrue node);
1140 1140
1141 // Support for literal foreign code. 1141 // Support for literal foreign code.
1142 T visitForeignCode(ForeignCode node); 1142 T visitForeignCode(ForeignCode node);
1143 } 1143 }
1144 1144
1145 /// Recursively visits the entire CPS term, and calls abstract `process*` 1145 /// Visits all non-recursive children of a CPS term, i.e. anything
1146 /// (i.e. `processLetPrim`) functions in pre-order. 1146 /// not of type [Expression] or [Continuation].
1147 class RecursiveVisitor implements Visitor { 1147 ///
1148 const RecursiveVisitor(); 1148 /// Note that the non-recursive nodes can contain other nodes inside of them,
1149 /// e.g. [Branch] contains an [IsTrue] which contains a [Reference].
1150 ///
1151 /// The `process*` methods are called in pre-order for every node visited.
1152 /// These can be overridden without disrupting the visitor traversal.
1153 class LeafVisitor implements Visitor {
1154 const LeafVisitor();
1149 1155
1150 visit(Node node) => node.accept(this); 1156 visit(Node node) => node.accept(this);
1151 1157
1152 processReference(Reference ref) {} 1158 processReference(Reference ref) {}
1153 1159
1154 processFunctionDefinition(FunctionDefinition node) {} 1160 processFunctionDefinition(FunctionDefinition node) {}
1155 visitFunctionDefinition(FunctionDefinition node) { 1161 visitFunctionDefinition(FunctionDefinition node) {
1156 processFunctionDefinition(node); 1162 processFunctionDefinition(node);
1157 if (node.thisParameter != null) visit(node.thisParameter); 1163 if (node.thisParameter != null) visit(node.thisParameter);
1158 node.parameters.forEach(visit); 1164 node.parameters.forEach(visit);
1159 visit(node.returnContinuation); 1165 visit(node.returnContinuation);
1160 visit(node.body);
1161 } 1166 }
1162 1167
1163 // Expressions. 1168 // Expressions.
1164 1169
1165 processLetPrim(LetPrim node) {} 1170 processLetPrim(LetPrim node) {}
1166 visitLetPrim(LetPrim node) { 1171 visitLetPrim(LetPrim node) {
1167 processLetPrim(node); 1172 processLetPrim(node);
1168 visit(node.primitive); 1173 visit(node.primitive);
1169 visit(node.body);
1170 } 1174 }
1171 1175
1172 processLetCont(LetCont node) {} 1176 processLetCont(LetCont node) {}
1173 visitLetCont(LetCont node) { 1177 visitLetCont(LetCont node) {
1174 processLetCont(node); 1178 processLetCont(node);
1175 node.continuations.forEach(visit); 1179 node.continuations.forEach(visit);
1176 visit(node.body);
1177 } 1180 }
1178 1181
1179 processLetHandler(LetHandler node) {} 1182 processLetHandler(LetHandler node) {}
1180 visitLetHandler(LetHandler node) { 1183 visitLetHandler(LetHandler node) {
1181 processLetHandler(node); 1184 processLetHandler(node);
1182 visit(node.handler);
1183 visit(node.body);
1184 } 1185 }
1185 1186
1186 processLetMutable(LetMutable node) {} 1187 processLetMutable(LetMutable node) {}
1187 visitLetMutable(LetMutable node) { 1188 visitLetMutable(LetMutable node) {
1188 processLetMutable(node); 1189 processLetMutable(node);
1189 visit(node.variable); 1190 visit(node.variable);
1190 processReference(node.value); 1191 processReference(node.value);
1191 visit(node.body);
1192 } 1192 }
1193 1193
1194 processInvokeStatic(InvokeStatic node) {} 1194 processInvokeStatic(InvokeStatic node) {}
1195 visitInvokeStatic(InvokeStatic node) { 1195 visitInvokeStatic(InvokeStatic node) {
1196 processInvokeStatic(node); 1196 processInvokeStatic(node);
1197 processReference(node.continuation); 1197 processReference(node.continuation);
1198 node.arguments.forEach(processReference); 1198 node.arguments.forEach(processReference);
1199 } 1199 }
1200 1200
1201 processInvokeContinuation(InvokeContinuation node) {} 1201 processInvokeContinuation(InvokeContinuation node) {}
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after
1314 1314
1315 processParameter(Parameter node) {} 1315 processParameter(Parameter node) {}
1316 visitParameter(Parameter node) { 1316 visitParameter(Parameter node) {
1317 processParameter(node); 1317 processParameter(node);
1318 } 1318 }
1319 1319
1320 processContinuation(Continuation node) {} 1320 processContinuation(Continuation node) {}
1321 visitContinuation(Continuation node) { 1321 visitContinuation(Continuation node) {
1322 processContinuation(node); 1322 processContinuation(node);
1323 node.parameters.forEach(visitParameter); 1323 node.parameters.forEach(visitParameter);
1324 if (node.body != null) visit(node.body);
1325 } 1324 }
1326 1325
1327 processIsTrue(IsTrue node) {} 1326 processIsTrue(IsTrue node) {}
1328 visitIsTrue(IsTrue node) { 1327 visitIsTrue(IsTrue node) {
1329 processIsTrue(node); 1328 processIsTrue(node);
1330 processReference(node.value); 1329 processReference(node.value);
1331 } 1330 }
1332 1331
1333 processInterceptor(Interceptor node) {} 1332 processInterceptor(Interceptor node) {}
1334 visitInterceptor(Interceptor node) { 1333 visitInterceptor(Interceptor node) {
(...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after
1431 1430
1432 processSetIndex(SetIndex node) {} 1431 processSetIndex(SetIndex node) {}
1433 visitSetIndex(SetIndex node) { 1432 visitSetIndex(SetIndex node) {
1434 processSetIndex(node); 1433 processSetIndex(node);
1435 processReference(node.object); 1434 processReference(node.object);
1436 processReference(node.index); 1435 processReference(node.index);
1437 processReference(node.value); 1436 processReference(node.value);
1438 } 1437 }
1439 } 1438 }
1440 1439
1440 typedef dynamic StackAction();
karlklose 2015/07/22 14:08:06 The return type should be void, the result seems n
asgerf 2015/07/22 14:32:25 Done.
1441
1442 /// Calls `process*` for all nodes in a tree.
1443 /// For simple usage, only override the `process*` methods.
1444 ///
1445 /// To avoid deep recursion, this class uses an "action stack" containing
1446 /// callbacks to be invoked after the processing of some term has finished.
1447 ///
1448 /// To avoid excessive overhead from the action stack, basic blocks of
1449 /// interior nodes are iterated in a loop without using the action stack.
1450 ///
1451 /// The iteration order can be controlled by overriding the `traverse*`
1452 /// methods for [LetCont], [LetPrim], [LetMutable], [LetHandler] and
1453 /// [Continuation].
1454 ///
1455 /// The `traverse*` methods return the expression to visit next, and may
1456 /// push other subterms onto the stack using [push] or [pushAction] to visit
1457 /// them later. Actions pushed onto the stack will be executed after the body
1458 /// has been processed (and the stack actions it pushed have been executed).
1459 ///
1460 /// By default, the `traverse` methods visit all non-recursive subterms,
1461 /// push all bound continuations on the stack, and return the body of the term.
1462 ///
1463 /// Subclasses should not override the `visit` methods for the nodes that have
1464 /// a `traverse` method.
1465 class RecursiveVisitor extends LeafVisitor {
1466 List<StackAction> _stack = <StackAction>[];
1467
1468 void pushAction(StackAction callback) {
1469 _stack.add(callback);
1470 }
1471
1472 void push(Continuation cont) {
1473 _stack.add(() {
1474 if (cont.isReturnContinuation) {
1475 traverseContinuation(cont);
1476 } else {
1477 _processBlock(traverseContinuation(cont));
1478 }
1479 });
1480 }
1481
1482 visitFunctionDefinition(FunctionDefinition node) {
1483 processFunctionDefinition(node);
1484 if (node.thisParameter != null) visit(node.thisParameter);
1485 node.parameters.forEach(visit);
1486 visit(node.returnContinuation);
1487 visit(node.body);
1488 }
1489
1490 visitContinuation(Continuation cont) {
1491 if (cont.isReturnContinuation) {
1492 traverseContinuation(cont);
1493 } else {
1494 _trampoline(traverseContinuation(cont));
1495 }
1496 }
1497
1498 visitLetPrim(LetPrim node) => _trampoline(node);
1499 visitLetCont(LetCont node) => _trampoline(node);
1500 visitLetHandler(LetHandler node) => _trampoline(node);
1501 visitLetMutable(LetMutable node) => _trampoline(node);
1502
1503 Expression traverseContinuation(Continuation cont) {
1504 processContinuation(cont);
1505 cont.parameters.forEach(visitParameter);
1506 return cont.body;
1507 }
1508
1509 Expression traverseLetCont(LetCont node) {
1510 processLetCont(node);
1511 node.continuations.forEach(push);
1512 return node.body;
1513 }
1514
1515 Expression traverseLetHandler(LetHandler node) {
1516 processLetHandler(node);
1517 push(node.handler);
1518 return node.body;
1519 }
1520
1521 Expression traverseLetPrim(LetPrim node) {
1522 processLetPrim(node);
1523 visit(node.primitive);
1524 return node.body;
1525 }
1526
1527 Expression traverseLetMutable(LetMutable node) {
1528 processLetMutable(node);
1529 visit(node.variable);
1530 processReference(node.value);
1531 return node.body;
1532 }
1533
1534 void _trampoline(Expression node) {
1535 int initialHeight = _stack.length;
1536 _processBlock(node);
1537 while (_stack.length > initialHeight) {
1538 StackAction callback = _stack.removeLast();
1539 callback();
1540 }
1541 }
1542
1543 _processBlock(Expression node) {
1544 while (node is InteriorExpression) {
1545 if (node is LetCont) {
1546 node = traverseLetCont(node);
1547 } else if (node is LetHandler) {
1548 node = traverseLetHandler(node);
1549 } else if (node is LetPrim) {
1550 node = traverseLetPrim(node);
1551 } else {
1552 node = traverseLetMutable(node);
1553 }
1554 }
1555 visit(node);
1556 }
1557 }
1558
1441 /// Visit a just-deleted subterm and unlink all [Reference]s in it. 1559 /// Visit a just-deleted subterm and unlink all [Reference]s in it.
1442 class RemovalVisitor extends RecursiveVisitor { 1560 class RemovalVisitor extends RecursiveVisitor {
1443 const RemovalVisitor();
1444
1445 processReference(Reference reference) { 1561 processReference(Reference reference) {
1446 reference.unlink(); 1562 reference.unlink();
1447 } 1563 }
1448 1564
1449 static void remove(Node node) { 1565 static void remove(Node node) {
1450 (const RemovalVisitor()).visit(node); 1566 (new RemovalVisitor()).visit(node);
1451 } 1567 }
1452 } 1568 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698