| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 class HValidator extends HInstructionVisitor { | |
| 6 bool isValid = true; | |
| 7 HGraph graph; | |
| 8 | |
| 9 void visitGraph(HGraph graph) { | |
| 10 this.graph = graph; | |
| 11 visitDominatorTree(graph); | |
| 12 } | |
| 13 | |
| 14 void markInvalid(String reason) { | |
| 15 print(reason); | |
| 16 isValid = false; | |
| 17 } | |
| 18 | |
| 19 // Note that during construction of the Ssa graph the basic blocks are | |
| 20 // not required to be valid yet. | |
| 21 void visitBasicBlock(HBasicBlock block) { | |
| 22 currentBlock = block; | |
| 23 if (!isValid) return; // Don't need to continue if we are already invalid. | |
| 24 | |
| 25 // Test that the last instruction is a branching instruction and that the | |
| 26 // basic block contains the branch-target. | |
| 27 if (block.first === null || block.last === null) { | |
| 28 markInvalid("empty block"); | |
| 29 } | |
| 30 if (block.last is !HControlFlow) { | |
| 31 markInvalid("block ends with non-tail node."); | |
| 32 } | |
| 33 if (block.last is HIf && block.successors.length != 2) { | |
| 34 markInvalid("If node without two successors"); | |
| 35 } | |
| 36 if (block.last is HConditionalBranch && block.successors.length != 2) { | |
| 37 markInvalid("Conditional node without two successors"); | |
| 38 } | |
| 39 if (block.last is HGoto && block.successors.length != 1) { | |
| 40 markInvalid("Goto node without one successor"); | |
| 41 } | |
| 42 if (block.last is HReturn && | |
| 43 (block.successors.length != 1 || !block.successors[0].isExitBlock())) { | |
| 44 markInvalid("Return node with > 1 succesor or not going to exit-block"); | |
| 45 } | |
| 46 if (block.last is HExit && !block.successors.isEmpty()) { | |
| 47 markInvalid("Exit block with successor"); | |
| 48 } | |
| 49 if (block.last is HThrow && !block.successors.isEmpty()) { | |
| 50 markInvalid("Throw block with successor"); | |
| 51 } | |
| 52 | |
| 53 if (block.successors.isEmpty() && | |
| 54 block.last is !HThrow && | |
| 55 !block.isExitBlock()) { | |
| 56 markInvalid("Non-exit or throw block without successor"); | |
| 57 } | |
| 58 | |
| 59 // Make sure that successors ids are always higher than the current one. | |
| 60 // TODO(floitsch): this is, of course, not true for back-branches. | |
| 61 if (block.id === null) markInvalid("block without id"); | |
| 62 for (HBasicBlock successor in block.successors) { | |
| 63 if (!isValid) break; | |
| 64 if (successor.id === null) markInvalid("successor without id"); | |
| 65 if (successor.id <= block.id && !successor.isLoopHeader()) { | |
| 66 markInvalid("successor with lower id, but not a loop-header"); | |
| 67 } | |
| 68 } | |
| 69 | |
| 70 // Make sure that the entries in the dominated-list are sorted. | |
| 71 int lastId = 0; | |
| 72 for (HBasicBlock dominated in block.dominatedBlocks) { | |
| 73 if (!isValid) break; | |
| 74 if (dominated.dominator !== block) { | |
| 75 markInvalid("dominated block not pointing back"); | |
| 76 } | |
| 77 if (dominated.id === null || dominated.id <= lastId) { | |
| 78 markInvalid("dominated.id === null or dominated has <= id"); | |
| 79 } | |
| 80 lastId = dominated.id; | |
| 81 } | |
| 82 | |
| 83 if (!isValid) return; | |
| 84 block.forEachPhi(visitInstruction); | |
| 85 super.visitBasicBlock(block); | |
| 86 } | |
| 87 | |
| 88 /** Returns how often [instruction] is contained in [instructions]. */ | |
| 89 static int countInstruction(List<HInstruction> instructions, | |
| 90 HInstruction instruction) { | |
| 91 int result = 0; | |
| 92 for (int i = 0; i < instructions.length; i++) { | |
| 93 if (instructions[i] === instruction) result++; | |
| 94 } | |
| 95 return result; | |
| 96 } | |
| 97 | |
| 98 /** | |
| 99 * Returns true if the predicate returns true for every instruction in the | |
| 100 * list. The argument to [f] is an instruction with the count of how often | |
| 101 * it appeared in the list [instructions]. | |
| 102 */ | |
| 103 static bool everyInstruction(List<HInstruction> instructions, Function f) { | |
| 104 var copy = new List<HInstruction>.from(instructions); | |
| 105 // TODO(floitsch): there is currently no way to sort HInstructions before | |
| 106 // we have assigned an ID. The loop is therefore O(n^2) for now. | |
| 107 for (int i = 0; i < copy.length; i++) { | |
| 108 var current = copy[i]; | |
| 109 if (current === null) continue; | |
| 110 int count = 1; | |
| 111 for (int j = i + 1; j < copy.length; j++) { | |
| 112 if (copy[j] === current) { | |
| 113 copy[j] = null; | |
| 114 count++; | |
| 115 } | |
| 116 } | |
| 117 if (!f(current, count)) return false; | |
| 118 } | |
| 119 return true; | |
| 120 } | |
| 121 | |
| 122 void visitInstruction(HInstruction instruction) { | |
| 123 // Verifies that we are in the use list of our inputs. | |
| 124 bool hasCorrectInputs(instruction) { | |
| 125 bool inBasicBlock = instruction.isInBasicBlock(); | |
| 126 return everyInstruction(instruction.inputs, (input, count) { | |
| 127 if (inBasicBlock) { | |
| 128 return countInstruction(input.usedBy, instruction) == count; | |
| 129 } else { | |
| 130 return countInstruction(input.usedBy, instruction) == 0; | |
| 131 } | |
| 132 }); | |
| 133 } | |
| 134 | |
| 135 // Verifies that all our uses have us in their inputs. | |
| 136 bool hasCorrectUses(instruction) { | |
| 137 if (!instruction.isInBasicBlock()) return true; | |
| 138 return everyInstruction(instruction.usedBy, (use, count) { | |
| 139 return countInstruction(use.inputs, instruction) == count; | |
| 140 }); | |
| 141 } | |
| 142 | |
| 143 if (instruction.block !== currentBlock) { | |
| 144 markInvalid("Instruction in wrong block"); | |
| 145 } | |
| 146 if (!hasCorrectInputs(instruction)) { | |
| 147 markInvalid("Incorrect inputs"); | |
| 148 } | |
| 149 if (!hasCorrectUses(instruction)) { | |
| 150 markInvalid("Incorrect uses"); | |
| 151 } | |
| 152 } | |
| 153 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 9873021:
Move frog/leg to lib/compiler/implementation. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/