Move linked list for RPO order into BasicBlock itself.

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 518 matching lines @@
 //    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 ZoneObject {
  public:
   SpecialRPONumberer(Zone* zone, Schedule* schedule)
       : zone_(zone),
         schedule_(schedule),
         order_(NULL),
+        beyond_end_(NULL),
         loops_(zone),
-        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(schedule_->end()->SuccessorCount() == 0);
     DCHECK_EQ(NULL, order_);  // Main order does not exist yet.
     ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end());
   }
 
   // Computes the special reverse-post-order for a partial control flow graph,
   // that is for the graph spanned between the given {entry} and {end} blocks,
   // then updates the existing ordering with this new information.
   void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) {
     DCHECK_NE(NULL, order_);  // Main order to be updated is present.
     ComputeAndInsertSpecialRPO(entry, end);
   }
 
   // Serialize the previously computed order as an assembly order (non-deferred
   // code first, deferred code afterwards) into the final schedule.
   void SerializeAOIntoSchedule() {
     int32_t number = 0;
-    for (BlockList* l = order_; l != NULL; l = l->next) {
-      if (l->block->deferred()) continue;
-      l->block->set_ao_number(number++);
+    for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) {
+      if (b->deferred()) continue;
+      b->set_ao_number(number++);
     }
-    for (BlockList* l = order_; l != NULL; l = l->next) {
-      if (!l->block->deferred()) continue;
-      l->block->set_ao_number(number++);
+    for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) {
+      if (!b->deferred()) continue;
+      b->set_ao_number(number++);
     }
   }
 
   // Serialize the previously computed order as a special reverse-post-order
   // numbering for basic blocks into the final schedule.
   void SerializeRPOIntoSchedule() {
     int32_t number = 0;
-    for (BlockList* l = order_; l != NULL; l = l->next) {
-      l->block->set_rpo_number(number++);
-      schedule_->rpo_order()->push_back(l->block);
+    for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) {
+      b->set_rpo_number(number++);
+      schedule_->rpo_order()->push_back(b);
     }
     BeyondEndSentinel()->set_rpo_number(number);
   }
 
   // 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;
 
   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;
-    }
-
-    BlockList* FindForBlock(BasicBlock* b) {
-      for (BlockList* l = this; l != NULL; l = l->next) {
-        if (l->block == b) return l;
-      }
-      return NULL;
-    }
-  };
-
   struct LoopInfo {
     BasicBlock* header;
     ZoneList<BasicBlock*>* outgoing;
     BitVector* members;
     LoopInfo* prev;
-    BlockList* end;
-    BlockList* start;
+    BasicBlock* end;
+    BasicBlock* start;
 
     void AddOutgoing(Zone* zone, BasicBlock* block) {
       if (outgoing == NULL) {
         outgoing = new (zone) ZoneList<BasicBlock*>(2, zone);
       }
       outgoing->Add(block, zone);
     }
   };
 
   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;
   }
 
+  BasicBlock* PushFront(BasicBlock* head, BasicBlock* block) {
+    block->set_rpo_next(head);
+    return block;
+  }
+
   // We are hijacking the {ao_number} to enumerate loops temporarily. Note that
   // these numbers are only valid within this class.
   static int GetLoopNumber(BasicBlock* block) { return block->ao_number(); }
   static void SetLoopNumber(BasicBlock* block, int loop_number) {
     return block->set_ao_number(loop_number);
   }
   static bool HasLoopNumber(BasicBlock* block) {
     return block->ao_number() >= 0;
   }
 
@@ skipping 10 matching lines @@
 
   // Compute special RPO for the control flow graph between {entry} and {end},
   // 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_before = order_->FindForBlock(entry);
