Continue for simple loops (while/for).

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 2c2174aeb49e8eda3fdf3c610e532c8d9ad4af0a..446d699c391d0b43084444cc6be6c8fd3c0be6d7 100644
--- a/frog/leg/ssa/builder.dart
+++ b/frog/leg/ssa/builder.dart
@@ -607,16 +607,21 @@ class LocalsHandler {
 
 
 // Represents a single break instruction.

[ngeoffray, 2012/03/19 11:42:06]

break/continue

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Done.

-class BreakHandlerEntry {
-  final HBreak breakInstruction;
+class JumpHandlerEntry {
+  final HGoto jumpInstruction;
   final LocalsHandler locals;
-  BreakHandlerEntry(this.breakInstruction, this.locals);
+  bool isBreak() => jumpInstruction is HBreak;
+  bool isContinue() => jumpInstruction is HContinue;
+  JumpHandlerEntry(this.jumpInstruction, this.locals);
 }
 
-interface BreakHandler default BreakHandlerImpl {
-  BreakHandler(SsaBuilder builder, TargetElement target);
-  void addBreak(HBreak breakInstruction, LocalsHandler locals);
-  void forEachBreak(Function action);
+
+interface JumpHandler default JumpHandlerImpl {
+  JumpHandler(SsaBuilder builder, TargetElement target);
+  void generateBreak([LabelElement label]);
+  void generateContinue([LabelElement label]);
+  void forEachBreak(void action(HBreak instruction, LocalsHandler locals));
+  void forEachContinue(void action(HBreak instruction, LocalsHandler locals));
   void close();
   List<LabelElement> labels();
 }
@@ -624,56 +629,81 @@ interface BreakHandler default BreakHandlerImpl {
 // Inert break handler used to avoid null checks when a loop isn't

[ngeoffray, 2012/03/19 11:42:06]

Inert -> Insert

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Done.

 // used as the target of a break, and therefore doesn't need a break
 // handler associated with it.

[ngeoffray, 2012/03/19 11:42:06]

Please update description now that you support switch.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Done.

-class NullBreakHandler implements BreakHandler {
-  const NullBreakHandler();
-  void addBreak(HBreak breakInstruction, LocalsHandler locals) {
-    unreachable();
-  }
+class NullJumpHandler implements JumpHandler {
+  const NullJumpHandler();
+  void generateBreak([LabelElement label]) { unreachable(); }
+  void generateContinue([LabelElement label]) { unreachable(); }
   void forEachBreak(Function ignored) { }
+  void forEachContinue(Function ignored) { }
   void close() { }
   List<LabelElement> labels() => const <LabelElement>[];
 }
 
 // Records breaks until a target block is available.
 // Breaks are always forward jumps.

[ngeoffray, 2012/03/19 11:42:06]

Ditto

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Done.

-class BreakHandlerImpl implements BreakHandler {
-  final BreakHandler previous;
+class JumpHandlerImpl implements JumpHandler {
+  final JumpHandler previous;
   final SsaBuilder builder;
   final TargetElement target;
-  final List<BreakHandlerEntry> breaks;
-  BreakHandlerImpl(SsaBuilder builder, this.target)
+  final List<JumpHandlerEntry> jumps;
+
+  JumpHandlerImpl(SsaBuilder builder, this.target)
       : this.builder = builder,
-        previous = builder.currentBreakHandler,
-        breaks = <BreakHandlerEntry>[] {
-    builder.currentBreakHandler = this;
-    assert(builder.breakTargets[target] === null);
-    builder.breakTargets[target] = this;
+        previous = builder.currentJumpHandler,
+        jumps = <JumpHandlerEntry>[] {
+    builder.currentJumpHandler = this;
+    assert(builder.jumpTargets[target] === null);
+    builder.jumpTargets[target] = this;
   }
 
-  void addBreak(HBreak breakInstruction, LocalsHandler locals) {
-    breaks.add(new BreakHandlerEntry(breakInstruction, locals));
+  void generateBreak([LabelElement label]) {
+    HInstruction breakInstruction;
+    if (label === null) {
+      breakInstruction = new HBreak(target);
+    } else {
+      breakInstruction = new HBreak.toLabel(label);
+    }
+    LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
+    builder.close(breakInstruction);
+    jumps.add(new JumpHandlerEntry(breakInstruction, locals));
+  }
+
+  void generateContinue([LabelElement label]) {
+    HInstruction continueInstruction;
+    if (label === null) {
+      continueInstruction = new HContinue(target);
+    } else {
+      continueInstruction = new HContinue.toLabel(label);
+    }
+    LocalsHandler locals = new LocalsHandler.from(builder.localsHandler);
+    builder.close(continueInstruction);
+    jumps.add(new JumpHandlerEntry(continueInstruction, locals));
   }
 
   void forEachBreak(Function action) {
-    for (BreakHandlerEntry entry in breaks) {
-      action(entry.breakInstruction, entry.locals);
+    for (JumpHandlerEntry entry in jumps) {
+      if (entry.isBreak()) action(entry.jumpInstruction, entry.locals);
+    }
+  }
+
+  void forEachContinue(Function action) {
+    for (JumpHandlerEntry entry in jumps) {
+      if (entry.isContinue()) action(entry.jumpInstruction, entry.locals);
     }
   }
 
   void close() {
-    assert(builder.currentBreakHandler === this);
-    // The mapping from TargetElement to BreakHandler is no longer needed.
-    builder.breakTargets.remove(target);
-    builder.currentBreakHandler = previous;
+    assert(builder.currentJumpHandler === this);
+    // The mapping from StatementElement to JumpHandler is no longer needed.
+    builder.jumpTargets.remove(target);
+    builder.currentJumpHandler = previous;
   }
 
   List<LabelElement> labels() {
     List<LabelElement> result = null;
     for (LabelElement element in target.labels) {
-      if (element.isBreakTarget) {
-        if (result === null) result = <LabelElement>[];
-        result.add(element);
-      }
+      if (result === null) result = <LabelElement>[];
+      result.add(element);
     }
     return (result === null) ? const <LabelElement>[] : result;
   }
@@ -689,7 +719,7 @@ class SsaBuilder implements Visitor {
   LocalsHandler localsHandler;
   HInstruction rethrowableException;
 
-  Map<TargetElement, BreakHandler> breakTargets;
+  Map<TargetElement, JumpHandler> jumpTargets;
 
   // We build the Ssa graph by simulating a stack machine.
   List<HInstruction> stack;
@@ -704,7 +734,10 @@ class SsaBuilder implements Visitor {
 
   // Linked list of active break-handlers. Will be removed in the order
   // they are added.
-  BreakHandler currentBreakHandler = const NullBreakHandler();
+  JumpHandler currentJumpHandler = const NullJumpHandler();
+  // The break handler to use for an upcoming loop statement (temporarily set

[ngeoffray, 2012/03/19 11:42:06]

break -> jump. On the other hand, I think you'll get rid of that field.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

True, this one can go away too (just as the next one).

+  // if a labeled statement is labeling a loop).
+  JumpHandler loopJumpHandler = null;
 
   LibraryElement get currentLibrary() => work.element.getLibrary();
 
@@ -716,7 +749,7 @@ class SsaBuilder implements Visitor {
       elements = work.resolutionTree,
       graph = new HGraph(),
       stack = new List<HInstruction>(),
-      breakTargets = new Map<TargetElement, BreakHandler>() {
+      jumpTargets = new Map<TargetElement, JumpHandler>() {
     localsHandler = new LocalsHandler(this);
   }
 
@@ -875,7 +908,7 @@ class SsaBuilder implements Visitor {
         fieldValues[fieldParameterElement.fieldElement] = parameterValue;
       }
     });
-    
+
     final Map<FunctionElement, TreeElements> constructorElements =
         compiler.resolver.constructorElements;
     List<FunctionElement> constructors = new List<FunctionElement>();
@@ -1029,16 +1062,17 @@ 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.
    */
-  BreakHandler beginLoopHeader(Node node) {
+  JumpHandler beginLoopHeader(Node node) {
     assert(!isAborted());
     HBasicBlock previousBlock = close(new HGoto());
-    BreakHandler breakHandler = getBreakHandler(node);
-    HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels());
+
+    JumpHandler jumpHandler = getLoopJumpHandler(node);
+    HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(jumpHandler.labels());
     previousBlock.addSuccessor(loopEntry);
     open(loopEntry);
 
     localsHandler.beginLoopHeader(node, loopEntry);
-    return breakHandler;
+    return jumpHandler;
   }
 
   /**
@@ -1049,12 +1083,12 @@ class SsaBuilder implements Visitor {
    */
   void endLoop(HBasicBlock loopEntry,
                HBasicBlock branchBlock,
-               BreakHandler breakHandler,
+               JumpHandler jumpHandler,
                LocalsHandler savedLocals) {
     HBasicBlock loopExitBlock = addNewBlock();
     assert(branchBlock.successors.length == 1);
     List<LocalsHandler> breakLocals = <LocalsHandler>[];
-    breakHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
+    jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
       breakInstruction.block.addSuccessor(loopExitBlock);
       breakLocals.add(locals);
     });
@@ -1070,7 +1104,10 @@ class SsaBuilder implements Visitor {
   }
 
   // For while loops, initializer and update are null.
-  visitLoop(Node loop, Node initializer, Expression condition, NodeList updates,
+  visitLoop(Node loop,
+            Node initializer,
+            Expression condition,
+            NodeList updates,
             Node body) {
     // Generate:
     //  <initializer>
@@ -1096,7 +1133,7 @@ class SsaBuilder implements Visitor {
     }
     assert(!isAborted());
 
-    BreakHandler breakHandler = beginLoopHeader(loop);
+    JumpHandler jumpHandler = beginLoopHeader(loop);
     HBasicBlock conditionBlock = current;
 
     HInstruction conditionInstruction;
@@ -1114,23 +1151,44 @@ class SsaBuilder implements Visitor {
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
     // The body.
-    HBasicBlock bodyBlock = addNewBlock();
-    conditionExitBlock.addSuccessor(bodyBlock);
-    open(bodyBlock);
+    HBasicBlock beginBodyBlock = addNewBlock();
+    conditionExitBlock.addSuccessor(beginBodyBlock);
+    open(beginBodyBlock);
 
     localsHandler.enterLoopBody(loop);
+
     hackAroundPossiblyAbortingBody(body);
-    bodyBlock = close(new HGoto());
+    SubGraph bodyGraph = new SubGraph(beginBodyBlock, current);
+    HBasicBlock bodyBlock = close(new HGoto());
 
     // Update.
     // We create an update block, even when we are in a while loop. There the
     // 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();
+
+    List<LocalsHandler> continueLocals = <LocalsHandler>[];

[ngeoffray, 2012/03/19 11:42:06]

Please explain why this isn't done in endLoop.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Because endLoop is also used by DoWhile, which isn't handled yet. It'll probably
be moved to endLoop when this is all done.

+    jumpHandler.forEachContinue((HContinue instruction, LocalsHandler locals) {
+      instruction.block.addSuccessor(updateBlock);
+      continueLocals.add(locals);
+    });
     bodyBlock.addSuccessor(updateBlock);
+    continueLocals.add(localsHandler);
+
     open(updateBlock);
 
+    localsHandler = localsHandler.mergeMultiple(continueLocals, updateBlock);
+
+    HLabeledBlockInformation labelInfo;
+    List<LabelElement> labels = jumpHandler.labels();
+    if (!labels.isEmpty()) {
+      beginBodyBlock.labeledBlockInformation =
+          new HLabeledBlockInformation(bodyGraph, updateBlock,
+                                       jumpHandler.labels(), isContinue: true);
+    }
+
     localsHandler.enterLoopUpdates(loop);
+
     if (updates !== null) {
       for (Expression expression in updates) {
         visit(expression);
@@ -1145,7 +1203,7 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals);
+    endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
   }
 
   visitFor(For node) {
@@ -1159,7 +1217,7 @@ class SsaBuilder implements Visitor {
 
   visitDoWhile(DoWhile node) {
     localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
+    JumpHandler jumpHandler = beginLoopHeader(node);
     HBasicBlock loopEntryBlock = current;
 
     localsHandler.enterLoopBody(node);
@@ -1170,6 +1228,10 @@ class SsaBuilder implements Visitor {
     HBasicBlock bodyExitBlock = close(new HGoto());
     HBasicBlock conditionBlock = addNewBlock();
     bodyExitBlock.addSuccessor(conditionBlock);
+    jumpHandler.forEachContinue((x,y) {
+      // TODO(lrn): Handle continue in do-while loops.
+      compiler.cancel("do-while with continue", node: node);
+    });
     open(conditionBlock);
     visit(node.condition);
     assert(!isAborted());
@@ -1179,7 +1241,8 @@ class SsaBuilder implements Visitor {
     conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
     loopEntryBlock.postProcessLoopHeader();
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler, localsHandler);
+    endLoop(loopEntryBlock, conditionBlock, jumpHandler, localsHandler);
+    jumpHandler.close();
   }
 
   visitFunctionExpression(FunctionExpression node) {
@@ -2113,30 +2176,45 @@ class SsaBuilder implements Visitor {
     assert(!isAborted());
     TargetElement target = elements[node];
     assert(target !== null);
-    BreakHandler handler = breakTargets[target];
+    JumpHandler handler = jumpTargets[target];
     assert(handler !== null);
-    LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
-    HBreak breakInstruction;
     if (node.target === null) {
-      breakInstruction = new HBreak(target);
+      handler.generateBreak();

[ngeoffray, 2012/03/19 11:42:06]

I think I'd prefer something like:
handler.generateBreak(node.target === null ? null : elements[node.target]).

It would also get rid of the optional parameter.

It's a matter of style, so your choice.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

I generally find the conditional operator harder to read than proper if/else.
I'll keep this.
Also, it would probably be a type warning to inline it without "casting"
elements[node.target] to LabelElement.

     } else {
       LabelElement label = elements[node.target];
-      breakInstruction = new HBreak.toLabel(label);
+      handler.generateBreak(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');
+    work.allowSpeculativeOptimization = false;
+    assert(!isAborted());

[ngeoffray, 2012/03/19 11:42:06]

I'd get rid of that assert, since the method that visits a block does not have
an abort block when visiting an individual instruction.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Done.

+    TargetElement target = elements[node];
+    assert(target !== null);
+    JumpHandler handler = jumpTargets[target];
+    assert(handler !== null);
+    if (node.target === null) {
+      handler.generateContinue();
+    } else {
+      LabelElement label = elements[node.target];
+      handler.generateContinue(label);
+    }
   }
 
-  BreakHandler getBreakHandler(Node node) {
-    TargetElement element = elements[node];
-    if (element === null) return const NullBreakHandler();
-    return new BreakHandler(this, element);
+  JumpHandler getLoopJumpHandler(Loop node) {

[ngeoffray, 2012/03/19 11:42:06]

Please consider what we discussed and remove this function.

[Lasse Reichstein Nielsen, 2012/03/19 12:13:58]

Renamed to createJumpHandler, and always creates something.
Still used in two places, so I'd like to share the code.

+    if (loopJumpHandler === null) {
+      // No labels on the loop.
+      TargetElement element = elements[node];
+      if (element === null) {
+        // No unlabeled breaks or continues on the loop either.
+        return const NullJumpHandler();
+      }
+      return new JumpHandler(this, element);
+    }
+    // Use the jump handler created for the labels for the loop too.
+    JumpHandler handler = loopJumpHandler;
+    loopJumpHandler = null;
+    return handler;
   }
 
   visitForInStatement(ForInStatement node) {
@@ -2161,7 +2239,7 @@ class SsaBuilder implements Visitor {
         selector, iteratorName, false, inputs);
     add(iterator);
 
-    BreakHandler breakHandler = beginLoopHeader(node);
+    JumpHandler jumpHandler = beginLoopHeader(node);
     HBasicBlock conditionBlock = current;
 
     // The condition.
@@ -2195,11 +2273,18 @@ class SsaBuilder implements Visitor {
     hackAroundPossiblyAbortingBody(node.body);
     bodyBlock = close(new HGoto());
 
+    jumpHandler.forEachContinue((x,y) {
+      // TODO(lrn): Handle continue in for-in.
+      // TODO(lrn): Or, preferably, use an abstraction of visitLoop for for-in.
+      compiler.cancel('for-in with continue', node: node);
+    });
+
     // Update.
     // We create an update block, even if we are in a for-in loop. The
     // 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());
@@ -2207,8 +2292,8 @@ class SsaBuilder implements Visitor {
     updateBlock.addSuccessor(conditionBlock);
     conditionBlock.postProcessLoopHeader();
 
-    endLoop(conditionBlock, conditionExitBlock, breakHandler, savedLocals);
-    breakHandler.close();
+    endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
+    jumpHandler.close();
   }
 
   visitLabeledStatement(LabeledStatement node) {
@@ -2230,7 +2315,7 @@ class SsaBuilder implements Visitor {
     }
     LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler);
     assert(targetElement.isBreakTarget);
-    BreakHandler handler = new BreakHandler(this, targetElement);
+    JumpHandler handler = new JumpHandler(this, targetElement);
     // Introduce a new basic block.
     HBasicBlock entryBlock = graph.addNewBlock();
     goto(current, entryBlock);
@@ -2300,7 +2385,10 @@ class SsaBuilder implements Visitor {
     }
     Link<Node> cases = node.cases.nodes;
 
-    BreakHandler breakHandler = getBreakHandler(node);
+    // TODO(lrn): Rename getLoopJumpHandler to also match switches.
+    // OR make it always create the handler, instead of letting
+    // the LabeledStatement do it.
+    JumpHandler jumpHandler = getLoopJumpHandler(node);
 
     buildSwitchCases(cases, expression);
 
@@ -2309,7 +2397,7 @@ class SsaBuilder implements Visitor {
     // Create merge block for break targets.
     HBasicBlock joinBlock = new HBasicBlock();
     List<LocalsHandler> caseLocals = <LocalsHandler>[];
-    breakHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
+    jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
       instruction.block.addSuccessor(joinBlock);
       caseLocals.add(locals);
     });
@@ -2336,6 +2424,7 @@ class SsaBuilder implements Visitor {
         new SubGraph(startBlock, lastBlock),
         joinBlock,
         elements[node]);
+    jumpHandler.close();
   }