Switch scheduler to iterative floating control placement.

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 17 matching lines @@
 }
 
 
 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
     : zone_(zone),
       graph_(graph),
       schedule_(schedule),
       scheduled_nodes_(zone),
       schedule_root_nodes_(zone),
       schedule_queue_(zone),
-      node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone),
-      has_floating_control_(false) {}
+      node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone) {}
 
 
 Schedule* Scheduler::ComputeSchedule(ZonePool* zone_pool, Graph* graph) {
-  Schedule* schedule;
-  bool had_floating_control = false;
-  do {
-    ZonePool::Scope zone_scope(zone_pool);
-    schedule = new (graph->zone())
-        Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
-    Scheduler scheduler(zone_scope.zone(), graph, schedule);
+  ZonePool::Scope zone_scope(zone_pool);
+  Schedule* schedule = new (graph->zone())
+      Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
+  Scheduler scheduler(zone_scope.zone(), graph, schedule);
 
-    scheduler.BuildCFG();
-    scheduler.ComputeSpecialRPONumbering();
-    scheduler.GenerateImmediateDominatorTree();
+  scheduler.BuildCFG();
+  scheduler.ComputeSpecialRPONumbering();
+  scheduler.GenerateImmediateDominatorTree();
 
-    scheduler.PrepareUses();
-    scheduler.ScheduleEarly();
-    scheduler.ScheduleLate();
-
-    had_floating_control = scheduler.ConnectFloatingControl();
-  } while (had_floating_control);
+  scheduler.PrepareUses();
+  scheduler.ScheduleEarly();
+  scheduler.ScheduleLate();
 
   return schedule;
 }
 
 
 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
   SchedulerData def = {schedule_->start(), 0, false, false, kUnknown};
   return def;
 }
 
@@ skipping 14 matching lines @@
         break;
       case IrOpcode::kPhi:
       case IrOpcode::kEffectPhi: {
         // Phis and effect phis are fixed if their control inputs are, whereas
         // otherwise they are coupled to a floating control node.
         Placement p = GetPlacement(NodeProperties::GetControlInput(node));
         data->placement_ = (p == kFixed ? kFixed : kCoupled);
         break;
       }
 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
-        CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
+      CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
 #undef DEFINE_FLOATING_CONTROL_CASE
-        {
-          // Control nodes that were not control-reachable from end may float.
-          data->placement_ = kSchedulable;
-          if (!data->is_connected_control_) {
-            data->is_floating_control_ = true;
-            has_floating_control_ = true;
-            Trace("Floating control found: #%d:%s\n", node->id(),
-                  node->op()->mnemonic());
-          }
-          break;
+      {
+        // Control nodes that were not control-reachable from end may float.
+        data->placement_ = kSchedulable;
+        if (!data->is_connected_control_) {
+          data->is_floating_control_ = true;
+          Trace("Floating control found: #%d:%s\n", node->id(),
+                node->op()->mnemonic());
         }
+        break;
+      }
       default:
         data->placement_ = kSchedulable;
         break;
     }
   }
   return data->placement_;
 }
 
 