-    BlockList* insert_after = insert_before ? insert_before->next : NULL;
-    BlockList* order = insert_after;
+    BasicBlock* insertion_point = entry->rpo_next();
+    BasicBlock* order = insertion_point;
 
     // Perform an iterative RPO traversal using an explicit stack,
     // recording backedges that form cycles. O(|B|).
     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 = static_cast<int>(loops_.size());
 
     while (stack_depth > 0) {
@@ skipping 12 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.
-        order = order->Add(zone_, frame->block);
+        order = PushFront(order, 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 > static_cast<int>(loops_.size())) {
       // 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 = insert_after;
+      order = insertion_point;
 
       // 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 (block != end && 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);
+            loop->start = PushFront(order, 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.
@@ skipping 27 matching lines @@
               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;
+            for (BasicBlock* b = info->start; true; b = b->rpo_next()) {
+              if (b->rpo_next() == info->end) {
+                b->set_rpo_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 = PushFront(order, block);
             block->set_rpo_number(kBlockVisited2);
           }
           stack_depth--;
         }
       }
     }
 
-    // Insert result into existing order.
-    if (insert_before == NULL) {
-      order_ = order;
-    } else {
-      // There already is a list element for the entry block in the list, hence
-      // we skip the first element of the sub-list to compensate duplication.
-      DCHECK_EQ(insert_before->block, order->block);
-      insert_before->next = order->next;
-    }
+    // Publish new order the first time.
+    if (order_ == NULL) order_ = order;
 
     // Compute the correct loop headers and set the correct loop ends.
     LoopInfo* current_loop = NULL;
     BasicBlock* current_header = entry->loop_header();
     int32_t loop_depth = entry->loop_depth();
     if (entry->IsLoopHeader()) --loop_depth;  // Entry might be a loop header.
-    for (BlockList* l = order; l != insert_after; l = l->next) {
-      BasicBlock* current = l->block;
+    for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) {
+      BasicBlock* current = b;
 
       // Reset BasicBlock::rpo_number again.
       current->set_rpo_number(kBlockUnvisited1);
 
       // 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);
 
       // Push a new loop onto the stack if this loop is a loop header.
       if (HasLoopNumber(current)) {
         ++loop_depth;
         current_loop = &loops_[GetLoopNumber(current)];
-        BlockList* end = current_loop->end;
-        current->set_loop_end(end == NULL ? BeyondEndSentinel() : end->block);
+        BasicBlock* end = current_loop->end;
+        current->set_loop_end(end == NULL ? BeyondEndSentinel() : end);
         current_header = current_loop->header;
         Trace("B%d is a loop header, increment loop depth to %d\n",
               current->id().ToInt(), 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());
@@ skipping 64 matching lines @@
     if (loops_.size() > 0) {
       os << " (";
       for (size_t i = 0; i < loops_.size(); i++) {
         if (i > 0) os << " ";
         os << "B" << loops_[i].header->id();
       }
       os << ")";
     }
     os << ":\n";
 
-    for (BlockList* l = order_; l != NULL; l = l->next) {
-      BasicBlock* block = l->block;
+    for (BasicBlock* block = order_; block != NULL; block = block->rpo_next()) {
       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:", x) here).
       os << "  " << block->rpo_number() << ":";
       for (size_t i = 0; i < loops_.size(); i++) {
         bool range = loops_[i].header->LoopContains(block);
         bool membership = loops_[i].header != block && range;
         os << (membership ? " |" : "  ");
         os << (range ? "x" : " ");
       }
@@ skipping 25 matching lines @@
       DCHECK(header != NULL);
       DCHECK(header->rpo_number() >= 0);
       DCHECK(header->rpo_number() < static_cast<int>(order->size()));
       DCHECK(end != NULL);
       DCHECK(end->rpo_number() <= static_cast<int>(order->size()));
       DCHECK(end->rpo_number() > header->rpo_number());
       DCHECK(header->loop_header() != header);
 
       // Verify the start ... end list relationship.
       int links = 0;
-      BlockList* l = loop->start;
-      DCHECK(l != NULL && l->block == header);
+      BasicBlock* block = loop->start;
+      DCHECK_EQ(header, block);
       bool end_found;
       while (true) {
-        if (l == NULL || l == loop->end) {
-          end_found = (loop->end == l);
+        if (block == NULL || block == loop->end) {
+          end_found = (loop->end == block);
           break;
         }
         // The list should be in same order as the final result.
-        DCHECK(l->block->rpo_number() == links + header->rpo_number());
+        DCHECK(block->rpo_number() == links + header->rpo_number());
         links++;
-        l = l->next;
+        block = block->rpo_next();
         DCHECK(links < static_cast<int>(2 * order->size()));  // cycle?
       }
       DCHECK(links > 0);
       DCHECK(links == end->rpo_number() - header->rpo_number());
       DCHECK(end_found);
 
       // Check loop depth of the header.
       int loop_depth = 0;
       for (LoopInfo* outer = loop; outer != NULL; outer = outer->prev) {
         loop_depth++;
@@ skipping 13 matching lines @@
           count++;
         }
       }
       DCHECK(links == count);
     }
   }
 #endif  // DEBUG
 
   Zone* zone_;
   Schedule* schedule_;
-  BlockList* order_;
+  BasicBlock* order_;
+  BasicBlock* beyond_end_;
   ZoneVector<LoopInfo> loops_;
-  BasicBlock* beyond_end_;
   ZoneList<Backedge> backedges_;
   ZoneVector<SpecialRPOStackFrame> stack_;
   size_t previous_block_count_;
 };
 
 
 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
   SpecialRPONumberer numberer(zone, schedule);
   numberer.ComputeSpecialRPO();
   numberer.SerializeAOIntoSchedule();
@@ skipping 12 matching lines @@
 }
 
 
 void Scheduler::GenerateImmediateDominatorTree() {
   Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
 
   // TODO(danno): Consider using Lengauer & Tarjan's if this becomes too slow.
 
   // Build the block dominator tree.
   schedule_->start()->set_dominator_depth(0);
-  typedef SpecialRPONumberer::BlockList BlockList;
-  DCHECK_EQ(schedule_->start(), special_rpo_->order_->block);
-  for (BlockList* l = special_rpo_->order_->next; l != NULL; l = l->next) {
-    BasicBlock* current = l->block;
-    BasicBlock::Predecessors::iterator pred = current->predecessors_begin();
-    BasicBlock::Predecessors::iterator end = current->predecessors_end();
+  BasicBlock* second = schedule_->start()->rpo_next();
+  for (BasicBlock* block = second; block != NULL; block = block->rpo_next()) {
+    BasicBlock::Predecessors::iterator pred = block->predecessors_begin();
+    BasicBlock::Predecessors::iterator end = block->predecessors_end();
     DCHECK(pred != end);  // All blocks except start have predecessors.
     BasicBlock* dominator = *pred;
     // For multiple predecessors, walk up the dominator tree until a common
     // dominator is found. Visitation order guarantees that all predecessors
     // except for backwards edges have been visited.
     for (++pred; pred != end; ++pred) {
       // Don't examine backwards edges.
       if ((*pred)->dominator_depth() < 0) continue;
       dominator = GetCommonDominator(dominator, *pred);
     }
-    current->set_dominator(dominator);
-    current->set_dominator_depth(dominator->dominator_depth() + 1);
+    block->set_dominator(dominator);
+    block->set_dominator_depth(dominator->dominator_depth() + 1);
     // Propagate "deferredness" of the dominator.
-    if (dominator->deferred()) current->set_deferred(true);
-    Trace("Block B%d's idom is B%d, depth = %d\n", current->id().ToInt(),
-          dominator->id().ToInt(), current->dominator_depth());
+    if (dominator->deferred()) block->set_deferred(true);
+    Trace("Block B%d's idom is B%d, depth = %d\n", block->id().ToInt(),
+          dominator->id().ToInt(), block->dominator_depth());
   }
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 3: Prepare use counts for nodes.
 
 
 class PrepareUsesVisitor : public NullNodeVisitor {
  public:
@@ skipping 405 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