Implement complex switch statement (switch with continue).

pkg/compiler/lib/src/ssa/builder_kernel.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import 'package:kernel/ast.dart' as ir;
 
 import '../closure.dart';
 import '../common.dart';
 import '../common/codegen.dart' show CodegenRegistry, CodegenWorkItem;
 import '../common/names.dart';
@@ skipping 1125 matching lines @@
   /// to distinguish the synthesized loop created for a switch statement with
   /// continue statements from simple switch statements.
   JumpHandler createJumpHandler(ir.TreeNode node, {bool isLoopJump: false}) {
     JumpTarget target = astAdapter.getJumpTarget(node);
     assert(target is KernelJumpTarget);
     if (target == null) {
       // No breaks or continues to this node.
       return new NullJumpHandler(compiler.reporter);
     }
     if (isLoopJump && node is ir.SwitchStatement) {
-      throw 'Kernel Switch Statement handler not yet implemented.';
+      return new KernelSwitchCaseJumpHandler(this, target, node, astAdapter);
     }
 
     return new JumpHandler(this, target);
   }
 
   @override
   void visitBreakStatement(ir.BreakStatement breakStatement) {
     assert(!isAborted());
     handleInTryStatement();
     JumpTarget target = astAdapter.getJumpTarget(breakStatement.target);
@@ skipping 72 matching lines @@
     JumpTarget target = astAdapter.getJumpTarget(switchStatement.target);
     assert(target != null);
     JumpHandler handler = jumpTargets[target];
     assert(handler != null);
     assert(target.labels.isNotEmpty);
     handler.generateContinue(target.labels.first);
   }
 
   @override
   void visitSwitchStatement(ir.SwitchStatement switchStatement) {
-    Map<ir.Expression, ConstantValue> constants =
-        _buildSwitchCaseConstants(switchStatement);
-
     // The switch case indices must match those computed in
     // [KernelSwitchCaseJumpHandler].
     bool hasContinue = false;
     Map<ir.SwitchCase, int> caseIndex = new Map<ir.SwitchCase, int>();
     int switchIndex = 1;
     bool hasDefault = false;
     for (ir.SwitchCase switchCase in switchStatement.cases) {
       if (SwitchContinueAnalysis.containsContinue(switchCase.body)) {
         hasContinue = true;
       }
       if (switchCase.isDefault) {
         hasDefault = true;
       }
       caseIndex[switchCase] = switchIndex;
       switchIndex++;
     }
 
     JumpHandler jumpHandler = createJumpHandler(switchStatement);
     if (!hasContinue) {
       // If the switch statement has no switch cases targeted by continue
       // statements we encode the switch statement directly.
-      _buildSimpleSwitchStatement(switchStatement, jumpHandler, constants);
+      _buildSimpleSwitchStatement(switchStatement, jumpHandler);
     } else {
-      throw 'Complex switch statement with continue label not implemented yet.';
+      _buildComplexSwitchStatement(
+          switchStatement, jumpHandler, caseIndex, hasDefault);
     }
   }
 
   /// Helper for building switch statements.
   static bool _isDefaultCase(ir.SwitchCase switchCase) =>
       switchCase == null || switchCase.isDefault;
 
+  /// Helper for building switch statements.
+  HInstruction _buildExpression(ir.SwitchStatement switchStatement) {
+    switchStatement.expression.accept(this);
+    return pop();
+  }
+
+  /// Helper method for creating the list of constants that make up the
+  /// switch case branches.
+  List<ConstantValue> _getSwitchConstants(
+      ir.SwitchStatement parentSwitch, ir.SwitchCase switchCase) {
+    Map<ir.Expression, ConstantValue> constantsLookup =
+        _buildSwitchCaseConstants(parentSwitch);
+    List<ConstantValue> constantList = <ConstantValue>[];
+    if (switchCase != null) {
+      for (var expression in switchCase.expressions) {
+        constantList.add(constantsLookup[expression]);
+      }
+    }
+    return constantList;
+  }
+
   /// Builds a simple switch statement which does not handle uses of continue
   /// statements to labeled switch cases.
