Switch ScheduleLateNodeVisitor to use explicit queue.

src/compiler/scheduler.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <deque>
 #include <queue>
 
 #include "src/compiler/scheduler.h"
 
 #include "src/compiler/graph.h"
@@ skipping 503 matching lines @@
   // position each node could be placed within a valid schedule.
   ScheduleEarlyNodeVisitor visitor(this);
   graph_->VisitNodeInputsFromEnd(&visitor);
 }
 
 
 // -----------------------------------------------------------------------------
 // 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) {
+  // 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 GenericGraphVisit::CONTINUE;
-    }
+    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;
     for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end();
          ++i) {
       BasicBlock* use_block = GetBlockForUse(i.edge());
       block = block == NULL ? use_block : use_block == NULL
                                               ? block
                                               : scheduler_->GetCommonDominator(
                                                     block, use_block);
@@ skipping 24 matching lines @@
                *hoist_block->predecessors_begin() == pre_header);
         Trace(
             "  hoist to pre-header B%d of loop header B%d, depth would be %d\n",
             pre_header->id().ToInt(), hoist_block->id().ToInt(),
             pre_header->loop_depth());
         hoist_block = pre_header;
       }
     }
 
     ScheduleNode(block, node);
-
-    return GenericGraphVisit::CONTINUE;
   }
 
- private:
   BasicBlock* GetBlockForUse(Node::Edge edge) {
     Node* use = edge.from();
     IrOpcode::Value opcode = use->opcode();
     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();
       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:%s in B%d\n", use->id(),
           use->op()->mnemonic(), result->id().ToInt());
     return result;
   }
 
   void ScheduleNode(BasicBlock* block, Node* node) {
     schedule_->PlanNode(block, node);
     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);
       --data->unscheduled_count_;
       if (FLAG_trace_turbo_scheduler) {
         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);
       }
     }
 
     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());
-            }
+          }
+          if (data->unscheduled_count_ == 0) {
+            Trace("  newly eligible #%d:%s\n", (*i)->id(),
+                  (*i)->op()->mnemonic());
+            queue_.push(*i);
           }
         }
       }
     }
   }
 
   Scheduler* scheduler_;
   Schedule* schedule_;
+  ZoneQueue<Node*> queue_;
 };
 
 
 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);
-
   {
     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.
   int block_num = 0;
   for (NodeVectorVectorIter i = scheduled_nodes_.begin();
        i != scheduled_nodes_.end(); ++i) {
     for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) {
       schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j);
     }
     block_num++;
@@ skipping 500 matching lines @@
 #if DEBUG
   if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
   VerifySpecialRPO(num_loops, loops, final_order);
 #endif
   return final_order;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8