OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 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/scheduler.h" | 5 #include "src/compiler/scheduler.h" |
6 | 6 |
7 #include "src/bit-vector.h" | 7 #include "src/bit-vector.h" |
8 #include "src/compiler/common-operator.h" | 8 #include "src/compiler/common-operator.h" |
9 #include "src/compiler/control-equivalence.h" | 9 #include "src/compiler/control-equivalence.h" |
10 #include "src/compiler/graph.h" | 10 #include "src/compiler/graph.h" |
(...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 component_end_ = schedule_->block(exit); | 259 component_end_ = schedule_->block(exit); |
260 scheduler_->equivalence_->Run(exit); | 260 scheduler_->equivalence_->Run(exit); |
261 while (!queue_.empty()) { // Breadth-first backwards traversal. | 261 while (!queue_.empty()) { // Breadth-first backwards traversal. |
262 Node* node = queue_.front(); | 262 Node* node = queue_.front(); |
263 queue_.pop(); | 263 queue_.pop(); |
264 | 264 |
265 // Use control dependence equivalence to find a canonical single-entry | 265 // Use control dependence equivalence to find a canonical single-entry |
266 // single-exit region that makes up a minimal component to be scheduled. | 266 // single-exit region that makes up a minimal component to be scheduled. |
267 if (IsSingleEntrySingleExitRegion(node, exit)) { | 267 if (IsSingleEntrySingleExitRegion(node, exit)) { |
268 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); | 268 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); |
269 DCHECK_EQ(NULL, component_entry_); | 269 DCHECK(!component_entry_); |
270 component_entry_ = node; | 270 component_entry_ = node; |
271 continue; | 271 continue; |
272 } | 272 } |
273 | 273 |
274 int max = NodeProperties::PastControlIndex(node); | 274 int max = NodeProperties::PastControlIndex(node); |
275 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 275 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
276 Queue(node->InputAt(i)); | 276 Queue(node->InputAt(i)); |
277 } | 277 } |
278 } | 278 } |
279 DCHECK_NE(NULL, component_entry_); | 279 DCHECK(component_entry_); |
280 | 280 |
281 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 281 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
282 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 282 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
283 } | 283 } |
284 } | 284 } |
285 | 285 |
286 private: | 286 private: |
287 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. | 287 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. |
288 friend class Scheduler; | 288 friend class Scheduler; |
289 | 289 |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
363 // Collect the branch-related projections from a node, such as IfTrue, | 363 // Collect the branch-related projections from a node, such as IfTrue, |
364 // IfFalse. | 364 // IfFalse. |
365 // TODO(titzer): consider moving this to node.h | 365 // TODO(titzer): consider moving this to node.h |
366 void CollectSuccessorProjections(Node* node, Node** buffer, | 366 void CollectSuccessorProjections(Node* node, Node** buffer, |
367 IrOpcode::Value true_opcode, | 367 IrOpcode::Value true_opcode, |
368 IrOpcode::Value false_opcode) { | 368 IrOpcode::Value false_opcode) { |
369 buffer[0] = NULL; | 369 buffer[0] = NULL; |
370 buffer[1] = NULL; | 370 buffer[1] = NULL; |
371 for (Node* use : node->uses()) { | 371 for (Node* use : node->uses()) { |
372 if (use->opcode() == true_opcode) { | 372 if (use->opcode() == true_opcode) { |
373 DCHECK_EQ(NULL, buffer[0]); | 373 DCHECK(!buffer[0]); |
374 buffer[0] = use; | 374 buffer[0] = use; |
375 } | 375 } |
376 if (use->opcode() == false_opcode) { | 376 if (use->opcode() == false_opcode) { |
377 DCHECK_EQ(NULL, buffer[1]); | 377 DCHECK(!buffer[1]); |
378 buffer[1] = use; | 378 buffer[1] = use; |
379 } | 379 } |
380 } | 380 } |
381 DCHECK_NE(NULL, buffer[0]); | 381 DCHECK(buffer[0]); |
382 DCHECK_NE(NULL, buffer[1]); | 382 DCHECK(buffer[1]); |
383 } | 383 } |
384 | 384 |
385 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, | 385 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, |
386 IrOpcode::Value true_opcode, | 386 IrOpcode::Value true_opcode, |
387 IrOpcode::Value false_opcode) { | 387 IrOpcode::Value false_opcode) { |
388 Node* successors[2]; | 388 Node* successors[2]; |
389 CollectSuccessorProjections(node, successors, true_opcode, false_opcode); | 389 CollectSuccessorProjections(node, successors, true_opcode, false_opcode); |
390 buffer[0] = schedule_->block(successors[0]); | 390 buffer[0] = schedule_->block(successors[0]); |
391 buffer[1] = schedule_->block(successors[1]); | 391 buffer[1] = schedule_->block(successors[1]); |
392 } | 392 } |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
441 } | 441 } |
442 | 442 |
443 void ConnectReturn(Node* ret) { | 443 void ConnectReturn(Node* ret) { |
444 Node* return_block_node = NodeProperties::GetControlInput(ret); | 444 Node* return_block_node = NodeProperties::GetControlInput(ret); |
445 BasicBlock* return_block = schedule_->block(return_block_node); | 445 BasicBlock* return_block = schedule_->block(return_block_node); |
446 TraceConnect(ret, return_block, NULL); | 446 TraceConnect(ret, return_block, NULL); |
447 schedule_->AddReturn(return_block, ret); | 447 schedule_->AddReturn(return_block, ret); |
448 } | 448 } |
449 | 449 |
450 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { | 450 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { |
451 DCHECK_NE(NULL, block); | 451 DCHECK(block); |
452 if (succ == NULL) { | 452 if (succ == NULL) { |
453 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), | 453 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), |
454 block->id().ToInt()); | 454 block->id().ToInt()); |
455 } else { | 455 } else { |
456 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), | 456 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), |
457 block->id().ToInt(), succ->id().ToInt()); | 457 block->id().ToInt(), succ->id().ToInt()); |
458 } | 458 } |
459 } | 459 } |
460 | 460 |
461 bool IsFinalMerge(Node* node) { | 461 bool IsFinalMerge(Node* node) { |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
526 beyond_end_(NULL), | 526 beyond_end_(NULL), |
527 loops_(zone), | 527 loops_(zone), |
528 backedges_(zone), | 528 backedges_(zone), |
529 stack_(zone), | 529 stack_(zone), |
530 previous_block_count_(0) {} | 530 previous_block_count_(0) {} |
531 | 531 |
532 // Computes the special reverse-post-order for the main control flow graph, | 532 // Computes the special reverse-post-order for the main control flow graph, |
533 // that is for the graph spanned between the schedule's start and end blocks. | 533 // that is for the graph spanned between the schedule's start and end blocks. |
534 void ComputeSpecialRPO() { | 534 void ComputeSpecialRPO() { |
535 DCHECK(schedule_->end()->SuccessorCount() == 0); | 535 DCHECK(schedule_->end()->SuccessorCount() == 0); |
536 DCHECK_EQ(NULL, order_); // Main order does not exist yet. | 536 DCHECK(!order_); // Main order does not exist yet. |
537 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); | 537 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); |
538 } | 538 } |
539 | 539 |
540 // Computes the special reverse-post-order for a partial control flow graph, | 540 // Computes the special reverse-post-order for a partial control flow graph, |
541 // that is for the graph spanned between the given {entry} and {end} blocks, | 541 // that is for the graph spanned between the given {entry} and {end} blocks, |
542 // then updates the existing ordering with this new information. | 542 // then updates the existing ordering with this new information. |
543 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { | 543 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { |
544 DCHECK_NE(NULL, order_); // Main order to be updated is present. | 544 DCHECK(order_); // Main order to be updated is present. |
545 ComputeAndInsertSpecialRPO(entry, end); | 545 ComputeAndInsertSpecialRPO(entry, end); |
546 } | 546 } |
547 | 547 |
548 // Serialize the previously computed order as a special reverse-post-order | 548 // Serialize the previously computed order as a special reverse-post-order |
549 // numbering for basic blocks into the final schedule. | 549 // numbering for basic blocks into the final schedule. |
550 void SerializeRPOIntoSchedule() { | 550 void SerializeRPOIntoSchedule() { |
551 int32_t number = 0; | 551 int32_t number = 0; |
552 for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) { | 552 for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) { |
553 b->set_rpo_number(number++); | 553 b->set_rpo_number(number++); |
554 schedule_->rpo_order()->push_back(b); | 554 schedule_->rpo_order()->push_back(b); |
(...skipping 911 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1466 for (Node* const node : *nodes) { | 1466 for (Node* const node : *nodes) { |
1467 schedule_->SetBlockForNode(to, node); | 1467 schedule_->SetBlockForNode(to, node); |
1468 scheduled_nodes_[to->id().ToSize()].push_back(node); | 1468 scheduled_nodes_[to->id().ToSize()].push_back(node); |
1469 } | 1469 } |
1470 nodes->clear(); | 1470 nodes->clear(); |
1471 } | 1471 } |
1472 | 1472 |
1473 } // namespace compiler | 1473 } // namespace compiler |
1474 } // namespace internal | 1474 } // namespace internal |
1475 } // namespace v8 | 1475 } // namespace v8 |
OLD | NEW |