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

lib/compiler/implementation/ssa/nodes.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.
 
 interface HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBailoutTarget(HBailoutTarget node);
   R visitBitAnd(HBitAnd node);
   R visitBitNot(HBitNot node);
   R visitBitOr(HBitOr node);
@@ skipping 586 matching lines @@
    * instruction instead.
    */
   void rewrite(HInstruction from, HInstruction to) {
     for (HInstruction use in from.usedBy) {
       use.rewriteInput(from, to);
     }
     to.usedBy.addAll(from.usedBy);
     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;
   }
 
   void addDominatedBlock(HBasicBlock block) {
     assert(isClosed());
     assert(id !== null && block.id !== null);
     assert(dominatedBlocks.indexOf(block) < 0);
     // Keep the list of dominated blocks sorted such that if there are two
     // succeeding blocks in the list, the predecessor is before the successor.
@@ skipping 380 matching lines @@
   }
 
   /**
    * The code for computing a bailout environment, and the code
    * generation must agree on what does not need to be captured,
    * so should always be generated at use site.
    */
   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 {
   HBoolify(HInstruction value) : super(<HInstruction>[value]);
   void prepareGvn(HTypeMap types) {
     assert(!hasSideEffects(types));
     setUseGvn();
   }
 
   HType get guaranteedType() => HType.BOOLEAN;
@@ skipping 1734 matching lines @@
   HBasicBlock get start() => expression.start;
   HBasicBlock get end() {
     // We don't create a switch block if there are no cases.
     assert(!statements.isEmpty());
     return statements.last().end;
   }
 
   bool accept(HStatementInformationVisitor visitor) =>
       visitor.visitSwitchInfo(this);
 }