Implement continue for switch.

sdk/lib/_internal/compiler/implementation/ssa/builder.dart

Index: sdk/lib/_internal/compiler/implementation/ssa/builder.dart
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/builder.dart b/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
index 487104cdabd11bc8281f7e5876f429521c42401d..2a4baf415a8f32dc1a765594c52c5ceec6fdd3dd 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
@@ -533,7 +533,7 @@ class LocalsHandler {
     }
   }
 
-  void enterLoopUpdates(Loop node) {
+  void enterLoopUpdates(Node node) {
     // If there are declared boxed loop variables then the updates might have
     // access to the box and we must switch to a new box before executing the
     // updates.
@@ -736,6 +736,9 @@ class TargetJumpHandler implements JumpHandler {
       continueInstruction = new HContinue(target);
     } else {
       continueInstruction = new HContinue.toLabel(label);
+      // Switch case continue statements must be handled by the
+      // [SwitchCaseJumpHandler].
+      assert(label.target.statement is! SwitchCase);
     }
     LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
     builder.close(continueInstruction);
@@ -783,6 +786,86 @@ class TargetJumpHandler implements JumpHandler {
   }
 }
 
+/// Special [JumpHandler] implementation used to handle continue statements
+/// targeting switch cases.
+class SwitchCaseJumpHandler extends TargetJumpHandler {
+  /// Map from switch case targets to indices used to encode the flow of the
+  /// switch case loop.
+  final Map<TargetElement, int> targetIndexMap = new Map<TargetElement, int>();
+
+  SwitchCaseJumpHandler(SsaBuilder builder,
+                        TargetElement target,
+                        SwitchStatement node)
+      : super(builder, target) {
+    // The switch case indices must match those computed in
+    // [SsaBuilder.visitSwitchStatement].
+    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.

+    for (SwitchCase switchCase in node.cases) {
+      for (Node labelOrCase in switchCase.labelsAndCases) {
+        Node label = labelOrCase.asLabel();
+        if (label != null) {
+          LabelElement labelElement = builder.elements[label];
+          if (labelElement != null) {
+            if (labelElement.isContinueTarget) {

[ngeoffray, 2013/05/14 07:08:51]

I prever avoiding nested if and do if (labelElement != null &&
labelElement.isContinueTarget).

[Johnni Winther, 2013/05/17 07:03:04]

Done.

+              TargetElement continueTarget = labelElement.target;
+              targetIndexMap[continueTarget] = switchIndex;
+              assert(builder.jumpTargets[continueTarget] == null);
+              builder.jumpTargets[continueTarget] = this;
+            }
+          }
+        }
+      }
+      switchIndex++;
+    }
+  }
+
+  void generateBreak([LabelElement label]) {
+    if (label == null) {
+      // Creates a special break instruction for the synthetic loop generated
+      // for a switch statement with continue statements. See
+      // [SsaBuilder.visitSwitchStatement] for detail.
+
+      HInstruction breakInstruction =
+          new HBreak(target, breakSwitchContinueLoop: true);
+      LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
+      builder.close(breakInstruction);
+      jumps.add(new JumpHandlerEntry(breakInstruction, locals));
+    } else {
+      super.generateBreak(label);
+    }
+  }
+
+  void generateContinue([LabelElement label]) {
+    if (label != null && targetIndexMap.containsKey(label.target)) {

[ngeoffray, 2013/05/14 07:08:51]

It would read nicer with a helper method whose name explains what it means: if
(isContinueToSwithCase(label)) {...

[Johnni Winther, 2013/05/17 07:03:04]

Done.

+      // Creates the special instructions 'label = i; continue l;' used in
+      // switch statements with continue statements. See
+      // [SsaBuilder.visitSwitchStatement] for detail.
+
+      assert(label != null);
+      HInstruction value = builder.graph.addConstantInt(
+          targetIndexMap[label.target],
+          builder.constantSystem);
+      builder.localsHandler.updateLocal(target, value);
+
+      assert(label.target.labels.contains(label));
+      HInstruction continueInstruction = new HContinue(target);
+      LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
+      builder.close(continueInstruction);
+      jumps.add(new JumpHandlerEntry(continueInstruction, locals));
+    } else {
+      super.generateContinue(label);
+    }
+  }
+
+  void close() {
+    // The mapping from TargetElement to JumpHandler is no longer needed.
+    for (TargetElement target in targetIndexMap.keys) {
+      builder.jumpTargets.remove(target);
+    }
+    super.close();
+  }
+}
+
 class SsaBuilder extends ResolvedVisitor implements Visitor {
   final SsaBuilderTask builder;
   final JavaScriptBackend backend;
@@ -1888,7 +1971,7 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
     assert(!isAborted());
     HBasicBlock previousBlock = close(new HGoto());
 
-    JumpHandler jumpHandler = createJumpHandler(node);
+    JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: true);
     HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(
         jumpHandler.target,
         jumpHandler.labels());
@@ -4127,13 +4210,22 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
    * Creates a [JumpHandler] for a statement. The node must be a jump
    * target. If there are no breaks or continues targeting the statement,
    * a special "null handler" is returned.
+   *
+   * [isLoopJump] is [:true:] when the jump handler is for a loop. This is used
+   * to distinguish the synthetized loop created for a switch statement with
+   * continue statements from simple switch statements.
    */
-  JumpHandler createJumpHandler(Statement node) {
+  JumpHandler createJumpHandler(Statement node, {bool isLoopJump}) {
     TargetElement element = elements[node];
     if (element == null || !identical(element.statement, node)) {
       // No breaks or continues to this node.
       return new NullJumpHandler(compiler);
     }
+    if (isLoopJump && node is SwitchStatement) {
+      // Create a special jump handler for loops created for switch statements
+      // with continue statements.
+      return new SwitchCaseJumpHandler(this, element, node);
+    }
     return new JumpHandler(this, element);
   }
 
@@ -4273,8 +4365,129 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
   }
 
   visitSwitchStatement(SwitchStatement node) {
-    if (tryBuildConstantSwitch(node)) return;
+    // The switch case indices must match those computed in
+    // [SwitchCaseJumpHandler].
+    bool hasContinue = false;
+    Map<SwitchCase, int> caseIndex = new Map<SwitchCase, int>();
+    int switchIndex = 1;
+    bool hasDefault = false;
+    for (SwitchCase switchCase in node.cases) {
+      for (Node labelOrCase in switchCase.labelsAndCases) {
+        Node label = labelOrCase.asLabel();
+        if (label != null) {
+          LabelElement labelElement = elements[label];
+          if (labelElement != null && labelElement.isContinueTarget) {
+            hasContinue = true;
+          }
+        }
+      }
+      if (switchCase.isDefaultCase) {
+        hasDefault = true;
+      }
+      caseIndex[switchCase] = switchIndex;
+      switchIndex++;
+    }
+    if (!hasContinue) {
+      // If the switch statement has no switch cases targeted by continue
+      // statements we encode the switch statement directly.
+      void buildSwitchCase(SwitchCase node) {
+        visit(node.statements);
+      }
+      buildSwitchStatement(node, buildSwitchCase);
+    } else {
+      // If the switch statement has switch cases targeted by continue
+      // statements we create the following encoding:
+      //
+      //   switch (e) {
+      //     l_1: case e0: s_1; break;
+      //     l_2: case e1: s_2; continue l_i;
+      //     ...
+      //     l_n: default: s_n; continue l_j;
+      //   }
+      //
+      // is encoded as
+      //
+      //   var target;
+      //   switch (e) {
+      //     case e1: target = 1; break;
+      //     case e2: target = 2; break;
+      //     ...
+      //     default: target = n; break;
+      //   }
+      //   l: while (true) {
+      //    switch (target) {
+      //       case 1: s_1; break l;
+      //       case 2: s_2; target = i; continue l;
+      //       ...
+      //       case n: s_n; target = j; continue l;
+      //     }
+      //   }
+
+      TargetElement switchTarget = elements[node];
+      HInstruction initialValue = graph.addConstantNull(constantSystem);
+      localsHandler.updateLocal(switchTarget, initialValue);
+      void buildSwitchCase(SwitchCase switchCase) {
+        // Generate 'target = i; break;' for switch case i.
+        int index = caseIndex[switchCase];
+        HInstruction value = graph.addConstantInt(index, constantSystem);
+        localsHandler.updateLocal(switchTarget, value);
+        jumpTargets[switchTarget].generateBreak();
+      }
+      buildSwitchStatement(node, buildSwitchCase);
+
+      HInstruction buildCondition() =>
+          graph.addConstantBool(true, constantSystem);
 
+      void buildSwitch() {
+        HInstruction buildExpression() {
+          return localsHandler.readLocal(switchTarget);
+        }
+        Iterable<Constant> getConstants(SwitchCase switchCase) {
+          return <Constant>[constantSystem.createInt(caseIndex[switchCase])];
+        }
+        void buildSwitchCase(SwitchCase switchCase) {
+          visit(switchCase.statements);
+          if (!isAborted()) {
+            // Ensure that we break the loop if the case falls through. (This
+            // is only possible for the last case.)
+            jumpTargets[switchTarget].generateBreak();
+          }
+        }
+        // Pass a [NullJumpHandler] because the target for the contained break
+        // is not the generated switch statement but instead the loop generated
+        // in the call to [handleLoop] below.
+        handleSwitch(
+            new NullJumpHandler(compiler),
+            buildExpression, node, getConstants,
+            (_) => false, // No case is default.
+            buildSwitchCase);
+      }
+
+      void buildLoop() {
+        handleLoop(node,
+            () {},
+            buildCondition,
+            () {},
+            buildSwitch);
+      }
+
+      if (hasDefault) {
+        buildLoop();
+      } else {
+        // If the switch statement has no default case, surround the loop with
+        // a test of the target.
+        void buildCondition() {
+          push(createForeign('#', HType.BOOLEAN,
+                             [localsHandler.readLocal(switchTarget)]));
+        }
+        handleIf(node, buildCondition, buildLoop, () => {});
+      }
+    }
+  }
+
+  buildSwitchStatement(SwitchStatement node,
+                       void buildSwitchCase(SwitchCase switchCase)) {
+    if (tryBuildConstantSwitch(node, buildSwitchCase)) return;
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
     HBasicBlock startBlock = openNewBlock();
     visit(node.expression);
@@ -4284,9 +4497,9 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
     }
 
     Link<Node> cases = node.cases.nodes;
-    JumpHandler jumpHandler = createJumpHandler(node);
+    JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: false);
 
-    buildSwitchCases(cases, expression);
+    buildSwitchCases(jumpHandler, cases, expression, buildSwitchCase);
 
     HBasicBlock lastBlock = lastOpenedBlock;
 
@@ -4324,7 +4537,8 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
     jumpHandler.close();
   }
 
