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

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: frog/leg/ssa/builder.dart

Issue 9863037: Generate prettier loops. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Adressed review comments. A few fixes. Created 8 years, 8 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 | Annotate | Revision Log
« no previous file with comments | « frog/leg/scanner/parser.dart ('k') | frog/leg/ssa/codegen.dart » ('j') | frog/leg/ssa/codegen.dart » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2012, 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 class Interceptors { 5 class Interceptors {
6 Compiler compiler; 6 Compiler compiler;
7 Interceptors(Compiler this.compiler); 7 Interceptors(Compiler this.compiler);
8 8
9 SourceString mapOperatorToMethodName(Operator op) { 9 SourceString mapOperatorToMethodName(Operator op) {
10 String name = op.source.stringValue; 10 String name = op.source.stringValue;
(...skipping 613 matching lines...) Expand 10 before | Expand all | Expand 10 after
624 } 624 }
625 625
626 626
627 interface JumpHandler default JumpHandlerImpl { 627 interface JumpHandler default JumpHandlerImpl {
628 JumpHandler(SsaBuilder builder, TargetElement target); 628 JumpHandler(SsaBuilder builder, TargetElement target);
629 void generateBreak([LabelElement label]); 629 void generateBreak([LabelElement label]);
630 void generateContinue([LabelElement label]); 630 void generateContinue([LabelElement label]);
631 void forEachBreak(void action(HBreak instruction, LocalsHandler locals)); 631 void forEachBreak(void action(HBreak instruction, LocalsHandler locals));
632 void forEachContinue(void action(HBreak instruction, LocalsHandler locals)); 632 void forEachContinue(void action(HBreak instruction, LocalsHandler locals));
633 void close(); 633 void close();
634 final TargetElement target;
634 List<LabelElement> labels(); 635 List<LabelElement> labels();
635 } 636 }
636 637
637 // Insert break handler used to avoid null checks when a target isn't 638 // Insert break handler used to avoid null checks when a target isn't
638 // used as the target of a break, and therefore doesn't need a break 639 // used as the target of a break, and therefore doesn't need a break
639 // handler associated with it. 640 // handler associated with it.
640 class NullJumpHandler implements JumpHandler { 641 class NullJumpHandler implements JumpHandler {
641 const NullJumpHandler(); 642 const NullJumpHandler();
642 void generateBreak([LabelElement label]) { unreachable(); } 643 void generateBreak([LabelElement label]) { unreachable(); }
643 void generateContinue([LabelElement label]) { unreachable(); } 644 void generateContinue([LabelElement label]) { unreachable(); }
644 void forEachBreak(Function ignored) { } 645 void forEachBreak(Function ignored) { }
645 void forEachContinue(Function ignored) { } 646 void forEachContinue(Function ignored) { }
646 void close() { } 647 void close() { }
648 final TargetElement target = null;
647 List<LabelElement> labels() => const <LabelElement>[]; 649 List<LabelElement> labels() => const <LabelElement>[];
648 } 650 }
649 651
650 // Records breaks until a target block is available. 652 // Records breaks until a target block is available.
651 // Breaks are always forward jumps. 653 // Breaks are always forward jumps.
652 // Continues in loops are implemented as breaks of the body. 654 // Continues in loops are implemented as breaks of the body.
653 // Continues in switches is currently not handled. 655 // Continues in switches is currently not handled.
654 class JumpHandlerImpl implements JumpHandler { 656 class JumpHandlerImpl implements JumpHandler {
655 final SsaBuilder builder; 657 final SsaBuilder builder;
656 final TargetElement target; 658 final TargetElement target;
(...skipping 401 matching lines...) Expand 10 before | Expand all | Expand 10 after
1058 /** 1060 /**
1059 * Creates a new loop-header block. The previous [current] block 1061 * Creates a new loop-header block. The previous [current] block
1060 * is closed with an [HGoto] and replaced by the newly created block. 1062 * is closed with an [HGoto] and replaced by the newly created block.
1061 * Also notifies the locals handler that we're entering a loop. 1063 * Also notifies the locals handler that we're entering a loop.
1062 */ 1064 */
1063 JumpHandler beginLoopHeader(Node node) { 1065 JumpHandler beginLoopHeader(Node node) {
1064 assert(!isAborted()); 1066 assert(!isAborted());
1065 HBasicBlock previousBlock = close(new HGoto()); 1067 HBasicBlock previousBlock = close(new HGoto());
1066 1068
1067 JumpHandler jumpHandler = createJumpHandler(node); 1069 JumpHandler jumpHandler = createJumpHandler(node);
1068 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(jumpHandler.labels()); 1070 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(
1071 HLoopInformation.loopType(node),
1072 jumpHandler.target,
1073 jumpHandler.labels());
1069 previousBlock.addSuccessor(loopEntry); 1074 previousBlock.addSuccessor(loopEntry);
1070 open(loopEntry); 1075 open(loopEntry);
1071 1076
1072 localsHandler.beginLoopHeader(node, loopEntry); 1077 localsHandler.beginLoopHeader(node, loopEntry);
1073 return jumpHandler; 1078 return jumpHandler;
1074 } 1079 }
1075 1080
1076 /** 1081 /**
1077 * Ends the loop: 1082 * Ends the loop:
1078 * - creates a new block and adds it as successor to the [branchBlock]. 1083 * - creates a new block and adds it as successor to the [branchBlock].
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
1114 // loop-entry: 1119 // loop-entry:
1115 // if (!<condition>) goto loop-exit; 1120 // if (!<condition>) goto loop-exit;
1116 // <body> 1121 // <body>
1117 // <updates> 1122 // <updates>
1118 // goto loop-entry; 1123 // goto loop-entry;
1119 // loop-exit: 1124 // loop-exit:
1120 1125
1121 localsHandler.startLoop(loop); 1126 localsHandler.startLoop(loop);
1122 1127
1123 // The initializer. 1128 // The initializer.
1129 HBasicBlock initializerBlock = graph.addNewBlock();
1130 goto(current, initializerBlock);
1131 open(initializerBlock);
1124 initialize(); 1132 initialize();
1125 assert(!isAborted()); 1133 assert(!isAborted());
1134 SubGraph initializerGraph = new SubGraph(initializerBlock, current);
1126 1135
1127 JumpHandler jumpHandler = beginLoopHeader(loop); 1136 JumpHandler jumpHandler = beginLoopHeader(loop);
1128 HBasicBlock conditionBlock = current; 1137 HBasicBlock conditionBlock = current;
1138 HLoopInformation loopInfo = current.loopInformation;
1139 // The initializer graph is currently unused due to the way we
1140 // generate code.
1141 loopInfo.initializer = initializerGraph;
1129 1142
1130 HInstruction conditionInstruction = condition(); 1143 HInstruction conditionInstruction = condition();
1131 HBasicBlock conditionExitBlock = 1144 HBasicBlock conditionExitBlock =
1132 close(new HLoopBranch(conditionInstruction)); 1145 close(new HLoopBranch(conditionInstruction));
1146 loopInfo.condition = new SubExpression(conditionBlock,
1147 conditionExitBlock,
1148 conditionInstruction);
1133 1149
1134 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 1150 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
1135 1151
1136 // The body. 1152 // The body.
1137 HBasicBlock beginBodyBlock = addNewBlock(); 1153 HBasicBlock beginBodyBlock = addNewBlock();
1138 conditionExitBlock.addSuccessor(beginBodyBlock); 1154 conditionExitBlock.addSuccessor(beginBodyBlock);
1139 open(beginBodyBlock); 1155 open(beginBodyBlock);
1140 1156
1141 localsHandler.enterLoopBody(loop); 1157 localsHandler.enterLoopBody(loop);
1142 hackAroundPossiblyAbortingBody(loop, body); 1158 hackAroundPossiblyAbortingBody(loop, body);
1143 1159
1144 SubGraph bodyGraph = new SubGraph(beginBodyBlock, current); 1160 SubGraph bodyGraph = new SubGraph(beginBodyBlock, current);
1145 HBasicBlock bodyBlock = close(new HGoto()); 1161 HBasicBlock bodyBlock = close(new HGoto());
1162 loopInfo.body = bodyGraph;
1146 1163
1147 // Update. 1164 // Update.
1148 // We create an update block, even when we are in a while loop. There the 1165 // We create an update block, even when we are in a while loop. There the
1149 // update block is the jump-target for continue statements. We could avoid 1166 // update block is the jump-target for continue statements. We could avoid
1150 // the creation if there is no continue, but for now we always create it. 1167 // the creation if there is no continue, but for now we always create it.
1151 HBasicBlock updateBlock = addNewBlock(); 1168 HBasicBlock updateBlock = addNewBlock();
1152 1169
1153 List<LocalsHandler> continueLocals = <LocalsHandler>[]; 1170 List<LocalsHandler> continueLocals = <LocalsHandler>[];
1154 jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) { 1171 jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {
1155 instruction.block.addSuccessor(updateBlock); 1172 instruction.block.addSuccessor(updateBlock);
(...skipping 16 matching lines...) Expand all
1172 } else if (target !== null && target.isContinueTarget) { 1189 } else if (target !== null && target.isContinueTarget) {
1173 beginBodyBlock.labeledBlockInformation = 1190 beginBodyBlock.labeledBlockInformation =
1174 new HLabeledBlockInformation.implicit(bodyGraph, updateBlock, 1191 new HLabeledBlockInformation.implicit(bodyGraph, updateBlock,
1175 target, isContinue: true); 1192 target, isContinue: true);
1176 } 1193 }
1177 1194
1178 localsHandler.enterLoopUpdates(loop); 1195 localsHandler.enterLoopUpdates(loop);
1179 1196
1180 update(); 1197 update();
1181 1198
1182 updateBlock = close(new HGoto()); 1199 HBasicBlock updateEndBlock = close(new HGoto());
1183 // The back-edge completing the cycle. 1200 // The back-edge completing the cycle.
1184 updateBlock.addSuccessor(conditionBlock); 1201 updateEndBlock.addSuccessor(conditionBlock);
1185 conditionBlock.postProcessLoopHeader(); 1202 conditionBlock.postProcessLoopHeader();
1203 loopInfo.updates = new SubGraph(updateBlock, updateEndBlock);
1186 1204
1187 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals); 1205 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
1206 loopInfo.joinBlock = current;
1188 } 1207 }
1189 1208
1190 visitFor(For node) { 1209 visitFor(For node) {
1191 assert(node.body !== null); 1210 assert(node.body !== null);
1192 void buildInitializer() { 1211 void buildInitializer() {
1193 if (node.initializer === null) return; 1212 if (node.initializer === null) return;
1194 Node initializer = node.initializer; 1213 Node initializer = node.initializer;
1195 if (initializer !== null) { 1214 if (initializer !== null) {
1196 visit(initializer); 1215 visit(initializer);
1197 if (initializer.asExpression() !== null) { 1216 if (initializer.asExpression() !== null) {
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
1230 () {}, 1249 () {},
1231 buildCondition, 1250 buildCondition,
1232 () {}, 1251 () {},
1233 () { visit(node.body); }); 1252 () { visit(node.body); });
1234 } 1253 }
1235 1254
1236 visitDoWhile(DoWhile node) { 1255 visitDoWhile(DoWhile node) {
1237 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 1256 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
1238 localsHandler.startLoop(node); 1257 localsHandler.startLoop(node);
1239 JumpHandler jumpHandler = beginLoopHeader(node); 1258 JumpHandler jumpHandler = beginLoopHeader(node);
1259 HLoopInformation loopInfo = current.loopInformation;
1240 HBasicBlock loopEntryBlock = current; 1260 HBasicBlock loopEntryBlock = current;
1241 HBasicBlock bodyEntryBlock = current; 1261 HBasicBlock bodyEntryBlock = current;
1242 TargetElement target = elements[node]; 1262 TargetElement target = elements[node];
1243 bool hasContinues = target !== null && target.isContinueTarget; 1263 bool hasContinues = target !== null && target.isContinueTarget;
1244 if (hasContinues) { 1264 if (hasContinues) {
1245 // Add extra block to hang labels on. 1265 // Add extra block to hang labels on.
1246 // It doesn't currently work if they are on the same block as the 1266 // It doesn't currently work if they are on the same block as the
1247 // HLoopInfo. The handling of HLabeledBlockInformation will visit a 1267 // HLoopInfo. The handling of HLabeledBlockInformation will visit a
1248 // SubGraph that starts at the same block again, so the HLoopInfo is 1268 // SubGraph that starts at the same block again, so the HLoopInfo is
1249 // either handled twice, or it's handled after the labeled block info, 1269 // either handled twice, or it's handled after the labeled block info,
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
1283 new HLabeledBlockInformation.implicit(bodyGraph, 1303 new HLabeledBlockInformation.implicit(bodyGraph,
1284 conditionBlock, 1304 conditionBlock,
1285 target, 1305 target,
1286 isContinue: true); 1306 isContinue: true);
1287 } 1307 }
1288 } 1308 }
1289 open(conditionBlock); 1309 open(conditionBlock);
1290 1310
1291 visit(node.condition); 1311 visit(node.condition);
1292 assert(!isAborted()); 1312 assert(!isAborted());
1293 conditionBlock = close(new HLoopBranch(popBoolified(), 1313 HInstruction conditionInstruction = popBoolified();
1294 HLoopBranch.DO_WHILE_LOOP)); 1314 HBasicBLock conditionEndBlock =
1315 close(new HLoopBranch(conditionInstruction, HLoopBranch.DO_WHILE_LOOP));
1295 1316
1296 conditionBlock.addSuccessor(loopEntryBlock); // The back-edge. 1317 conditionEndBlock.addSuccessor(loopEntryBlock); // The back-edge.
1297 loopEntryBlock.postProcessLoopHeader(); 1318 loopEntryBlock.postProcessLoopHeader();
1298 1319
1299 endLoop(loopEntryBlock, conditionBlock, jumpHandler, localsHandler); 1320 endLoop(loopEntryBlock, conditionEndBlock, jumpHandler, localsHandler);
1300 jumpHandler.close(); 1321 jumpHandler.close();
1322
1323 loopInfo.body = new SubGraph(bodyEntryBlock, bodyExitBlock);
1324 loopInfo.condition = new SubExpression(conditionBlock, conditionEndBlock,
1325 conditionInstruction);
1326 loopInfo.joinBlock = current;
1301 } 1327 }
1302 1328
1303 visitFunctionExpression(FunctionExpression node) { 1329 visitFunctionExpression(FunctionExpression node) {
1304 ClosureData nestedClosureData = compiler.builder.closureDataCache[node]; 1330 ClosureData nestedClosureData = compiler.builder.closureDataCache[node];
1305 if (nestedClosureData === null) { 1331 if (nestedClosureData === null) {
1306 // TODO(floitsch): we can only assume that the reason for not having a 1332 // TODO(floitsch): we can only assume that the reason for not having a
1307 // closure data here is, because the function is inside an initializer. 1333 // closure data here is, because the function is inside an initializer.
1308 compiler.unimplemented("Closures inside initializers", node: node); 1334 compiler.unimplemented("Closures inside initializers", node: node);
1309 } 1335 }
1310 assert(nestedClosureData !== null); 1336 assert(nestedClosureData !== null);
(...skipping 1074 matching lines...) Expand 10 before | Expand all | Expand 10 after
2385 visitContinueStatement(ContinueStatement node) { 2411 visitContinueStatement(ContinueStatement node) {
2386 work.allowSpeculativeOptimization = false; 2412 work.allowSpeculativeOptimization = false;
2387 TargetElement target = elements[node]; 2413 TargetElement target = elements[node];
2388 assert(target !== null); 2414 assert(target !== null);
2389 JumpHandler handler = jumpTargets[target]; 2415 JumpHandler handler = jumpTargets[target];
2390 assert(handler !== null); 2416 assert(handler !== null);
2391 if (node.target === null) { 2417 if (node.target === null) {
2392 handler.generateContinue(); 2418 handler.generateContinue();
2393 } else { 2419 } else {
2394 LabelElement label = elements[node.target]; 2420 LabelElement label = elements[node.target];
2421 assert(label !== null);
2395 handler.generateContinue(label); 2422 handler.generateContinue(label);
2396 } 2423 }
2397 } 2424 }
2398 2425
2399 /** 2426 /**
2400 * Creates a [JumpHandler] for a statement. The node must be a jump 2427 * Creates a [JumpHandler] for a statement. The node must be a jump
2401 * target. If there are no breaks or continues targeting the statement, 2428 * target. If there are no breaks or continues targeting the statement,
2402 * a special "null handler" is returned. 2429 * a special "null handler" is returned.
2403 */ 2430 */
2404 JumpHandler createJumpHandler(Statement node) { 2431 JumpHandler createJumpHandler(Statement node) {
2405 TargetElement element = elements[node]; 2432 TargetElement element = elements[node];
2406 if (element === null || element.statement !== node) { 2433 if (element === null || element.statement !== node) {
2407 // No breaks or continues to this node. 2434 // No breaks or continues to this node.
2408 return const NullJumpHandler(); 2435 return const NullJumpHandler();
2409 } 2436 }
2410 return new JumpHandler(this, element); 2437 return new JumpHandler(this, element);
2411 } 2438 }
2412 2439
2413 visitForInStatement(ForInStatement node) { 2440 visitForIn(ForIn node) {
2414 // Generate a structure equivalent to: 2441 // Generate a structure equivalent to:
2415 // Iterator<E> $iter = <iterable>.iterator() 2442 // Iterator<E> $iter = <iterable>.iterator()
2416 // while ($iter.hasNext()) { 2443 // while ($iter.hasNext()) {
2417 // E <declaredIdentifier> = $iter.next(); 2444 // E <declaredIdentifier> = $iter.next();
2418 // <body> 2445 // <body>
2419 // } 2446 // }
2420 2447
2421 // All the generated calls are to zero-argument functions. 2448 // All the generated calls are to zero-argument functions.
2422 Selector selector = Selector.INVOCATION_0; 2449 Selector selector = Selector.INVOCATION_0;
2423 // The iterator is shared between initializer, condition and body. 2450 // The iterator is shared between initializer, condition and body.
(...skipping 538 matching lines...) Expand 10 before | Expand all | Expand 10 after
2962 false, 2989 false,
2963 <HInstruction>[target, input])); 2990 <HInstruction>[target, input]));
2964 return builder.pop(); 2991 return builder.pop();
2965 } 2992 }
2966 2993
2967 HInstruction result() { 2994 HInstruction result() {
2968 flushLiterals(); 2995 flushLiterals();
2969 return prefix; 2996 return prefix;
2970 } 2997 }
2971 } 2998 }
OLDNEW
« no previous file with comments | « frog/leg/scanner/parser.dart ('k') | frog/leg/ssa/codegen.dart » ('j') | frog/leg/ssa/codegen.dart » ('J')

Powered by Google App Engine
This is Rietveld 408576698