Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(556)

Unified Diff: frog/leg/ssa/validate.dart

Issue 9873021: Move frog/leg to lib/compiler/implementation. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 8 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « frog/leg/ssa/types.dart ('k') | frog/leg/ssa/value_set.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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");
- }
- }
-}
« no previous file with comments | « frog/leg/ssa/types.dart ('k') | frog/leg/ssa/value_set.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698