Generate prettier loops.

frog/leg/ssa/codegen.dart

Index: frog/leg/ssa/codegen.dart
diff --git a/frog/leg/ssa/codegen.dart b/frog/leg/ssa/codegen.dart
index 95645915f20bda1928b321b59942120d5501bc57..1b0ce802a02a72acc97155ab447fbe0f4ab58364 100644
--- a/frog/leg/ssa/codegen.dart
+++ b/frog/leg/ssa/codegen.dart
@@ -80,6 +80,18 @@ class SsaCodeGeneratorTask extends CompilerTask {
 typedef void ElementAction(Element element);
 
 class SsaCodeGenerator implements HVisitor {
+  /**
+   * Current state for generating simple (non-local-control) code.
+   * It is generated as either statements (indented and ';'-terminated),
+   * expressions (comma separated) or declarations (also comma separated,
+   * but expected to be preceeded by a 'var' so it declares its variables);
+   */
+  static final int STATE_STATEMENT = 0;
+  static final int STATE_FIRST_EXPRESSION = 1;
+  static final int STATE_FIRST_DECLARATION = 2;

[floitsch, 2012/03/28 04:03:48]

FIRST_DECLARATION and STATE_DECLARATION are unused.

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Yes. They are preparing for including the initializer part of a for loop.

+  static final int STATE_EXPRESSION = 3;
+  static final int STATE_DECLARATION = 4;
+
   final Compiler compiler;
   final WorkItem work;
   final StringBuffer buffer;
@@ -97,11 +109,21 @@ class SsaCodeGenerator implements HVisitor {
   int indent = 0;
   int expectedPrecedence = JSPrecedence.STATEMENT_PRECEDENCE;
   HGraph currentGraph;
+  /**
+   * Whether the code-generation should try to generate an expression
+   * instead of a sequence of statements.
+   */
+  int generationState = STATE_STATEMENT;
+  /**
+   * While generating expressions, we can't insert variable declarations.
+   * Instead we declare them at the end of the function
+   */
+  Link<String> delayedVarDecl = const EmptyLink<String>();
   HBasicBlock currentBlock;
 
   // Records a block-information that is being handled specially.
   // Used to break bad recursion.
-  HLabeledBlockInformation currentBlockInformation;
+  HBlockInformation currentBlockInformation;
   // The subgraph is used to delimit traversal for some constructions, e.g.,
   // if branches.
   SubGraph subGraph;
@@ -174,6 +196,17 @@ class SsaCodeGenerator implements HVisitor {
     subGraph = new SubGraph(graph.entry, graph.exit);
     beginGraph(graph);
     visitBasicBlock(graph.entry);
+    if (!delayedVarDecl.isEmpty()) {
+      addIndentation();
+      buffer.add("var ");
+      while (true) {
+        buffer.add(delayedVarDecl.head);
+        delayedVarDecl = delayedVarDecl.tail;
+        if (delayedVarDecl.isEmpty()) break;
+        buffer.add(", ");
+      }
+      buffer.add(";\n");
+    }
     endGraph(graph);
   }
 
@@ -184,6 +217,54 @@ class SsaCodeGenerator implements HVisitor {
     subGraph = oldSubGraph;
   }
 
+  bool isExpression(SubGraph limits) {
+    HBasicBlock basicBlock = limits.start;
+    do {
+      HInstruction current = basicBlock.first;
+      while (current != basicBlock.last) {
+        // E.g, BailoutTarget.

[ngeoffray, 2012/03/28 15:28:04]

BailoutTarget does not exist anymore.

+        if (current.isControlFlow()) {
+          print("[isExpression FAIL: $current]");

[floitsch, 2012/03/28 04:03:48]

debug code?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Ah, yes. Will remove them all.

+          return false;
+        }
+        current = current.next;
+      }
+      if (current is HGoto) {
+        basicBlock = basicBlock.successors[0];
+      } else if (current is HConditionalBranch) {
+        if (generateAtUseSite.contains(current)) {
+          // Short-circuit logical operator trickery.
+          // Check the second half, which will continue into the join.

[floitsch, 2012/03/28 04:03:48]

Isn't the second half successors[1]?
Can't we just jump to the join-node?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

No, successors[1] is the join node, the first half is inputs[0].

Checking the second half is really a sanity check. It should be all expressions
or we wouldn't have made the logical operation inlinable anyway. I prefer not to
rely too much on the preconditions for the current state (i.e., the
HConditionalBranch is generateAtUseSite - I allow myself to know what that
means, but not to make assumptions about how it was decided).

[floitsch, 2012/03/29 21:44:10]

Right... missed that. Please add as comment.

[Lasse Reichstein Nielsen, 2012/03/30 09:37:17]

Done.

+          basicBlock = basicBlock.successors[0];
+        } else {
+          // We allow an expression to end on an HIf (a condition expression).
+          if (basicBlock !== limits.end) print("[isExpression IF_FAIL: $current]");

[floitsch, 2012/03/28 04:03:48]

debug code?

+          return basicBlock === limits.end;
+        }
+      } else {
+        print("[isExpression CC-FAIL: $current");

[floitsch, 2012/03/28 04:03:48]

debug code?

+        // Expression-incompatible control flow.
+        return false;
+      }
+    } while (limits.contains(basicBlock));
+    return true;
+  }
+
+  bool isCondition(SubGraph limits) {
+    return isExpression(limits) && (limits.end.last is HConditionalBranch);
+  }
+
+  void visitExpressionGraph(SubGraph subGraph) {
+    int oldState = generationState;
+    generationState = STATE_FIRST_EXPRESSION;
+    visitSubGraph(subGraph);
+    generationState = oldState;
+  }
+
+  void visitConditionGraph(SubGraph subGraph) {
+    visitExpressionGraph(subGraph);
+  }
+
   String temporary(HInstruction instruction) {
     int id = instruction.id;
     String name = names[id];
@@ -240,9 +321,53 @@ class SsaCodeGenerator implements HVisitor {
     buffer.add(')');
   }
 
+
+
+  /**
+   * Whether we are currently generating expressions instead of statements.
+   * This includes declarations, which are generated as expressions.
+   */
+  bool isGeneratingExpression() {
+    return generationState != STATE_STATEMENT;
+  }
+
+  /**
+   * Whether we are generating a declaration.
+   */
+  bool isGeneratingDeclaration() {
+    assert(generationState != STATE_STATEMENT);
+    return (generationState & 0x01) == 0;

[floitsch, 2012/03/28 04:03:48]

magic constant.
I don't see generationState as a bitfield. Is this just to avoid to test against
two constants?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Yep. Fixed.

+  }
+
+  /**
+   * Called before writing an expression.
+   * Ensures that expressions are comma spearated.
+   */
+  void addExpressionSeparator() {
+    if (generationState <= STATE_FIRST_DECLARATION) {

[floitsch, 2012/03/28 04:03:48]

if (generationState == STATE_FIRST_EXPRESSION) generationState = ...
else if (gen...

Your comment explains this, but I still need to verify it, and it is more
brittle (if we ever change the state).

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

+      // From STATE_FIRST_EXPRESSION to STATE_EXPRESSION or from
+      // STATE_FIRST_DECLARATION to STATE_DECLARATION.
+      generationState += 2;
+    } else {
+      buffer.add(", ");
+    }
+  }
+
   void define(HInstruction instruction) {
-    buffer.add('var ${temporary(instruction)} = ');
-    visit(instruction, JSPrecedence.ASSIGNMENT_PRECEDENCE);
+    String temporaryVar = temporary(instruction);
+    if (isGeneratingExpression()) {
+      // As expression.
+      if (!isGeneratingDeclaration()) {
+        delayedVarDecl = delayedVarDecl.prepend(temporaryVar);
+      }
+      addExpressionSeparator();
+      buffer.add('$temporaryVar = ');
+      visit(instruction, JSPrecedence.ASSIGNMENT_PRECEDENCE);
+    } else {
+      // As statement.
+      buffer.add('var $temporaryVar = ');
+      visit(instruction, JSPrecedence.ASSIGNMENT_PRECEDENCE);
+    }
   }
 
   void use(HInstruction argument, int expectedPrecedence) {
@@ -363,7 +488,101 @@ class SsaCodeGenerator implements HVisitor {
     endExpression(operatorPrecedence.precedence);
   }
 
-  visitBasicBlock(HBasicBlock node) {
+  bool handleLoop(HBasicBlock node) {
+    assert(node.isLoopHeader());
+    HLoopInformation info = node.loopInformation;
+    SubExpression condition = info.condition;
+    print("LOOP: [${["WHILE","FOR","DO-WHILE","FOR-IN"][info.type]}]");

[floitsch, 2012/03/28 04:03:48]

debug code?

+    if (isCondition(condition)) {
+      print("--[Condition is Expression!]");
+      switch (info.type) {
+        case HLoopInformation.WHILE_LOOP:
+        case HLoopInformation.FOR_IN_LOOP: {
+          addIndentation();
+          for (LabelElement label in info.labels) {
+            writeLabel(label);
+            buffer.add(":");
+          }
+          buffer.add("while (");
+          visitConditionGraph(condition);
+          buffer.add(") {\n");
+          indent++;
+          visitSubGraph(info.body);
+          if (info.updates !== null) {
+            // Even in while loops the updates block may be needed to
+            // handle phi nodes of its successors.
+            visitSubGraph(info.updates);
+          }
+          indent--;
+          addIndentation();
+          buffer.add("}\n");
+          break;
+        }
+        case HLoopInformation.FOR_LOOP: {
+          // TODO(lrn): Find a way to put initialization into the for.
+          // It's currently handled before we reach the [HLoopInformation].
+          addIndentation();
+          for (LabelElement label in info.labels) {
+            if (label.isTarget) {
+              writeLabel(label);
+              buffer.add(":");
+            }
+          }
+          buffer.add("for(;");
+          visitConditionGraph(info.condition);
+          buffer.add(";");
+          if (isExpression(info.updates)) {
+            visitExpressionGraph(info.updates);
+            buffer.add(") {\n");
+            indent++;
+            visitSubGraph(info.body);
+            indent--;
+            addIndentation();
+            buffer.add("}\n");
+          } else {
+            buffer.add(") {\n");
+            indent++;
+            if (info.target !== null && info.target.isContinueTarget) {
+              addIndentation();
+              for (LabelElement label in info.labels) {
+                if (label.isContinueTarget) {
+                  writeContinueLabel(label);
+                  buffer.add(":");
+                  continueActions[label] = continueAsBreak;

[floitsch, 2012/03/28 04:03:48]

continueAction.
Add test.

+                }
+              }
+              addImplicitContinueLabel();
+              buffer.add(":{\n");
+              continueAction[info.target] = implicitContinueAsBreak;
+              indent++;

[floitsch, 2012/03/28 04:03:48]

move indent++ closer to "{" ?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Refactored away.

+            }
+            visitSubGraph(info.body);

[floitsch, 2012/03/28 04:03:48]

I would keep the 'if' open and duplicate the 'visitSubGraph' line:
if (info.target === null || !info.target.isContinueTarget) {
  visitSubGraph(info.body);
} else {
  ...
  visitSubGraph(info.body);
  ...
}

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

+            if (info.target !== null && info.target.isContinueTarget) {
+              indent--;
+              buffer.add("}\n");
+              continueAction.remove(info.target);
+              for (LabelElement label in info.labels) {
+                if (label.isContinueTarget) {
+                  continueAction.remove(label);
+                }
+              }
+            }
+            visitSubGraph(info.updates);
+            indent--;
+            buffer.add("}\n");
+          }
+          break;
+        }
+        case HLoopInformation.DO_WHILE_LOOP:
+        default:
+          return false;

[floitsch, 2012/03/28 04:03:48]

I don't like these "return false/true" where it is difficult to see what
condition succeeded/failed to get to this line.
Maybe add a "bool succeeded = false" in the beginning and update it, when we
were able to handle it.

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

+      }
+      return true;
+    }
+    return false;
+  }
+
+  void visitBasicBlock(HBasicBlock node) {
     // Abort traversal if we are leaving the currently active sub-graph.
     if (!subGraph.contains(node)) return;
 
@@ -373,21 +592,32 @@ class SsaCodeGenerator implements HVisitor {
     // don't handle it again.
     if (node.hasLabeledBlockInformation() &&
         node.labeledBlockInformation !== currentBlockInformation) {
-      HLabeledBlockInformation oldBlockInformation = currentBlockInformation;
+      HBlockInformation oldBlockInformation = currentBlockInformation;
       currentBlockInformation = node.labeledBlockInformation;
       handleLabeledBlock(currentBlockInformation);
       currentBlockInformation = oldBlockInformation;
       return;
     }
 
-    currentBlock = node;
-
-    if (node.isLoopHeader()) {
-      // While loop will be closed by the conditional loop-branch.
-      // TODO(floitsch): HACK HACK HACK.

[floitsch, 2012/03/28 04:03:48]

WOOT!!! ;)

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Don't be too happy, the code is still there as a fallback in case the handleLoop
can't do it's job.

Eventually, I want to move the fall-back code to handleLoop too, and do it using
subgraphs, but it's not there yet.

+    if (node.isLoopHeader() &&
+        node.loopInformation !== currentBlockInformation) {
+      HBlockInformation oldBlockInformation = currentBlockInformation;
+      currentBlockInformation = node.loopInformation;
+      if (handleLoop(node)) {

[floitsch, 2012/03/28 04:03:48]

not a strong preference but I would prefer:
bool succeededNiceLoop = handleLoop(node);
currentBlockinformation = oldBlockInformation;
if (succeededNiceLoop) {
  visitBasicBlock(node.loopInformation.joinBlock);
  return;
}

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

+        currentBlockInformation = oldBlockInformation;
+        visitBasicBlock(node.loopInformation.joinBlock);
+        return;
+      }
+      currentBlockInformation = oldBlockInformation;
       beginLoop(node);
     }
 
+    iterateBasicBlock(node);
+  }
+
+  void iterateBasicBlock(HBasicBlock node) {
+    currentBlock = node;
+    bool firstExpression = true;

[floitsch, 2012/03/28 04:03:48]

unused variable.

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

     HInstruction instruction = node.first;
     while (instruction != null) {
       if (instruction === node.last) {
@@ -398,15 +628,30 @@ class SsaCodeGenerator implements HVisitor {
             // In case the phi is being generated by another
             // instruction.
             if (isLogicalOperation && isGenerateAtUseSite(phi)) return;
-            addIndentation();
-            if (!temporaryExists(phi)) buffer.add('var ');
-            buffer.add('${temporary(phi)} = ');
+            if (isGeneratingExpression()) {
+              addExpressionSeparator();
+              String temporaryVar;
+              if (!temporaryExists(phi) && !isGeneratingDeclaration()) {
+                temporaryVar = temporary(phi);
+                delayedVarDecl = delayedVarDecl.prepend(temporaryVar);
+              } else {
+                temporaryVar = temporary(phi);
+              }
+              buffer.add(temporaryVar);
+              buffer.add(" = ");
+            } else {
+              addIndentation();
+              if (!temporaryExists(phi)) buffer.add('var ');
+              buffer.add('${temporary(phi)} = ');
+            }
             if (isLogicalOperation) {
               emitLogicalOperation(phi, logicalOperations[phi]);
             } else {
               use(phi.inputs[index], JSPrecedence.ASSIGNMENT_PRECEDENCE);
             }
-            buffer.add(';\n');
+            if (!isGeneratingExpression()) {
+              buffer.add(';\n');
+            }
           });
         }
       }
@@ -415,18 +660,23 @@ class SsaCodeGenerator implements HVisitor {
         visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
         return;
       } else if (!isGenerateAtUseSite(instruction)) {
-        if (instruction is !HIf && instruction is !HBailoutTarget) {
+        if (instruction is !HIf && instruction is !HBailoutTarget &&
+            !isGeneratingExpression()) {
           addIndentation();
         }
         if (instruction.usedBy.isEmpty()
             || instruction is HTypeGuard
             || instruction is HCheck) {
+          if (isGeneratingExpression()) {
+            addExpressionSeparator();
+          }
           visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
         } else {
           define(instruction);
         }
         // Control flow instructions know how to handle ';'.
-        if (instruction is !HControlFlow && instruction is !HBailoutTarget) {
+        if (instruction is! HControlFlow && instruction is! HBailoutTarget &&
+            !isGeneratingExpression()) {
           buffer.add(';\n');
         }
       } else if (instruction is HIf) {
@@ -646,6 +896,13 @@ class SsaCodeGenerator implements HVisitor {
   }
 
   visitIf(HIf node) {
+    if (isGeneratingExpression()) {

[floitsch, 2012/03/28 04:03:48]

can you give an example when this is happening?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

When we are expression-generating the condition of a loop (via
visitConditionSubGraph(SubGraph)).

[floitsch, 2012/03/29 21:44:10]

But then it should be a loop-condition and end with a LoopBranch. When is this
not the case?

[Lasse Reichstein Nielsen, 2012/03/30 09:37:17]

True. A HIf is only part of an expression if it's a logical operator, and that's
handled elsewhere.
I'll remove this.

+      assert(node.block == subGraph.end);
+      // We are generating an expression for a condition.
+      addExpressionSeparator();
+      use(node.inputs[0], JSPrecedence.EXPRESSION_PRECEDENCE);
+      return;
+    }
     List<HBasicBlock> dominated = node.block.dominatedBlocks;
     HIfBlockInformation info = node.blockInformation;
     startIf(node);
@@ -787,6 +1044,7 @@ class SsaCodeGenerator implements HVisitor {
   }
 
   visitFieldSet(HFieldSet node) {
+    bool delayDeclaration = false;

[ngeoffray, 2012/03/28 15:28:04]

Please add a comment on why FieldSet needs to participate so actively in the
delayed variable declaration.

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Even better, instead of deferring it to a later cleanup, I have abstracted the
var-introduction into a separate method. Made everything much more readable.

     if (node.receiver !== null) {
       beginExpression(JSPrecedence.ASSIGNMENT_PRECEDENCE);
       use(node.receiver, JSPrecedence.MEMBER_PRECEDENCE);
@@ -794,10 +1052,15 @@ class SsaCodeGenerator implements HVisitor {
     } else {
       // TODO(ngeoffray): Remove the 'var' once we don't globally box
       // variables used in a try/catch.
-      buffer.add('var ');
+      if (isGeneratingExpression()) {
+        delayDeclaration = !isGeneratingDeclaration();
+      } else {
+        buffer.add('var ');
+      }
     }
     String name = JsNames.getValid(node.element.name.slowToString());
     buffer.add(name);
+    if (delayDeclaration) delayedVarDecl = delayedVarDecl.prepend(name);
     buffer.add(' = ');
     use(node.value, JSPrecedence.ASSIGNMENT_PRECEDENCE);
     if (node.receiver !== null) {
@@ -861,6 +1124,12 @@ class SsaCodeGenerator implements HVisitor {
   }
 
   visitLoopBranch(HLoopBranch node) {
+    if (subGraph !== null && node.block == subGraph.end) {

[ngeoffray, 2012/03/28 15:28:04]

How can that happen? Please add a comment.

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

Done.

+      if (isGeneratingExpression()) {

[floitsch, 2012/03/28 04:03:48]

when can we enter here, but not generate an expression?

[Lasse Reichstein Nielsen, 2012/03/29 13:09:38]

We can't yet.
Eventually I'll want to handle loops with non-expression-able conditions using
subgraph traversal too, and then we'll get here when traversing the condition
subgraph as statements.

Should I remove the special case here and always use the condition expression at
the visitExpressionSubGraph call point?

[floitsch, 2012/03/29 21:44:10]

If we can't reach this unless it's an expression, make it an internal error if
it is not an expression. You won't lose any code, and it will be easy to change
once it can happen.

[Lasse Reichstein Nielsen, 2012/03/30 09:37:17]

Done.

+        use(node.inputs[0], JSPrecedence.EXPRESSION_PRECEDENCE);
+      }
+      return;
+    }
     HBasicBlock branchBlock = currentBlock;
     handleLoopCondition(node);
     List<HBasicBlock> dominated = currentBlock.dominatedBlocks;
@@ -1437,6 +1706,8 @@ class SsaUnoptimizedCodeGenerator extends SsaCodeGenerator {
     setup.add('  }\n');
   }
 
+  bool handleLoop(HBasicBlock node) => false;
+
   void visitTypeGuard(HTypeGuard guard) {
     compiler.internalError('Type guard in an unoptimized method');
   }