| 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 <iomanip> | 7 #include <iomanip> |
| 8 | 8 |
| 9 #include "src/base/adapters.h" | 9 #include "src/base/adapters.h" |
| 10 #include "src/bit-vector.h" | 10 #include "src/bit-vector.h" |
| (...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 214 // subgraph, needed for scheduling. | 214 // subgraph, needed for scheduling. |
| 215 class CFGBuilder : public ZoneObject { | 215 class CFGBuilder : public ZoneObject { |
| 216 public: | 216 public: |
| 217 CFGBuilder(Zone* zone, Scheduler* scheduler) | 217 CFGBuilder(Zone* zone, Scheduler* scheduler) |
| 218 : zone_(zone), | 218 : zone_(zone), |
| 219 scheduler_(scheduler), | 219 scheduler_(scheduler), |
| 220 schedule_(scheduler->schedule_), | 220 schedule_(scheduler->schedule_), |
| 221 queued_(scheduler->graph_, 2), | 221 queued_(scheduler->graph_, 2), |
| 222 queue_(zone), | 222 queue_(zone), |
| 223 control_(zone), | 223 control_(zone), |
| 224 component_entry_(NULL), | 224 component_entry_(nullptr), |
| 225 component_start_(NULL), | 225 component_start_(nullptr), |
| 226 component_end_(NULL) {} | 226 component_end_(nullptr) {} |
| 227 | 227 |
| 228 // Run the control flow graph construction algorithm by walking the graph | 228 // Run the control flow graph construction algorithm by walking the graph |
| 229 // backwards from end through control edges, building and connecting the | 229 // backwards from end through control edges, building and connecting the |
| 230 // basic blocks for control nodes. | 230 // basic blocks for control nodes. |
| 231 void Run() { | 231 void Run() { |
| 232 ResetDataStructures(); | 232 ResetDataStructures(); |
| 233 Queue(scheduler_->graph_->end()); | 233 Queue(scheduler_->graph_->end()); |
| 234 | 234 |
| 235 while (!queue_.empty()) { // Breadth-first backwards traversal. | 235 while (!queue_.empty()) { // Breadth-first backwards traversal. |
| 236 Node* node = queue_.front(); | 236 Node* node = queue_.front(); |
| 237 queue_.pop(); | 237 queue_.pop(); |
| 238 int max = NodeProperties::PastControlIndex(node); | 238 int max = NodeProperties::PastControlIndex(node); |
| 239 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 239 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
| 240 Queue(node->InputAt(i)); | 240 Queue(node->InputAt(i)); |
| 241 } | 241 } |
| 242 } | 242 } |
| 243 | 243 |
| 244 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 244 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
| 245 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 245 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
| 246 } | 246 } |
| 247 } | 247 } |
| 248 | 248 |
| 249 // Run the control flow graph construction for a minimal control-connected | 249 // Run the control flow graph construction for a minimal control-connected |
| 250 // component ending in {exit} and merge that component into an existing | 250 // component ending in {exit} and merge that component into an existing |
| 251 // control flow graph at the bottom of {block}. | 251 // control flow graph at the bottom of {block}. |
| 252 void Run(BasicBlock* block, Node* exit) { | 252 void Run(BasicBlock* block, Node* exit) { |
| 253 ResetDataStructures(); | 253 ResetDataStructures(); |
| 254 Queue(exit); | 254 Queue(exit); |
| 255 | 255 |
| 256 component_entry_ = NULL; | 256 component_entry_ = nullptr; |
| 257 component_start_ = block; | 257 component_start_ = block; |
| 258 component_end_ = schedule_->block(exit); | 258 component_end_ = schedule_->block(exit); |
| 259 scheduler_->equivalence_->Run(exit); | 259 scheduler_->equivalence_->Run(exit); |
| 260 while (!queue_.empty()) { // Breadth-first backwards traversal. | 260 while (!queue_.empty()) { // Breadth-first backwards traversal. |
| 261 Node* node = queue_.front(); | 261 Node* node = queue_.front(); |
| 262 queue_.pop(); | 262 queue_.pop(); |
| 263 | 263 |
| 264 // Use control dependence equivalence to find a canonical single-entry | 264 // Use control dependence equivalence to find a canonical single-entry |
| 265 // single-exit region that makes up a minimal component to be scheduled. | 265 // single-exit region that makes up a minimal component to be scheduled. |
| 266 if (IsSingleEntrySingleExitRegion(node, exit)) { | 266 if (IsSingleEntrySingleExitRegion(node, exit)) { |
| (...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 370 ConnectCall(node); | 370 ConnectCall(node); |
| 371 } | 371 } |
| 372 break; | 372 break; |
| 373 default: | 373 default: |
| 374 break; | 374 break; |
| 375 } | 375 } |
| 376 } | 376 } |
| 377 | 377 |
| 378 BasicBlock* BuildBlockForNode(Node* node) { | 378 BasicBlock* BuildBlockForNode(Node* node) { |
| 379 BasicBlock* block = schedule_->block(node); | 379 BasicBlock* block = schedule_->block(node); |
| 380 if (block == NULL) { | 380 if (block == nullptr) { |
| 381 block = schedule_->NewBasicBlock(); | 381 block = schedule_->NewBasicBlock(); |
| 382 TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(), | 382 TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(), |
| 383 node->op()->mnemonic()); | 383 node->op()->mnemonic()); |
| 384 FixNode(block, node); | 384 FixNode(block, node); |
| 385 } | 385 } |
| 386 return block; | 386 return block; |
| 387 } | 387 } |
| 388 | 388 |
| 389 void BuildBlocksForSuccessors(Node* node) { | 389 void BuildBlocksForSuccessors(Node* node) { |
| 390 size_t const successor_cnt = node->op()->ControlOutputCount(); | 390 size_t const successor_cnt = node->op()->ControlOutputCount(); |
| (...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 494 for (Node* const input : merge->inputs()) { | 494 for (Node* const input : merge->inputs()) { |
| 495 BasicBlock* predecessor_block = FindPredecessorBlock(input); | 495 BasicBlock* predecessor_block = FindPredecessorBlock(input); |
| 496 TraceConnect(merge, predecessor_block, block); | 496 TraceConnect(merge, predecessor_block, block); |
| 497 schedule_->AddGoto(predecessor_block, block); | 497 schedule_->AddGoto(predecessor_block, block); |
| 498 } | 498 } |
| 499 } | 499 } |
| 500 | 500 |
| 501 void ConnectTailCall(Node* call) { | 501 void ConnectTailCall(Node* call) { |
| 502 Node* call_control = NodeProperties::GetControlInput(call); | 502 Node* call_control = NodeProperties::GetControlInput(call); |
| 503 BasicBlock* call_block = FindPredecessorBlock(call_control); | 503 BasicBlock* call_block = FindPredecessorBlock(call_control); |
| 504 TraceConnect(call, call_block, NULL); | 504 TraceConnect(call, call_block, nullptr); |
| 505 schedule_->AddTailCall(call_block, call); | 505 schedule_->AddTailCall(call_block, call); |
| 506 } | 506 } |
| 507 | 507 |
| 508 void ConnectReturn(Node* ret) { | 508 void ConnectReturn(Node* ret) { |
| 509 Node* return_control = NodeProperties::GetControlInput(ret); | 509 Node* return_control = NodeProperties::GetControlInput(ret); |
| 510 BasicBlock* return_block = FindPredecessorBlock(return_control); | 510 BasicBlock* return_block = FindPredecessorBlock(return_control); |
| 511 TraceConnect(ret, return_block, NULL); | 511 TraceConnect(ret, return_block, nullptr); |
| 512 schedule_->AddReturn(return_block, ret); | 512 schedule_->AddReturn(return_block, ret); |
| 513 } | 513 } |
| 514 | 514 |
| 515 void ConnectDeoptimize(Node* deopt) { | 515 void ConnectDeoptimize(Node* deopt) { |
| 516 Node* deoptimize_control = NodeProperties::GetControlInput(deopt); | 516 Node* deoptimize_control = NodeProperties::GetControlInput(deopt); |
| 517 BasicBlock* deoptimize_block = FindPredecessorBlock(deoptimize_control); | 517 BasicBlock* deoptimize_block = FindPredecessorBlock(deoptimize_control); |
| 518 TraceConnect(deopt, deoptimize_block, NULL); | 518 TraceConnect(deopt, deoptimize_block, nullptr); |
| 519 schedule_->AddDeoptimize(deoptimize_block, deopt); | 519 schedule_->AddDeoptimize(deoptimize_block, deopt); |
| 520 } | 520 } |
| 521 | 521 |
| 522 void ConnectThrow(Node* thr) { | 522 void ConnectThrow(Node* thr) { |
| 523 Node* throw_control = NodeProperties::GetControlInput(thr); | 523 Node* throw_control = NodeProperties::GetControlInput(thr); |
| 524 BasicBlock* throw_block = FindPredecessorBlock(throw_control); | 524 BasicBlock* throw_block = FindPredecessorBlock(throw_control); |
| 525 TraceConnect(thr, throw_block, NULL); | 525 TraceConnect(thr, throw_block, nullptr); |
| 526 schedule_->AddThrow(throw_block, thr); | 526 schedule_->AddThrow(throw_block, thr); |
| 527 } | 527 } |
| 528 | 528 |
| 529 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { | 529 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { |
| 530 DCHECK_NOT_NULL(block); | 530 DCHECK_NOT_NULL(block); |
| 531 if (succ == NULL) { | 531 if (succ == nullptr) { |
| 532 TRACE("Connect #%d:%s, id:%d -> end\n", node->id(), | 532 TRACE("Connect #%d:%s, id:%d -> end\n", node->id(), |
| 533 node->op()->mnemonic(), block->id().ToInt()); | 533 node->op()->mnemonic(), block->id().ToInt()); |
| 534 } else { | 534 } else { |
| 535 TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(), | 535 TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(), |
| 536 node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt()); | 536 node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt()); |
| 537 } | 537 } |
| 538 } | 538 } |
| 539 | 539 |
| 540 bool IsFinalMerge(Node* node) { | 540 bool IsFinalMerge(Node* node) { |
| 541 return (node->opcode() == IrOpcode::kMerge && | 541 return (node->opcode() == IrOpcode::kMerge && |
| (...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 595 // => If block A is a loop header, A appears before all blocks in the loop | 595 // => If block A is a loop header, A appears before all blocks in the loop |
| 596 // headed at A. | 596 // headed at A. |
| 597 // 2. All loops are contiguous in the order (i.e. no intervening blocks that | 597 // 2. All loops are contiguous in the order (i.e. no intervening blocks that |
| 598 // do not belong to the loop.) | 598 // do not belong to the loop.) |
| 599 // Note a simple RPO traversal satisfies (1) but not (2). | 599 // Note a simple RPO traversal satisfies (1) but not (2). |
| 600 class SpecialRPONumberer : public ZoneObject { | 600 class SpecialRPONumberer : public ZoneObject { |
| 601 public: | 601 public: |
| 602 SpecialRPONumberer(Zone* zone, Schedule* schedule) | 602 SpecialRPONumberer(Zone* zone, Schedule* schedule) |
| 603 : zone_(zone), | 603 : zone_(zone), |
| 604 schedule_(schedule), | 604 schedule_(schedule), |
| 605 order_(NULL), | 605 order_(nullptr), |
| 606 beyond_end_(NULL), | 606 beyond_end_(nullptr), |
| 607 loops_(zone), | 607 loops_(zone), |
| 608 backedges_(zone), | 608 backedges_(zone), |
| 609 stack_(zone), | 609 stack_(zone), |
| 610 previous_block_count_(0), | 610 previous_block_count_(0), |
| 611 empty_(0, zone) {} | 611 empty_(0, zone) {} |
| 612 | 612 |
| 613 // Computes the special reverse-post-order for the main control flow graph, | 613 // Computes the special reverse-post-order for the main control flow graph, |
| 614 // that is for the graph spanned between the schedule's start and end blocks. | 614 // that is for the graph spanned between the schedule's start and end blocks. |
| 615 void ComputeSpecialRPO() { | 615 void ComputeSpecialRPO() { |
| 616 DCHECK(schedule_->end()->SuccessorCount() == 0); | 616 DCHECK(schedule_->end()->SuccessorCount() == 0); |
| 617 DCHECK(!order_); // Main order does not exist yet. | 617 DCHECK(!order_); // Main order does not exist yet. |
| 618 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); | 618 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); |
| 619 } | 619 } |
| 620 | 620 |
| 621 // Computes the special reverse-post-order for a partial control flow graph, | 621 // Computes the special reverse-post-order for a partial control flow graph, |
| 622 // that is for the graph spanned between the given {entry} and {end} blocks, | 622 // that is for the graph spanned between the given {entry} and {end} blocks, |
| 623 // then updates the existing ordering with this new information. | 623 // then updates the existing ordering with this new information. |
| 624 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { | 624 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { |
| 625 DCHECK(order_); // Main order to be updated is present. | 625 DCHECK(order_); // Main order to be updated is present. |
| 626 ComputeAndInsertSpecialRPO(entry, end); | 626 ComputeAndInsertSpecialRPO(entry, end); |
| 627 } | 627 } |
| 628 | 628 |
| 629 // Serialize the previously computed order as a special reverse-post-order | 629 // Serialize the previously computed order as a special reverse-post-order |
| 630 // numbering for basic blocks into the final schedule. | 630 // numbering for basic blocks into the final schedule. |
| 631 void SerializeRPOIntoSchedule() { | 631 void SerializeRPOIntoSchedule() { |
| 632 int32_t number = 0; | 632 int32_t number = 0; |
| 633 for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) { | 633 for (BasicBlock* b = order_; b != nullptr; b = b->rpo_next()) { |
| 634 b->set_rpo_number(number++); | 634 b->set_rpo_number(number++); |
| 635 schedule_->rpo_order()->push_back(b); | 635 schedule_->rpo_order()->push_back(b); |
| 636 } | 636 } |
| 637 BeyondEndSentinel()->set_rpo_number(number); | 637 BeyondEndSentinel()->set_rpo_number(number); |
| 638 } | 638 } |
| 639 | 639 |
| 640 // Print and verify the special reverse-post-order. | 640 // Print and verify the special reverse-post-order. |
| 641 void PrintAndVerifySpecialRPO() { | 641 void PrintAndVerifySpecialRPO() { |
| 642 #if DEBUG | 642 #if DEBUG |
| 643 if (FLAG_trace_turbo_scheduler) PrintRPO(); | 643 if (FLAG_trace_turbo_scheduler) PrintRPO(); |
| (...skipping 26 matching lines...) Expand all Loading... |
| 670 | 670 |
| 671 struct LoopInfo { | 671 struct LoopInfo { |
| 672 BasicBlock* header; | 672 BasicBlock* header; |
| 673 ZoneVector<BasicBlock*>* outgoing; | 673 ZoneVector<BasicBlock*>* outgoing; |
| 674 BitVector* members; | 674 BitVector* members; |
| 675 LoopInfo* prev; | 675 LoopInfo* prev; |
| 676 BasicBlock* end; | 676 BasicBlock* end; |
| 677 BasicBlock* start; | 677 BasicBlock* start; |
| 678 | 678 |
| 679 void AddOutgoing(Zone* zone, BasicBlock* block) { | 679 void AddOutgoing(Zone* zone, BasicBlock* block) { |
| 680 if (outgoing == NULL) { | 680 if (outgoing == nullptr) { |
| 681 outgoing = new (zone->New(sizeof(ZoneVector<BasicBlock*>))) | 681 outgoing = new (zone->New(sizeof(ZoneVector<BasicBlock*>))) |
| 682 ZoneVector<BasicBlock*>(zone); | 682 ZoneVector<BasicBlock*>(zone); |
| 683 } | 683 } |
| 684 outgoing->push_back(block); | 684 outgoing->push_back(block); |
| 685 } | 685 } |
| 686 }; | 686 }; |
| 687 | 687 |
| 688 int Push(ZoneVector<SpecialRPOStackFrame>& stack, int depth, | 688 int Push(ZoneVector<SpecialRPOStackFrame>& stack, int depth, |
| 689 BasicBlock* child, int unvisited) { | 689 BasicBlock* child, int unvisited) { |
| 690 if (child->rpo_number() == unvisited) { | 690 if (child->rpo_number() == unvisited) { |
| (...skipping 15 matching lines...) Expand all Loading... |
| 706 return block->set_loop_number(loop_number); | 706 return block->set_loop_number(loop_number); |
| 707 } | 707 } |
| 708 static bool HasLoopNumber(BasicBlock* block) { | 708 static bool HasLoopNumber(BasicBlock* block) { |
| 709 return block->loop_number() >= 0; | 709 return block->loop_number() >= 0; |
| 710 } | 710 } |
| 711 | 711 |
| 712 // TODO(mstarzinger): We only need this special sentinel because some tests | 712 // TODO(mstarzinger): We only need this special sentinel because some tests |
| 713 // use the schedule's end block in actual control flow (e.g. with end having | 713 // use the schedule's end block in actual control flow (e.g. with end having |
| 714 // successors). Once this has been cleaned up we can use the end block here. | 714 // successors). Once this has been cleaned up we can use the end block here. |
| 715 BasicBlock* BeyondEndSentinel() { | 715 BasicBlock* BeyondEndSentinel() { |
| 716 if (beyond_end_ == NULL) { | 716 if (beyond_end_ == nullptr) { |
| 717 BasicBlock::Id id = BasicBlock::Id::FromInt(-1); | 717 BasicBlock::Id id = BasicBlock::Id::FromInt(-1); |
| 718 beyond_end_ = new (schedule_->zone()) BasicBlock(schedule_->zone(), id); | 718 beyond_end_ = new (schedule_->zone()) BasicBlock(schedule_->zone(), id); |
| 719 } | 719 } |
| 720 return beyond_end_; | 720 return beyond_end_; |
| 721 } | 721 } |
| 722 | 722 |
| 723 // Compute special RPO for the control flow graph between {entry} and {end}, | 723 // Compute special RPO for the control flow graph between {entry} and {end}, |
| 724 // mutating any existing order so that the result is still valid. | 724 // mutating any existing order so that the result is still valid. |
| 725 void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) { | 725 void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) { |
| 726 // RPO should not have been serialized for this schedule yet. | 726 // RPO should not have been serialized for this schedule yet. |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 770 } | 770 } |
| 771 | 771 |
| 772 // If no loops were encountered, then the order we computed was correct. | 772 // If no loops were encountered, then the order we computed was correct. |
| 773 if (num_loops > static_cast<int>(loops_.size())) { | 773 if (num_loops > static_cast<int>(loops_.size())) { |
| 774 // Otherwise, compute the loop information from the backedges in order | 774 // Otherwise, compute the loop information from the backedges in order |
| 775 // to perform a traversal that groups loop bodies together. | 775 // to perform a traversal that groups loop bodies together. |
| 776 ComputeLoopInfo(stack_, num_loops, &backedges_); | 776 ComputeLoopInfo(stack_, num_loops, &backedges_); |
| 777 | 777 |
| 778 // Initialize the "loop stack". Note the entry could be a loop header. | 778 // Initialize the "loop stack". Note the entry could be a loop header. |
| 779 LoopInfo* loop = | 779 LoopInfo* loop = |
| 780 HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : NULL; | 780 HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : nullptr; |
| 781 order = insertion_point; | 781 order = insertion_point; |
| 782 | 782 |
| 783 // Perform an iterative post-order traversal, visiting loop bodies before | 783 // Perform an iterative post-order traversal, visiting loop bodies before |
| 784 // edges that lead out of loops. Visits each block once, but linking loop | 784 // edges that lead out of loops. Visits each block once, but linking loop |
| 785 // sections together is linear in the loop size, so overall is | 785 // sections together is linear in the loop size, so overall is |
| 786 // O(|B| + max(loop_depth) * max(|loop|)) | 786 // O(|B| + max(loop_depth) * max(|loop|)) |
| 787 stack_depth = Push(stack_, 0, entry, kBlockUnvisited2); | 787 stack_depth = Push(stack_, 0, entry, kBlockUnvisited2); |
| 788 while (stack_depth > 0) { | 788 while (stack_depth > 0) { |
| 789 SpecialRPOStackFrame* frame = &stack_[stack_depth - 1]; | 789 SpecialRPOStackFrame* frame = &stack_[stack_depth - 1]; |
| 790 BasicBlock* block = frame->block; | 790 BasicBlock* block = frame->block; |
| 791 BasicBlock* succ = NULL; | 791 BasicBlock* succ = nullptr; |
| 792 | 792 |
| 793 if (block != end && frame->index < block->SuccessorCount()) { | 793 if (block != end && frame->index < block->SuccessorCount()) { |
| 794 // Process the next normal successor. | 794 // Process the next normal successor. |
| 795 succ = block->SuccessorAt(frame->index++); | 795 succ = block->SuccessorAt(frame->index++); |
| 796 } else if (HasLoopNumber(block)) { | 796 } else if (HasLoopNumber(block)) { |
| 797 // Process additional outgoing edges from the loop header. | 797 // Process additional outgoing edges from the loop header. |
| 798 if (block->rpo_number() == kBlockOnStack) { | 798 if (block->rpo_number() == kBlockOnStack) { |
| 799 // Finish the loop body the first time the header is left on the | 799 // Finish the loop body the first time the header is left on the |
| 800 // stack. | 800 // stack. |
| 801 DCHECK(loop != NULL && loop->header == block); | 801 DCHECK(loop != nullptr && loop->header == block); |
| 802 loop->start = PushFront(order, block); | 802 loop->start = PushFront(order, block); |
| 803 order = loop->end; | 803 order = loop->end; |
| 804 block->set_rpo_number(kBlockVisited2); | 804 block->set_rpo_number(kBlockVisited2); |
| 805 // Pop the loop stack and continue visiting outgoing edges within | 805 // Pop the loop stack and continue visiting outgoing edges within |
| 806 // the context of the outer loop, if any. | 806 // the context of the outer loop, if any. |
| 807 loop = loop->prev; | 807 loop = loop->prev; |
| 808 // We leave the loop header on the stack; the rest of this iteration | 808 // We leave the loop header on the stack; the rest of this iteration |
| 809 // and later iterations will go through its outgoing edges list. | 809 // and later iterations will go through its outgoing edges list. |
| 810 } | 810 } |
| 811 | 811 |
| 812 // Use the next outgoing edge if there are any. | 812 // Use the next outgoing edge if there are any. |
| 813 size_t outgoing_index = frame->index - block->SuccessorCount(); | 813 size_t outgoing_index = frame->index - block->SuccessorCount(); |
| 814 LoopInfo* info = &loops_[GetLoopNumber(block)]; | 814 LoopInfo* info = &loops_[GetLoopNumber(block)]; |
| 815 DCHECK(loop != info); | 815 DCHECK(loop != info); |
| 816 if (block != entry && info->outgoing != NULL && | 816 if (block != entry && info->outgoing != nullptr && |
| 817 outgoing_index < info->outgoing->size()) { | 817 outgoing_index < info->outgoing->size()) { |
| 818 succ = info->outgoing->at(outgoing_index); | 818 succ = info->outgoing->at(outgoing_index); |
| 819 frame->index++; | 819 frame->index++; |
| 820 } | 820 } |
| 821 } | 821 } |
| 822 | 822 |
| 823 if (succ != NULL) { | 823 if (succ != nullptr) { |
| 824 // Process the next successor. | 824 // Process the next successor. |
| 825 if (succ->rpo_number() == kBlockOnStack) continue; | 825 if (succ->rpo_number() == kBlockOnStack) continue; |
| 826 if (succ->rpo_number() == kBlockVisited2) continue; | 826 if (succ->rpo_number() == kBlockVisited2) continue; |
| 827 DCHECK(succ->rpo_number() == kBlockUnvisited2); | 827 DCHECK(succ->rpo_number() == kBlockUnvisited2); |
| 828 if (loop != NULL && !loop->members->Contains(succ->id().ToInt())) { | 828 if (loop != nullptr && !loop->members->Contains(succ->id().ToInt())) { |
| 829 // The successor is not in the current loop or any nested loop. | 829 // The successor is not in the current loop or any nested loop. |
| 830 // Add it to the outgoing edges of this loop and visit it later. | 830 // Add it to the outgoing edges of this loop and visit it later. |
| 831 loop->AddOutgoing(zone_, succ); | 831 loop->AddOutgoing(zone_, succ); |
| 832 } else { | 832 } else { |
| 833 // Push the successor onto the stack. | 833 // Push the successor onto the stack. |
| 834 stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2); | 834 stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2); |
| 835 if (HasLoopNumber(succ)) { | 835 if (HasLoopNumber(succ)) { |
| 836 // Push the inner loop onto the loop stack. | 836 // Push the inner loop onto the loop stack. |
| 837 DCHECK(GetLoopNumber(succ) < num_loops); | 837 DCHECK(GetLoopNumber(succ) < num_loops); |
| 838 LoopInfo* next = &loops_[GetLoopNumber(succ)]; | 838 LoopInfo* next = &loops_[GetLoopNumber(succ)]; |
| (...skipping 19 matching lines...) Expand all Loading... |
| 858 // Pop a single node off the stack and add it to the order. | 858 // Pop a single node off the stack and add it to the order. |
| 859 order = PushFront(order, block); | 859 order = PushFront(order, block); |
| 860 block->set_rpo_number(kBlockVisited2); | 860 block->set_rpo_number(kBlockVisited2); |
| 861 } | 861 } |
| 862 stack_depth--; | 862 stack_depth--; |
| 863 } | 863 } |
| 864 } | 864 } |
| 865 } | 865 } |
| 866 | 866 |
| 867 // Publish new order the first time. | 867 // Publish new order the first time. |
| 868 if (order_ == NULL) order_ = order; | 868 if (order_ == nullptr) order_ = order; |
| 869 | 869 |
| 870 // Compute the correct loop headers and set the correct loop ends. | 870 // Compute the correct loop headers and set the correct loop ends. |
| 871 LoopInfo* current_loop = NULL; | 871 LoopInfo* current_loop = nullptr; |
| 872 BasicBlock* current_header = entry->loop_header(); | 872 BasicBlock* current_header = entry->loop_header(); |
| 873 int32_t loop_depth = entry->loop_depth(); | 873 int32_t loop_depth = entry->loop_depth(); |
| 874 if (entry->IsLoopHeader()) --loop_depth; // Entry might be a loop header. | 874 if (entry->IsLoopHeader()) --loop_depth; // Entry might be a loop header. |
| 875 for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) { | 875 for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) { |
| 876 BasicBlock* current = b; | 876 BasicBlock* current = b; |
| 877 | 877 |
| 878 // Reset BasicBlock::rpo_number again. | 878 // Reset BasicBlock::rpo_number again. |
| 879 current->set_rpo_number(kBlockUnvisited1); | 879 current->set_rpo_number(kBlockUnvisited1); |
| 880 | 880 |
| 881 // Finish the previous loop(s) if we just exited them. | 881 // Finish the previous loop(s) if we just exited them. |
| 882 while (current_header != NULL && current == current_header->loop_end()) { | 882 while (current_header != nullptr && |
| 883 current == current_header->loop_end()) { |
| 883 DCHECK(current_header->IsLoopHeader()); | 884 DCHECK(current_header->IsLoopHeader()); |
| 884 DCHECK(current_loop != NULL); | 885 DCHECK_NOT_NULL(current_loop); |
| 885 current_loop = current_loop->prev; | 886 current_loop = current_loop->prev; |
| 886 current_header = current_loop == NULL ? NULL : current_loop->header; | 887 current_header = |
| 888 current_loop == nullptr ? nullptr : current_loop->header; |
| 887 --loop_depth; | 889 --loop_depth; |
| 888 } | 890 } |
| 889 current->set_loop_header(current_header); | 891 current->set_loop_header(current_header); |
| 890 | 892 |
| 891 // Push a new loop onto the stack if this loop is a loop header. | 893 // Push a new loop onto the stack if this loop is a loop header. |
| 892 if (HasLoopNumber(current)) { | 894 if (HasLoopNumber(current)) { |
| 893 ++loop_depth; | 895 ++loop_depth; |
| 894 current_loop = &loops_[GetLoopNumber(current)]; | 896 current_loop = &loops_[GetLoopNumber(current)]; |
| 895 BasicBlock* end = current_loop->end; | 897 BasicBlock* end = current_loop->end; |
| 896 current->set_loop_end(end == NULL ? BeyondEndSentinel() : end); | 898 current->set_loop_end(end == nullptr ? BeyondEndSentinel() : end); |
| 897 current_header = current_loop->header; | 899 current_header = current_loop->header; |
| 898 TRACE("id:%d is a loop header, increment loop depth to %d\n", | 900 TRACE("id:%d is a loop header, increment loop depth to %d\n", |
| 899 current->id().ToInt(), loop_depth); | 901 current->id().ToInt(), loop_depth); |
| 900 } | 902 } |
| 901 | 903 |
| 902 current->set_loop_depth(loop_depth); | 904 current->set_loop_depth(loop_depth); |
| 903 | 905 |
| 904 if (current->loop_header() == NULL) { | 906 if (current->loop_header() == nullptr) { |
| 905 TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(), | 907 TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(), |
| 906 current->loop_depth()); | 908 current->loop_depth()); |
| 907 } else { | 909 } else { |
| 908 TRACE("id:%d has loop header id:%d, (depth == %d)\n", | 910 TRACE("id:%d has loop header id:%d, (depth == %d)\n", |
| 909 current->id().ToInt(), current->loop_header()->id().ToInt(), | 911 current->id().ToInt(), current->loop_header()->id().ToInt(), |
| 910 current->loop_depth()); | 912 current->loop_depth()); |
| 911 } | 913 } |
| 912 } | 914 } |
| 913 } | 915 } |
| 914 | 916 |
| (...skipping 10 matching lines...) Expand all Loading... |
| 925 | 927 |
| 926 // Extend loop information vector. | 928 // Extend loop information vector. |
| 927 loops_.resize(num_loops, LoopInfo()); | 929 loops_.resize(num_loops, LoopInfo()); |
| 928 | 930 |
| 929 // Compute loop membership starting from backedges. | 931 // Compute loop membership starting from backedges. |
| 930 // O(max(loop_depth) * max(|loop|) | 932 // O(max(loop_depth) * max(|loop|) |
| 931 for (size_t i = 0; i < backedges->size(); i++) { | 933 for (size_t i = 0; i < backedges->size(); i++) { |
| 932 BasicBlock* member = backedges->at(i).first; | 934 BasicBlock* member = backedges->at(i).first; |
| 933 BasicBlock* header = member->SuccessorAt(backedges->at(i).second); | 935 BasicBlock* header = member->SuccessorAt(backedges->at(i).second); |
| 934 size_t loop_num = GetLoopNumber(header); | 936 size_t loop_num = GetLoopNumber(header); |
| 935 if (loops_[loop_num].header == NULL) { | 937 if (loops_[loop_num].header == nullptr) { |
| 936 loops_[loop_num].header = header; | 938 loops_[loop_num].header = header; |
| 937 loops_[loop_num].members = new (zone_) | 939 loops_[loop_num].members = new (zone_) |
| 938 BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_); | 940 BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_); |
| 939 } | 941 } |
| 940 | 942 |
| 941 int queue_length = 0; | 943 int queue_length = 0; |
| 942 if (member != header) { | 944 if (member != header) { |
| 943 // As long as the header doesn't have a backedge to itself, | 945 // As long as the header doesn't have a backedge to itself, |
| 944 // Push the member onto the queue and process its predecessors. | 946 // Push the member onto the queue and process its predecessors. |
| 945 if (!loops_[loop_num].members->Contains(member->id().ToInt())) { | 947 if (!loops_[loop_num].members->Contains(member->id().ToInt())) { |
| (...skipping 26 matching lines...) Expand all Loading... |
| 972 if (loops_.size() > 0) { | 974 if (loops_.size() > 0) { |
| 973 os << " ("; | 975 os << " ("; |
| 974 for (size_t i = 0; i < loops_.size(); i++) { | 976 for (size_t i = 0; i < loops_.size(); i++) { |
| 975 if (i > 0) os << " "; | 977 if (i > 0) os << " "; |
| 976 os << "id:" << loops_[i].header->id(); | 978 os << "id:" << loops_[i].header->id(); |
| 977 } | 979 } |
| 978 os << ")"; | 980 os << ")"; |
| 979 } | 981 } |
| 980 os << ":\n"; | 982 os << ":\n"; |
| 981 | 983 |
| 982 for (BasicBlock* block = order_; block != NULL; block = block->rpo_next()) { | 984 for (BasicBlock* block = order_; block != nullptr; |
| 985 block = block->rpo_next()) { |
| 983 os << std::setw(5) << "B" << block->rpo_number() << ":"; | 986 os << std::setw(5) << "B" << block->rpo_number() << ":"; |
| 984 for (size_t i = 0; i < loops_.size(); i++) { | 987 for (size_t i = 0; i < loops_.size(); i++) { |
| 985 bool range = loops_[i].header->LoopContains(block); | 988 bool range = loops_[i].header->LoopContains(block); |
| 986 bool membership = loops_[i].header != block && range; | 989 bool membership = loops_[i].header != block && range; |
| 987 os << (membership ? " |" : " "); | 990 os << (membership ? " |" : " "); |
| 988 os << (range ? "x" : " "); | 991 os << (range ? "x" : " "); |
| 989 } | 992 } |
| 990 os << " id:" << block->id() << ": "; | 993 os << " id:" << block->id() << ": "; |
| 991 if (block->loop_end() != NULL) { | 994 if (block->loop_end() != nullptr) { |
| 992 os << " range: [B" << block->rpo_number() << ", B" | 995 os << " range: [B" << block->rpo_number() << ", B" |
| 993 << block->loop_end()->rpo_number() << ")"; | 996 << block->loop_end()->rpo_number() << ")"; |
| 994 } | 997 } |
| 995 if (block->loop_header() != NULL) { | 998 if (block->loop_header() != nullptr) { |
| 996 os << " header: id:" << block->loop_header()->id(); | 999 os << " header: id:" << block->loop_header()->id(); |
| 997 } | 1000 } |
| 998 if (block->loop_depth() > 0) { | 1001 if (block->loop_depth() > 0) { |
| 999 os << " depth: " << block->loop_depth(); | 1002 os << " depth: " << block->loop_depth(); |
| 1000 } | 1003 } |
| 1001 os << "\n"; | 1004 os << "\n"; |
| 1002 } | 1005 } |
| 1003 } | 1006 } |
| 1004 | 1007 |
| 1005 void VerifySpecialRPO() { | 1008 void VerifySpecialRPO() { |
| 1006 BasicBlockVector* order = schedule_->rpo_order(); | 1009 BasicBlockVector* order = schedule_->rpo_order(); |
| 1007 DCHECK(order->size() > 0); | 1010 DCHECK(order->size() > 0); |
| 1008 DCHECK((*order)[0]->id().ToInt() == 0); // entry should be first. | 1011 DCHECK((*order)[0]->id().ToInt() == 0); // entry should be first. |
| 1009 | 1012 |
| 1010 for (size_t i = 0; i < loops_.size(); i++) { | 1013 for (size_t i = 0; i < loops_.size(); i++) { |
| 1011 LoopInfo* loop = &loops_[i]; | 1014 LoopInfo* loop = &loops_[i]; |
| 1012 BasicBlock* header = loop->header; | 1015 BasicBlock* header = loop->header; |
| 1013 BasicBlock* end = header->loop_end(); | 1016 BasicBlock* end = header->loop_end(); |
| 1014 | 1017 |
| 1015 DCHECK(header != NULL); | 1018 DCHECK_NOT_NULL(header); |
| 1016 DCHECK(header->rpo_number() >= 0); | 1019 DCHECK(header->rpo_number() >= 0); |
| 1017 DCHECK(header->rpo_number() < static_cast<int>(order->size())); | 1020 DCHECK(header->rpo_number() < static_cast<int>(order->size())); |
| 1018 DCHECK(end != NULL); | 1021 DCHECK_NOT_NULL(end); |
| 1019 DCHECK(end->rpo_number() <= static_cast<int>(order->size())); | 1022 DCHECK(end->rpo_number() <= static_cast<int>(order->size())); |
| 1020 DCHECK(end->rpo_number() > header->rpo_number()); | 1023 DCHECK(end->rpo_number() > header->rpo_number()); |
| 1021 DCHECK(header->loop_header() != header); | 1024 DCHECK(header->loop_header() != header); |
| 1022 | 1025 |
| 1023 // Verify the start ... end list relationship. | 1026 // Verify the start ... end list relationship. |
| 1024 int links = 0; | 1027 int links = 0; |
| 1025 BasicBlock* block = loop->start; | 1028 BasicBlock* block = loop->start; |
| 1026 DCHECK_EQ(header, block); | 1029 DCHECK_EQ(header, block); |
| 1027 bool end_found; | 1030 bool end_found; |
| 1028 while (true) { | 1031 while (true) { |
| 1029 if (block == NULL || block == loop->end) { | 1032 if (block == nullptr || block == loop->end) { |
| 1030 end_found = (loop->end == block); | 1033 end_found = (loop->end == block); |
| 1031 break; | 1034 break; |
| 1032 } | 1035 } |
| 1033 // The list should be in same order as the final result. | 1036 // The list should be in same order as the final result. |
| 1034 DCHECK(block->rpo_number() == links + header->rpo_number()); | 1037 DCHECK(block->rpo_number() == links + header->rpo_number()); |
| 1035 links++; | 1038 links++; |
| 1036 block = block->rpo_next(); | 1039 block = block->rpo_next(); |
| 1037 DCHECK_LT(links, static_cast<int>(2 * order->size())); // cycle? | 1040 DCHECK_LT(links, static_cast<int>(2 * order->size())); // cycle? |
| 1038 } | 1041 } |
| 1039 DCHECK(links > 0); | 1042 DCHECK(links > 0); |
| 1040 DCHECK(links == end->rpo_number() - header->rpo_number()); | 1043 DCHECK(links == end->rpo_number() - header->rpo_number()); |
| 1041 DCHECK(end_found); | 1044 DCHECK(end_found); |
| 1042 | 1045 |
| 1043 // Check loop depth of the header. | 1046 // Check loop depth of the header. |
| 1044 int loop_depth = 0; | 1047 int loop_depth = 0; |
| 1045 for (LoopInfo* outer = loop; outer != NULL; outer = outer->prev) { | 1048 for (LoopInfo* outer = loop; outer != nullptr; outer = outer->prev) { |
| 1046 loop_depth++; | 1049 loop_depth++; |
| 1047 } | 1050 } |
| 1048 DCHECK_EQ(loop_depth, header->loop_depth()); | 1051 DCHECK_EQ(loop_depth, header->loop_depth()); |
| 1049 | 1052 |
| 1050 // Check the contiguousness of loops. | 1053 // Check the contiguousness of loops. |
| 1051 int count = 0; | 1054 int count = 0; |
| 1052 for (int j = 0; j < static_cast<int>(order->size()); j++) { | 1055 for (int j = 0; j < static_cast<int>(order->size()); j++) { |
| 1053 BasicBlock* block = order->at(j); | 1056 BasicBlock* block = order->at(j); |
| 1054 DCHECK(block->rpo_number() == j); | 1057 DCHECK(block->rpo_number() == j); |
| 1055 if (j < header->rpo_number() || j >= end->rpo_number()) { | 1058 if (j < header->rpo_number() || j >= end->rpo_number()) { |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1089 void Scheduler::ComputeSpecialRPONumbering() { | 1092 void Scheduler::ComputeSpecialRPONumbering() { |
| 1090 TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n"); | 1093 TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n"); |
| 1091 | 1094 |
| 1092 // Compute the special reverse-post-order for basic blocks. | 1095 // Compute the special reverse-post-order for basic blocks. |
| 1093 special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_); | 1096 special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_); |
| 1094 special_rpo_->ComputeSpecialRPO(); | 1097 special_rpo_->ComputeSpecialRPO(); |
| 1095 } | 1098 } |
| 1096 | 1099 |
| 1097 | 1100 |
| 1098 void Scheduler::PropagateImmediateDominators(BasicBlock* block) { | 1101 void Scheduler::PropagateImmediateDominators(BasicBlock* block) { |
| 1099 for (/*nop*/; block != NULL; block = block->rpo_next()) { | 1102 for (/*nop*/; block != nullptr; block = block->rpo_next()) { |
| 1100 auto pred = block->predecessors().begin(); | 1103 auto pred = block->predecessors().begin(); |
| 1101 auto end = block->predecessors().end(); | 1104 auto end = block->predecessors().end(); |
| 1102 DCHECK(pred != end); // All blocks except start have predecessors. | 1105 DCHECK(pred != end); // All blocks except start have predecessors. |
| 1103 BasicBlock* dominator = *pred; | 1106 BasicBlock* dominator = *pred; |
| 1104 bool deferred = dominator->deferred(); | 1107 bool deferred = dominator->deferred(); |
| 1105 // For multiple predecessors, walk up the dominator tree until a common | 1108 // For multiple predecessors, walk up the dominator tree until a common |
| 1106 // dominator is found. Visitation order guarantees that all predecessors | 1109 // dominator is found. Visitation order guarantees that all predecessors |
| 1107 // except for backwards edges have been visited. | 1110 // except for backwards edges have been visited. |
| 1108 for (++pred; pred != end; ++pred) { | 1111 for (++pred; pred != end; ++pred) { |
| 1109 // Don't examine backwards edges. | 1112 // Don't examine backwards edges. |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1146 scheduler_->schedule_root_nodes_.push_back(node); | 1149 scheduler_->schedule_root_nodes_.push_back(node); |
| 1147 if (!schedule_->IsScheduled(node)) { | 1150 if (!schedule_->IsScheduled(node)) { |
| 1148 // Make sure root nodes are scheduled in their respective blocks. | 1151 // Make sure root nodes are scheduled in their respective blocks. |
| 1149 TRACE("Scheduling fixed position node #%d:%s\n", node->id(), | 1152 TRACE("Scheduling fixed position node #%d:%s\n", node->id(), |
| 1150 node->op()->mnemonic()); | 1153 node->op()->mnemonic()); |
| 1151 IrOpcode::Value opcode = node->opcode(); | 1154 IrOpcode::Value opcode = node->opcode(); |
| 1152 BasicBlock* block = | 1155 BasicBlock* block = |
| 1153 opcode == IrOpcode::kParameter | 1156 opcode == IrOpcode::kParameter |
| 1154 ? schedule_->start() | 1157 ? schedule_->start() |
| 1155 : schedule_->block(NodeProperties::GetControlInput(node)); | 1158 : schedule_->block(NodeProperties::GetControlInput(node)); |
| 1156 DCHECK(block != NULL); | 1159 DCHECK_NOT_NULL(block); |
| 1157 schedule_->AddNode(block, node); | 1160 schedule_->AddNode(block, node); |
| 1158 } | 1161 } |
| 1159 } | 1162 } |
| 1160 } | 1163 } |
| 1161 | 1164 |
| 1162 void PostEdge(Node* from, int index, Node* to) { | 1165 void PostEdge(Node* from, int index, Node* to) { |
| 1163 // If the edge is from an unscheduled node, then tally it in the use count | 1166 // If the edge is from an unscheduled node, then tally it in the use count |
| 1164 // for all of its inputs. The same criterion will be used in ScheduleLate | 1167 // for all of its inputs. The same criterion will be used in ScheduleLate |
| 1165 // for decrementing use counts. | 1168 // for decrementing use counts. |
| 1166 if (!schedule_->IsScheduled(from)) { | 1169 if (!schedule_->IsScheduled(from)) { |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1236 TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n", | 1239 TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n", |
| 1237 node->id(), node->op()->mnemonic(), | 1240 node->id(), node->op()->mnemonic(), |
| 1238 data->minimum_block_->id().ToInt(), | 1241 data->minimum_block_->id().ToInt(), |
| 1239 data->minimum_block_->dominator_depth()); | 1242 data->minimum_block_->dominator_depth()); |
| 1240 } | 1243 } |
| 1241 | 1244 |
| 1242 // No need to propagate unconstrained schedule early positions. | 1245 // No need to propagate unconstrained schedule early positions. |
| 1243 if (data->minimum_block_ == schedule_->start()) return; | 1246 if (data->minimum_block_ == schedule_->start()) return; |
| 1244 | 1247 |
| 1245 // Propagate schedule early position. | 1248 // Propagate schedule early position. |
| 1246 DCHECK(data->minimum_block_ != NULL); | 1249 DCHECK_NOT_NULL(data->minimum_block_); |
| 1247 for (auto use : node->uses()) { | 1250 for (auto use : node->uses()) { |
| 1248 PropagateMinimumPositionToNode(data->minimum_block_, use); | 1251 PropagateMinimumPositionToNode(data->minimum_block_, use); |
| 1249 } | 1252 } |
| 1250 } | 1253 } |
| 1251 | 1254 |
| 1252 // Propagates {block} as another minimum position into the given {node}. This | 1255 // Propagates {block} as another minimum position into the given {node}. This |
| 1253 // has the net effect of computing the minimum dominator block of {node} that | 1256 // has the net effect of computing the minimum dominator block of {node} that |
| 1254 // still post-dominates all inputs to {node} when the queue is processed. | 1257 // still post-dominates all inputs to {node} when the queue is processed. |
| 1255 void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) { | 1258 void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) { |
| 1256 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 1259 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
| (...skipping 257 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1514 } | 1517 } |
| 1515 return header_block->dominator(); | 1518 return header_block->dominator(); |
| 1516 } | 1519 } |
| 1517 return nullptr; | 1520 return nullptr; |
| 1518 } | 1521 } |
| 1519 | 1522 |
| 1520 BasicBlock* GetCommonDominatorOfUses(Node* node) { | 1523 BasicBlock* GetCommonDominatorOfUses(Node* node) { |
| 1521 BasicBlock* block = nullptr; | 1524 BasicBlock* block = nullptr; |
| 1522 for (Edge edge : node->use_edges()) { | 1525 for (Edge edge : node->use_edges()) { |
| 1523 BasicBlock* use_block = GetBlockForUse(edge); | 1526 BasicBlock* use_block = GetBlockForUse(edge); |
| 1524 block = block == NULL ? use_block : use_block == NULL | 1527 block = block == nullptr |
| 1525 ? block | 1528 ? use_block |
| 1526 : BasicBlock::GetCommonDominator( | 1529 : use_block == nullptr |
| 1527 block, use_block); | 1530 ? block |
| 1531 : BasicBlock::GetCommonDominator(block, use_block); |
| 1528 } | 1532 } |
| 1529 return block; | 1533 return block; |
| 1530 } | 1534 } |
| 1531 | 1535 |
| 1532 BasicBlock* FindPredecessorBlock(Node* node) { | 1536 BasicBlock* FindPredecessorBlock(Node* node) { |
| 1533 return scheduler_->control_flow_builder_->FindPredecessorBlock(node); | 1537 return scheduler_->control_flow_builder_->FindPredecessorBlock(node); |
| 1534 } | 1538 } |
| 1535 | 1539 |
| 1536 BasicBlock* GetBlockForUse(Edge edge) { | 1540 BasicBlock* GetBlockForUse(Edge edge) { |
| 1537 Node* use = edge.from(); | 1541 Node* use = edge.from(); |
| (...skipping 19 matching lines...) Expand all Loading... |
| 1557 } else if (IrOpcode::IsMergeOpcode(use->opcode())) { | 1561 } else if (IrOpcode::IsMergeOpcode(use->opcode())) { |
| 1558 // If the use is from a fixed (i.e. non-floating) merge, we use the | 1562 // If the use is from a fixed (i.e. non-floating) merge, we use the |
| 1559 // predecessor block of the current input to the merge. | 1563 // predecessor block of the current input to the merge. |
| 1560 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { | 1564 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { |
| 1561 TRACE(" input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(), | 1565 TRACE(" input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(), |
| 1562 use->op()->mnemonic()); | 1566 use->op()->mnemonic()); |
| 1563 return FindPredecessorBlock(edge.to()); | 1567 return FindPredecessorBlock(edge.to()); |
| 1564 } | 1568 } |
| 1565 } | 1569 } |
| 1566 BasicBlock* result = schedule_->block(use); | 1570 BasicBlock* result = schedule_->block(use); |
| 1567 if (result == NULL) return NULL; | 1571 if (result == nullptr) return nullptr; |
| 1568 TRACE(" must dominate use #%d:%s in id:%d\n", use->id(), | 1572 TRACE(" must dominate use #%d:%s in id:%d\n", use->id(), |
| 1569 use->op()->mnemonic(), result->id().ToInt()); | 1573 use->op()->mnemonic(), result->id().ToInt()); |
| 1570 return result; | 1574 return result; |
| 1571 } | 1575 } |
| 1572 | 1576 |
| 1573 void ScheduleFloatingControl(BasicBlock* block, Node* node) { | 1577 void ScheduleFloatingControl(BasicBlock* block, Node* node) { |
| 1574 scheduler_->FuseFloatingControl(block, node); | 1578 scheduler_->FuseFloatingControl(block, node); |
| 1575 } | 1579 } |
| 1576 | 1580 |
| 1577 void ScheduleRegion(BasicBlock* block, Node* region_end) { | 1581 void ScheduleRegion(BasicBlock* block, Node* region_end) { |
| (...skipping 100 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1678 OFStream os(stdout); | 1682 OFStream os(stdout); |
| 1679 os << "Schedule before control flow fusion:\n" << *schedule_; | 1683 os << "Schedule before control flow fusion:\n" << *schedule_; |
| 1680 } | 1684 } |
| 1681 | 1685 |
| 1682 // Iterate on phase 1: Build control-flow graph. | 1686 // Iterate on phase 1: Build control-flow graph. |
| 1683 control_flow_builder_->Run(block, node); | 1687 control_flow_builder_->Run(block, node); |
| 1684 | 1688 |
| 1685 // Iterate on phase 2: Compute special RPO and dominator tree. | 1689 // Iterate on phase 2: Compute special RPO and dominator tree. |
| 1686 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); | 1690 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); |
| 1687 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. | 1691 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. |
| 1688 for (BasicBlock* b = block->rpo_next(); b != NULL; b = b->rpo_next()) { | 1692 for (BasicBlock* b = block->rpo_next(); b != nullptr; b = b->rpo_next()) { |
| 1689 b->set_dominator_depth(-1); | 1693 b->set_dominator_depth(-1); |
| 1690 b->set_dominator(NULL); | 1694 b->set_dominator(nullptr); |
| 1691 } | 1695 } |
| 1692 PropagateImmediateDominators(block->rpo_next()); | 1696 PropagateImmediateDominators(block->rpo_next()); |
| 1693 | 1697 |
| 1694 // Iterate on phase 4: Schedule nodes early. | 1698 // Iterate on phase 4: Schedule nodes early. |
| 1695 // TODO(mstarzinger): The following loop gathering the propagation roots is a | 1699 // TODO(mstarzinger): The following loop gathering the propagation roots is a |
| 1696 // temporary solution and should be merged into the rest of the scheduler as | 1700 // temporary solution and should be merged into the rest of the scheduler as |
| 1697 // soon as the approach settled for all floating loops. | 1701 // soon as the approach settled for all floating loops. |
| 1698 NodeVector propagation_roots(control_flow_builder_->control_); | 1702 NodeVector propagation_roots(control_flow_builder_->control_); |
| 1699 for (Node* node : control_flow_builder_->control_) { | 1703 for (Node* node : control_flow_builder_->control_) { |
| 1700 for (Node* use : node->uses()) { | 1704 for (Node* use : node->uses()) { |
| (...skipping 29 matching lines...) Expand all Loading... |
| 1730 for (Node* const node : *nodes) { | 1734 for (Node* const node : *nodes) { |
| 1731 schedule_->SetBlockForNode(to, node); | 1735 schedule_->SetBlockForNode(to, node); |
| 1732 scheduled_nodes_[to->id().ToSize()].push_back(node); | 1736 scheduled_nodes_[to->id().ToSize()].push_back(node); |
| 1733 } | 1737 } |
| 1734 nodes->clear(); | 1738 nodes->clear(); |
| 1735 } | 1739 } |
| 1736 | 1740 |
| 1737 } // namespace compiler | 1741 } // namespace compiler |
| 1738 } // namespace internal | 1742 } // namespace internal |
| 1739 } // namespace v8 | 1743 } // namespace v8 |
| OLD | NEW |