Move special RPO computation into separate class.

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 31 matching lines @@
 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);
 
     scheduler.BuildCFG();
-    Scheduler::ComputeSpecialRPO(zone_pool, schedule);
+    scheduler.ComputeSpecialRPONumbering();
     scheduler.GenerateImmediateDominatorTree();
 
     scheduler.PrepareUses();
     scheduler.ScheduleEarly();
     scheduler.ScheduleLate();
 
     had_floating_control = scheduler.ConnectFloatingControl();
   } while (had_floating_control);
 
   return schedule;
@@ skipping 103 matching lines @@
       b2 = b2->dominator();
     } else {
       b1 = b1->dominator();
     }
   }
   return b1;
 }
 
 
 // -----------------------------------------------------------------------------
-// Phase 1: Build control-flow graph and dominator tree.
+// 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.
 class CFGBuilder {
  public:
   Scheduler* scheduler_;
   Schedule* schedule_;
@@ skipping 201 matching lines @@
 
 void Scheduler::BuildCFG() {
   Trace("--- CREATING CFG -------------------------------------------\n");
   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
+// 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 (2).
+class SpecialRPONumberer {
+ public:
+  explicit SpecialRPONumberer(Zone* zone, Schedule* schedule)
+      : zone_(zone), schedule_(schedule) {}
+
+  void ComputeSpecialRPO() {
+    // RPO should not have been computed for this schedule yet.
+    CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
+    CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));
+
+    // Perform an iterative RPO traversal using an explicit stack,
+    // recording backedges that form cycles. O(|B|).
+    ZoneList<std::pair<BasicBlock*, size_t> > backedges(1, zone_);
+    SpecialRPOStackFrame* stack = zone_->NewArray<SpecialRPOStackFrame>(
+        static_cast<int>(schedule_->BasicBlockCount()));
+    BasicBlock* entry = schedule_->start();
+    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*, size_t>(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->set_loop_end(num_loops++);
+          }
+        } else {
+          // Push the successor onto the stack.
+          DCHECK(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->set_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(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.
+            DCHECK(loop != NULL && loop->header == block);
+            loop->start = order->Add(zone_, block);
+            order = loop->end;
+            block->set_rpo_number(kBlockVisited2);
+            // Pop the loop stack and continue visiting outgoing edges within
+            // 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 =
+              static_cast<int>(frame->index - block->SuccessorCount());
+          LoopInfo* info = &loops[block->loop_end()];
+          DCHECK(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;
+          DCHECK(succ->rpo_number() == kBlockUnvisited2);
+          if (loop != NULL && !loop->members->Contains(succ->id().ToInt())) {
+            // 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.
+              DCHECK(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->set_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->set_loop_header(current_header);
+      if (current->IsLoopHeader()) {
+        loop_depth++;
+        current_loop = &loops[current->loop_end()];
+        BlockList* end = current_loop->end;
+        current->set_loop_end(end == NULL
+                                  ? static_cast<int>(final_order->size())
+                                  : end->block->rpo_number());
+        current_header = current_loop->header;
+        Trace("B%d is a loop header, increment loop depth to %d\n",
+              current->id().ToInt(), loop_depth);
+      } else {
+        while (current_header != NULL &&
+               current->rpo_number() >= current_header->loop_end()) {
+          DCHECK(current_header->IsLoopHeader());
+          DCHECK(current_loop != NULL);
+          current_loop = current_loop->prev;
+          current_header = current_loop == NULL ? NULL : current_loop->header;
+          --loop_depth;
+        }
+      }
+      current->set_loop_depth(loop_depth);
+      if (current->loop_header() == NULL) {
+        Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(),
+              current->loop_depth());
+      } else {
+        Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(),
+              current->loop_header()->id().ToInt(), current->loop_depth());
+      }
+    }
+
+    // Compute the assembly order (non-deferred code first, deferred code
+    // afterwards).
+    int32_t number = 0;
+    for (auto block : *final_order) {
+      if (block->deferred()) continue;
+      block->set_ao_number(number++);
+    }
+    for (auto block : *final_order) {
+      if (!block->deferred()) continue;
+      block->set_ao_number(number++);
+    }
+
+#if DEBUG
+    if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
+    VerifySpecialRPO(num_loops, loops, final_order);
+#endif
+  }
+
+ private:
+  // 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;
+    size_t 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->set_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);
+    }
+  };
+
+  int Push(SpecialRPOStackFrame* stack, int depth, BasicBlock* child,
+           int unvisited) {
+    if (child->rpo_number() == unvisited) {
+      stack[depth].block = child;
+      stack[depth].index = 0;
+      child->set_rpo_number(kBlockOnStack);
+      return depth + 1;
+    }
+    return depth;
+  }
+
+  // Computes loop membership from the backedges of the control flow graph.
+  LoopInfo* ComputeLoopInfo(
+      SpecialRPOStackFrame* queue, int num_loops, size_t num_blocks,
+      ZoneList<std::pair<BasicBlock*, size_t> >* 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(static_cast<int>(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().ToInt())) {
+          loops[loop_num].members->Add(member->id().ToInt());
+        }
+        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 (size_t i = 0; i < block->PredecessorCount(); i++) {
+          BasicBlock* pred = block->PredecessorAt(i);
+          if (pred != header) {
+            if (!loops[loop_num].members->Contains(pred->id().ToInt())) {
+              loops[loop_num].members->Add(pred->id().ToInt());
+              queue[queue_length++].block = pred;
+            }
+          }
+        }
+      }
+    }
+    return loops;
+  }
+
+#if DEBUG
+  void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) {
+    OFStream os(stdout);
+    os << "-- RPO with " << num_loops << " loops ";
+    if (num_loops > 0) {
+      os << "(";
+      for (int i = 0; i < num_loops; i++) {
+        if (i > 0) os << " ";
+        os << "B" << loops[i].header->id();
+      }
+      os << ") ";
+    }
+    os << "-- \n";
+
+    for (size_t i = 0; i < order->size(); i++) {
+      BasicBlock* block = (*order)[i];
+      BasicBlock::Id bid = block->id();
+      // TODO(jarin,svenpanne): Add formatting here once we have support for
+      // that in streams (we want an equivalent of PrintF("%5d:", i) here).
+      os << i << ":";
+      for (int j = 0; j < num_loops; j++) {
+        bool membership = loops[j].members->Contains(bid.ToInt());
+        bool range = loops[j].header->LoopContains(block);
+        os << (membership ? " |" : "  ");
+        os << (range ? "x" : " ");
+      }
+      os << "  B" << bid << ": ";
+      if (block->loop_end() >= 0) {
+        os << " range: [" << block->rpo_number() << ", " << block->loop_end()
+           << ")";
+      }
+      os << "\n";
+    }
+  }
+
+  void VerifySpecialRPO(int num_loops, LoopInfo* loops,
+                        BasicBlockVector* order) {
+    DCHECK(order->size() > 0);
+    DCHECK((*order)[0]->id().ToInt() == 0);  // entry should be first.
+
+    for (int i = 0; i < num_loops; i++) {
+      LoopInfo* loop = &loops[i];
+      BasicBlock* header = loop->header;
+
+      DCHECK(header != NULL);
+      DCHECK(header->rpo_number() >= 0);
+      DCHECK(header->rpo_number() < static_cast<int>(order->size()));
+      DCHECK(header->loop_end() >= 0);
+      DCHECK(header->loop_end() <= static_cast<int>(order->size()));
+      DCHECK(header->loop_end() > header->rpo_number());
+
+      // Verify the start ... end list relationship.
+      int links = 0;
+      BlockList* l = loop->start;
+      DCHECK(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.
+        DCHECK(l->block->rpo_number() == links + loop->header->rpo_number());
+        links++;
+        l = l->next;
+        DCHECK(links < static_cast<int>(2 * order->size()));  // cycle?
+      }
+      DCHECK(links > 0);
+      DCHECK(links == (header->loop_end() - header->rpo_number()));
+      DCHECK(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);
+        DCHECK(block->rpo_number() == j);
+        if (j < header->rpo_number() || j >= header->loop_end()) {
+          DCHECK(!loop->members->Contains(block->id().ToInt()));
+        } else {
+          if (block == header) {
+            DCHECK(!loop->members->Contains(block->id().ToInt()));
+          } else {
+            DCHECK(loop->members->Contains(block->id().ToInt()));
+          }
+          count++;
+        }
+      }
+      DCHECK(links == count);
+    }
+  }
+#endif  // DEBUG
+
+  Zone* zone_;
+  Schedule* schedule_;
+};
+
+
+BasicBlockVector* Scheduler::ComputeSpecialRPO(ZonePool* zone_pool,
+                                               Schedule* schedule) {
+  ZonePool::Scope zone_scope(zone_pool);
+  Zone* zone = zone_scope.zone();
+
+  SpecialRPONumberer numberer(zone, schedule);
+  numberer.ComputeSpecialRPO();
+  return schedule->rpo_order();
+}
+
+
+void Scheduler::ComputeSpecialRPONumbering() {
+  Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n");
+
+  SpecialRPONumberer numberer(zone_, schedule_);
+  numberer.ComputeSpecialRPO();
+}
+
+
 void Scheduler::GenerateImmediateDominatorTree() {
-  // Build the dominator graph.  TODO(danno): consider using Lengauer & Tarjan's
-  // if this becomes really slow.
   Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
+
+  // Build the dominator graph.
+  // 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
       // 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;
       }
       current_rpo->set_dominator(dominator);
       Trace("Block %d's idom is %d\n", current_rpo->id().ToInt(),
             dominator->id().ToInt());
     }
   }
 }
 
 
 // -----------------------------------------------------------------------------
