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 627 matching lines @@
   // 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) {
-        Trace("  Floating control #%d:%s was scheduled in B%d\n", node->id(),
-              node->op()->mnemonic(), block->id());
-        ConnectFloatingControlSubgraph(block, node);
-        one_placed = true;
+      if (!one_placed && (NodeProperties::IsControl(node) ||
+                          OperatorProperties::HasControlInput(node->op()))) {
+        Node* ctl = NodeProperties::IsControl(node)
+                        ? node
+                        : NodeProperties::GetControlInput(node);
+        SchedulerData* data = GetData(ctl);
+        if (data->is_floating_control_ && !data->is_connected_control_) {
+          Trace("  Floating control #%d:%s was scheduled in B%d\n", ctl->id(),
+                ctl->op()->mnemonic(), block->id());
+          ConnectFloatingControlSubgraph(block, ctl);
+          one_placed = true;

[titzer, 2014/09/25 12:19:24]

So this basically matches the first node that is either a floating control node
or has a floating control node as a control dependency.

This is not quite correct because if there is more than one such non-control
node that depends on a floating control node, then they could in fact be pushed
down to different blocks. Placing the merge in one or the other of the blocks
wouldn't dominate the remaining. E.g. suppose there are two phis hanging off the
merge of a floating diamond. Then the two phis can be scheduled independently of
the merge. The merge definitely dominates the phis. That's where it needs to be
placed.

Now that I look at this loop again, you can just return from this method after
the first one is placed (no need to continue processing the block). That will
simplify this condition a bit.

Actually, I am not even sure if we need to return anything from this method now.

[sigurds, 2014/09/26 11:35:24]

This is a valid point, I added a unit test to expose the faulty behaviour in my
patch:

cctest/test-scheduler/PhisPushedDownToDifferentBranches

+        }
       }
     }
   }
 
   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