Revision: 24597
Author: [email protected]
Date: Tue Oct 14 12:08:55 2014 UTC
Log: Reland "Fix scheduler to correctly schedule nested diamonds".
Reland fix: Consume less memory.
[email protected]
Review URL: https://codereview.chromium.org/636233006
https://code.google.com/p/v8/source/detail?r=24597
Modified:
/branches/bleeding_edge/src/compiler/scheduler.cc
/branches/bleeding_edge/src/compiler/verifier.cc
/branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc
=======================================
--- /branches/bleeding_edge/src/compiler/scheduler.cc Mon Oct 13 16:32:12
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.cc Tue Oct 14 12:08:55
2014 UTC
@@ -181,6 +181,7 @@
data->is_connected_control_ = true;
}
}
+
void BuildBlocks(Node* node) {
switch (node->opcode()) {
@@ -395,6 +396,24 @@
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 @@
if (schedule_->IsScheduled(node)) {
return GenericGraphVisit::CONTINUE;
}
+
Scheduler::SchedulerData* data = scheduler_->GetData(node);
DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
@@ -607,6 +627,29 @@
}
}
}
+
+ 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 @@
// 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;
}
}
}
=======================================
--- /branches/bleeding_edge/src/compiler/verifier.cc Mon Oct 13 16:08:29
2014 UTC
+++ /branches/bleeding_edge/src/compiler/verifier.cc Tue Oct 14 12:08:55
2014 UTC
@@ -269,6 +269,19 @@
}
return false;
}
+
+
+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,
@@ -289,6 +302,19 @@
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());
+ }
+ }
}
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Mon Oct
13 16:08:29 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Tue Oct
14 12:08:55 2014 UTC
@@ -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;
@@ -1716,5 +1718,86 @@
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
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
