Revision: 24561
Author: [email protected]
Date: Mon Oct 13 13:07:49 2014 UTC
Log: Fix scheduler to correctly schedule nested diamonds.
The scheduler rewires control based on the last *control*
node that appears in the schedule of a block. This is not
sufficient to account for dependencies.
This patch adds additional dependencies to floating control
nodes. Given a floating control node A, every non-control
dependency of every node B that depends on A is introduces
as an additional dependency of A.
This allows the scheduler to correctly schedule two
diamonds A, B, if their only correct schedule is to
schedule B into the ifTrue successor in A.
TEST=cctest/test-scheduler/NestedFloatingDiamonds
[email protected], [email protected]
Review URL: https://codereview.chromium.org/602083003
https://code.google.com/p/v8/source/detail?r=24561
Modified:
/branches/bleeding_edge/src/compiler/scheduler.cc
/branches/bleeding_edge/src/compiler/scheduler.h
/branches/bleeding_edge/src/compiler/verifier.cc
/branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc
=======================================
--- /branches/bleeding_edge/src/compiler/scheduler.cc Fri Oct 10 11:57:55
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.cc Mon Oct 13 13:07:49
2014 UTC
@@ -34,7 +34,7 @@
schedule_(schedule),
scheduled_nodes_(zone),
schedule_root_nodes_(zone),
- node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone),
+ node_data_(graph_->NodeCount(), DefaultSchedulerData(zone), zone),
has_floating_control_(false) {}
@@ -62,8 +62,8 @@
}
-Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
- SchedulerData def = {0, -1, false, false, kUnknown};
+Scheduler::SchedulerData Scheduler::DefaultSchedulerData(Zone* zone) {
+ SchedulerData def = {0, -1, false, false, kUnknown, NodeVector(zone)};
return def;
}
@@ -181,6 +181,7 @@
data->is_connected_control_ = true;
}
}
+
void BuildBlocks(Node* node) {
switch (node->opcode()) {
@@ -395,6 +396,26 @@
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::SchedulerData* data = scheduler_->GetData(to);
+ data->additional_dependencies.push_back(*i);
+ ++(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_);
+ }
+ }
+ }
}
}
@@ -509,6 +530,7 @@
if (schedule_->IsScheduled(node)) {
return GenericGraphVisit::CONTINUE;
}
+
Scheduler::SchedulerData* data = scheduler_->GetData(node);
DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
@@ -611,6 +633,24 @@
}
}
}
+
+ Scheduler::SchedulerData* data = scheduler_->GetData(node);
+ for (NodeVectorIter i = data->additional_dependencies.begin();
+ i != data->additional_dependencies.end(); ++i) {
+ Scheduler::SchedulerData* data = scheduler_->GetData(*i);
+ DCHECK(data->unscheduled_count_ > 0);
+ --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_;
@@ -669,16 +709,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/scheduler.h Fri Oct 10 11:57:55
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.h Mon Oct 13 13:07:49
2014 UTC
@@ -36,8 +36,9 @@
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,
+ Placement placement_; // Whether the node is fixed, schedulable,
// or not yet known.
+ NodeVector additional_dependencies;
};
Zone* zone_;
@@ -50,7 +51,7 @@
Scheduler(Zone* zone, Graph* graph, Schedule* schedule);
- SchedulerData DefaultSchedulerData();
+ SchedulerData DefaultSchedulerData(Zone* zone);
SchedulerData* GetData(Node* node) {
DCHECK(node->id() < static_cast<int>(node_data_.size()));
=======================================
--- /branches/bleeding_edge/src/compiler/verifier.cc Tue Sep 30 09:34:16
2014 UTC
+++ /branches/bleeding_edge/src/compiler/verifier.cc Mon Oct 13 13:07:49
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 Tue Oct
7 13:30:28 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Mon Oct
13 13:07:49 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.
