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 602 matching lines @@
   final HBreak breakInstruction;
   final LocalsHandler locals;
   BreakHandlerEntry(this.breakInstruction, this.locals);
 }
 
 interface BreakHandler default BreakHandlerImpl {
   BreakHandler(SsaBuilder builder, StatementElement target);
   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
 // 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 278 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 622 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 107 matching lines @@
     if (!isAborted()) {
       goto(current, joinBlock);
       breakLocals.add(localsHandler);
     }
     open(joinBlock);
     localsHandler = beforeLocals.mergeMultiple(breakLocals, joinBlock);
 
     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();
   }
 
   visitLiteralMap(LiteralMap node) {
     List<HInstruction> inputs = <HInstruction>[];
     for (Link<Node> link = node.entries.nodes;
          !link.isEmpty();
          link = link.tail) {
@@ skipping 13 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);
+    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;
+      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();
-        Element equalsHelper = interceptors.getEqualsInterceptor();
-        HInstruction target = new HStatic(equalsHelper);
-        add(target);
-        push(new HEquals(target, caseExpression, expression));
+    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);
-
-    handleElse();
-
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: 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;
     }
 
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
+    // 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));
 
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
+      HIf branch = new HIf(pop(), false);
+      HBasicBlock leftBlock = close(branch);
+      LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
+      HBasicBlock rightBlock = addNewBlock();
+      leftBlock.addSuccessor(rightBlock);
+      open(rightBlock);
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler);
+      buildCompare(expressions.head);
+      HInstruction right = buildTests(expressions.tail, popBoolified());
+
+      SubGraph rightGraph = new SubGraph(rightBlock, current);
+
+      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) {
     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());
     }
   }
 }