Remove duplication in Scheduler and simplify interface. Make ComputeSchedule() and ComputeSpecialRP…

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* Scheduler::ComputeSchedule(Graph* graph) {
+  Zone tmp_zone(graph->zone()->isolate());
+  Schedule* schedule = new (graph->zone()) Schedule(graph->zone());
+  Scheduler scheduler(&tmp_zone, graph, schedule);
 
-  schedule_->AddNode(schedule_->end(), graph_->end());
+  schedule->AddNode(schedule->end(), graph->end());
 
-  PrepareAuxiliaryNodeData();
+  scheduler.PrepareAuxiliaryNodeData();
+  scheduler.CreateBlocks();
+  scheduler.WireBlocks();
+  scheduler.PrepareAuxiliaryBlockData();
 
-  // Create basic blocks for each block and merge node in the graph.
-  CreateBlocks();
+  Scheduler::ComputeSpecialRPO(schedule);
+  scheduler.GenerateImmediateDominatorTree();
 
-  // Wire the basic blocks together.
-  WireBlocks();
+  scheduler.PrepareUses();
+  scheduler.ScheduleEarly();
+  scheduler.ScheduleLate();
 
-  PrepareAuxiliaryBlockData();
-
-  ComputeSpecialRPO();
-  GenerateImmediateDominatorTree();
-
-  PrepareUses();
-  ScheduleEarly();
-  ScheduleLate();
-
-  return schedule_;
+  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()) {
@@ skipping 775 matching lines @@
 // 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() {
+BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) {
+  Zone tmp_zone(schedule->zone()->isolate());
+  Zone* zone = &tmp_zone;
   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, static_cast<int>(schedule_->rpo_order_.size()));
+  CHECK_EQ(kBlockUnvisited1, schedule->entry()->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*, int> > backedges(1, zone_);
+  ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone);
   SpecialRPOStackFrame* stack =
-      zone_->NewArray<SpecialRPOStackFrame>(schedule_->BasicBlockCount());
-  BasicBlock* entry = schedule_->entry();
+      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_);
+            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.
         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);
+      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);
+    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);
+          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_];
         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())) {
           // 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);
+          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);
+          order = order->Add(zone, block);
           block->rpo_number_ = kBlockVisited2;
         }
         stack_depth--;
       }
     }
   }
 
   // Construct the final order from the list.
-  BasicBlockVector* final_order = &schedule_->rpo_order_;
+  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;
@@ skipping 34 matching lines @@
 
 #if DEBUG
   if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
   VerifySpecialRPO(num_loops, loops, final_order);
 #endif
   return final_order;
 }
 }
 }
 }  // namespace v8::internal::compiler