OLD | NEW |
(Empty) | |
| 1 // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "src/compiler/verifier.h" |
| 6 |
| 7 #include "src/compiler/generic-algorithm.h" |
| 8 #include "src/compiler/generic-node-inl.h" |
| 9 #include "src/compiler/generic-node.h" |
| 10 #include "src/compiler/graph-inl.h" |
| 11 #include "src/compiler/graph.h" |
| 12 #include "src/compiler/node.h" |
| 13 #include "src/compiler/node-properties-inl.h" |
| 14 #include "src/compiler/node-properties.h" |
| 15 #include "src/compiler/opcodes.h" |
| 16 #include "src/compiler/operator.h" |
| 17 |
| 18 namespace v8 { |
| 19 namespace internal { |
| 20 namespace compiler { |
| 21 |
| 22 |
| 23 static bool IsDefUseChainLinkPresent(Node* def, Node* use) { |
| 24 Node::Uses uses = def->uses(); |
| 25 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { |
| 26 if (*it == use) return true; |
| 27 } |
| 28 return false; |
| 29 } |
| 30 |
| 31 |
| 32 static bool IsUseDefChainLinkPresent(Node* def, Node* use) { |
| 33 Node::Inputs inputs = use->inputs(); |
| 34 for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) { |
| 35 if (*it == def) return true; |
| 36 } |
| 37 return false; |
| 38 } |
| 39 |
| 40 |
| 41 class Verifier::Visitor : public NullNodeVisitor { |
| 42 public: |
| 43 explicit Visitor(Zone* zone) |
| 44 : reached_from_start(NodeSet::key_compare(), |
| 45 NodeSet::allocator_type(zone)), |
| 46 reached_from_end(NodeSet::key_compare(), |
| 47 NodeSet::allocator_type(zone)) {} |
| 48 |
| 49 // Fulfills the PreNodeCallback interface. |
| 50 GenericGraphVisit::Control Pre(Node* node); |
| 51 |
| 52 bool from_start; |
| 53 NodeSet reached_from_start; |
| 54 NodeSet reached_from_end; |
| 55 }; |
| 56 |
| 57 |
| 58 GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) { |
| 59 int value_count = NodeProperties::GetValueInputCount(node); |
| 60 int context_count = NodeProperties::GetContextInputCount(node); |
| 61 int effect_count = NodeProperties::GetEffectInputCount(node); |
| 62 int control_count = NodeProperties::GetControlInputCount(node); |
| 63 |
| 64 // Verify number of inputs matches up. |
| 65 int input_count = value_count + context_count + effect_count + control_count; |
| 66 CHECK_EQ(input_count, node->InputCount()); |
| 67 |
| 68 // Verify all value inputs actually produce a value. |
| 69 for (int i = 0; i < value_count; ++i) { |
| 70 Node* value = NodeProperties::GetValueInput(node, i); |
| 71 CHECK(NodeProperties::HasValueOutput(value)); |
| 72 CHECK(IsDefUseChainLinkPresent(value, node)); |
| 73 CHECK(IsUseDefChainLinkPresent(value, node)); |
| 74 } |
| 75 |
| 76 // Verify all context inputs are value nodes. |
| 77 for (int i = 0; i < context_count; ++i) { |
| 78 Node* context = NodeProperties::GetContextInput(node); |
| 79 CHECK(NodeProperties::HasValueOutput(context)); |
| 80 CHECK(IsDefUseChainLinkPresent(context, node)); |
| 81 CHECK(IsUseDefChainLinkPresent(context, node)); |
| 82 } |
| 83 |
| 84 // Verify all effect inputs actually have an effect. |
| 85 for (int i = 0; i < effect_count; ++i) { |
| 86 Node* effect = NodeProperties::GetEffectInput(node); |
| 87 CHECK(NodeProperties::HasEffectOutput(effect)); |
| 88 CHECK(IsDefUseChainLinkPresent(effect, node)); |
| 89 CHECK(IsUseDefChainLinkPresent(effect, node)); |
| 90 } |
| 91 |
| 92 // Verify all control inputs are control nodes. |
| 93 for (int i = 0; i < control_count; ++i) { |
| 94 Node* control = NodeProperties::GetControlInput(node, i); |
| 95 CHECK(NodeProperties::HasControlOutput(control)); |
| 96 CHECK(IsDefUseChainLinkPresent(control, node)); |
| 97 CHECK(IsUseDefChainLinkPresent(control, node)); |
| 98 } |
| 99 |
| 100 // Verify all successors are projections if multiple value outputs exist. |
| 101 if (NodeProperties::GetValueOutputCount(node) > 1) { |
| 102 Node::Uses uses = node->uses(); |
| 103 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { |
| 104 CHECK(!NodeProperties::IsValueEdge(it.edge()) || |
| 105 (*it)->opcode() == IrOpcode::kProjection); |
| 106 } |
| 107 } |
| 108 |
| 109 switch (node->opcode()) { |
| 110 case IrOpcode::kStart: |
| 111 // Start has no inputs. |
| 112 CHECK_EQ(0, input_count); |
| 113 break; |
| 114 case IrOpcode::kEnd: |
| 115 // End has no outputs. |
| 116 CHECK(!NodeProperties::HasValueOutput(node)); |
| 117 CHECK(!NodeProperties::HasEffectOutput(node)); |
| 118 CHECK(!NodeProperties::HasControlOutput(node)); |
| 119 break; |
| 120 case IrOpcode::kDead: |
| 121 // Dead is never connected to the graph. |
| 122 UNREACHABLE(); |
| 123 case IrOpcode::kBranch: { |
| 124 // Branch uses are IfTrue and IfFalse. |
| 125 Node::Uses uses = node->uses(); |
| 126 bool got_true = false, got_false = false; |
| 127 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { |
| 128 CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) || |
| 129 ((*it)->opcode() == IrOpcode::kIfFalse && !got_false)); |
| 130 if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true; |
| 131 if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true; |
| 132 } |
| 133 // TODO(rossberg): Currently fails for various tests. |
| 134 // CHECK(got_true && got_false); |
| 135 break; |
| 136 } |
| 137 case IrOpcode::kIfTrue: |
| 138 case IrOpcode::kIfFalse: |
| 139 CHECK_EQ(IrOpcode::kBranch, |
| 140 NodeProperties::GetControlInput(node, 0)->opcode()); |
| 141 break; |
| 142 case IrOpcode::kLoop: |
| 143 case IrOpcode::kMerge: |
| 144 break; |
| 145 case IrOpcode::kReturn: |
| 146 // TODO(rossberg): check successor is End |
| 147 break; |
| 148 case IrOpcode::kThrow: |
| 149 // TODO(rossberg): what are the constraints on these? |
| 150 break; |
| 151 case IrOpcode::kParameter: |
| 152 // Parameters have no inputs. |
| 153 CHECK_EQ(0, input_count); |
| 154 break; |
| 155 case IrOpcode::kInt32Constant: |
| 156 case IrOpcode::kInt64Constant: |
| 157 case IrOpcode::kFloat64Constant: |
| 158 case IrOpcode::kExternalConstant: |
| 159 case IrOpcode::kNumberConstant: |
| 160 case IrOpcode::kHeapConstant: |
| 161 // Constants have no inputs. |
| 162 CHECK_EQ(0, input_count); |
| 163 break; |
| 164 case IrOpcode::kPhi: { |
| 165 // Phi input count matches parent control node. |
| 166 CHECK_EQ(1, control_count); |
| 167 Node* control = NodeProperties::GetControlInput(node, 0); |
| 168 CHECK_EQ(value_count, NodeProperties::GetControlInputCount(control)); |
| 169 break; |
| 170 } |
| 171 case IrOpcode::kEffectPhi: { |
| 172 // EffectPhi input count matches parent control node. |
| 173 CHECK_EQ(1, control_count); |
| 174 Node* control = NodeProperties::GetControlInput(node, 0); |
| 175 CHECK_EQ(effect_count, NodeProperties::GetControlInputCount(control)); |
| 176 break; |
| 177 } |
| 178 case IrOpcode::kLazyDeoptimization: |
| 179 // TODO(jarin): what are the constraints on these? |
| 180 break; |
| 181 case IrOpcode::kDeoptimize: |
| 182 // TODO(jarin): what are the constraints on these? |
| 183 break; |
| 184 case IrOpcode::kFrameState: |
| 185 // TODO(jarin): what are the constraints on these? |
| 186 break; |
| 187 case IrOpcode::kCall: |
| 188 // TODO(rossberg): what are the constraints on these? |
| 189 break; |
| 190 case IrOpcode::kContinuation: |
| 191 // TODO(jarin): what are the constraints on these? |
| 192 break; |
| 193 case IrOpcode::kProjection: { |
| 194 // Projection has an input that produces enough values. |
| 195 int index = static_cast<Operator1<int>*>(node->op())->parameter(); |
| 196 Node* input = NodeProperties::GetValueInput(node, 0); |
| 197 CHECK_GT(NodeProperties::GetValueOutputCount(input), index); |
| 198 break; |
| 199 } |
| 200 default: |
| 201 // TODO(rossberg): Check other node kinds. |
| 202 break; |
| 203 } |
| 204 |
| 205 if (from_start) { |
| 206 reached_from_start.insert(node); |
| 207 } else { |
| 208 reached_from_end.insert(node); |
| 209 } |
| 210 |
| 211 return GenericGraphVisit::CONTINUE; |
| 212 } |
| 213 |
| 214 |
| 215 void Verifier::Run(Graph* graph) { |
| 216 Visitor visitor(graph->zone()); |
| 217 |
| 218 visitor.from_start = true; |
| 219 graph->VisitNodeUsesFromStart(&visitor); |
| 220 visitor.from_start = false; |
| 221 graph->VisitNodeInputsFromEnd(&visitor); |
| 222 |
| 223 // All control nodes reachable from end are reachable from start. |
| 224 for (NodeSet::iterator it = visitor.reached_from_end.begin(); |
| 225 it != visitor.reached_from_end.end(); ++it) { |
| 226 CHECK(!NodeProperties::IsControl(*it) || |
| 227 visitor.reached_from_start.count(*it)); |
| 228 } |
| 229 } |
| 230 } |
| 231 } |
| 232 } // namespace v8::internal::compiler |
OLD | NEW |