Refactor SsaBranchBuilder.

lib/compiler/implementation/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 570 matching lines @@
     loopEntry.forEachPhi((HPhi phi) {
       Element element = phi.sourceElement;
       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.
+   * 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
     // 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, <HInstruction>[instruction, mine]);
+              new HPhi.manyInputs(element, <HInstruction>[mine, instruction]);
           joinBlock.addPhi(phi);
           joinedLocals[element] = phi;
         }
       }
     });
     directLocals = joinedLocals;
   }
 
   /**
    * The current localsHandler is not used for its values, only for its
@@ skipping 2757 matching lines @@
      node.visitChildren(this);
   }
 
   HInstruction concat(HInstruction left, HInstruction right) {
     HInstruction instruction = new HStringConcat(left, right, diagnosticNode);
     builder.add(instruction);
     return instruction;
   }
 }
 
+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;
 
   void checkNotAborted() {
     if (builder.isAborted()) {
       compiler.unimplemented("aborted control flow", node: diagnosticNode);
     }
   }
 
-  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);
+    conditionBranch.exitLocals = builder.localsHandler;
+    conditionExitBlock.addSuccessor(thenBranch.block);
+    conditionExitBlock.addSuccessor(elseBranch.block);
+    bool copied = mergeLocals(conditionBranch, thenBranch, needsCopy: false);
+    mergeLocals(conditionBranch, elseBranch, needsCopy: !copied);
 
-    conditionGraph =
-        new SubExpression(conditionStartBlock, builder.lastOpenedBlock);
-    conditionLocals = builder.localsHandler;
-    return conditionGraph;
+    conditionBranch.graph =
+        new SubExpression(conditionBranch.block, conditionExitBlock);
   }
 
-  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();
+  /** 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;
     }
-    thenGraph = new SubGraph(thenBlock, builder.lastOpenedBlock);
-    thenLocals = builder.localsHandler;
-    return thenGraph;
   }
 
-  SubGraph buildElse(void visitElse(), LocalsHandler locals) {
-    builder.localsHandler = locals;
-    HBasicBlock elseBlock = builder.addNewBlock();
-    conditionGraph.end.addSuccessor(elseBlock);
-    builder.open(elseBlock);
-    visitElse();
-    if (branchesHaveValues) {
-      checkNotAborted();
-      elseValue = builder.pop();
-    }
-    elseGraph = new SubGraph(elseBlock, builder.lastOpenedBlock);
-    elseLocals = builder.localsHandler;
-    return elseGraph;
+  void startBranch(SsaBranch branch) {
+    builder.graph.addBlock(branch.block);
+    builder.localsHandler = branch.startLocals;
+    builder.open(branch.block);
   }
 
-  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);
-      }
+  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);
     }
-    return builder.current;
+    if (isExpression) {
+      checkNotAborted();
+      return builder.pop();
+    }
+    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);
   }
 
   void _handleDiamondBranch(void visitCondition(),
                             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;
   }
 }