Switch-implementation.

frog/leg/ssa/builder.dart

Index: frog/leg/ssa/builder.dart
diff --git a/frog/leg/ssa/builder.dart b/frog/leg/ssa/builder.dart
index 152355ae1b21381f03419eb18a99923af657407c..f0c4eab397567b67924b16333d67056c69a4534c 100644
--- a/frog/leg/ssa/builder.dart
+++ b/frog/leg/ssa/builder.dart
@@ -620,7 +620,7 @@ interface BreakHandler default BreakHandlerImpl {
   void addBreak(HBreak breakInstruction);
   void forEachBreak(Function action);
   void close();
-  List<SourceString> labels();
+  List<LabelElement> labels();
 }
 
 // Inert break handler used to avoid null checks when a loop isn't
@@ -631,7 +631,7 @@ class NullBreakHandler implements BreakHandler {
   void addBreak(HBreak breakInstruction) { unreachable(); }
   void forEachBreak(Function ignored) { }
   void close() { }
-  List<SourceString> labels() => const <SourceString>[];
+  List<LabelElement> labels() => const <LabelElement>[];
 }
 
 // Records breaks until a target block is available.
@@ -668,15 +668,15 @@ class BreakHandlerImpl implements BreakHandler {
     builder.currentBreakHandler = previous;
   }
 
-  List<SourceString> labels() {
-    List<SourceString> result = null;
+  List<LabelElement> labels() {
+    List<LabelElement> result = null;
     for (LabelElement element in target.labels) {
       if (element.isBreakTarget) {
-        if (result === null) result = <SourceString>[];
-        result.add(element.label.source);
+        if (result === null) result = <LabelElement>[];
+        result.add(element);
       }
     }
-    return (result === null) ? const <SourceString>[] : result;
+    return (result === null) ? const <LabelElement>[] : result;
   }
 }
 
@@ -706,9 +706,6 @@ class SsaBuilder implements Visitor {
   // Linked list of active break-handlers. Will be removed in the order
   // they are added.
   BreakHandler currentBreakHandler = const NullBreakHandler();
-  // The break handler to use for an upcoming loop statement (temporarily set
-  // if a labeled statement is labeling a loop).
-  BreakHandler loopBreakHandler = null;
 
   SsaBuilder(Compiler compiler, WorkItem work)
     : this.compiler = compiler,
@@ -1007,7 +1004,7 @@ class SsaBuilder implements Visitor {
   BreakHandler beginLoopHeader(Node node) {
     assert(!isAborted());
     HBasicBlock previousBlock = close(new HGoto());
-    BreakHandler breakHandler = getLoopBreakHandler(node);
+    BreakHandler breakHandler = getBreakHandler(node);
     HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels());
     previousBlock.addSuccessor(loopEntry);
     open(loopEntry);
@@ -1329,7 +1326,7 @@ class SsaBuilder implements Visitor {
       if (folded !== null) {
         stack.add(graph.addConstant(folded));
         return;
-      }      
+      }
     }
     HInstruction target =
         new HStatic(interceptors.getPrefixOperatorInterceptor(op));
@@ -1644,7 +1641,7 @@ class SsaBuilder implements Visitor {
           list.add(namedArguments[foundIndex]);
         } else {
           Constant constant = compiler.compileVariable(parameter);
-          list.add(graph.addConstant(constant)); 
+          list.add(graph.addConstant(constant));
         }
       }
     }
