Support break and labeled statements.

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 464 matching lines @@
   void enterLoopUpdates(Loop node) {
     // If there are declared boxed loop variables then the updates might have
     // access to the box and we must switch to a new box before executing the
     // updates.
     // In all other cases a new box will be created when entering the body of
     // the next iteration.
     ClosureScope scopeData = closureData.capturingScopes[node];
     if (scopeData == null) return;
     if (scopeData.hasBoxedLoopVariables()) {
       updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables);
-    }    
+    }
   }
 
   void endLoop(HBasicBlock loopEntry) {
     loopEntry.forEachPhi((HPhi phi) {
       Element element = phi.element;
       HInstruction postLoopDefinition = directLocals[element];
       phi.addInput(postLoopDefinition);
     });
   }
 
+  /**
+   * 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
     // block. Since variable declarations are scoped the declared
     // variable cannot be alive outside the block. Note: this is only
     // true for nodes where we do joins.
     Map<Element, HInstruction> joinedLocals = new Map<Element, HInstruction>();
     otherLocals.directLocals.forEach((element, instruction) {
       // We know 'this' cannot be modified.
       if (element === closureData.thisElement) {
         assert(directLocals[element] == instruction);
         joinedLocals[element] = instruction;
       } else {
         HInstruction mine = directLocals[element];
         if (mine === null) return;
         if (instruction === mine) {
           joinedLocals[element] = instruction;
         } else {
           HInstruction phi = new HPhi.manyInputs(element, [instruction, mine]);
           joinBlock.addPhi(phi);
           joinedLocals[element] = phi;
         }
       }
     });
     directLocals = joinedLocals;
   }
 }
 
+
+// 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;
   final Interceptors interceptors;
   final WorkItem work;
   bool methodInterceptionEnabled;
   HGraph graph;
   LocalsHandler localsHandler;
 
+  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;
 
   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>() {
+      stack = new List<HInstruction>(),
+      breakTargets = new Map<StatementElement, BreakHandler>() {
     localsHandler = new LocalsHandler(this);
   }
 
   void disableMethodInterception() {
     assert(methodInterceptionEnabled);
     methodInterceptionEnabled = false;
   }
 
   void enableMethodInterception() {
     assert(!methodInterceptionEnabled);
@@ skipping 282 matching lines @@
   visitExpressionStatement(ExpressionStatement node) {
     visit(node.expression);
     pop();
   }
 
   /**
    * 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.
    */
