Revision: 24803
Author: [email protected]
Date: Wed Oct 22 11:31:12 2014 UTC
Log: Switch ScheduleLateNodeVisitor to use explicit queue.
[email protected]
Review URL: https://codereview.chromium.org/672583002
https://code.google.com/p/v8/source/detail?r=24803
Modified:
/branches/bleeding_edge/src/compiler/scheduler.cc
=======================================
--- /branches/bleeding_edge/src/compiler/scheduler.cc Wed Oct 22 11:24:55
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.cc Wed Oct 22 11:31:12
2014 UTC
@@ -535,27 +535,42 @@
// Phase 4: Schedule nodes late.
-class ScheduleLateNodeVisitor : public NullNodeVisitor {
+class ScheduleLateNodeVisitor {
public:
- explicit ScheduleLateNodeVisitor(Scheduler* scheduler)
- : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
+ ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
+ : scheduler_(scheduler), schedule_(scheduler_->schedule_),
queue_(zone) {}
- GenericGraphVisit::Control Pre(Node* node) {
- // Don't schedule nodes that are already scheduled.
- if (schedule_->IsScheduled(node)) {
- return GenericGraphVisit::CONTINUE;
+ // Run the schedule late algorithm on a set of fixed root nodes.
+ void Run(NodeVector* roots) {
+ for (NodeVectorIter i = roots->begin(); i != roots->end(); ++i) {
+ ProcessQueue(*i);
}
+ }
+
+ private:
+ void ProcessQueue(Node* root) {
+ for (InputIter i = root->inputs().begin(); i != root->inputs().end();
++i) {
+ if (scheduler_->GetData(*i)->unscheduled_count_ != 0) continue;
+ queue_.push(*i);
+ while (!queue_.empty()) {
+ VisitNode(queue_.front());
+ queue_.pop();
+ }
+ }
+ }
+
+ // Visits one node from the queue of schedulable nodes and determines its
+ // schedule late position. Also hoists nodes out of loops to find a more
+ // optimal scheduling position.
+ void VisitNode(Node* node) {
+ DCHECK(scheduler_->GetData(node)->unscheduled_count_ == 0);
+
+ // Don't schedule nodes that are already scheduled.
+ if (schedule_->IsScheduled(node)) return;
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 = 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
// the latest block that this node can be scheduled in.
BasicBlock* block = NULL;
@@ -600,11 +615,8 @@
}
ScheduleNode(block, node);
-
- return GenericGraphVisit::CONTINUE;
}
- private:
BasicBlock* GetBlockForUse(Node::Edge edge) {
Node* use = edge.from();
IrOpcode::Value opcode = use->opcode();
@@ -633,7 +645,8 @@
scheduler_->scheduled_nodes_[block->id().ToSize()].push_back(node);
// Reduce the use count of the node's inputs to potentially make them
- // schedulable.
+ // schedulable. If all the uses of a node have been scheduled, then
the node
+ // itself can be scheduled.
for (InputIter i = node->inputs().begin(); i != node->inputs().end();
++i) {
Scheduler::SchedulerData* data = scheduler_->GetData(*i);
DCHECK(data->unscheduled_count_ > 0);
@@ -642,10 +655,10 @@
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());
- }
+ }
+ if (data->unscheduled_count_ == 0) {
+ Trace(" newly eligible #%d:%s\n", (*i)->id(),
(*i)->op()->mnemonic());
+ queue_.push(*i);
}
}
@@ -663,10 +676,11 @@
"%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());
- }
+ }
+ if (data->unscheduled_count_ == 0) {
+ Trace(" newly eligible #%d:%s\n", (*i)->id(),
+ (*i)->op()->mnemonic());
+ queue_.push(*i);
}
}
}
@@ -675,6 +689,7 @@
Scheduler* scheduler_;
Schedule* schedule_;
+ ZoneQueue<Node*> queue_;
};
@@ -690,15 +705,10 @@
}
// Schedule: Places nodes in dominator block of all their uses.
- ScheduleLateNodeVisitor schedule_late_visitor(this);
-
{
ZonePool::Scope zone_scope(zone_pool_);
- Zone* zone = zone_scope.zone();
- GenericGraphVisit::Visit<ScheduleLateNodeVisitor,
- NodeInputIterationTraits<Node> >(
- graph_, zone, schedule_root_nodes_.begin(),
schedule_root_nodes_.end(),
- &schedule_late_visitor);
+ ScheduleLateNodeVisitor schedule_late_visitor(zone_scope.zone(), this);
+ schedule_late_visitor.Run(&schedule_root_nodes_);
}
// Add collected nodes for basic blocks to their blocks in the right
order.
--
--
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.
