From 6bbf6c5cb03ec2b8d9a182a47bb650b91b2abc2f Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Tue, 26 Aug 2014 15:25:07 +0000 Subject: [PATCH] Schedule floating control. This CL makes several changes to the scheduling algorithm to handle control flow that is not connected to End. Such control nodes constitute "floating control islands" that must be linearized by the schedule. This is done by considering such nodes to be schedulable, and then editing the control dependencies after a first pass of scheduling. Then a subsequent pass of scheduling will place all nodes correctly into the fully connected graph. R=mstarzinger@chromium.org, rossberg@chromium.org BUG= Review URL: https://codereview.chromium.org/499363002 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23411 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- .gitignore | 2 +- src/compiler/node-properties.h | 1 - src/compiler/pipeline.cc | 14 +- src/compiler/schedule.h | 29 ++- src/compiler/scheduler.cc | 435 +++++++++++++++++++++++---------- src/compiler/scheduler.h | 37 ++- src/compiler/verifier.cc | 12 +- test/cctest/compiler/test-scheduler.cc | 203 +++++++++------ 8 files changed, 486 insertions(+), 247 deletions(-) diff --git a/.gitignore b/.gitignore index e26a13f..9d4325b 100644 --- a/.gitignore +++ b/.gitignore @@ -80,4 +80,4 @@ GRTAGS GSYMS GPATH gtags.files -turbo*.dot \ No newline at end of file +turbo*.dot diff --git a/src/compiler/node-properties.h b/src/compiler/node-properties.h index e3aec3e..6bc9856 100644 --- a/src/compiler/node-properties.h +++ b/src/compiler/node-properties.h @@ -42,7 +42,6 @@ class NodeProperties { static inline Bounds GetBounds(Node* node); static inline void SetBounds(Node* node, Bounds bounds); - private: static inline int FirstValueIndex(Node* node); static inline int FirstContextIndex(Node* node); static inline int FirstFrameStateIndex(Node* node); diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index ca10a80..57e7039 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -87,12 +87,16 @@ void Pipeline::VerifyAndPrintGraph(Graph* graph, const char* phase) { if (FLAG_trace_turbo) { char buffer[256]; Vector filename(buffer, sizeof(buffer)); - SmartArrayPointer functionname = - info_->shared_info()->DebugName()->ToCString(); - if (strlen(functionname.get()) > 0) { - SNPrintF(filename, "turbo-%s-%s.dot", functionname.get(), phase); + if (!info_->shared_info().is_null()) { + SmartArrayPointer functionname = + info_->shared_info()->DebugName()->ToCString(); + if (strlen(functionname.get()) > 0) { + SNPrintF(filename, "turbo-%s-%s.dot", functionname.get(), phase); + } else { + SNPrintF(filename, "turbo-%p-%s.dot", static_cast(info_), phase); + } } else { - SNPrintF(filename, "turbo-%p-%s.dot", static_cast(info_), phase); + SNPrintF(filename, "turbo-none-%s.dot", phase); } std::replace(filename.start(), filename.start() + filename.length(), ' ', '_'); diff --git a/src/compiler/schedule.h b/src/compiler/schedule.h index d54bae6..13a8ba4 100644 --- a/src/compiler/schedule.h +++ b/src/compiler/schedule.h @@ -40,6 +40,7 @@ class BasicBlockData { }; int32_t rpo_number_; // special RPO number of the block. + BasicBlock* dominator_; // Immediate dominator of the block. BasicBlock* loop_header_; // Pointer to dominating loop header basic block, // NULL if none. For loop headers, this points to // enclosing loop header. @@ -55,6 +56,7 @@ class BasicBlockData { explicit BasicBlockData(Zone* zone) : rpo_number_(-1), + dominator_(NULL), loop_header_(NULL), loop_depth_(0), loop_end_(-1), @@ -160,8 +162,7 @@ class Schedule : public GenericGraph { zone_(zone), all_blocks_(zone), nodeid_to_block_(zone), - rpo_order_(zone), - immediate_dominator_(zone) { + rpo_order_(zone) { SetStart(NewBasicBlock()); // entry. SetEnd(NewBasicBlock()); // exit. } @@ -174,10 +175,6 @@ class Schedule : public GenericGraph { return NULL; } - BasicBlock* dominator(BasicBlock* block) { - return immediate_dominator_[block->id()]; - } - bool IsScheduled(Node* node) { int length = static_cast(nodeid_to_block_.size()); if (node->id() >= length) return false; @@ -212,8 +209,8 @@ class Schedule : public GenericGraph { // doesn't actually add the node to the block. inline void PlanNode(BasicBlock* block, Node* node) { if (FLAG_trace_turbo_scheduler) { - PrintF("Planning node %d for future add to block %d\n", node->id(), - block->id()); + PrintF("Planning #%d:%s for future add to B%d\n", node->id(), + node->op()->mnemonic(), block->id()); } DCHECK(this->block(node) == NULL); SetBlockForNode(block, node); @@ -222,7 +219,8 @@ class Schedule : public GenericGraph { // BasicBlock building: add a node to the end of the block. inline void AddNode(BasicBlock* block, Node* node) { if (FLAG_trace_turbo_scheduler) { - PrintF("Adding node %d to block %d\n", node->id(), block->id()); + PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(), + block->id()); } DCHECK(this->block(node) == NULL || this->block(node) == block); block->nodes_.push_back(node); @@ -247,6 +245,7 @@ class Schedule : public GenericGraph { AddSuccessor(block, deopt_block); AddSuccessor(block, cont_block); SetControlInput(block, call); + SetBlockForNode(block, call); } // BasicBlock building: add a branch at the end of {block}. @@ -258,15 +257,22 @@ class Schedule : public GenericGraph { AddSuccessor(block, tblock); AddSuccessor(block, fblock); SetControlInput(block, branch); + if (branch->opcode() == IrOpcode::kBranch) { + // TODO(titzer): require a Branch node here. (sloppy tests). + SetBlockForNode(block, branch); + } } // BasicBlock building: add a return at the end of {block}. void AddReturn(BasicBlock* block, Node* input) { - // TODO(titzer): require a Return node here. DCHECK(block->control_ == BasicBlock::kNone); block->control_ = BasicBlock::kReturn; SetControlInput(block, input); if (block != end()) AddSuccessor(block, end()); + if (input->opcode() == IrOpcode::kReturn) { + // TODO(titzer): require a Return node here. (sloppy tests). + SetBlockForNode(block, input); + } } // BasicBlock building: add a throw at the end of {block}. @@ -315,9 +321,6 @@ class Schedule : public GenericGraph { BasicBlockVector all_blocks_; // All basic blocks in the schedule. BasicBlockVector nodeid_to_block_; // Map from node to containing block. BasicBlockVector rpo_order_; // Reverse-post-order block list. - BasicBlockVector immediate_dominator_; // Maps to a block's immediate - // dominator, indexed by block - // id. }; OStream& operator<<(OStream& os, const Schedule& s); diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index bdca6b4..9f194cb 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -2,6 +2,9 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include +#include + #include "src/compiler/scheduler.h" #include "src/compiler/graph.h" @@ -27,15 +30,63 @@ static inline void Trace(const char* msg, ...) { // Internal class to build a control flow graph (i.e the basic blocks and edges // between them within a Schedule) from the node graph. -// Visits the graph backwards from end, following control and data edges. -class CFGBuilder : public NullNodeVisitor { +// Visits the control edges of the graph backwards from end in order to find +// the connected control subgraph, needed for scheduling. +class CFGBuilder { public: + Scheduler* scheduler_; Schedule* schedule_; + ZoneQueue queue_; + NodeVector control_; + + CFGBuilder(Zone* zone, Scheduler* scheduler) + : scheduler_(scheduler), + schedule_(scheduler->schedule_), + queue_(zone), + control_(zone) {} + + // Run the control flow graph construction algorithm by walking the graph + // backwards from end through control edges, building and connecting the + // basic blocks for control nodes. + void Run() { + Graph* graph = scheduler_->graph_; + FixNode(schedule_->start(), graph->start()); + Queue(graph->end()); + + while (!queue_.empty()) { // Breadth-first backwards traversal. + Node* node = queue_.front(); + queue_.pop(); + int max = NodeProperties::PastControlIndex(node); + for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { + Queue(node->InputAt(i)); + } + } - explicit CFGBuilder(Schedule* schedule) : schedule_(schedule) {} + for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { + ConnectBlocks(*i); // Connect block to its predecessor/successors. + } + + FixNode(schedule_->end(), graph->end()); + } + + void FixNode(BasicBlock* block, Node* node) { + schedule_->AddNode(block, node); + scheduler_->GetData(node)->is_connected_control_ = true; + scheduler_->GetData(node)->placement_ = Scheduler::kFixed; + } - // Create the blocks for the schedule in pre-order. - void PreEdge(Node* from, int index, Node* node) { + void Queue(Node* node) { + // Mark the connected control nodes as they queued. + Scheduler::SchedulerData* data = scheduler_->GetData(node); + if (!data->is_connected_control_) { + BuildBlocks(node); + queue_.push(node); + control_.push_back(node); + data->is_connected_control_ = true; + } + } + + void BuildBlocks(Node* node) { switch (node->opcode()) { case IrOpcode::kLoop: case IrOpcode::kMerge: @@ -55,38 +106,40 @@ class CFGBuilder : public NullNodeVisitor { } } - // Connect the blocks after nodes have been visited in post-order. - GenericGraphVisit::Control Post(Node* node) { + void ConnectBlocks(Node* node) { switch (node->opcode()) { case IrOpcode::kLoop: case IrOpcode::kMerge: ConnectMerge(node); break; case IrOpcode::kBranch: + scheduler_->schedule_root_nodes_.push_back(node); ConnectBranch(node); break; case IrOpcode::kDeoptimize: + scheduler_->schedule_root_nodes_.push_back(node); ConnectDeoptimize(node); case IrOpcode::kCall: if (OperatorProperties::CanLazilyDeoptimize(node->op())) { + scheduler_->schedule_root_nodes_.push_back(node); ConnectCall(node); } break; case IrOpcode::kReturn: + scheduler_->schedule_root_nodes_.push_back(node); ConnectReturn(node); break; default: break; } - return GenericGraphVisit::CONTINUE; } void BuildBlockForNode(Node* node) { if (schedule_->block(node) == NULL) { BasicBlock* block = schedule_->NewBasicBlock(); - Trace("Create block B%d for node %d (%s)\n", block->id(), node->id(), - IrOpcode::Mnemonic(node->opcode())); - schedule_->AddNode(block, node); + Trace("Create block B%d for #%d:%s\n", block->id(), node->id(), + node->op()->mnemonic()); + FixNode(block, node); } } @@ -193,11 +246,11 @@ class CFGBuilder : public NullNodeVisitor { void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { DCHECK_NE(NULL, block); if (succ == NULL) { - Trace("node %d (%s) in block %d -> end\n", node->id(), - IrOpcode::Mnemonic(node->opcode()), block->id()); + Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), + block->id()); } else { - Trace("node %d (%s) in block %d -> block %d\n", node->id(), - IrOpcode::Mnemonic(node->opcode()), block->id(), succ->id()); + Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), + block->id(), succ->id()); } } }; @@ -207,74 +260,80 @@ Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule) : zone_(zone), graph_(graph), schedule_(schedule), - unscheduled_uses_(zone), scheduled_nodes_(zone), schedule_root_nodes_(zone), - schedule_early_rpo_index_(zone) {} + node_data_(graph_->NodeCount(), + SchedulerData{0, 0, false, false, kUnknown}, zone), + has_floating_control_(false) {} Schedule* Scheduler::ComputeSchedule(Graph* graph) { - Zone tmp_zone(graph->zone()->isolate()); - Schedule* schedule = new (graph->zone()) Schedule(graph->zone()); - - Scheduler::ComputeCFG(graph, schedule); + Schedule* schedule; + bool had_floating_control = false; + do { + Zone tmp_zone(graph->zone()->isolate()); + schedule = new (graph->zone()) Schedule(graph->zone()); + Scheduler scheduler(&tmp_zone, graph, schedule); - Scheduler scheduler(&tmp_zone, graph, schedule); + scheduler.BuildCFG(); - scheduler.PrepareAuxiliaryNodeData(); + Scheduler::ComputeSpecialRPO(schedule); + scheduler.GenerateImmediateDominatorTree(); - scheduler.PrepareAuxiliaryBlockData(); + scheduler.PrepareUses(); + scheduler.ScheduleEarly(); + scheduler.ScheduleLate(); - Scheduler::ComputeSpecialRPO(schedule); - scheduler.GenerateImmediateDominatorTree(); - - scheduler.PrepareUses(); - scheduler.ScheduleEarly(); - scheduler.ScheduleLate(); + had_floating_control = scheduler.ConnectFloatingControl(); + } while (had_floating_control); return schedule; } -bool Scheduler::IsBasicBlockBegin(Node* node) { - return OperatorProperties::IsBasicBlockBegin(node->op()); -} - - -bool Scheduler::HasFixedSchedulePosition(Node* node) { - IrOpcode::Value opcode = node->opcode(); - return (IrOpcode::IsControlOpcode(opcode)) || - opcode == IrOpcode::kParameter || opcode == IrOpcode::kEffectPhi || - opcode == IrOpcode::kPhi; -} - - -bool Scheduler::IsScheduleRoot(Node* node) { - IrOpcode::Value opcode = node->opcode(); - return opcode == IrOpcode::kEnd || opcode == IrOpcode::kEffectPhi || - opcode == IrOpcode::kPhi; +Scheduler::Placement Scheduler::GetPlacement(Node* node) { + SchedulerData* data = GetData(node); + if (data->placement_ == kUnknown) { // Compute placement, once, on demand. + switch (node->opcode()) { + case IrOpcode::kParameter: + // Parameters are always fixed to the start node. + data->placement_ = kFixed; + break; + case IrOpcode::kPhi: + case IrOpcode::kEffectPhi: { + // Phis and effect phis are fixed if their control inputs are. + data->placement_ = GetPlacement(NodeProperties::GetControlInput(node)); + break; + } +#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V: + CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE) +#undef DEFINE_FLOATING_CONTROL_CASE + { + // Control nodes that were not control-reachable from end may float. + data->placement_ = kSchedulable; + if (!data->is_connected_control_) { + data->is_floating_control_ = true; + has_floating_control_ = true; + Trace("Floating control found: #%d:%s\n", node->id(), + node->op()->mnemonic()); + } + break; + } + default: + data->placement_ = kSchedulable; + break; + } + } + return data->placement_; } -void Scheduler::ComputeCFG(Graph* graph, Schedule* schedule) { - CFGBuilder cfg_builder(schedule); +void Scheduler::BuildCFG() { Trace("---------------- CREATING CFG ------------------\n"); - schedule->AddNode(schedule->start(), graph->start()); - graph->VisitNodeInputsFromEnd(&cfg_builder); - schedule->AddNode(schedule->end(), graph->end()); -} - - -void Scheduler::PrepareAuxiliaryNodeData() { - unscheduled_uses_.resize(graph_->NodeCount(), 0); - schedule_early_rpo_index_.resize(graph_->NodeCount(), 0); -} - - -void Scheduler::PrepareAuxiliaryBlockData() { - Zone* zone = schedule_->zone(); - scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone)); - schedule_->immediate_dominator_.resize(schedule_->BasicBlockCount(), NULL); + CFGBuilder cfg_builder(zone_, this); + cfg_builder.Run(); + // Initialize per-block data. + scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); } @@ -284,9 +343,9 @@ BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { int b2_rpo = GetRPONumber(b2); DCHECK(b1_rpo != b2_rpo); if (b1_rpo < b2_rpo) { - b2 = schedule_->immediate_dominator_[b2->id()]; + b2 = b2->dominator_; } else { - b1 = schedule_->immediate_dominator_[b1->id()]; + b1 = b1->dominator_; } } return b1; @@ -318,7 +377,7 @@ void Scheduler::GenerateImmediateDominatorTree() { } ++current_pred; } - schedule_->immediate_dominator_[current_rpo->id()] = dominator; + current_rpo->dominator_ = dominator; Trace("Block %d's idom is %d\n", current_rpo->id(), dominator->id()); } } @@ -333,39 +392,39 @@ class ScheduleEarlyNodeVisitor : public NullNodeVisitor { schedule_(scheduler->schedule_) {} GenericGraphVisit::Control Pre(Node* node) { - int id = node->id(); int max_rpo = 0; // Fixed nodes already know their schedule early position. - if (scheduler_->HasFixedSchedulePosition(node)) { + if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { BasicBlock* block = schedule_->block(node); DCHECK(block != NULL); max_rpo = block->rpo_number_; - if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { + if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) { has_changed_rpo_constraints_ = true; } - scheduler_->schedule_early_rpo_index_[id] = max_rpo; - Trace("Node %d pre-scheduled early at rpo limit %d\n", id, max_rpo); + scheduler_->GetData(node)->minimum_rpo_ = max_rpo; + Trace("Preschedule #%d:%s minimum_rpo = %d\n", node->id(), + node->op()->mnemonic(), max_rpo); } return GenericGraphVisit::CONTINUE; } GenericGraphVisit::Control Post(Node* node) { - int id = node->id(); int max_rpo = 0; // Otherwise, the minimum rpo for the node is the max of all of the inputs. - if (!scheduler_->HasFixedSchedulePosition(node)) { + if (scheduler_->GetPlacement(node) != Scheduler::kFixed) { for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { - int control_rpo = scheduler_->schedule_early_rpo_index_[(*i)->id()]; + int control_rpo = scheduler_->GetData(*i)->minimum_rpo_; if (control_rpo > max_rpo) { max_rpo = control_rpo; } } - if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { + if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) { has_changed_rpo_constraints_ = true; } - scheduler_->schedule_early_rpo_index_[id] = max_rpo; - Trace("Node %d post-scheduled early at rpo limit %d\n", id, max_rpo); + scheduler_->GetData(node)->minimum_rpo_ = max_rpo; + Trace("Postschedule #%d:%s minimum_rpo = %d\n", node->id(), + node->op()->mnemonic(), max_rpo); } return GenericGraphVisit::CONTINUE; } @@ -401,24 +460,21 @@ class PrepareUsesVisitor : public NullNodeVisitor { : scheduler_(scheduler), schedule_(scheduler->schedule_) {} GenericGraphVisit::Control Pre(Node* node) { - // Some nodes must be scheduled explicitly to ensure they are in exactly the - // right place; it's a convenient place during the preparation of use counts - // to schedule them. - if (!schedule_->IsScheduled(node) && - scheduler_->HasFixedSchedulePosition(node)) { - Trace("Fixed position node %d is unscheduled, scheduling now\n", - node->id()); - IrOpcode::Value opcode = node->opcode(); - BasicBlock* block = - opcode == IrOpcode::kParameter - ? schedule_->start() - : schedule_->block(NodeProperties::GetControlInput(node)); - DCHECK(block != NULL); - schedule_->AddNode(block, node); - } - - if (scheduler_->IsScheduleRoot(node)) { + if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { + // Fixed nodes are always roots for schedule late. scheduler_->schedule_root_nodes_.push_back(node); + if (!schedule_->IsScheduled(node)) { + // Make sure root nodes are scheduled in their respective blocks. + Trace(" Scheduling fixed position node #%d:%s\n", node->id(), + node->op()->mnemonic()); + IrOpcode::Value opcode = node->opcode(); + BasicBlock* block = + opcode == IrOpcode::kParameter + ? schedule_->start() + : schedule_->block(NodeProperties::GetControlInput(node)); + DCHECK(block != NULL); + schedule_->AddNode(block, node); + } } return GenericGraphVisit::CONTINUE; @@ -429,10 +485,11 @@ class PrepareUsesVisitor : public NullNodeVisitor { // for all of its inputs. The same criterion will be used in ScheduleLate // for decrementing use counts. if (!schedule_->IsScheduled(from)) { - DCHECK(!scheduler_->HasFixedSchedulePosition(from)); - ++scheduler_->unscheduled_uses_[to->id()]; - Trace("Incrementing uses of node %d from %d to %d\n", to->id(), - from->id(), scheduler_->unscheduled_uses_[to->id()]); + DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); + ++(scheduler_->GetData(to)->unscheduled_count_); + Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(), + to->op()->mnemonic(), from->id(), from->op()->mnemonic(), + scheduler_->GetData(to)->unscheduled_count_); } } @@ -461,13 +518,14 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { if (schedule_->IsScheduled(node)) { return GenericGraphVisit::CONTINUE; } - DCHECK(!scheduler_->HasFixedSchedulePosition(node)); + Scheduler::SchedulerData* data = scheduler_->GetData(node); + DCHECK_EQ(Scheduler::kSchedulable, data->placement_); // If all the uses of a node have been scheduled, then the node itself can // be scheduled. - bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0; - Trace("Testing for schedule eligibility for node %d -> %s\n", node->id(), - eligible ? "true" : "false"); + bool eligible = data->unscheduled_count_ == 0; + Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(), + node->op()->mnemonic(), eligible ? "true" : "false"); if (!eligible) return GenericGraphVisit::DEFER; // Determine the dominating block for all of the uses of this node. It is @@ -483,29 +541,30 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { } DCHECK(block != NULL); - int min_rpo = scheduler_->schedule_early_rpo_index_[node->id()]; + int min_rpo = data->minimum_rpo_; Trace( - "Schedule late conservative for node %d is block %d at " - "loop depth %d, min rpo = %d\n", - node->id(), block->id(), block->loop_depth_, min_rpo); + "Schedule late conservative for #%d:%s is B%d at loop depth %d, " + "minimum_rpo = %d\n", + node->id(), node->op()->mnemonic(), block->id(), block->loop_depth_, + min_rpo); // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively - // into enlcosing loop pre-headers until they would preceed their + // into enclosing loop pre-headers until they would preceed their // ScheduleEarly position. BasicBlock* hoist_block = block; while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) { if (hoist_block->loop_depth_ < block->loop_depth_) { block = hoist_block; - Trace("Hoisting node %d to block %d\n", node->id(), block->id()); + Trace(" hoisting #%d:%s to block %d\n", node->id(), + node->op()->mnemonic(), block->id()); } // Try to hoist to the pre-header of the loop header. hoist_block = hoist_block->loop_header(); if (hoist_block != NULL) { - BasicBlock* pre_header = schedule_->dominator(hoist_block); + BasicBlock* pre_header = hoist_block->dominator_; DCHECK(pre_header == NULL || *hoist_block->predecessors().begin() == pre_header); Trace( - "Try hoist to pre-header block %d of loop header block %d," - " depth would be %d\n", + " hoist to pre-header B%d of loop header B%d, depth would be %d\n", pre_header->id(), hoist_block->id(), pre_header->loop_depth_); hoist_block = pre_header; } @@ -520,19 +579,23 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { BasicBlock* GetBlockForUse(Node::Edge edge) { Node* use = edge.from(); IrOpcode::Value opcode = use->opcode(); - // If the use is a phi, forward through the phi to the basic block - // corresponding to the phi's input. if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { + // If the use is from a fixed (i.e. non-floating) phi, use the block + // of the corresponding control input to the merge. int index = edge.index(); - Trace("Use %d is input %d to a phi\n", use->id(), index); - use = NodeProperties::GetControlInput(use, 0); - opcode = use->opcode(); - DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop); - use = NodeProperties::GetControlInput(use, index); + if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { + Trace(" input@%d into a fixed phi #%d:%s\n", index, use->id(), + use->op()->mnemonic()); + Node* merge = NodeProperties::GetControlInput(use, 0); + opcode = merge->opcode(); + DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop); + use = NodeProperties::GetControlInput(merge, index); + } } BasicBlock* result = schedule_->block(use); if (result == NULL) return NULL; - Trace("Must dominate use %d in block %d\n", use->id(), result->id()); + Trace(" must dominate use #%d:%s in B%d\n", use->id(), + use->op()->mnemonic(), result->id()); return result; } @@ -541,16 +604,18 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { scheduler_->scheduled_nodes_[block->id()].push_back(node); // Reduce the use count of the node's inputs to potentially make them - // scheduable. + // schedulable. for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { - DCHECK(scheduler_->unscheduled_uses_[(*i)->id()] > 0); - --scheduler_->unscheduled_uses_[(*i)->id()]; + Scheduler::SchedulerData* data = scheduler_->GetData(*i); + DCHECK(data->unscheduled_count_ > 0); + --data->unscheduled_count_; if (FLAG_trace_turbo_scheduler) { - Trace("Decrementing use count for node %d from node %d (now %d)\n", - (*i)->id(), i.edge().from()->id(), - scheduler_->unscheduled_uses_[(*i)->id()]); - if (scheduler_->unscheduled_uses_[(*i)->id()] == 0) { - Trace("node %d is now eligible for scheduling\n", (*i)->id()); + Trace(" Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(), + (*i)->op()->mnemonic(), i.edge().from()->id(), + i.edge().from()->op()->mnemonic(), data->unscheduled_count_); + if (data->unscheduled_count_ == 0) { + Trace(" newly eligible #%d:%s\n", (*i)->id(), + (*i)->op()->mnemonic()); } } } @@ -563,6 +628,14 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { void Scheduler::ScheduleLate() { Trace("------------------- SCHEDULE LATE -----------------\n"); + if (FLAG_trace_turbo_scheduler) { + Trace("roots: "); + for (NodeVectorIter i = schedule_root_nodes_.begin(); + i != schedule_root_nodes_.end(); ++i) { + Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic()); + } + Trace("\n"); + } // Schedule: Places nodes in dominator block of all their uses. ScheduleLateNodeVisitor schedule_late_visitor(this); @@ -587,6 +660,96 @@ void Scheduler::ScheduleLate() { } +bool Scheduler::ConnectFloatingControl() { + if (!has_floating_control_) return false; + + Trace("Connecting floating control...\n"); + + // Process blocks and instructions backwards to find and connect floating + // control nodes into the control graph according to the block they were + // scheduled into. + int max = static_cast(schedule_->rpo_order()->size()); + for (int i = max - 1; i >= 0; i--) { + BasicBlock* block = schedule_->rpo_order()->at(i); + for (int j = static_cast(block->nodes_.size()) - 1; j >= 0; j--) { + Node* node = block->nodes_[j]; + SchedulerData* data = GetData(node); + if (data->is_floating_control_ && !data->is_connected_control_) { + Trace(" Floating control #%d:%s was scheduled in B%d\n", node->id(), + node->op()->mnemonic(), block->id()); + ConnectFloatingControlSubgraph(block, node); + } + } + } + + return true; +} + + +void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) { + Node* block_start = block->nodes_[0]; + DCHECK(IrOpcode::IsControlOpcode(block_start->opcode())); + // Find the current "control successor" of the node that starts the block + // by searching the control uses for a control input edge from a connected + // control node. + Node* control_succ = NULL; + for (UseIter i = block_start->uses().begin(); i != block_start->uses().end(); + ++i) { + Node::Edge edge = i.edge(); + if (NodeProperties::IsControlEdge(edge) && + GetData(edge.from())->is_connected_control_) { + DCHECK_EQ(NULL, control_succ); + control_succ = edge.from(); + control_succ->ReplaceInput(edge.index(), end); + } + } + DCHECK_NE(NULL, control_succ); + Trace(" Inserting floating control end %d:%s between %d:%s -> %d:%s\n", + end->id(), end->op()->mnemonic(), control_succ->id(), + control_succ->op()->mnemonic(), block_start->id(), + block_start->op()->mnemonic()); + + // Find the "start" node of the control subgraph, which should be the + // unique node that is itself floating control but has a control input that + // is not floating. + Node* start = NULL; + ZoneQueue queue(zone_); + queue.push(end); + GetData(end)->is_connected_control_ = true; + while (!queue.empty()) { + Node* node = queue.front(); + queue.pop(); + Trace(" Search #%d:%s for control subgraph start\n", node->id(), + node->op()->mnemonic()); + int max = NodeProperties::PastControlIndex(node); + for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { + Node* input = node->InputAt(i); + SchedulerData* data = GetData(input); + if (data->is_floating_control_) { + // {input} is floating control. + if (!data->is_connected_control_) { + // First time seeing {input} during this traversal, queue it. + queue.push(input); + data->is_connected_control_ = true; + } + } else { + // Otherwise, {node} is the start node, because it is floating control + // but is connected to {input} that is not floating control. + DCHECK_EQ(NULL, start); // There can be only one. + start = node; + } + } + } + + DCHECK_NE(NULL, start); + start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start); + + Trace(" Connecting floating control start %d:%s to %d:%s\n", start->id(), + start->op()->mnemonic(), block_start->id(), + block_start->op()->mnemonic()); +} + + // Numbering for BasicBlockData.rpo_number_ for this block traversal: static const int kBlockOnStack = -2; static const int kBlockVisited1 = -3; @@ -956,8 +1119,8 @@ BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) { current->loop_end_ = end == NULL ? static_cast(final_order->size()) : end->block->rpo_number_; current_header = current_loop->header; - Trace("Block %d is a loop header, increment loop depth to %d\n", - current->id(), loop_depth); + Trace("B%d is a loop header, increment loop depth to %d\n", current->id(), + loop_depth); } else { while (current_header != NULL && current->rpo_number_ >= current_header->loop_end_) { @@ -969,9 +1132,13 @@ BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) { } } current->loop_depth_ = loop_depth; - Trace("Block %d's loop header is block %d, loop depth %d\n", current->id(), - current->loop_header_ == NULL ? -1 : current->loop_header_->id(), - current->loop_depth_); + if (current->loop_header_ == NULL) { + Trace("B%d is not in a loop (depth == %d)\n", current->id(), + current->loop_depth_); + } else { + Trace("B%d has loop header B%d, (depth == %d)\n", current->id(), + current->loop_header_->id(), current->loop_depth_); + } } #if DEBUG diff --git a/src/compiler/scheduler.h b/src/compiler/scheduler.h index f7c7798..773cbfa 100644 --- a/src/compiler/scheduler.h +++ b/src/compiler/scheduler.h @@ -31,19 +31,37 @@ class Scheduler { static void ComputeCFG(Graph* graph, Schedule* schedule); private: + enum Placement { kUnknown, kSchedulable, kFixed }; + + // Per-node data tracked during scheduling. + struct SchedulerData { + int unscheduled_count_; // Number of unscheduled uses of this node. + int minimum_rpo_; // Minimum legal RPO placement. + bool is_connected_control_; // {true} if control-connected to the end node. + bool is_floating_control_; // {true} if control, but not control-connected + // to the end node. + Placement placement_ : 3; // Whether the node is fixed, schedulable, + // or not yet known. + }; + Zone* zone_; Graph* graph_; Schedule* schedule_; - IntVector unscheduled_uses_; NodeVectorVector scheduled_nodes_; NodeVector schedule_root_nodes_; - IntVector schedule_early_rpo_index_; + ZoneVector node_data_; + bool has_floating_control_; Scheduler(Zone* zone, Graph* graph, Schedule* schedule); - bool IsBasicBlockBegin(Node* node); - bool HasFixedSchedulePosition(Node* node); - bool IsScheduleRoot(Node* node); + SchedulerData* GetData(Node* node) { + DCHECK(node->id() < static_cast(node_data_.size())); + return &node_data_[node->id()]; + } + + void BuildCFG(); + + Placement GetPlacement(Node* node); int GetRPONumber(BasicBlock* block) { DCHECK(block->rpo_number_ >= 0 && @@ -52,12 +70,11 @@ class Scheduler { return block->rpo_number_; } - void PrepareAuxiliaryNodeData(); - void PrepareAuxiliaryBlockData(); - void GenerateImmediateDominatorTree(); BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); + friend class CFGBuilder; + friend class ScheduleEarlyNodeVisitor; void ScheduleEarly(); @@ -66,6 +83,10 @@ class Scheduler { friend class ScheduleLateNodeVisitor; void ScheduleLate(); + + bool ConnectFloatingControl(); + + void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); }; } } diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc index 8b780e9..1f00773 100644 --- a/src/compiler/verifier.cc +++ b/src/compiler/verifier.cc @@ -259,7 +259,7 @@ static bool HasDominatingDef(Schedule* schedule, Node* node, if (block->nodes_[use_pos] == node) return true; use_pos--; } - block = schedule->dominator(block); + block = block->dominator_; if (block == NULL) break; use_pos = static_cast(block->nodes_.size()) - 1; if (node == block->control_input_) return true; @@ -308,7 +308,7 @@ void ScheduleVerifier::Run(Schedule* schedule) { for (size_t b = 0; b < rpo_order->size(); b++) { BasicBlock* block = rpo_order->at(b); CHECK_EQ(static_cast(b), block->rpo_number_); - BasicBlock* dom = schedule->dominator(block); + BasicBlock* dom = block->dominator_; if (b == 0) { // All blocks except start should have a dominator. CHECK_EQ(NULL, dom); @@ -365,7 +365,7 @@ void ScheduleVerifier::Run(Schedule* schedule) { BasicBlock* block = queue.front(); queue.pop(); BitVector* block_doms = dominators[block->id()]; - BasicBlock* idom = schedule->dominator(block); + BasicBlock* idom = block->dominator_; if (idom != NULL && !block_doms->Contains(idom->id())) { V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", block->id(), idom->id()); @@ -375,14 +375,14 @@ void ScheduleVerifier::Run(Schedule* schedule) { BitVector* succ_doms = dominators[succ->id()]; if (succ_doms == NULL) { - // First time visiting the node. S.vec = B U B.vec + // First time visiting the node. S.doms = B U B.doms succ_doms = new (zone) BitVector(count, zone); succ_doms->CopyFrom(*block_doms); succ_doms->Add(block->id()); dominators[succ->id()] = succ_doms; queue.push(succ); } else { - // Nth time visiting the successor. S.vec = S.vec ^ (B U B.vec) + // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) bool had = succ_doms->Contains(block->id()); if (had) succ_doms->Remove(block->id()); if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); @@ -395,7 +395,7 @@ void ScheduleVerifier::Run(Schedule* schedule) { for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); ++b) { BasicBlock* block = *b; - BasicBlock* idom = schedule->dominator(block); + BasicBlock* idom = block->dominator_; if (idom == NULL) continue; BitVector* block_doms = dominators[block->id()]; diff --git a/test/cctest/compiler/test-scheduler.cc b/test/cctest/compiler/test-scheduler.cc index 67190fc..157bdc2 100644 --- a/test/cctest/compiler/test-scheduler.cc +++ b/test/cctest/compiler/test-scheduler.cc @@ -16,10 +16,12 @@ #include "src/compiler/operator.h" #include "src/compiler/schedule.h" #include "src/compiler/scheduler.h" +#include "src/compiler/verifier.h" using namespace v8::internal; using namespace v8::internal::compiler; +// TODO(titzer): pull RPO tests out to their own file. struct TestLoop { int count; BasicBlock** nodes; @@ -65,6 +67,42 @@ static void CheckLoopContains(BasicBlock** blocks, int body_size) { } +static int GetScheduledNodeCount(Schedule* schedule) { + int node_count = 0; + for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); + i != schedule->rpo_order()->end(); ++i) { + BasicBlock* block = *i; + for (BasicBlock::const_iterator j = block->begin(); j != block->end(); + ++j) { + ++node_count; + } + BasicBlock::Control control = block->control_; + if (control != BasicBlock::kNone) { + ++node_count; + } + } + return node_count; +} + + +static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) { + if (FLAG_trace_turbo) { + OFStream os(stdout); + os << AsDOT(*graph); + } + + Schedule* schedule = Scheduler::ComputeSchedule(graph); + + if (FLAG_trace_turbo_scheduler) { + OFStream os(stdout); + os << *schedule << endl; + } + ScheduleVerifier::Run(schedule); + CHECK_EQ(expected, GetScheduledNodeCount(schedule)); + return schedule; +} + + TEST(RPODegenerate1) { HandleAndZoneScope scope; Schedule schedule(scope.main_zone()); @@ -605,36 +643,6 @@ TEST(BuildScheduleOneParameter) { } -static int GetScheduledNodeCount(Schedule* schedule) { - int node_count = 0; - for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); - i != schedule->rpo_order()->end(); ++i) { - BasicBlock* block = *i; - for (BasicBlock::const_iterator j = block->begin(); j != block->end(); - ++j) { - ++node_count; - } - BasicBlock::Control control = block->control_; - if (control != BasicBlock::kNone) { - ++node_count; - } - } - return node_count; -} - - -static void PrintGraph(Graph* graph) { - OFStream os(stdout); - os << AsDOT(*graph); -} - - -static void PrintSchedule(Schedule* schedule) { - OFStream os(stdout); - os << *schedule << endl; -} - - TEST(BuildScheduleIfSplit) { HandleAndZoneScope scope; Graph graph(scope.main_zone()); @@ -658,14 +666,7 @@ TEST(BuildScheduleIfSplit) { Node* merge = graph.NewNode(builder.Merge(2), ret1, ret2); graph.SetEnd(graph.NewNode(builder.End(), merge)); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - - CHECK_EQ(13, GetScheduledNodeCount(schedule)); + ComputeAndVerifySchedule(13, &graph); } @@ -811,13 +812,7 @@ TEST(BuildScheduleIfSplitWithEffects) { graph.SetStart(n0); graph.SetEnd(n23); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - CHECK_EQ(20, GetScheduledNodeCount(schedule)); + ComputeAndVerifySchedule(20, &graph); } @@ -930,13 +925,7 @@ TEST(BuildScheduleSimpleLoop) { graph.SetStart(n0); graph.SetEnd(n20); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - CHECK_EQ(19, GetScheduledNodeCount(schedule)); + ComputeAndVerifySchedule(19, &graph); } @@ -1184,13 +1173,7 @@ TEST(BuildScheduleComplexLoops) { graph.SetStart(n0); graph.SetEnd(n46); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - CHECK_EQ(46, GetScheduledNodeCount(schedule)); + ComputeAndVerifySchedule(46, &graph); } @@ -1520,13 +1503,7 @@ TEST(BuildScheduleBreakAndContinue) { graph.SetStart(n0); graph.SetEnd(n58); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - CHECK_EQ(62, GetScheduledNodeCount(schedule)); + ComputeAndVerifySchedule(62, &graph); } @@ -1651,14 +1628,7 @@ TEST(BuildScheduleSimpleLoopWithCodeMotion) { graph.SetStart(n0); graph.SetEnd(n22); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); - - CHECK_EQ(19, GetScheduledNodeCount(schedule)); - + Schedule* schedule = ComputeAndVerifySchedule(19, &graph); // Make sure the integer-only add gets hoisted to a different block that the // JSAdd. CHECK(schedule->block(n19) != schedule->block(n20)); @@ -1771,11 +1741,7 @@ TEST(BuildScheduleTrivialLazyDeoptCall) { graph.SetStart(start_node); graph.SetEnd(end_node); - PrintGraph(&graph); - - Schedule* schedule = Scheduler::ComputeSchedule(&graph); - - PrintSchedule(schedule); + Schedule* schedule = ComputeAndVerifySchedule(12, &graph); // Tests: // Continuation and deopt have basic blocks. @@ -1806,4 +1772,83 @@ TEST(BuildScheduleTrivialLazyDeoptCall) { CHECK_EQ(state_node, deopt_block->nodes_[4]); } + +static Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, + Node* cond) { + Node* tv = graph->NewNode(common->Int32Constant(6)); + Node* fv = graph->NewNode(common->Int32Constant(7)); + Node* br = graph->NewNode(common->Branch(), cond, graph->start()); + Node* t = graph->NewNode(common->IfTrue(), br); + Node* f = graph->NewNode(common->IfFalse(), br); + Node* m = graph->NewNode(common->Merge(2), t, f); + Node* phi = graph->NewNode(common->Phi(2), tv, fv, m); + return phi; +} + + +TEST(FloatingDiamond1) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(1)); + graph.SetStart(start); + + Node* p0 = graph.NewNode(common.Parameter(0), start); + Node* d1 = CreateDiamond(&graph, &common, p0); + Node* ret = graph.NewNode(common.Return(), d1, start, start); + Node* end = graph.NewNode(common.End(), ret, start); + + graph.SetEnd(end); + + ComputeAndVerifySchedule(13, &graph); +} + + +TEST(FloatingDiamond2) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + MachineOperatorBuilder machine(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(2)); + graph.SetStart(start); + + Node* p0 = graph.NewNode(common.Parameter(0), start); + Node* p1 = graph.NewNode(common.Parameter(1), start); + Node* d1 = CreateDiamond(&graph, &common, p0); + Node* d2 = CreateDiamond(&graph, &common, p1); + Node* add = graph.NewNode(machine.Int32Add(), d1, d2); + Node* ret = graph.NewNode(common.Return(), add, start, start); + Node* end = graph.NewNode(common.End(), ret, start); + + graph.SetEnd(end); + + ComputeAndVerifySchedule(24, &graph); +} + + +TEST(FloatingDiamond3) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + MachineOperatorBuilder machine(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(2)); + graph.SetStart(start); + + Node* p0 = graph.NewNode(common.Parameter(0), start); + Node* p1 = graph.NewNode(common.Parameter(1), start); + Node* d1 = CreateDiamond(&graph, &common, p0); + Node* d2 = CreateDiamond(&graph, &common, p1); + Node* add = graph.NewNode(machine.Int32Add(), d1, d2); + Node* d3 = CreateDiamond(&graph, &common, add); + Node* ret = graph.NewNode(common.Return(), d3, start, start); + Node* end = graph.NewNode(common.End(), ret, start); + + graph.SetEnd(end); + + ComputeAndVerifySchedule(33, &graph); +} + #endif -- 2.7.4