-// Phase 2: Prepare use counts for nodes.
+// Phase 3: Prepare use counts for nodes.
 
 
 class PrepareUsesVisitor : public NullNodeVisitor {
  public:
   explicit PrepareUsesVisitor(Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
       // Fixed nodes are always roots for schedule late.
@@ skipping 41 matching lines @@
   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);
 }
 
 
 // -----------------------------------------------------------------------------
-// Phase 3: Schedule nodes early.
+// Phase 4: Schedule nodes early.
 
 
 class ScheduleEarlyNodeVisitor : public NullNodeVisitor {
  public:
   explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
     Scheduler::SchedulerData* data = scheduler_->GetData(node);
     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
@@ skipping 56 matching lines @@
   Trace("--- SCHEDULE EARLY -----------------------------------------\n");
 
   // Compute the minimum RPO for each node thereby determining the earliest
   // position each node could be placed within a valid schedule.
   ScheduleEarlyNodeVisitor visitor(this);
   graph_->VisitNodeInputsFromEnd(&visitor);
 }
 
 
 // -----------------------------------------------------------------------------
-// Phase 4: Schedule nodes late.
+// Phase 5: Schedule nodes late.
 
 
 class ScheduleLateNodeVisitor {
  public:
   ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
 
   // 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) {
@@ skipping 247 matching lines @@
   }
 
   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());
 }
 
