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 b06a9e0fbedde818cf27adaed93b0a3f4abfe0fb..550d5d03db241dd1346a0aca9b8db22593b2350d 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, LocalsHandler locals);
   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
@@ -633,7 +633,7 @@ class NullBreakHandler implements BreakHandler {
   }
   void forEachBreak(Function ignored) { }
   void close() { }
-  List<SourceString> labels() => const <SourceString>[];
+  List<LabelElement> labels() => const <LabelElement>[];
 }
 
 // Records breaks until a target block is available.
@@ -669,15 +669,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;
   }
 }
 
@@ -707,9 +707,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,
@@ -1008,7 +1005,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);
@@ -1651,7 +1648,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));
         }
       }
     }
@@ -2123,9 +2120,10 @@ class SsaBuilder implements Visitor {
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
     HBreak breakInstruction;
     if (node.target === null) {
-      breakInstruction = new HBreak();
-    }  else {
-      breakInstruction = new HBreak(node.target.source);
+      breakInstruction = new HBreak(target);
+    } else {
+      LabelElement label = elements[node.target];
+      breakInstruction = new HBreak(label);
     }
     close(breakInstruction);
     handler.addBreak(breakInstruction, savedLocals);
@@ -2137,18 +2135,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) {
@@ -2276,7 +2266,8 @@ class SsaBuilder implements Visitor {
     if (hasBreak) {
       // There was at least one reachable break, so the label is needed.
       HLabeledBlockInformation blockInfo =
-          new HLabeledBlockInformation(bodyGraph, joinBlock, handler.labels());
+          new HLabeledBlockInformation(

[floitsch, 2012/03/09 16:52:15]

keep on one line.

+            bodyGraph, joinBlock, handler.labels());
       entryBlock.labeledBlockInformation = blockInfo;
     }
     handler.close();
@@ -2310,61 +2301,152 @@ class SsaBuilder implements Visitor {
 
   visitSwitchStatement(SwitchStatement node) {
     work.allowSpeculativeOptimization = false;
+    LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
+    HBasicBlock startBlock = graph.addNewBlock();
+    goto(current, startBlock);
+    open(startBlock);
     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) {

[floitsch, 2012/03/09 16:52:15]

Can't you move buildCompare and buildThrow into buildSwitchCases?
The only thing that would be needed to be passed to buildSwitchCase would be the
'expression', which seems logical.
Also you could inline buildThrow (it is only used in one place).
I would also consider inlining buildCompare, but we can definitely keep it.

[Lasse Reichstein Nielsen, 2012/03/12 13:05:23]

I'll inline them.

+      visit(caseExpression);
+      push(new HEquals(target, pop(), expression));
+    }

[floitsch, 2012/03/09 16:52:15]

please add a newline after function declarations.

[Lasse Reichstein Nielsen, 2012/03/12 13:05:23]

Done.

+    void buildThrow() {
+      Element element =
+          compiler.findHelper(const SourceString("getFallThroughError"));
+      push(new HStatic(element));
+      HInstruction error = new HInvokeStatic(
+           Selector.INVOCATION_0, <HInstruction>[pop()]);
+      add(error);
+      close(new HThrow(error));
+    }
+    buildSwitchCases(cases, buildCompare, buildThrow);
+
+    HBasicBlock lastBlock = lastOpenedBlock;
+
+    // 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 (!isAborted()) {
+      caseLocals.add(localsHandler);
+    }
+    if (caseLocals.length != 0) {
+      graph.addBlock(joinBlock);
+      if (!isAborted()) {
+        goto(current, joinBlock);
       }
-      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);
-        }
+      open(joinBlock);
+      if (caseLocals.length == 1) {
+        localsHandler = caseLocals[0];
       } 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));
+        localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
+      }
+    } else {
+      // The joinblock is not used.
+      joinBlock = null;
+    }
+    startBlock.labeledBlockInformation = new HLabeledBlockInformation.implicit(
+        new SubGraph(startBlock, lastBlock),
+        joinBlock,
+        elements[node]);
+  }
+
+
+  // Recursively build an if/else structure to match the cases.
+  buildSwitchCases(Link<Node> cases,
+                   Function buildCompare,
+                   Function buildThrow) {
+    SwitchCase node = cases.head;
+    // TODO(lrn): Handle labels and continues.
+
+    // 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);
+      if (!isAborted()) {
+        compiler.reportWarning(node, 'Missing break at end of switch case');
+        buildThrow();
       }
-      handleIf(handleThen, handleElse);
     }
 
-    localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
-    HBasicBlock loopEntryBlock = current;
-    localsHandler.enterLoopBody(node);
+    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");
+      }
+      visit(node.statements);
+      return;
+    }
 
-    handleElse();
+    // Recursively build the test conditions.
+    HInstruction buildTests(Link<Node> expressions, HInstruction left) {

[floitsch, 2012/03/09 16:52:15]

This looks a lot like the visitLogicalAndOr. I vote for having a handleAndOr
like the handleIf.

[Lasse Reichstein Nielsen, 2012/03/12 13:05:23]

Good idea.

+      // previous is a boolean instruction.

[floitsch, 2012/03/09 16:52:15]

'previous' is still here.

[Lasse Reichstein Nielsen, 2012/03/12 13:05:23]

Not any more. And good riddance.

+      if (expressions.isEmpty()) return left;
+      push(new HNot(left));
 
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: node);
-    }
+      HIf branch = new HIf(pop(), false);
+      HBasicBlock leftBlock = close(branch);
+      LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
+      HBasicBlock rightBlock = addNewBlock();
+      leftBlock.addSuccessor(rightBlock);
+      open(rightBlock);
 
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
+      buildCompare(expressions.head);
+      HInstruction right = buildTests(expressions.tail, popBoolified());
 
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
+      SubGraph rightGraph = new SubGraph(rightBlock, current);
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler);
+      rightBlock = close(new HGoto());
+      HBasicBlock joinBlock = addNewBlock();
+      leftBlock.addSuccessor(joinBlock);
+      rightBlock.addSuccessor(joinBlock);
+      open(joinBlock);
+
+      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);
+      if (cases.tail.isEmpty()) {
+        handleIf(() { visit(node.statements); }, null);
+      } else {
+        handleIf(() { visitStatementsAndAbort(); },
+                 () { buildSwitchCases(cases.tail,
+                                       buildCompare, buildThrow); });
+      }
+    }
+  }
+
+  visitSwitchCase(SwitchCase node) {
+    unreachable();
   }
 
   visitTryStatement(TryStatement node) {