+void Scheduler::UpdatePlacement(Node* node, Placement placement) {
+  SchedulerData* data = GetData(node);
+  if (data->placement_ != kUnknown) {  // Trap on mutation, not initialization.
+    switch (node->opcode()) {
+      case IrOpcode::kParameter:
+        // Parameters are fixed once and for all.
+        UNREACHABLE();
+        break;
+      case IrOpcode::kPhi:
+      case IrOpcode::kEffectPhi: {
+        // Phis and effect phis are coupled to their respective blocks.
+        DCHECK_EQ(Scheduler::kCoupled, data->placement_);
+        DCHECK_EQ(Scheduler::kFixed, placement);
+        Node* control = NodeProperties::GetControlInput(node);
+        BasicBlock* block = schedule_->block(control);
+        schedule_->AddNode(block, node);
+        // TODO(mstarzinger): Cheap hack to make sure unscheduled use count of
+        // control does not drop below zero. This might cause the control to be
+        // queued for scheduling more than once, which makes this ugly!
+        ++(GetData(control)->unscheduled_count_);
+        break;
+      }
+#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
+      CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
+#undef DEFINE_FLOATING_CONTROL_CASE
+      {
+        // Control nodes force coupled uses to be placed.
+        Node::Uses uses = node->uses();
+        for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) {
+          if (GetPlacement(*i) == Scheduler::kCoupled) {
+            DCHECK_EQ(node, NodeProperties::GetControlInput(*i));
+            UpdatePlacement(*i, placement);
+          }
+        }
+        break;
+      }
+      default:
+        DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
+        DCHECK_EQ(Scheduler::kScheduled, placement);
+        break;
+    }
+    // Reduce the use count of the node's inputs to potentially make them
+    // 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) {
+      // TODO(mstarzinger): Another cheap hack for use counts.
+      if (GetData(*i)->placement_ == kFixed) continue;
+      DecrementUnscheduledUseCount(*i, i.edge().from());
+    }
+  }
+  data->placement_ = placement;
+}
+
+
 void Scheduler::IncrementUnscheduledUseCount(Node* node, Node* from) {
   if (GetPlacement(node) == kCoupled) {
     // Use count for coupled nodes is summed up on their control.
     Node* control = NodeProperties::GetControlInput(node);
     return IncrementUnscheduledUseCount(control, from);
   }
   ++(GetData(node)->unscheduled_count_);
   if (FLAG_trace_turbo_scheduler) {
     Trace("  Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
           node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
@@ skipping 43 matching lines @@
   }
   return b1;
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 1: Build control-flow graph.
 
 
 // Internal class to build a control flow graph (i.e the basic blocks and edges
-// between them within a Schedule) from the node graph.
-// Visits the control edges of the graph backwards from end in order to find
-// the connected control subgraph, needed for scheduling.
+// between them within a Schedule) from the node graph. Visits control edges of
+// the graph backwards from an end node in order to find the connected control
+// subgraph, needed for scheduling.
 class CFGBuilder {
  public:
-  Scheduler* scheduler_;
-  Schedule* schedule_;
-  ZoneQueue<Node*> queue_;
-  NodeVector control_;
-
   CFGBuilder(Zone* zone, Scheduler* scheduler)
       : scheduler_(scheduler),
         schedule_(scheduler->schedule_),
         queue_(zone),
-        control_(zone) {}
+        control_(zone),
+        component_head_(NULL),
+        component_start_(NULL),
+        component_end_(NULL) {}
 
   // Run the control flow graph construction algorithm by walking the graph
   // backwards from end through control edges, building and connecting the
   // basic blocks for control nodes.
   void Run() {
     Graph* graph = scheduler_->graph_;
     FixNode(schedule_->start(), graph->start());
     Queue(graph->end());
 
     while (!queue_.empty()) {  // Breadth-first backwards traversal.
       Node* node = queue_.front();
       queue_.pop();
       int max = NodeProperties::PastControlIndex(node);
       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
         Queue(node->InputAt(i));
       }
     }
 
     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
     }
 
     FixNode(schedule_->end(), graph->end());
   }
 
+  // Run the control flow graph construction for a minimal control-connected
+  // component ending in {node} and merge that component into an existing
+  // control flow graph at the bottom of {block}.
+  void Run(BasicBlock* block, Node* node) {
+    Queue(node);
+
+    component_start_ = block;
+    component_end_ = schedule_->block(node);
+    while (!queue_.empty()) {  // Breadth-first backwards traversal.
+      Node* node = queue_.front();
+      queue_.pop();
+      bool is_dom = true;
+      int max = NodeProperties::PastControlIndex(node);
+      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
+        is_dom = is_dom &&
+            !scheduler_->GetData(node->InputAt(i))->is_floating_control_;
+        Queue(node->InputAt(i));
+      }
+      // TODO(mstarzinger): This is a hacky way to find component dominator.
+      if (is_dom) component_head_ = node;
+    }
+    DCHECK_NOT_NULL(component_head_);
+
+    for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
+      scheduler_->GetData(*i)->is_floating_control_ = false;
+      ConnectBlocks(*i);  // Connect block to its predecessor/successors.
+    }
+  }
+
+ private:
   void FixNode(BasicBlock* block, Node* node) {
     schedule_->AddNode(block, node);
     scheduler_->GetData(node)->is_connected_control_ = true;
-    scheduler_->GetData(node)->placement_ = Scheduler::kFixed;
+    scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   }
 
   void Queue(Node* node) {
     // 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;
@@ skipping 16 matching lines @@
     }
   }
 
   void ConnectBlocks(Node* node) {
     switch (node->opcode()) {
       case IrOpcode::kLoop:
       case IrOpcode::kMerge:
         ConnectMerge(node);
         break;
       case IrOpcode::kBranch:
-        scheduler_->schedule_root_nodes_.push_back(node);
+        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
         ConnectBranch(node);
         break;
       case IrOpcode::kReturn:
-        scheduler_->schedule_root_nodes_.push_back(node);
+        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
         ConnectReturn(node);
         break;
       default:
         break;
     }
   }
 
   void BuildBlockForNode(Node* node) {
     if (schedule_->block(node) == NULL) {
       BasicBlock* block = schedule_->NewBasicBlock();
@@ skipping 36 matching lines @@
   void CollectSuccessorBlocks(Node* node, BasicBlock** buffer,
                               IrOpcode::Value true_opcode,
                               IrOpcode::Value false_opcode) {
     Node* successors[2];
     CollectSuccessorProjections(node, successors, true_opcode, false_opcode);
     buffer[0] = schedule_->block(successors[0]);
     buffer[1] = schedule_->block(successors[1]);
   }
 
   void ConnectBranch(Node* branch) {
-    Node* branch_block_node = NodeProperties::GetControlInput(branch);
-    BasicBlock* branch_block = schedule_->block(branch_block_node);
-    DCHECK(branch_block != NULL);
-
     BasicBlock* successor_blocks[2];
     CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue,
                            IrOpcode::kIfFalse);
 
-    TraceConnect(branch, branch_block, successor_blocks[0]);
-    TraceConnect(branch, branch_block, successor_blocks[1]);
-
     // Consider branch hints.
     // TODO(turbofan): Propagate the deferred flag to all blocks dominated by
     // this IfTrue/IfFalse later.
     switch (BranchHintOf(branch->op())) {
       case BranchHint::kNone:
         break;
       case BranchHint::kTrue:
         successor_blocks[1]->set_deferred(true);
         break;
       case BranchHint::kFalse:
         successor_blocks[0]->set_deferred(true);
         break;
     }
 
-    schedule_->AddBranch(branch_block, branch, successor_blocks[0],
-                         successor_blocks[1]);
+    if (branch == component_head_) {
+      TraceConnect(branch, component_start_, successor_blocks[0]);
+      TraceConnect(branch, component_start_, successor_blocks[1]);
+      schedule_->InsertBranch(component_start_, component_end_, branch,
+                              successor_blocks[0], successor_blocks[1]);
+    } else {
+      Node* branch_block_node = NodeProperties::GetControlInput(branch);
+      BasicBlock* branch_block = schedule_->block(branch_block_node);
+      DCHECK(branch_block != NULL);
+
+      TraceConnect(branch, branch_block, successor_blocks[0]);
+      TraceConnect(branch, branch_block, successor_blocks[1]);
+      schedule_->AddBranch(branch_block, branch, successor_blocks[0],
+                           successor_blocks[1]);
+    }
   }
 
   void ConnectMerge(Node* merge) {
     // Don't connect the special merge at the end to its predecessors.
     if (IsFinalMerge(merge)) return;
 
     BasicBlock* block = schedule_->block(merge);
     DCHECK(block != NULL);
     // For all of the merge's control inputs, add a goto at the end to the
     // merge's basic block.
@@ skipping 20 matching lines @@
     } else {
       Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
             block->id().ToInt(), succ->id().ToInt());
     }
   }
 
   bool IsFinalMerge(Node* node) {
     return (node->opcode() == IrOpcode::kMerge &&
             node == scheduler_->graph_->end()->InputAt(0));
   }
