Recognize nested logical operations.

lib/compiler/implementation/ssa/codegen_helpers.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.
 
 /**
  * Instead of emitting each SSA instruction with a temporary variable
  * mark instructions that can be emitted at their use-site.
  * For example, in:
  *   t0 = 4;
  *   t1 = 3;
@@ skipping 133 matching lines @@
   /**
    * Check if a block has at least one statement other than
    * [instruction].
    */
   bool hasStatement(HBasicBlock block, HInstruction instruction) {
     // If [instruction] is not in [block], then if the block is not
     // empty, we know there will be a statement to emit.
     if (instruction.block !== block) return block.last !== block.first;
 
     // If [instruction] is not the last instruction of the block
-    // before the control flow instruction, then we will have to emit
-    // a statement for that last instruction.
-    if (instruction !== block.last.previous) return true;
+    // before the control flow instruction, or the last instruction,
+    // then we will have to emit a statement for that last instruction.
+    if (instruction != block.last
+        && instruction !== block.last.previous) return true;

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

Putting "&&" at the end of the previous line seems more common. I actually like
this, so keep it :)

 
     // If one of the instructions in the block until [instruction] is
     // not generated at use site, then we will have to emit a
     // statement for it.
     // TODO(ngeoffray): we could generate a comma separated
     // list of expressions.
     for (HInstruction temp = block.first;
          temp !== instruction;
          temp = temp.next) {
       if (!generateAtUseSite.contains(temp)) return true;
@@ skipping 12 matching lines @@
     //       /    \
     //      /      \
     //   1 expr    goto
     //    goto     /
     //      \     /
     //       \   /
     // phi(expr, true|false)
     if (end == null) return;
     if (end.phis.isEmpty()) return;
     if (end.phis.first !== end.phis.last) return;
-    HBasicBlock thenBlock = startIf.thenBlock;
     HBasicBlock elseBlock = startIf.elseBlock;
-    if (end.predecessors[0] !== thenBlock) return;
+
     if (end.predecessors[1] !== elseBlock) return;
     HPhi phi = end.phis.first;
-    if (!phi.inputs[1].isConstantBoolean()) return;
+    if (!phi.inputs[1].isConstantBoolean()) return; 
+    if (elseBlock.first !== elseBlock.last) return;

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

Or "if (elseBlock.first is! HGoto) return;"?

[ngeoffray, 2012/06/07 12:39:18]

Done.

+
+    HBasicBlock thenBlock = startIf.thenBlock;
+    // Skip trivial goto blocks.
+    while (thenBlock.successors[0] != end
+           && thenBlock.first == thenBlock.last

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

You could just check that thenBlock.first is HGoto.

[ngeoffray, 2012/06/07 12:39:18]

Done.

+           && thenBlock.last is HGoto) {
+      thenBlock = thenBlock.successors[0];
+    }
     
     HInstruction thenInput = phi.inputs[0];
-    if (hasStatement(thenBlock, thenInput)) return;
-    if (elseBlock.first !== elseBlock.last) return;
-    
+
+    // If the [thenBlock] is already a logical operation, and does not
+    // have statements, we can emit a sequence of logical operation.

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

"have a statement" to match the call to "hasStatement" below.

[ngeoffray, 2012/06/07 12:39:18]

Done.

+    if (logicalOperations.contains(thenBlock.last)) {
+      if (hasStatement(thenBlock, thenBlock.last)) return;
+      assert(thenInput.usedBy.length == 1);
+      generateAtUseSite.add(thenInput);
+    } else {
+      if (end.predecessors[0] !== thenBlock) return;
+      if (hasStatement(thenBlock, thenInput)) return;
+      // If [thenInput] is defined in [thenBlock], then it is only used
+      // by [phi] and can be generated at use site.
+      if (thenInput.block === thenBlock) {
+        assert(thenInput.usedBy.length == 1);

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

Can't it also be used internally in the block?

[ngeoffray, 2012/06/07 12:39:18]

No, because otherwise there would be an instruction in-between the instruction
and the control flow instruction, which I guard against in hasStatement. I added
a comment.

+        generateAtUseSite.add(thenInput);
+      }
+    }
+     
     // From now on, we have recognized a logical operation built from
     // the builder. We don't expect the builder and the optimizers to
     // generate the then and else branches with multiple successors,
     // and the join branch to have more than two predecessors.

[Lasse Reichstein Nielsen, 2012/06/07 12:02:47]

Then check if that's the case and return if it isn't.
Before setting the generateAtUseSite bit.

[ngeoffray, 2012/06/07 12:39:18]

Added asserts instead.

 
     // Mark the if instruction as a logical operation.
     logicalOperations.add(startIf);
 
     // If the logical operation is only used by the first instruction
     // of its block, it can be generated at use site.
     if (phi.usedBy.length == 1 && phi.usedBy[0] === phi.block.first) {
       generateAtUseSite.add(phi);
     }
-
-    // If [thenInput] is defined in [thenBlock], then it is only used
-    // by [phi] and can be generated at use site.
-    if (thenInput.block === thenBlock) {
-      assert(thenInput.usedBy.length == 1);
-      generateAtUseSite.add(thenInput);
-    }
   }
 }
 
 // Precedence information for JavaScript operators.
 class JSPrecedence {
    // Used as precedence for something that's not even an expression.
   static final int STATEMENT_PRECEDENCE      = 0;
   // Precedences of JS operators.
   static final int EXPRESSION_PRECEDENCE     = 1;
   static final int ASSIGNMENT_PRECEDENCE     = 2;
@@ skipping 63 matching lines @@
   };
 }
 
 class JSBinaryOperatorPrecedence {
   final int left;
   final int right;
   const JSBinaryOperatorPrecedence(this.left, this.right);
   // All binary operators (excluding assignment) are left associative.
   int get precedence() => left;
 }