OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/verifier.h" | 5 #include "src/compiler/verifier.h" |
6 | 6 |
7 #include <deque> | 7 #include <deque> |
8 #include <queue> | 8 #include <queue> |
9 | 9 |
10 #include "src/compiler/generic-algorithm.h" | 10 #include "src/compiler/generic-algorithm.h" |
(...skipping 241 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
252 } | 252 } |
253 } | 253 } |
254 | 254 |
255 | 255 |
256 static bool HasDominatingDef(Schedule* schedule, Node* node, | 256 static bool HasDominatingDef(Schedule* schedule, Node* node, |
257 BasicBlock* container, BasicBlock* use_block, | 257 BasicBlock* container, BasicBlock* use_block, |
258 int use_pos) { | 258 int use_pos) { |
259 BasicBlock* block = use_block; | 259 BasicBlock* block = use_block; |
260 while (true) { | 260 while (true) { |
261 while (use_pos >= 0) { | 261 while (use_pos >= 0) { |
262 if (block->nodes_[use_pos] == node) return true; | 262 if (block->NodeAt(use_pos) == node) return true; |
263 use_pos--; | 263 use_pos--; |
264 } | 264 } |
265 block = block->dominator_; | 265 block = block->dominator(); |
266 if (block == NULL) break; | 266 if (block == NULL) break; |
267 use_pos = static_cast<int>(block->nodes_.size()) - 1; | 267 use_pos = static_cast<int>(block->NodeCount()) - 1; |
268 if (node == block->control_input_) return true; | 268 if (node == block->control_input()) return true; |
269 } | 269 } |
270 return false; | 270 return false; |
271 } | 271 } |
272 | 272 |
273 | 273 |
274 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, | 274 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, |
275 Node* node, int use_pos) { | 275 Node* node, int use_pos) { |
276 for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0; | 276 for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0; |
277 j--) { | 277 j--) { |
278 BasicBlock* use_block = block; | 278 BasicBlock* use_block = block; |
279 if (node->opcode() == IrOpcode::kPhi) { | 279 if (node->opcode() == IrOpcode::kPhi) { |
280 use_block = use_block->PredecessorAt(j); | 280 use_block = use_block->PredecessorAt(j); |
281 use_pos = static_cast<int>(use_block->nodes_.size()) - 1; | 281 use_pos = static_cast<int>(use_block->NodeCount()) - 1; |
282 } | 282 } |
283 Node* input = node->InputAt(j); | 283 Node* input = node->InputAt(j); |
284 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, | 284 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, |
285 use_pos)) { | 285 use_pos)) { |
286 V8_Fatal(__FILE__, __LINE__, | 286 V8_Fatal(__FILE__, __LINE__, |
287 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", | 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(), | 288 node->id(), node->op()->mnemonic(), block->id(), j, input->id(), |
289 input->op()->mnemonic()); | 289 input->op()->mnemonic()); |
290 } | 290 } |
291 } | 291 } |
292 } | 292 } |
293 | 293 |
294 | 294 |
295 void ScheduleVerifier::Run(Schedule* schedule) { | 295 void ScheduleVerifier::Run(Schedule* schedule) { |
296 const int count = schedule->BasicBlockCount(); | 296 const size_t count = schedule->BasicBlockCount(); |
297 Zone tmp_zone(schedule->zone()->isolate()); | 297 Zone tmp_zone(schedule->zone()->isolate()); |
298 Zone* zone = &tmp_zone; | 298 Zone* zone = &tmp_zone; |
299 BasicBlock* start = schedule->start(); | 299 BasicBlock* start = schedule->start(); |
300 BasicBlockVector* rpo_order = schedule->rpo_order(); | 300 BasicBlockVector* rpo_order = schedule->rpo_order(); |
301 | 301 |
302 // Verify the RPO order contains only blocks from this schedule. | 302 // Verify the RPO order contains only blocks from this schedule. |
303 CHECK_GE(count, static_cast<int>(rpo_order->size())); | 303 CHECK_GE(count, rpo_order->size()); |
304 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); | 304 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); |
305 ++b) { | 305 ++b) { |
306 CHECK_EQ((*b), schedule->GetBlockById((*b)->id())); | 306 CHECK_EQ((*b), schedule->GetBlockById((*b)->id())); |
307 } | 307 } |
308 | 308 |
309 // Verify RPO numbers of blocks. | 309 // Verify RPO numbers of blocks. |
310 CHECK_EQ(start, rpo_order->at(0)); // Start should be first. | 310 CHECK_EQ(start, rpo_order->at(0)); // Start should be first. |
311 for (size_t b = 0; b < rpo_order->size(); b++) { | 311 for (size_t b = 0; b < rpo_order->size(); b++) { |
312 BasicBlock* block = rpo_order->at(b); | 312 BasicBlock* block = rpo_order->at(b); |
313 CHECK_EQ(static_cast<int>(b), block->rpo_number_); | 313 CHECK_EQ(static_cast<int>(b), block->rpo_number()); |
314 BasicBlock* dom = block->dominator_; | 314 BasicBlock* dom = block->dominator(); |
315 if (b == 0) { | 315 if (b == 0) { |
316 // All blocks except start should have a dominator. | 316 // All blocks except start should have a dominator. |
317 CHECK_EQ(NULL, dom); | 317 CHECK_EQ(NULL, dom); |
318 } else { | 318 } else { |
319 // Check that the immediate dominator appears somewhere before the block. | 319 // Check that the immediate dominator appears somewhere before the block. |
320 CHECK_NE(NULL, dom); | 320 CHECK_NE(NULL, dom); |
321 CHECK_LT(dom->rpo_number_, block->rpo_number_); | 321 CHECK_LT(dom->rpo_number(), block->rpo_number()); |
322 } | 322 } |
323 } | 323 } |
324 | 324 |
325 // Verify that all blocks reachable from start are in the RPO. | 325 // Verify that all blocks reachable from start are in the RPO. |
326 BoolVector marked(count, false, zone); | 326 BoolVector marked(static_cast<int>(count), false, zone); |
327 { | 327 { |
328 ZoneQueue<BasicBlock*> queue(zone); | 328 ZoneQueue<BasicBlock*> queue(zone); |
329 queue.push(start); | 329 queue.push(start); |
330 marked[start->id()] = true; | 330 marked[start->id().ToSize()] = true; |
331 while (!queue.empty()) { | 331 while (!queue.empty()) { |
332 BasicBlock* block = queue.front(); | 332 BasicBlock* block = queue.front(); |
333 queue.pop(); | 333 queue.pop(); |
334 for (int s = 0; s < block->SuccessorCount(); s++) { | 334 for (size_t s = 0; s < block->SuccessorCount(); s++) { |
335 BasicBlock* succ = block->SuccessorAt(s); | 335 BasicBlock* succ = block->SuccessorAt(s); |
336 if (!marked[succ->id()]) { | 336 if (!marked[succ->id().ToSize()]) { |
337 marked[succ->id()] = true; | 337 marked[succ->id().ToSize()] = true; |
338 queue.push(succ); | 338 queue.push(succ); |
339 } | 339 } |
340 } | 340 } |
341 } | 341 } |
342 } | 342 } |
343 // Verify marked blocks are in the RPO. | 343 // Verify marked blocks are in the RPO. |
344 for (int i = 0; i < count; i++) { | 344 for (size_t i = 0; i < count; i++) { |
345 BasicBlock* block = schedule->GetBlockById(i); | 345 BasicBlock* block = schedule->GetBlockById(BasicBlock::Id::FromSize(i)); |
346 if (marked[i]) { | 346 if (marked[i]) { |
347 CHECK_GE(block->rpo_number_, 0); | 347 CHECK_GE(block->rpo_number(), 0); |
348 CHECK_EQ(block, rpo_order->at(block->rpo_number_)); | 348 CHECK_EQ(block, rpo_order->at(block->rpo_number())); |
349 } | 349 } |
350 } | 350 } |
351 // Verify RPO blocks are marked. | 351 // Verify RPO blocks are marked. |
352 for (size_t b = 0; b < rpo_order->size(); b++) { | 352 for (size_t b = 0; b < rpo_order->size(); b++) { |
353 CHECK(marked[rpo_order->at(b)->id()]); | 353 CHECK(marked[rpo_order->at(b)->id().ToSize()]); |
354 } | 354 } |
355 | 355 |
356 { | 356 { |
357 // Verify the dominance relation. | 357 // Verify the dominance relation. |
358 ZoneList<BitVector*> dominators(count, zone); | 358 ZoneVector<BitVector*> dominators(zone); |
359 dominators.Initialize(count, zone); | 359 dominators.resize(count, NULL); |
360 dominators.AddBlock(NULL, count, zone); | |
361 | 360 |
362 // Compute a set of all the nodes that dominate a given node by using | 361 // Compute a set of all the nodes that dominate a given node by using |
363 // a forward fixpoint. O(n^2). | 362 // a forward fixpoint. O(n^2). |
364 ZoneQueue<BasicBlock*> queue(zone); | 363 ZoneQueue<BasicBlock*> queue(zone); |
365 queue.push(start); | 364 queue.push(start); |
366 dominators[start->id()] = new (zone) BitVector(count, zone); | 365 dominators[start->id().ToSize()] = |
| 366 new (zone) BitVector(static_cast<int>(count), zone); |
367 while (!queue.empty()) { | 367 while (!queue.empty()) { |
368 BasicBlock* block = queue.front(); | 368 BasicBlock* block = queue.front(); |
369 queue.pop(); | 369 queue.pop(); |
370 BitVector* block_doms = dominators[block->id()]; | 370 BitVector* block_doms = dominators[block->id().ToSize()]; |
371 BasicBlock* idom = block->dominator_; | 371 BasicBlock* idom = block->dominator(); |
372 if (idom != NULL && !block_doms->Contains(idom->id())) { | 372 if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) { |
373 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", | 373 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", |
374 block->id(), idom->id()); | 374 block->id().ToInt(), idom->id().ToInt()); |
375 } | 375 } |
376 for (int s = 0; s < block->SuccessorCount(); s++) { | 376 for (size_t s = 0; s < block->SuccessorCount(); s++) { |
377 BasicBlock* succ = block->SuccessorAt(s); | 377 BasicBlock* succ = block->SuccessorAt(s); |
378 BitVector* succ_doms = dominators[succ->id()]; | 378 BitVector* succ_doms = dominators[succ->id().ToSize()]; |
379 | 379 |
380 if (succ_doms == NULL) { | 380 if (succ_doms == NULL) { |
381 // First time visiting the node. S.doms = B U B.doms | 381 // First time visiting the node. S.doms = B U B.doms |
382 succ_doms = new (zone) BitVector(count, zone); | 382 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); |
383 succ_doms->CopyFrom(*block_doms); | 383 succ_doms->CopyFrom(*block_doms); |
384 succ_doms->Add(block->id()); | 384 succ_doms->Add(block->id().ToInt()); |
385 dominators[succ->id()] = succ_doms; | 385 dominators[succ->id().ToSize()] = succ_doms; |
386 queue.push(succ); | 386 queue.push(succ); |
387 } else { | 387 } else { |
388 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) | 388 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) |
389 bool had = succ_doms->Contains(block->id()); | 389 bool had = succ_doms->Contains(block->id().ToInt()); |
390 if (had) succ_doms->Remove(block->id()); | 390 if (had) succ_doms->Remove(block->id().ToInt()); |
391 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); | 391 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); |
392 if (had) succ_doms->Add(block->id()); | 392 if (had) succ_doms->Add(block->id().ToInt()); |
393 } | 393 } |
394 } | 394 } |
395 } | 395 } |
396 | 396 |
397 // Verify the immediateness of dominators. | 397 // Verify the immediateness of dominators. |
398 for (BasicBlockVector::iterator b = rpo_order->begin(); | 398 for (BasicBlockVector::iterator b = rpo_order->begin(); |
399 b != rpo_order->end(); ++b) { | 399 b != rpo_order->end(); ++b) { |
400 BasicBlock* block = *b; | 400 BasicBlock* block = *b; |
401 BasicBlock* idom = block->dominator_; | 401 BasicBlock* idom = block->dominator(); |
402 if (idom == NULL) continue; | 402 if (idom == NULL) continue; |
403 BitVector* block_doms = dominators[block->id()]; | 403 BitVector* block_doms = dominators[block->id().ToSize()]; |
404 | 404 |
405 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { | 405 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { |
406 BasicBlock* dom = schedule->GetBlockById(it.Current()); | 406 BasicBlock* dom = |
407 if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) { | 407 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); |
| 408 if (dom != idom && |
| 409 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { |
408 V8_Fatal(__FILE__, __LINE__, | 410 V8_Fatal(__FILE__, __LINE__, |
409 "Block B%d is not immediately dominated by B%d", block->id(), | 411 "Block B%d is not immediately dominated by B%d", |
410 idom->id()); | 412 block->id().ToInt(), idom->id().ToInt()); |
411 } | 413 } |
412 } | 414 } |
413 } | 415 } |
414 } | 416 } |
415 | 417 |
416 // Verify phis are placed in the block of their control input. | 418 // Verify phis are placed in the block of their control input. |
417 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); | 419 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); |
418 ++b) { | 420 ++b) { |
419 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { | 421 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { |
420 Node* phi = *i; | 422 Node* phi = *i; |
421 if (phi->opcode() != IrOpcode::kPhi) continue; | 423 if (phi->opcode() != IrOpcode::kPhi) continue; |
422 // TODO(titzer): Nasty special case. Phis from RawMachineAssembler | 424 // TODO(titzer): Nasty special case. Phis from RawMachineAssembler |
423 // schedules don't have control inputs. | 425 // schedules don't have control inputs. |
424 if (phi->InputCount() > | 426 if (phi->InputCount() > |
425 OperatorProperties::GetValueInputCount(phi->op())) { | 427 OperatorProperties::GetValueInputCount(phi->op())) { |
426 Node* control = NodeProperties::GetControlInput(phi); | 428 Node* control = NodeProperties::GetControlInput(phi); |
427 CHECK(control->opcode() == IrOpcode::kMerge || | 429 CHECK(control->opcode() == IrOpcode::kMerge || |
428 control->opcode() == IrOpcode::kLoop); | 430 control->opcode() == IrOpcode::kLoop); |
429 CHECK_EQ((*b), schedule->block(control)); | 431 CHECK_EQ((*b), schedule->block(control)); |
430 } | 432 } |
431 } | 433 } |
432 } | 434 } |
433 | 435 |
434 // Verify that all uses are dominated by their definitions. | 436 // Verify that all uses are dominated by their definitions. |
435 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); | 437 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); |
436 ++b) { | 438 ++b) { |
437 BasicBlock* block = *b; | 439 BasicBlock* block = *b; |
438 | 440 |
439 // Check inputs to control for this block. | 441 // Check inputs to control for this block. |
440 Node* control = block->control_input_; | 442 Node* control = block->control_input(); |
441 if (control != NULL) { | 443 if (control != NULL) { |
442 CHECK_EQ(block, schedule->block(control)); | 444 CHECK_EQ(block, schedule->block(control)); |
443 CheckInputsDominate(schedule, block, control, | 445 CheckInputsDominate(schedule, block, control, |
444 static_cast<int>(block->nodes_.size()) - 1); | 446 static_cast<int>(block->NodeCount()) - 1); |
445 } | 447 } |
446 // Check inputs for all nodes in the block. | 448 // Check inputs for all nodes in the block. |
447 for (size_t i = 0; i < block->nodes_.size(); i++) { | 449 for (size_t i = 0; i < block->NodeCount(); i++) { |
448 Node* node = block->nodes_[i]; | 450 Node* node = block->NodeAt(i); |
449 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); | 451 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); |
450 } | 452 } |
451 } | 453 } |
452 } | 454 } |
453 } | 455 } |
454 } | 456 } |
455 } // namespace v8::internal::compiler | 457 } // namespace v8::internal::compiler |
OLD | NEW |