+
+  Scheduler* scheduler_;
+  Schedule* schedule_;
+  ZoneQueue<Node*> queue_;
+  NodeVector control_;
+  Node* component_head_;
+  BasicBlock* component_start_;
+  BasicBlock* component_end_;
 };
 
 
 void Scheduler::BuildCFG() {
   Trace("--- CREATING CFG -------------------------------------------\n");
+
+  // Build a control-flow graph for the main control-connected component that
+  // is being spanned by the graph's start and end nodes.
   CFGBuilder cfg_builder(zone_, this);
   cfg_builder.Run();
+
   // Initialize per-block data.
   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 2: Compute special RPO and dominator tree.
 
 
 // Compute the special reverse-post-order block ordering, which is essentially
@@ skipping 455 matching lines @@
   // TODO(danno): consider using Lengauer & Tarjan's if this becomes too slow.
   for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
     BasicBlock* current_rpo = schedule_->rpo_order_[i];
     if (current_rpo != schedule_->start()) {
       BasicBlock::Predecessors::iterator current_pred =
           current_rpo->predecessors_begin();
       BasicBlock::Predecessors::iterator end = current_rpo->predecessors_end();
       DCHECK(current_pred != end);
       BasicBlock* dominator = *current_pred;
       ++current_pred;
-      // For multiple predecessors, walk up the rpo ordering until a common
+      // For multiple predecessors, walk up the RPO ordering until a common
       // dominator is found.
       int current_rpo_pos = GetRPONumber(current_rpo);
       while (current_pred != end) {
         // Don't examine backwards edges
         BasicBlock* pred = *current_pred;
         if (GetRPONumber(pred) < current_rpo_pos) {
           dominator = GetCommonDominator(dominator, *current_pred);
         }
         ++current_pred;
       }
@@ skipping 203 matching lines @@
   // optimal scheduling position.
   void VisitNode(Node* node) {
     DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
 
     // Don't schedule nodes that are already scheduled.
     if (schedule_->IsScheduled(node)) return;
     DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));
 
     // Determine the dominating block for all of the uses of this node. It is
     // the latest block that this node can be scheduled in.
+    Trace("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
     BasicBlock* block = GetCommonDominatorOfUses(node);
     DCHECK_NOT_NULL(block);
 
     int min_rpo = scheduler_->GetData(node)->minimum_block_->rpo_number();
     Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum_rpo = %d\n",
           node->id(), node->op()->mnemonic(), block->id().ToInt(),
           block->loop_depth(), min_rpo);
 
     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
     // into enclosing loop pre-headers until they would preceed their
     // ScheduleEarly position.
     BasicBlock* hoist_block = GetPreHeader(block);
     while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) {
       Trace("  hoisting #%d:%s to block %d\n", node->id(),
             node->op()->mnemonic(), hoist_block->id().ToInt());
       DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
       block = hoist_block;
       hoist_block = GetPreHeader(hoist_block);
     }
 
