From 4dc4b409250b1286005dc0645e34be3c2b09aa97 Mon Sep 17 00:00:00 2001 From: "sigurds@chromium.org" Date: Tue, 14 Oct 2014 12:08:55 +0000 Subject: [PATCH] Reland "Fix scheduler to correctly schedule nested diamonds". Reland fix: Consume less memory. R=mstarzinger@chromium.org Review URL: https://codereview.chromium.org/636233006 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24597 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/scheduler.cc | 49 ++++++++++++++++++-- src/compiler/verifier.cc | 26 +++++++++++ test/cctest/compiler/test-scheduler.cc | 83 ++++++++++++++++++++++++++++++++++ 3 files changed, 154 insertions(+), 4 deletions(-) diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index 37c99ba..c3fa6b9 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -182,6 +182,7 @@ class CFGBuilder { } } + void BuildBlocks(Node* node) { switch (node->opcode()) { case IrOpcode::kLoop: @@ -395,6 +396,24 @@ class PrepareUsesVisitor : public NullNodeVisitor { 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_); + if (OperatorProperties::IsBasicBlockBegin(to->op()) && + (from->opcode() == IrOpcode::kEffectPhi || + from->opcode() == IrOpcode::kPhi) && + scheduler_->GetData(to)->is_floating_control_ && + !scheduler_->GetData(to)->is_connected_control_) { + for (InputIter i = from->inputs().begin(); i != from->inputs().end(); + ++i) { + if (!NodeProperties::IsControlEdge(i.edge())) { + ++(scheduler_->GetData(*i)->unscheduled_count_); + Trace( + " Use count of #%d:%s (additional dependency of #%d:%s)++ = " + "%d\n", + (*i)->id(), (*i)->op()->mnemonic(), to->id(), + to->op()->mnemonic(), + scheduler_->GetData(*i)->unscheduled_count_); + } + } + } } } @@ -505,6 +524,7 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { if (schedule_->IsScheduled(node)) { return GenericGraphVisit::CONTINUE; } + Scheduler::SchedulerData* data = scheduler_->GetData(node); DCHECK_EQ(Scheduler::kSchedulable, data->placement_); @@ -607,6 +627,29 @@ class ScheduleLateNodeVisitor : public NullNodeVisitor { } } } + + for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { + Node* use = *i; + if (use->opcode() == IrOpcode::kPhi || + use->opcode() == IrOpcode::kEffectPhi) { + Node* control = NodeProperties::GetControlInput(use); + Scheduler::SchedulerData* data = scheduler_->GetData(control); + if (data->is_floating_control_ && !data->is_connected_control_) { + --data->unscheduled_count_; + if (FLAG_trace_turbo_scheduler) { + Trace( + " Use count for #%d:%s (additional dependency of #%d:%s)-- = " + "%d\n", + (*i)->id(), (*i)->op()->mnemonic(), node->id(), + node->op()->mnemonic(), data->unscheduled_count_); + if (data->unscheduled_count_ == 0) { + Trace(" newly eligible #%d:%s\n", (*i)->id(), + (*i)->op()->mnemonic()); + } + } + } + } + } } Scheduler* scheduler_; @@ -665,16 +708,14 @@ bool Scheduler::ConnectFloatingControl() { // TODO(titzer): we place at most one floating control structure per // basic block because scheduling currently can interleave phis from // one subgraph with the merges from another subgraph. - bool one_placed = false; for (size_t j = 0; j < block->NodeCount(); j++) { Node* node = block->NodeAt(block->NodeCount() - 1 - j); SchedulerData* data = GetData(node); - if (data->is_floating_control_ && !data->is_connected_control_ && - !one_placed) { + 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().ToInt()); ConnectFloatingControlSubgraph(block, node); - one_placed = true; + return true; } } } diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc index 3d6bd16..4c28f35 100644 --- a/src/compiler/verifier.cc +++ b/src/compiler/verifier.cc @@ -271,6 +271,19 @@ static bool HasDominatingDef(Schedule* schedule, Node* node, } +static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) { + BasicBlock* dom = schedule->block(dominator); + BasicBlock* sub = schedule->block(dominatee); + while (sub != NULL) { + if (sub == dom) { + return true; + } + sub = sub->dominator(); + } + return false; +} + + static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, Node* node, int use_pos) { for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0; @@ -289,6 +302,19 @@ static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, input->id(), input->op()->mnemonic()); } } + // Ensure that nodes are dominated by their control inputs; + // kEnd is an exception, as unreachable blocks resulting from kMerge + // are not in the RPO. + if (OperatorProperties::GetControlInputCount(node->op()) == 1 && + node->opcode() != IrOpcode::kEnd) { + Node* ctl = NodeProperties::GetControlInput(node); + if (!Dominates(schedule, ctl, node)) { + V8_Fatal(__FILE__, __LINE__, + "Node #%d:%s in B%d is not dominated by control input #%d:%s", + node->id(), node->op()->mnemonic(), block->id(), ctl->id(), + ctl->op()->mnemonic()); + } + } } diff --git a/test/cctest/compiler/test-scheduler.cc b/test/cctest/compiler/test-scheduler.cc index f544db1..f513112 100644 --- a/test/cctest/compiler/test-scheduler.cc +++ b/test/cctest/compiler/test-scheduler.cc @@ -5,6 +5,7 @@ #include "src/v8.h" #include "test/cctest/cctest.h" +#include "src/compiler/access-builder.h" #include "src/compiler/common-operator.h" #include "src/compiler/generic-node-inl.h" #include "src/compiler/generic-node.h" @@ -16,6 +17,7 @@ #include "src/compiler/operator.h" #include "src/compiler/schedule.h" #include "src/compiler/scheduler.h" +#include "src/compiler/simplified-operator.h" #include "src/compiler/verifier.h" using namespace v8::internal; @@ -1717,4 +1719,85 @@ TEST(FloatingDiamond3) { ComputeAndVerifySchedule(33, &graph); } + +TEST(NestedFloatingDiamonds) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + SimplifiedOperatorBuilder simplified(scope.main_zone()); + MachineOperatorBuilder machine; + + Node* start = graph.NewNode(common.Start(2)); + graph.SetStart(start); + + Node* p0 = graph.NewNode(common.Parameter(0), start); + + Node* fv = graph.NewNode(common.Int32Constant(7)); + Node* br = graph.NewNode(common.Branch(), p0, graph.start()); + Node* t = graph.NewNode(common.IfTrue(), br); + Node* f = graph.NewNode(common.IfFalse(), br); + + Node* map = graph.NewNode( + simplified.LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0, p0, + start, f); + Node* br1 = graph.NewNode(common.Branch(), map, graph.start()); + Node* t1 = graph.NewNode(common.IfTrue(), br1); + Node* f1 = graph.NewNode(common.IfFalse(), br1); + Node* m1 = graph.NewNode(common.Merge(2), t1, f1); + Node* ttrue = graph.NewNode(common.Int32Constant(1)); + Node* ffalse = graph.NewNode(common.Int32Constant(0)); + Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), ttrue, ffalse, m1); + + + Node* m = graph.NewNode(common.Merge(2), t, f); + Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), fv, phi1, m); + Node* ephi1 = graph.NewNode(common.EffectPhi(2), start, map, m); + + Node* ret = graph.NewNode(common.Return(), phi, ephi1, start); + Node* end = graph.NewNode(common.End(), ret, start); + + graph.SetEnd(end); + + ComputeAndVerifySchedule(23, &graph); +} + + +TEST(PhisPushedDownToDifferentBranches) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + SimplifiedOperatorBuilder simplified(scope.main_zone()); + MachineOperatorBuilder machine; + + 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* v1 = graph.NewNode(common.Int32Constant(1)); + Node* v2 = graph.NewNode(common.Int32Constant(2)); + Node* v3 = graph.NewNode(common.Int32Constant(3)); + Node* v4 = graph.NewNode(common.Int32Constant(4)); + Node* br = graph.NewNode(common.Branch(), p0, 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(kMachAnyTagged, 2), v1, v2, m); + Node* phi2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), v3, v4, m); + + Node* br2 = graph.NewNode(common.Branch(), p1, graph.start()); + Node* t2 = graph.NewNode(common.IfTrue(), br2); + Node* f2 = graph.NewNode(common.IfFalse(), br2); + Node* m2 = graph.NewNode(common.Merge(2), t2, f2); + Node* phi3 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phi, phi2, m2); + + Node* ret = graph.NewNode(common.Return(), phi3, start, start); + Node* end = graph.NewNode(common.End(), ret, start); + + graph.SetEnd(end); + + ComputeAndVerifySchedule(24, &graph); +} + #endif -- 2.7.4