-  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;
   }
 
   /**
    * Ends the loop:
    * - creates a new block and adds it as successor to the [branchBlock].
    * - 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.
   visitLoop(Node loop, Node initializer, Expression condition, NodeList updates,
             Node body) {
     // Generate:
     //  <initializer>
     //  loop-entry:
     //    if (!<condition>) goto loop-exit;
     //    <body>
     //    <updates>
     //    goto loop-entry;
     //  loop-exit:
     if (condition === null || body === null) {
       compiler.unimplemented(
           'SsaBuilder.visitLoop with empty condition or body',
           node: loop);
     }
 
     localsHandler.startLoop(loop);
 
     // The initializer.
     if (initializer !== null) {
       visit(initializer);
       // We don't care about the value of the initialization.
       if (initializer.asExpression() !== null) pop();
     }
     assert(!isAborted());
 
-    beginLoopHeader(loop);
+    BreakHandler breakHandler = beginLoopHeader(loop);
     HBasicBlock conditionBlock = current;
 
     // The condition.
     visit(condition);
     HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified()));
 
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
     // The body.
     HBasicBlock bodyBlock = addNewBlock();
@@ skipping 24 matching lines @@
         // The result of the update instruction isn't used, and can just
         // be dropped.
         HInstruction updateInstruction = pop();
       }
     }
     updateBlock = close(new HGoto());
     // The back-edge completing the cycle.
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock);
+    endLoop(conditionBlock, conditionExitBlock, breakHandler);
     localsHandler = savedLocals;
   }
 
   visitFor(For node) {
     if (node.condition === null) {
       compiler.unimplemented("SsaBuilder for loop without condition");
     }
     assert(node.body !== null);
     visitLoop(node, node.initializer, node.condition, node.update, node.body);
   }
 
   visitWhile(While node) {
     visitLoop(node, null, node.condition, null, node.body);
   }
 
   visitDoWhile(DoWhile node) {
     localsHandler.startLoop(node);
-    beginLoopHeader(node);
+    BreakHandler breakHandler = beginLoopHeader(node);
     HBasicBlock loopEntryBlock = current;
 
     localsHandler.enterLoopBody(node);
     visit(node.body);
     if (isAborted()) {
       compiler.unimplemented("SsaBuilder for loop with aborting body");
     }
 
     // If there are no continues we could avoid the creation of the condition
     // block. This could also lead to a block having multiple entries and exits.
     HBasicBlock bodyExitBlock = close(new HGoto());
     HBasicBlock conditionBlock = addNewBlock();
     bodyExitBlock.addSuccessor(conditionBlock);
     open(conditionBlock);
     visit(node.condition);
     assert(!isAborted());
     conditionBlock = close(new HLoopBranch(popBoolified()));
 
     conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
     loopEntryBlock.postProcessLoopHeader();
 
-    endLoop(loopEntryBlock, conditionBlock);
+    endLoop(loopEntryBlock, conditionBlock, breakHandler);
   }
 
   visitFunctionExpression(FunctionExpression node) {
     ClosureData nestedClosureData = closureDataCache[node];
     assert(nestedClosureData !== null);
     assert(nestedClosureData.closureClassElement !== null);
     ClassElement closureClassElement =
         nestedClosureData.closureClassElement;
     FunctionElement callElement = nestedClosureData.callElement;
     compiler.enqueue(new WorkItem.toCodegen(callElement, elements));
@@ skipping 876 matching lines @@
   visitEmptyStatement(EmptyStatement node) {
     compiler.unimplemented('SsaBuilder.visitEmptyStatement',
                            node: node);
   }
 
   visitModifiers(Modifiers node) {
     compiler.unimplemented('SsaBuilder.visitModifiers', node: node);
   }
 
   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()
     //   while ($iter.hasNext()) {
     //     E <declaredIdentifier> = $iter.next();
     //     <body>
     //   }
     localsHandler.startLoop(node);
 
     SourceString iteratorName = const SourceString("iterator");
 
     Selector selector = Selector.INVOCATION_0;
     Element interceptor = interceptors.getStaticInterceptor(iteratorName, 0);
     assert(interceptor != null);
     HStatic target = new HStatic(interceptor);
     add(target);
     visit(node.expression);
     List<HInstruction> inputs = <HInstruction>[target, pop()];
     HInstruction iterator = new HInvokeInterceptor(
         selector, iteratorName, false, inputs);
     add(iterator);
 
-    beginLoopHeader(node);
+    BreakHandler breakHandler = beginLoopHeader(node);
     HBasicBlock conditionBlock = current;
 
     // The condition.
     push(new HInvokeDynamicMethod(
         selector, const SourceString('hasNext'), [iterator]));
     HBasicBlock conditionExitBlock = close(new HLoopBranch(popBoolified()));
 
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
     // The body.
@@ skipping 29 matching lines @@
     // update block is the jump-target for continue statements. We could avoid
     // the creation if there is no continue, but for now we always create it.
     HBasicBlock updateBlock = addNewBlock();
     bodyBlock.addSuccessor(updateBlock);
     open(updateBlock);
     updateBlock = close(new HGoto());
     // The back-edge completing the cycle.
     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) {
     compiler.unimplemented('SsaBuilder.visitLiteralMap', node: node);
   }
 
   visitLiteralMapEntry(LiteralMapEntry node) {
     compiler.unimplemented('SsaBuilder.visitLiteralMapEntry', node: node);
   }
 
@@ skipping 100 matching lines @@
   }
 
   visitCatchBlock(CatchBlock node) {
     visit(node.block);
   }
 
   visitTypedef(Typedef node) {
     compiler.unimplemented('SsaBuilder.visitTypedef', node: node);
   }
 }