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 |