-  void _buildSimpleSwitchStatement(ir.SwitchStatement switchStatement,
-      JumpHandler jumpHandler, Map<ir.Expression, ConstantValue> constants) {
+  void _buildSimpleSwitchStatement(
+      ir.SwitchStatement switchStatement, JumpHandler jumpHandler) {
     void buildSwitchCase(ir.SwitchCase switchCase) {
       switchCase.body.accept(this);
     }
 
-    handleSwitch(switchStatement, jumpHandler, switchStatement.cases,
-        _isDefaultCase, buildSwitchCase, constants);
+    _handleSwitch(
+        switchStatement,
+        jumpHandler,
+        _buildExpression,
+        switchStatement.cases,
+        _getSwitchConstants,
+        _isDefaultCase,
+        buildSwitchCase);
     jumpHandler.close();
   }
 
+  /// Builds a switch statement that can handle arbitrary uses of continue
+  /// statements to labeled switch cases.
+  void _buildComplexSwitchStatement(
+      ir.SwitchStatement switchStatement,
+      JumpHandler jumpHandler,
+      Map<ir.SwitchCase, int> caseIndex,
+      bool hasDefault) {
+    // 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;
+    //     }
+    //   }
+    //
+    // This is because JS does not have this same "continue label" semantics so
+    // we encode it in the form of a state machine.
+
+    JumpTarget switchTarget = astAdapter.getJumpTarget(switchStatement.parent);
+    localsHandler.updateLocal(switchTarget, graph.addConstantNull(closedWorld));
+
+    var switchCases = switchStatement.cases;
+    if (!hasDefault) {
+      // Use null as the marker for a synthetic default clause.
+      // The synthetic default is added because otherwise there would be no
+      // good place to give a default value to the local.
+      switchCases = new List<ir.SwitchCase>.from(switchCases);
+      switchCases.add(null);
+    }
+
+    void buildSwitchCase(ir.SwitchCase switchCase) {
+      if (switchCase != null) {
+        // Generate 'target = i; break;' for switch case i.
+        int index = caseIndex[switchCase];
+        HInstruction value = graph.addConstantInt(index, closedWorld);
+        localsHandler.updateLocal(switchTarget, value);
+      } else {
+        // Generate synthetic default case 'target = null; break;'.
+        HInstruction nullValue = graph.addConstantNull(closedWorld);
+        localsHandler.updateLocal(switchTarget, nullValue);
+      }
+      jumpTargets[switchTarget].generateBreak();
+    }
+
+    _handleSwitch(switchStatement, jumpHandler, _buildExpression, switchCases,
+        _getSwitchConstants, _isDefaultCase, buildSwitchCase);
+    jumpHandler.close();
+
+    HInstruction buildCondition() => graph.addConstantBool(true, closedWorld);
+
+    void buildSwitch() {
+      HInstruction buildExpression(ir.SwitchStatement notUsed) {
+        return localsHandler.readLocal(switchTarget);
+      }
+
+      List<ConstantValue> getConstants(
+          ir.SwitchStatement parentSwitch, ir.SwitchCase switchCase) {
+        return <ConstantValue>[
+          backend.constantSystem.createInt(caseIndex[switchCase])
+        ];
+      }
+
+      void buildSwitchCase(ir.SwitchCase switchCase) {
+        switchCase.body.accept(this);
+        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(
+          switchStatement, // nor is buildExpression.
+          new NullJumpHandler(compiler.reporter),
+          buildExpression,
+          switchStatement.cases,
+          getConstants,
+          (_) => false, // No case is default.
+          buildSwitchCase);
+    }
+
+    void buildLoop() {
+      loopHandler.handleLoop(
+          switchStatement, () {}, buildCondition, () {}, buildSwitch);
+    }
+
+    if (hasDefault) {
+      buildLoop();
+    } else {
+      // If the switch statement has no default case, surround the loop with
+      // a test of the target. So:
+      // `if (target) while (true) ...` If there's no default case, target is
+      // null, so we don't drop into the while loop.
+      void buildCondition() {
+        js.Template code = js.js.parseForeignJS('#');
+        push(new HForeignCode(
+            code, commonMasks.boolType, [localsHandler.readLocal(switchTarget)],
+            nativeBehavior: native.NativeBehavior.PURE));
+      }
+
+      handleIf(
+          node: switchStatement,
+          visitCondition: buildCondition,
+          visitThen: buildLoop,
+          visitElse: () => {});
+    }
+  }
+
   /// Creates a switch statement.
   ///
   /// [jumpHandler] is the [JumpHandler] for the created switch statement.
   /// [buildSwitchCase] creates the statements for the switch case.
-  void handleSwitch(
+  void _handleSwitch(
       ir.SwitchStatement switchStatement,
       JumpHandler jumpHandler,
+      HInstruction buildExpression(ir.SwitchStatement statement),
       List<ir.SwitchCase> switchCases,
+      List<ConstantValue> getConstants(
+          ir.SwitchStatement parentSwitch, ir.SwitchCase switchCase),
       bool isDefaultCase(ir.SwitchCase switchCase),
-      void buildSwitchCase(ir.SwitchCase switchCase),
-      Map<ir.Expression, ConstantValue> constantsLookup) {
+      void buildSwitchCase(ir.SwitchCase switchCase)) {
     HBasicBlock expressionStart = openNewBlock();
-    switchStatement.expression.accept(this);
-    HInstruction expression = pop();
-
-    List<ConstantValue> getConstants(ir.SwitchCase switchCase) {
-      List<ConstantValue> constantList = <ConstantValue>[];
-      if (switchCase != null) {
-        for (var expression in switchCase.expressions) {
-          constantList.add(constantsLookup[expression]);
-        }
-      }
-      return constantList;
-    }
+    HInstruction expression = buildExpression(switchStatement);
 
     if (switchCases.isEmpty) {
       return;
     }
 
     HSwitch switchInstruction = new HSwitch(<HInstruction>[expression]);
     HBasicBlock expressionEnd = close(switchInstruction);
     LocalsHandler savedLocals = localsHandler;
 
     List<HStatementInformation> statements = <HStatementInformation>[];
     bool hasDefault = false;
     for (ir.SwitchCase switchCase in switchCases) {
       HBasicBlock block = graph.addNewBlock();
-      for (ConstantValue constant in getConstants(switchCase)) {
+      for (ConstantValue constant
+          in getConstants(switchStatement, switchCase)) {
         HConstant hConstant = graph.addConstant(constant, closedWorld);
         switchInstruction.inputs.add(hConstant);
         hConstant.usedBy.add(switchInstruction);
         expressionEnd.addSuccessor(block);
       }
 
       if (isDefaultCase(switchCase)) {
         // An HSwitch has n inputs and n+1 successors, the last being the
         // default case.
         expressionEnd.addSuccessor(block);
@@ skipping 1545 matching lines @@
     enterBlock.setBlockFlow(
         new HTryBlockInformation(
             kernelBuilder.wrapStatementGraph(bodyGraph),
             exception,
             kernelBuilder.wrapStatementGraph(catchGraph),
             kernelBuilder.wrapStatementGraph(finallyGraph)),
         exitBlock);
     kernelBuilder.inTryStatement = previouslyInTryStatement;
   }
 }