Make sure that we don't assign phis before its uses.

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 {
   SsaCodeGeneratorTask(Compiler compiler) : super(compiler);
   String get name() => 'SSA code generator';
 
 
   String buildJavaScriptFunction(FunctionElement element,
@@ skipping 417 matching lines @@
       }
     }
 
     name = '${prefix}${prefixes[prefix]++}';
     while (usedNames.contains(name)) {
       name = '${prefix}${prefixes[prefix]++}';
     }
     return newName(id, name);
   }
 
+  // TODO(floitsch): share more code with [temporary].
+  String freshTemporary() {
+    String prefix = TEMPORARY_PREFIX;
+    String name = '${prefix}${prefixes[prefix]++}';
+    while (usedNames.contains(name)) {
+      name = '${prefix}${prefixes[prefix]++}';
+    }
+    String result = JsNames.getValid(name);
+    usedNames.add(result);
+    return result;
+  }
+
   bool temporaryExists(HInstruction instruction) {
     return names.containsKey(instruction.id);
   }
 
   String newName(int id, String name) {
     String result = JsNames.getValid(name);
     names[id] = result;
     usedNames.add(result);
     return result;
   }
@@ skipping 454 matching lines @@
 
       // If our special handling didn't succeed, we have to emit a generic
       // version. This still requires special handling for loop-blocks
       if (node.isLoopHeader()) {
         beginLoop(node);
       }
     }
     iterateBasicBlock(node);
   }
 
