Move frog/leg to lib/compiler/implementation.

frog/leg/ssa/validate.dart

Index: frog/leg/ssa/validate.dart
===================================================================
--- frog/leg/ssa/validate.dart	(revision 5925)
+++ frog/leg/ssa/validate.dart	(working copy)
@@ -1,153 +0,0 @@
-// 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 graph) {
-    this.graph = graph;
-    visitDominatorTree(graph);
-  }
-
-  void markInvalid(String reason) {
-    print(reason);
-    isValid = false;
-  }
-
-  // Note that during construction of the Ssa graph the basic blocks are
-  // not required to be valid yet.
-  void visitBasicBlock(HBasicBlock block) {
-    currentBlock = block;
-    if (!isValid) return;  // Don't need to continue if we are already invalid.
-
-    // Test that the last instruction is a branching instruction and that the
-    // basic block contains the branch-target.
-    if (block.first === null || block.last === null) {
-      markInvalid("empty block");
-    }
-    if (block.last is !HControlFlow) {
-      markInvalid("block ends with non-tail node.");
-    }
-    if (block.last is HIf && block.successors.length != 2) {
-      markInvalid("If node without two successors");
-    }
-    if (block.last is HConditionalBranch && block.successors.length != 2) {
-      markInvalid("Conditional node without two successors");
-    }
-    if (block.last is HGoto && block.successors.length != 1) {
-      markInvalid("Goto node without one successor");
-    }
-    if (block.last is HReturn &&
-        (block.successors.length != 1 || !block.successors[0].isExitBlock())) {
-      markInvalid("Return node with > 1 succesor or not going to exit-block");
-    }
-    if (block.last is HExit && !block.successors.isEmpty()) {
-      markInvalid("Exit block with successor");
-    }
-    if (block.last is HThrow && !block.successors.isEmpty()) {
-      markInvalid("Throw block with successor");
-    }
-
-    if (block.successors.isEmpty() &&
-        block.last is !HThrow &&
-        !block.isExitBlock()) {
-      markInvalid("Non-exit or throw block without successor");
-    }
-
-    // Make sure that successors ids are always higher than the current one.
-    // TODO(floitsch): this is, of course, not true for back-branches.
-    if (block.id === null) markInvalid("block without id");
-    for (HBasicBlock successor in block.successors) {
-      if (!isValid) break;
-      if (successor.id === null) markInvalid("successor without id");
-      if (successor.id <= block.id && !successor.isLoopHeader()) {
-        markInvalid("successor with lower id, but not a loop-header");
-      }
-    }
-
-    // Make sure that the entries in the dominated-list are sorted.
-    int lastId = 0;
-    for (HBasicBlock dominated in block.dominatedBlocks) {
-      if (!isValid) break;
-      if (dominated.dominator !== block) {
-        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);
-    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++;
-    }
-    return result;
-  }
-
-  /**
-   * Returns true if the predicate returns true for every instruction in the
-   * list. The argument to [f] is an instruction with the count of how often
-   * it appeared in the list [instructions].
-   */
-  static bool everyInstruction(List<HInstruction> instructions, Function f) {
-    var copy = new List<HInstruction>.from(instructions);
-    // TODO(floitsch): there is currently no way to sort HInstructions before
-    // we have assigned an ID. The loop is therefore O(n^2) for now.
-    for (int i = 0; i < copy.length; i++) {
-      var current = copy[i];
-      if (current === null) continue;
-      int count = 1;
-      for (int j = i + 1; j < copy.length; j++) {
-        if (copy[j] === current) {
-          copy[j] = null;
-          count++;
-        }
-      }
-      if (!f(current, count)) return false;
-    }
-    return true;
-  }
-
-  void visitInstruction(HInstruction instruction) {
-    // Verifies that we are in the use list of our inputs.
-    bool hasCorrectInputs(instruction) {
-      bool inBasicBlock = instruction.isInBasicBlock();
-      return everyInstruction(instruction.inputs, (input, count) {
-        if (inBasicBlock) {
-          return countInstruction(input.usedBy, instruction) == count;
-        } else {
-          return countInstruction(input.usedBy, instruction) == 0;
-        }
-      });
-    }
-
-    // Verifies that all our uses have us in their inputs.
-    bool hasCorrectUses(instruction) {
-      if (!instruction.isInBasicBlock()) return true;
-      return everyInstruction(instruction.usedBy, (use, count) {
-        return countInstruction(use.inputs, instruction) == count;
-      });
-    }
-
-    if (instruction.block !== currentBlock) {
-      markInvalid("Instruction in wrong block");
-    }
-    if (!hasCorrectInputs(instruction)) {
-      markInvalid("Incorrect inputs");
-    }
-    if (!hasCorrectUses(instruction)) {
-      markInvalid("Incorrect uses");
-    }
-  }
-}