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
3 // found in the LICENSE file.
8 #include "src/compiler/scheduler.h"
10 #include "src/compiler/graph.h"
11 #include "src/compiler/graph-inl.h"
12 #include "src/compiler/node.h"
13 #include "src/compiler/node-properties.h"
14 #include "src/compiler/node-properties-inl.h"
15 #include "src/data-flow.h"
21 static inline void Trace(const char* msg, ...) {
22 if (FLAG_trace_turbo_scheduler) {
24 va_start(arguments, msg);
25 base::OS::VPrint(msg, arguments);
31 // Internal class to build a control flow graph (i.e the basic blocks and edges
32 // between them within a Schedule) from the node graph.
33 // Visits the control edges of the graph backwards from end in order to find
34 // the connected control subgraph, needed for scheduling.
37 Scheduler* scheduler_;
39 ZoneQueue<Node*> queue_;
42 CFGBuilder(Zone* zone, Scheduler* scheduler)
43 : scheduler_(scheduler),
44 schedule_(scheduler->schedule_),
48 // Run the control flow graph construction algorithm by walking the graph
49 // backwards from end through control edges, building and connecting the
50 // basic blocks for control nodes.
52 Graph* graph = scheduler_->graph_;
53 FixNode(schedule_->start(), graph->start());
56 while (!queue_.empty()) { // Breadth-first backwards traversal.
57 Node* node = queue_.front();
59 int max = NodeProperties::PastControlIndex(node);
60 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
61 Queue(node->InputAt(i));
65 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
66 ConnectBlocks(*i); // Connect block to its predecessor/successors.
69 FixNode(schedule_->end(), graph->end());
72 void FixNode(BasicBlock* block, Node* node) {
73 schedule_->AddNode(block, node);
74 scheduler_->GetData(node)->is_connected_control_ = true;
75 scheduler_->GetData(node)->placement_ = Scheduler::kFixed;
78 void Queue(Node* node) {
79 // Mark the connected control nodes as they queued.
80 Scheduler::SchedulerData* data = scheduler_->GetData(node);
81 if (!data->is_connected_control_) {
84 control_.push_back(node);
85 data->is_connected_control_ = true;
89 void BuildBlocks(Node* node) {
90 switch (node->opcode()) {
92 case IrOpcode::kMerge:
93 BuildBlockForNode(node);
95 case IrOpcode::kBranch:
96 BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse);
103 void ConnectBlocks(Node* node) {
104 switch (node->opcode()) {
105 case IrOpcode::kLoop:
106 case IrOpcode::kMerge:
109 case IrOpcode::kBranch:
110 scheduler_->schedule_root_nodes_.push_back(node);
113 case IrOpcode::kReturn:
114 scheduler_->schedule_root_nodes_.push_back(node);
122 void BuildBlockForNode(Node* node) {
123 if (schedule_->block(node) == NULL) {
124 BasicBlock* block = schedule_->NewBasicBlock();
125 Trace("Create block B%d for #%d:%s\n", block->id(), node->id(),
126 node->op()->mnemonic());
127 FixNode(block, node);
131 void BuildBlocksForSuccessors(Node* node, IrOpcode::Value a,
134 CollectSuccessorProjections(node, successors, a, b);
135 BuildBlockForNode(successors[0]);
136 BuildBlockForNode(successors[1]);
139 // Collect the branch-related projections from a node, such as IfTrue,
141 // TODO(titzer): consider moving this to node.h
142 void CollectSuccessorProjections(Node* node, Node** buffer,
143 IrOpcode::Value true_opcode,
144 IrOpcode::Value false_opcode) {
147 for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) {
148 if ((*i)->opcode() == true_opcode) {
149 DCHECK_EQ(NULL, buffer[0]);
152 if ((*i)->opcode() == false_opcode) {
153 DCHECK_EQ(NULL, buffer[1]);
157 DCHECK_NE(NULL, buffer[0]);
158 DCHECK_NE(NULL, buffer[1]);
161 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer,
162 IrOpcode::Value true_opcode,
163 IrOpcode::Value false_opcode) {
165 CollectSuccessorProjections(node, successors, true_opcode, false_opcode);
166 buffer[0] = schedule_->block(successors[0]);
167 buffer[1] = schedule_->block(successors[1]);
170 void ConnectBranch(Node* branch) {
171 Node* branch_block_node = NodeProperties::GetControlInput(branch);
172 BasicBlock* branch_block = schedule_->block(branch_block_node);
173 DCHECK(branch_block != NULL);
175 BasicBlock* successor_blocks[2];
176 CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue,
179 TraceConnect(branch, branch_block, successor_blocks[0]);
180 TraceConnect(branch, branch_block, successor_blocks[1]);
182 schedule_->AddBranch(branch_block, branch, successor_blocks[0],
183 successor_blocks[1]);
186 void ConnectMerge(Node* merge) {
187 BasicBlock* block = schedule_->block(merge);
188 DCHECK(block != NULL);
189 // For all of the merge's control inputs, add a goto at the end to the
190 // merge's basic block.
191 for (InputIter j = merge->inputs().begin(); j != merge->inputs().end();
193 BasicBlock* predecessor_block = schedule_->block(*j);
194 if ((*j)->opcode() != IrOpcode::kReturn) {
195 TraceConnect(merge, predecessor_block, block);
196 schedule_->AddGoto(predecessor_block, block);
201 void ConnectReturn(Node* ret) {
202 Node* return_block_node = NodeProperties::GetControlInput(ret);
203 BasicBlock* return_block = schedule_->block(return_block_node);
204 TraceConnect(ret, return_block, NULL);
205 schedule_->AddReturn(return_block, ret);
208 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
209 DCHECK_NE(NULL, block);
211 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(),
214 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
215 block->id(), succ->id());
221 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
222 SchedulerData def = {0, 0, false, false, kUnknown};
227 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
231 scheduled_nodes_(zone),
232 schedule_root_nodes_(zone),
233 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone),
234 has_floating_control_(false) {}
237 Schedule* Scheduler::ComputeSchedule(Graph* graph) {
239 bool had_floating_control = false;
241 Zone tmp_zone(graph->zone()->isolate());
242 schedule = new (graph->zone()) Schedule(graph->zone());
243 Scheduler scheduler(&tmp_zone, graph, schedule);
245 scheduler.BuildCFG();
247 Scheduler::ComputeSpecialRPO(schedule);
248 scheduler.GenerateImmediateDominatorTree();
250 scheduler.PrepareUses();
251 scheduler.ScheduleEarly();
252 scheduler.ScheduleLate();
254 had_floating_control = scheduler.ConnectFloatingControl();
255 } while (had_floating_control);
261 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
262 SchedulerData* data = GetData(node);
263 if (data->placement_ == kUnknown) { // Compute placement, once, on demand.
264 switch (node->opcode()) {
265 case IrOpcode::kParameter:
266 // Parameters are always fixed to the start node.
267 data->placement_ = kFixed;
270 case IrOpcode::kEffectPhi: {
271 // Phis and effect phis are fixed if their control inputs are.
272 data->placement_ = GetPlacement(NodeProperties::GetControlInput(node));
275 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
276 CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
277 #undef DEFINE_FLOATING_CONTROL_CASE
279 // Control nodes that were not control-reachable from end may float.
280 data->placement_ = kSchedulable;
281 if (!data->is_connected_control_) {
282 data->is_floating_control_ = true;
283 has_floating_control_ = true;
284 Trace("Floating control found: #%d:%s\n", node->id(),
285 node->op()->mnemonic());
290 data->placement_ = kSchedulable;
294 return data->placement_;
298 void Scheduler::BuildCFG() {
299 Trace("---------------- CREATING CFG ------------------\n");
300 CFGBuilder cfg_builder(zone_, this);
302 // Initialize per-block data.
303 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
307 BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
309 int b1_rpo = GetRPONumber(b1);
310 int b2_rpo = GetRPONumber(b2);
311 DCHECK(b1_rpo != b2_rpo);
312 if (b1_rpo < b2_rpo) {
322 void Scheduler::GenerateImmediateDominatorTree() {
323 // Build the dominator graph. TODO(danno): consider using Lengauer & Tarjan's
324 // if this becomes really slow.
325 Trace("------------ IMMEDIATE BLOCK DOMINATORS -----------\n");
326 for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
327 BasicBlock* current_rpo = schedule_->rpo_order_[i];
328 if (current_rpo != schedule_->start()) {
329 BasicBlock::Predecessors::iterator current_pred =
330 current_rpo->predecessors().begin();
331 BasicBlock::Predecessors::iterator end =
332 current_rpo->predecessors().end();
333 DCHECK(current_pred != end);
334 BasicBlock* dominator = *current_pred;
336 // For multiple predecessors, walk up the rpo ordering until a common
337 // dominator is found.
338 int current_rpo_pos = GetRPONumber(current_rpo);
339 while (current_pred != end) {
340 // Don't examine backwards edges
341 BasicBlock* pred = *current_pred;
342 if (GetRPONumber(pred) < current_rpo_pos) {
343 dominator = GetCommonDominator(dominator, *current_pred);
347 current_rpo->dominator_ = dominator;
348 Trace("Block %d's idom is %d\n", current_rpo->id(), dominator->id());
354 class ScheduleEarlyNodeVisitor : public NullNodeVisitor {
356 explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler)
357 : has_changed_rpo_constraints_(true),
358 scheduler_(scheduler),
359 schedule_(scheduler->schedule_) {}
361 GenericGraphVisit::Control Pre(Node* node) {
363 // Fixed nodes already know their schedule early position.
364 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
365 BasicBlock* block = schedule_->block(node);
366 DCHECK(block != NULL);
367 max_rpo = block->rpo_number_;
368 if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) {
369 has_changed_rpo_constraints_ = true;
371 scheduler_->GetData(node)->minimum_rpo_ = max_rpo;
372 Trace("Preschedule #%d:%s minimum_rpo = %d\n", node->id(),
373 node->op()->mnemonic(), max_rpo);
375 return GenericGraphVisit::CONTINUE;
378 GenericGraphVisit::Control Post(Node* node) {
380 // Otherwise, the minimum rpo for the node is the max of all of the inputs.
381 if (scheduler_->GetPlacement(node) != Scheduler::kFixed) {
382 for (InputIter i = node->inputs().begin(); i != node->inputs().end();
384 int control_rpo = scheduler_->GetData(*i)->minimum_rpo_;
385 if (control_rpo > max_rpo) {
386 max_rpo = control_rpo;
389 if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) {
390 has_changed_rpo_constraints_ = true;
392 scheduler_->GetData(node)->minimum_rpo_ = max_rpo;
393 Trace("Postschedule #%d:%s minimum_rpo = %d\n", node->id(),
394 node->op()->mnemonic(), max_rpo);
396 return GenericGraphVisit::CONTINUE;
399 // TODO(mstarzinger): Dirty hack to unblock others, schedule early should be
400 // rewritten to use a pre-order traversal from the start instead.
401 bool has_changed_rpo_constraints_;
404 Scheduler* scheduler_;
409 void Scheduler::ScheduleEarly() {
410 Trace("------------------- SCHEDULE EARLY ----------------\n");
412 int fixpoint_count = 0;
413 ScheduleEarlyNodeVisitor visitor(this);
414 while (visitor.has_changed_rpo_constraints_) {
415 visitor.has_changed_rpo_constraints_ = false;
416 graph_->VisitNodeInputsFromEnd(&visitor);
420 Trace("It took %d iterations to determine fixpoint\n", fixpoint_count);
424 class PrepareUsesVisitor : public NullNodeVisitor {
426 explicit PrepareUsesVisitor(Scheduler* scheduler)
427 : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
429 GenericGraphVisit::Control Pre(Node* node) {
430 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
431 // Fixed nodes are always roots for schedule late.
432 scheduler_->schedule_root_nodes_.push_back(node);
433 if (!schedule_->IsScheduled(node)) {
434 // Make sure root nodes are scheduled in their respective blocks.
435 Trace(" Scheduling fixed position node #%d:%s\n", node->id(),
436 node->op()->mnemonic());
437 IrOpcode::Value opcode = node->opcode();
439 opcode == IrOpcode::kParameter
441 : schedule_->block(NodeProperties::GetControlInput(node));
442 DCHECK(block != NULL);
443 schedule_->AddNode(block, node);
447 return GenericGraphVisit::CONTINUE;
450 void PostEdge(Node* from, int index, Node* to) {
451 // If the edge is from an unscheduled node, then tally it in the use count
452 // for all of its inputs. The same criterion will be used in ScheduleLate
453 // for decrementing use counts.
454 if (!schedule_->IsScheduled(from)) {
455 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
456 ++(scheduler_->GetData(to)->unscheduled_count_);
457 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(),
458 to->op()->mnemonic(), from->id(), from->op()->mnemonic(),
459 scheduler_->GetData(to)->unscheduled_count_);
464 Scheduler* scheduler_;
469 void Scheduler::PrepareUses() {
470 Trace("------------------- PREPARE USES ------------------\n");
471 // Count the uses of every node, it will be used to ensure that all of a
472 // node's uses are scheduled before the node itself.
473 PrepareUsesVisitor prepare_uses(this);
474 graph_->VisitNodeInputsFromEnd(&prepare_uses);
478 class ScheduleLateNodeVisitor : public NullNodeVisitor {
480 explicit ScheduleLateNodeVisitor(Scheduler* scheduler)
481 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
483 GenericGraphVisit::Control Pre(Node* node) {
484 // Don't schedule nodes that are already scheduled.
485 if (schedule_->IsScheduled(node)) {
486 return GenericGraphVisit::CONTINUE;
488 Scheduler::SchedulerData* data = scheduler_->GetData(node);
489 DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
491 // If all the uses of a node have been scheduled, then the node itself can
493 bool eligible = data->unscheduled_count_ == 0;
494 Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(),
495 node->op()->mnemonic(), eligible ? "true" : "false");
496 if (!eligible) return GenericGraphVisit::DEFER;
498 // Determine the dominating block for all of the uses of this node. It is
499 // the latest block that this node can be scheduled in.
500 BasicBlock* block = NULL;
501 for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end();
503 BasicBlock* use_block = GetBlockForUse(i.edge());
504 block = block == NULL ? use_block : use_block == NULL
506 : scheduler_->GetCommonDominator(
509 DCHECK(block != NULL);
511 int min_rpo = data->minimum_rpo_;
513 "Schedule late conservative for #%d:%s is B%d at loop depth %d, "
514 "minimum_rpo = %d\n",
515 node->id(), node->op()->mnemonic(), block->id(), block->loop_depth_,
517 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
518 // into enclosing loop pre-headers until they would preceed their
519 // ScheduleEarly position.
520 BasicBlock* hoist_block = block;
521 while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) {
522 if (hoist_block->loop_depth_ < block->loop_depth_) {
524 Trace(" hoisting #%d:%s to block %d\n", node->id(),
525 node->op()->mnemonic(), block->id());
527 // Try to hoist to the pre-header of the loop header.
528 hoist_block = hoist_block->loop_header();
529 if (hoist_block != NULL) {
530 BasicBlock* pre_header = hoist_block->dominator_;
531 DCHECK(pre_header == NULL ||
532 *hoist_block->predecessors().begin() == pre_header);
534 " hoist to pre-header B%d of loop header B%d, depth would be %d\n",
535 pre_header->id(), hoist_block->id(), pre_header->loop_depth_);
536 hoist_block = pre_header;
540 ScheduleNode(block, node);
542 return GenericGraphVisit::CONTINUE;
546 BasicBlock* GetBlockForUse(Node::Edge edge) {
547 Node* use = edge.from();
548 IrOpcode::Value opcode = use->opcode();
549 if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) {
550 // If the use is from a fixed (i.e. non-floating) phi, use the block
551 // of the corresponding control input to the merge.
552 int index = edge.index();
553 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
554 Trace(" input@%d into a fixed phi #%d:%s\n", index, use->id(),
555 use->op()->mnemonic());
556 Node* merge = NodeProperties::GetControlInput(use, 0);
557 opcode = merge->opcode();
558 DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop);
559 use = NodeProperties::GetControlInput(merge, index);
562 BasicBlock* result = schedule_->block(use);
563 if (result == NULL) return NULL;
564 Trace(" must dominate use #%d:%s in B%d\n", use->id(),
565 use->op()->mnemonic(), result->id());
569 void ScheduleNode(BasicBlock* block, Node* node) {
570 schedule_->PlanNode(block, node);
571 scheduler_->scheduled_nodes_[block->id()].push_back(node);
573 // Reduce the use count of the node's inputs to potentially make them
575 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
576 Scheduler::SchedulerData* data = scheduler_->GetData(*i);
577 DCHECK(data->unscheduled_count_ > 0);
578 --data->unscheduled_count_;
579 if (FLAG_trace_turbo_scheduler) {
580 Trace(" Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(),
581 (*i)->op()->mnemonic(), i.edge().from()->id(),
582 i.edge().from()->op()->mnemonic(), data->unscheduled_count_);
583 if (data->unscheduled_count_ == 0) {
584 Trace(" newly eligible #%d:%s\n", (*i)->id(),
585 (*i)->op()->mnemonic());
591 Scheduler* scheduler_;
596 void Scheduler::ScheduleLate() {
597 Trace("------------------- SCHEDULE LATE -----------------\n");
598 if (FLAG_trace_turbo_scheduler) {
600 for (NodeVectorIter i = schedule_root_nodes_.begin();
601 i != schedule_root_nodes_.end(); ++i) {
602 Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic());
607 // Schedule: Places nodes in dominator block of all their uses.
608 ScheduleLateNodeVisitor schedule_late_visitor(this);
611 Zone zone(zone_->isolate());
612 GenericGraphVisit::Visit<ScheduleLateNodeVisitor,
613 NodeInputIterationTraits<Node> >(
614 graph_, &zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(),
615 &schedule_late_visitor);
618 // Add collected nodes for basic blocks to their blocks in the right order.
620 for (NodeVectorVectorIter i = scheduled_nodes_.begin();
621 i != scheduled_nodes_.end(); ++i) {
622 for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) {
623 schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j);
630 bool Scheduler::ConnectFloatingControl() {
631 if (!has_floating_control_) return false;
633 Trace("Connecting floating control...\n");
635 // Process blocks and instructions backwards to find and connect floating
636 // control nodes into the control graph according to the block they were
638 int max = static_cast<int>(schedule_->rpo_order()->size());
639 for (int i = max - 1; i >= 0; i--) {
640 BasicBlock* block = schedule_->rpo_order()->at(i);
641 // TODO(titzer): we place at most one floating control structure per
642 // basic block because scheduling currently can interleave phis from
643 // one subgraph with the merges from another subgraph.
644 bool one_placed = false;
645 for (int j = static_cast<int>(block->nodes_.size()) - 1; j >= 0; j--) {
646 Node* node = block->nodes_[j];
647 SchedulerData* data = GetData(node);
648 if (data->is_floating_control_ && !data->is_connected_control_ &&
650 Trace(" Floating control #%d:%s was scheduled in B%d\n", node->id(),
651 node->op()->mnemonic(), block->id());
652 ConnectFloatingControlSubgraph(block, node);
662 void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) {
663 Node* block_start = block->nodes_[0];
664 DCHECK(IrOpcode::IsControlOpcode(block_start->opcode()));
665 // Find the current "control successor" of the node that starts the block
666 // by searching the control uses for a control input edge from a connected
668 Node* control_succ = NULL;
669 for (UseIter i = block_start->uses().begin(); i != block_start->uses().end();
671 Node::Edge edge = i.edge();
672 if (NodeProperties::IsControlEdge(edge) &&
673 GetData(edge.from())->is_connected_control_) {
674 DCHECK_EQ(NULL, control_succ);
675 control_succ = edge.from();
676 control_succ->ReplaceInput(edge.index(), end);
679 DCHECK_NE(NULL, control_succ);
680 Trace(" Inserting floating control end %d:%s between %d:%s -> %d:%s\n",
681 end->id(), end->op()->mnemonic(), control_succ->id(),
682 control_succ->op()->mnemonic(), block_start->id(),
683 block_start->op()->mnemonic());
685 // Find the "start" node of the control subgraph, which should be the
686 // unique node that is itself floating control but has a control input that
689 ZoneQueue<Node*> queue(zone_);
691 GetData(end)->is_connected_control_ = true;
692 while (!queue.empty()) {
693 Node* node = queue.front();
695 Trace(" Search #%d:%s for control subgraph start\n", node->id(),
696 node->op()->mnemonic());
697 int max = NodeProperties::PastControlIndex(node);
698 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
699 Node* input = node->InputAt(i);
700 SchedulerData* data = GetData(input);
701 if (data->is_floating_control_) {
702 // {input} is floating control.
703 if (!data->is_connected_control_) {
704 // First time seeing {input} during this traversal, queue it.
706 data->is_connected_control_ = true;
709 // Otherwise, {node} is the start node, because it is floating control
710 // but is connected to {input} that is not floating control.
711 DCHECK_EQ(NULL, start); // There can be only one.
717 DCHECK_NE(NULL, start);
718 start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start);
720 Trace(" Connecting floating control start %d:%s to %d:%s\n", start->id(),
721 start->op()->mnemonic(), block_start->id(),
722 block_start->op()->mnemonic());
726 // Numbering for BasicBlockData.rpo_number_ for this block traversal:
727 static const int kBlockOnStack = -2;
728 static const int kBlockVisited1 = -3;
729 static const int kBlockVisited2 = -4;
730 static const int kBlockUnvisited1 = -1;
731 static const int kBlockUnvisited2 = kBlockVisited1;
733 struct SpecialRPOStackFrame {
742 BlockList* Add(Zone* zone, BasicBlock* b) {
743 BlockList* list = static_cast<BlockList*>(zone->New(sizeof(BlockList)));
749 void Serialize(BasicBlockVector* final_order) {
750 for (BlockList* l = this; l != NULL; l = l->next) {
751 l->block->rpo_number_ = static_cast<int>(final_order->size());
752 final_order->push_back(l->block);
759 ZoneList<BasicBlock*>* outgoing;
765 void AddOutgoing(Zone* zone, BasicBlock* block) {
766 if (outgoing == NULL) outgoing = new (zone) ZoneList<BasicBlock*>(2, zone);
767 outgoing->Add(block, zone);
772 static int Push(SpecialRPOStackFrame* stack, int depth, BasicBlock* child,
774 if (child->rpo_number_ == unvisited) {
775 stack[depth].block = child;
776 stack[depth].index = 0;
777 child->rpo_number_ = kBlockOnStack;
784 // Computes loop membership from the backedges of the control flow graph.
785 static LoopInfo* ComputeLoopInfo(
786 Zone* zone, SpecialRPOStackFrame* queue, int num_loops, int num_blocks,
787 ZoneList<std::pair<BasicBlock*, int> >* backedges) {
788 LoopInfo* loops = zone->NewArray<LoopInfo>(num_loops);
789 memset(loops, 0, num_loops * sizeof(LoopInfo));
791 // Compute loop membership starting from backedges.
792 // O(max(loop_depth) * max(|loop|)
793 for (int i = 0; i < backedges->length(); i++) {
794 BasicBlock* member = backedges->at(i).first;
795 BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
796 int loop_num = header->loop_end_;
797 if (loops[loop_num].header == NULL) {
798 loops[loop_num].header = header;
799 loops[loop_num].members = new (zone) BitVector(num_blocks, zone);
802 int queue_length = 0;
803 if (member != header) {
804 // As long as the header doesn't have a backedge to itself,
805 // Push the member onto the queue and process its predecessors.
806 if (!loops[loop_num].members->Contains(member->id())) {
807 loops[loop_num].members->Add(member->id());
809 queue[queue_length++].block = member;
812 // Propagate loop membership backwards. All predecessors of M up to the
813 // loop header H are members of the loop too. O(|blocks between M and H|).
814 while (queue_length > 0) {
815 BasicBlock* block = queue[--queue_length].block;
816 for (int i = 0; i < block->PredecessorCount(); i++) {
817 BasicBlock* pred = block->PredecessorAt(i);
818 if (pred != header) {
819 if (!loops[loop_num].members->Contains(pred->id())) {
820 loops[loop_num].members->Add(pred->id());
821 queue[queue_length++].block = pred;
832 static void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) {
833 PrintF("-- RPO with %d loops ", num_loops);
836 for (int i = 0; i < num_loops; i++) {
837 if (i > 0) PrintF(" ");
838 PrintF("B%d", loops[i].header->id());
844 for (int i = 0; i < static_cast<int>(order->size()); i++) {
845 BasicBlock* block = (*order)[i];
846 int bid = block->id();
848 for (int i = 0; i < num_loops; i++) {
849 bool membership = loops[i].members->Contains(bid);
850 bool range = loops[i].header->LoopContains(block);
851 PrintF(membership ? " |" : " ");
852 PrintF(range ? "x" : " ");
854 PrintF(" B%d: ", bid);
855 if (block->loop_end_ >= 0) {
856 PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_);
863 static void VerifySpecialRPO(int num_loops, LoopInfo* loops,
864 BasicBlockVector* order) {
865 DCHECK(order->size() > 0);
866 DCHECK((*order)[0]->id() == 0); // entry should be first.
868 for (int i = 0; i < num_loops; i++) {
869 LoopInfo* loop = &loops[i];
870 BasicBlock* header = loop->header;
872 DCHECK(header != NULL);
873 DCHECK(header->rpo_number_ >= 0);
874 DCHECK(header->rpo_number_ < static_cast<int>(order->size()));
875 DCHECK(header->loop_end_ >= 0);
876 DCHECK(header->loop_end_ <= static_cast<int>(order->size()));
877 DCHECK(header->loop_end_ > header->rpo_number_);
879 // Verify the start ... end list relationship.
881 BlockList* l = loop->start;
882 DCHECK(l != NULL && l->block == header);
885 if (l == NULL || l == loop->end) {
886 end_found = (loop->end == l);
889 // The list should be in same order as the final result.
890 DCHECK(l->block->rpo_number_ == links + loop->header->rpo_number_);
893 DCHECK(links < static_cast<int>(2 * order->size())); // cycle?
896 DCHECK(links == (header->loop_end_ - header->rpo_number_));
899 // Check the contiguousness of loops.
901 for (int j = 0; j < static_cast<int>(order->size()); j++) {
902 BasicBlock* block = order->at(j);
903 DCHECK(block->rpo_number_ == j);
904 if (j < header->rpo_number_ || j >= header->loop_end_) {
905 DCHECK(!loop->members->Contains(block->id()));
907 if (block == header) {
908 DCHECK(!loop->members->Contains(block->id()));
910 DCHECK(loop->members->Contains(block->id()));
915 DCHECK(links == count);
921 // Compute the special reverse-post-order block ordering, which is essentially
922 // a RPO of the graph where loop bodies are contiguous. Properties:
923 // 1. If block A is a predecessor of B, then A appears before B in the order,
924 // unless B is a loop header and A is in the loop headed at B
925 // (i.e. A -> B is a backedge).
926 // => If block A dominates block B, then A appears before B in the order.
927 // => If block A is a loop header, A appears before all blocks in the loop
929 // 2. All loops are contiguous in the order (i.e. no intervening blocks that
930 // do not belong to the loop.)
931 // Note a simple RPO traversal satisfies (1) but not (3).
932 BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) {
933 Zone tmp_zone(schedule->zone()->isolate());
934 Zone* zone = &tmp_zone;
935 Trace("------------- COMPUTING SPECIAL RPO ---------------\n");
936 // RPO should not have been computed for this schedule yet.
937 CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number_);
938 CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size()));
940 // Perform an iterative RPO traversal using an explicit stack,
941 // recording backedges that form cycles. O(|B|).
942 ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone);
943 SpecialRPOStackFrame* stack =
944 zone->NewArray<SpecialRPOStackFrame>(schedule->BasicBlockCount());
945 BasicBlock* entry = schedule->start();
946 BlockList* order = NULL;
947 int stack_depth = Push(stack, 0, entry, kBlockUnvisited1);
950 while (stack_depth > 0) {
951 int current = stack_depth - 1;
952 SpecialRPOStackFrame* frame = stack + current;
954 if (frame->index < frame->block->SuccessorCount()) {
955 // Process the next successor.
956 BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
957 if (succ->rpo_number_ == kBlockVisited1) continue;
958 if (succ->rpo_number_ == kBlockOnStack) {
959 // The successor is on the stack, so this is a backedge (cycle).
961 std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone);
962 if (succ->loop_end_ < 0) {
963 // Assign a new loop number to the header if it doesn't have one.
964 succ->loop_end_ = num_loops++;
967 // Push the successor onto the stack.
968 DCHECK(succ->rpo_number_ == kBlockUnvisited1);
969 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1);
972 // Finished with all successors; pop the stack and add the block.
973 order = order->Add(zone, frame->block);
974 frame->block->rpo_number_ = kBlockVisited1;
979 // If no loops were encountered, then the order we computed was correct.
980 LoopInfo* loops = NULL;
981 if (num_loops != 0) {
982 // Otherwise, compute the loop information from the backedges in order
983 // to perform a traversal that groups loop bodies together.
984 loops = ComputeLoopInfo(zone, stack, num_loops, schedule->BasicBlockCount(),
987 // Initialize the "loop stack". Note the entry could be a loop header.
988 LoopInfo* loop = entry->IsLoopHeader() ? &loops[entry->loop_end_] : NULL;
991 // Perform an iterative post-order traversal, visiting loop bodies before
992 // edges that lead out of loops. Visits each block once, but linking loop
993 // sections together is linear in the loop size, so overall is
994 // O(|B| + max(loop_depth) * max(|loop|))
995 stack_depth = Push(stack, 0, entry, kBlockUnvisited2);
996 while (stack_depth > 0) {
997 SpecialRPOStackFrame* frame = stack + (stack_depth - 1);
998 BasicBlock* block = frame->block;
999 BasicBlock* succ = NULL;
1001 if (frame->index < block->SuccessorCount()) {
1002 // Process the next normal successor.
1003 succ = block->SuccessorAt(frame->index++);
1004 } else if (block->IsLoopHeader()) {
1005 // Process additional outgoing edges from the loop header.
1006 if (block->rpo_number_ == kBlockOnStack) {
1007 // Finish the loop body the first time the header is left on the
1009 DCHECK(loop != NULL && loop->header == block);
1010 loop->start = order->Add(zone, block);
1012 block->rpo_number_ = kBlockVisited2;
1013 // Pop the loop stack and continue visiting outgoing edges within the
1014 // the context of the outer loop, if any.
1016 // We leave the loop header on the stack; the rest of this iteration
1017 // and later iterations will go through its outgoing edges list.
1020 // Use the next outgoing edge if there are any.
1021 int outgoing_index = frame->index - block->SuccessorCount();
1022 LoopInfo* info = &loops[block->loop_end_];
1023 DCHECK(loop != info);
1024 if (info->outgoing != NULL &&
1025 outgoing_index < info->outgoing->length()) {
1026 succ = info->outgoing->at(outgoing_index);
1032 // Process the next successor.
1033 if (succ->rpo_number_ == kBlockOnStack) continue;
1034 if (succ->rpo_number_ == kBlockVisited2) continue;
1035 DCHECK(succ->rpo_number_ == kBlockUnvisited2);
1036 if (loop != NULL && !loop->members->Contains(succ->id())) {
1037 // The successor is not in the current loop or any nested loop.
1038 // Add it to the outgoing edges of this loop and visit it later.
1039 loop->AddOutgoing(zone, succ);
1041 // Push the successor onto the stack.
1042 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2);
1043 if (succ->IsLoopHeader()) {
1044 // Push the inner loop onto the loop stack.
1045 DCHECK(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops);
1046 LoopInfo* next = &loops[succ->loop_end_];
1053 // Finished with all successors of the current block.
1054 if (block->IsLoopHeader()) {
1055 // If we are going to pop a loop header, then add its entire body.
1056 LoopInfo* info = &loops[block->loop_end_];
1057 for (BlockList* l = info->start; true; l = l->next) {
1058 if (l->next == info->end) {
1064 order = info->start;
1066 // Pop a single node off the stack and add it to the order.
1067 order = order->Add(zone, block);
1068 block->rpo_number_ = kBlockVisited2;
1075 // Construct the final order from the list.
1076 BasicBlockVector* final_order = &schedule->rpo_order_;
1077 order->Serialize(final_order);
1079 // Compute the correct loop header for every block and set the correct loop
1081 LoopInfo* current_loop = NULL;
1082 BasicBlock* current_header = NULL;
1084 for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end();
1086 BasicBlock* current = *i;
1087 current->loop_header_ = current_header;
1088 if (current->IsLoopHeader()) {
1090 current_loop = &loops[current->loop_end_];
1091 BlockList* end = current_loop->end;
1092 current->loop_end_ = end == NULL ? static_cast<int>(final_order->size())
1093 : end->block->rpo_number_;
1094 current_header = current_loop->header;
1095 Trace("B%d is a loop header, increment loop depth to %d\n", current->id(),
1098 while (current_header != NULL &&
1099 current->rpo_number_ >= current_header->loop_end_) {
1100 DCHECK(current_header->IsLoopHeader());
1101 DCHECK(current_loop != NULL);
1102 current_loop = current_loop->prev;
1103 current_header = current_loop == NULL ? NULL : current_loop->header;
1107 current->loop_depth_ = loop_depth;
1108 if (current->loop_header_ == NULL) {
1109 Trace("B%d is not in a loop (depth == %d)\n", current->id(),
1110 current->loop_depth_);
1112 Trace("B%d has loop header B%d, (depth == %d)\n", current->id(),
1113 current->loop_header_->id(), current->loop_depth_);
1118 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
1119 VerifySpecialRPO(num_loops, loops, final_order);
1125 } // namespace v8::internal::compiler