+  /** Generates the assignments for all phis of successors blocks. */
+  void assignPhisOfAllSuccessors(HBasicBlock node) {
+    Map<HInstruction, String> temporaryNamesOfPhis = null;
+
+    /**
+     * Generates the assignment [canonicalPhi] = [value].
+     *
+     * If the [canonicalPhi] has a temporary name (in [temporaryNamesOfPhis])
+     * then the temporary is assigned instead of the [canonicalPhi]. However,
+     * when the left and right-hand side are equal ([:canonicalPhi === value:])
+     * then the [canonicalPhi] is assigned with the temporary.

[Lasse Reichstein Nielsen, 2012/05/03 12:19:49]

Still a slightly odd "modal" function. Acceptable, but odd. Does it have to be
one function?

[floitsch, 2012/05/03 12:27:23]

It could be split, but there is quite some boiler-plate code... (like is it an
expression, a logical operation, ...)
If you see a nice way to split it, tell me and I will change it in another CL.

+     */
+    void generateAssignment(HPhi canonicalPhi, HInstruction value) {
+      if (isGeneratingExpression()) {
+        addExpressionSeparator();
+      } else {
+        addIndentation();
+      }
+      if (temporaryNamesOfPhis !== null &&
+          canonicalPhi !== value &&
+          temporaryNamesOfPhis.containsKey(canonicalPhi)) {
+        // This is the assignment to the temporary.
+        declareVariable(temporaryNamesOfPhis[canonicalPhi]);
+      } else if (!temporaryExists(canonicalPhi)) {
+        declareVariable(temporary(canonicalPhi));
+      } else {
+        buffer.add(temporary(canonicalPhi));
+      }
+      buffer.add(" = ");
+      bool isLogicalOperation = logicalOperations.containsKey(canonicalPhi);
+      if (isLogicalOperation) {
+        emitLogicalOperation(canonicalPhi, logicalOperations[canonicalPhi]);
+      } else if (canonicalPhi === value) {
+        buffer.add(temporaryNamesOfPhis[value]);
+      } else {
+        use(value, JSPrecedence.ASSIGNMENT_PRECEDENCE);
+      }
+      if (!isGeneratingExpression()) {
+        buffer.add(';\n');
+      }
+    }
+
+    // Assignments are delayed so that we don't overwrite phis that might
+    // be used as inputs.
+    // TODO(floitsch): improve phi assignments. Currently we introduce
+    // way too many temporary variables.
+    Map<HPhi, HInstruction> phiAssignments = new Map<HPhi, HInstruction>();
+
+    for (HBasicBlock successor in node.successors) {
+      int index = successor.predecessors.indexOf(node);
+      successor.forEachPhi((HPhi phi) {
+        bool isLogicalOperation = logicalOperations.containsKey(phi);
+        // In case the phi is being generated by another
+        // instruction.
+        if (isLogicalOperation && isGenerateAtUseSite(phi)) return;
+        HPhi canonicalPhi = phiEquivalence.getRepresentative(phi);
+        assert(!isLogicalOperation || canonicalPhi === phi);
+        HInstruction input = phi.inputs[index];
+        if (input is HPhi) {
+          input = phiEquivalence.getRepresentative(input);
+          // If we use the same variable, we don't need to create an
+          // assignment.
+          if (input === canonicalPhi) {
+            assert(!isLogicalOperation);
+            return;
+          }
+        }
+        phiAssignments[canonicalPhi] = input;
+      });
+    }
+
+    Set<HPhi> inputPhis = new Set<HPhi>();
+    List<HPhi> phis = <HPhi>[];
+
+    /**
+     * Transitively collects the phis that are used when emitting the [input]
+     * and adds them to [inputPhis]. Does not add phis that are equal to the
+     * [targetPhi] or are not in the [phiAssignments] map.
+     */
+    void collectInputPhis(HInstruction input, HPhi targetPhi) {
+      if (input is HPhi) {
+        HPhi canonicalPhi = phiEquivalence.getRepresentative(input);
+        // Self-updates are ok.
+        if (canonicalPhi !== targetPhi &&
+            phiAssignments.containsKey(canonicalPhi)) {
+          inputPhis.add(canonicalPhi);
+        }
+      } else if (isGenerateAtUseSite(input)) {
+        for (HInstruction inputOfInput in input.inputs) {
+          collectInputPhis(inputOfInput, targetPhi);
+        }
+      }
+    }
+
+    phiAssignments.forEach((HPhi targetPhi, HInstruction input) {
+      phis.add(targetPhi);
+      collectInputPhis(input, targetPhi);
+    });
+
+    if (inputPhis.isEmpty()) {
+      phiAssignments.forEach(generateAssignment);
+    } else {
+      // Emit the phiX=phiY assignments, taking care to break cycles.
+      // Example program:
+      //   var x = 499;
+      //   var y = 99;
+      //   while (x != 99) {
+      //     var tmp = x;  // <=== The tmp variable is removed in Ssa-form.
+      //     x = y;
+      //     y = tmp;
+      //   }
+      //
+      temporaryNamesOfPhis = new HashMap<HInstruction, String>();
+      // For phis that are used as inputs simply *always* allocate a
+      // temporary.
+      for (HPhi phi in phis) {
+        if (inputPhis.contains(phi)) {
+          String temporaryPhi = freshTemporary();
+          temporaryNamesOfPhis[phi] = temporaryPhi;
+        }
+        // The assignPhi uses temporary variables for the left-hand side if
+        // they exist.
+        generateAssignment(phi, phiAssignments[phi]);
+      }
+      // Finally assign the input phis.
+      for (HPhi phi in inputPhis) {
+        // The assignPhi special-cases phi assignments to itself and recognizes
+        // it as assignment from the temporary variable to the actual phi.
+        generateAssignment(phi, phi);
+      }
+    }
+  }
+
   void iterateBasicBlock(HBasicBlock node) {
     HInstruction instruction = node.first;
     while (instruction != null) {
       if (instruction === node.last) {
-        for (HBasicBlock successor in node.successors) {
-          int index = successor.predecessors.indexOf(node);
-          successor.forEachPhi((HPhi phi) {
-            bool isLogicalOperation = logicalOperations.containsKey(phi);
-            // In case the phi is being generated by another
-            // instruction.
-            if (isLogicalOperation && isGenerateAtUseSite(phi)) return;
-            HPhi canonicalPhi = phiEquivalence.getRepresentative(phi);
-            HInstruction input = phi.inputs[index];
-            if (input is HPhi) {
-              HPhi inputPhi = input;
-              HPhi canonicalInput = phiEquivalence.getRepresentative(inputPhi);
-              // If we use the same variable, we don't need to create an
-              // assignment.
-              if (canonicalInput === canonicalPhi) {
-                assert(!isLogicalOperation);
-                return;
-              }
-            }
-            if (isGeneratingExpression()) {
-              addExpressionSeparator();
-            } else {
-              addIndentation();
-            }
-            if (!temporaryExists(canonicalPhi)) {
-              declareVariable(temporary(canonicalPhi));
-            } else {
-              buffer.add(temporary(canonicalPhi));
-            }
-            buffer.add(" = ");
-            if (isLogicalOperation) {
-              emitLogicalOperation(phi, logicalOperations[phi]);
-            } else {
-              use(phi.inputs[index], JSPrecedence.ASSIGNMENT_PRECEDENCE);
-            }
-            if (!isGeneratingExpression()) {
-              buffer.add(';\n');
-            }
-          });
-        }
+        assignPhisOfAllSuccessors(node);
       }
 
       if (instruction is HGoto || instruction is HExit || instruction is HTry) {
         visit(instruction, JSPrecedence.STATEMENT_PRECEDENCE);
         return;
       } else if (!isGenerateAtUseSite(instruction)) {
         if (instruction is !HIf && instruction is !HTypeGuard &&
             instruction is !HLoopBranch && !isGeneratingExpression()) {
           addIndentation();
         }
@@ skipping 1328 matching lines @@
       startBailoutSwitch();
     }
   }
 
   void endLabeledBlock(HLabeledBlockInformation labeledBlockInfo) {
     if (labeledBlockInfo.body.start.hasGuards()) {
       endBailoutSwitch();
     }
   }
 }