Compute liveness of instructions to get better and fewer variable names.

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;
  *   t2 = add(t0, t1);
  * t0 and t1 would be marked and the resulting code would then be:
  *   t2 = add(4, 3);
  */
 class SsaInstructionMerger extends HBaseVisitor {
   List<HInstruction> expectedInputs;
   Set<HInstruction> generateAtUseSite;
 
   SsaInstructionMerger(this.generateAtUseSite);
 
   void visitGraph(HGraph graph) {
     visitDominatorTree(graph);
   }
 
-  bool usedOnlyByPhis(instruction) {
-    for (HInstruction user in instruction.usedBy) {
-      if (user is! HPhi) return false;
-    }
-    return true;
-  }
-
   void visitInstruction(HInstruction instruction) {
     // A code motion invariant instruction is dealt before visiting it.
     assert(!instruction.isCodeMotionInvariant());
     for (HInstruction input in instruction.inputs) {
       if (!generateAtUseSite.contains(input)
           && !input.isCodeMotionInvariant()
           && input.usedBy.length == 1
           && input is! HPhi) {
         expectedInputs.add(input);
       }
@@ skipping 53 matching lines @@
         HInstruction nextInput = expectedInputs.removeLast();
         assert(!generateAtUseSite.contains(nextInput));
         assert(nextInput.usedBy.length == 1);
         if (nextInput === instruction) {
           return true;
         }
       }
       return false;
     }
 
-    for (HBasicBlock successor in block.successors) {
-      // Only add the input of the first phi. Making inputs of
-      // later phis generate-at-use-site would make them move
-      // accross the assignment of the first phi, and we need
-      // more analysis before we can do that.
-      HPhi phi = successor.phis.first;
-      if (phi != null) {
-        int index = successor.predecessors.indexOf(block);
-        HInstruction input = phi.inputs[index];
-        if (!generateAtUseSite.contains(input)
-            && !input.isCodeMotionInvariant()
-            && input.usedBy.length == 1
-            && input is! HPhi) {
-          expectedInputs.add(input);
-        }
-        break;
-      }
-    }
-
     block.last.accept(this);
     for (HInstruction instruction = block.last.previous;
          instruction !== null;
          instruction = instruction.previous) {
       if (generateAtUseSite.contains(instruction)) {
         continue;
       }
       if (instruction.isCodeMotionInvariant()) {
         generateAtUseSite.add(instruction);
         continue;
@@ skipping 286 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;
 }
-
-class PhiEquivalator {
-  final Equivalence<HPhi> equivalence;
-  final Map<HPhi, String> logicalOperations;
-  PhiEquivalator(this.equivalence, this.logicalOperations);
-
-  void analyzeGraph(HGraph graph) {
-    graph.blocks.forEach(analyzeBlock);
-  }
-
-  void analyzeBlock(HBasicBlock block) {
-    for (HPhi phi = block.phis.first; phi !== null; phi = phi.next) {
-      if (!logicalOperations.containsKey(phi) &&
-          phi.usedBy.length == 1 &&
-          phi.usedBy[0] is HPhi &&
-          phi.block.id < phi.usedBy[0].block.id) {
-        equivalence.makeEquivalent(phi, phi.usedBy[0]);
-      }
-    }
-  }
-}
-
-
-/**
- * Try to figure out which phis can be represented by the same temporary
- * variable, to avoid creating a new variable for each phi.
- */
-class Equivalence<T extends Hashable> {
-  // Represent equivalence classes of HPhi nodes as a forest of trees,
-  // where each tree is one equivalence class, and the root is the
-  // canonical representative for the equivalence class.
-  // Implement the forest by having each phi point to its parent in the tree,
-  // transitively linking it to the root, which itself doesn't have a parent.
-  final Map<T,T> representative;
-
-  Equivalence() : representative = new Map<T,T>();
-
-  T makeEquivalent(T a, T b) {
-    T root1 = getRepresentative(a);
-    T root2 = getRepresentative(b);
-    if (root1 !== root2) {
-      // Merge the trees for the two classes into one.
-      representative[root1] = root2;
-    }
-  }
-
-  /**
-   * Get the canonical representative for an equivalence class of phis.
-   */
-  T getRepresentative(T element) {
-    T parent = representative[element];
-    if (parent === null) {
-      // This is the root of a tree (a previously unseen node is considered
-      // the root of its own tree).
-      return element;
-    }
-    // Shorten the path for all the elements on the way to the root,
-    // improving the performance of future lookups.
-    T root = getRepresentative(parent);
-    if (root !== parent) representative[element] = root;
-    return root;
-  }
-
-  bool areEquivalent(T a, T b) {
-    return getRepresentative(a) === getRepresentative(b);
-  }
-}