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

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

Issue 9718034: Continue for simple loops (while/for). (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Addressed review comments. Created 8 years, 9 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/resolver.dart ('k') | frog/leg/ssa/codegen.dart » ('j') | no next file with comments »
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 588 matching lines...) Expand 10 before | Expand all | Expand 10 after
599 if (thisValue !== null) { 599 if (thisValue !== null) {
600 // If there was a "this" for the scope, add it to the new locals. 600 // If there was a "this" for the scope, add it to the new locals.
601 joinedLocals[closureData.thisElement] = thisValue; 601 joinedLocals[closureData.thisElement] = thisValue;
602 } 602 }
603 directLocals = joinedLocals; 603 directLocals = joinedLocals;
604 return this; 604 return this;
605 } 605 }
606 } 606 }
607 607
608 608
609 // Represents a single break instruction. 609 // Represents a single break/continue instruction.
610 class BreakHandlerEntry { 610 class JumpHandlerEntry {
611 final HBreak breakInstruction; 611 final HGoto jumpInstruction;
612 final LocalsHandler locals; 612 final LocalsHandler locals;
613 BreakHandlerEntry(this.breakInstruction, this.locals); 613 bool isBreak() => jumpInstruction is HBreak;
614 bool isContinue() => jumpInstruction is HContinue;
615 JumpHandlerEntry(this.jumpInstruction, this.locals);
614 } 616 }
615 617
616 interface BreakHandler default BreakHandlerImpl { 618
617 BreakHandler(SsaBuilder builder, TargetElement target); 619 interface JumpHandler default JumpHandlerImpl {
618 void addBreak(HBreak breakInstruction, LocalsHandler locals); 620 JumpHandler(SsaBuilder builder, TargetElement target);
619 void forEachBreak(Function action); 621 void generateBreak([LabelElement label]);
622 void generateContinue([LabelElement label]);
623 void forEachBreak(void action(HBreak instruction, LocalsHandler locals));
624 void forEachContinue(void action(HBreak instruction, LocalsHandler locals));
620 void close(); 625 void close();
621 List<LabelElement> labels(); 626 List<LabelElement> labels();
622 } 627 }
623 628
624 // Inert break handler used to avoid null checks when a loop isn't 629 // Insert break handler used to avoid null checks when a target isn't
625 // used as the target of a break, and therefore doesn't need a break 630 // used as the target of a break, and therefore doesn't need a break
626 // handler associated with it. 631 // handler associated with it.
627 class NullBreakHandler implements BreakHandler { 632 class NullJumpHandler implements JumpHandler {
628 const NullBreakHandler(); 633 const NullJumpHandler();
629 void addBreak(HBreak breakInstruction, LocalsHandler locals) { 634 void generateBreak([LabelElement label]) { unreachable(); }
630 unreachable(); 635 void generateContinue([LabelElement label]) { unreachable(); }
631 }
632 void forEachBreak(Function ignored) { } 636 void forEachBreak(Function ignored) { }
637 void forEachContinue(Function ignored) { }
633 void close() { } 638 void close() { }
634 List<LabelElement> labels() => const <LabelElement>[]; 639 List<LabelElement> labels() => const <LabelElement>[];
635 } 640 }
636 641
637 // Records breaks until a target block is available. 642 // Records breaks until a target block is available.
638 // Breaks are always forward jumps. 643 // Breaks are always forward jumps.
639 class BreakHandlerImpl implements BreakHandler { 644 // Continues in loops are implemented as breaks of the body.
640 final BreakHandler previous; 645 // Continues in switches is currently not handled.
646 class JumpHandlerImpl implements JumpHandler {
641 final SsaBuilder builder; 647 final SsaBuilder builder;
642 final TargetElement target; 648 final TargetElement target;
643 final List<BreakHandlerEntry> breaks; 649 final List<JumpHandlerEntry> jumps;
644 BreakHandlerImpl(SsaBuilder builder, this.target) 650
651 JumpHandlerImpl(SsaBuilder builder, this.target)
645 : this.builder = builder, 652 : this.builder = builder,
646 previous = builder.currentBreakHandler, 653 jumps = <JumpHandlerEntry>[] {
647 breaks = <BreakHandlerEntry>[] { 654 assert(builder.jumpTargets[target] === null);
648 builder.currentBreakHandler = this; 655 builder.jumpTargets[target] = this;
649 assert(builder.breakTargets[target] === null);
650 builder.breakTargets[target] = this;
651 } 656 }
652 657
653 void addBreak(HBreak breakInstruction, LocalsHandler locals) { 658 void generateBreak([LabelElement label]) {
654 breaks.add(new BreakHandlerEntry(breakInstruction, locals)); 659 HInstruction breakInstruction;
660 if (label === null) {
661 breakInstruction = new HBreak(target);
662 } else {
663 breakInstruction = new HBreak.toLabel(label);
664 }
665 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
666 builder.close(breakInstruction);
667 jumps.add(new JumpHandlerEntry(breakInstruction, locals));
668 }
669
670 void generateContinue([LabelElement label]) {
671 HInstruction continueInstruction;
672 if (label === null) {
673 continueInstruction = new HContinue(target);
674 } else {
675 continueInstruction = new HContinue.toLabel(label);
676 }
677 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
678 builder.close(continueInstruction);
679 jumps.add(new JumpHandlerEntry(continueInstruction, locals));
655 } 680 }
656 681
657 void forEachBreak(Function action) { 682 void forEachBreak(Function action) {
658 for (BreakHandlerEntry entry in breaks) { 683 for (JumpHandlerEntry entry in jumps) {
659 action(entry.breakInstruction, entry.locals); 684 if (entry.isBreak()) action(entry.jumpInstruction, entry.locals);
685 }
686 }
687
688 void forEachContinue(Function action) {
689 for (JumpHandlerEntry entry in jumps) {
690 if (entry.isContinue()) action(entry.jumpInstruction, entry.locals);
660 } 691 }
661 } 692 }
662 693
663 void close() { 694 void close() {
664 assert(builder.currentBreakHandler === this); 695 // The mapping from TargetElement to JumpHandler is no longer needed.
665 // The mapping from TargetElement to BreakHandler is no longer needed. 696 builder.jumpTargets.remove(target);
666 builder.breakTargets.remove(target);
667 builder.currentBreakHandler = previous;
668 } 697 }
669 698
670 List<LabelElement> labels() { 699 List<LabelElement> labels() {
671 List<LabelElement> result = null; 700 List<LabelElement> result = null;
672 for (LabelElement element in target.labels) { 701 for (LabelElement element in target.labels) {
673 if (element.isBreakTarget) { 702 if (result === null) result = <LabelElement>[];
674 if (result === null) result = <LabelElement>[]; 703 result.add(element);
675 result.add(element);
676 }
677 } 704 }
678 return (result === null) ? const <LabelElement>[] : result; 705 return (result === null) ? const <LabelElement>[] : result;
679 } 706 }
680 } 707 }
681 708
682 class SsaBuilder implements Visitor { 709 class SsaBuilder implements Visitor {
683 final Compiler compiler; 710 final Compiler compiler;
684 TreeElements elements; 711 TreeElements elements;
685 final Interceptors interceptors; 712 final Interceptors interceptors;
686 final WorkItem work; 713 final WorkItem work;
687 bool methodInterceptionEnabled; 714 bool methodInterceptionEnabled;
688 HGraph graph; 715 HGraph graph;
689 LocalsHandler localsHandler; 716 LocalsHandler localsHandler;
690 HInstruction rethrowableException; 717 HInstruction rethrowableException;
691 718
692 Map<TargetElement, BreakHandler> breakTargets; 719 Map<TargetElement, JumpHandler> jumpTargets;
693 720
694 // We build the Ssa graph by simulating a stack machine. 721 // We build the Ssa graph by simulating a stack machine.
695 List<HInstruction> stack; 722 List<HInstruction> stack;
696 723
697 // The current block to add instructions to. Might be null, if we are 724 // The current block to add instructions to. Might be null, if we are
698 // visiting dead code. 725 // visiting dead code.
699 HBasicBlock current; 726 HBasicBlock current;
700 // The most recently opened block. Has the same value as [current] while 727 // The most recently opened block. Has the same value as [current] while
701 // the block is open, but unlike [current], it isn't cleared when the current 728 // the block is open, but unlike [current], it isn't cleared when the current
702 // block is closed. 729 // block is closed.
703 HBasicBlock lastOpenedBlock; 730 HBasicBlock lastOpenedBlock;
704 731
705 // Linked list of active break-handlers. Will be removed in the order
706 // they are added.
707 BreakHandler currentBreakHandler = const NullBreakHandler();
708
709 LibraryElement get currentLibrary() => work.element.getLibrary(); 732 LibraryElement get currentLibrary() => work.element.getLibrary();
710 733
711 SsaBuilder(Compiler compiler, WorkItem work) 734 SsaBuilder(Compiler compiler, WorkItem work)
712 : this.compiler = compiler, 735 : this.compiler = compiler,
713 this.work = work, 736 this.work = work,
714 interceptors = compiler.builder.interceptors, 737 interceptors = compiler.builder.interceptors,
715 methodInterceptionEnabled = true, 738 methodInterceptionEnabled = true,
716 elements = work.resolutionTree, 739 elements = work.resolutionTree,
717 graph = new HGraph(), 740 graph = new HGraph(),
718 stack = new List<HInstruction>(), 741 stack = new List<HInstruction>(),
719 breakTargets = new Map<TargetElement, BreakHandler>() { 742 jumpTargets = new Map<TargetElement, JumpHandler>() {
720 localsHandler = new LocalsHandler(this); 743 localsHandler = new LocalsHandler(this);
721 } 744 }
722 745
723 void disableMethodInterception() { 746 void disableMethodInterception() {
724 assert(methodInterceptionEnabled); 747 assert(methodInterceptionEnabled);
725 methodInterceptionEnabled = false; 748 methodInterceptionEnabled = false;
726 } 749 }
727 750
728 void enableMethodInterception() { 751 void enableMethodInterception() {
729 assert(!methodInterceptionEnabled); 752 assert(!methodInterceptionEnabled);
(...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after
868 FunctionParameters parameters = functionElement.computeParameters(compiler); 891 FunctionParameters parameters = functionElement.computeParameters(compiler);
869 parameters.forEachParameter((Element element) { 892 parameters.forEachParameter((Element element) {
870 if (element.kind == ElementKind.FIELD_PARAMETER) { 893 if (element.kind == ElementKind.FIELD_PARAMETER) {
871 // If the [element] is a field-parameter (such as [:this.x:] then 894 // If the [element] is a field-parameter (such as [:this.x:] then
872 // initialize the field element with its value. 895 // initialize the field element with its value.
873 FieldParameterElement fieldParameterElement = element; 896 FieldParameterElement fieldParameterElement = element;
874 HInstruction parameterValue = localsHandler.readLocal(element); 897 HInstruction parameterValue = localsHandler.readLocal(element);
875 fieldValues[fieldParameterElement.fieldElement] = parameterValue; 898 fieldValues[fieldParameterElement.fieldElement] = parameterValue;
876 } 899 }
877 }); 900 });
878 901
879 final Map<FunctionElement, TreeElements> constructorElements = 902 final Map<FunctionElement, TreeElements> constructorElements =
880 compiler.resolver.constructorElements; 903 compiler.resolver.constructorElements;
881 List<FunctionElement> constructors = new List<FunctionElement>(); 904 List<FunctionElement> constructors = new List<FunctionElement>();
882 905
883 // Analyze the constructor and all referenced constructors and collect 906 // Analyze the constructor and all referenced constructors and collect
884 // initializers and constructor bodies. 907 // initializers and constructor bodies.
885 inlineInitializers(functionElement, constructors, fieldValues); 908 inlineInitializers(functionElement, constructors, fieldValues);
886 909
887 // Call the JavaScript constructor with the fields as argument. 910 // Call the JavaScript constructor with the fields as argument.
888 // TODO(floitsch,karlklose): move this code to ClassElement and share with 911 // TODO(floitsch,karlklose): move this code to ClassElement and share with
(...skipping 133 matching lines...) Expand 10 before | Expand all | Expand 10 after
1022 visitExpressionStatement(ExpressionStatement node) { 1045 visitExpressionStatement(ExpressionStatement node) {
1023 visit(node.expression); 1046 visit(node.expression);
1024 pop(); 1047 pop();
1025 } 1048 }
1026 1049
1027 /** 1050 /**
1028 * Creates a new loop-header block. The previous [current] block 1051 * Creates a new loop-header block. The previous [current] block
1029 * is closed with an [HGoto] and replaced by the newly created block. 1052 * is closed with an [HGoto] and replaced by the newly created block.
1030 * Also notifies the locals handler that we're entering a loop. 1053 * Also notifies the locals handler that we're entering a loop.
1031 */ 1054 */
1032 BreakHandler beginLoopHeader(Node node) { 1055 JumpHandler beginLoopHeader(Node node) {
1033 assert(!isAborted()); 1056 assert(!isAborted());
1034 HBasicBlock previousBlock = close(new HGoto()); 1057 HBasicBlock previousBlock = close(new HGoto());
1035 BreakHandler breakHandler = getBreakHandler(node); 1058
1036 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels()); 1059 JumpHandler jumpHandler = createJumpHandler(node);
1060 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(jumpHandler.labels());
1037 previousBlock.addSuccessor(loopEntry); 1061 previousBlock.addSuccessor(loopEntry);
1038 open(loopEntry); 1062 open(loopEntry);
1039 1063
1040 localsHandler.beginLoopHeader(node, loopEntry); 1064 localsHandler.beginLoopHeader(node, loopEntry);
1041 return breakHandler; 1065 return jumpHandler;
1042 } 1066 }
1043 1067
1044 /** 1068 /**
1045 * Ends the loop: 1069 * Ends the loop:
1046 * - creates a new block and adds it as successor to the [branchBlock]. 1070 * - creates a new block and adds it as successor to the [branchBlock].
1047 * - opens the new block (setting as [current]). 1071 * - opens the new block (setting as [current]).
1048 * - notifies the locals handler that we're exiting a loop. 1072 * - notifies the locals handler that we're exiting a loop.
1049 */ 1073 */
1050 void endLoop(HBasicBlock loopEntry, 1074 void endLoop(HBasicBlock loopEntry,
1051 HBasicBlock branchBlock, 1075 HBasicBlock branchBlock,
1052 BreakHandler breakHandler, 1076 JumpHandler jumpHandler,
1053 LocalsHandler savedLocals) { 1077 LocalsHandler savedLocals) {
1054 HBasicBlock loopExitBlock = addNewBlock(); 1078 HBasicBlock loopExitBlock = addNewBlock();
1055 assert(branchBlock.successors.length == 1); 1079 assert(branchBlock.successors.length == 1);
1056 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 1080 List<LocalsHandler> breakLocals = <LocalsHandler>[];
1057 breakHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 1081 jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
1058 breakInstruction.block.addSuccessor(loopExitBlock); 1082 breakInstruction.block.addSuccessor(loopExitBlock);
1059 breakLocals.add(locals); 1083 breakLocals.add(locals);
1060 }); 1084 });
1061 branchBlock.addSuccessor(loopExitBlock); 1085 branchBlock.addSuccessor(loopExitBlock);
1062 open(loopExitBlock); 1086 open(loopExitBlock);
1063 localsHandler.endLoop(loopEntry); 1087 localsHandler.endLoop(loopEntry);
1064 if (!breakLocals.isEmpty()) { 1088 if (!breakLocals.isEmpty()) {
1065 breakLocals.add(savedLocals); 1089 breakLocals.add(savedLocals);
1066 localsHandler = localsHandler.mergeMultiple(breakLocals, loopExitBlock); 1090 localsHandler = localsHandler.mergeMultiple(breakLocals, loopExitBlock);
1067 } else { 1091 } else {
1068 localsHandler = savedLocals; 1092 localsHandler = savedLocals;
1069 } 1093 }
1070 } 1094 }
1071 1095
1072 // For while loops, initializer and update are null. 1096 // For while loops, initializer and update are null.
1073 visitLoop(Node loop, Node initializer, Expression condition, NodeList updates, 1097 visitLoop(Node loop,
1098 Node initializer,
1099 Expression condition,
1100 NodeList updates,
1074 Node body) { 1101 Node body) {
1075 // Generate: 1102 // Generate:
1076 // <initializer> 1103 // <initializer>
1077 // loop-entry: 1104 // loop-entry:
1078 // if (!<condition>) goto loop-exit; 1105 // if (!<condition>) goto loop-exit;
1079 // <body> 1106 // <body>
1080 // <updates> 1107 // <updates>
1081 // goto loop-entry; 1108 // goto loop-entry;
1082 // loop-exit: 1109 // loop-exit:
1083 if (body === null) { 1110 if (body === null) {
1084 compiler.unimplemented( 1111 compiler.unimplemented(
1085 'SsaBuilder.visitLoop with empty body', 1112 'SsaBuilder.visitLoop with empty body',
1086 node: loop); 1113 node: loop);
1087 } 1114 }
1088 1115
1089 localsHandler.startLoop(loop); 1116 localsHandler.startLoop(loop);
1090 1117
1091 // The initializer. 1118 // The initializer.
1092 if (initializer !== null) { 1119 if (initializer !== null) {
1093 visit(initializer); 1120 visit(initializer);
1094 // We don't care about the value of the initialization. 1121 // We don't care about the value of the initialization.
1095 if (initializer.asExpression() !== null) pop(); 1122 if (initializer.asExpression() !== null) pop();
1096 } 1123 }
1097 assert(!isAborted()); 1124 assert(!isAborted());
1098 1125
1099 BreakHandler breakHandler = beginLoopHeader(loop); 1126 JumpHandler jumpHandler = beginLoopHeader(loop);
1100 HBasicBlock conditionBlock = current; 1127 HBasicBlock conditionBlock = current;
1101 1128
1102 HInstruction conditionInstruction; 1129 HInstruction conditionInstruction;
1103 if (condition != null) { 1130 if (condition != null) {
1104 visit(condition); 1131 visit(condition);
1105 conditionInstruction = popBoolified(); 1132 conditionInstruction = popBoolified();
1106 } else { 1133 } else {
1107 // TODO(ngeoffray): Once our loop recognition does not require a 1134 // TODO(ngeoffray): Once our loop recognition does not require a
1108 // HLoopBranch, we could just generate a HGoto. 1135 // HLoopBranch, we could just generate a HGoto.
1109 conditionInstruction = graph.addConstantBool(true); 1136 conditionInstruction = graph.addConstantBool(true);
1110 } 1137 }
1111 HBasicBlock conditionExitBlock = 1138 HBasicBlock conditionExitBlock =
1112 close(new HLoopBranch(conditionInstruction)); 1139 close(new HLoopBranch(conditionInstruction));
1113 1140
1114 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 1141 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
1115 1142
1116 // The body. 1143 // The body.
1117 HBasicBlock bodyBlock = addNewBlock(); 1144 HBasicBlock beginBodyBlock = addNewBlock();
1118 conditionExitBlock.addSuccessor(bodyBlock); 1145 conditionExitBlock.addSuccessor(beginBodyBlock);
1119 open(bodyBlock); 1146 open(beginBodyBlock);
1120 1147
1121 localsHandler.enterLoopBody(loop); 1148 localsHandler.enterLoopBody(loop);
1149
1122 hackAroundPossiblyAbortingBody(body); 1150 hackAroundPossiblyAbortingBody(body);
1123 bodyBlock = close(new HGoto()); 1151 SubGraph bodyGraph = new SubGraph(beginBodyBlock, current);
1152 HBasicBlock bodyBlock = close(new HGoto());
1124 1153
1125 // Update. 1154 // Update.
1126 // We create an update block, even when we are in a while loop. There the 1155 // We create an update block, even when we are in a while loop. There the
1127 // update block is the jump-target for continue statements. We could avoid 1156 // update block is the jump-target for continue statements. We could avoid
1128 // the creation if there is no continue, but for now we always create it. 1157 // the creation if there is no continue, but for now we always create it.
1129 HBasicBlock updateBlock = addNewBlock(); 1158 HBasicBlock updateBlock = addNewBlock();
1159
1160 List<LocalsHandler> continueLocals = <LocalsHandler>[];
1161 jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {
1162 instruction.block.addSuccessor(updateBlock);
1163 continueLocals.add(locals);
1164 });
1130 bodyBlock.addSuccessor(updateBlock); 1165 bodyBlock.addSuccessor(updateBlock);
1166 continueLocals.add(localsHandler);
1167
1131 open(updateBlock); 1168 open(updateBlock);
1132 1169
1170 localsHandler = localsHandler.mergeMultiple(continueLocals, updateBlock);
1171
1172 HLabeledBlockInformation labelInfo;
1173 List<LabelElement> labels = jumpHandler.labels();
1174 if (!labels.isEmpty()) {
1175 beginBodyBlock.labeledBlockInformation =
1176 new HLabeledBlockInformation(bodyGraph, updateBlock,
1177 jumpHandler.labels(), isContinue: true);
1178 }
1179
1133 localsHandler.enterLoopUpdates(loop); 1180 localsHandler.enterLoopUpdates(loop);
1181
1134 if (updates !== null) { 1182 if (updates !== null) {
1135 for (Expression expression in updates) { 1183 for (Expression expression in updates) {
1136 visit(expression); 1184 visit(expression);
1137 assert(!isAborted()); 1185 assert(!isAborted());
1138 // The result of the update instruction isn't used, and can just 1186 // The result of the update instruction isn't used, and can just
1139 // be dropped. 1187 // be dropped.
1140 HInstruction updateInstruction = pop(); 1188 HInstruction updateInstruction = pop();
1141 } 1189 }
1142 } 1190 }
1143 updateBlock = close(new HGoto()); 1191 updateBlock = close(new HGoto());
1144 // The back-edge completing the cycle. 1192 // The back-edge completing the cycle.
1145 updateBlock.addSuccessor(conditionBlock); 1193 updateBlock.addSuccessor(conditionBlock);
1146 conditionBlock.postProcessLoopHeader(); 1194 conditionBlock.postProcessLoopHeader();
1147 1195
1148 endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals); 1196 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
1149 } 1197 }
1150 1198
1151 visitFor(For node) { 1199 visitFor(For node) {
1152 assert(node.body !== null); 1200 assert(node.body !== null);
1153 visitLoop(node, node.initializer, node.condition, node.update, node.body); 1201 visitLoop(node, node.initializer, node.condition, node.update, node.body);
1154 } 1202 }
1155 1203
1156 visitWhile(While node) { 1204 visitWhile(While node) {
1157 visitLoop(node, null, node.condition, null, node.body); 1205 visitLoop(node, null, node.condition, null, node.body);
1158 } 1206 }
1159 1207
1160 visitDoWhile(DoWhile node) { 1208 visitDoWhile(DoWhile node) {
1161 localsHandler.startLoop(node); 1209 localsHandler.startLoop(node);
1162 BreakHandler breakHandler = beginLoopHeader(node); 1210 JumpHandler jumpHandler = beginLoopHeader(node);
1163 HBasicBlock loopEntryBlock = current; 1211 HBasicBlock loopEntryBlock = current;
1164 1212
1165 localsHandler.enterLoopBody(node); 1213 localsHandler.enterLoopBody(node);
1166 hackAroundPossiblyAbortingBody(node.body); 1214 hackAroundPossiblyAbortingBody(node.body);
1167 1215
1168 // If there are no continues we could avoid the creation of the condition 1216 // If there are no continues we could avoid the creation of the condition
1169 // block. This could also lead to a block having multiple entries and exits. 1217 // block. This could also lead to a block having multiple entries and exits.
1170 HBasicBlock bodyExitBlock = close(new HGoto()); 1218 HBasicBlock bodyExitBlock = close(new HGoto());
1171 HBasicBlock conditionBlock = addNewBlock(); 1219 HBasicBlock conditionBlock = addNewBlock();
1172 bodyExitBlock.addSuccessor(conditionBlock); 1220 bodyExitBlock.addSuccessor(conditionBlock);
1221 jumpHandler.forEachContinue((x,y) {
1222 // TODO(lrn): Handle continue in do-while loops.
1223 compiler.cancel("do-while with continue", node: node);
1224 });
1173 open(conditionBlock); 1225 open(conditionBlock);
1174 visit(node.condition); 1226 visit(node.condition);
1175 assert(!isAborted()); 1227 assert(!isAborted());
1176 conditionBlock = close(new HLoopBranch(popBoolified(), 1228 conditionBlock = close(new HLoopBranch(popBoolified(),
1177 HLoopBranch.DO_WHILE_LOOP)); 1229 HLoopBranch.DO_WHILE_LOOP));
1178 1230
1179 conditionBlock.addSuccessor(loopEntryBlock); // The back-edge. 1231 conditionBlock.addSuccessor(loopEntryBlock); // The back-edge.
1180 loopEntryBlock.postProcessLoopHeader(); 1232 loopEntryBlock.postProcessLoopHeader();
1181 1233
1182 endLoop(loopEntryBlock, conditionBlock, breakHandler, localsHandler); 1234 endLoop(loopEntryBlock, conditionBlock, jumpHandler, localsHandler);
1235 jumpHandler.close();
1183 } 1236 }
1184 1237
1185 visitFunctionExpression(FunctionExpression node) { 1238 visitFunctionExpression(FunctionExpression node) {
1186 ClosureData nestedClosureData = closureDataCache[node]; 1239 ClosureData nestedClosureData = closureDataCache[node];
1187 assert(nestedClosureData !== null); 1240 assert(nestedClosureData !== null);
1188 assert(nestedClosureData.closureClassElement !== null); 1241 assert(nestedClosureData.closureClassElement !== null);
1189 ClassElement closureClassElement = 1242 ClassElement closureClassElement =
1190 nestedClosureData.closureClassElement; 1243 nestedClosureData.closureClassElement;
1191 FunctionElement callElement = nestedClosureData.callElement; 1244 FunctionElement callElement = nestedClosureData.callElement;
1192 compiler.enqueue(new WorkItem.toCodegen(callElement, elements)); 1245 compiler.enqueue(new WorkItem.toCodegen(callElement, elements));
(...skipping 984 matching lines...) Expand 10 before | Expand all | Expand 10 after
2177 2230
2178 visitModifiers(Modifiers node) { 2231 visitModifiers(Modifiers node) {
2179 compiler.unimplemented('SsaBuilder.visitModifiers', node: node); 2232 compiler.unimplemented('SsaBuilder.visitModifiers', node: node);
2180 } 2233 }
2181 2234
2182 visitBreakStatement(BreakStatement node) { 2235 visitBreakStatement(BreakStatement node) {
2183 work.allowSpeculativeOptimization = false; 2236 work.allowSpeculativeOptimization = false;
2184 assert(!isAborted()); 2237 assert(!isAborted());
2185 TargetElement target = elements[node]; 2238 TargetElement target = elements[node];
2186 assert(target !== null); 2239 assert(target !== null);
2187 BreakHandler handler = breakTargets[target]; 2240 JumpHandler handler = jumpTargets[target];
2188 assert(handler !== null); 2241 assert(handler !== null);
2189 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
2190 HBreak breakInstruction;
2191 if (node.target === null) { 2242 if (node.target === null) {
2192 breakInstruction = new HBreak(target); 2243 handler.generateBreak();
2193 } else { 2244 } else {
2194 LabelElement label = elements[node.target]; 2245 LabelElement label = elements[node.target];
2195 breakInstruction = new HBreak.toLabel(label); 2246 handler.generateBreak(label);
2196 } 2247 }
2197 close(breakInstruction);
2198 handler.addBreak(breakInstruction, savedLocals);
2199 } 2248 }
2200 2249
2201 visitContinueStatement(ContinueStatement node) { 2250 visitContinueStatement(ContinueStatement node) {
2202 // TODO(lrn): Replace this with a real implementation of continue. 2251 work.allowSpeculativeOptimization = false;
2203 compiler.reportWarning(node, 'continue not implemented'); 2252 TargetElement target = elements[node];
2204 generateUnimplemented('continue not implemented'); 2253 assert(target !== null);
2254 JumpHandler handler = jumpTargets[target];
2255 assert(handler !== null);
2256 if (node.target === null) {
2257 handler.generateContinue();
2258 } else {
2259 LabelElement label = elements[node.target];
2260 handler.generateContinue(label);
2261 }
2205 } 2262 }
2206 2263
2207 BreakHandler getBreakHandler(Node node) { 2264 /**
2265 * Creates a [JumpHandler] for a statement. The node must be a jump
2266 * target. If there are no breaks or continues targeting the statement,
2267 * a special "null handler" is returned.
2268 */
2269 JumpHandler createJumpHandler(Statement node) {
2208 TargetElement element = elements[node]; 2270 TargetElement element = elements[node];
2209 if (element === null) return const NullBreakHandler(); 2271 if (element === null || element.statement !== node) {
2210 return new BreakHandler(this, element); 2272 // No breaks or continues to this node.
2273 return const NullJumpHandler();
2274 }
2275 return new JumpHandler(this, element);
2211 } 2276 }
2212 2277
2213 visitForInStatement(ForInStatement node) { 2278 visitForInStatement(ForInStatement node) {
2214 // Generate a structure equivalent to: 2279 // Generate a structure equivalent to:
2215 // Iterator<E> $iter = <iterable>.iterator() 2280 // Iterator<E> $iter = <iterable>.iterator()
2216 // while ($iter.hasNext()) { 2281 // while ($iter.hasNext()) {
2217 // E <declaredIdentifier> = $iter.next(); 2282 // E <declaredIdentifier> = $iter.next();
2218 // <body> 2283 // <body>
2219 // } 2284 // }
2220 localsHandler.startLoop(node); 2285 localsHandler.startLoop(node);
2221 2286
2222 SourceString iteratorName = const SourceString("iterator"); 2287 SourceString iteratorName = const SourceString("iterator");
2223 2288
2224 Selector selector = Selector.INVOCATION_0; 2289 Selector selector = Selector.INVOCATION_0;
2225 Element interceptor = interceptors.getStaticInterceptor(iteratorName, 0); 2290 Element interceptor = interceptors.getStaticInterceptor(iteratorName, 0);
2226 assert(interceptor != null); 2291 assert(interceptor != null);
2227 HStatic target = new HStatic(interceptor); 2292 HStatic target = new HStatic(interceptor);
2228 add(target); 2293 add(target);
2229 visit(node.expression); 2294 visit(node.expression);
2230 List<HInstruction> inputs = <HInstruction>[target, pop()]; 2295 List<HInstruction> inputs = <HInstruction>[target, pop()];
2231 HInstruction iterator = new HInvokeInterceptor( 2296 HInstruction iterator = new HInvokeInterceptor(
2232 selector, iteratorName, false, inputs); 2297 selector, iteratorName, false, inputs);
2233 add(iterator); 2298 add(iterator);
2234 2299
2235 BreakHandler breakHandler = beginLoopHeader(node); 2300 JumpHandler jumpHandler = beginLoopHeader(node);
2236 HBasicBlock conditionBlock = current; 2301 HBasicBlock conditionBlock = current;
2237 2302
2238 // The condition. 2303 // The condition.
2239 push(new HInvokeDynamicMethod( 2304 push(new HInvokeDynamicMethod(
2240 selector, const SourceString('hasNext'), [iterator])); 2305 selector, const SourceString('hasNext'), [iterator]));
2241 HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified())); 2306 HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified()));
2242 2307
2243 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 2308 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
2244 2309
2245 // The body. 2310 // The body.
(...skipping 13 matching lines...) Expand all
2259 } else { 2324 } else {
2260 assert(node.declaredIdentifier.asVariableDefinitions() !== null); 2325 assert(node.declaredIdentifier.asVariableDefinitions() !== null);
2261 VariableDefinitions variableDefinitions = node.declaredIdentifier; 2326 VariableDefinitions variableDefinitions = node.declaredIdentifier;
2262 variable = elements[variableDefinitions.definitions.nodes.head]; 2327 variable = elements[variableDefinitions.definitions.nodes.head];
2263 } 2328 }
2264 localsHandler.updateLocal(variable, pop()); 2329 localsHandler.updateLocal(variable, pop());
2265 2330
2266 hackAroundPossiblyAbortingBody(node.body); 2331 hackAroundPossiblyAbortingBody(node.body);
2267 bodyBlock = close(new HGoto()); 2332 bodyBlock = close(new HGoto());
2268 2333
2334 jumpHandler.forEachContinue((x,y) {
2335 // TODO(lrn): Handle continue in for-in.
2336 // TODO(lrn): Or, preferably, use an abstraction of visitLoop for for-in.
2337 compiler.cancel('for-in with continue', node: node);
2338 });
2339
2269 // Update. 2340 // Update.
2270 // We create an update block, even if we are in a for-in loop. The 2341 // We create an update block, even if we are in a for-in loop. The
2271 // update block is the jump-target for continue statements. We could avoid 2342 // update block is the jump-target for continue statements. We could avoid
2272 // the creation if there is no continue, but for now we always create it. 2343 // the creation if there is no continue, but for now we always create it.
2273 HBasicBlock updateBlock = addNewBlock(); 2344 HBasicBlock updateBlock = addNewBlock();
2345
2274 bodyBlock.addSuccessor(updateBlock); 2346 bodyBlock.addSuccessor(updateBlock);
2275 open(updateBlock); 2347 open(updateBlock);
2276 updateBlock = close(new HGoto()); 2348 updateBlock = close(new HGoto());
2277 // The back-edge completing the cycle. 2349 // The back-edge completing the cycle.
2278 updateBlock.addSuccessor(conditionBlock); 2350 updateBlock.addSuccessor(conditionBlock);
2279 conditionBlock.postProcessLoopHeader(); 2351 conditionBlock.postProcessLoopHeader();
2280 2352
2281 endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals); 2353 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
2282 breakHandler.close(); 2354 jumpHandler.close();
2283 } 2355 }
2284 2356
2285 visitLabeledStatement(LabeledStatement node) { 2357 visitLabeledStatement(LabeledStatement node) {
2286 Statement body = node.getBody(); 2358 Statement body = node.getBody();
2287 if (body is Loop || body is SwitchStatement) { 2359 if (body is Loop || body is SwitchStatement) {
2288 // Loops and switches handle their own labels. 2360 // Loops and switches handle their own labels.
2289 visit(body); 2361 visit(body);
2290 return; 2362 return;
2291 } 2363 }
2292 // Non-loop statements can only be break targets, not continue targets. 2364 // Non-loop statements can only be break targets, not continue targets.
2293 TargetElement targetElement = elements[body]; 2365 TargetElement targetElement = elements[body];
2294 if (targetElement === null || targetElement.statement !== body) { 2366 if (targetElement === null || targetElement.statement !== body) {
2295 // Labeled statements with no element on the body have no breaks. 2367 // Labeled statements with no element on the body have no breaks.
2296 // A different target statement only happens if the body is itself 2368 // A different target statement only happens if the body is itself
2297 // a break or continue for a different target. In that case, this 2369 // a break or continue for a different target. In that case, this
2298 // label is also always unused. 2370 // label is also always unused.
2299 visit(body); 2371 visit(body);
2300 return; 2372 return;
2301 } 2373 }
2302 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler); 2374 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler);
2303 assert(targetElement.isBreakTarget); 2375 assert(targetElement.isBreakTarget);
2304 BreakHandler handler = new BreakHandler(this, targetElement); 2376 JumpHandler handler = new JumpHandler(this, targetElement);
2305 // Introduce a new basic block. 2377 // Introduce a new basic block.
2306 HBasicBlock entryBlock = graph.addNewBlock(); 2378 HBasicBlock entryBlock = graph.addNewBlock();
2307 goto(current, entryBlock); 2379 goto(current, entryBlock);
2308 open(entryBlock); 2380 open(entryBlock);
2309 hackAroundPossiblyAbortingBody(body); 2381 hackAroundPossiblyAbortingBody(body);
2310 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock); 2382 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock);
2311 2383
2312 HBasicBlock joinBlock = graph.addNewBlock(); 2384 HBasicBlock joinBlock = graph.addNewBlock();
2313 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 2385 List<LocalsHandler> breakLocals = <LocalsHandler>[];
2314 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 2386 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
2364 HBasicBlock startBlock = graph.addNewBlock(); 2436 HBasicBlock startBlock = graph.addNewBlock();
2365 goto(current, startBlock); 2437 goto(current, startBlock);
2366 open(startBlock); 2438 open(startBlock);
2367 visit(node.expression); 2439 visit(node.expression);
2368 HInstruction expression = pop(); 2440 HInstruction expression = pop();
2369 if (node.cases.isEmpty()) { 2441 if (node.cases.isEmpty()) {
2370 return; 2442 return;
2371 } 2443 }
2372 Link<Node> cases = node.cases.nodes; 2444 Link<Node> cases = node.cases.nodes;
2373 2445
2374 BreakHandler breakHandler = getBreakHandler(node); 2446 JumpHandler jumpHandler = createJumpHandler(node);
2375 2447
2376 buildSwitchCases(cases, expression); 2448 buildSwitchCases(cases, expression);
2377 2449
2378 HBasicBlock lastBlock = lastOpenedBlock; 2450 HBasicBlock lastBlock = lastOpenedBlock;
2379 2451
2380 // Create merge block for break targets. 2452 // Create merge block for break targets.
2381 HBasicBlock joinBlock = new HBasicBlock(); 2453 HBasicBlock joinBlock = new HBasicBlock();
2382 List<LocalsHandler> caseLocals = <LocalsHandler>[]; 2454 List<LocalsHandler> caseLocals = <LocalsHandler>[];
2383 breakHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 2455 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
2384 instruction.block.addSuccessor(joinBlock); 2456 instruction.block.addSuccessor(joinBlock);
2385 caseLocals.add(locals); 2457 caseLocals.add(locals);
2386 }); 2458 });
2387 if (!isAborted()) { 2459 if (!isAborted()) {
2388 // The current flow is only aborted if the switch has a default that 2460 // The current flow is only aborted if the switch has a default that
2389 // aborts (all previous cases must abort, and if there is no default, 2461 // aborts (all previous cases must abort, and if there is no default,
2390 // it's possible to miss all the cases). 2462 // it's possible to miss all the cases).
2391 caseLocals.add(localsHandler); 2463 caseLocals.add(localsHandler);
2392 goto(current, joinBlock); 2464 goto(current, joinBlock);
2393 } 2465 }
2394 if (caseLocals.length != 0) { 2466 if (caseLocals.length != 0) {
2395 graph.addBlock(joinBlock); 2467 graph.addBlock(joinBlock);
2396 open(joinBlock); 2468 open(joinBlock);
2397 if (caseLocals.length == 1) { 2469 if (caseLocals.length == 1) {
2398 localsHandler = caseLocals[0]; 2470 localsHandler = caseLocals[0];
2399 } else { 2471 } else {
2400 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock); 2472 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
2401 } 2473 }
2402 } else { 2474 } else {
2403 // The joinblock is not used. 2475 // The joinblock is not used.
2404 joinBlock = null; 2476 joinBlock = null;
2405 } 2477 }
2406 startBlock.labeledBlockInformation = new HLabeledBlockInformation.implicit( 2478 startBlock.labeledBlockInformation = new HLabeledBlockInformation.implicit(
2407 new SubGraph(startBlock, lastBlock), 2479 new SubGraph(startBlock, lastBlock),
2408 joinBlock, 2480 joinBlock,
2409 elements[node]); 2481 elements[node]);
2482 jumpHandler.close();
2410 } 2483 }
2411 2484
2412 2485
2413 // Recursively build an if/else structure to match the cases. 2486 // Recursively build an if/else structure to match the cases.
2414 buildSwitchCases(Link<Node> cases, HInstruction expression) { 2487 buildSwitchCases(Link<Node> cases, HInstruction expression) {
2415 SwitchCase node = cases.head; 2488 SwitchCase node = cases.head;
2416 2489
2417 // Called for the statements on all but the last case block. 2490 // Called for the statements on all but the last case block.
2418 // Ensures that a user expecting a fallthrough gets an error. 2491 // Ensures that a user expecting a fallthrough gets an error.
2419 void visitStatementsAndAbort() { 2492 void visitStatementsAndAbort() {
(...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after
2628 buildBody() { 2701 buildBody() {
2629 // TODO(lrn): Make sure to take continue into account. 2702 // TODO(lrn): Make sure to take continue into account.
2630 visit(body); 2703 visit(body);
2631 if (isAborted()) { 2704 if (isAborted()) {
2632 compiler.reportWarning(body, "aborting loop body"); 2705 compiler.reportWarning(body, "aborting loop body");
2633 } 2706 }
2634 } 2707 }
2635 handleIf(buildBody, null); 2708 handleIf(buildBody, null);
2636 } 2709 }
2637 } 2710 }
OLDNEW
« no previous file with comments | « frog/leg/resolver.dart ('k') | frog/leg/ssa/codegen.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698