Better detection of logical and/or inlining opportunities.

lib/compiler/implementation/ssa/codegen_helpers.dart

Index: lib/compiler/implementation/ssa/codegen_helpers.dart
diff --git a/lib/compiler/implementation/ssa/codegen_helpers.dart b/lib/compiler/implementation/ssa/codegen_helpers.dart
index 41dadc6ba6e9a0ff046711c3cb12ae3943ace338..1fd633b0ad8e19b11d70a9d5229e6de2dcbc14a7 100644
--- a/lib/compiler/implementation/ssa/codegen_helpers.dart
+++ b/lib/compiler/implementation/ssa/codegen_helpers.dart
@@ -178,43 +178,94 @@ class SsaConditionMerger extends HGraphVisitor {
    * generated at use-site.
    */
   bool isExpression(HInstruction instruction, HBasicBlock limit) {
-    if (instruction is HPhi && !logicalOperations.containsKey(instruction)) {
-      return false;
-    }
-    while (instruction.previous != null) {
-      instruction = instruction.previous;
-      if (!generateAtUseSite.contains(instruction)) {
+    HBasicBlock block = instruction.block;
+    if (instruction is HPhi) {
+      if (!logicalOperations.containsKey(instruction)) {
         return false;
       }
+    } else {
+      while (instruction.previous != null) {
+        instruction = instruction.previous;
+        if (!generateAtUseSite.contains(instruction)) {
+          return false;
+        }
+      }
+      // Now [instruction] is the first instruction of the block
+      // (aka [block.first]). If there are also a phi, check the current
+      // [instruction] normally and make [instruction] be the phi.
+      if (!block.phis.isEmpty()) {
+        if (!generateAtUseSite.contains(instruction)) {
+          return false;
+        }
+        instruction = block.phis.last;
+        if (block.phis.first !== instruction) {
+          // If there is more than one phi, don't try to undestand it.
+          return false;
+        }
+        if (!logicalOperations.containsKey(instruction)) {
+          return false;
+        }
+      }
     }
-    HBasicBlock block = instruction.block;
-    if (!block.phis.isEmpty()) return false;
-    if (instruction is HPhi && logicalOperations.containsKey(instruction)) {
+    if (instruction is HPhi) {
+      assert(logicalOperations.containsKey(instruction));
       return isExpression(instruction.inputs[0], limit);
     }
-    return block.predecessors.length == 1 && block.predecessors[0] == limit;
+    if (block.predecessors.length !== 1) {
+      return false;
+    }
+    HBasicBlock previousBlock = block.predecessors[0];
+    if (previousBlock === limit) return true;
+    if (previousBlock.successors.length !== 1 ||
+        previousBlock.last is! HGoto) {
+      return false;
+    }
+    return isExpression(previousBlock.last, limit);
   }
 
   void replaceWithLogicalOperator(HPhi phi, String type) {
     if (canGenerateAtUseSite(phi)) generateAtUseSite.add(phi);
     logicalOperations[phi] = type;
+    // If the phi corresponds to logical control flow, mark the
+    // control-flow instructions as generate-at-use-site.
+    generateAtUseSite.add(phi.block.predecessors[0].last);
+    generateAtUseSite.add(phi.block.predecessors[1].last);
+    // If the first input is only used as branch condition and result, it too
+    // can be generate-at-use-site.
+    if (phi.inputs[0].usedBy.length == 2) {
+      generateAtUseSite.add(phi.inputs[0]);
+    }
+    if (phi.inputs[1].usedBy.length == 1) {
+      generateAtUseSite.add(phi.inputs[1]);
+    }
   }
 
   bool canGenerateAtUseSite(HPhi phi) {
-    if (phi.usedBy.length != 1) return false;
+    if (phi.usedBy.length != 1) {
+      return false;
+    }
     assert(phi.next == null);
     HInstruction use = phi.usedBy[0];
 
     HInstruction current = phi.block.first;
     while (current != use) {
-      if (!generateAtUseSite.contains(current)) return false;
+      // Check that every instruction between the start of the block and the
+      // use of the phi (i.e., every instruction between the phi and the use)
+      // is itself generated at use site. That means that the phi can be
+      // moved to its use site without crossing any other code, because those
+      // instructions (if any) are moved too.
+      if (current is! HControlFlow && !generateAtUseSite.contains(current)) {
+        return false;
+      }
       if (current.next != null) {
         current = current.next;
       } else if (current is HPhi) {
         current = current.block.first;
       } else {
         assert(current is HControlFlow);
-        if (current is !HGoto) return false;
+        if (current is !HGoto) {
+          return false;
+        }
         HBasicBlock nextBlock = current.block.successors[0];
         if (!nextBlock.phis.isEmpty()) {
           current = nextBlock.phis.first;
@@ -226,6 +277,23 @@ class SsaConditionMerger extends HGraphVisitor {
     return true;
   }
 
+  HInstruction previousInstruction(HInstruction instruction) {
+    if (instruction.previous != null) return instruction.previous;
+    HBasicBlock block = instruction.block;
+    if (instruction is! HPhi) {
+      if (block.phis.last != null) return block.phis.last;
+    }
+    if (block.predecessors.length == 1) {
+      HBasicBlock previousBlock = block.predecessors[0];
+      if (previousBlock.last is HGoto) {
+        assert(previousBlock.successors.length == 1);
+        assert(previousBlock.successors[0] === block);
+        return previousInstruction(previousBlock.last);
+      }
+    }
+    return null;
+  }
+
   void detectLogicControlFlow(HPhi phi) {
     // Check for the most common pattern for a short-circuit logic operation:
     //   B0 b0 = ...; if (b0) goto B1 else B2 (or: if (!b0) goto B2 else B1)
@@ -234,12 +302,11 @@ class SsaConditionMerger extends HGraphVisitor {
     //   |/
     //   B2 b2 = phi(b0,b1); if(b2) ...
     // TODO(lrn): Also recognize ?:-flow?
-
     if (phi.inputs.length != 2) return;
     HInstruction first = phi.inputs[0];
-    HBasicBlock firstBlock = first.block;
+    HBasicBlock firstBlock = phi.block.predecessors[0];
     HInstruction second = phi.inputs[1];
-    HBasicBlock secondBlock = second.block;
+    HBasicBlock secondBlock = phi.block.predecessors[1];
     // Check second input of phi being an expression followed by a goto.
     if (second.usedBy.length != 1) return;
     HInstruction secondNext =
@@ -251,36 +318,32 @@ class SsaConditionMerger extends HGraphVisitor {
     // Check first input of phi being followed by a (possibly negated)
     // conditional branch based on the same value.
     if (firstBlock != phi.block.dominator) return;
-    if (firstBlock.last is !HConditionalBranch) return;
-    HConditionalBranch firstBranch = firstBlock.last;
-    // Must be used both for value and for control to avoid the second branch.
-    if (first.usedBy.length != 2) return;
+    if (firstBlock.last is! HIf) return;
     if (firstBlock.successors[1] != phi.block) return;
-    HInstruction firstNext = (first is HPhi) ? firstBlock.first : first.next;
-    if (firstNext == firstBranch &&
-        firstBranch.condition == first) {
+    HIf firstBranch = firstBlock.last;
+    HInstruction condition = firstBranch.inputs[0];
+    if (condition === first) {
       replaceWithLogicalOperator(phi, "&&");
-    } else if (firstNext is HNot &&
-               firstNext.inputs[0] == first &&
-               generateAtUseSite.contains(firstNext) &&
-               firstNext.next == firstBlock.last &&
-               firstBranch.condition == firstNext) {
+    } else if (condition is HNot &&
+               condition.inputs[0] == first) {
       replaceWithLogicalOperator(phi, "||");
-    } else {
-      return;
+      // If the negation is only used by this logical operation, or only by
+      // logical operators in general, it won't need to be generated.
+      if (!generateAtUseSite.contains(condition)) {
+        for (HInstruction user in condition.usedBy) {
+          if (user is! HIf || !generateAtUseSite.contains(user)) {
+            return;
+          }
+        }
+        generateAtUseSite.add(condition);
+      }
     }
-    // Detected as logic control flow. Mark the corresponding
-    // inputs as generated at use site. These will now be generated
-    // as part of an expression.
-    generateAtUseSite.add(first);
-    generateAtUseSite.add(firstBlock.last);
-    generateAtUseSite.add(second);
-    generateAtUseSite.add(secondBlock.last);
+    return;
   }
 
   void visitBasicBlock(HBasicBlock block) {
     if (!block.phis.isEmpty() &&
-        block.phis.first == block.phis.last) {
+        block.phis.first === block.phis.last) {
       detectLogicControlFlow(block.phis.first);
     }
   }