Avoid redundant work in scheduler loop header/depth calculation.

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 566 matching lines @@
 #if DEBUG
     if (FLAG_trace_turbo_scheduler) PrintRPO();
     VerifySpecialRPO();
 #endif
   }
 
  private:
   // TODO(mstarzinger): Only for Scheduler::GenerateImmediateDominatorTree.
   friend class Scheduler;
 
-  // Numbering for BasicBlockData.rpo_number_ for this block traversal:
+  // 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;
 
   struct SpecialRPOStackFrame {
     BasicBlock* block;
     size_t index;
   };
@@ skipping 69 matching lines @@
   // mutating any existing order so that the result is still valid.
   void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) {
     // RPO should not have been serialized for this schedule yet.
     CHECK_EQ(kBlockUnvisited1, schedule_->start()->ao_number());
     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_head = order_->FindForBlock(entry);
     BlockList* insert_tail = insert_head == NULL ? NULL : insert_head->next;
+    BlockList* order = insert_tail;
 
     // 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);
     int num_loops = 0;
 
     while (stack_depth > 0) {
@@ skipping 14 matching lines @@
             // 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);
         }
       } else {
         // Finished with all successors; pop the stack and add the block.
-        insert_tail = insert_tail->Add(zone_, frame->block);
+        order = order->Add(zone_, frame->block);
         frame->block->set_rpo_number(kBlockVisited1);
         stack_depth--;
       }
     }
 
-    // Insert the result into any existing order.
-    if (insert_head == NULL) {
-      order_ = insert_tail;
-    } else {
-      insert_head->next = insert_tail->next;
-    }
-
     // 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);
 
       // Initialize the "loop stack". Note the entry could be a loop header.
       LoopInfo* loop =
           HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : NULL;
-      order_ = 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 (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
             // stack.
             DCHECK(loop != NULL && loop->header == block);
-            loop->start = order_->Add(zone_, block);
-            order_ = loop->end;
+            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 =
@@ skipping 16 matching lines @@
             // 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 (HasLoopNumber(succ)) {
               // Push the inner loop onto the loop stack.
               DCHECK(GetLoopNumber(succ) < num_loops);
               LoopInfo* next = &loops_[GetLoopNumber(succ)];
-              next->end = order_;
+              next->end = order;
               next->prev = loop;
               loop = next;
             }
           }
         } else {
           // Finished with all successors of the current block.
           if (HasLoopNumber(block)) {
             // If we are going to pop a loop header, then add its entire body.
             LoopInfo* info = &loops_[GetLoopNumber(block)];
             for (BlockList* l = info->start; true; l = l->next) {
               if (l->next == info->end) {
-                l->next = order_;
-                info->end = order_;
+                l->next = order;
+                info->end = order;
                 break;
               }
             }
-            order_ = info->start;
+            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->set_rpo_number(kBlockVisited2);
           }
           stack_depth--;
         }
       }
     }
 
+    // Insert result into existing order.
+    if (insert_head == NULL) {
+      order_ = order;
+    } else {
+      insert_head->next = order->next;
+    }
+
     // Compute the correct loop headers and set the correct loop ends.
     LoopInfo* current_loop = NULL;
-    BasicBlock* current_header = NULL;
-    int loop_depth = 0;
-    for (BlockList* l = order_; l != NULL; l = l->next) {
+    BasicBlock* current_header = entry->loop_header();
+    int32_t loop_depth = entry->loop_depth();
+    for (BlockList* l = order; l != insert_tail; l = l->next) {
       BasicBlock* current = l->block;
 
+      // Reset BasicBlock::rpo_number again.
+      current->set_rpo_number(-1);

[Jarin, 2014/11/05 01:03:56]

Could we use the constant defined above? (kBlockUnvisited1)

[Michael Starzinger, 2014/11/05 10:18:40]

Done.

+
       // Finish the previous loop(s) if we just exited them.
       while (current_header != NULL && current == 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_header(current_header);
 
@@ skipping 586 matching lines @@
   if (FLAG_trace_turbo_scheduler) {
     OFStream os(stdout);
     os << "Schedule before control flow fusion:\n" << *schedule_;
   }
 
   // Iterate on phase 1: Build control-flow graph.
   CFGBuilder cfg_builder(zone_, this);
   cfg_builder.Run(block, node);
 
   // Iterate on phase 2: Compute special RPO and dominator tree.
+  special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
   // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
   for (BasicBlock* block : schedule_->all_blocks_) {
-    block->set_rpo_number(-1);
     block->set_dominator_depth(-1);
     block->set_dominator(NULL);
   }
-  special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
   GenerateImmediateDominatorTree();
 
   // Move previously planned nodes.
   // TODO(mstarzinger): Improve that by supporting bulk moves.
   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
   MovePlannedNodes(block, schedule_->block(node));
 
   if (FLAG_trace_turbo_scheduler) {
     OFStream os(stdout);
     os << "Schedule after control flow fusion:\n" << *schedule_;
   }
 }
 
 
 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
   Trace("Move planned nodes from B%d to B%d\n", from->id().ToInt(),
         to->id().ToInt());
   NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]);
   for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
     schedule_->SetBlockForNode(to, *i);
     scheduled_nodes_[to->id().ToSize()].push_back(*i);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8