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 302 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
313 // All blocks except start should have a dominator. | 313 // All blocks except start should have a dominator. |
314 CHECK_EQ(NULL, dom); | 314 CHECK_EQ(NULL, dom); |
315 } else { | 315 } else { |
316 // Check that the immediate dominator appears somewhere before the block. | 316 // Check that the immediate dominator appears somewhere before the block. |
317 CHECK_NE(NULL, dom); | 317 CHECK_NE(NULL, dom); |
318 CHECK_LT(dom->rpo_number_, block->rpo_number_); | 318 CHECK_LT(dom->rpo_number_, block->rpo_number_); |
319 } | 319 } |
320 } | 320 } |
321 | 321 |
322 // Verify that all blocks reachable from start are in the RPO. | 322 // Verify that all blocks reachable from start are in the RPO. |
323 BoolVector marked(count, false, BoolVector::allocator_type(zone)); | 323 BoolVector marked(count, false, zone); |
324 { | 324 { |
325 std::queue<BasicBlock*> queue; | 325 ZoneQueue<BasicBlock*> queue(zone); |
326 queue.push(start); | 326 queue.push(start); |
327 marked[start->id()] = true; | 327 marked[start->id()] = true; |
328 while (!queue.empty()) { | 328 while (!queue.empty()) { |
329 BasicBlock* block = queue.front(); | 329 BasicBlock* block = queue.front(); |
330 queue.pop(); | 330 queue.pop(); |
331 for (int s = 0; s < block->SuccessorCount(); s++) { | 331 for (int s = 0; s < block->SuccessorCount(); s++) { |
332 BasicBlock* succ = block->SuccessorAt(s); | 332 BasicBlock* succ = block->SuccessorAt(s); |
333 if (!marked[succ->id()]) { | 333 if (!marked[succ->id()]) { |
334 marked[succ->id()] = true; | 334 marked[succ->id()] = true; |
335 queue.push(succ); | 335 queue.push(succ); |
(...skipping 15 matching lines...) Expand all Loading... |
351 } | 351 } |
352 | 352 |
353 { | 353 { |
354 // Verify the dominance relation. | 354 // Verify the dominance relation. |
355 ZoneList<BitVector*> dominators(count, zone); | 355 ZoneList<BitVector*> dominators(count, zone); |
356 dominators.Initialize(count, zone); | 356 dominators.Initialize(count, zone); |
357 dominators.AddBlock(NULL, count, zone); | 357 dominators.AddBlock(NULL, count, zone); |
358 | 358 |
359 // Compute a set of all the nodes that dominate a given node by using | 359 // Compute a set of all the nodes that dominate a given node by using |
360 // a forward fixpoint. O(n^2). | 360 // a forward fixpoint. O(n^2). |
361 std::queue<BasicBlock*> queue; | 361 ZoneQueue<BasicBlock*> queue(zone); |
362 queue.push(start); | 362 queue.push(start); |
363 dominators[start->id()] = new (zone) BitVector(count, zone); | 363 dominators[start->id()] = new (zone) BitVector(count, zone); |
364 while (!queue.empty()) { | 364 while (!queue.empty()) { |
365 BasicBlock* block = queue.front(); | 365 BasicBlock* block = queue.front(); |
366 queue.pop(); | 366 queue.pop(); |
367 BitVector* block_doms = dominators[block->id()]; | 367 BitVector* block_doms = dominators[block->id()]; |
368 BasicBlock* idom = schedule->dominator(block); | 368 BasicBlock* idom = schedule->dominator(block); |
369 if (idom != NULL && !block_doms->Contains(idom->id())) { | 369 if (idom != NULL && !block_doms->Contains(idom->id())) { |
370 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", | 370 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", |
371 block->id(), idom->id()); | 371 block->id(), idom->id()); |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
443 // Check inputs for all nodes in the block. | 443 // Check inputs for all nodes in the block. |
444 for (size_t i = 0; i < block->nodes_.size(); i++) { | 444 for (size_t i = 0; i < block->nodes_.size(); i++) { |
445 Node* node = block->nodes_[i]; | 445 Node* node = block->nodes_[i]; |
446 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); | 446 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); |
447 } | 447 } |
448 } | 448 } |
449 } | 449 } |
450 } | 450 } |
451 } | 451 } |
452 } // namespace v8::internal::compiler | 452 } // namespace v8::internal::compiler |
OLD | NEW |