Recognize logical operations before code generation.

lib/compiler/implementation/ssa/codegen.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 SsaCodeGeneratorTask extends CompilerTask {
   final JavaScriptBackend backend;
   SsaCodeGeneratorTask(JavaScriptBackend backend)
       : this.backend = backend,
         super(backend.compiler);
   String get name() => 'SSA code generator';
@@ skipping 129 matching lines @@
   static final int TYPE_STATEMENT = 0;
   static final int TYPE_EXPRESSION = 1;
   static final int TYPE_DECLARATION = 2;
 
   final JavaScriptBackend backend;
   final WorkItem work;
   final StringBuffer buffer;
   final String parameters;
 
   final Set<HInstruction> generateAtUseSite;
-  final Map<HPhi, String> logicalOperations;
+  final Set<HInstruction> logicalOperations;
   final Map<Element, ElementAction> breakAction;
   final Map<Element, ElementAction> continueAction;
   final Map<Element, String> parameterNames;
 
   /**
    * Contains the names of the instructions, as well as the parallel
    * copies to perform on block transitioning.
    */
   VariableNames variableNames;
 
@@ skipping 38 matching lines @@
   }
 
   SsaCodeGenerator(this.backend,
                    this.work,
                    this.parameters,
                    this.parameterNames)
     : declaredVariables = new Set<String>(),
       delayedVariablesDeclaration = new List<String>(),
       buffer = new StringBuffer(),
       generateAtUseSite = new Set<HInstruction>(),
-      logicalOperations = new Map<HPhi, String>(),
+      logicalOperations = new Set<HInstruction>(),
       breakAction = new Map<Element, ElementAction>(),
       continueAction = new Map<Element, ElementAction>(),
       unsignedShiftPrecedences = JSPrecedence.binary['>>>'] {
 
     Interceptors interceptors = backend.builder.interceptors;
     equalsNullElement = interceptors.getEqualsNullInterceptor();
     boolifiedEqualsNullElement =
         interceptors.getBoolifiedVersionOf(equalsNullElement);
   }
 
