Support break and labeled statements.

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 c74c887a0f4ef499225484b326e0b25dc78ff54e..7fa4de7978cef4196aed964f760174dbf899452c 100644
--- a/frog/leg/ssa/builder.dart
+++ b/frog/leg/ssa/builder.dart
@@ -482,7 +482,7 @@ class LocalsHandler {
     if (scopeData == null) return;
     if (scopeData.hasBoxedLoopVariables()) {
       updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables);
-    }    
+    }
   }
 
   void endLoop(HBasicBlock loopEntry) {
@@ -493,6 +493,15 @@ class LocalsHandler {
     });
   }
 
+  /**
+   * Merge [otherLocals] into this locals handler, creating phi-nodes when
+   * there is a conflict.
+   * If a phi node is necessary, it will use the otherLocals instruction as the
+   * first input, and this handler's instruction as the second.
+   * NOTICE: This means that the predecessor corresponding to [otherLocals]
+   * should be the first predecessor of the current block, and the one
+   * corresponding to this locals handler should be the second.
+   */
   void mergeWith(LocalsHandler otherLocals, HBasicBlock joinBlock) {
     // If an element is in one map but not the other we can safely
     // ignore it. It means that a variable was declared in the
@@ -521,6 +530,90 @@ class LocalsHandler {
   }
 }
 
