pkg/compiler/lib/src/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.

import 'nodes.dart';

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.
  @override
  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);
  }

  // Limit for the size of `inputs` and `usedBy` lists. We assume lists longer
  // than this are OK in order to avoid the O(N^2) validation getting out of
  // hand.
  //
  // Poster child: corelib_2/regexp/pcre_test.dart, which has a 7KLOC main().
  static const int kMaxValidatedInstructionListLength = 1000;

  /// Verifies [instruction] is contained in [instructions] [count] times.
  static bool checkInstructionCount(
      List<HInstruction> instructions, HInstruction instruction, int count) {
    if (instructions.length > kMaxValidatedInstructionListLength) return true;
    int result = 0;
    for (int i = 0; i < instructions.length; i++) {
      if (identical(instructions[i], instruction)) result++;
    }
    return result == count;
  }

  /// 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, bool Function(HInstruction, int) f) {
    if (instructions.length > kMaxValidatedInstructionListLength) return true;
    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;
  }

  @override
  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() &&
              checkInstructionCount(input.usedBy, instruction, count);
        } else {
          return checkInstructionCount(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() &&
            checkInstructionCount(use.inputs, instruction, count);
      });
    }

    if (!identical(instruction.block, currentBlock)) {
      markInvalid("Instruction in wrong block");
    }
    if (!hasCorrectInputs()) {
      markInvalid("Incorrect inputs");
    }
    if (!hasCorrectUses()) {
      markInvalid("Incorrect uses");
    }
  }
}