-    ScheduleNode(block, node);
+    // Schedule the node or a floating control structure.
+    if (NodeProperties::IsControl(node)) {
+      ScheduleFloatingControl(block, node);
+    } else {
+      ScheduleNode(block, node);
+    }
   }
 
   BasicBlock* GetPreHeader(BasicBlock* block) {
     if (block->IsLoopHeader()) {
       return block->dominator();
     } else if (block->loop_header() != NULL) {
       return block->loop_header()->dominator();
     } else {
       return NULL;
     }
@@ skipping 12 matching lines @@
     return block;
   }
 
   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 coupled (i.e. floating) phi, compute the common
       // dominator of its uses. This will not recurse more than one level.
       if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) {
-        Trace("  inspecting uses of coupled phi #%d:%s\n", use->id(),
+        Trace("  inspecting uses of coupled #%d:%s\n", use->id(),
               use->op()->mnemonic());
         DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use));
         return GetCommonDominatorOfUses(use);
       }
       // If the use is from a fixed (i.e. non-floating) phi, use the block
       // of the corresponding control input to the merge.
       if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
         Trace("  input@%d into a fixed phi #%d:%s\n", edge.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, edge.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 ScheduleFloatingControl(BasicBlock* block, Node* node) {
+    DCHECK(scheduler_->GetData(node)->is_floating_control_);
+    scheduler_->FuseFloatingControl(block, node);
+  }
+
   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. 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_->DecrementUnscheduledUseCount(*i, i.edge().from());
-    }
+    scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
   }
 
   Scheduler* scheduler_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::ScheduleLate() {
   Trace("--- SCHEDULE LATE ------------------------------------------\n");
   if (FLAG_trace_turbo_scheduler) {
@@ skipping 17 matching lines @@
       schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j);
     }
     block_num++;
   }
 }
 
 
 // -----------------------------------------------------------------------------
 
 
