When replacing an instruction with another in GVN-like optimizations, try to find a better user of …

lib/compiler/implementation/ssa/nodes.dart

Index: lib/compiler/implementation/ssa/nodes.dart
===================================================================
--- lib/compiler/implementation/ssa/nodes.dart	(revision 11018)
+++ lib/compiler/implementation/ssa/nodes.dart	(working copy)
@@ -604,6 +604,35 @@
     from.usedBy.clear();
   }
 
+  /**
+   * Rewrites all uses of the [from] instruction to using either the
+   * [to] instruction, or a [HCheck] instruction that has better type
+   * information on [to], and that dominates the user.
+   */
+  void rewriteWithBetterUser(HInstruction from, HInstruction to) {
+    List<HCheck> better = <HCheck>[];

[kasperl, 2012/08/21 10:37:41]

Wouldn't a Link<HCheck> be more efficient here? The common case is probably that
we do not need to allocate a list.

[ngeoffray, 2012/08/21 10:43:54]

Done.

+    for (HInstruction user in to.usedBy) {
+      if (user is HCheck && (user as HCheck).checkedInput == to) {

[kasperl, 2012/08/21 10:37:41]

===

[ngeoffray, 2012/08/21 10:43:54]

Done.

+        better.add(user);
+      }
+    }
+
+    if (better.isEmpty()) return rewrite(from, to);
+
+    L1: for (HInstruction user in from.usedBy) {
+      for (HCheck check in better) {
+        if (check.dominates(user)) {
+          user.rewriteInput(from, check);
+          check.usedBy.add(user);
+          continue L1;
+        }
+      }
+      user.rewriteInput(from, to);
+      to.usedBy.add(user);
+    }
+    from.usedBy.clear();
+  }
+
   bool isExitBlock() {
     return first === last && first is HExit;
   }
@@ -1004,6 +1033,17 @@
   bool isCodeMotionInvariant() => false;
 
   bool isStatement(HTypeMap types) => false;
+
+  bool dominates(HInstruction other) {
+    if (block != other.block) return block.dominates(other.block);
+
+    HInstruction current = this;
+    while (current != null) {

[kasperl, 2012/08/21 10:37:41]

!==

[ngeoffray, 2012/08/21 10:43:54]

Done.

+      if (current == other) return true;

[kasperl, 2012/08/21 10:37:41]

===

[ngeoffray, 2012/08/21 10:43:54]

Done.

+      current = current.next;
+    }
+    return false;
+  }
 }
 
 class HBoolify extends HInstruction {