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

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: 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
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 instruction.
ngeoffray 2012/03/19 11:42:06 break/continue
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Done.
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 // Inert break handler used to avoid null checks when a loop isn't
ngeoffray 2012/03/19 11:42:06 Inert -> Insert
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Done.
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.
ngeoffray 2012/03/19 11:42:06 Please update description now that you support swi
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Done.
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.
ngeoffray 2012/03/19 11:42:06 Ditto
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Done.
639 class BreakHandlerImpl implements BreakHandler { 644 class JumpHandlerImpl implements JumpHandler {
640 final BreakHandler previous; 645 final JumpHandler previous;
641 final SsaBuilder builder; 646 final SsaBuilder builder;
642 final TargetElement target; 647 final TargetElement target;
643 final List<BreakHandlerEntry> breaks; 648 final List<JumpHandlerEntry> jumps;
644 BreakHandlerImpl(SsaBuilder builder, this.target) 649
650 JumpHandlerImpl(SsaBuilder builder, this.target)
645 : this.builder = builder, 651 : this.builder = builder,
646 previous = builder.currentBreakHandler, 652 previous = builder.currentJumpHandler,
647 breaks = <BreakHandlerEntry>[] { 653 jumps = <JumpHandlerEntry>[] {
648 builder.currentBreakHandler = this; 654 builder.currentJumpHandler = this;
649 assert(builder.breakTargets[target] === null); 655 assert(builder.jumpTargets[target] === null);
650 builder.breakTargets[target] = this; 656 builder.jumpTargets[target] = this;
651 } 657 }
652 658
653 void addBreak(HBreak breakInstruction, LocalsHandler locals) { 659 void generateBreak([LabelElement label]) {
654 breaks.add(new BreakHandlerEntry(breakInstruction, locals)); 660 HInstruction breakInstruction;
661 if (label === null) {
662 breakInstruction = new HBreak(target);
663 } else {
664 breakInstruction = new HBreak.toLabel(label);
665 }
666 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
667 builder.close(breakInstruction);
668 jumps.add(new JumpHandlerEntry(breakInstruction, locals));
669 }
670
671 void generateContinue([LabelElement label]) {
672 HInstruction continueInstruction;
673 if (label === null) {
674 continueInstruction = new HContinue(target);
675 } else {
676 continueInstruction = new HContinue.toLabel(label);
677 }
678 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
679 builder.close(continueInstruction);
680 jumps.add(new JumpHandlerEntry(continueInstruction, locals));
655 } 681 }
656 682
657 void forEachBreak(Function action) { 683 void forEachBreak(Function action) {
658 for (BreakHandlerEntry entry in breaks) { 684 for (JumpHandlerEntry entry in jumps) {
659 action(entry.breakInstruction, entry.locals); 685 if (entry.isBreak()) action(entry.jumpInstruction, entry.locals);
686 }
687 }
688
689 void forEachContinue(Function action) {
690 for (JumpHandlerEntry entry in jumps) {
691 if (entry.isContinue()) action(entry.jumpInstruction, entry.locals);
660 } 692 }
661 } 693 }
662 694
663 void close() { 695 void close() {
664 assert(builder.currentBreakHandler === this); 696 assert(builder.currentJumpHandler === this);
665 // The mapping from TargetElement to BreakHandler is no longer needed. 697 // The mapping from StatementElement to JumpHandler is no longer needed.
666 builder.breakTargets.remove(target); 698 builder.jumpTargets.remove(target);
667 builder.currentBreakHandler = previous; 699 builder.currentJumpHandler = previous;
668 } 700 }
669 701
670 List<LabelElement> labels() { 702 List<LabelElement> labels() {
671 List<LabelElement> result = null; 703 List<LabelElement> result = null;
672 for (LabelElement element in target.labels) { 704 for (LabelElement element in target.labels) {
673 if (element.isBreakTarget) { 705 if (result === null) result = <LabelElement>[];
674 if (result === null) result = <LabelElement>[]; 706 result.add(element);
675 result.add(element);
676 }
677 } 707 }
678 return (result === null) ? const <LabelElement>[] : result; 708 return (result === null) ? const <LabelElement>[] : result;
679 } 709 }
680 } 710 }
681 711
682 class SsaBuilder implements Visitor { 712 class SsaBuilder implements Visitor {
683 final Compiler compiler; 713 final Compiler compiler;
684 TreeElements elements; 714 TreeElements elements;
685 final Interceptors interceptors; 715 final Interceptors interceptors;
686 final WorkItem work; 716 final WorkItem work;
687 bool methodInterceptionEnabled; 717 bool methodInterceptionEnabled;
688 HGraph graph; 718 HGraph graph;
689 LocalsHandler localsHandler; 719 LocalsHandler localsHandler;
690 HInstruction rethrowableException; 720 HInstruction rethrowableException;
691 721
692 Map<TargetElement, BreakHandler> breakTargets; 722 Map<TargetElement, JumpHandler> jumpTargets;
693 723
694 // We build the Ssa graph by simulating a stack machine. 724 // We build the Ssa graph by simulating a stack machine.
695 List<HInstruction> stack; 725 List<HInstruction> stack;
696 726
697 // The current block to add instructions to. Might be null, if we are 727 // The current block to add instructions to. Might be null, if we are
698 // visiting dead code. 728 // visiting dead code.
699 HBasicBlock current; 729 HBasicBlock current;
700 // The most recently opened block. Has the same value as [current] while 730 // 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 731 // the block is open, but unlike [current], it isn't cleared when the current
702 // block is closed. 732 // block is closed.
703 HBasicBlock lastOpenedBlock; 733 HBasicBlock lastOpenedBlock;
704 734
705 // Linked list of active break-handlers. Will be removed in the order 735 // Linked list of active break-handlers. Will be removed in the order
706 // they are added. 736 // they are added.
707 BreakHandler currentBreakHandler = const NullBreakHandler(); 737 JumpHandler currentJumpHandler = const NullJumpHandler();
738 // The break handler to use for an upcoming loop statement (temporarily set
ngeoffray 2012/03/19 11:42:06 break -> jump. On the other hand, I think you'll g
Lasse Reichstein Nielsen 2012/03/19 12:13:58 True, this one can go away too (just as the next o
739 // if a labeled statement is labeling a loop).
740 JumpHandler loopJumpHandler = null;
708 741
709 LibraryElement get currentLibrary() => work.element.getLibrary(); 742 LibraryElement get currentLibrary() => work.element.getLibrary();
710 743
711 SsaBuilder(Compiler compiler, WorkItem work) 744 SsaBuilder(Compiler compiler, WorkItem work)
712 : this.compiler = compiler, 745 : this.compiler = compiler,
713 this.work = work, 746 this.work = work,
714 interceptors = compiler.builder.interceptors, 747 interceptors = compiler.builder.interceptors,
715 methodInterceptionEnabled = true, 748 methodInterceptionEnabled = true,
716 elements = work.resolutionTree, 749 elements = work.resolutionTree,
717 graph = new HGraph(), 750 graph = new HGraph(),
718 stack = new List<HInstruction>(), 751 stack = new List<HInstruction>(),
719 breakTargets = new Map<TargetElement, BreakHandler>() { 752 jumpTargets = new Map<TargetElement, JumpHandler>() {
720 localsHandler = new LocalsHandler(this); 753 localsHandler = new LocalsHandler(this);
721 } 754 }
722 755
723 void disableMethodInterception() { 756 void disableMethodInterception() {
724 assert(methodInterceptionEnabled); 757 assert(methodInterceptionEnabled);
725 methodInterceptionEnabled = false; 758 methodInterceptionEnabled = false;
726 } 759 }
727 760
728 void enableMethodInterception() { 761 void enableMethodInterception() {
729 assert(!methodInterceptionEnabled); 762 assert(!methodInterceptionEnabled);
(...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after
868 FunctionParameters parameters = functionElement.computeParameters(compiler); 901 FunctionParameters parameters = functionElement.computeParameters(compiler);
869 parameters.forEachParameter((Element element) { 902 parameters.forEachParameter((Element element) {
870 if (element.kind == ElementKind.FIELD_PARAMETER) { 903 if (element.kind == ElementKind.FIELD_PARAMETER) {
871 // If the [element] is a field-parameter (such as [:this.x:] then 904 // If the [element] is a field-parameter (such as [:this.x:] then
872 // initialize the field element with its value. 905 // initialize the field element with its value.
873 FieldParameterElement fieldParameterElement = element; 906 FieldParameterElement fieldParameterElement = element;
874 HInstruction parameterValue = localsHandler.readLocal(element); 907 HInstruction parameterValue = localsHandler.readLocal(element);
875 fieldValues[fieldParameterElement.fieldElement] = parameterValue; 908 fieldValues[fieldParameterElement.fieldElement] = parameterValue;
876 } 909 }
877 }); 910 });
878 911
879 final Map<FunctionElement, TreeElements> constructorElements = 912 final Map<FunctionElement, TreeElements> constructorElements =
880 compiler.resolver.constructorElements; 913 compiler.resolver.constructorElements;
881 List<FunctionElement> constructors = new List<FunctionElement>(); 914 List<FunctionElement> constructors = new List<FunctionElement>();
882 915
883 // Analyze the constructor and all referenced constructors and collect 916 // Analyze the constructor and all referenced constructors and collect
884 // initializers and constructor bodies. 917 // initializers and constructor bodies.
885 inlineInitializers(functionElement, constructors, fieldValues); 918 inlineInitializers(functionElement, constructors, fieldValues);
886 919
887 // Call the JavaScript constructor with the fields as argument. 920 // Call the JavaScript constructor with the fields as argument.
888 // TODO(floitsch,karlklose): move this code to ClassElement and share with 921 // 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) { 1055 visitExpressionStatement(ExpressionStatement node) {
1023 visit(node.expression); 1056 visit(node.expression);
1024 pop(); 1057 pop();
1025 } 1058 }
1026 1059
1027 /** 1060 /**
1028 * Creates a new loop-header block. The previous [current] block 1061 * Creates a new loop-header block. The previous [current] block
1029 * 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.
1030 * Also notifies the locals handler that we're entering a loop. 1063 * Also notifies the locals handler that we're entering a loop.
1031 */ 1064 */
1032 BreakHandler beginLoopHeader(Node node) { 1065 JumpHandler beginLoopHeader(Node node) {
1033 assert(!isAborted()); 1066 assert(!isAborted());
1034 HBasicBlock previousBlock = close(new HGoto()); 1067 HBasicBlock previousBlock = close(new HGoto());
1035 BreakHandler breakHandler = getBreakHandler(node); 1068
1036 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels()); 1069 JumpHandler jumpHandler = getLoopJumpHandler(node);
1070 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(jumpHandler.labels());
1037 previousBlock.addSuccessor(loopEntry); 1071 previousBlock.addSuccessor(loopEntry);
1038 open(loopEntry); 1072 open(loopEntry);
1039 1073
1040 localsHandler.beginLoopHeader(node, loopEntry); 1074 localsHandler.beginLoopHeader(node, loopEntry);
1041 return breakHandler; 1075 return jumpHandler;
1042 } 1076 }
1043 1077
1044 /** 1078 /**
1045 * Ends the loop: 1079 * Ends the loop:
1046 * - creates a new block and adds it as successor to the [branchBlock]. 1080 * - creates a new block and adds it as successor to the [branchBlock].
1047 * - opens the new block (setting as [current]). 1081 * - opens the new block (setting as [current]).
1048 * - notifies the locals handler that we're exiting a loop. 1082 * - notifies the locals handler that we're exiting a loop.
1049 */ 1083 */
1050 void endLoop(HBasicBlock loopEntry, 1084 void endLoop(HBasicBlock loopEntry,
1051 HBasicBlock branchBlock, 1085 HBasicBlock branchBlock,
1052 BreakHandler breakHandler, 1086 JumpHandler jumpHandler,
1053 LocalsHandler savedLocals) { 1087 LocalsHandler savedLocals) {
1054 HBasicBlock loopExitBlock = addNewBlock(); 1088 HBasicBlock loopExitBlock = addNewBlock();
1055 assert(branchBlock.successors.length == 1); 1089 assert(branchBlock.successors.length == 1);
1056 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 1090 List<LocalsHandler> breakLocals = <LocalsHandler>[];
1057 breakHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 1091 jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
1058 breakInstruction.block.addSuccessor(loopExitBlock); 1092 breakInstruction.block.addSuccessor(loopExitBlock);
1059 breakLocals.add(locals); 1093 breakLocals.add(locals);
1060 }); 1094 });
1061 branchBlock.addSuccessor(loopExitBlock); 1095 branchBlock.addSuccessor(loopExitBlock);
1062 open(loopExitBlock); 1096 open(loopExitBlock);
1063 localsHandler.endLoop(loopEntry); 1097 localsHandler.endLoop(loopEntry);
1064 if (!breakLocals.isEmpty()) { 1098 if (!breakLocals.isEmpty()) {
1065 breakLocals.add(savedLocals); 1099 breakLocals.add(savedLocals);
1066 localsHandler = localsHandler.mergeMultiple(breakLocals, loopExitBlock); 1100 localsHandler = localsHandler.mergeMultiple(breakLocals, loopExitBlock);
1067 } else { 1101 } else {
1068 localsHandler = savedLocals; 1102 localsHandler = savedLocals;
1069 } 1103 }
1070 } 1104 }
1071 1105
1072 // For while loops, initializer and update are null. 1106 // For while loops, initializer and update are null.
1073 visitLoop(Node loop, Node initializer, Expression condition, NodeList updates, 1107 visitLoop(Node loop,
1108 Node initializer,
1109 Expression condition,
1110 NodeList updates,
1074 Node body) { 1111 Node body) {
1075 // Generate: 1112 // Generate:
1076 // <initializer> 1113 // <initializer>
1077 // loop-entry: 1114 // loop-entry:
1078 // if (!<condition>) goto loop-exit; 1115 // if (!<condition>) goto loop-exit;
1079 // <body> 1116 // <body>
1080 // <updates> 1117 // <updates>
1081 // goto loop-entry; 1118 // goto loop-entry;
1082 // loop-exit: 1119 // loop-exit:
1083 if (body === null) { 1120 if (body === null) {
1084 compiler.unimplemented( 1121 compiler.unimplemented(
1085 'SsaBuilder.visitLoop with empty body', 1122 'SsaBuilder.visitLoop with empty body',
1086 node: loop); 1123 node: loop);
1087 } 1124 }
1088 1125
1089 localsHandler.startLoop(loop); 1126 localsHandler.startLoop(loop);
1090 1127
1091 // The initializer. 1128 // The initializer.
1092 if (initializer !== null) { 1129 if (initializer !== null) {
1093 visit(initializer); 1130 visit(initializer);
1094 // We don't care about the value of the initialization. 1131 // We don't care about the value of the initialization.
1095 if (initializer.asExpression() !== null) pop(); 1132 if (initializer.asExpression() !== null) pop();
1096 } 1133 }
1097 assert(!isAborted()); 1134 assert(!isAborted());
1098 1135
1099 BreakHandler breakHandler = beginLoopHeader(loop); 1136 JumpHandler jumpHandler = beginLoopHeader(loop);
1100 HBasicBlock conditionBlock = current; 1137 HBasicBlock conditionBlock = current;
1101 1138
1102 HInstruction conditionInstruction; 1139 HInstruction conditionInstruction;
1103 if (condition != null) { 1140 if (condition != null) {
1104 visit(condition); 1141 visit(condition);
1105 conditionInstruction = popBoolified(); 1142 conditionInstruction = popBoolified();
1106 } else { 1143 } else {
1107 // TODO(ngeoffray): Once our loop recognition does not require a 1144 // TODO(ngeoffray): Once our loop recognition does not require a
1108 // HLoopBranch, we could just generate a HGoto. 1145 // HLoopBranch, we could just generate a HGoto.
1109 conditionInstruction = graph.addConstantBool(true); 1146 conditionInstruction = graph.addConstantBool(true);
1110 } 1147 }
1111 HBasicBlock conditionExitBlock = 1148 HBasicBlock conditionExitBlock =
1112 close(new HLoopBranch(conditionInstruction)); 1149 close(new HLoopBranch(conditionInstruction));
1113 1150
1114 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 1151 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
1115 1152
1116 // The body. 1153 // The body.
1117 HBasicBlock bodyBlock = addNewBlock(); 1154 HBasicBlock beginBodyBlock = addNewBlock();
1118 conditionExitBlock.addSuccessor(bodyBlock); 1155 conditionExitBlock.addSuccessor(beginBodyBlock);
1119 open(bodyBlock); 1156 open(beginBodyBlock);
1120 1157
1121 localsHandler.enterLoopBody(loop); 1158 localsHandler.enterLoopBody(loop);
1159
1122 hackAroundPossiblyAbortingBody(body); 1160 hackAroundPossiblyAbortingBody(body);
1123 bodyBlock = close(new HGoto()); 1161 SubGraph bodyGraph = new SubGraph(beginBodyBlock, current);
1162 HBasicBlock bodyBlock = close(new HGoto());
1124 1163
1125 // Update. 1164 // Update.
1126 // 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
1127 // 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
1128 // 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.
1129 HBasicBlock updateBlock = addNewBlock(); 1168 HBasicBlock updateBlock = addNewBlock();
1169
1170 List<LocalsHandler> continueLocals = <LocalsHandler>[];
ngeoffray 2012/03/19 11:42:06 Please explain why this isn't done in endLoop.
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Because endLoop is also used by DoWhile, which isn
1171 jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {
1172 instruction.block.addSuccessor(updateBlock);
1173 continueLocals.add(locals);
1174 });
1130 bodyBlock.addSuccessor(updateBlock); 1175 bodyBlock.addSuccessor(updateBlock);
1176 continueLocals.add(localsHandler);
1177
1131 open(updateBlock); 1178 open(updateBlock);
1132 1179
1180 localsHandler = localsHandler.mergeMultiple(continueLocals, updateBlock);
1181
1182 HLabeledBlockInformation labelInfo;
1183 List<LabelElement> labels = jumpHandler.labels();
1184 if (!labels.isEmpty()) {
1185 beginBodyBlock.labeledBlockInformation =
1186 new HLabeledBlockInformation(bodyGraph, updateBlock,
1187 jumpHandler.labels(), isContinue: true);
1188 }
1189
1133 localsHandler.enterLoopUpdates(loop); 1190 localsHandler.enterLoopUpdates(loop);
1191
1134 if (updates !== null) { 1192 if (updates !== null) {
1135 for (Expression expression in updates) { 1193 for (Expression expression in updates) {
1136 visit(expression); 1194 visit(expression);
1137 assert(!isAborted()); 1195 assert(!isAborted());
1138 // The result of the update instruction isn't used, and can just 1196 // The result of the update instruction isn't used, and can just
1139 // be dropped. 1197 // be dropped.
1140 HInstruction updateInstruction = pop(); 1198 HInstruction updateInstruction = pop();
1141 } 1199 }
1142 } 1200 }
1143 updateBlock = close(new HGoto()); 1201 updateBlock = close(new HGoto());
1144 // The back-edge completing the cycle. 1202 // The back-edge completing the cycle.
1145 updateBlock.addSuccessor(conditionBlock); 1203 updateBlock.addSuccessor(conditionBlock);
1146 conditionBlock.postProcessLoopHeader(); 1204 conditionBlock.postProcessLoopHeader();
1147 1205
1148 endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals); 1206 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
1149 } 1207 }
1150 1208
1151 visitFor(For node) { 1209 visitFor(For node) {
1152 assert(node.body !== null); 1210 assert(node.body !== null);
1153 visitLoop(node, node.initializer, node.condition, node.update, node.body); 1211 visitLoop(node, node.initializer, node.condition, node.update, node.body);
1154 } 1212 }
1155 1213
1156 visitWhile(While node) { 1214 visitWhile(While node) {
1157 visitLoop(node, null, node.condition, null, node.body); 1215 visitLoop(node, null, node.condition, null, node.body);
1158 } 1216 }
1159 1217
1160 visitDoWhile(DoWhile node) { 1218 visitDoWhile(DoWhile node) {
1161 localsHandler.startLoop(node); 1219 localsHandler.startLoop(node);
1162 BreakHandler breakHandler = beginLoopHeader(node); 1220 JumpHandler jumpHandler = beginLoopHeader(node);
1163 HBasicBlock loopEntryBlock = current; 1221 HBasicBlock loopEntryBlock = current;
1164 1222
1165 localsHandler.enterLoopBody(node); 1223 localsHandler.enterLoopBody(node);
1166 hackAroundPossiblyAbortingBody(node.body); 1224 hackAroundPossiblyAbortingBody(node.body);
1167 1225
1168 // If there are no continues we could avoid the creation of the condition 1226 // 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. 1227 // block. This could also lead to a block having multiple entries and exits.
1170 HBasicBlock bodyExitBlock = close(new HGoto()); 1228 HBasicBlock bodyExitBlock = close(new HGoto());
1171 HBasicBlock conditionBlock = addNewBlock(); 1229 HBasicBlock conditionBlock = addNewBlock();
1172 bodyExitBlock.addSuccessor(conditionBlock); 1230 bodyExitBlock.addSuccessor(conditionBlock);
1231 jumpHandler.forEachContinue((x,y) {
1232 // TODO(lrn): Handle continue in do-while loops.
1233 compiler.cancel("do-while with continue", node: node);
1234 });
1173 open(conditionBlock); 1235 open(conditionBlock);
1174 visit(node.condition); 1236 visit(node.condition);
1175 assert(!isAborted()); 1237 assert(!isAborted());
1176 conditionBlock = close(new HLoopBranch(popBoolified(), 1238 conditionBlock = close(new HLoopBranch(popBoolified(),
1177 HLoopBranch.DO_WHILE_LOOP)); 1239 HLoopBranch.DO_WHILE_LOOP));
1178 1240
1179 conditionBlock.addSuccessor(loopEntryBlock); // The back-edge. 1241 conditionBlock.addSuccessor(loopEntryBlock); // The back-edge.
1180 loopEntryBlock.postProcessLoopHeader(); 1242 loopEntryBlock.postProcessLoopHeader();
1181 1243
1182 endLoop(loopEntryBlock, conditionBlock, breakHandler, localsHandler); 1244 endLoop(loopEntryBlock, conditionBlock, jumpHandler, localsHandler);
1245 jumpHandler.close();
1183 } 1246 }
1184 1247
1185 visitFunctionExpression(FunctionExpression node) { 1248 visitFunctionExpression(FunctionExpression node) {
1186 ClosureData nestedClosureData = closureDataCache[node]; 1249 ClosureData nestedClosureData = closureDataCache[node];
1187 assert(nestedClosureData !== null); 1250 assert(nestedClosureData !== null);
1188 assert(nestedClosureData.closureClassElement !== null); 1251 assert(nestedClosureData.closureClassElement !== null);
1189 ClassElement closureClassElement = 1252 ClassElement closureClassElement =
1190 nestedClosureData.closureClassElement; 1253 nestedClosureData.closureClassElement;
1191 FunctionElement callElement = nestedClosureData.callElement; 1254 FunctionElement callElement = nestedClosureData.callElement;
1192 compiler.enqueue(new WorkItem.toCodegen(callElement, elements)); 1255 compiler.enqueue(new WorkItem.toCodegen(callElement, elements));
(...skipping 913 matching lines...) Expand 10 before | Expand all | Expand 10 after
2106 2169
2107 visitModifiers(Modifiers node) { 2170 visitModifiers(Modifiers node) {
2108 compiler.unimplemented('SsaBuilder.visitModifiers', node: node); 2171 compiler.unimplemented('SsaBuilder.visitModifiers', node: node);
2109 } 2172 }
2110 2173
2111 visitBreakStatement(BreakStatement node) { 2174 visitBreakStatement(BreakStatement node) {
2112 work.allowSpeculativeOptimization = false; 2175 work.allowSpeculativeOptimization = false;
2113 assert(!isAborted()); 2176 assert(!isAborted());
2114 TargetElement target = elements[node]; 2177 TargetElement target = elements[node];
2115 assert(target !== null); 2178 assert(target !== null);
2116 BreakHandler handler = breakTargets[target]; 2179 JumpHandler handler = jumpTargets[target];
2117 assert(handler !== null); 2180 assert(handler !== null);
2118 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
2119 HBreak breakInstruction;
2120 if (node.target === null) { 2181 if (node.target === null) {
2121 breakInstruction = new HBreak(target); 2182 handler.generateBreak();
ngeoffray 2012/03/19 11:42:06 I think I'd prefer something like: handler.generat
Lasse Reichstein Nielsen 2012/03/19 12:13:58 I generally find the conditional operator harder t
2122 } else { 2183 } else {
2123 LabelElement label = elements[node.target]; 2184 LabelElement label = elements[node.target];
2124 breakInstruction = new HBreak.toLabel(label); 2185 handler.generateBreak(label);
2125 } 2186 }
2126 close(breakInstruction);
2127 handler.addBreak(breakInstruction, savedLocals);
2128 } 2187 }
2129 2188
2130 visitContinueStatement(ContinueStatement node) { 2189 visitContinueStatement(ContinueStatement node) {
2131 // TODO(lrn): Replace this with a real implementation of continue. 2190 work.allowSpeculativeOptimization = false;
2132 compiler.reportWarning(node, 'continue not implemented'); 2191 assert(!isAborted());
ngeoffray 2012/03/19 11:42:06 I'd get rid of that assert, since the method that
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Done.
2133 generateUnimplemented('continue not implemented'); 2192 TargetElement target = elements[node];
2193 assert(target !== null);
2194 JumpHandler handler = jumpTargets[target];
2195 assert(handler !== null);
2196 if (node.target === null) {
2197 handler.generateContinue();
2198 } else {
2199 LabelElement label = elements[node.target];
2200 handler.generateContinue(label);
2201 }
2134 } 2202 }
2135 2203
2136 BreakHandler getBreakHandler(Node node) { 2204 JumpHandler getLoopJumpHandler(Loop node) {
ngeoffray 2012/03/19 11:42:06 Please consider what we discussed and remove this
Lasse Reichstein Nielsen 2012/03/19 12:13:58 Renamed to createJumpHandler, and always creates s
2137 TargetElement element = elements[node]; 2205 if (loopJumpHandler === null) {
2138 if (element === null) return const NullBreakHandler(); 2206 // No labels on the loop.
2139 return new BreakHandler(this, element); 2207 TargetElement element = elements[node];
2208 if (element === null) {
2209 // No unlabeled breaks or continues on the loop either.
2210 return const NullJumpHandler();
2211 }
2212 return new JumpHandler(this, element);
2213 }
2214 // Use the jump handler created for the labels for the loop too.
2215 JumpHandler handler = loopJumpHandler;
2216 loopJumpHandler = null;
2217 return handler;
2140 } 2218 }
2141 2219
2142 visitForInStatement(ForInStatement node) { 2220 visitForInStatement(ForInStatement node) {
2143 // Generate a structure equivalent to: 2221 // Generate a structure equivalent to:
2144 // Iterator<E> $iter = <iterable>.iterator() 2222 // Iterator<E> $iter = <iterable>.iterator()
2145 // while ($iter.hasNext()) { 2223 // while ($iter.hasNext()) {
2146 // E <declaredIdentifier> = $iter.next(); 2224 // E <declaredIdentifier> = $iter.next();
2147 // <body> 2225 // <body>
2148 // } 2226 // }
2149 localsHandler.startLoop(node); 2227 localsHandler.startLoop(node);
2150 2228
2151 SourceString iteratorName = const SourceString("iterator"); 2229 SourceString iteratorName = const SourceString("iterator");
2152 2230
2153 Selector selector = Selector.INVOCATION_0; 2231 Selector selector = Selector.INVOCATION_0;
2154 Element interceptor = interceptors.getStaticInterceptor(iteratorName, 0); 2232 Element interceptor = interceptors.getStaticInterceptor(iteratorName, 0);
2155 assert(interceptor != null); 2233 assert(interceptor != null);
2156 HStatic target = new HStatic(interceptor); 2234 HStatic target = new HStatic(interceptor);
2157 add(target); 2235 add(target);
2158 visit(node.expression); 2236 visit(node.expression);
2159 List<HInstruction> inputs = <HInstruction>[target, pop()]; 2237 List<HInstruction> inputs = <HInstruction>[target, pop()];
2160 HInstruction iterator = new HInvokeInterceptor( 2238 HInstruction iterator = new HInvokeInterceptor(
2161 selector, iteratorName, false, inputs); 2239 selector, iteratorName, false, inputs);
2162 add(iterator); 2240 add(iterator);
2163 2241
2164 BreakHandler breakHandler = beginLoopHeader(node); 2242 JumpHandler jumpHandler = beginLoopHeader(node);
2165 HBasicBlock conditionBlock = current; 2243 HBasicBlock conditionBlock = current;
2166 2244
2167 // The condition. 2245 // The condition.
2168 push(new HInvokeDynamicMethod( 2246 push(new HInvokeDynamicMethod(
2169 selector, const SourceString('hasNext'), [iterator])); 2247 selector, const SourceString('hasNext'), [iterator]));
2170 HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified())); 2248 HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified()));
2171 2249
2172 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 2250 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
2173 2251
2174 // The body. 2252 // The body.
(...skipping 13 matching lines...) Expand all
2188 } else { 2266 } else {
2189 assert(node.declaredIdentifier.asVariableDefinitions() !== null); 2267 assert(node.declaredIdentifier.asVariableDefinitions() !== null);
2190 VariableDefinitions variableDefinitions = node.declaredIdentifier; 2268 VariableDefinitions variableDefinitions = node.declaredIdentifier;
2191 variable = elements[variableDefinitions.definitions.nodes.head]; 2269 variable = elements[variableDefinitions.definitions.nodes.head];
2192 } 2270 }
2193 localsHandler.updateLocal(variable, pop()); 2271 localsHandler.updateLocal(variable, pop());
2194 2272
2195 hackAroundPossiblyAbortingBody(node.body); 2273 hackAroundPossiblyAbortingBody(node.body);
2196 bodyBlock = close(new HGoto()); 2274 bodyBlock = close(new HGoto());
2197 2275
2276 jumpHandler.forEachContinue((x,y) {
2277 // TODO(lrn): Handle continue in for-in.
2278 // TODO(lrn): Or, preferably, use an abstraction of visitLoop for for-in.
2279 compiler.cancel('for-in with continue', node: node);
2280 });
2281
2198 // Update. 2282 // Update.
2199 // We create an update block, even if we are in a for-in loop. The 2283 // We create an update block, even if we are in a for-in loop. The
2200 // update block is the jump-target for continue statements. We could avoid 2284 // update block is the jump-target for continue statements. We could avoid
2201 // the creation if there is no continue, but for now we always create it. 2285 // the creation if there is no continue, but for now we always create it.
2202 HBasicBlock updateBlock = addNewBlock(); 2286 HBasicBlock updateBlock = addNewBlock();
2287
2203 bodyBlock.addSuccessor(updateBlock); 2288 bodyBlock.addSuccessor(updateBlock);
2204 open(updateBlock); 2289 open(updateBlock);
2205 updateBlock = close(new HGoto()); 2290 updateBlock = close(new HGoto());
2206 // The back-edge completing the cycle. 2291 // The back-edge completing the cycle.
2207 updateBlock.addSuccessor(conditionBlock); 2292 updateBlock.addSuccessor(conditionBlock);
2208 conditionBlock.postProcessLoopHeader(); 2293 conditionBlock.postProcessLoopHeader();
2209 2294
2210 endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals); 2295 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
2211 breakHandler.close(); 2296 jumpHandler.close();
2212 } 2297 }
2213 2298
2214 visitLabeledStatement(LabeledStatement node) { 2299 visitLabeledStatement(LabeledStatement node) {
2215 Statement body = node.getBody(); 2300 Statement body = node.getBody();
2216 if (body is Loop || body is SwitchStatement) { 2301 if (body is Loop || body is SwitchStatement) {
2217 // Loops and switches handle their own labels. 2302 // Loops and switches handle their own labels.
2218 visit(body); 2303 visit(body);
2219 return; 2304 return;
2220 } 2305 }
2221 // Non-loop statements can only be break targets, not continue targets. 2306 // Non-loop statements can only be break targets, not continue targets.
2222 TargetElement targetElement = elements[body]; 2307 TargetElement targetElement = elements[body];
2223 if (targetElement === null || targetElement.statement !== body) { 2308 if (targetElement === null || targetElement.statement !== body) {
2224 // Labeled statements with no element on the body have no breaks. 2309 // Labeled statements with no element on the body have no breaks.
2225 // A different target statement only happens if the body is itself 2310 // A different target statement only happens if the body is itself
2226 // a break or continue for a different target. In that case, this 2311 // a break or continue for a different target. In that case, this
2227 // label is also always unused. 2312 // label is also always unused.
2228 visit(body); 2313 visit(body);
2229 return; 2314 return;
2230 } 2315 }
2231 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler); 2316 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler);
2232 assert(targetElement.isBreakTarget); 2317 assert(targetElement.isBreakTarget);
2233 BreakHandler handler = new BreakHandler(this, targetElement); 2318 JumpHandler handler = new JumpHandler(this, targetElement);
2234 // Introduce a new basic block. 2319 // Introduce a new basic block.
2235 HBasicBlock entryBlock = graph.addNewBlock(); 2320 HBasicBlock entryBlock = graph.addNewBlock();
2236 goto(current, entryBlock); 2321 goto(current, entryBlock);
2237 open(entryBlock); 2322 open(entryBlock);
2238 hackAroundPossiblyAbortingBody(body); 2323 hackAroundPossiblyAbortingBody(body);
2239 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock); 2324 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock);
2240 2325
2241 HBasicBlock joinBlock = graph.addNewBlock(); 2326 HBasicBlock joinBlock = graph.addNewBlock();
2242 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 2327 List<LocalsHandler> breakLocals = <LocalsHandler>[];
2243 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 2328 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
2293 HBasicBlock startBlock = graph.addNewBlock(); 2378 HBasicBlock startBlock = graph.addNewBlock();
2294 goto(current, startBlock); 2379 goto(current, startBlock);
2295 open(startBlock); 2380 open(startBlock);
2296 visit(node.expression); 2381 visit(node.expression);
2297 HInstruction expression = pop(); 2382 HInstruction expression = pop();
2298 if (node.cases.isEmpty()) { 2383 if (node.cases.isEmpty()) {
2299 return; 2384 return;
2300 } 2385 }
2301 Link<Node> cases = node.cases.nodes; 2386 Link<Node> cases = node.cases.nodes;
2302 2387
2303 BreakHandler breakHandler = getBreakHandler(node); 2388 // TODO(lrn): Rename getLoopJumpHandler to also match switches.
2389 // OR make it always create the handler, instead of letting
2390 // the LabeledStatement do it.
2391 JumpHandler jumpHandler = getLoopJumpHandler(node);
2304 2392
2305 buildSwitchCases(cases, expression); 2393 buildSwitchCases(cases, expression);
2306 2394
2307 HBasicBlock lastBlock = lastOpenedBlock; 2395 HBasicBlock lastBlock = lastOpenedBlock;
2308 2396
2309 // Create merge block for break targets. 2397 // Create merge block for break targets.
2310 HBasicBlock joinBlock = new HBasicBlock(); 2398 HBasicBlock joinBlock = new HBasicBlock();
2311 List<LocalsHandler> caseLocals = <LocalsHandler>[]; 2399 List<LocalsHandler> caseLocals = <LocalsHandler>[];
2312 breakHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 2400 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
2313 instruction.block.addSuccessor(joinBlock); 2401 instruction.block.addSuccessor(joinBlock);
2314 caseLocals.add(locals); 2402 caseLocals.add(locals);
2315 }); 2403 });
2316 if (!isAborted()) { 2404 if (!isAborted()) {
2317 // The current flow is only aborted if the switch has a default that 2405 // The current flow is only aborted if the switch has a default that
2318 // aborts (all previous cases must abort, and if there is no default, 2406 // aborts (all previous cases must abort, and if there is no default,
2319 // it's possible to miss all the cases). 2407 // it's possible to miss all the cases).
2320 caseLocals.add(localsHandler); 2408 caseLocals.add(localsHandler);
2321 goto(current, joinBlock); 2409 goto(current, joinBlock);
2322 } 2410 }
2323 if (caseLocals.length != 0) { 2411 if (caseLocals.length != 0) {
2324 graph.addBlock(joinBlock); 2412 graph.addBlock(joinBlock);
2325 open(joinBlock); 2413 open(joinBlock);
2326 if (caseLocals.length == 1) { 2414 if (caseLocals.length == 1) {
2327 localsHandler = caseLocals[0]; 2415 localsHandler = caseLocals[0];
2328 } else { 2416 } else {
2329 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock); 2417 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
2330 } 2418 }
2331 } else { 2419 } else {
2332 // The joinblock is not used. 2420 // The joinblock is not used.
2333 joinBlock = null; 2421 joinBlock = null;
2334 } 2422 }
2335 startBlock.labeledBlockInformation = new HLabeledBlockInformation.implicit( 2423 startBlock.labeledBlockInformation = new HLabeledBlockInformation.implicit(
2336 new SubGraph(startBlock, lastBlock), 2424 new SubGraph(startBlock, lastBlock),
2337 joinBlock, 2425 joinBlock,
2338 elements[node]); 2426 elements[node]);
2427 jumpHandler.close();
2339 } 2428 }
2340 2429
2341 2430
2342 // Recursively build an if/else structure to match the cases. 2431 // Recursively build an if/else structure to match the cases.
2343 buildSwitchCases(Link<Node> cases, HInstruction expression) { 2432 buildSwitchCases(Link<Node> cases, HInstruction expression) {
2344 SwitchCase node = cases.head; 2433 SwitchCase node = cases.head;
2345 2434
2346 // Called for the statements on all but the last case block. 2435 // Called for the statements on all but the last case block.
2347 // Ensures that a user expecting a fallthrough gets an error. 2436 // Ensures that a user expecting a fallthrough gets an error.
2348 void visitStatementsAndAbort() { 2437 void visitStatementsAndAbort() {
(...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after
2557 buildBody() { 2646 buildBody() {
2558 // TODO(lrn): Make sure to take continue into account. 2647 // TODO(lrn): Make sure to take continue into account.
2559 visit(body); 2648 visit(body);
2560 if (isAborted()) { 2649 if (isAborted()) {
2561 compiler.reportWarning(body, "aborting loop body"); 2650 compiler.reportWarning(body, "aborting loop body");
2562 } 2651 }
2563 } 2652 }
2564 handleIf(buildBody, null); 2653 handleIf(buildBody, null);
2565 } 2654 }
2566 } 2655 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698