Refactor SsaBranchBuilder.

lib/compiler/implementation/ssa/builder.dart

Index: lib/compiler/implementation/ssa/builder.dart
diff --git a/lib/compiler/implementation/ssa/builder.dart b/lib/compiler/implementation/ssa/builder.dart
index 4041d33c8e79866db86cb2f6cb5e629ffde6f46a..7b2be83f65003bd5efa28f4c80799d4b03a683ef 100644
--- a/lib/compiler/implementation/ssa/builder.dart
+++ b/lib/compiler/implementation/ssa/builder.dart
@@ -588,11 +588,8 @@ 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.
+   * If a phi node is necessary, it will use this handler's instruction as the
+   * first input, and the otherLocals instruction as the second.
    */
   void mergeWith(LocalsHandler otherLocals, HBasicBlock joinBlock) {
     // If an element is in one map but not the other we can safely
@@ -613,7 +610,7 @@ class LocalsHandler {
           joinedLocals[element] = instruction;
         } else {
           HInstruction phi =
-              new HPhi.manyInputs(element, <HInstruction>[instruction, mine]);
+              new HPhi.manyInputs(element, <HInstruction>[mine, instruction]);
           joinBlock.addPhi(phi);
           joinedLocals[element] = phi;
         }
@@ -3391,21 +3388,20 @@ class StringBuilderVisitor extends AbstractVisitor {
   }
 }
 
+class SsaBranch {
+  final SsaBranchBuilder branchBuilder;
+  final HBasicBlock block;
+  LocalsHandler startLocals;
+  LocalsHandler exitLocals;
+  SubGraph graph;
+
+  SsaBranch(this.branchBuilder) : block = new HBasicBlock();
+}
+
 class SsaBranchBuilder {
   final SsaBuilder builder;
   final Node diagnosticNode;
 
-  bool branchesHaveValues;
-  HInstruction thenValue;
-  HInstruction elseValue;
-  // The locals-handler at the end of the condition block.
-  LocalsHandler conditionLocals;
-  LocalsHandler thenLocals;
-  LocalsHandler elseLocals;
-  SubGraph conditionGraph;
-  SubGraph thenGraph;
-  SubGraph elseGraph;
-
   SsaBranchBuilder(this.builder, [this.diagnosticNode]);
 
   Compiler get compiler() => builder.compiler;
@@ -3416,95 +3412,85 @@ class SsaBranchBuilder {
     }
   }
 
