Reuse RPO traversal stack in the scheduler.

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/bit-vector.h"
@@ skipping 509 matching lines @@
 // 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 ZoneObject {
  public:
   SpecialRPONumberer(Zone* zone, Schedule* schedule)
       : zone_(zone),
         schedule_(schedule),
         order_(NULL),
         loops_(zone),
-        beyond_end_(NULL) {}
+        beyond_end_(NULL),
+        backedges_(1, zone),
+        stack_(zone),
+        previous_block_count_(0) {}
 
   // Computes the special reverse-post-order for the main control flow graph,
   // that is for the graph spanned between the schedule's start and end blocks.
   void ComputeSpecialRPO() {
     DCHECK_EQ(NULL, order_);  // Main order does not exist yet.
     // TODO(mstarzinger): Should use Schedule::end() after tests are fixed.
     ComputeAndInsertSpecialRPO(schedule_->start(), NULL);
   }
 
   // Computes the special reverse-post-order for a partial control flow graph,
@@ skipping 31 matching lines @@
 
   // Print and verify the special reverse-post-order.
   void PrintAndVerifySpecialRPO() {
 #if DEBUG
     if (FLAG_trace_turbo_scheduler) PrintRPO();
     VerifySpecialRPO();
 #endif
   }
 
  private:
+  typedef std::pair<BasicBlock*, size_t> Backedge;
+
   // TODO(mstarzinger): Only for Scheduler::GenerateImmediateDominatorTree.
   friend class Scheduler;
 
   // Numbering for BasicBlock::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;
 
@@ skipping 30 matching lines @@
     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) {
+  int Push(ZoneVector<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;
   }
 
   // We are hijacking the {ao_number} to enumerate loops temporarily. Note that
@@ skipping 25 matching lines @@
     CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
     CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));
 
     // Find correct insertion point within existing order.
     BlockList* insert_before = order_->FindForBlock(entry);
     BlockList* insert_after = insert_before ? insert_before->next : NULL;
     BlockList* order = insert_after;
 
     // 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()));
-    int stack_depth = Push(stack, 0, entry, kBlockUnvisited1);
+    DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount());
+    stack_.resize(schedule_->BasicBlockCount() - previous_block_count_);
+    previous_block_count_ = schedule_->BasicBlockCount();
+    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;
+      SpecialRPOStackFrame* frame = &stack_[current];
 
       if (frame->block != end &&
           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_);
+          backedges_.Add(Backedge(frame->block, frame->index - 1), zone_);
           if (!HasLoopNumber(succ)) {
             // Assign a new loop number to the header if it doesn't have one.
             SetLoopNumber(succ, num_loops++);
           }
         } else {
           // Push the successor onto the stack.
           DCHECK(succ->rpo_number() == kBlockUnvisited1);
-          stack_depth = Push(stack, stack_depth, succ, 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.
     if (num_loops != 0) {
       // Otherwise, compute the loop information from the backedges in order
       // to perform a traversal that groups loop bodies together.
-      ComputeLoopInfo(stack, num_loops, &backedges);
+      ComputeLoopInfo(stack_, num_loops, &backedges_);
 
       // Initialize the "loop stack". Note the entry could be a loop header.
       LoopInfo* loop =
           HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : 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);
+      stack_depth = Push(stack_, 0, entry, kBlockUnvisited2);
       while (stack_depth > 0) {
-        SpecialRPOStackFrame* frame = stack + (stack_depth - 1);
+        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 (HasLoopNumber(block)) {
           // 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
@@ skipping 25 matching lines @@
           // 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);
+            stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2);
             if (HasLoopNumber(succ)) {
               // Push the inner loop onto the loop stack.
               DCHECK(GetLoopNumber(succ) < num_loops);
               LoopInfo* next = &loops_[GetLoopNumber(succ)];
               next->end = order;
               next->prev = loop;
               loop = next;
             }
           }
         } else {
@@ skipping 67 matching lines @@
         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());
       }
     }
   }
 
   // Computes loop membership from the backedges of the control flow graph.
-  void ComputeLoopInfo(SpecialRPOStackFrame* queue, size_t num_loops,
-                       ZoneList<std::pair<BasicBlock*, size_t> >* backedges) {
+  void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue,
+                       size_t num_loops, ZoneList<Backedge>* backedges) {
     loops_.resize(num_loops, 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);
       size_t loop_num = GetLoopNumber(header);
       if (loops_[loop_num].header == NULL) {
         loops_[loop_num].header = header;
@@ skipping 130 matching lines @@
       DCHECK(links == count);
     }
   }
 #endif  // DEBUG
 
   Zone* zone_;
   Schedule* schedule_;
   BlockList* order_;
   ZoneVector<LoopInfo> loops_;
   BasicBlock* beyond_end_;
+  ZoneList<Backedge> backedges_;
+  ZoneVector<SpecialRPOStackFrame> stack_;
+  size_t previous_block_count_;
 };
 
 
 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();
@@ skipping 439 matching lines @@
   for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
     schedule_->SetBlockForNode(to, *i);
     scheduled_nodes_[to->id().ToSize()].push_back(*i);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8