kernel -> ssa: implement if-statements

pkg/compiler/lib/src/ssa/builder.dart

Index: pkg/compiler/lib/src/ssa/builder.dart
diff --git a/pkg/compiler/lib/src/ssa/builder.dart b/pkg/compiler/lib/src/ssa/builder.dart
index c9ef7eeb36a8334be1988372ff04a6645a278c72..1f5d56b36da1d0db797b4bfae3cd61574ca2875f 100644
--- a/pkg/compiler/lib/src/ssa/builder.dart
+++ b/pkg/compiler/lib/src/ssa/builder.dart
@@ -38,10 +38,12 @@ import '../universe/side_effects.dart' show SideEffects;
 import '../universe/use.dart' show DynamicUse, StaticUse, TypeUse;
 import '../util/util.dart';
 import '../world.dart' show ClassWorld;
+
 import 'graph_builder.dart';
 import 'locals_handler.dart';
 import 'nodes.dart';
 import 'optimize.dart';
+import 'ssa_branch_builder.dart';
 import 'types.dart';
 
 /// A synthetic local variable only used with the SSA graph.
@@ -411,8 +413,6 @@ class SsaBuilder extends ast.Visitor
    */
   final List<Element> sourceElementStack = <Element>[];
 
-  LocalsHandler localsHandler;
-
   HInstruction rethrowableException;
 
   Map<JumpTarget, JumpHandler> jumpTargets = <JumpTarget, JumpHandler>{};
@@ -1907,6 +1907,7 @@ class SsaBuilder extends ast.Visitor
     push(attachPosition(instruction, node));
   }
 
+  @override
   HInstruction popBoolified() {
     HInstruction value = pop();
     if (_checkOrTrustTypes) {
@@ -2537,31 +2538,69 @@ class SsaBuilder extends ast.Visitor
       void visitThen(),
       void visitElse(),
       SourceInformation sourceInformation}) {
-    SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, diagnosticNode);
+    SsaBranchBuilder branchBuilder =
+        new SsaBranchBuilder(this, compiler, diagnosticNode);
     branchBuilder.handleIf(visitCondition, visitThen, visitElse,
         sourceInformation: sourceInformation);
   }
 
   @override
   void visitIfNull(ast.Send node, ast.Node left, ast.Node right, _) {
-    SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+    SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
     brancher.handleIfNull(() => visit(left), () => visit(right));
   }
 
+  /// Optimizes logical binary where the left is also a logical binary.
+  ///
+  /// This method transforms the operator by optimizing the case where [left] is
+  /// a logical "and" or logical "or". Then it uses [branchBuilder] to build the
+  /// graph for the optimized expression.
+  ///
+  /// For example, `(x && y) && z` is transformed into `x && (y && z)`:
+  ///
+  ///     t0 = boolify(x);
+  ///     if (t0) {
+  ///       t1 = boolify(y);
+  ///       if (t1) {
+  ///         t2 = boolify(z);
+  ///       }
+  ///       t3 = phi(t2, false);
+  ///     }
+  ///     result = phi(t3, false);
+  void handleLogicalBinaryWithLeftNode(
+      ast.Node left, void visitRight(), SsaBranchBuilder branchBuilder,
+      {bool isAnd}) {
+    ast.Send send = left.asSend();
+    if (send != null && (isAnd ? send.isLogicalAnd : send.isLogicalOr)) {
+      ast.Node newLeft = send.receiver;
+      Link<ast.Node> link = send.argumentsNode.nodes;
+      assert(link.tail.isEmpty);
+      ast.Node middle = link.head;
+      handleLogicalBinaryWithLeftNode(
+          newLeft,
+          () => handleLogicalBinaryWithLeftNode(
+              middle, visitRight, branchBuilder,
+              isAnd: isAnd),
+          branchBuilder,
+          isAnd: isAnd);
+    } else {
+      branchBuilder.handleLogicalBinary(() => visit(left), visitRight,
+          isAnd: isAnd);
+    }
+  }
+
   @override
   void visitLogicalAnd(ast.Send node, ast.Node left, ast.Node right, _) {
-    SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, node);
-    branchBuilder.handleLogicalAndOrWithLeftNode(left, () {
-      visit(right);
-    }, isAnd: true);
+    SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, compiler, node);
+    handleLogicalBinaryWithLeftNode(left, () => visit(right), branchBuilder,
+        isAnd: true);
   }
 
   @override
   void visitLogicalOr(ast.Send node, ast.Node left, ast.Node right, _) {
-    SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, node);
-    branchBuilder.handleLogicalAndOrWithLeftNode(left, () {
-      visit(right);
-    }, isAnd: false);
+    SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, compiler, node);
+    handleLogicalBinaryWithLeftNode(left, () => visit(right), branchBuilder,
+        isAnd: false);
   }
 
   @override