-  SubGraph buildCondition(void doCondition()) {
-    HBasicBlock conditionStartBlock = builder.openNewBlock();
-    doCondition();
+  void buildCondition(void visitCondition(),
+                      SsaBranch conditionBranch,
+                      SsaBranch thenBranch,
+                      SsaBranch elseBranch) {
+    startBranch(conditionBranch);
+    visitCondition();
     checkNotAborted();
     assert(builder.current === builder.lastOpenedBlock);
-    HInstruction condition = builder.popBoolified();
-    HIf branch = new HIf(condition);
+    HInstruction conditionValue = builder.popBoolified();
+    HIf branch = new HIf(conditionValue);
+    HBasicBlock conditionExitBlock = builder.current;
     builder.close(branch);
-
-    conditionGraph =
-        new SubExpression(conditionStartBlock, builder.lastOpenedBlock);
-    conditionLocals = builder.localsHandler;
-    return conditionGraph;
+    conditionBranch.exitLocals = builder.localsHandler;
+    conditionExitBlock.addSuccessor(thenBranch.block);
+    conditionExitBlock.addSuccessor(elseBranch.block);
+    bool copied = mergeLocals(conditionBranch, thenBranch, needsCopy: false);
+    mergeLocals(conditionBranch, elseBranch, needsCopy: !copied);
+
+    conditionBranch.graph =
+        new SubExpression(conditionBranch.block, conditionExitBlock);
+  }
+
+  /** Returns true if the locals have been copied. */

[Lasse Reichstein Nielsen, 2012/07/11 12:10:53]

What does it mean to "have been copied"?
Can we use the originals again, or can't we? I'm *guessing* that "have been
copied" means that the original is free to be reused.

Generally, the "copy" word doesn't carry much meaning, it's referring to a
technical thing we do in some cases, but not to why we do it or what it means.
Is there a better term?
E.g., this function returns true if the fromBranch's exitLocals have not been
modified or stored, so they are free to reuse.
The "needsCopy" could be reversed to "mayReuse" with a comment that it refers to
fromBranch.exitLocals. And the return value can be reversed to mean "did reuse".

[floitsch, 2012/07/11 12:24:19]

Did not change the return type, but inverted the argument. Now
"mayReuseFromLocals".

+  bool mergeLocals(SsaBranch fromBranch, SsaBranch toBranch, [needsCopy]) {

[Lasse Reichstein Nielsen, 2012/07/11 12:10:53]

Type 'bool' on needsCopy.

[floitsch, 2012/07/11 12:24:19]

Done.

+    LocalsHandler fromLocals = fromBranch.exitLocals;
+    if (toBranch.startLocals == null) {
+      if (needsCopy) {
+        toBranch.startLocals = new LocalsHandler.from(fromLocals);
+        return true;
+      } else {
+        toBranch.startLocals = fromLocals;
+        return false;
+      }
+    } else {
+      toBranch.startLocals.mergeWith(fromLocals, toBranch.block);
+      return true;
+    }
   }
 
-  SubGraph buildThen(void visitThen(), LocalsHandler locals) {
-    builder.localsHandler = locals;
-    HBasicBlock thenBlock = builder.addNewBlock();
-    conditionGraph.end.addSuccessor(thenBlock);
-    builder.open(thenBlock);
-    visitThen();
-    if (branchesHaveValues) {
-      checkNotAborted();
-      thenValue = builder.pop();
-    }
-    thenGraph = new SubGraph(thenBlock, builder.lastOpenedBlock);
-    thenLocals = builder.localsHandler;
-    return thenGraph;
+  void startBranch(SsaBranch branch) {
+    builder.graph.addBlock(branch.block);
+    builder.localsHandler = branch.startLocals;
+    builder.open(branch.block);
   }
 
-  SubGraph buildElse(void visitElse(), LocalsHandler locals) {
-    builder.localsHandler = locals;
-    HBasicBlock elseBlock = builder.addNewBlock();
-    conditionGraph.end.addSuccessor(elseBlock);
-    builder.open(elseBlock);
-    visitElse();
-    if (branchesHaveValues) {
+  HInstruction buildBranch(SsaBranch branch,
+                           void visitBranch(),
+                           SsaBranch joinBranch,
+                           bool isExpression) {
+    startBranch(branch);
+    visitBranch();
+    branch.graph = new SubGraph(branch.block, builder.lastOpenedBlock);
+    branch.exitLocals = builder.localsHandler;
+    if (!builder.isAborted()) {
+      builder.goto(builder.current, joinBranch.block);
+      mergeLocals(branch, joinBranch, needsCopy: false);
+    }
+    if (isExpression) {
       checkNotAborted();
-      elseValue = builder.pop();
-    }
-    elseGraph = new SubGraph(elseBlock, builder.lastOpenedBlock);
-    elseLocals = builder.localsHandler;
-    return elseGraph;
-  }
-
-  HBasicBlock join() {
-    HBasicBlock joinBlock = null;
-    HBasicBlock thenBlock = thenGraph.end;
-    HBasicBlock elseBlock = elseGraph.end;
-    // If the last instruction is already a control-flow instruction then the
-    // block has been aborted.
-    if (thenBlock.last is HControlFlow) thenBlock = null;
-    if (elseBlock.last is HControlFlow) elseBlock = null;
-
-    if (thenBlock !== null || elseBlock !== null) {
-      joinBlock = builder.addNewBlock();
-      if (thenBlock !== null) builder.goto(thenBlock, joinBlock);
-      if (elseBlock !== null) builder.goto(elseBlock, joinBlock);
-      // If the join block has two predecessors we have to merge the
-      // locals. The current locals is what either the
-      // condition or the else block left us with, so we merge that
-      // with the set of locals we got after visiting the then
-      // part of the if.
-      builder.open(joinBlock);
-      if (joinBlock.predecessors.length == 2) {
-        builder.localsHandler.mergeWith(thenLocals, joinBlock);
-        if (branchesHaveValues) {
-          assert(thenValue !== null);
-          assert(elseValue !== null);
-          HPhi phi = new HPhi.manyInputs(null,
-              <HInstruction>[thenValue, elseValue]);
-          joinBlock.addPhi(phi);
-          builder.stack.add(phi);
-        }
-      } else if (thenBlock !== null) {
-        // The only predecessor is the then branch.
-        builder.localsHandler = thenLocals;
-      } else {
-        assert(builder.localsHandler == elseLocals);
-      }
+      return builder.pop();
     }
-    return builder.current;
+    return null;
   }
 
   handleIf(void visitCondition(), void visitThen(), void visitElse()) {
+    if (visitElse == null) {
+      // Make sure to have an else part to avoid a critical edge. A
+      // critical edge is an edge that connects a block with multiple
+      // successors to a block with multiple predecessors. We avoid
+      // such edges because they prevent inserting copies during code
+      // generation of phi instructions.
+      visitElse = () {};
+    }
+
     _handleDiamondBranch(visitCondition, visitThen, visitElse, false);
   }
 
   handleConditional(void visitCondition(), void visitThen(), void visitElse()) {
+    assert(visitElse != null);
     _handleDiamondBranch(visitCondition, visitThen, visitElse, true);
   }
 
@@ -3512,35 +3498,46 @@ class SsaBranchBuilder {
                             void visitThen(),
                             void visitElse(),
                             bool isExpression) {
-    branchesHaveValues = isExpression;
-    if (visitElse == null) {
-      if (isExpression) {
-        compiler.internalError("Diamond branch with values but without else.",
-                               node: diagnosticNode);
-      }
-      // Make sure to have an else part to avoid a critical edge. A
-      // critical edge is an edge that connects a block with multiple
-      // successors to a block with multiple predecessors. We avoid
-      // such edges because they prevent inserting copies during code
-      // generation of phi instructions.
-      visitElse = () {};
+    SsaBranch conditionBranch = new SsaBranch(this);
+    SsaBranch thenBranch = new SsaBranch(this);
+    SsaBranch elseBranch = new SsaBranch(this);
+    SsaBranch joinBranch = new SsaBranch(this);
+
+    conditionBranch.startLocals = builder.localsHandler;
+    builder.goto(builder.current, conditionBranch.block);
+
+    buildCondition(visitCondition, conditionBranch, thenBranch, elseBranch);
+    HInstruction thenValue =
+        buildBranch(thenBranch, visitThen, joinBranch, isExpression);
+    HInstruction elseValue =
+        buildBranch(elseBranch, visitElse, joinBranch, isExpression);
+
+    if (isExpression) {
+      assert(thenValue != null && elseValue != null);
+      HPhi phi =
+          new HPhi.manyInputs(null, <HInstruction>[thenValue, elseValue]);
+      joinBranch.block.addPhi(phi);
+      builder.stack.add(phi);
     }
 
-    buildCondition(visitCondition);
-    buildThen(visitThen, new LocalsHandler.from(conditionLocals));
-    // Use the locals state after the condition. We are the last ones to use the
-    // conditionLocals. So we don't need to make a copy of it.
-    buildElse(visitElse, conditionLocals);
-    HBasicBlock joinBlock = join();
+    HBasicBlock thenBlock = thenBranch.block;
+    HBasicBlock elseBlock = elseBranch.block;
+    HBasicBlock joinBlock;
+    // If at least one branch did not abort, open the joinBranch.
+    if (!joinBranch.block.predecessors.isEmpty()) {
+      startBranch(joinBranch);
+      joinBlock = joinBranch.block;
+    }
 
     HIfBlockInformation info =
         new HIfBlockInformation(
-            new HSubExpressionBlockInformation(conditionGraph),
-            new HSubGraphBlockInformation(thenGraph),
-            new HSubGraphBlockInformation(elseGraph));
+          new HSubExpressionBlockInformation(conditionBranch.graph),
+          new HSubGraphBlockInformation(thenBranch.graph),
+          new HSubGraphBlockInformation(elseBranch.graph));
 
-    HBasicBlock conditionStartBlock = conditionGraph.start;
-    conditionGraph.start.setBlockFlow(info, joinBlock);
+    HBasicBlock conditionStartBlock = conditionBranch.block;
+    conditionStartBlock.setBlockFlow(info, joinBlock);
+    SubGraph conditionGraph = conditionBranch.graph;
     HIf branch = conditionGraph.end.last;
     assert(branch is HIf);
     branch.blockInformation = conditionStartBlock.blockFlow;