-  bool tryBuildConstantSwitch(SwitchStatement node) {
+  bool tryBuildConstantSwitch(SwitchStatement node,
+                              void buildSwitchCase(SwitchCase switchCase)) {
     Map<CaseMatch, Constant> constants = new Map<CaseMatch, Constant>();
     // First check whether all case expressions are compile-time constants,
     // and all have the same type that doesn't override operator==.
@@ -4362,9 +4576,6 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
             }
           }
           constants[labelOrCase] = constant;
-        } else {
-          compiler.reportWarning(node, "Unsupported: Labels on cases");
-          failure = true;
         }
       }
     }
@@ -4372,20 +4583,56 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
       return false;
     }
 
+    JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: false);
+    HInstruction buildExpression() {
+      visit(node.expression);
+      return pop();
+    }
+    Iterable<Constant> getConstants(SwitchCase switchCase) {
+      List<Constant> constantList = <Constant>[];
+      for (Node labelOrCase in switchCase.labelsAndCases) {
+        if (labelOrCase is CaseMatch) {
+          constantList.add(constants[labelOrCase]);
+        }
+      }
+      return constantList;
+    }
+    handleSwitch(jumpHandler, buildExpression, node,
+                 getConstants,
+                 (SwitchCase switchCase) => switchCase.isDefaultCase,
+                 buildSwitchCase);
+    jumpHandler.close();
+    return true;
+  }
+
+  /**
+   * 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.

+   *
+   * [jumpHandler] is the [JumpHandler] for the created switch statement.
+   * [buildExpression] creates the switch expression.
+   * [getConstants] returns the set of constants for a switch case.
+   * [buildSwitchCase] creates the statements for the switch case.
+   */
+  void handleSwitch(JumpHandler jumpHandler,
+                    HInstruction buildExpression(),
+                    SwitchStatement node,
+                    Iterable<Constant> getConstants(SwitchCase switchCase),
+                    bool isDefaultCase(SwitchCase switchCase),
+                    void buildSwitchCase(SwitchCase switchCase)) {
+    Map<CaseMatch, Constant> constants = new Map<CaseMatch, Constant>();
+
     // TODO(ngeoffray): Handle switch-instruction in bailout code.
     work.allowSpeculativeOptimization = false;
     // Then build a switch structure.
     HBasicBlock expressionStart = openNewBlock();
-    visit(node.expression);
-    HInstruction expression = pop();
+    HInstruction expression = buildExpression();
     if (node.cases.isEmpty) {
-      return true;
+      return;
     }
     HBasicBlock expressionEnd = current;
 
     HSwitch switchInstruction = new HSwitch(<HInstruction>[expression]);
     HBasicBlock expressionBlock = close(switchInstruction);
-    JumpHandler jumpHandler = createJumpHandler(node);
     LocalsHandler savedLocals = localsHandler;
 
     List<List<Constant>> matchExpressions = <List<Constant>>[];
@@ -4398,19 +4645,16 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
       SwitchCase switchCase = caseIterator.next();
       List<Constant> caseConstants = <Constant>[];
       HBasicBlock block = graph.addNewBlock();
-      for (Node labelOrCase in switchCase.labelsAndCases) {
-        if (labelOrCase is CaseMatch) {
-          Constant constant = constants[labelOrCase];
-          caseConstants.add(constant);
-          HConstant hConstant = graph.addConstant(constant);
-          switchInstruction.inputs.add(hConstant);
-          hConstant.usedBy.add(switchInstruction);
-          expressionBlock.addSuccessor(block);
-        }
+      for (Constant constant in getConstants(switchCase)) {
+        caseConstants.add(constant);
+        HConstant hConstant = graph.addConstant(constant);
+        switchInstruction.inputs.add(hConstant);
+        hConstant.usedBy.add(switchInstruction);
+        expressionBlock.addSuccessor(block);
       }
       matchExpressions.add(caseConstants);
 
-      if (switchCase.isDefaultCase) {
+      if (isDefaultCase(switchCase)) {
         // An HSwitch has n inputs and n+1 successors, the last being the
         // default case.
         expressionBlock.addSuccessor(block);
@@ -4418,7 +4662,7 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
       }
       open(block);
       localsHandler = new LocalsHandler.from(savedLocals);
-      visit(switchCase.statements);
+      buildSwitchCase(switchCase);
       if (!isAborted() && caseIterator.hasNext) {
         pushInvokeHelper0(getFallThroughErrorElement, HType.UNKNOWN);
         HInstruction error = pop();
@@ -4441,6 +4685,10 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
       instruction.block.addSuccessor(joinBlock);
       caseHandlers.add(locals);
     });
+    jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {

[ngeoffray, 2013/05/14 07:08:51]

If that's a simple switch, those continues should be to something out of the
switch right?

[Johnni Winther, 2013/05/17 07:03:04]

It should not happen: If simple, no continue should target [jumpHandler]. If
complex, the jump handler should have no targets.

Inserted an assertion instead.

+      instruction.block.addSuccessor(joinBlock);
+      caseHandlers.add(locals);
+    });
     if (!isAborted()) {
       current.close(new HGoto());
       lastOpenedBlock.addSuccessor(joinBlock);
@@ -4480,7 +4728,6 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
         joinBlock);
 
     jumpHandler.close();
-    return true;
   }
 
   bool nonPrimitiveTypeOverridesEquals(Constant constant) {
@@ -4520,7 +4767,9 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
 
 
   // Recursively build an if/else structure to match the cases.
-  void buildSwitchCases(Link<Node> cases, HInstruction expression,
+  void buildSwitchCases(JumpHandler jumpHandler,
+                        Link<Node> cases, HInstruction expression,
+                        void buildSwitchCase(SwitchCase switchCase),
                         [int encounteredCaseTypes = 0]) {
     final int NO_TYPE = 0;
     final int INT_TYPE = 1;
@@ -4532,7 +4781,7 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
     // Called for the statements on all but the last case block.
     // Ensures that a user expecting a fallthrough gets an error.
     void visitStatementsAndAbort() {
-      visit(node.statements);
+      buildSwitchCase(node);
       if (!isAborted()) {
         compiler.reportWarning(node, 'Missing break at end of switch case');
         Element element =
@@ -4557,7 +4806,7 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
         compiler.internalError("Case with no expression and not default",
                                node: node);
       }
-      visit(node.statements);
+      buildSwitchCase(node);
       // This must be the final case (otherwise "default" would be invalid),
       // so we don't need to check for fallthrough.
       return;
@@ -4605,18 +4854,19 @@ class SsaBuilder extends ResolvedVisitor implements Visitor {
       // TODO(lrn): Stop performing tests when all expressions are compile-time
       // constant strings or integers.
       handleIf(node, () { buildTests(labelsAndCases); }, (){}, null);
-      visit(node.statements);
+      buildSwitchCase(node);
     } else {
       if (cases.tail.isEmpty) {
         handleIf(node,
                  () { buildTests(labelsAndCases); },
-                 () { visit(node.statements); },
+                 () { buildSwitchCase(node); },
                  null);
       } else {
         handleIf(node,
                  () { buildTests(labelsAndCases); },
                  () { visitStatementsAndAbort(); },
-                 () { buildSwitchCases(cases.tail, expression,
+                 () { buildSwitchCases(jumpHandler, cases.tail, expression,
+                                       buildSwitchCase,
                                        encounteredCaseTypes); });
       }
     }