Move dart2js from sdk/lib/_internal/compiler to pkg/compiler

sdk/lib/_internal/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.
-
-part of ssa;
-
-class HValidator extends HInstructionVisitor {
-  bool isValid = true;
-  HGraph graph;
-
-  void visitGraph(HGraph visitee) {
-    graph = visitee;
-    visitDominatorTree(visitee);
-  }
-
-  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 HLoopBranch) {
-      // Assert that the block we inserted to avoid critical edges satisfies
-      // our assumptions. That is, it must not contain any instructions
-      // (although it may contain phi-updates).
-      HBasicBlock avoidCriticalEdgeBlock = block.successors.last;
-      if (avoidCriticalEdgeBlock.first is! HGoto) {
-        markInvalid("Critical edge block contains instructions");
-      }
-    }
-    if (block.last is HGoto && block.successors.length != 1) {
-      markInvalid("Goto node with not exactly one successor");
-    }
-    if (block.last is HJump && block.successors.length != 1) {
-      markInvalid("Break or continue node without one successor");
-    }
-    if ((block.last is HReturn || block.last is HThrow) &&
-        (block.successors.length != 1 || !block.successors[0].isExitBlock())) {
-      markInvalid("Return or throw node with > 1 successor "
-                  "or not going to exit-block");
-    }
-    if (block.last is HExit && !block.successors.isEmpty) {
-      markInvalid("Exit block with successor");
-    }
-
-    if (block.successors.isEmpty && !block.isExitBlock()) {
-      markInvalid("Non-exit block without successor");
-    }
-
-    // Check 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 we don't have a critical edge.
-    if (isValid && block.successors.length > 1 &&
-        block.last is! HTry && block.last is! HExitTry &&
-        block.last is! HSwitch) {
-      for (HBasicBlock successor in block.successors) {
-        if (!isValid) break;
-        if (successor.predecessors.length >= 2) {
-          markInvalid("SSA graph contains critical edge.");
-        }
-      }
-    }
-
-    // Check that the entries in the dominated-list are sorted.
-    int lastId = 0;
-    for (HBasicBlock dominated in block.dominatedBlocks) {
-      if (!isValid) break;
-      if (!identical(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);
-
-    // Check that the blocks of the parameters of a phi are dominating the
-    // corresponding predecessor block. Note that a block dominates
-    // itself.
-    block.forEachPhi((HPhi phi) {
-      assert(phi.inputs.length <= block.predecessors.length);
-      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");
-        }
-      }
-    });
-
-    // Check that the blocks of the inputs of an instruction dominate the
-    // instruction's block.
-    block.forEachInstruction((HInstruction instruction) {
-      for (HInstruction input in instruction.inputs) {
-        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 (identical(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 (identical(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() {
-      bool inBasicBlock = instruction.isInBasicBlock();
-      return everyInstruction(instruction.inputs, (input, count) {
-        if (inBasicBlock) {
-          return input.isInBasicBlock()
-              && countInstruction(input.usedBy, instruction) == count;
-        } else {
-          return countInstruction(input.usedBy, instruction) == 0;
-        }
-      });
-    }
-
-    // Verifies that all our uses have us in their inputs.
-    bool hasCorrectUses() {
-      if (!instruction.isInBasicBlock()) return true;
-      return everyInstruction(instruction.usedBy, (use, count) {
-        return use.isInBasicBlock()
-            && countInstruction(use.inputs, instruction) == count;
-      });
-    }
-
-    if (!identical(instruction.block, currentBlock)) {
-      markInvalid("Instruction in wrong block");
-    }
-    if (!hasCorrectInputs()) {
-      markInvalid("Incorrect inputs");
-    }
-    if (!hasCorrectUses()) {
-      markInvalid("Incorrect uses");
-    }
-  }
-}