Validate that all instructions dominate their inputs. And fix a bug where that did not happen.

lib/compiler/implementation/ssa/validate.dart

 // Copyright (c) 2011, 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 HValidator extends HInstructionVisitor {
   bool isValid = true;
   HGraph graph;
 
   void visitGraph(HGraph visitee) {
     graph = visitee;
@@ skipping 64 matching lines @@
         markInvalid("dominated block not pointing back");
       }
       if (dominated.id === null || dominated.id <= lastId) {
         markInvalid("dominated.id === null or dominated has <= id");
       }
       lastId = dominated.id;
     }
 
     if (!isValid) return;
     block.forEachPhi(visitInstruction);
+
+    // Make sure the parameters of a phi are dominating the
+    // corresponding predecessor block.

[Lasse Reichstein Nielsen, 2012/05/30 09:35:14]

We usually use "dominating" about blocks, not instructions.
Maybe say that the parameters/inputs' blocks dominate the corresponding
predecessor blocks (with a comment that blocks dominate themselves).

[ngeoffray, 2012/05/30 10:19:07]

Done.

+    block.forEachPhi((HPhi phi) {
+      for (int i = 0; i < phi.inputs.length; i++) {
+        HInstruction input = phi.inputs[i];
+        if (!input.block.dominates(block.predecessors[i])) {
+          markInvalid("Definition does not dominate use");
+        }
+      }
+    });
+
+    // Make sure the inputs of an instruction dominate the
+    // instruction.
+    block.forEachInstruction((HInstruction instruction) {
+      for (HInstruction input in instruction.inputs) {

[Lasse Reichstein Nielsen, 2012/05/30 09:35:14]

This is an un-pretty combination of functional for-each and iterator based
for-each. How about making blocks/instruction-lists Iterable<HInstruction>
instead?
Then you can do
 for (HPhi phi in block.phis)
and
 for (HInstruction instruction in block)

[ngeoffray, 2012/05/30 10:19:07]

As discussed, it doesn't look un-pretty to me, as I usually use forEach on
non-array data structures, and forin (or for (int i....)) on arrays.

+        if (!input.block.dominates(block)) {
+          markInvalid("Definition does not dominate use");
+        }
+      }
+    });
+
     super.visitBasicBlock(block);
   }
 
   /** Returns how often [instruction] is contained in [instructions]. */
   static int countInstruction(List<HInstruction> instructions,
                               HInstruction instruction) {
     int result = 0;
     for (int i = 0; i < instructions.length; i++) {
       if (instructions[i] === instruction) result++;
     }
@@ skipping 49 matching lines @@
       markInvalid("Instruction in wrong block");
     }
     if (!hasCorrectInputs()) {
       markInvalid("Incorrect inputs");
     }
     if (!hasCorrectUses()) {
       markInvalid("Incorrect uses");
     }
   }
 }