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 <deque> 8 #include <queue> 9 10 #include "src/compiler/generic-algorithm.h" 11 #include "src/compiler/generic-node-inl.h" 12 #include "src/compiler/generic-node.h" 13 #include "src/compiler/graph-inl.h" 14 #include "src/compiler/graph.h" 15 #include "src/compiler/node.h" 16 #include "src/compiler/node-properties-inl.h" 17 #include "src/compiler/node-properties.h" 18 #include "src/compiler/opcodes.h" 19 #include "src/compiler/operator.h" 20 #include "src/compiler/schedule.h" 21 #include "src/data-flow.h" 22 23 namespace v8 { 24 namespace internal { 25 namespace compiler { 26 27 28 static bool IsDefUseChainLinkPresent(Node* def, Node* use) { 29 Node::Uses uses = def->uses(); 30 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 31 if (*it == use) return true; 32 } 33 return false; 34 } 35 36 37 static bool IsUseDefChainLinkPresent(Node* def, Node* use) { 38 Node::Inputs inputs = use->inputs(); 39 for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) { 40 if (*it == def) return true; 41 } 42 return false; 43 } 44 45 46 class Verifier::Visitor : public NullNodeVisitor { 47 public: 48 explicit Visitor(Zone* zone) 49 : reached_from_start(NodeSet::key_compare(), 50 NodeSet::allocator_type(zone)), 51 reached_from_end(NodeSet::key_compare(), 52 NodeSet::allocator_type(zone)) {} 53 54 // Fulfills the PreNodeCallback interface. 55 GenericGraphVisit::Control Pre(Node* node); 56 57 bool from_start; 58 NodeSet reached_from_start; 59 NodeSet reached_from_end; 60 }; 61 62 63 GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) { 64 int value_count = OperatorProperties::GetValueInputCount(node->op()); 65 int context_count = OperatorProperties::GetContextInputCount(node->op()); 66 int frame_state_count = 67 OperatorProperties::GetFrameStateInputCount(node->op()); 68 int effect_count = OperatorProperties::GetEffectInputCount(node->op()); 69 int control_count = OperatorProperties::GetControlInputCount(node->op()); 70 71 // Verify number of inputs matches up. 72 int input_count = value_count + context_count + frame_state_count + 73 effect_count + control_count; 74 CHECK_EQ(input_count, node->InputCount()); 75 76 // Verify that frame state has been inserted for the nodes that need it. 77 if (OperatorProperties::HasFrameStateInput(node->op())) { 78 Node* frame_state = NodeProperties::GetFrameStateInput(node); 79 CHECK(frame_state->opcode() == IrOpcode::kFrameState || 80 // kFrameState uses undefined as a sentinel. 81 (node->opcode() == IrOpcode::kFrameState && 82 frame_state->opcode() == IrOpcode::kHeapConstant)); 83 CHECK(IsDefUseChainLinkPresent(frame_state, node)); 84 CHECK(IsUseDefChainLinkPresent(frame_state, node)); 85 } 86 87 // Verify all value inputs actually produce a value. 88 for (int i = 0; i < value_count; ++i) { 89 Node* value = NodeProperties::GetValueInput(node, i); 90 CHECK(OperatorProperties::HasValueOutput(value->op())); 91 CHECK(IsDefUseChainLinkPresent(value, node)); 92 CHECK(IsUseDefChainLinkPresent(value, node)); 93 } 94 95 // Verify all context inputs are value nodes. 96 for (int i = 0; i < context_count; ++i) { 97 Node* context = NodeProperties::GetContextInput(node); 98 CHECK(OperatorProperties::HasValueOutput(context->op())); 99 CHECK(IsDefUseChainLinkPresent(context, node)); 100 CHECK(IsUseDefChainLinkPresent(context, node)); 101 } 102 103 // Verify all effect inputs actually have an effect. 104 for (int i = 0; i < effect_count; ++i) { 105 Node* effect = NodeProperties::GetEffectInput(node); 106 CHECK(OperatorProperties::HasEffectOutput(effect->op())); 107 CHECK(IsDefUseChainLinkPresent(effect, node)); 108 CHECK(IsUseDefChainLinkPresent(effect, node)); 109 } 110 111 // Verify all control inputs are control nodes. 112 for (int i = 0; i < control_count; ++i) { 113 Node* control = NodeProperties::GetControlInput(node, i); 114 CHECK(OperatorProperties::HasControlOutput(control->op())); 115 CHECK(IsDefUseChainLinkPresent(control, node)); 116 CHECK(IsUseDefChainLinkPresent(control, node)); 117 } 118 119 // Verify all successors are projections if multiple value outputs exist. 120 if (OperatorProperties::GetValueOutputCount(node->op()) > 1) { 121 Node::Uses uses = node->uses(); 122 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 123 CHECK(!NodeProperties::IsValueEdge(it.edge()) || 124 (*it)->opcode() == IrOpcode::kProjection || 125 (*it)->opcode() == IrOpcode::kParameter); 126 } 127 } 128 129 switch (node->opcode()) { 130 case IrOpcode::kStart: 131 // Start has no inputs. 132 CHECK_EQ(0, input_count); 133 break; 134 case IrOpcode::kEnd: 135 // End has no outputs. 136 CHECK(!OperatorProperties::HasValueOutput(node->op())); 137 CHECK(!OperatorProperties::HasEffectOutput(node->op())); 138 CHECK(!OperatorProperties::HasControlOutput(node->op())); 139 break; 140 case IrOpcode::kDead: 141 // Dead is never connected to the graph. 142 UNREACHABLE(); 143 case IrOpcode::kBranch: { 144 // Branch uses are IfTrue and IfFalse. 145 Node::Uses uses = node->uses(); 146 bool got_true = false, got_false = false; 147 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 148 CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) || 149 ((*it)->opcode() == IrOpcode::kIfFalse && !got_false)); 150 if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true; 151 if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true; 152 } 153 // TODO(rossberg): Currently fails for various tests. 154 // CHECK(got_true && got_false); 155 break; 156 } 157 case IrOpcode::kIfTrue: 158 case IrOpcode::kIfFalse: 159 CHECK_EQ(IrOpcode::kBranch, 160 NodeProperties::GetControlInput(node, 0)->opcode()); 161 break; 162 case IrOpcode::kLoop: 163 case IrOpcode::kMerge: 164 break; 165 case IrOpcode::kReturn: 166 // TODO(rossberg): check successor is End 167 break; 168 case IrOpcode::kThrow: 169 // TODO(rossberg): what are the constraints on these? 170 break; 171 case IrOpcode::kParameter: { 172 // Parameters have the start node as inputs. 173 CHECK_EQ(1, input_count); 174 CHECK_EQ(IrOpcode::kStart, 175 NodeProperties::GetValueInput(node, 0)->opcode()); 176 // Parameter has an input that produces enough values. 177 int index = OpParameter<int>(node); 178 Node* input = NodeProperties::GetValueInput(node, 0); 179 // Currently, parameter indices start at -1 instead of 0. 180 CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1); 181 break; 182 } 183 case IrOpcode::kInt32Constant: 184 case IrOpcode::kInt64Constant: 185 case IrOpcode::kFloat64Constant: 186 case IrOpcode::kExternalConstant: 187 case IrOpcode::kNumberConstant: 188 case IrOpcode::kHeapConstant: 189 // Constants have no inputs. 190 CHECK_EQ(0, input_count); 191 break; 192 case IrOpcode::kPhi: { 193 // Phi input count matches parent control node. 194 CHECK_EQ(1, control_count); 195 Node* control = NodeProperties::GetControlInput(node, 0); 196 CHECK_EQ(value_count, 197 OperatorProperties::GetControlInputCount(control->op())); 198 break; 199 } 200 case IrOpcode::kEffectPhi: { 201 // EffectPhi input count matches parent control node. 202 CHECK_EQ(1, control_count); 203 Node* control = NodeProperties::GetControlInput(node, 0); 204 CHECK_EQ(effect_count, 205 OperatorProperties::GetControlInputCount(control->op())); 206 break; 207 } 208 case IrOpcode::kFrameState: 209 // TODO(jarin): what are the constraints on these? 210 break; 211 case IrOpcode::kCall: 212 // TODO(rossberg): what are the constraints on these? 213 break; 214 case IrOpcode::kProjection: { 215 // Projection has an input that produces enough values. 216 size_t index = OpParameter<size_t>(node); 217 Node* input = NodeProperties::GetValueInput(node, 0); 218 CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), 219 static_cast<int>(index)); 220 break; 221 } 222 default: 223 // TODO(rossberg): Check other node kinds. 224 break; 225 } 226 227 if (from_start) { 228 reached_from_start.insert(node); 229 } else { 230 reached_from_end.insert(node); 231 } 232 233 return GenericGraphVisit::CONTINUE; 234 } 235 236 237 void Verifier::Run(Graph* graph) { 238 Visitor visitor(graph->zone()); 239 240 CHECK_NE(NULL, graph->start()); 241 visitor.from_start = true; 242 graph->VisitNodeUsesFromStart(&visitor); 243 CHECK_NE(NULL, graph->end()); 244 visitor.from_start = false; 245 graph->VisitNodeInputsFromEnd(&visitor); 246 247 // All control nodes reachable from end are reachable from start. 248 for (NodeSet::iterator it = visitor.reached_from_end.begin(); 249 it != visitor.reached_from_end.end(); ++it) { 250 CHECK(!NodeProperties::IsControl(*it) || 251 visitor.reached_from_start.count(*it)); 252 } 253 } 254 255 256 static bool HasDominatingDef(Schedule* schedule, Node* node, 257 BasicBlock* container, BasicBlock* use_block, 258 int use_pos) { 259 BasicBlock* block = use_block; 260 while (true) { 261 while (use_pos >= 0) { 262 if (block->nodes_[use_pos] == node) return true; 263 use_pos--; 264 } 265 block = block->dominator_; 266 if (block == NULL) break; 267 use_pos = static_cast<int>(block->nodes_.size()) - 1; 268 if (node == block->control_input_) return true; 269 } 270 return false; 271 } 272 273 274 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, 275 Node* node, int use_pos) { 276 for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0; 277 j--) { 278 BasicBlock* use_block = block; 279 if (node->opcode() == IrOpcode::kPhi) { 280 use_block = use_block->PredecessorAt(j); 281 use_pos = static_cast<int>(use_block->nodes_.size()) - 1; 282 } 283 Node* input = node->InputAt(j); 284 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, 285 use_pos)) { 286 V8_Fatal(__FILE__, __LINE__, 287 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", 288 node->id(), node->op()->mnemonic(), block->id(), j, input->id(), 289 input->op()->mnemonic()); 290 } 291 } 292 } 293 294 295 void ScheduleVerifier::Run(Schedule* schedule) { 296 const int count = schedule->BasicBlockCount(); 297 Zone tmp_zone(schedule->zone()->isolate()); 298 Zone* zone = &tmp_zone; 299 BasicBlock* start = schedule->start(); 300 BasicBlockVector* rpo_order = schedule->rpo_order(); 301 302 // Verify the RPO order contains only blocks from this schedule. 303 CHECK_GE(count, static_cast<int>(rpo_order->size())); 304 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 305 ++b) { 306 CHECK_EQ((*b), schedule->GetBlockById((*b)->id())); 307 } 308 309 // Verify RPO numbers of blocks. 310 CHECK_EQ(start, rpo_order->at(0)); // Start should be first. 311 for (size_t b = 0; b < rpo_order->size(); b++) { 312 BasicBlock* block = rpo_order->at(b); 313 CHECK_EQ(static_cast<int>(b), block->rpo_number_); 314 BasicBlock* dom = block->dominator_; 315 if (b == 0) { 316 // All blocks except start should have a dominator. 317 CHECK_EQ(NULL, dom); 318 } else { 319 // Check that the immediate dominator appears somewhere before the block. 320 CHECK_NE(NULL, dom); 321 CHECK_LT(dom->rpo_number_, block->rpo_number_); 322 } 323 } 324 325 // Verify that all blocks reachable from start are in the RPO. 326 BoolVector marked(count, false, zone); 327 { 328 ZoneQueue<BasicBlock*> queue(zone); 329 queue.push(start); 330 marked[start->id()] = true; 331 while (!queue.empty()) { 332 BasicBlock* block = queue.front(); 333 queue.pop(); 334 for (int s = 0; s < block->SuccessorCount(); s++) { 335 BasicBlock* succ = block->SuccessorAt(s); 336 if (!marked[succ->id()]) { 337 marked[succ->id()] = true; 338 queue.push(succ); 339 } 340 } 341 } 342 } 343 // Verify marked blocks are in the RPO. 344 for (int i = 0; i < count; i++) { 345 BasicBlock* block = schedule->GetBlockById(i); 346 if (marked[i]) { 347 CHECK_GE(block->rpo_number_, 0); 348 CHECK_EQ(block, rpo_order->at(block->rpo_number_)); 349 } 350 } 351 // Verify RPO blocks are marked. 352 for (size_t b = 0; b < rpo_order->size(); b++) { 353 CHECK(marked[rpo_order->at(b)->id()]); 354 } 355 356 { 357 // Verify the dominance relation. 358 ZoneList<BitVector*> dominators(count, zone); 359 dominators.Initialize(count, zone); 360 dominators.AddBlock(NULL, count, zone); 361 362 // Compute a set of all the nodes that dominate a given node by using 363 // a forward fixpoint. O(n^2). 364 ZoneQueue<BasicBlock*> queue(zone); 365 queue.push(start); 366 dominators[start->id()] = new (zone) BitVector(count, zone); 367 while (!queue.empty()) { 368 BasicBlock* block = queue.front(); 369 queue.pop(); 370 BitVector* block_doms = dominators[block->id()]; 371 BasicBlock* idom = block->dominator_; 372 if (idom != NULL && !block_doms->Contains(idom->id())) { 373 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", 374 block->id(), idom->id()); 375 } 376 for (int s = 0; s < block->SuccessorCount(); s++) { 377 BasicBlock* succ = block->SuccessorAt(s); 378 BitVector* succ_doms = dominators[succ->id()]; 379 380 if (succ_doms == NULL) { 381 // First time visiting the node. S.doms = B U B.doms 382 succ_doms = new (zone) BitVector(count, zone); 383 succ_doms->CopyFrom(*block_doms); 384 succ_doms->Add(block->id()); 385 dominators[succ->id()] = succ_doms; 386 queue.push(succ); 387 } else { 388 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) 389 bool had = succ_doms->Contains(block->id()); 390 if (had) succ_doms->Remove(block->id()); 391 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); 392 if (had) succ_doms->Add(block->id()); 393 } 394 } 395 } 396 397 // Verify the immediateness of dominators. 398 for (BasicBlockVector::iterator b = rpo_order->begin(); 399 b != rpo_order->end(); ++b) { 400 BasicBlock* block = *b; 401 BasicBlock* idom = block->dominator_; 402 if (idom == NULL) continue; 403 BitVector* block_doms = dominators[block->id()]; 404 405 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { 406 BasicBlock* dom = schedule->GetBlockById(it.Current()); 407 if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) { 408 V8_Fatal(__FILE__, __LINE__, 409 "Block B%d is not immediately dominated by B%d", block->id(), 410 idom->id()); 411 } 412 } 413 } 414 } 415 416 // Verify phis are placed in the block of their control input. 417 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 418 ++b) { 419 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { 420 Node* phi = *i; 421 if (phi->opcode() != IrOpcode::kPhi) continue; 422 // TODO(titzer): Nasty special case. Phis from RawMachineAssembler 423 // schedules don't have control inputs. 424 if (phi->InputCount() > 425 OperatorProperties::GetValueInputCount(phi->op())) { 426 Node* control = NodeProperties::GetControlInput(phi); 427 CHECK(control->opcode() == IrOpcode::kMerge || 428 control->opcode() == IrOpcode::kLoop); 429 CHECK_EQ((*b), schedule->block(control)); 430 } 431 } 432 } 433 434 // Verify that all uses are dominated by their definitions. 435 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 436 ++b) { 437 BasicBlock* block = *b; 438 439 // Check inputs to control for this block. 440 Node* control = block->control_input_; 441 if (control != NULL) { 442 CHECK_EQ(block, schedule->block(control)); 443 CheckInputsDominate(schedule, block, control, 444 static_cast<int>(block->nodes_.size()) - 1); 445 } 446 // Check inputs for all nodes in the block. 447 for (size_t i = 0; i < block->nodes_.size(); i++) { 448 Node* node = block->nodes_[i]; 449 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); 450 } 451 } 452 } 453 } 454 } 455 } // namespace v8::internal::compiler 456
