Fix scheduler to correctly schedule nested diamonds.

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 68 matching lines @@
     // Mark the connected control nodes as they queued.
     Scheduler::SchedulerData* data = scheduler_->GetData(node);
     if (!data->is_connected_control_) {
       BuildBlocks(node);
       queue_.push(node);
       control_.push_back(node);
       data->is_connected_control_ = true;
     }
   }
 
+
   void BuildBlocks(Node* node) {
     switch (node->opcode()) {
       case IrOpcode::kLoop:
       case IrOpcode::kMerge:
         BuildBlockForNode(node);
         break;
       case IrOpcode::kBranch:
         BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse);
         break;
       default:
@@ skipping 112 matching lines @@
       Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(),
             block->id());
     } else {
       Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
             block->id(), succ->id());
     }
   }
 };
 
 
-Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
-  SchedulerData def = {0, 0, false, false, kUnknown};
+Scheduler::SchedulerData Scheduler::DefaultSchedulerData(Zone* zone) {
+  SchedulerData def = {0, 0, false, false, kUnknown, NodeVector(zone)};
   return def;
 }
 
 
 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
     : zone_(zone),
       graph_(graph),
       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) {}
 
 
 Schedule* Scheduler::ComputeSchedule(Graph* graph) {
   Schedule* schedule;
   bool had_floating_control = false;
   do {
     Zone tmp_zone(graph->zone()->isolate());
     schedule = new (graph->zone())
         Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
@@ skipping 207 matching lines @@
   void PostEdge(Node* from, int index, Node* to) {
     // If the edge is from an unscheduled node, then tally it in the use count
     // for all of its inputs. The same criterion will be used in ScheduleLate
     // for decrementing use counts.
     if (!schedule_->IsScheduled(from)) {
       DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
       ++(scheduler_->GetData(to)->unscheduled_count_);
       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()) &&

[titzer, 2014/10/07 07:48:26]

I think this should only be EffectPhi and Phi, and floating_control and
connected_control should be mutually exclusive.

[sigurds, 2014/10/13 13:08:18]

I'm doing the IsBasicBlockBegin check to make sure to add the additional
dependencies only once per (Effect)Phi.

+          (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_);
+          }
+        }
+      }
     }
   }
 
  private:
   Scheduler* scheduler_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::PrepareUses() {
   Trace("------------------- PREPARE USES ------------------\n");
   // Count the uses of every node, it will be used to ensure that all of a
   // node's uses are scheduled before the node itself.
   PrepareUsesVisitor prepare_uses(this);
   graph_->VisitNodeInputsFromEnd(&prepare_uses);
 }
 
 
 class ScheduleLateNodeVisitor : public NullNodeVisitor {
  public:
   explicit ScheduleLateNodeVisitor(Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
     // Don't schedule nodes that are already scheduled.
     if (schedule_->IsScheduled(node)) {
       return GenericGraphVisit::CONTINUE;
     }
+
     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;
 
@@ skipping 81 matching lines @@
       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());
         }
       }
     }
+
+    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_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::ScheduleLate() {
   Trace("------------------- SCHEDULE LATE -----------------\n");
   if (FLAG_trace_turbo_scheduler) {
@@ skipping 35 matching lines @@
 
   // Process blocks and instructions backwards to find and connect floating
   // control nodes into the control graph according to the block they were
   // scheduled into.
   int max = static_cast<int>(schedule_->rpo_order()->size());
   for (int i = max - 1; i >= 0; i--) {
     BasicBlock* block = schedule_->rpo_order()->at(i);
     // 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 (int j = static_cast<int>(block->nodes_.size()) - 1; j >= 0; j--) {
       Node* node = block->nodes_[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());
         ConnectFloatingControlSubgraph(block, node);
-        one_placed = true;
+        return true;
       }
     }
   }
 
   return true;
 }
 
 
 void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) {
   Node* block_start = block->nodes_[0];
@@ skipping 452 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 v8::internal::compiler