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 453 matching lines @@
       if (success) return;
 
       // 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);
   }
 

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Please add dart-doc describing what the method does.
This *generates* assignments *for* all phis of successor blocks, right?

[floitsch, 2012/05/03 09:11:29]

Done.

+  void assignPhisOfAllSuccessors(HBasicBlock node) {
+    Map<HInstruction, String> phiTemporaries = null;

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Can you give a better name to this map? I gives no indication what role the
stored phi/string pairs have. I'm guessing it's temporary *names* for phis, so,
e.g., temporaryNameForPhis?

[floitsch, 2012/05/03 09:11:29]

renamed to temporaryNamesOfPhis. (dart-editor for the win ;)

+
+    void assignPhi(HPhi canonicalPhi, HInstruction value) {

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

assignPhi -> generateAssignment.
You don't assign to the phi, you generate an assignment that stores the result
of the phi in a (temporary) variable.
(Where "temporary" means one that isn't in the original source?)

[floitsch, 2012/05/03 09:11:29]

Renamed and added doc.

+      if (isGeneratingExpression()) {
+        addExpressionSeparator();
+      } else {
+        addIndentation();
+      }
+      if (phiTemporaries !== null &&
+          canonicalPhi !== value &&
+          phiTemporaries.containsKey(canonicalPhi)) {
+        // This is the assignment to the temporary.
+        declareVariable(phiTemporaries[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(phiTemporaries[value]);
+      } else {
+        use(value, JSPrecedence.ASSIGNMENT_PRECEDENCE);
+      }
+      if (!isGeneratingExpression()) {
+        buffer.add(';\n');
+      }
+    }
+
+    void collectInputPhis(HInstruction input, Set<HPhi> inputPhis,

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Dart-doc description of what the function does, please.
Would be easier if the condition wasn't parameterized entirely, but only by
targetPhi.

[floitsch, 2012/05/03 09:11:29]

Done.

+                          bool shouldBeAdded(HPhi phi)) {
+      if (input is HPhi) {
+        HPhi canonicalPhi = phiEquivalence.getRepresentative(input);
+        if (shouldBeAdded(canonicalPhi)) inputPhis.add(canonicalPhi);
+      } else if (isGenerateAtUseSite(input)) {
+        for (HInstruction inputOfInput in input.inputs) {
+          collectInputPhis(inputOfInput, inputPhis, shouldBeAdded);
+        }
+      }
+    }
+
+    // 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>();

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Please add empty line after declaration.

[floitsch, 2012/05/03 09:11:29]

Done.

+    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(canonicalPhi === phi || !isLogicalOperation);

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Reading this now, I actually prefer:
  assert(!isLogicalOperation || canonicalPhi === phi);

[floitsch, 2012/05/03 09:11:29]

Done.

+        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;
+      });
+    }
+

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Remove extra empty line.

[floitsch, 2012/05/03 09:11:29]

Done.

+
+    List<HPhi> phis = <HPhi>[];
+    Set<HPhi> inputPhis = new Set<HPhi>();
+    phiAssignments.forEach((HPhi targetPhi, HInstruction input) {
+      phis.add(targetPhi);
+      collectInputPhis(input, inputPhis, (HPhi phi) {
+        // Self-assignments are ok.
+        return phi !== targetPhi && phiAssignments.containsKey(phi);
+      });

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

Inline the shouldBeAdded function in collectInputPhis. It's always the same. Or
if you really want a function, make it a function declaration and call it from
collectInputPhis.

And/or move the declaration of collectInputPhis here, after the declaration of
inputPhis, so you don't need to pass the set as an argument.

[floitsch, 2012/05/03 09:11:29]

Done.

+    });
+
+    bool phisAreUsedAsInputs = !inputPhis.isEmpty();
+
+    if (!phisAreUsedAsInputs) {
+      phiAssignments.forEach(assignPhi);
+    } 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;
+      //   }
+      //
+      int length = phis.length;
+      phiTemporaries = new HashMap<HInstruction, String>();
+      // For phis that are used as inputs simply *always* allocate a
+      // temporary.
+      for (int i = 0; i < length; i++) {

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

You don't use "i", so perhaps just
  for (HPhi phi in phis) {
?

[floitsch, 2012/05/03 09:11:29]

Done.

+        HPhi phi = phis[i];
+        if (inputPhis.contains(phi)) {
+          String temporaryPhi = freshTemporary();
+          phiTemporaries[phi] = temporaryPhi;
+        }
+        // The assignPhi uses temporary variables for the left-hand side if
+        // they exist.
+        assignPhi(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.
+        assignPhi(phi, phi);
+      }

[Lasse Reichstein Nielsen, 2012/05/03 08:22:02]

For a later version, maybe we can try sorting the phis in an order where
assignments to phis are after uses, and only introduce temporaries if there is
one or more cycles.

[floitsch, 2012/05/03 09:11:29]

That's what the TODO implies.

+    }
+  }
+
   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();
     }
   }
 }