-
-// 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;
-  size_t 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->set_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->set_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, size_t num_blocks,
-    ZoneList<std::pair<BasicBlock*, size_t> >* 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(static_cast<int>(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().ToInt())) {
-        loops[loop_num].members->Add(member->id().ToInt());
-      }
-      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 (size_t i = 0; i < block->PredecessorCount(); i++) {
-        BasicBlock* pred = block->PredecessorAt(i);
-        if (pred != header) {
-          if (!loops[loop_num].members->Contains(pred->id().ToInt())) {
-            loops[loop_num].members->Add(pred->id().ToInt());
-            queue[queue_length++].block = pred;
-          }
-        }
-      }
-    }
-  }
-  return loops;
-}
-
-
-#if DEBUG
-static void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) {
-  OFStream os(stdout);
-  os << "-- RPO with " << num_loops << " loops ";
-  if (num_loops > 0) {
-    os << "(";
-    for (int i = 0; i < num_loops; i++) {
-      if (i > 0) os << " ";
-      os << "B" << loops[i].header->id();
-    }
-    os << ") ";
-  }
-  os << "-- \n";
-
-  for (size_t i = 0; i < order->size(); i++) {
-    BasicBlock* block = (*order)[i];
-    BasicBlock::Id bid = block->id();
-    // TODO(jarin,svenpanne): Add formatting here once we have support for that
-    // in streams (we want an equivalent of PrintF("%5d:", i) here).
-    os << i << ":";
-    for (int j = 0; j < num_loops; j++) {
-      bool membership = loops[j].members->Contains(bid.ToInt());
-      bool range = loops[j].header->LoopContains(block);
-      os << (membership ? " |" : "  ");
-      os << (range ? "x" : " ");
-    }
-    os << "  B" << bid << ": ";
-    if (block->loop_end() >= 0) {
-      os << " range: [" << block->rpo_number() << ", " << block->loop_end()
-         << ")";
-    }
-    os << "\n";
-  }
-}
-
-
-static void VerifySpecialRPO(int num_loops, LoopInfo* loops,
-                             BasicBlockVector* order) {
-  DCHECK(order->size() > 0);
-  DCHECK((*order)[0]->id().ToInt() == 0);  // entry should be first.
-
-  for (int i = 0; i < num_loops; i++) {
-    LoopInfo* loop = &loops[i];
-    BasicBlock* header = loop->header;
-
-    DCHECK(header != NULL);
-    DCHECK(header->rpo_number() >= 0);
-    DCHECK(header->rpo_number() < static_cast<int>(order->size()));
-    DCHECK(header->loop_end() >= 0);
-    DCHECK(header->loop_end() <= static_cast<int>(order->size()));
-    DCHECK(header->loop_end() > header->rpo_number());
-
-    // Verify the start ... end list relationship.
-    int links = 0;
-    BlockList* l = loop->start;
-    DCHECK(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.
-      DCHECK(l->block->rpo_number() == links + loop->header->rpo_number());
-      links++;
-      l = l->next;
-      DCHECK(links < static_cast<int>(2 * order->size()));  // cycle?
-    }
-    DCHECK(links > 0);
-    DCHECK(links == (header->loop_end() - header->rpo_number()));
-    DCHECK(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);
-      DCHECK(block->rpo_number() == j);
-      if (j < header->rpo_number() || j >= header->loop_end()) {
-        DCHECK(!loop->members->Contains(block->id().ToInt()));
-      } else {
-        if (block == header) {
-          DCHECK(!loop->members->Contains(block->id().ToInt()));
-        } else {
-          DCHECK(loop->members->Contains(block->id().ToInt()));
-        }
-        count++;
-      }
-    }
-    DCHECK(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(ZonePool* zone_pool,
-                                               Schedule* schedule) {
-  ZonePool::Scope zone_scope(zone_pool);
-  Zone* zone = zone_scope.zone();
-  Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n");
-  // RPO should not have been computed for this schedule yet.
-  CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number());
-  CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size()));
-
-  // Perform an iterative RPO traversal using an explicit stack,
-  // recording backedges that form cycles. O(|B|).
-  ZoneList<std::pair<BasicBlock*, size_t> > backedges(1, zone);
-  SpecialRPOStackFrame* stack = zone->NewArray<SpecialRPOStackFrame>(
-      static_cast<int>(schedule->BasicBlockCount()));
-  BasicBlock* entry = schedule->start();
-  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*, size_t>(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->set_loop_end(num_loops++);
-        }
-      } else {
-        // Push the successor onto the stack.
-        DCHECK(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->set_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.
-          DCHECK(loop != NULL && loop->header == block);
-          loop->start = order->Add(zone, block);
-          order = loop->end;
-          block->set_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 =
-            static_cast<int>(frame->index - block->SuccessorCount());
-        LoopInfo* info = &loops[block->loop_end()];
-        DCHECK(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;
-        DCHECK(succ->rpo_number() == kBlockUnvisited2);
-        if (loop != NULL && !loop->members->Contains(succ->id().ToInt())) {
-          // 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.
-            DCHECK(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->set_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->set_loop_header(current_header);
-    if (current->IsLoopHeader()) {
-      loop_depth++;
-      current_loop = &loops[current->loop_end()];
-      BlockList* end = current_loop->end;
-      current->set_loop_end(end == NULL ? static_cast<int>(final_order->size())
-                                        : end->block->rpo_number());
-      current_header = current_loop->header;
-      Trace("B%d is a loop header, increment loop depth to %d\n",
-            current->id().ToInt(), loop_depth);
-    } else {
-      while (current_header != NULL &&
-             current->rpo_number() >= current_header->loop_end()) {
-        DCHECK(current_header->IsLoopHeader());
-        DCHECK(current_loop != NULL);
-        current_loop = current_loop->prev;
-        current_header = current_loop == NULL ? NULL : current_loop->header;
-        --loop_depth;
-      }
-    }
-    current->set_loop_depth(loop_depth);
-    if (current->loop_header() == NULL) {
-      Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(),
-            current->loop_depth());
-    } else {
-      Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(),
-            current->loop_header()->id().ToInt(), current->loop_depth());
-    }
-  }
-
-  // Compute the assembly order (non-deferred code first, deferred code
-  // afterwards).
-  int32_t number = 0;
-  for (auto block : *final_order) {
-    if (block->deferred()) continue;
-    block->set_ao_number(number++);
-  }
-  for (auto block : *final_order) {
-    if (!block->deferred()) continue;
-    block->set_ao_number(number++);
-  }
-
-#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