@@ skipping 260 matching lines @@
       buffer.add("var ");
     }
     buffer.add(variableName);
   }
 
   void declareInstruction(HInstruction instruction) {
     declareVariable(variableNames.getName(instruction));
   }
 
   void define(HInstruction instruction) {
+    if (isGeneratingExpression()) {
+      addExpressionSeparator();
+    } else {
+      addIndentation();
+    }
     if (instruction is !HCheck && variableNames.hasName(instruction)) {
       declareInstruction(instruction);
       buffer.add(" = ");
       visit(instruction, JSPrecedence.ASSIGNMENT_PRECEDENCE);
     } else {
       visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
     }
+    if (!isGeneratingExpression()) buffer.add(';\n');
   }
 
   void use(HInstruction argument, int expectedPrecedenceForArgument) {
     if (isGenerateAtUseSite(argument)) {
       visit(argument, expectedPrecedenceForArgument);
     } else if (argument is HCheck) {
       HCheck check = argument;
       use(argument.checkedInput, expectedPrecedenceForArgument);
     } else {
       buffer.add(variableNames.getName(argument));
@@ skipping 19 matching lines @@
     buffer.add(";\n");
   }
 
   void implicitBreakWithLabel(TargetElement target) {
     addIndented("break ");
     writeImplicitLabel(target);
     buffer.add(";\n");
   }
 
   bool visitIfInfo(HIfBlockInformation info) {
+    if (logicalOperations.contains(info.condition.end.last)) return false;

[kasperl, 2012/06/04 11:12:55]

Add a comment that explains what this does.

[ngeoffray, 2012/06/04 11:37:54]

Done.

     HInstruction condition = info.condition.conditionExpression;
     if (condition.isConstant()) {
       // If the condition is constant, only generate one branch (if any).
       HConstant constantCondition = condition;
       Constant constant = constantCondition.constant;
       generateStatements(info.condition);
       if (constant.isTrue()) {
         generateStatements(info.thenGraph);
       } else if (info.elseGraph !== null) {
         generateStatements(info.elseGraph);
@@ skipping 256 matching lines @@
       while (!continueOverrides.isEmpty()) {
         continueAction.remove(continueOverrides.head);
         continueOverrides = continueOverrides.tail;
       }
     } else {
       breakAction.remove(labeledBlockInfo.target);
     }
     return true;
   }
 
-  void emitLogicalOperation(HPhi node, String operation) {
-    JSBinaryOperatorPrecedence operatorPrecedence =
-        JSPrecedence.binary[operation];
-    beginExpression(operatorPrecedence.precedence);
-    use(node.inputs[0], operatorPrecedence.left);
-    buffer.add(" $operation ");
-    use(node.inputs[1], operatorPrecedence.right);
-    endExpression(operatorPrecedence.precedence);
-  }
-
   // Wraps a loop body in a block to make continues have a target to break
   // to (if necessary).
   void wrapLoopBodyForContinue(HLoopBlockInformation info) {
     TargetElement target = info.target;
     if (target !== null && target.isContinueTarget) {
       addIndentation();
       for (LabelElement label in info.labels) {
         if (label.isContinueTarget) {
           writeContinueLabel(label);
           buffer.add(":");
@@ skipping 173 matching lines @@
       buffer.add(' = ');
       use(copy.source, JSPrecedence.ASSIGNMENT_PRECEDENCE);
       if (!isGeneratingExpression()) {
         buffer.add(';\n');
       }
     }
   }
 
   void iterateBasicBlock(HBasicBlock node) {
     HInstruction instruction = node.first;
-    while (instruction != null) {
-      if (instruction === node.last) {
-        assignPhisOfSuccessors(node);
-      }
-
-      if (isGenerateAtUseSite(instruction)) {
-        if (instruction is HIf) {
-          HIf hif = instruction;
-          // The "if" is implementing part of a logical expression.
-          // Skip directly forward to to its latest successor, since everything
-          // in-between must also be generateAtUseSite.
-          assert(hif.trueBranch.id < hif.falseBranch.id);
-          visitBasicBlock(hif.falseBranch);
-        }
-      } else if (instruction is HControlFlow) {
-        if (instruction is HLoopBranch && isGeneratingExpression()) {
-          addExpressionSeparator();
-        }
+    while (instruction !== node.last) {
+      if (instruction is HTypeGuard) {
         visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
-      } else if (instruction is HTypeGuard) {
-        visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
-      } else {
-        if (isGeneratingExpression()) {
-          addExpressionSeparator();
-        } else {
-          addIndentation();
-        }
+      } else if (!isGenerateAtUseSite(instruction)) {
         define(instruction);
-        if (!isGeneratingExpression()) buffer.add(';\n');
       }
       instruction = instruction.next;
     }
+    assignPhisOfSuccessors(node);
+    if (instruction is HLoopBranch && isGeneratingExpression()) {
+      addExpressionSeparator();
+    }
+    visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
   }
 
   visitInvokeBinary(HInvokeBinary node, String op) {
     if (node.builtin) {
       JSBinaryOperatorPrecedence operatorPrecedences = JSPrecedence.binary[op];
       beginExpression(operatorPrecedences.precedence);
       use(node.left, operatorPrecedences.left);
       buffer.add(' $op ');
       use(node.right, operatorPrecedences.right);
       endExpression(operatorPrecedences.precedence);
@@ skipping 199 matching lines @@
     compiler.internalError('visitTry should not be called', instruction: node);
   }
 
   bool isEmptyElse(HBasicBlock start, HBasicBlock end) {
     if (start !== end) return false;
     if (start.last is !HGoto
         || start.last is HBreak
         || start.last is HContinue) {
       return false;
     }
-    HInstruction instruction = start.first;
     for (HInstruction instruction = start.first;
          instruction != start.last;
          instruction = instruction.next) {
       // Instructions generated at use site are okay because they do
       // not generate code in this else block.
       if (!isGenerateAtUseSite(instruction)) return false;
     }
     CopyHandler handler = variableNames.getCopyHandler(start);
     if (handler == null || handler.isEmpty()) return true;
     if (!handler.assignments.isEmpty()) return false;
     // If the block has a copy where the destination and source are
     // different, we will emit that copy, and therefore the block is
     // not empty.
     for (Copy copy in handler.copies) {
       String sourceName = variableNames.getName(copy.source);
       String destinationName = variableNames.getName(copy.destination);
       if (sourceName != destinationName) return false;
     }
     return true;
   }
 
   visitIf(HIf node) {
-    if (subGraph !== null && node.block === subGraph.end) {
+    if (logicalOperations.contains(node)) {
+      HPhi phi = node.joinBlock.phis.first;
+      if (!isGenerateAtUseSite(phi)) define(phi);
+      visitBasicBlock(node.joinBlock);
+      return;

[kasperl, 2012/06/04 11:12:55]

Maybe get rid of the two returns and add the last code under an else? If you
want to keep the returns, I would get rid of the else if (and just use if).

[ngeoffray, 2012/06/04 11:37:54]

Removed the else if.

+    } else if (subGraph !== null && node.block === subGraph.end) {
       if (isGeneratingExpression()) {
         use(node.inputs[0], JSPrecedence.EXPRESSION_PRECEDENCE);
       }
       return;
     }
     HInstruction condition = node.inputs[0];
     int preVisitedBlocks = 0;
     List<HBasicBlock> dominated = node.block.dominatedBlocks;
     HIfBlockInformation info = node.blockInformation.body;
     HBasicBlock joinBlock = node.joinBlock;
@@ skipping 280 matching lines @@
     visitBasicBlock(branchBlock.successors[1]);
     // With labeled breaks we can have more dominated blocks.
     if (dominated.length >= 3) {
       for (int i = 2; i < dominated.length; i++) {
         visitBasicBlock(dominated[i]);
       }
     }
   }
 
   visitNot(HNot node) {
+    assert(node.inputs.length == 1);
+    generateNot(node.inputs[0]);
+  }
+
+
+  void generateNot(HInstruction input) {
     bool isBuiltinRelational(HInstruction instruction) {
       if (instruction is !HRelational) return false;
       HRelational relational = instruction;
       return relational.builtin;
     }
 
-    assert(node.inputs.length == 1);
-    HInstruction input = node.inputs[0];
     if (input is HBoolify && isGenerateAtUseSite(input)) {
       beginExpression(JSPrecedence.EQUALITY_PRECEDENCE);
-      assert(node.inputs.length == 1);
       use(input.inputs[0], JSPrecedence.EQUALITY_PRECEDENCE);
       buffer.add(' !== true');
       endExpression(JSPrecedence.EQUALITY_PRECEDENCE);
     } else if (isBuiltinRelational(input) &&
                isGenerateAtUseSite(input) &&
                input.inputs[0].propagatedType.isUseful() &&
                !input.inputs[0].isDouble() &&
                input.inputs[1].propagatedType.isUseful() &&
                !input.inputs[1].isDouble()) {
       // This optimization doesn't work for NaN, so we only do it if the
@@ skipping 18 matching lines @@
       endExpression(JSPrecedence.PREFIX_PRECEDENCE);
     }
   }
 
   visitParameterValue(HParameterValue node) {
     assert(isGenerateAtUseSite(node));
     buffer.add(variableNames.getName(node));
   }
 
   visitPhi(HPhi node) {
-    String operation = logicalOperations[node];
-    if (operation !== null) {
-      emitLogicalOperation(node, operation);
+    HBasicBlock ifBlock = node.block.predecessors[0].predecessors[0];
+    // A phi can be generated at use site only if it is the result of a
+    // logical operation.

[Lasse Reichstein Nielsen, 2012/06/04 11:09:22]

Is this method only called for phis that are generated at use site? If so, say
so somewhere, otherwise explain this comment.
It seems not all logical-operator phis are generate-at-use-site.

[ngeoffray, 2012/06/04 11:37:54]

Done.

+    assert(logicalOperations.contains(ifBlock.last));
+    HInstruction input = ifBlock.last.inputs[0];
+    if (input.isConstantFalse()) {
+      use(node.inputs[1], JSPrecedence.EXPRESSION_PRECEDENCE);

[Lasse Reichstein Nielsen, 2012/06/04 11:09:22]

You should pass expectedPrecedence as second argument here and below.

[ngeoffray, 2012/06/04 11:37:54]

Done.

+    } else if (input.isConstantTrue()) {
+      use(node.inputs[0], JSPrecedence.EXPRESSION_PRECEDENCE);
     } else {
-      buffer.add('${variableNames.getName(node)}');
+      String operation = node.inputs[1].isConstantFalse() ? '&&' : '||';
+      JSBinaryOperatorPrecedence operatorPrecedence =
+          JSPrecedence.binary[operation];
+      beginExpression(operatorPrecedence.precedence);
+      if (operation == '||') {
+        if (input is HNot) {
+          use(input.inputs[0], operatorPrecedence.left);
+        } else {
+          generateNot(input);
+        }
+      } else {
+        use(input, operatorPrecedence.left);
+      }
+      buffer.add(" $operation ");
+      use(node.inputs[0], operatorPrecedence.right);
+      endExpression(operatorPrecedence.precedence);
     }
   }
 
   visitReturn(HReturn node) {
     addIndentation();
     assert(node.inputs.length == 1);
     HInstruction input = node.inputs[0];
     if (input.isConstantNull()) {
       buffer.add('return;\n');
     } else {
@@ skipping 851 matching lines @@
       startBailoutSwitch();
     }
   }
 
   void endLabeledBlock(HLabeledBlockInformation labeledBlockInfo) {
     if (labeledBlockInfo.body.start.hasGuards()) {
       endBailoutSwitch();
     }
   }
 }