Land the Fan (disabled)

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 "src/compiler/scheduler.h"
+
+#include "src/compiler/graph.h"
+#include "src/compiler/graph-inl.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-properties.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/data-flow.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+Scheduler::Scheduler(Zone* zone)
+    : zone_(zone),
+      graph_(NULL),
+      schedule_(NULL),
+      branches_(NodeVector::allocator_type(zone)),
+      calls_(NodeVector::allocator_type(zone)),
+      deopts_(NodeVector::allocator_type(zone)),
+      returns_(NodeVector::allocator_type(zone)),
+      loops_and_merges_(NodeVector::allocator_type(zone)),
+      node_block_placement_(BasicBlockVector::allocator_type(zone)),
+      unscheduled_uses_(IntVector::allocator_type(zone)),
+      scheduled_nodes_(NodeVectorVector::allocator_type(zone)),
+      schedule_root_nodes_(NodeVector::allocator_type(zone)),
+      schedule_early_rpo_index_(IntVector::allocator_type(zone)) {}
+
+
+Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
+    : zone_(zone),
+      graph_(graph),
+      schedule_(schedule),
+      branches_(NodeVector::allocator_type(zone)),
+      calls_(NodeVector::allocator_type(zone)),
+      deopts_(NodeVector::allocator_type(zone)),
+      returns_(NodeVector::allocator_type(zone)),
+      loops_and_merges_(NodeVector::allocator_type(zone)),
+      node_block_placement_(BasicBlockVector::allocator_type(zone)),
+      unscheduled_uses_(IntVector::allocator_type(zone)),
+      scheduled_nodes_(NodeVectorVector::allocator_type(zone)),
+      schedule_root_nodes_(NodeVector::allocator_type(zone)),
+      schedule_early_rpo_index_(IntVector::allocator_type(zone)) {}
+
+
+Schedule* Scheduler::NewSchedule(Graph* graph) {
+  graph_ = graph;
+  schedule_ = new (zone_) Schedule(zone_);
+
+  schedule_->AddNode(schedule_->end(), graph_->end());
+
+  PrepareAuxiliaryNodeData();
+
+  // Create basic blocks for each block and merge node in the graph.
+  CreateBlocks();
+
+  // Wire the basic blocks together.
+  WireBlocks();
+
+  PrepareAuxiliaryBlockData();
+
+  ComputeSpecialRPO();
+  GenerateImmediateDominatorTree();
+
+  PrepareUses();
+  ScheduleEarly();
+  ScheduleLate();
+
+  return schedule_;
+}
+
+
+class CreateBlockVisitor : public NullNodeVisitor {
+ public:
+  explicit CreateBlockVisitor(Scheduler* scheduler) : scheduler_(scheduler) {}
+
+  GenericGraphVisit::Control Post(Node* node) {
+    Schedule* schedule = scheduler_->schedule_;
+    switch (node->opcode()) {
+      case IrOpcode::kIfTrue:
+      case IrOpcode::kIfFalse:
+      case IrOpcode::kContinuation:
+      case IrOpcode::kLazyDeoptimization: {
+        BasicBlock* block = schedule->NewBasicBlock();
+        schedule->AddNode(block, node);
+        break;
+      }
+      case IrOpcode::kLoop:
+      case IrOpcode::kMerge: {
+        BasicBlock* block = schedule->NewBasicBlock();
+        schedule->AddNode(block, node);
+        scheduler_->loops_and_merges_.push_back(node);
+        break;
+      }
+      case IrOpcode::kBranch: {
+        scheduler_->branches_.push_back(node);
+        break;
+      }
+      case IrOpcode::kDeoptimize: {
+        scheduler_->deopts_.push_back(node);
+        break;
+      }
+      case IrOpcode::kCall: {
+        if (NodeProperties::CanLazilyDeoptimize(node)) {
+          scheduler_->calls_.push_back(node);
+        }
+        break;
+      }
+      case IrOpcode::kReturn:
+        scheduler_->returns_.push_back(node);
+        break;
+      default:
+        break;
+    }
+
+    return GenericGraphVisit::CONTINUE;
+  }
+
+ private:
+  Scheduler* scheduler_;
+};
+
+
+void Scheduler::CreateBlocks() {
+  CreateBlockVisitor create_blocks(this);
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("---------------- CREATING BLOCKS ------------------\n");
+  }
+  schedule_->AddNode(schedule_->entry(), graph_->start());
+  graph_->VisitNodeInputsFromEnd(&create_blocks);
+}
+
+
+void Scheduler::WireBlocks() {
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("----------------- WIRING BLOCKS -------------------\n");
+  }
+  AddSuccessorsForBranches();
+  AddSuccessorsForReturns();
+  AddSuccessorsForCalls();
+  AddSuccessorsForDeopts();
+  AddPredecessorsForLoopsAndMerges();
+  // TODO(danno): Handle Throw, et al.
+}
+
+
+void Scheduler::PrepareAuxiliaryNodeData() {
+  unscheduled_uses_.resize(graph_->NodeCount(), 0);
+  schedule_early_rpo_index_.resize(graph_->NodeCount(), 0);
+}
+
+
+void Scheduler::PrepareAuxiliaryBlockData() {
+  Zone* zone = schedule_->zone();
+  scheduled_nodes_.resize(schedule_->BasicBlockCount(),
+                          NodeVector(NodeVector::allocator_type(zone)));
+  schedule_->immediate_dominator_.resize(schedule_->BasicBlockCount(), NULL);
+}
+
+
+void Scheduler::AddPredecessorsForLoopsAndMerges() {
+  for (NodeVectorIter i = loops_and_merges_.begin();
+       i != loops_and_merges_.end(); ++i) {
+    Node* merge_or_loop = *i;
+    BasicBlock* block = schedule_->block(merge_or_loop);
+    ASSERT(block != NULL);
+    // For all of the merge's control inputs, add a goto at the end to the
+    // merge's basic block.
+    for (InputIter j = (*i)->inputs().begin(); j != (*i)->inputs().end(); ++j) {
+      if (NodeProperties::IsBasicBlockBegin(*i)) {
+        BasicBlock* predecessor_block = schedule_->block(*j);
+        if ((*j)->opcode() != IrOpcode::kReturn &&
+            (*j)->opcode() != IrOpcode::kDeoptimize) {
+          ASSERT(predecessor_block != NULL);
+          if (FLAG_trace_turbo_scheduler) {
+            IrOpcode::Value opcode = (*i)->opcode();
+            PrintF("node %d (%s) in block %d -> block %d\n", (*i)->id(),
+                   IrOpcode::Mnemonic(opcode), predecessor_block->id(),
+                   block->id());
+          }
+          schedule_->AddGoto(predecessor_block, block);
+        }
+      }
+    }
+  }
+}
+
+
+void Scheduler::AddSuccessorsForCalls() {
+  for (NodeVectorIter i = calls_.begin(); i != calls_.end(); ++i) {
+    Node* call = *i;
+    ASSERT(call->opcode() == IrOpcode::kCall);
+    ASSERT(NodeProperties::CanLazilyDeoptimize(call));
+
+    Node* lazy_deopt_node = NULL;
+    Node* cont_node = NULL;
+    // Find the continuation and lazy-deopt nodes among the uses.
+    for (UseIter use_iter = call->uses().begin();
+         use_iter != call->uses().end(); ++use_iter) {
+      switch ((*use_iter)->opcode()) {
+        case IrOpcode::kContinuation: {
+          ASSERT(cont_node == NULL);
+          cont_node = *use_iter;
+          break;
+        }
+        case IrOpcode::kLazyDeoptimization: {
+          ASSERT(lazy_deopt_node == NULL);
+          lazy_deopt_node = *use_iter;
+          break;
+        }
+        default:
+          break;
+      }
+    }
+    ASSERT(lazy_deopt_node != NULL);
+    ASSERT(cont_node != NULL);
+    BasicBlock* cont_successor_block = schedule_->block(cont_node);
+    BasicBlock* deopt_successor_block = schedule_->block(lazy_deopt_node);
+    Node* call_block_node = NodeProperties::GetControlInput(call);
+    BasicBlock* call_block = schedule_->block(call_block_node);
+    if (FLAG_trace_turbo_scheduler) {
+      IrOpcode::Value opcode = call->opcode();
+      PrintF("node %d (%s) in block %d -> block %d\n", call->id(),
+             IrOpcode::Mnemonic(opcode), call_block->id(),
+             cont_successor_block->id());
+      PrintF("node %d (%s) in block %d -> block %d\n", call->id(),
+             IrOpcode::Mnemonic(opcode), call_block->id(),
+             deopt_successor_block->id());
+    }
+    schedule_->AddCall(call_block, call, cont_successor_block,
+                       deopt_successor_block);
+  }
+}
+
+
+void Scheduler::AddSuccessorsForDeopts() {
+  for (NodeVectorIter i = deopts_.begin(); i != deopts_.end(); ++i) {
+    Node* deopt_block_node = NodeProperties::GetControlInput(*i);
+    BasicBlock* deopt_block = schedule_->block(deopt_block_node);
+    ASSERT(deopt_block != NULL);
+    if (FLAG_trace_turbo_scheduler) {
+      IrOpcode::Value opcode = (*i)->opcode();
+      PrintF("node %d (%s) in block %d -> end\n", (*i)->id(),
+             IrOpcode::Mnemonic(opcode), deopt_block->id());
+    }
+    schedule_->AddDeoptimize(deopt_block, *i);
+  }
+}
+
+
+void Scheduler::AddSuccessorsForBranches() {
+  for (NodeVectorIter i = branches_.begin(); i != branches_.end(); ++i) {
+    Node* branch = *i;
+    ASSERT(branch->opcode() == IrOpcode::kBranch);
+    Node* branch_block_node = NodeProperties::GetControlInput(branch);
+    BasicBlock* branch_block = schedule_->block(branch_block_node);
+    ASSERT(branch_block != NULL);
+    UseIter use_iter = branch->uses().begin();
+    Node* first_successor = *use_iter;
+    ++use_iter;
+    ASSERT(use_iter != branch->uses().end());
+    Node* second_successor = *use_iter;
+    ASSERT(++use_iter == branch->uses().end());
+    Node* true_successor_node = first_successor->opcode() == IrOpcode::kIfTrue
+                                    ? first_successor
+                                    : second_successor;
+    Node* false_successor_node = first_successor->opcode() == IrOpcode::kIfTrue
+                                     ? second_successor
+                                     : first_successor;
+    ASSERT(true_successor_node->opcode() == IrOpcode::kIfTrue);
+    ASSERT(false_successor_node->opcode() == IrOpcode::kIfFalse);
+    BasicBlock* true_successor_block = schedule_->block(true_successor_node);
+    BasicBlock* false_successor_block = schedule_->block(false_successor_node);
+    ASSERT(true_successor_block != NULL);
+    ASSERT(false_successor_block != NULL);
+    if (FLAG_trace_turbo_scheduler) {
+      IrOpcode::Value opcode = branch->opcode();
+      PrintF("node %d (%s) in block %d -> block %d\n", branch->id(),
+             IrOpcode::Mnemonic(opcode), branch_block->id(),
+             true_successor_block->id());
+      PrintF("node %d (%s) in block %d -> block %d\n", branch->id(),
+             IrOpcode::Mnemonic(opcode), branch_block->id(),
+             false_successor_block->id());
+    }
+    schedule_->AddBranch(branch_block, branch, true_successor_block,
+                         false_successor_block);
+  }
+}
+
+
+void Scheduler::AddSuccessorsForReturns() {
+  for (NodeVectorIter i = returns_.begin(); i != returns_.end(); ++i) {
+    Node* return_block_node = NodeProperties::GetControlInput(*i);
+    BasicBlock* return_block = schedule_->block(return_block_node);
+    ASSERT(return_block != NULL);
+    if (FLAG_trace_turbo_scheduler) {
+      IrOpcode::Value opcode = (*i)->opcode();
+      PrintF("node %d (%s) in block %d -> end\n", (*i)->id(),
+             IrOpcode::Mnemonic(opcode), return_block->id());
+    }
+    schedule_->AddReturn(return_block, *i);
+  }
+}
+
+
+BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
+  while (b1 != b2) {
+    int b1_rpo = GetRPONumber(b1);
+    int b2_rpo = GetRPONumber(b2);
+    ASSERT(b1_rpo != b2_rpo);
+    if (b1_rpo < b2_rpo) {
+      b2 = schedule_->immediate_dominator_[b2->id()];
+    } else {
+      b1 = schedule_->immediate_dominator_[b1->id()];
+    }
+  }
+  return b1;
+}
+
+
+void Scheduler::GenerateImmediateDominatorTree() {
+  // Build the dominator graph.  TODO(danno): consider using Lengauer & Tarjan's
+  // if this becomes really slow.
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("------------ IMMEDIATE BLOCK DOMINATORS -----------\n");
+  }
+  for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
+    BasicBlock* current_rpo = schedule_->rpo_order_[i];
+    if (current_rpo != schedule_->entry()) {
+      BasicBlock::Predecessors::iterator current_pred =
+          current_rpo->predecessors().begin();
+      BasicBlock::Predecessors::iterator end =
+          current_rpo->predecessors().end();
+      ASSERT(current_pred != end);
+      BasicBlock* dominator = *current_pred;
+      ++current_pred;
+      // 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;
+      }
+      schedule_->immediate_dominator_[current_rpo->id()] = dominator;
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Block %d's idom is %d\n", current_rpo->id(), dominator->id());
+      }
+    }
+  }
+}
+
+
+class ScheduleEarlyNodeVisitor : public NullNodeVisitor {
+ public:
+  explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler)
+      : has_changed_rpo_constraints_(true),
+        scheduler_(scheduler),
+        schedule_(scheduler->schedule_) {}
+
+  GenericGraphVisit::Control Pre(Node* node) {
+    int id = node->id();
+    int max_rpo = 0;
+    // Fixed nodes already know their schedule early position.
+    if (IsFixedNode(node)) {
+      BasicBlock* block = schedule_->block(node);
+      ASSERT(block != NULL);
+      max_rpo = block->rpo_number_;
+      if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) {
+        has_changed_rpo_constraints_ = true;
+      }
+      scheduler_->schedule_early_rpo_index_[id] = max_rpo;
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Node %d pre-scheduled early at rpo limit %d\n", id, max_rpo);
+      }
+    }
+    return GenericGraphVisit::CONTINUE;
+  }
+
+  GenericGraphVisit::Control Post(Node* node) {
+    int id = node->id();
+    int max_rpo = 0;
+    // Otherwise, the minimum rpo for the node is the max of all of the inputs.
+    if (!IsFixedNode(node)) {
+      ASSERT(!NodeProperties::IsBasicBlockBegin(node));
+      for (InputIter i = node->inputs().begin(); i != node->inputs().end();
+           ++i) {
+        int control_rpo = scheduler_->schedule_early_rpo_index_[(*i)->id()];
+        if (control_rpo > max_rpo) {
+          max_rpo = control_rpo;
+        }
+      }
+      if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) {
+        has_changed_rpo_constraints_ = true;
+      }
+      scheduler_->schedule_early_rpo_index_[id] = max_rpo;
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Node %d post-scheduled early at rpo limit %d\n", id, max_rpo);
+      }
+    }
+    return GenericGraphVisit::CONTINUE;
+  }
+
+  static bool IsFixedNode(Node* node) {
+    return NodeProperties::HasFixedSchedulePosition(node) ||
+           !NodeProperties::CanBeScheduled(node);
+  }
+
+  // TODO(mstarzinger): Dirty hack to unblock others, schedule early should be
+  // rewritten to use a pre-order traversal from the start instead.
+  bool has_changed_rpo_constraints_;
+
+ private:
+  Scheduler* scheduler_;
+  Schedule* schedule_;
+};
+
+
+void Scheduler::ScheduleEarly() {
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("------------------- SCHEDULE EARLY ----------------\n");
+  }
+
+  int fixpoint_count = 0;
+  ScheduleEarlyNodeVisitor visitor(this);
+  while (visitor.has_changed_rpo_constraints_) {
+    visitor.has_changed_rpo_constraints_ = false;
+    graph_->VisitNodeInputsFromEnd(&visitor);
+    fixpoint_count++;
+  }
+
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("It took %d iterations to determine fixpoint\n", fixpoint_count);
+  }
+}
+
+
+class PrepareUsesVisitor : public NullNodeVisitor {
+ public:
+  explicit PrepareUsesVisitor(Scheduler* scheduler)
+      : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
+
+  GenericGraphVisit::Control Pre(Node* node) {
+    // Some nodes must be scheduled explicitly to ensure they are in exactly the
+    // right place; it's a convenient place during the preparation of use counts
+    // to schedule them.
+    if (!schedule_->IsScheduled(node) &&
+        NodeProperties::HasFixedSchedulePosition(node)) {
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Fixed position node %d is unscheduled, scheduling now\n",
+               node->id());
+      }
+      IrOpcode::Value opcode = node->opcode();
+      BasicBlock* block =
+          opcode == IrOpcode::kParameter
+              ? schedule_->entry()
+              : schedule_->block(NodeProperties::GetControlInput(node));
+      ASSERT(block != NULL);
+      schedule_->AddNode(block, node);
+    }
+
+    if (NodeProperties::IsScheduleRoot(node)) {
+      scheduler_->schedule_root_nodes_.push_back(node);
+    }
+
+    return GenericGraphVisit::CONTINUE;
+  }
+
+  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) && NodeProperties::CanBeScheduled(from)) {
+      ASSERT(!NodeProperties::HasFixedSchedulePosition(from));
+      ++scheduler_->unscheduled_uses_[to->id()];
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Incrementing uses of node %d from %d to %d\n", to->id(),
+               from->id(), scheduler_->unscheduled_uses_[to->id()]);
+      }
+    }
+  }
+
+ private:
+  Scheduler* scheduler_;
+  Schedule* schedule_;
+};
+
+
+void Scheduler::PrepareUses() {
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("------------------- 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 cannot be scheduled or are already scheduled.
+    if (!NodeProperties::CanBeScheduled(node) || schedule_->IsScheduled(node)) {
+      return GenericGraphVisit::CONTINUE;
+    }
+    ASSERT(!NodeProperties::HasFixedSchedulePosition(node));
+
+    // If all the uses of a node have been scheduled, then the node itself can
+    // be scheduled.
+    bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0;
+    if (FLAG_trace_turbo_scheduler) {
+      PrintF("Testing for schedule eligibility for node %d -> %s\n", node->id(),
+             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);
+    }
+    ASSERT(block != NULL);
+
+    int min_rpo = scheduler_->schedule_early_rpo_index_[node->id()];
+    if (FLAG_trace_turbo_scheduler) {
+      PrintF(
+          "Schedule late conservative for node %d is block %d at "
+          "loop depth %d, min rpo = %d\n",
+          node->id(), block->id(), block->loop_depth_, min_rpo);
+    }
+    // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
+    // into enlcosing loop pre-headers until they would preceed their
+    // ScheduleEarly position.
+    BasicBlock* hoist_block = block;
+    while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) {
+      if (hoist_block->loop_depth_ < block->loop_depth_) {
+        block = hoist_block;
+        if (FLAG_trace_turbo_scheduler) {
+          PrintF("Hoisting node %d to block %d\n", node->id(), block->id());
+        }
+      }
+      // Try to hoist to the pre-header of the loop header.
+      hoist_block = hoist_block->loop_header();
+      if (hoist_block != NULL) {
+        BasicBlock* pre_header = schedule_->dominator(hoist_block);
+        ASSERT(pre_header == NULL ||
+               *hoist_block->predecessors().begin() == pre_header);
+        if (FLAG_trace_turbo_scheduler) {
+          PrintF(
+              "Try hoist to pre-header block %d of loop header block %d,"
+              " depth would be %d\n",
+              pre_header->id(), hoist_block->id(), 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 the use is a phi, forward through the the phi to the basic block
+    // corresponding to the phi's input.
+    if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) {
+      int index = edge.index();
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Use %d is input %d to a phi\n", use->id(), index);
+      }
+      use = NodeProperties::GetControlInput(use, 0);
+      opcode = use->opcode();
+      ASSERT(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop);
+      use = NodeProperties::GetControlInput(use, index);
+    }
+    BasicBlock* result = schedule_->block(use);
+    if (result == NULL) return NULL;
+    if (FLAG_trace_turbo_scheduler) {
+      PrintF("Must dominate use %d in block %d\n", use->id(), result->id());
+    }
+    return result;
+  }
+
+  bool IsNodeEligible(Node* node) {
+    bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0;
+    return eligible;
+  }
+
+  void ScheduleNode(BasicBlock* block, Node* node) {
+    schedule_->PlanNode(block, node);
+    scheduler_->scheduled_nodes_[block->id()].push_back(node);
+
+    // Reduce the use count of the node's inputs to potentially make them
+    // scheduable.
+    for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
+      ASSERT(scheduler_->unscheduled_uses_[(*i)->id()] > 0);
+      --scheduler_->unscheduled_uses_[(*i)->id()];
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Decrementing use count for node %d from node %d (now %d)\n",
+               (*i)->id(), i.edge().from()->id(),
+               scheduler_->unscheduled_uses_[(*i)->id()]);
+        if (scheduler_->unscheduled_uses_[(*i)->id()] == 0) {
+          PrintF("node %d is now eligible for scheduling\n", (*i)->id());
+        }
+      }
+    }
+  }
+
+  Scheduler* scheduler_;
+  Schedule* schedule_;
+};
+
+
+void Scheduler::ScheduleLate() {
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("------------------- SCHEDULE LATE -----------------\n");
+  }
+
+  // Schedule: Places nodes in dominator block of all their uses.
+  ScheduleLateNodeVisitor schedule_late_visitor(this);
+
+  for (NodeVectorIter i = schedule_root_nodes_.begin();
+       i != schedule_root_nodes_.end(); ++i) {
+    GenericGraphVisit::Visit<ScheduleLateNodeVisitor,
+                             NodeInputIterationTraits<Node> >(
+        graph_, *i, &schedule_late_visitor);
+  }
+
+  // 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++;
+  }
+}
+
+
+// Numbering for BasicBlockData.rpo_number_ for this block traversal:
+static const int kBlockOnStack = -2;
+static const int kBlockVisited1 = -3;
+static const int kBlockVisited2 = -4;
+static const int kBlockUnvisited1 = -1;
+static const int kBlockUnvisited2 = kBlockVisited1;
+
+struct SpecialRPOStackFrame {
+  BasicBlock* block;
+  int index;
+};
+
+struct BlockList {
+  BasicBlock* block;
+  BlockList* next;
+
+  BlockList* Add(Zone* zone, BasicBlock* b) {
+    BlockList* list = static_cast<BlockList*>(zone->New(sizeof(BlockList)));
+    list->block = b;
+    list->next = this;
+    return list;
+  }
+
+  void Serialize(BasicBlockVector* final_order) {
+    for (BlockList* l = this; l != NULL; l = l->next) {
+      l->block->rpo_number_ = static_cast<int>(final_order->size());
+      final_order->push_back(l->block);
+    }
+  }
+};
+
+struct LoopInfo {
+  BasicBlock* header;
+  ZoneList<BasicBlock*>* outgoing;
+  BitVector* members;
+  LoopInfo* prev;
+  BlockList* end;
+  BlockList* start;
+
+  void AddOutgoing(Zone* zone, BasicBlock* block) {
+    if (outgoing == NULL) outgoing = new (zone) ZoneList<BasicBlock*>(2, zone);
+    outgoing->Add(block, zone);
+  }
+};
+
+
+static int Push(SpecialRPOStackFrame* stack, int depth, BasicBlock* child,
+                int unvisited) {
+  if (child->rpo_number_ == unvisited) {
+    stack[depth].block = child;
+    stack[depth].index = 0;
+    child->rpo_number_ = kBlockOnStack;
+    return depth + 1;
+  }
+  return depth;
+}
+
+
+// Computes loop membership from the backedges of the control flow graph.
+static LoopInfo* ComputeLoopInfo(
+    Zone* zone, SpecialRPOStackFrame* queue, int num_loops, int num_blocks,
+    ZoneList<std::pair<BasicBlock*, int> >* backedges) {
+  LoopInfo* loops = zone->NewArray<LoopInfo>(num_loops);
+  memset(loops, 0, num_loops * sizeof(LoopInfo));
+
+  // Compute loop membership starting from backedges.
+  // O(max(loop_depth) * max(|loop|)
+  for (int i = 0; i < backedges->length(); i++) {
+    BasicBlock* member = backedges->at(i).first;
+    BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
+    int loop_num = header->loop_end_;
+    if (loops[loop_num].header == NULL) {
+      loops[loop_num].header = header;
+      loops[loop_num].members = new (zone) BitVector(num_blocks, zone);
+    }
+
+    int queue_length = 0;
+    if (member != header) {
+      // As long as the header doesn't have a backedge to itself,
+      // Push the member onto the queue and process its predecessors.
+      if (!loops[loop_num].members->Contains(member->id())) {
+        loops[loop_num].members->Add(member->id());
+      }
+      queue[queue_length++].block = member;
+    }
+
+    // Propagate loop membership backwards. All predecessors of M up to the
+    // loop header H are members of the loop too. O(|blocks between M and H|).
+    while (queue_length > 0) {
+      BasicBlock* block = queue[--queue_length].block;
+      for (int i = 0; i < block->PredecessorCount(); i++) {
+        BasicBlock* pred = block->PredecessorAt(i);
+        if (pred != header) {
+          if (!loops[loop_num].members->Contains(pred->id())) {
+            loops[loop_num].members->Add(pred->id());
+            queue[queue_length++].block = pred;
+          }
+        }
+      }
+    }
+  }
+  return loops;
+}
+
+
+#if DEBUG
+static void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) {
+  PrintF("-- RPO with %d loops ", num_loops);
+  if (num_loops > 0) {
+    PrintF("(");
+    for (int i = 0; i < num_loops; i++) {
+      if (i > 0) PrintF(" ");
+      PrintF("B%d", loops[i].header->id());
+    }
+    PrintF(") ");
+  }
+  PrintF("-- \n");
+
+  for (int i = 0; i < static_cast<int>(order->size()); i++) {
+    BasicBlock* block = (*order)[i];
+    int bid = block->id();
+    PrintF("%5d:", i);
+    for (int i = 0; i < num_loops; i++) {
+      bool membership = loops[i].members->Contains(bid);
+      bool range = loops[i].header->LoopContains(block);
+      PrintF(membership ? " |" : "  ");
+      PrintF(range ? "x" : " ");
+    }
+    PrintF("  B%d: ", bid);
+    if (block->loop_end_ >= 0) {
+      PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_);
+    }
+    PrintF("\n");
+  }
+}
+
+
+static void VerifySpecialRPO(int num_loops, LoopInfo* loops,
+                             BasicBlockVector* order) {
+  ASSERT(order->size() > 0);
+  ASSERT((*order)[0]->id() == 0);  // entry should be first.
+
+  for (int i = 0; i < num_loops; i++) {
+    LoopInfo* loop = &loops[i];
+    BasicBlock* header = loop->header;
+
+    ASSERT(header != NULL);
+    ASSERT(header->rpo_number_ >= 0);
+    ASSERT(header->rpo_number_ < static_cast<int>(order->size()));
+    ASSERT(header->loop_end_ >= 0);
+    ASSERT(header->loop_end_ <= static_cast<int>(order->size()));
+    ASSERT(header->loop_end_ > header->rpo_number_);
+
+    // Verify the start ... end list relationship.
+    int links = 0;
+    BlockList* l = loop->start;
+    ASSERT(l != NULL && l->block == header);
+    bool end_found;
+    while (true) {
+      if (l == NULL || l == loop->end) {
+        end_found = (loop->end == l);
+        break;
+      }
+      // The list should be in same order as the final result.
+      ASSERT(l->block->rpo_number_ == links + loop->header->rpo_number_);
+      links++;
+      l = l->next;
+      ASSERT(links < static_cast<int>(2 * order->size()));  // cycle?
+    }
+    ASSERT(links > 0);
+    ASSERT(links == (header->loop_end_ - header->rpo_number_));
+    ASSERT(end_found);
+
+    // Check the contiguousness of loops.
+    int count = 0;
+    for (int j = 0; j < static_cast<int>(order->size()); j++) {
+      BasicBlock* block = order->at(j);
+      ASSERT(block->rpo_number_ == j);
+      if (j < header->rpo_number_ || j >= header->loop_end_) {
+        ASSERT(!loop->members->Contains(block->id()));
+      } else {
+        if (block == header) {
+          ASSERT(!loop->members->Contains(block->id()));
+        } else {
+          ASSERT(loop->members->Contains(block->id()));
+        }
+        count++;
+      }
+    }
+    ASSERT(links == count);
+  }
+}
+#endif  // DEBUG
+
+
+// Compute the special reverse-post-order block ordering, which is essentially
+// a RPO of the graph where loop bodies are contiguous. Properties:
+// 1. If block A is a predecessor of B, then A appears before B in the order,
+//    unless B is a loop header and A is in the loop headed at B
+//    (i.e. A -> B is a backedge).
+// => If block A dominates block B, then A appears before B in the order.
+// => If block A is a loop header, A appears before all blocks in the loop
+//    headed at A.
+// 2. All loops are contiguous in the order (i.e. no intervening blocks that
+//    do not belong to the loop.)
+// Note a simple RPO traversal satisfies (1) but not (3).
+BasicBlockVector* Scheduler::ComputeSpecialRPO() {
+  if (FLAG_trace_turbo_scheduler) {
+    PrintF("------------- COMPUTING SPECIAL RPO ---------------\n");
+  }
+  // RPO should not have been computed for this schedule yet.
+  CHECK_EQ(kBlockUnvisited1, schedule_->entry()->rpo_number_);
+  CHECK_EQ(0, schedule_->rpo_order_.size());
+
+  // Perform an iterative RPO traversal using an explicit stack,
+  // recording backedges that form cycles. O(|B|).
+  ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone_);
+  SpecialRPOStackFrame* stack =
+      zone_->NewArray<SpecialRPOStackFrame>(schedule_->BasicBlockCount());
+  BasicBlock* entry = schedule_->entry();
+  BlockList* order = NULL;
+  int stack_depth = Push(stack, 0, entry, kBlockUnvisited1);
+  int num_loops = 0;
+
+  while (stack_depth > 0) {
+    int current = stack_depth - 1;
+    SpecialRPOStackFrame* frame = stack + current;
+
+    if (frame->index < frame->block->SuccessorCount()) {
+      // Process the next successor.
+      BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
+      if (succ->rpo_number_ == kBlockVisited1) continue;
+      if (succ->rpo_number_ == kBlockOnStack) {
+        // The successor is on the stack, so this is a backedge (cycle).
+        backedges.Add(
+            std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone_);
+        if (succ->loop_end_ < 0) {
+          // Assign a new loop number to the header if it doesn't have one.
+          succ->loop_end_ = num_loops++;
+        }
+      } else {
+        // Push the successor onto the stack.
+        ASSERT(succ->rpo_number_ == kBlockUnvisited1);
+        stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1);
+      }
+    } else {
+      // Finished with all successors; pop the stack and add the block.
+      order = order->Add(zone_, frame->block);
+      frame->block->rpo_number_ = kBlockVisited1;
+      stack_depth--;
+    }
+  }
+
+  // If no loops were encountered, then the order we computed was correct.
+  LoopInfo* loops = NULL;
+  if (num_loops != 0) {
+    // Otherwise, compute the loop information from the backedges in order
+    // to perform a traversal that groups loop bodies together.
+    loops = ComputeLoopInfo(zone_, stack, num_loops,
+                            schedule_->BasicBlockCount(), &backedges);
+
+    // Initialize the "loop stack". Note the entry could be a loop header.
+    LoopInfo* loop = entry->IsLoopHeader() ? &loops[entry->loop_end_] : NULL;
+    order = NULL;
+
+    // Perform an iterative post-order traversal, visiting loop bodies before
+    // edges that lead out of loops. Visits each block once, but linking loop
+    // sections together is linear in the loop size, so overall is
+    // O(|B| + max(loop_depth) * max(|loop|))
+    stack_depth = Push(stack, 0, entry, kBlockUnvisited2);
+    while (stack_depth > 0) {
+      SpecialRPOStackFrame* frame = stack + (stack_depth - 1);
+      BasicBlock* block = frame->block;
+      BasicBlock* succ = NULL;
+
+      if (frame->index < block->SuccessorCount()) {
+        // Process the next normal successor.
+        succ = block->SuccessorAt(frame->index++);
+      } else if (block->IsLoopHeader()) {
+        // Process additional outgoing edges from the loop header.
+        if (block->rpo_number_ == kBlockOnStack) {
+          // Finish the loop body the first time the header is left on the
+          // stack.
+          ASSERT(loop != NULL && loop->header == block);
+          loop->start = order->Add(zone_, block);
+          order = loop->end;
+          block->rpo_number_ = kBlockVisited2;
+          // Pop the loop stack and continue visiting outgoing edges within the
+          // the context of the outer loop, if any.
+          loop = loop->prev;
+          // We leave the loop header on the stack; the rest of this iteration
+          // and later iterations will go through its outgoing edges list.
+        }
+
+        // Use the next outgoing edge if there are any.
+        int outgoing_index = frame->index - block->SuccessorCount();
+        LoopInfo* info = &loops[block->loop_end_];
+        ASSERT(loop != info);
+        if (info->outgoing != NULL &&
+            outgoing_index < info->outgoing->length()) {
+          succ = info->outgoing->at(outgoing_index);
+          frame->index++;
+        }
+      }
+
+      if (succ != NULL) {
+        // Process the next successor.
+        if (succ->rpo_number_ == kBlockOnStack) continue;
+        if (succ->rpo_number_ == kBlockVisited2) continue;
+        ASSERT(succ->rpo_number_ == kBlockUnvisited2);
+        if (loop != NULL && !loop->members->Contains(succ->id())) {
+          // The successor is not in the current loop or any nested loop.
+          // Add it to the outgoing edges of this loop and visit it later.
+          loop->AddOutgoing(zone_, succ);
+        } else {
+          // Push the successor onto the stack.
+          stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2);
+          if (succ->IsLoopHeader()) {
+            // Push the inner loop onto the loop stack.
+            ASSERT(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops);
+            LoopInfo* next = &loops[succ->loop_end_];
+            next->end = order;
+            next->prev = loop;
+            loop = next;
+          }
+        }
+      } else {
+        // Finished with all successors of the current block.
+        if (block->IsLoopHeader()) {
+          // If we are going to pop a loop header, then add its entire body.
+          LoopInfo* info = &loops[block->loop_end_];
+          for (BlockList* l = info->start; true; l = l->next) {
+            if (l->next == info->end) {
+              l->next = order;
+              info->end = order;
+              break;
+            }
+          }
+          order = info->start;
+        } else {
+          // Pop a single node off the stack and add it to the order.
+          order = order->Add(zone_, block);
+          block->rpo_number_ = kBlockVisited2;
+        }
+        stack_depth--;
+      }
+    }
+  }
+
+  // Construct the final order from the list.
+  BasicBlockVector* final_order = &schedule_->rpo_order_;
+  order->Serialize(final_order);
+
+  // Compute the correct loop header for every block and set the correct loop
+  // ends.
+  LoopInfo* current_loop = NULL;
+  BasicBlock* current_header = NULL;
+  int loop_depth = 0;
+  for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end();
+       ++i) {
+    BasicBlock* current = *i;
+    current->loop_header_ = current_header;
+    if (current->IsLoopHeader()) {
+      loop_depth++;
+      current_loop = &loops[current->loop_end_];
+      BlockList* end = current_loop->end;
+      current->loop_end_ = end == NULL ? static_cast<int>(final_order->size())
+                                       : end->block->rpo_number_;
+      current_header = current_loop->header;
+      if (FLAG_trace_turbo_scheduler) {
+        PrintF("Block %d is a loop header, increment loop depth to %d\n",
+               current->id(), loop_depth);
+      }
+    } else {
+      while (current_header != NULL &&
+             current->rpo_number_ >= current_header->loop_end_) {
+        ASSERT(current_header->IsLoopHeader());
+        ASSERT(current_loop != NULL);
+        current_loop = current_loop->prev;
+        current_header = current_loop == NULL ? NULL : current_loop->header;
+        --loop_depth;
+      }
+    }
+    current->loop_depth_ = loop_depth;
+    if (FLAG_trace_turbo_scheduler) {
+      if (current->loop_header_ == NULL) {
+        PrintF("Block %d's loop header is NULL, loop depth %d\n", current->id(),
+               current->loop_depth_);
+      } else {
+        PrintF("Block %d's loop header is block %d, loop depth %d\n",
+               current->id(), current->loop_header_->id(),
+               current->loop_depth_);
+      }
+    }
+  }
+
+#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