| // 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. |
| 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"); |
| } |
| } |
| } |