-bool Scheduler::ConnectFloatingControl() {
-  if (!has_floating_control_) return false;
-
-  Trace("Connecting floating control...\n");
-
-  // 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.
-    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_) {
-        Trace("  Floating control #%d:%s was scheduled in B%d\n", node->id(),
-              node->op()->mnemonic(), block->id().ToInt());
-        ConnectFloatingControlSubgraph(block, node);
-        break;
-      }
-    }
+void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
+  Trace("--- FUSE FLOATING CONTROL ----------------------------------\n");
+  if (FLAG_trace_turbo_scheduler) {
+    OFStream os(stdout);
+    os << "Schedule before control flow fusion:\n" << *schedule_;
   }
 
-  return true;
+  // Iterate on phase 1: Build control-flow graph.
+  CFGBuilder cfg_builder(zone_, this);
+  cfg_builder.Run(block, node);
+
+  // Iterate on phase 2: Compute special RPO and dominator tree.
+  // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
+  BasicBlockVector* rpo = schedule_->rpo_order();
+  for (BasicBlockVectorIter i = rpo->begin(); i != rpo->end(); ++i) {
+    BasicBlock* block = *i;
+    block->set_rpo_number(-1);
+    block->set_loop_header(NULL);
+    block->set_loop_depth(0);
+    block->set_loop_end(-1);
+  }
+  schedule_->rpo_order()->clear();
+  SpecialRPONumberer numberer(zone_, schedule_);
+  numberer.ComputeSpecialRPO();
+  GenerateImmediateDominatorTree();
+  scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
+
+  // Move previously planned nodes.
+  // TODO(mstarzinger): Improve that by supporting bulk moves.
+  MovePlannedNodes(block, schedule_->block(node));
+
+  if (FLAG_trace_turbo_scheduler) {
+    OFStream os(stdout);
+    os << "Schedule after control flow fusion:" << *schedule_;
+  }
 }
 
 
-void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) {
-  Node* block_start = block->NodeAt(0);
-  DCHECK(IrOpcode::IsControlOpcode(block_start->opcode()));
-  // Find the current "control successor" of the node that starts the block
-  // by searching the control uses for a control input edge from a connected
-  // control node.
-  Node* control_succ = NULL;
-  for (UseIter i = block_start->uses().begin(); i != block_start->uses().end();
-       ++i) {
-    Node::Edge edge = i.edge();
-    if (NodeProperties::IsControlEdge(edge) &&
-        GetData(edge.from())->is_connected_control_) {
-      DCHECK_EQ(NULL, control_succ);
-      control_succ = edge.from();
-      control_succ->ReplaceInput(edge.index(), end);
-    }
+void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
+  Trace("Move planned nodes from B%d to B%d\n", from->id().ToInt(),
+        to->id().ToInt());
+  NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]);
+  for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
+    schedule_->SetBlockForNode(to, *i);
+    scheduled_nodes_[to->id().ToSize()].push_back(*i);
   }
-  DCHECK_NE(NULL, control_succ);
-  Trace("  Inserting floating control end %d:%s between %d:%s -> %d:%s\n",
-        end->id(), end->op()->mnemonic(), control_succ->id(),
-        control_succ->op()->mnemonic(), block_start->id(),
-        block_start->op()->mnemonic());
-
-  // Find the "start" node of the control subgraph, which should be the
-  // unique node that is itself floating control but has a control input that
-  // is not floating.
-  Node* start = NULL;
-  ZoneQueue<Node*> queue(zone_);
-  queue.push(end);
-  GetData(end)->is_connected_control_ = true;
-  while (!queue.empty()) {
-    Node* node = queue.front();
-    queue.pop();
-    Trace("  Search #%d:%s for control subgraph start\n", node->id(),
-          node->op()->mnemonic());
-    int max = NodeProperties::PastControlIndex(node);
-    for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
-      Node* input = node->InputAt(i);
-      SchedulerData* data = GetData(input);
-      if (data->is_floating_control_) {
-        // {input} is floating control.
-        if (!data->is_connected_control_) {
-          // First time seeing {input} during this traversal, queue it.
-          queue.push(input);
-          data->is_connected_control_ = true;
-        }
-      } else {
-        // Otherwise, {node} is the start node, because it is floating control
-        // but is connected to {input} that is not floating control.
-        DCHECK_EQ(NULL, start);  // There can be only one.
-        start = node;
-      }
-    }
-  }
-
-  DCHECK_NE(NULL, start);
-  start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start);
-
-  Trace("  Connecting floating control start %d:%s to %d:%s\n", start->id(),
-        start->op()->mnemonic(), block_start->id(),
-        block_start->op()->mnemonic());
+  nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8