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 9d022554f50a5c631849663b5998dbe9b58f2436..5be8f1e83b67846b9f8e75f37c2190c6acd7814a 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();

[ahe, 2012/03/13 10:17:15]

I like seeing a move from SourceString to Element.

 }
 
 // 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,
@@ -1005,7 +1002,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);
@@ -1266,6 +1263,13 @@ class SsaBuilder implements Visitor {
   }
 
   void visitLogicalAndOr(Send node, Operator op) {
+    handleLogicalAndOr(() { visit(node.receiver); },
+                       () { visit(node.argumentsNode); },
+                       isAnd: (const SourceString("&&") == op.source));
+  }
+
+
+  void handleLogicalAndOr(void left(), void right(), [bool isAnd = true]) {
     // x && y is transformed into:
     //   t0 = boolify(x);
     //   if (t0) t1 = boolify(y);
@@ -1275,9 +1279,7 @@ class SsaBuilder implements Visitor {
     //   t0 = boolify(x);
     //   if (not(t0)) t1 = boolify(y);
     //   result = phi(t0, t1);
-    bool isAnd = (const SourceString("&&") == op.source);
-
-    visit(node.receiver);
+    left();
     HInstruction boolifiedLeft = popBoolified();
     HInstruction condition;
     if (isAnd) {
@@ -1293,7 +1295,8 @@ class SsaBuilder implements Visitor {
     HBasicBlock rightBlock = addNewBlock();
     leftBlock.addSuccessor(rightBlock);
     open(rightBlock);
-    visit(node.argumentsNode);
+
+    right();
     HInstruction boolifiedRight = popBoolified();
     SubGraph rightGraph = new SubGraph(rightBlock, current);
     rightBlock = close(new HGoto());
@@ -1648,7 +1651,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));
         }
       }
     }
@@ -2120,9 +2123,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);
@@ -2134,18 +2138,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) {
@@ -2307,61 +2303,130 @@ 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);
+
+    BreakHandler breakHandler = getBreakHandler(node);
+
+    buildSwitchCases(cases, expression);
+
+    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()) {

[floitsch, 2012/03/12 13:46:05]

Please add comment when this happens: it's never aborted, unless there is a
default clause and the default-clause breaks or returns.

[Lasse Reichstein Nielsen, 2012/03/13 12:09:38]

Done.

+      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();
+        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, HInstruction expression) {
+    SwitchCase node = cases.head;
+
+    // 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');

[floitsch, 2012/03/12 13:46:05]

Shouldn't that be caught earlier?
If yes add at least a TODO.

[Lasse Reichstein Nielsen, 2012/03/13 12:09:38]

How? This is the first time we actually detect whether control reaches the end
of the case.
We don't want to warn on:
 case 42: {if (x) return 42; else break;}
so we would a general analysis to check whether a block always aborts.

+        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));
+      }
+    }
+
+    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");

[ahe, 2012/03/13 10:17:15]

Please pass the node.

[Lasse Reichstein Nielsen, 2012/03/13 12:09:38]

Done.

+      }
+      visit(node.statements);
+      // This must be the final case (otherwise "default" would be invalid),
+      // so we don't need to check for fallthrough.
+      return;
+    }
+
+    // Recursively build the test conditions. Leaves the result on the
+    // expression stack.
+    void buildTests(Link<Node> expressions) {
+      // Build comparison for one case expression.
+      void left() {
         Element equalsHelper = interceptors.getEqualsInterceptor();
         HInstruction target = new HStatic(equalsHelper);
         add(target);
-        push(new HEquals(target, caseExpression, expression));
+        visit(expressions.head);
+        push(new HEquals(target, pop(), expression));
       }
-      handleIf(handleThen, handleElse);
-    }
-
-    localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
-    HBasicBlock loopEntryBlock = current;
-    localsHandler.enterLoopBody(node);
 
-    handleElse();
+      // If this is the last expression, just return it.
+      if (expressions.tail.isEmpty()) {
+        left();
+        return;
+      }
 
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: node);
+      void right() {
+        buildTests(expressions.tail);
+      }
+      handleLogicalAndOr(left, right, isAnd: false);
     }
 
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
+    buildTests(expressions);
+    HInstruction result = popBoolified();
 
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
-
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
+    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, expression); });
+      }
+    }
+  }
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler);
+  visitSwitchCase(SwitchCase node) {
+    unreachable();

[ahe, 2012/03/13 10:17:15]

Please make sure to pass in the node to unreachable.

[Lasse Reichstein Nielsen, 2012/03/13 12:09:38]

I dont' think unreachable takes an argument (defined in leg.dart).

   }
 
   visitTryStatement(TryStatement node) {