@@ -2111,8 +2108,9 @@ class SsaBuilder implements Visitor {
     HBreak breakInstruction;
     if (node.target === null) {
       breakInstruction = new HBreak();
-    }  else {
-      breakInstruction = new HBreak(node.target.source);
+    } else {
+      LabelElement label = elements[node.target];
+      breakInstruction = new HBreak(label);
     }
     close(breakInstruction);
     handler.addBreak(breakInstruction, savedLocals);
@@ -2124,18 +2122,10 @@ class SsaBuilder implements Visitor {
     generateUnimplemented('continue not implemented');
   }
 
-  BreakHandler getLoopBreakHandler(Node node) {
+  BreakHandler getBreakHandler(Node node) {
     StatementElement element = elements[node];
-    BreakHandler handler;
-    if (loopBreakHandler === null) {
-      if (element === null) return const NullBreakHandler();
-      handler = new BreakHandler(this, element);
-    } else {
-      handler = loopBreakHandler;
-      loopBreakHandler = null;
-      if (element === null) return handler;
-    }
-    return handler;
+    if (element === null) return const NullBreakHandler();
+    return new BreakHandler(this, element);
   }
 
   visitForInStatement(ForInStatement node) {
@@ -2297,61 +2287,123 @@ class SsaBuilder implements Visitor {
 
   visitSwitchStatement(SwitchStatement node) {
     work.allowSpeculativeOptimization = false;
+    LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
     visit(node.expression);
     HInstruction expression = pop();
+    if (node.cases.isEmpty()) {
+      return;
+    }
     Link<Node> cases = node.cases.nodes;
-    int count = 0;
-    handleThen() {
-      if (cases.head.statements.nodes.isEmpty()) {
-        compiler.unimplemented('fall-through', node: cases.head);
+    Element equalsHelper = interceptors.getEqualsInterceptor();
+    HInstruction target = new HStatic(equalsHelper);
+    add(target);
+
+    BreakHandler breakHandler = getBreakHandler(node);
+
+    void buildCompare(Expression caseExpression) {
+      visit(caseExpression);
+      push(new HEquals(target, pop(), expression));
+    }
+    buildSwitchCases(cases, buildCompare);
+
+    // Create merge block for break targets.
+    HBasicBlock joinBlock = new HBasicBlock();
+    List<LocalsHandler> caseLocals = <LocalsHandler>[];
+    breakHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
+      instruction.block.addSuccessor(joinBlock);
+      caseLocals.add(locals);
+    });
+    if (caseLocals.length == 0) return;
+    if (!isAborted()) {
+      caseLocals.add(localsHandler);
+      goto(current, joinBlock);
+    }
+    graph.addBlock(joinBlock);
+    open(joinBlock);
+    if (caseLocals.length == 1) {
+      localsHandler = caseLocals[0];
+    } else {
+      localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
+    }
+  }
+
+
+  // Recursively build an if/else structure to match the cases.
+  buildSwitchCases(Link<Node> cases, Function buildCompare) {
+    SwitchCase node = cases.head;
+    // TODO(lrn): Handle labels and continues.
+
+    void visitStatementsAndAbort() {
+      visit(node.statements);
+      if (!isAborted()) {
+        compiler.cancel('Missing break at end of switch case', node: node);
+        HBreak breakInstruction = new HBreak();
+        close(breakInstruction);
+        currentBreakHandler.addBreak(breakInstruction, localsHandler);
       }
-      visit(cases.head.statements);
-      cases = cases.tail;
-    }
-    handleElse() {
-      if (cases.isEmpty()) return;
-      if (cases.head.asDefaultCase() !== null) {
-        stack.add(graph.addConstantBool(true));
-        if (!cases.tail.isEmpty()) {
-          compiler.unimplemented('default case not last', node: cases.head);
-        }
-      } else {
-        SwitchCase switchCase = cases.head;
-        visit(switchCase.expression);
-        HInstruction caseExpression = pop();
-        Element equalsHelper = interceptors.getEqualsInterceptor();
-        HInstruction target = new HStatic(equalsHelper);
-        add(target);
-        push(new HEquals(target, caseExpression, expression));
+    }
+
+    Link<Node> expressions = node.expressions.nodes;
+    if (expressions.isEmpty()) {
+      // Default case with no expressions.
+      if (!node.isDefaultCase) {
+        compiler.internalError("Case with no expression and not default");
       }
-      handleIf(handleThen, handleElse);
+      visitStatementsAndAbort();
+      return;
     }
 
-    localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
-    HBasicBlock loopEntryBlock = current;
-    localsHandler.enterLoopBody(node);
+    // Recursively build the test conditions.
+    HInstruction buildTests(Link<Node> expressions, HInstruction left) {
+      // previous is a boolean instruction.

[floitsch, 2012/03/08 16:35:14]

P

[Lasse Reichstein Nielsen, 2012/03/08 18:35:40]

Whoops, 'previous'->'left'.

+      if (expressions.isEmpty()) return left;
+      push(new HNot(left));
 
-    handleElse();
+      HIf branch = new HIf(pop(), false);
+      HBasicBlock leftBlock = close(branch);
+      LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: node);
-    }
+      HBasicBlock rightBlock = addNewBlock();
+      leftBlock.addSuccessor(rightBlock);
+      open(rightBlock);
 
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
+      buildCompare(expressions.head);
+      HInstruction right = buildTests(expressions.tail, popBoolified());
 
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
+      SubGraph rightGraph = new SubGraph(rightBlock, current);
 
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
+      rightBlock = close(new HGoto());
+      HBasicBlock joinBlock = addNewBlock();
+      leftBlock.addSuccessor(joinBlock);
+      rightBlock.addSuccessor(joinBlock);
+      open(joinBlock);
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler);
+      branch.blockInformation =
+          new HIfBlockInformation(branch, rightGraph, null, joinBlock);
+
+      localsHandler.mergeWith(savedLocals, joinBlock);
+      HPhi result = new HPhi.manyInputs(null, [left, right]);
+      joinBlock.addPhi(result);
+      return result;
+    }
+
+    buildCompare(expressions.head);
+    HInstruction result = buildTests(expressions.tail, popBoolified());
+
+    if (node.isDefaultCase) {
+      // Don't actually use the condition result.
+      visitStatementsAndAbort();
+    } else {
+      stack.add(result);
+      handleIf(() { visitStatementsAndAbort(); },
+               cases.tail.isEmpty() ?
+                   null :
+                   () { buildSwitchCases(cases.tail, buildCompare); });
+    }
+  }
+
+  visitSwitchCase(SwitchCase node) {
+    unreachable();
   }
 
   visitTryStatement(TryStatement node) {