+
+// Represents a single break instruction.
+class BreakHandlerEntry {
+  final HBreak breakInstruction;
+  final LocalsHandler locals;
+  BreakHandlerEntry(this.breakInstruction, this.locals);
+}
+
+interface BreakHandler default BreakHandlerImpl {
+  BreakHandler(SsaBuilder builder);
+  void addTarget(StatementElement element);
+  void addBreak(HBreak breakInstruction);
+  void forEachBreak(Function action);
+  void close();
+  List<SourceString> 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 addTarget(StatementElement element) { unreachable(); }
+  void addBreak(HBreak breakInstruction) { unreachable() }
+  void forEachBreak(Function ignored) { }
+  void close() { }
+  List<SourceString> labels() => const <SourceString>[];
+}
+
+// Records breaks until a target block is available.
+// Breaks are always forward jumps.
+class BreakHandlerImpl implements BreakHandler{
+  final BreakHandler previous;
+  final SsaBuilder builder;
+  final List<StatementElement> elements;
+  final List<BreakHandlerEntry> breaks;
+  BreakHandlerImpl(SsaBuilder builder)
+      : this.builder = builder,
+        previous = builder.currentBreakHandler,
+        elements = <StatementElement>[],
+        breaks = <BreakHandlerEntry>[] {
+    builder.currentBreakHandler = this;
+  }
+
+  void addTarget(StatementElement element) {
+    assert(builder.breakTargets[element] === null);
+    elements.add(element);
+    builder.breakTargets[element] = this;
+  }
+
+  void addBreak(HBreak breakInstruction,
+                LocalsHandler locals) {
+    breaks.add(new BreakHandlerEntry(breakInstruction, locals));
+  }
+
+  void forEachBreak(Function action) {
+    for (BreakHandlerEntry entry in breaks) {
+      action(entry.breakInstruction, entry.locals);
+    }
+  }
+
+  void close() {
+    assert(builder.currentBreakHandler === this);
+    // The mapping from StatementElement to BreakHandler is no longer needed.
+    for (StatementElement element in elements) {
+      assert(builder.breakTargets[element] === this);
+      builder.breakTargets.remove(element);
+    }
+    builder.currentBreakHandler = previous;
+  }
+
+  List<SourceString> labels() {
+    List<SourceString> result = null;
+    for (StatementElement element in elements) {
+      SourceString name = element.name;
+      if (!name.isEmpty()) {
+        if (result === null) result = <SourceString>[];
+        result.add(name);
+      }
+    }
+    return result === null ? const <SourceString>[] : result;
+  }
+}
+
 class SsaBuilder implements Visitor {
   final Compiler compiler;
   TreeElements elements;
@@ -530,6 +623,8 @@ class SsaBuilder implements Visitor {
   HGraph graph;
   LocalsHandler localsHandler;
 
+  Map<StatementElement, BreakHandler> breakTargets;
+
   // We build the Ssa graph by simulating a stack machine.
   List<HInstruction> stack;
 
@@ -537,6 +632,13 @@ class SsaBuilder implements Visitor {
   // visiting dead code.
   HBasicBlock current;
 
+  // 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,
@@ -544,7 +646,8 @@ class SsaBuilder implements Visitor {
       methodInterceptionEnabled = true,
       elements = work.resolutionTree,
       graph = new HGraph(),
-      stack = new List<HInstruction>() {
+      stack = new List<HInstruction>(),
+      breakTargets = new Map<StatementElement, BreakHandler>() {
     localsHandler = new LocalsHandler(this);
   }
 
@@ -847,15 +950,16 @@ class SsaBuilder implements Visitor {
    * is closed with an [HGoto] and replaced by the newly created block.
    * Also notifies the locals handler that we're entering a loop.
    */
-  void beginLoopHeader(Node node) {
+  BreakHandler beginLoopHeader(Node node) {
     assert(!isAborted());
     HBasicBlock previousBlock = close(new HGoto());
-
-    HBasicBlock loopEntry = graph.addNewLoopHeaderBlock();
+    BreakHandler breakHandler = getLoopBreakHandler(node);
+    HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels());
     previousBlock.addSuccessor(loopEntry);
     open(loopEntry);
 
     localsHandler.beginLoopHeader(node, loopEntry);
+    return breakHandler;
   }
 
   /**
@@ -864,12 +968,21 @@ class SsaBuilder implements Visitor {
    * - opens the new block (setting as [current]).
    * - notifies the locals handler that we're exiting a loop.
    */
-  void endLoop(HBasicBlock loopEntry, HBasicBlock branchBlock) {
+  void endLoop(HBasicBlock loopEntry,
+               HBasicBlock branchBlock,
+               BreakHandler breakHandler) {
     HBasicBlock loopExitBlock = addNewBlock();
     assert(branchBlock.successors.length == 1);
     branchBlock.addSuccessor(loopExitBlock);
     open(loopExitBlock);
     localsHandler.endLoop(loopEntry);
+    breakHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
+      HBasicBlock joinBlock = addNewBlock();
+      breakInstruction.block.addSuccessor(joinBlock);
+      goto(current, joinBlock);
+      open(joinBlock);
+      localsHandler.mergeWith(locals, joinBlock);
+    });
   }
 
   // For while loops, initializer and update are null.
@@ -899,7 +1012,7 @@ class SsaBuilder implements Visitor {
     }
     assert(!isAborted());
 
-    beginLoopHeader(loop);
+    BreakHandler breakHandler = beginLoopHeader(loop);
     HBasicBlock conditionBlock = current;
 
     // The condition.
@@ -944,7 +1057,7 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock);
+    endLoop(conditionBlock, conditionExitBlock, breakHandler);
     localsHandler = savedLocals;
   }
 
@@ -962,7 +1075,7 @@ class SsaBuilder implements Visitor {
 
   visitDoWhile(DoWhile node) {
     localsHandler.startLoop(node);
-    beginLoopHeader(node);
+    BreakHandler breakHandler = beginLoopHeader(node);
     HBasicBlock loopEntryBlock = current;
 
     localsHandler.enterLoopBody(node);
@@ -984,7 +1097,7 @@ class SsaBuilder implements Visitor {
     conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
     loopEntryBlock.postProcessLoopHeader();
 
-    endLoop(loopEntryBlock, conditionBlock);
+    endLoop(loopEntryBlock, conditionBlock, breakHandler);
   }
 
   visitFunctionExpression(FunctionExpression node) {
@@ -1881,13 +1994,42 @@ class SsaBuilder implements Visitor {
   }
 
   visitBreakStatement(BreakStatement node) {
-    compiler.unimplemented('SsaBuilder.visitBreakStatement', node: 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);
+    }
+    close(breakInstruction);
+    handler.addBreak(breakInstruction, savedLocals);
   }
 
   visitContinueStatement(ContinueStatement node) {
     compiler.unimplemented('SsaBuilder.visitContinueStatement', node: node);
   }
 
+  BreakHandler getLoopBreakHandler(Loop node) {
+    StatementElement element = elements[node];
+    BreakHandler handler;
+    if (loopBreakHandler === null) {
+      if (element === null) return const NullBreakHandler();
+      handler = new BreakHandler(this);
+    } else {
+      handler = loopBreakHandler;
+      loopBreakHandler = null;
+      if (element === null) return handler;
+    }
+    handler.addTarget(element);
+    return handler;
+  }
+
   visitForInStatement(ForInStatement node) {
     // Generate a structure equivalent to:
     //   Iterator<E> $iter = <iterable>.iterator()
@@ -1910,7 +2052,7 @@ class SsaBuilder implements Visitor {
         selector, iteratorName, false, inputs);
     add(iterator);
 
-    beginLoopHeader(node);
+    BreakHandler breakHandler = beginLoopHeader(node);
     HBasicBlock conditionBlock = current;
 
     // The condition.
@@ -1960,12 +2102,72 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock);
+    endLoop(conditionBlock, conditionExitBlock, breakHandler);
     localsHandler = savedLocals;
+    breakHandler.close();
   }
 
   visitLabelledStatement(LabelledStatement node) {
-    compiler.unimplemented('SsaBuilder.visitLabelledStatement', node: node);
+    BreakHandler handler = null;
+    Node currentNode = node;
+    do {
+      StatementElement element = elements[currentNode];
+      if (element !== null && element.isBreakTarget) {
+        if (handler === null) handler = new BreakHandler(this);
+        handler.addTarget(element);
+      }
+      currentNode = currentNode.statement;
+    } while (currentNode is LabelledStatement);
+    if (handler === null) {
+      // The labels are not break targets.
+      visit(currentNode);
+    } else if (currentNode is Loop || currentNode is SwitchStatement) {
+      // The labels apply to that statement, and will be handled there.
+      loopBreakHandler = handler;
+      visit(currentNode);
+      assert(loopBreakHandler === null);
+    } else {
+      // Introduce a new basic block.
+      HBasicBlock entryBlock = graph.addNewBlock();
+      goto(current, entryBlock);
+      open(entryBlock);
+      visit(currentNode);
+      if (isAborted()) {
+        compiler.unimplemented(
+            "SsaBuilder for labeled statement with aborting body", node: node);
+      }
+      // Always create at least one join block, even if there turns out to be
+      // no breaks anyway.
+      HBasicBlock firstJoinBlock = null;

[floitsch, 2012/02/22 13:17:21]

As discussed. let's get rid of firstJoinBlock and simply put the
labeledBlockInformation on the last merge-block.

[Lasse Reichstein Nielsen, 2012/02/22 14:12:24]

Done.

+      handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
+        HBasicBlock joinBlock = graph.addNewBlock();
+        if (firstJoinBlock === null) {
+          firstJoinBlock = joinBlock;
+        }
+        breakInstruction.block.addSuccessor(joinBlock);
+        if (!isAborted()) {
+          goto(current, joinBlock);
+          open(joinBlock);
+          localsHandler.mergeWith(locals, joinBlock);
+        } else {
+          open(joinBlock);
+          localsHandler = locals;
+        }
+      });
+      if (firstJoinBlock === null) {
+        firstJoinBlock = graph.addNewBlock();
+        if (!isAborted()) goto(current, firstJoinBlock);
+        open(firstJoinBlock);
+      }
+      HLabeledBlockInformation blockInfo =
+          new HLabeledBlockInformation(entryBlock, firstJoinBlock,
+                                       handler.labels());
+      handler.close();
+      // Mark both entry and exit with the information. You can
+      // tell which one is which by comparing with blockInfo.start/end.
+      entryBlock.labeledBlockInformation = blockInfo;
+      firstJoinBlock.labeledBlockInformation = blockInfo;
+    }
   }
 
   visitLiteralMap(LiteralMap node) {