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(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;
   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;
 
+  // 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>() {
+      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) {
     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 (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()
     //   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();
   }
 
   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) {
     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);
   }
 }