@@ -2819,7 +2858,7 @@ class SsaBuilder extends ast.Visitor
     // we will be able to later compress it as:
     //   t1 || t1.x
     HInstruction expression;
-    SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+    SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
     brancher.handleConditional(
         () {
           expression = visitAndPop(receiver);
@@ -2835,7 +2874,7 @@ class SsaBuilder extends ast.Visitor
         });
   }
 
-  /// Pushes a boolean checking [expression] against null.
+  @override
   pushCheckNull(HInstruction expression) {
     push(new HIdentity(
         expression, graph.addConstantNull(compiler), null, backend.boolType));
@@ -3202,7 +3241,7 @@ class SsaBuilder extends ast.Visitor
       ast.NodeList arguments, Selector selector, _) {
     /// Desugar `exp?.m()` to `(t1 = exp) == null ? t1 : t1.m()`
     HInstruction receiver;
-    SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+    SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
     brancher.handleConditional(() {
       receiver = generateInstanceSendReceiver(node);
       pushCheckNull(receiver);
@@ -5008,7 +5047,7 @@ class SsaBuilder extends ast.Visitor
       }
 
       if (node.isIfNullAssignment) {
-        SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+        SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
         brancher.handleIfNull(() => stack.add(getterInstruction), () {
           addDynamicSendArgumentsToList(node, setterInputs);
           generateSuperSendSet();
@@ -5328,7 +5367,7 @@ class SsaBuilder extends ast.Visitor
         //   if (t1 == null)
         //      t1 = x[i] = e;
         //   result = t1
-        SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+        SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
         brancher.handleIfNull(() => stack.add(getterInstruction), () {
           visit(arguments.head);
           HInstruction value = pop();
@@ -5376,7 +5415,7 @@ class SsaBuilder extends ast.Visitor
     // else
     //   result = e.x = e2
     HInstruction receiverInstruction;
-    SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+    SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
     brancher.handleConditional(
         () {
           receiverInstruction = generateInstanceSendReceiver(node);
@@ -5549,7 +5588,8 @@ class SsaBuilder extends ast.Visitor
             receiver);
         HInstruction getterInstruction = pop();
         if (node.isIfNullAssignment) {
-          SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+          SsaBranchBuilder brancher =
+              new SsaBranchBuilder(this, compiler, node);
           brancher.handleIfNull(() => stack.add(getterInstruction), () {
             visit(node.arguments.head);
             generateInstanceSetterWithCompiledReceiver(node, receiver, pop());
@@ -5570,7 +5610,7 @@ class SsaBuilder extends ast.Visitor
         //   t1 = e
         //   t1 == null ? t1 : (t1.x = t1.x op e2);
         HInstruction receiver;
-        SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+        SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
         brancher.handleConditional(() {
           receiver = generateInstanceSendReceiver(node);
           pushCheckNull(receiver);
@@ -5596,7 +5636,7 @@ class SsaBuilder extends ast.Visitor
     }
     HInstruction getterInstruction = pop();
     if (node.isIfNullAssignment) {
-      SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+      SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
       brancher.handleIfNull(() => stack.add(getterInstruction), () {
         visit(node.arguments.head);
         generateNonInstanceSetter(node, element, pop());
@@ -6006,7 +6046,7 @@ class SsaBuilder extends ast.Visitor
   }
 
   visitConditional(ast.Conditional node) {
-    SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);
+    SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);
     brancher.handleConditional(() => visit(node.condition),
         () => visit(node.thenExpression), () => visit(node.elseExpression));
   }
@@ -7478,252 +7518,6 @@ class AstInliningState extends InliningState {
       : super(function);
 }
 
-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 ast.Node diagnosticNode;
-
-  SsaBranchBuilder(this.builder, [this.diagnosticNode]);
-
-  Compiler get compiler => builder.compiler;
-
-  void checkNotAborted() {
-    if (builder.isAborted()) {
-      compiler.unimplemented(diagnosticNode, "aborted control flow");
-    }
-  }
-
-  void buildCondition(
-      void visitCondition(),
-      SsaBranch conditionBranch,
-      SsaBranch thenBranch,
-      SsaBranch elseBranch,
-      SourceInformation sourceInformation) {
-    startBranch(conditionBranch);
-    visitCondition();
-    checkNotAborted();
-    assert(identical(builder.current, builder.lastOpenedBlock));
-    HInstruction conditionValue = builder.popBoolified();
-    HIf branch = new HIf(conditionValue)..sourceInformation = sourceInformation;
-    HBasicBlock conditionExitBlock = builder.current;
-    builder.close(branch);
-    conditionBranch.exitLocals = builder.localsHandler;
-    conditionExitBlock.addSuccessor(thenBranch.block);
-    conditionExitBlock.addSuccessor(elseBranch.block);
-    bool conditionBranchLocalsCanBeReused =
-        mergeLocals(conditionBranch, thenBranch, mayReuseFromLocals: true);
-    mergeLocals(conditionBranch, elseBranch,
-        mayReuseFromLocals: conditionBranchLocalsCanBeReused);
-
-    conditionBranch.graph =
-        new SubExpression(conditionBranch.block, conditionExitBlock);
-  }
-
-  /**
-   * Returns true if the locals of the [fromBranch] may be reused. A [:true:]
-   * return value implies that [mayReuseFromLocals] was set to [:true:].
-   */
-  bool mergeLocals(SsaBranch fromBranch, SsaBranch toBranch,
-      {bool mayReuseFromLocals}) {
-    LocalsHandler fromLocals = fromBranch.exitLocals;
-    if (toBranch.startLocals == null) {
-      if (mayReuseFromLocals) {
-        toBranch.startLocals = fromLocals;
-        return false;
-      } else {
-        toBranch.startLocals = new LocalsHandler.from(fromLocals);
-        return true;
-      }
-    } else {
-      toBranch.startLocals.mergeWith(fromLocals, toBranch.block);
-      return true;
-    }
-  }
-
-  void startBranch(SsaBranch branch) {
-    builder.graph.addBlock(branch.block);
-    builder.localsHandler = branch.startLocals;
-    builder.open(branch.block);
-  }
-
-  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, mayReuseFromLocals: true);
-    }
-    if (isExpression) {
-      checkNotAborted();
-      return builder.pop();
-    }
-    return null;
-  }
-
-  handleIf(void visitCondition(), void visitThen(), void visitElse(),
-      {SourceInformation sourceInformation}) {
-    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,
-        isExpression: false, sourceInformation: sourceInformation);
-  }
-
-  handleConditional(void visitCondition(), void visitThen(), void visitElse()) {
-    assert(visitElse != null);
-    _handleDiamondBranch(visitCondition, visitThen, visitElse,
-        isExpression: true);
-  }
-
-  handleIfNull(void left(), void right()) {
-    // x ?? y is transformed into: x == null ? y : x
-    HInstruction leftExpression;
-    handleConditional(() {
-      left();
-      leftExpression = builder.pop();
-      builder.pushCheckNull(leftExpression);
-    }, right, () => builder.stack.add(leftExpression));
-  }
-
-  void handleLogicalAndOr(void left(), void right(), {bool isAnd}) {
-    // x && y is transformed into:
-    //   t0 = boolify(x);
-    //   if (t0) {
-    //     t1 = boolify(y);
-    //   }
-    //   result = phi(t1, false);
-    //
-    // x || y is transformed into:
-    //   t0 = boolify(x);
-    //   if (not(t0)) {
-    //     t1 = boolify(y);
-    //   }
-    //   result = phi(t1, true);
-    HInstruction boolifiedLeft;
-    HInstruction boolifiedRight;
-
-    void visitCondition() {
-      left();
-      boolifiedLeft = builder.popBoolified();
-      builder.stack.add(boolifiedLeft);
-      if (!isAnd) {
-        builder.push(new HNot(builder.pop(), builder.backend.boolType));
-      }
-    }
-
-    void visitThen() {
-      right();
-      boolifiedRight = builder.popBoolified();
-    }
-
-    handleIf(visitCondition, visitThen, null);
-    HConstant notIsAnd =
-        builder.graph.addConstantBool(!isAnd, builder.compiler);
-    JavaScriptBackend backend = builder.backend;
-    HPhi result = new HPhi.manyInputs(
-        null, <HInstruction>[boolifiedRight, notIsAnd], backend.dynamicType);
-    builder.current.addPhi(result);
-    builder.stack.add(result);
-  }
-
-  void handleLogicalAndOrWithLeftNode(ast.Node left, void visitRight(),
-      {bool isAnd}) {
-    // This method is similar to [handleLogicalAndOr] but optimizes the case
-    // where left is a logical "and" or logical "or".
-    //
-    // For example (x && y) && z is transformed into x && (y && z):
-    //   t0 = boolify(x);
-    //   if (t0) {
-    //     t1 = boolify(y);
-    //     if (t1) {
-    //       t2 = boolify(z);
-    //     }
-    //     t3 = phi(t2, false);
-    //   }
-    //   result = phi(t3, false);
-
-    ast.Send send = left.asSend();
-    if (send != null && (isAnd ? send.isLogicalAnd : send.isLogicalOr)) {
-      ast.Node newLeft = send.receiver;
-      Link<ast.Node> link = send.argumentsNode.nodes;
-      assert(link.tail.isEmpty);
-      ast.Node middle = link.head;
-      handleLogicalAndOrWithLeftNode(
-          newLeft,
-          () =>
-              handleLogicalAndOrWithLeftNode(middle, visitRight, isAnd: isAnd),
-          isAnd: isAnd);
-    } else {
-      handleLogicalAndOr(() => builder.visit(left), visitRight, isAnd: isAnd);
-    }
-  }
-
-  void _handleDiamondBranch(
-      void visitCondition(), void visitThen(), void visitElse(),
-      {bool isExpression, SourceInformation sourceInformation}) {
-    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,
-        sourceInformation);
-    HInstruction thenValue =
-        buildBranch(thenBranch, visitThen, joinBranch, isExpression);
-    HInstruction elseValue =
-        buildBranch(elseBranch, visitElse, joinBranch, isExpression);
-
-    if (isExpression) {
-      assert(thenValue != null && elseValue != null);
-      JavaScriptBackend backend = builder.backend;
-      HPhi phi = new HPhi.manyInputs(
-          null, <HInstruction>[thenValue, elseValue], backend.dynamicType);
-      joinBranch.block.addPhi(phi);
-      builder.stack.add(phi);
-    }
-
-    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(conditionBranch.graph),
-        new HSubGraphBlockInformation(thenBranch.graph),
-        new HSubGraphBlockInformation(elseBranch.graph));
-
-    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;
-  }
-}
-
 class TypeBuilder implements DartTypeVisitor<dynamic, SsaBuilder> {
   final ClassWorld classWorld;