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

Side by Side Diff: sdk/lib/_internal/compiler/implementation/ssa/builder.dart

Issue 14969004: Implement continue for switch. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 7 years, 7 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 part of ssa; 5 part of ssa;
6 6
7 /** 7 /**
8 * A special element for the extra parameter taken by intercepted 8 * A special element for the extra parameter taken by intercepted
9 * methods. We need to override [Element.computeType] because our 9 * methods. We need to override [Element.computeType] because our
10 * optimizers may look at its declared type. 10 * optimizers may look at its declared type.
(...skipping 515 matching lines...) Expand 10 before | Expand all | Expand 10 after
526 void enterLoopBody(Node node) { 526 void enterLoopBody(Node node) {
527 ClosureScope scopeData = closureData.capturingScopes[node]; 527 ClosureScope scopeData = closureData.capturingScopes[node];
528 if (scopeData == null) return; 528 if (scopeData == null) return;
529 // If there are no declared boxed loop variables then we did not create the 529 // If there are no declared boxed loop variables then we did not create the
530 // box before the initializer and we have to create the box now. 530 // box before the initializer and we have to create the box now.
531 if (!scopeData.hasBoxedLoopVariables()) { 531 if (!scopeData.hasBoxedLoopVariables()) {
532 enterScope(node, null); 532 enterScope(node, null);
533 } 533 }
534 } 534 }
535 535
536 void enterLoopUpdates(Loop node) { 536 void enterLoopUpdates(Node node) {
537 // If there are declared boxed loop variables then the updates might have 537 // If there are declared boxed loop variables then the updates might have
538 // access to the box and we must switch to a new box before executing the 538 // access to the box and we must switch to a new box before executing the
539 // updates. 539 // updates.
540 // In all other cases a new box will be created when entering the body of 540 // In all other cases a new box will be created when entering the body of
541 // the next iteration. 541 // the next iteration.
542 ClosureScope scopeData = closureData.capturingScopes[node]; 542 ClosureScope scopeData = closureData.capturingScopes[node];
543 if (scopeData == null) return; 543 if (scopeData == null) return;
544 if (scopeData.hasBoxedLoopVariables()) { 544 if (scopeData.hasBoxedLoopVariables()) {
545 updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables); 545 updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables);
546 } 546 }
(...skipping 182 matching lines...) Expand 10 before | Expand all | Expand 10 after
729 builder.close(breakInstruction); 729 builder.close(breakInstruction);
730 jumps.add(new JumpHandlerEntry(breakInstruction, locals)); 730 jumps.add(new JumpHandlerEntry(breakInstruction, locals));
731 } 731 }
732 732
733 void generateContinue([LabelElement label]) { 733 void generateContinue([LabelElement label]) {
734 HInstruction continueInstruction; 734 HInstruction continueInstruction;
735 if (label == null) { 735 if (label == null) {
736 continueInstruction = new HContinue(target); 736 continueInstruction = new HContinue(target);
737 } else { 737 } else {
738 continueInstruction = new HContinue.toLabel(label); 738 continueInstruction = new HContinue.toLabel(label);
739 // Switch case continue statements must be handled by the
740 // [SwitchCaseJumpHandler].
741 assert(label.target.statement is! SwitchCase);
739 } 742 }
740 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler); 743 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
741 builder.close(continueInstruction); 744 builder.close(continueInstruction);
742 jumps.add(new JumpHandlerEntry(continueInstruction, locals)); 745 jumps.add(new JumpHandlerEntry(continueInstruction, locals));
743 } 746 }
744 747
745 void forEachBreak(Function action) { 748 void forEachBreak(Function action) {
746 for (JumpHandlerEntry entry in jumps) { 749 for (JumpHandlerEntry entry in jumps) {
747 if (entry.isBreak()) action(entry.jumpInstruction, entry.locals); 750 if (entry.isBreak()) action(entry.jumpInstruction, entry.locals);
748 } 751 }
(...skipping 27 matching lines...) Expand all
776 List<LabelElement> labels() { 779 List<LabelElement> labels() {
777 List<LabelElement> result = null; 780 List<LabelElement> result = null;
778 for (LabelElement element in target.labels) { 781 for (LabelElement element in target.labels) {
779 if (result == null) result = <LabelElement>[]; 782 if (result == null) result = <LabelElement>[];
780 result.add(element); 783 result.add(element);
781 } 784 }
782 return (result == null) ? const <LabelElement>[] : result; 785 return (result == null) ? const <LabelElement>[] : result;
783 } 786 }
784 } 787 }
785 788
789 /// Special [JumpHandler] implementation used to handle continue statements
790 /// targeting switch cases.
791 class SwitchCaseJumpHandler extends TargetJumpHandler {
792 /// Map from switch case targets to indices used to encode the flow of the
793 /// switch case loop.
794 final Map<TargetElement, int> targetIndexMap = new Map<TargetElement, int>();
795
796 SwitchCaseJumpHandler(SsaBuilder builder,
797 TargetElement target,
798 SwitchStatement node)
799 : super(builder, target) {
800 // The switch case indices must match those computed in
801 // [SsaBuilder.visitSwitchStatement].
802 int switchIndex = 1;
ngeoffray 2013/05/14 07:08:51 Explain why you start with 1.
Johnni Winther 2013/05/17 07:03:04 Done.
803 for (SwitchCase switchCase in node.cases) {
804 for (Node labelOrCase in switchCase.labelsAndCases) {
805 Node label = labelOrCase.asLabel();
806 if (label != null) {
807 LabelElement labelElement = builder.elements[label];
808 if (labelElement != null) {
809 if (labelElement.isContinueTarget) {
ngeoffray 2013/05/14 07:08:51 I prever avoiding nested if and do if (labelElemen
Johnni Winther 2013/05/17 07:03:04 Done.
810 TargetElement continueTarget = labelElement.target;
811 targetIndexMap[continueTarget] = switchIndex;
812 assert(builder.jumpTargets[continueTarget] == null);
813 builder.jumpTargets[continueTarget] = this;
814 }
815 }
816 }
817 }
818 switchIndex++;
819 }
820 }
821
822 void generateBreak([LabelElement label]) {
823 if (label == null) {
824 // Creates a special break instruction for the synthetic loop generated
825 // for a switch statement with continue statements. See
826 // [SsaBuilder.visitSwitchStatement] for detail.
827
828 HInstruction breakInstruction =
829 new HBreak(target, breakSwitchContinueLoop: true);
830 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
831 builder.close(breakInstruction);
832 jumps.add(new JumpHandlerEntry(breakInstruction, locals));
833 } else {
834 super.generateBreak(label);
835 }
836 }
837
838 void generateContinue([LabelElement label]) {
839 if (label != null && targetIndexMap.containsKey(label.target)) {
ngeoffray 2013/05/14 07:08:51 It would read nicer with a helper method whose nam
Johnni Winther 2013/05/17 07:03:04 Done.
840 // Creates the special instructions 'label = i; continue l;' used in
841 // switch statements with continue statements. See
842 // [SsaBuilder.visitSwitchStatement] for detail.
843
844 assert(label != null);
845 HInstruction value = builder.graph.addConstantInt(
846 targetIndexMap[label.target],
847 builder.constantSystem);
848 builder.localsHandler.updateLocal(target, value);
849
850 assert(label.target.labels.contains(label));
851 HInstruction continueInstruction = new HContinue(target);
852 LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
853 builder.close(continueInstruction);
854 jumps.add(new JumpHandlerEntry(continueInstruction, locals));
855 } else {
856 super.generateContinue(label);
857 }
858 }
859
860 void close() {
861 // The mapping from TargetElement to JumpHandler is no longer needed.
862 for (TargetElement target in targetIndexMap.keys) {
863 builder.jumpTargets.remove(target);
864 }
865 super.close();
866 }
867 }
868
786 class SsaBuilder extends ResolvedVisitor implements Visitor { 869 class SsaBuilder extends ResolvedVisitor implements Visitor {
787 final SsaBuilderTask builder; 870 final SsaBuilderTask builder;
788 final JavaScriptBackend backend; 871 final JavaScriptBackend backend;
789 final CodegenWorkItem work; 872 final CodegenWorkItem work;
790 final ConstantSystem constantSystem; 873 final ConstantSystem constantSystem;
791 HGraph graph; 874 HGraph graph;
792 LocalsHandler localsHandler; 875 LocalsHandler localsHandler;
793 HInstruction rethrowableException; 876 HInstruction rethrowableException;
794 Map<Element, HInstruction> parameters; 877 Map<Element, HInstruction> parameters;
795 final RuntimeTypes rti; 878 final RuntimeTypes rti;
(...skipping 1085 matching lines...) Expand 10 before | Expand all | Expand 10 after
1881 1964
1882 /** 1965 /**
1883 * Creates a new loop-header block. The previous [current] block 1966 * Creates a new loop-header block. The previous [current] block
1884 * is closed with an [HGoto] and replaced by the newly created block. 1967 * is closed with an [HGoto] and replaced by the newly created block.
1885 * Also notifies the locals handler that we're entering a loop. 1968 * Also notifies the locals handler that we're entering a loop.
1886 */ 1969 */
1887 JumpHandler beginLoopHeader(Node node) { 1970 JumpHandler beginLoopHeader(Node node) {
1888 assert(!isAborted()); 1971 assert(!isAborted());
1889 HBasicBlock previousBlock = close(new HGoto()); 1972 HBasicBlock previousBlock = close(new HGoto());
1890 1973
1891 JumpHandler jumpHandler = createJumpHandler(node); 1974 JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: true);
1892 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock( 1975 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(
1893 jumpHandler.target, 1976 jumpHandler.target,
1894 jumpHandler.labels()); 1977 jumpHandler.labels());
1895 previousBlock.addSuccessor(loopEntry); 1978 previousBlock.addSuccessor(loopEntry);
1896 open(loopEntry); 1979 open(loopEntry);
1897 1980
1898 localsHandler.beginLoopHeader(loopEntry); 1981 localsHandler.beginLoopHeader(loopEntry);
1899 return jumpHandler; 1982 return jumpHandler;
1900 } 1983 }
1901 1984
(...skipping 2218 matching lines...) Expand 10 before | Expand all | Expand 10 after
4120 LabelElement label = elements[node.target]; 4203 LabelElement label = elements[node.target];
4121 assert(label != null); 4204 assert(label != null);
4122 handler.generateContinue(label); 4205 handler.generateContinue(label);
4123 } 4206 }
4124 } 4207 }
4125 4208
4126 /** 4209 /**
4127 * Creates a [JumpHandler] for a statement. The node must be a jump 4210 * Creates a [JumpHandler] for a statement. The node must be a jump
4128 * target. If there are no breaks or continues targeting the statement, 4211 * target. If there are no breaks or continues targeting the statement,
4129 * a special "null handler" is returned. 4212 * a special "null handler" is returned.
4213 *
4214 * [isLoopJump] is [:true:] when the jump handler is for a loop. This is used
4215 * to distinguish the synthetized loop created for a switch statement with
4216 * continue statements from simple switch statements.
4130 */ 4217 */
4131 JumpHandler createJumpHandler(Statement node) { 4218 JumpHandler createJumpHandler(Statement node, {bool isLoopJump}) {
4132 TargetElement element = elements[node]; 4219 TargetElement element = elements[node];
4133 if (element == null || !identical(element.statement, node)) { 4220 if (element == null || !identical(element.statement, node)) {
4134 // No breaks or continues to this node. 4221 // No breaks or continues to this node.
4135 return new NullJumpHandler(compiler); 4222 return new NullJumpHandler(compiler);
4136 } 4223 }
4224 if (isLoopJump && node is SwitchStatement) {
4225 // Create a special jump handler for loops created for switch statements
4226 // with continue statements.
4227 return new SwitchCaseJumpHandler(this, element, node);
4228 }
4137 return new JumpHandler(this, element); 4229 return new JumpHandler(this, element);
4138 } 4230 }
4139 4231
4140 visitForIn(ForIn node) { 4232 visitForIn(ForIn node) {
4141 // Generate a structure equivalent to: 4233 // Generate a structure equivalent to:
4142 // Iterator<E> $iter = <iterable>.iterator; 4234 // Iterator<E> $iter = <iterable>.iterator;
4143 // while ($iter.moveNext()) { 4235 // while ($iter.moveNext()) {
4144 // E <declaredIdentifier> = $iter.current; 4236 // E <declaredIdentifier> = $iter.current;
4145 // <body> 4237 // <body>
4146 // } 4238 // }
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after
4266 visitLiteralMapEntry(LiteralMapEntry node) { 4358 visitLiteralMapEntry(LiteralMapEntry node) {
4267 visit(node.value); 4359 visit(node.value);
4268 visit(node.key); 4360 visit(node.key);
4269 } 4361 }
4270 4362
4271 visitNamedArgument(NamedArgument node) { 4363 visitNamedArgument(NamedArgument node) {
4272 visit(node.expression); 4364 visit(node.expression);
4273 } 4365 }
4274 4366
4275 visitSwitchStatement(SwitchStatement node) { 4367 visitSwitchStatement(SwitchStatement node) {
4276 if (tryBuildConstantSwitch(node)) return; 4368 // The switch case indices must match those computed in
4369 // [SwitchCaseJumpHandler].
4370 bool hasContinue = false;
4371 Map<SwitchCase, int> caseIndex = new Map<SwitchCase, int>();
4372 int switchIndex = 1;
4373 bool hasDefault = false;
4374 for (SwitchCase switchCase in node.cases) {
4375 for (Node labelOrCase in switchCase.labelsAndCases) {
4376 Node label = labelOrCase.asLabel();
4377 if (label != null) {
4378 LabelElement labelElement = elements[label];
4379 if (labelElement != null && labelElement.isContinueTarget) {
4380 hasContinue = true;
4381 }
4382 }
4383 }
4384 if (switchCase.isDefaultCase) {
4385 hasDefault = true;
4386 }
4387 caseIndex[switchCase] = switchIndex;
4388 switchIndex++;
4389 }
4390 if (!hasContinue) {
4391 // If the switch statement has no switch cases targeted by continue
4392 // statements we encode the switch statement directly.
4393 void buildSwitchCase(SwitchCase node) {
4394 visit(node.statements);
4395 }
4396 buildSwitchStatement(node, buildSwitchCase);
4397 } else {
4398 // If the switch statement has switch cases targeted by continue
4399 // statements we create the following encoding:
4400 //
4401 // switch (e) {
4402 // l_1: case e0: s_1; break;
4403 // l_2: case e1: s_2; continue l_i;
4404 // ...
4405 // l_n: default: s_n; continue l_j;
4406 // }
4407 //
4408 // is encoded as
4409 //
4410 // var target;
4411 // switch (e) {
4412 // case e1: target = 1; break;
4413 // case e2: target = 2; break;
4414 // ...
4415 // default: target = n; break;
4416 // }
4417 // l: while (true) {
4418 // switch (target) {
4419 // case 1: s_1; break l;
4420 // case 2: s_2; target = i; continue l;
4421 // ...
4422 // case n: s_n; target = j; continue l;
4423 // }
4424 // }
4277 4425
4426 TargetElement switchTarget = elements[node];
4427 HInstruction initialValue = graph.addConstantNull(constantSystem);
4428 localsHandler.updateLocal(switchTarget, initialValue);
4429 void buildSwitchCase(SwitchCase switchCase) {
4430 // Generate 'target = i; break;' for switch case i.
4431 int index = caseIndex[switchCase];
4432 HInstruction value = graph.addConstantInt(index, constantSystem);
4433 localsHandler.updateLocal(switchTarget, value);
4434 jumpTargets[switchTarget].generateBreak();
4435 }
4436 buildSwitchStatement(node, buildSwitchCase);
4437
4438 HInstruction buildCondition() =>
4439 graph.addConstantBool(true, constantSystem);
4440
4441 void buildSwitch() {
4442 HInstruction buildExpression() {
4443 return localsHandler.readLocal(switchTarget);
4444 }
4445 Iterable<Constant> getConstants(SwitchCase switchCase) {
4446 return <Constant>[constantSystem.createInt(caseIndex[switchCase])];
4447 }
4448 void buildSwitchCase(SwitchCase switchCase) {
4449 visit(switchCase.statements);
4450 if (!isAborted()) {
4451 // Ensure that we break the loop if the case falls through. (This
4452 // is only possible for the last case.)
4453 jumpTargets[switchTarget].generateBreak();
4454 }
4455 }
4456 // Pass a [NullJumpHandler] because the target for the contained break
4457 // is not the generated switch statement but instead the loop generated
4458 // in the call to [handleLoop] below.
4459 handleSwitch(
4460 new NullJumpHandler(compiler),
4461 buildExpression, node, getConstants,
4462 (_) => false, // No case is default.
4463 buildSwitchCase);
4464 }
4465
4466 void buildLoop() {
4467 handleLoop(node,
4468 () {},
4469 buildCondition,
4470 () {},
4471 buildSwitch);
4472 }
4473
4474 if (hasDefault) {
4475 buildLoop();
4476 } else {
4477 // If the switch statement has no default case, surround the loop with
4478 // a test of the target.
4479 void buildCondition() {
4480 push(createForeign('#', HType.BOOLEAN,
4481 [localsHandler.readLocal(switchTarget)]));
4482 }
4483 handleIf(node, buildCondition, buildLoop, () => {});
4484 }
4485 }
4486 }
4487
4488 buildSwitchStatement(SwitchStatement node,
4489 void buildSwitchCase(SwitchCase switchCase)) {
4490 if (tryBuildConstantSwitch(node, buildSwitchCase)) return;
4278 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 4491 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
4279 HBasicBlock startBlock = openNewBlock(); 4492 HBasicBlock startBlock = openNewBlock();
4280 visit(node.expression); 4493 visit(node.expression);
4281 HInstruction expression = pop(); 4494 HInstruction expression = pop();
4282 if (node.cases.isEmpty) { 4495 if (node.cases.isEmpty) {
4283 return; 4496 return;
4284 } 4497 }
4285 4498
4286 Link<Node> cases = node.cases.nodes; 4499 Link<Node> cases = node.cases.nodes;
4287 JumpHandler jumpHandler = createJumpHandler(node); 4500 JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: false);
4288 4501
4289 buildSwitchCases(cases, expression); 4502 buildSwitchCases(jumpHandler, cases, expression, buildSwitchCase);
4290 4503
4291 HBasicBlock lastBlock = lastOpenedBlock; 4504 HBasicBlock lastBlock = lastOpenedBlock;
4292 4505
4293 // Create merge block for break targets. 4506 // Create merge block for break targets.
4294 HBasicBlock joinBlock = new HBasicBlock(); 4507 HBasicBlock joinBlock = new HBasicBlock();
4295 List<LocalsHandler> caseHandlers = <LocalsHandler>[]; 4508 List<LocalsHandler> caseHandlers = <LocalsHandler>[];
4296 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 4509 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
4297 instruction.block.addSuccessor(joinBlock); 4510 instruction.block.addSuccessor(joinBlock);
4298 caseHandlers.add(locals); 4511 caseHandlers.add(locals);
4299 }); 4512 });
(...skipping 17 matching lines...) Expand all
4317 joinBlock = null; 4530 joinBlock = null;
4318 } 4531 }
4319 startBlock.setBlockFlow( 4532 startBlock.setBlockFlow(
4320 new HLabeledBlockInformation.implicit( 4533 new HLabeledBlockInformation.implicit(
4321 new HSubGraphBlockInformation(new SubGraph(startBlock, lastBlock)), 4534 new HSubGraphBlockInformation(new SubGraph(startBlock, lastBlock)),
4322 elements[node]), 4535 elements[node]),
4323 joinBlock); 4536 joinBlock);
4324 jumpHandler.close(); 4537 jumpHandler.close();
4325 } 4538 }
4326 4539
4327 bool tryBuildConstantSwitch(SwitchStatement node) { 4540 bool tryBuildConstantSwitch(SwitchStatement node,
4541 void buildSwitchCase(SwitchCase switchCase)) {
4328 Map<CaseMatch, Constant> constants = new Map<CaseMatch, Constant>(); 4542 Map<CaseMatch, Constant> constants = new Map<CaseMatch, Constant>();
4329 // First check whether all case expressions are compile-time constants, 4543 // First check whether all case expressions are compile-time constants,
4330 // and all have the same type that doesn't override operator==. 4544 // and all have the same type that doesn't override operator==.
4331 // TODO(lrn): Move the constant resolution to the resolver, so 4545 // TODO(lrn): Move the constant resolution to the resolver, so
4332 // we can report an error before reaching the backend. 4546 // we can report an error before reaching the backend.
4333 DartType firstConstantType = null; 4547 DartType firstConstantType = null;
4334 bool failure = false; 4548 bool failure = false;
4335 for (SwitchCase switchCase in node.cases) { 4549 for (SwitchCase switchCase in node.cases) {
4336 for (Node labelOrCase in switchCase.labelsAndCases) { 4550 for (Node labelOrCase in switchCase.labelsAndCases) {
4337 if (labelOrCase is CaseMatch) { 4551 if (labelOrCase is CaseMatch) {
(...skipping 17 matching lines...) Expand all
4355 } else { 4569 } else {
4356 DartType constantType = 4570 DartType constantType =
4357 constant.computeType(compiler); 4571 constant.computeType(compiler);
4358 if (constantType != firstConstantType) { 4572 if (constantType != firstConstantType) {
4359 compiler.reportWarning(match.expression, 4573 compiler.reportWarning(match.expression,
4360 MessageKind.SWITCH_CASE_TYPES_NOT_EQUAL.error()); 4574 MessageKind.SWITCH_CASE_TYPES_NOT_EQUAL.error());
4361 failure = true; 4575 failure = true;
4362 } 4576 }
4363 } 4577 }
4364 constants[labelOrCase] = constant; 4578 constants[labelOrCase] = constant;
4365 } else {
4366 compiler.reportWarning(node, "Unsupported: Labels on cases");
4367 failure = true;
4368 } 4579 }
4369 } 4580 }
4370 } 4581 }
4371 if (failure) { 4582 if (failure) {
4372 return false; 4583 return false;
4373 } 4584 }
4374 4585
4586 JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: false);
4587 HInstruction buildExpression() {
4588 visit(node.expression);
4589 return pop();
4590 }
4591 Iterable<Constant> getConstants(SwitchCase switchCase) {
4592 List<Constant> constantList = <Constant>[];
4593 for (Node labelOrCase in switchCase.labelsAndCases) {
4594 if (labelOrCase is CaseMatch) {
4595 constantList.add(constants[labelOrCase]);
4596 }
4597 }
4598 return constantList;
4599 }
4600 handleSwitch(jumpHandler, buildExpression, node,
4601 getConstants,
4602 (SwitchCase switchCase) => switchCase.isDefaultCase,
4603 buildSwitchCase);
4604 jumpHandler.close();
4605 return true;
4606 }
4607
4608 /**
4609 * Creates a switch statement [node].
ngeoffray 2013/05/14 07:08:51 Do you mean a [HSwitch] ?
Johnni Winther 2013/05/17 07:03:04 A 'for' was missing. Now it doesn't apply.
4610 *
4611 * [jumpHandler] is the [JumpHandler] for the created switch statement.
4612 * [buildExpression] creates the switch expression.
4613 * [getConstants] returns the set of constants for a switch case.
4614 * [buildSwitchCase] creates the statements for the switch case.
4615 */
4616 void handleSwitch(JumpHandler jumpHandler,
4617 HInstruction buildExpression(),
4618 SwitchStatement node,
4619 Iterable<Constant> getConstants(SwitchCase switchCase),
4620 bool isDefaultCase(SwitchCase switchCase),
4621 void buildSwitchCase(SwitchCase switchCase)) {
4622 Map<CaseMatch, Constant> constants = new Map<CaseMatch, Constant>();
4623
4375 // TODO(ngeoffray): Handle switch-instruction in bailout code. 4624 // TODO(ngeoffray): Handle switch-instruction in bailout code.
4376 work.allowSpeculativeOptimization = false; 4625 work.allowSpeculativeOptimization = false;
4377 // Then build a switch structure. 4626 // Then build a switch structure.
4378 HBasicBlock expressionStart = openNewBlock(); 4627 HBasicBlock expressionStart = openNewBlock();
4379 visit(node.expression); 4628 HInstruction expression = buildExpression();
4380 HInstruction expression = pop();
4381 if (node.cases.isEmpty) { 4629 if (node.cases.isEmpty) {
4382 return true; 4630 return;
4383 } 4631 }
4384 HBasicBlock expressionEnd = current; 4632 HBasicBlock expressionEnd = current;
4385 4633
4386 HSwitch switchInstruction = new HSwitch(<HInstruction>[expression]); 4634 HSwitch switchInstruction = new HSwitch(<HInstruction>[expression]);
4387 HBasicBlock expressionBlock = close(switchInstruction); 4635 HBasicBlock expressionBlock = close(switchInstruction);
4388 JumpHandler jumpHandler = createJumpHandler(node);
4389 LocalsHandler savedLocals = localsHandler; 4636 LocalsHandler savedLocals = localsHandler;
4390 4637
4391 List<List<Constant>> matchExpressions = <List<Constant>>[]; 4638 List<List<Constant>> matchExpressions = <List<Constant>>[];
4392 List<HStatementInformation> statements = <HStatementInformation>[]; 4639 List<HStatementInformation> statements = <HStatementInformation>[];
4393 bool hasDefault = false; 4640 bool hasDefault = false;
4394 Element getFallThroughErrorElement = backend.getFallThroughError(); 4641 Element getFallThroughErrorElement = backend.getFallThroughError();
4395 HasNextIterator<Node> caseIterator = 4642 HasNextIterator<Node> caseIterator =
4396 new HasNextIterator<Node>(node.cases.iterator); 4643 new HasNextIterator<Node>(node.cases.iterator);
4397 while (caseIterator.hasNext) { 4644 while (caseIterator.hasNext) {
4398 SwitchCase switchCase = caseIterator.next(); 4645 SwitchCase switchCase = caseIterator.next();
4399 List<Constant> caseConstants = <Constant>[]; 4646 List<Constant> caseConstants = <Constant>[];
4400 HBasicBlock block = graph.addNewBlock(); 4647 HBasicBlock block = graph.addNewBlock();
4401 for (Node labelOrCase in switchCase.labelsAndCases) { 4648 for (Constant constant in getConstants(switchCase)) {
4402 if (labelOrCase is CaseMatch) { 4649 caseConstants.add(constant);
4403 Constant constant = constants[labelOrCase]; 4650 HConstant hConstant = graph.addConstant(constant);
4404 caseConstants.add(constant); 4651 switchInstruction.inputs.add(hConstant);
4405 HConstant hConstant = graph.addConstant(constant); 4652 hConstant.usedBy.add(switchInstruction);
4406 switchInstruction.inputs.add(hConstant); 4653 expressionBlock.addSuccessor(block);
4407 hConstant.usedBy.add(switchInstruction);
4408 expressionBlock.addSuccessor(block);
4409 }
4410 } 4654 }
4411 matchExpressions.add(caseConstants); 4655 matchExpressions.add(caseConstants);
4412 4656
4413 if (switchCase.isDefaultCase) { 4657 if (isDefaultCase(switchCase)) {
4414 // An HSwitch has n inputs and n+1 successors, the last being the 4658 // An HSwitch has n inputs and n+1 successors, the last being the
4415 // default case. 4659 // default case.
4416 expressionBlock.addSuccessor(block); 4660 expressionBlock.addSuccessor(block);
4417 hasDefault = true; 4661 hasDefault = true;
4418 } 4662 }
4419 open(block); 4663 open(block);
4420 localsHandler = new LocalsHandler.from(savedLocals); 4664 localsHandler = new LocalsHandler.from(savedLocals);
4421 visit(switchCase.statements); 4665 buildSwitchCase(switchCase);
4422 if (!isAborted() && caseIterator.hasNext) { 4666 if (!isAborted() && caseIterator.hasNext) {
4423 pushInvokeHelper0(getFallThroughErrorElement, HType.UNKNOWN); 4667 pushInvokeHelper0(getFallThroughErrorElement, HType.UNKNOWN);
4424 HInstruction error = pop(); 4668 HInstruction error = pop();
4425 closeAndGotoExit(new HThrow(error)); 4669 closeAndGotoExit(new HThrow(error));
4426 } 4670 }
4427 statements.add( 4671 statements.add(
4428 new HSubGraphBlockInformation(new SubGraph(block, lastOpenedBlock))); 4672 new HSubGraphBlockInformation(new SubGraph(block, lastOpenedBlock)));
4429 } 4673 }
4430 4674
4431 // Add a join-block if necessary. 4675 // Add a join-block if necessary.
4432 // We create [joinBlock] early, and then go through the cases that might 4676 // We create [joinBlock] early, and then go through the cases that might
4433 // want to jump to it. In each case, if we add [joinBlock] as a successor 4677 // want to jump to it. In each case, if we add [joinBlock] as a successor
4434 // of another block, we also add an element to [caseHandlers] that is used 4678 // of another block, we also add an element to [caseHandlers] that is used
4435 // to create the phis in [joinBlock]. 4679 // to create the phis in [joinBlock].
4436 // If we never jump to the join block, [caseHandlers] will stay empty, and 4680 // If we never jump to the join block, [caseHandlers] will stay empty, and
4437 // the join block is never added to the graph. 4681 // the join block is never added to the graph.
4438 HBasicBlock joinBlock = new HBasicBlock(); 4682 HBasicBlock joinBlock = new HBasicBlock();
4439 List<LocalsHandler> caseHandlers = <LocalsHandler>[]; 4683 List<LocalsHandler> caseHandlers = <LocalsHandler>[];
4440 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 4684 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
4441 instruction.block.addSuccessor(joinBlock); 4685 instruction.block.addSuccessor(joinBlock);
4442 caseHandlers.add(locals); 4686 caseHandlers.add(locals);
4443 }); 4687 });
4688 jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {
ngeoffray 2013/05/14 07:08:51 If that's a simple switch, those continues should
Johnni Winther 2013/05/17 07:03:04 It should not happen: If simple, no continue shoul
4689 instruction.block.addSuccessor(joinBlock);
4690 caseHandlers.add(locals);
4691 });
4444 if (!isAborted()) { 4692 if (!isAborted()) {
4445 current.close(new HGoto()); 4693 current.close(new HGoto());
4446 lastOpenedBlock.addSuccessor(joinBlock); 4694 lastOpenedBlock.addSuccessor(joinBlock);
4447 caseHandlers.add(localsHandler); 4695 caseHandlers.add(localsHandler);
4448 } 4696 }
4449 if (!hasDefault) { 4697 if (!hasDefault) {
4450 // The current flow is only aborted if the switch has a default that 4698 // The current flow is only aborted if the switch has a default that
4451 // aborts (all previous cases must abort, and if there is no default, 4699 // aborts (all previous cases must abort, and if there is no default,
4452 // it's possible to miss all the cases). 4700 // it's possible to miss all the cases).
4453 expressionEnd.addSuccessor(joinBlock); 4701 expressionEnd.addSuccessor(joinBlock);
(...skipping 19 matching lines...) Expand all
4473 expressionStart.setBlockFlow( 4721 expressionStart.setBlockFlow(
4474 new HSwitchBlockInformation(expressionInfo, 4722 new HSwitchBlockInformation(expressionInfo,
4475 matchExpressions, 4723 matchExpressions,
4476 statements, 4724 statements,
4477 hasDefault, 4725 hasDefault,
4478 jumpHandler.target, 4726 jumpHandler.target,
4479 jumpHandler.labels()), 4727 jumpHandler.labels()),
4480 joinBlock); 4728 joinBlock);
4481 4729
4482 jumpHandler.close(); 4730 jumpHandler.close();
4483 return true;
4484 } 4731 }
4485 4732
4486 bool nonPrimitiveTypeOverridesEquals(Constant constant) { 4733 bool nonPrimitiveTypeOverridesEquals(Constant constant) {
4487 // Function values override equals. Even static ones, since 4734 // Function values override equals. Even static ones, since
4488 // they inherit from [Function]. 4735 // they inherit from [Function].
4489 if (constant.isFunction()) return true; 4736 if (constant.isFunction()) return true;
4490 4737
4491 // [Map] and [List] do not override equals. 4738 // [Map] and [List] do not override equals.
4492 // If constant is primitive, just return false. We know 4739 // If constant is primitive, just return false. We know
4493 // about the equals methods of num/String classes. 4740 // about the equals methods of num/String classes.
(...skipping 19 matching lines...) Expand all
4513 } 4760 }
4514 4761
4515 Element lookupOperator(ClassElement classElement, SourceString operatorName) { 4762 Element lookupOperator(ClassElement classElement, SourceString operatorName) {
4516 SourceString dartMethodName = 4763 SourceString dartMethodName =
4517 Elements.constructOperatorName(operatorName, false); 4764 Elements.constructOperatorName(operatorName, false);
4518 return classElement.lookupMember(dartMethodName); 4765 return classElement.lookupMember(dartMethodName);
4519 } 4766 }
4520 4767
4521 4768
4522 // Recursively build an if/else structure to match the cases. 4769 // Recursively build an if/else structure to match the cases.
4523 void buildSwitchCases(Link<Node> cases, HInstruction expression, 4770 void buildSwitchCases(JumpHandler jumpHandler,
4771 Link<Node> cases, HInstruction expression,
4772 void buildSwitchCase(SwitchCase switchCase),
4524 [int encounteredCaseTypes = 0]) { 4773 [int encounteredCaseTypes = 0]) {
4525 final int NO_TYPE = 0; 4774 final int NO_TYPE = 0;
4526 final int INT_TYPE = 1; 4775 final int INT_TYPE = 1;
4527 final int STRING_TYPE = 2; 4776 final int STRING_TYPE = 2;
4528 final int CONFLICT_TYPE = 3; 4777 final int CONFLICT_TYPE = 3;
4529 int combine(int type1, int type2) => type1 | type2; 4778 int combine(int type1, int type2) => type1 | type2;
4530 4779
4531 SwitchCase node = cases.head; 4780 SwitchCase node = cases.head;
4532 // Called for the statements on all but the last case block. 4781 // Called for the statements on all but the last case block.
4533 // Ensures that a user expecting a fallthrough gets an error. 4782 // Ensures that a user expecting a fallthrough gets an error.
4534 void visitStatementsAndAbort() { 4783 void visitStatementsAndAbort() {
4535 visit(node.statements); 4784 buildSwitchCase(node);
4536 if (!isAborted()) { 4785 if (!isAborted()) {
4537 compiler.reportWarning(node, 'Missing break at end of switch case'); 4786 compiler.reportWarning(node, 'Missing break at end of switch case');
4538 Element element = 4787 Element element =
4539 compiler.findHelper(const SourceString("getFallThroughError")); 4788 compiler.findHelper(const SourceString("getFallThroughError"));
4540 pushInvokeHelper0(element, HType.UNKNOWN); 4789 pushInvokeHelper0(element, HType.UNKNOWN);
4541 HInstruction error = pop(); 4790 HInstruction error = pop();
4542 closeAndGotoExit(new HThrow(error)); 4791 closeAndGotoExit(new HThrow(error));
4543 } 4792 }
4544 } 4793 }
4545 4794
4546 Link<Node> skipLabels(Link<Node> labelsAndCases) { 4795 Link<Node> skipLabels(Link<Node> labelsAndCases) {
4547 while (!labelsAndCases.isEmpty && labelsAndCases.head is Label) { 4796 while (!labelsAndCases.isEmpty && labelsAndCases.head is Label) {
4548 labelsAndCases = labelsAndCases.tail; 4797 labelsAndCases = labelsAndCases.tail;
4549 } 4798 }
4550 return labelsAndCases; 4799 return labelsAndCases;
4551 } 4800 }
4552 4801
4553 Link<Node> labelsAndCases = skipLabels(node.labelsAndCases.nodes); 4802 Link<Node> labelsAndCases = skipLabels(node.labelsAndCases.nodes);
4554 if (labelsAndCases.isEmpty) { 4803 if (labelsAndCases.isEmpty) {
4555 // Default case with no expressions. 4804 // Default case with no expressions.
4556 if (!node.isDefaultCase) { 4805 if (!node.isDefaultCase) {
4557 compiler.internalError("Case with no expression and not default", 4806 compiler.internalError("Case with no expression and not default",
4558 node: node); 4807 node: node);
4559 } 4808 }
4560 visit(node.statements); 4809 buildSwitchCase(node);
4561 // This must be the final case (otherwise "default" would be invalid), 4810 // This must be the final case (otherwise "default" would be invalid),
4562 // so we don't need to check for fallthrough. 4811 // so we don't need to check for fallthrough.
4563 return; 4812 return;
4564 } 4813 }
4565 4814
4566 // Recursively build the test conditions. Leaves the result on the 4815 // Recursively build the test conditions. Leaves the result on the
4567 // expression stack. 4816 // expression stack.
4568 void buildTests(Link<Node> remainingCases) { 4817 void buildTests(Link<Node> remainingCases) {
4569 // Build comparison for one case expression. 4818 // Build comparison for one case expression.
4570 void left() { 4819 void left() {
(...skipping 27 matching lines...) Expand all
4598 } 4847 }
4599 4848
4600 if (node.isDefaultCase) { 4849 if (node.isDefaultCase) {
4601 // Default case must be last. 4850 // Default case must be last.
4602 assert(cases.tail.isEmpty); 4851 assert(cases.tail.isEmpty);
4603 // Perform the tests until one of them match, but then always execute the 4852 // Perform the tests until one of them match, but then always execute the
4604 // statements. 4853 // statements.
4605 // TODO(lrn): Stop performing tests when all expressions are compile-time 4854 // TODO(lrn): Stop performing tests when all expressions are compile-time
4606 // constant strings or integers. 4855 // constant strings or integers.
4607 handleIf(node, () { buildTests(labelsAndCases); }, (){}, null); 4856 handleIf(node, () { buildTests(labelsAndCases); }, (){}, null);
4608 visit(node.statements); 4857 buildSwitchCase(node);
4609 } else { 4858 } else {
4610 if (cases.tail.isEmpty) { 4859 if (cases.tail.isEmpty) {
4611 handleIf(node, 4860 handleIf(node,
4612 () { buildTests(labelsAndCases); }, 4861 () { buildTests(labelsAndCases); },
4613 () { visit(node.statements); }, 4862 () { buildSwitchCase(node); },
4614 null); 4863 null);
4615 } else { 4864 } else {
4616 handleIf(node, 4865 handleIf(node,
4617 () { buildTests(labelsAndCases); }, 4866 () { buildTests(labelsAndCases); },
4618 () { visitStatementsAndAbort(); }, 4867 () { visitStatementsAndAbort(); },
4619 () { buildSwitchCases(cases.tail, expression, 4868 () { buildSwitchCases(jumpHandler, cases.tail, expression,
4869 buildSwitchCase,
4620 encounteredCaseTypes); }); 4870 encounteredCaseTypes); });
4621 } 4871 }
4622 } 4872 }
4623 } 4873 }
4624 4874
4625 visitSwitchCase(SwitchCase node) { 4875 visitSwitchCase(SwitchCase node) {
4626 compiler.internalError('SsaBuilder.visitSwitchCase'); 4876 compiler.internalError('SsaBuilder.visitSwitchCase');
4627 } 4877 }
4628 4878
4629 visitCaseMatch(CaseMatch node) { 4879 visitCaseMatch(CaseMatch node) {
(...skipping 649 matching lines...) Expand 10 before | Expand all | Expand 10 after
5279 new HSubGraphBlockInformation(elseBranch.graph)); 5529 new HSubGraphBlockInformation(elseBranch.graph));
5280 5530
5281 HBasicBlock conditionStartBlock = conditionBranch.block; 5531 HBasicBlock conditionStartBlock = conditionBranch.block;
5282 conditionStartBlock.setBlockFlow(info, joinBlock); 5532 conditionStartBlock.setBlockFlow(info, joinBlock);
5283 SubGraph conditionGraph = conditionBranch.graph; 5533 SubGraph conditionGraph = conditionBranch.graph;
5284 HIf branch = conditionGraph.end.last; 5534 HIf branch = conditionGraph.end.last;
5285 assert(branch is HIf); 5535 assert(branch is HIf);
5286 branch.blockInformation = conditionStartBlock.blockFlow; 5536 branch.blockInformation = conditionStartBlock.blockFlow;
5287 } 5537 }
5288 } 5538 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698