Switch-implementation.

frog/leg/ssa/builder.dart

 // Copyright (c) 2012, 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.
 
 class Interceptors {
   Compiler compiler;
   Interceptors(Compiler this.compiler);
 
   SourceString mapOperatorToMethodName(Operator op) {
     String name = op.source.stringValue;
@@ skipping 597 matching lines @@
 }
 
 
 // Represents a single break instruction.
 class BreakHandlerEntry {
   final HBreak breakInstruction;
   final LocalsHandler locals;
   BreakHandlerEntry(this.breakInstruction, this.locals);
 }
 
 interface BreakHandler default BreakHandlerImpl {

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

Do we really need an interface for this?

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

Maybe not, but I like making the NullBreakHandler const-creatable.
This is really just a linked stack of break handlers, that manage their own
attach/detach logic.
The NullBreakHandler is just convenience, to avoid checking for null.

   BreakHandler(SsaBuilder builder, StatementElement target);
   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
 // used as the target of a break, and therefore doesn't need a break
 // handler associated with it.
 class NullBreakHandler implements BreakHandler {
   const NullBreakHandler();
   void addBreak(HBreak breakInstruction, LocalsHandler locals) {
     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.
 // Breaks are always forward jumps.
 class BreakHandlerImpl implements BreakHandler {
   final BreakHandler previous;
   final SsaBuilder builder;
   final StatementElement target;
   final List<BreakHandlerEntry> breaks;
   BreakHandlerImpl(SsaBuilder builder, this.target)
@@ skipping 15 matching lines @@
     }
   }
 
   void close() {
     assert(builder.currentBreakHandler === this);
     // The mapping from StatementElement to BreakHandler is no longer needed.
     builder.breakTargets.remove(target);
     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;
   }
 }
 
 class SsaBuilder implements Visitor {
   final Compiler compiler;
   TreeElements elements;
   final Interceptors interceptors;
   final WorkItem work;
   bool methodInterceptionEnabled;
   HGraph graph;
   LocalsHandler localsHandler;
   HInstruction rethrowableException;
 
   Map<StatementElement, BreakHandler> breakTargets;
 
   // We build the Ssa graph by simulating a stack machine.
   List<HInstruction> stack;
 
   // The current block to add instructions to. Might be null, if we are
   // visiting dead code.
   HBasicBlock current;
   // The most recently opened block. Has the same value as [current] while
   // the block is open, but unlike [current], it isn't cleared when the current
   // block is closed.
   HBasicBlock lastOpenedBlock;
 
   // 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,
       this.work = work,
       interceptors = compiler.builder.interceptors,
       methodInterceptionEnabled = true,
       elements = work.resolutionTree,
       graph = new HGraph(),
       stack = new List<HInstruction>(),
       breakTargets = new Map<StatementElement, BreakHandler>() {
@@ skipping 275 matching lines @@
   }
 
   /**
    * Creates a new loop-header block. The previous [current] block
    * is closed with an [HGoto] and replaced by the newly created block.
    * Also notifies the locals handler that we're entering a loop.
    */
   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);
 
     localsHandler.beginLoopHeader(node, loopEntry);
     return breakHandler;
   }
 
   /**
    * Ends the loop:
@@ skipping 240 matching lines @@
       } else if (thenBlock !== null) {
         // The only predecessor is the then branch.
         localsHandler = thenLocals;
       }
     }
     condition.blockInformation =
         new HIfBlockInformation(condition, thenGraph, elseGraph, joinBlock);
   }
 
   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);
     //   result = phi(t0, t1);
     //
     // x || y is transformed into:
     //   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) {
       condition = boolifiedLeft;
     } else {
       condition = new HNot(boolifiedLeft);
       add(condition);
     }
     HIf branch = new HIf(condition, false);
     HBasicBlock leftBlock = close(branch);
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
     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());
 
     HBasicBlock joinBlock = addNewBlock();
     leftBlock.addSuccessor(joinBlock);
     rightBlock.addSuccessor(joinBlock);
     open(joinBlock);
 
     branch.blockInformation =
@@ skipping 334 matching lines @@
           SourceString name = selector.namedArguments[i];
           if (name == parameter.name) {
             foundIndex = i;
             break;
           }
         }
         if (foundIndex != -1) {
           list.add(namedArguments[foundIndex]);
         } else {
           Constant constant = compiler.compileVariable(parameter);
-          list.add(graph.addConstant(constant)); 
+          list.add(graph.addConstant(constant));
         }
       }
     }
   }
 
   void addGenericSendArgumentsToList(Link<Node> link, List<HInstruction> list) {
     for (; !link.isEmpty(); link = link.tail) {
       visit(link.head);
       list.add(pop());
     }
@@ skipping 451 matching lines @@
   visitBreakStatement(BreakStatement node) {
     work.allowSpeculativeOptimization = false;
     assert(!isAborted());
     StatementElement target = elements[node];
     assert(target !== null);
     BreakHandler handler = breakTargets[target];
     assert(handler !== null);
     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);
   }
 
   visitContinueStatement(ContinueStatement node) {
     // TODO(lrn): Replace this with a real implementation of continue.
     compiler.reportWarning(node, 'continue not implemented');
     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) {
     // Generate a structure equivalent to:
     //   Iterator<E> $iter = <iterable>.iterator()
     //   while ($iter.hasNext()) {
     //     E <declaredIdentifier> = $iter.next();
     //     <body>
     //   }
     localsHandler.startLoop(node);
@@ skipping 141 matching lines @@
     visit(node.value);
     visit(node.key);
   }
 
   visitNamedArgument(NamedArgument node) {
     visit(node.expression);
   }
 
   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;
+      open(joinBlock);
+      if (caseLocals.length == 1) {
+        localsHandler = caseLocals[0];
+      } else {
+        localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
+      }
+    } else {
+      // The joinblock is not used.
+      joinBlock = null;
     }
-    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();
+    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);
+
+      // If this is the last expression, just return it.
+      if (expressions.tail.isEmpty()) {
+        left();
+        return;
+      }
+
+      void right() {
+        buildTests(expressions.tail);
+      }
+      handleLogicalAndOr(left, right, isAnd: false);
     }
 
-    localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
-    HBasicBlock loopEntryBlock = current;
-    localsHandler.enterLoopBody(node);
+    buildTests(expressions);
+    HInstruction result = popBoolified();
 
-    handleElse();
+    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); });
+      }
+    }
+  }
 
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: node);
-    }
-
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
-
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
-
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
-
-    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) {
     work.allowSpeculativeOptimization = false;
     assert(!work.isBailoutVersion());
     HBasicBlock enterBlock = graph.addNewBlock();
     close(new HGoto()).addSuccessor(enterBlock);
     open(enterBlock);
     HTry tryInstruction = new HTry();
     List<HBasicBlock> blocks = <HBasicBlock>[];
@@ skipping 111 matching lines @@
     // Normally, we would call [close] here. However, then we hit
     // another unimplemented feature: aborting loop body. Simply
     // calling [add] does not work as it asserts that the instruction
     // isn't a control flow instruction. So we inline parts of [add].
     current.addAfter(current.last, new HThrow(message));
     if (isExpression) {
       stack.add(graph.addConstantNull());
     }
   }
 }