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..dcf86b14910183184233271582cdafe8b0a55642 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,86 @@ 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(Map<StatementElement, BreakHandler> breakTargets);
+  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 Map<StatementElement, BreakHandler> breakTargets;
+  final List<StatementElement> elements;
+  final List<BreakHandlerEntry> breaks;
+  bool closed = false;
+  BreakHandlerImpl(this.breakTargets)

[floitsch, 2012/02/20 19:01:54]

Instead of passing in breakTargets take the builder.
This looks too much like a non-shared variable.

[Lasse Reichstein Nielsen, 2012/02/21 13:53:56]

Will do.

+      : elements = <StatementElement>[],
+        breaks = <BreakHandlerEntry>[];
+
+  void addTarget(StatementElement element) {
+    assert(breakTargets[element] === null);
+    elements.add(element);
+    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(!closed);
+    closed = true;
+    // The mapping from StatementElement to BreakHandler is no longer needed.
+    for (StatementElement element in elements) {
+      assert(breakTargets[element] === this);
+      breakTargets.remove(element);
+    }
+  }
+
+  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 +619,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;
 
@@ -544,7 +635,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 +939,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) {

[floitsch, 2012/02/20 19:01:54]

Instead of returning a BreakHandler make the BreakHandler a cons-structure
(stack) that returns the last head when closing.
Then add a field currentBreakHandler in the builder.

[Lasse Reichstein Nielsen, 2012/02/21 13:53:56]

Done. Break handlers are now a list, and since they know the builder, they even
add and remove themselves from the list.

     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 +957,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 +1001,7 @@ class SsaBuilder implements Visitor {
     }
     assert(!isAborted());
 
-    beginLoopHeader(loop);
+    BreakHandler breakHandler = beginLoopHeader(loop);
     HBasicBlock conditionBlock = current;
 
     // The condition.
@@ -944,7 +1046,7 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock);
+    endLoop(conditionBlock, conditionExitBlock, breakHandler);
     localsHandler = savedLocals;
   }
 
@@ -962,7 +1064,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 +1086,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 +1983,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 (currentBreakHandler === null) {
+      if (element === null) return const NullBreakHandler();
+      handler = new BreakHandler(breakTargets);
+    } else {
+      handler = currentBreakHandler;
+      currentBreakHandler = 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 +2041,7 @@ class SsaBuilder implements Visitor {
         selector, iteratorName, false, inputs);
     add(iterator);
 
-    beginLoopHeader(node);
+    BreakHandler breakHandler = beginLoopHeader(node);
     HBasicBlock conditionBlock = current;
 
     // The condition.
@@ -1960,12 +2091,61 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock);
+    endLoop(conditionBlock, conditionExitBlock, breakHandler);
     localsHandler = savedLocals;
+    breakHandler.close();
   }
 
+  BreakHandler currentBreakHandler = null;
+
   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(breakTargets);
+        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.
+      currentBreakHandler = handler;

[floitsch, 2012/02/20 19:01:54]

This looks like work that the resolver should have done.

[Lasse Reichstein Nielsen, 2012/02/21 13:53:56]

I agree, and agreed when doing the resolution, but someone wanted the label of a
labeled statement to resolve to that, not the the underlying statement.

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

What I wanted:
a LabelElement that points to its AST node.
a mapping that gets the list of LabelElements for a block/loop.
But somebody didn't want to implement that.

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

Touche. I'll consider redoing this in a different CL.

+      visit(currentNode);
+      assert(currentBreakHandler === null);
+    } else {
+      // Introduce a new basic block.
+      HBasicBlock entryBlock = graph.addNewBlock();
+      goto(current, entryBlock);
+      open(entryBlock);
+      visit(currentNode);
+      // Always create at least one join block, even if there turns out to be
+      // no breaks anyway.

[floitsch, 2012/02/20 19:01:54]

How can this be possible? I thought that the handler would be null then.

[Lasse Reichstein Nielsen, 2012/02/21 13:53:56]

Some analysis might have turned a break into dead code, even though it was there
at resolution.

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

As long as we don't have such an optimization, assert that it is not the case.
This comment is otherwise confusing.

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

As discussed offline, the break could be dead code from the beginning - it would
still be resolved by the resolver, but not be visited here in the builder.
If there really is no break for the target, we don't need the label, and without
the HLabeledBlockInformation, we don't need to create a join node at all. So,
much simplified.

+      HBasicBlock firstJoinBlock = graph.addNewBlock();
+      bool isFirst = true;
+      handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
+        HBasicBlock joinBlock = isFirst ? firstJoinBlock : graph.addNewBlock();
+        isFirst = false;
+        breakInstruction.block.addSuccessor(joinBlock);
+        if (!isAborted()) {
+          goto(current, joinBlock);
+        }
+        open(joinBlock);
+        localsHandler.mergeWith(locals, joinBlock);
+      });
+      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) {