Perform block ordering in-place.

src/hydrogen.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 "hydrogen.h"
 
 #include <algorithm>
 
 #include "v8.h"
 #include "allocation-site-scopes.h"
@@ skipping 61 matching lines @@
       last_environment_(NULL),
       argument_count_(-1),
       first_instruction_index_(-1),
       last_instruction_index_(-1),
       deleted_phis_(4, graph->zone()),
       parent_loop_header_(NULL),
       inlined_entry_block_(NULL),
       is_inline_return_target_(false),
       is_reachable_(true),
       dominates_loop_successors_(false),
-      is_osr_entry_(false) { }
+      is_osr_entry_(false),
+      is_ordered_(false) { }
 
 
 Isolate* HBasicBlock::isolate() const {
   return graph_->isolate();
 }
 
 
 void HBasicBlock::MarkUnreachable() {
   is_reachable_ = false;
 }
@@ skipping 3230 matching lines @@
  public:
   // Back link (towards the stack bottom).
   PostorderProcessor* parent() {return father_; }
   // Forward link (towards the stack top).
   PostorderProcessor* child() {return child_; }
   HBasicBlock* block() { return block_; }
   HLoopInformation* loop() { return loop_; }
   HBasicBlock* loop_header() { return loop_header_; }
 
   static PostorderProcessor* CreateEntryProcessor(Zone* zone,
-                                                  HBasicBlock* block,
-                                                  BitVector* visited) {
+                                                  HBasicBlock* block) {
     PostorderProcessor* result = new(zone) PostorderProcessor(NULL);
-    return result->SetupSuccessors(zone, block, NULL, visited);
+    return result->SetupSuccessors(zone, block, NULL);
   }
 
   PostorderProcessor* PerformStep(Zone* zone,
-                                  BitVector* visited,
                                   ZoneList<HBasicBlock*>* order) {
     PostorderProcessor* next =
-        PerformNonBacktrackingStep(zone, visited, order);
+        PerformNonBacktrackingStep(zone, order);
     if (next != NULL) {
       return next;
     } else {
-      return Backtrack(zone, visited, order);
+      return Backtrack(zone, order);
     }
   }
 
  private:
   explicit PostorderProcessor(PostorderProcessor* father)
       : father_(father), child_(NULL), successor_iterator(NULL) { }
 
   // Each enum value states the cycle whose state is kept by this instance.
   enum LoopKind {
     NONE,
     SUCCESSORS,
     SUCCESSORS_OF_LOOP_HEADER,
     LOOP_MEMBERS,
     SUCCESSORS_OF_LOOP_MEMBER
   };
 
   // Each "Setup..." method is like a constructor for a cycle state.
   PostorderProcessor* SetupSuccessors(Zone* zone,
                                       HBasicBlock* block,
-                                      HBasicBlock* loop_header,
-                                      BitVector* visited) {
-    if (block == NULL || visited->Contains(block->block_id()) ||
+                                      HBasicBlock* loop_header) {
+    if (block == NULL || block->IsOrdered() ||
         block->parent_loop_header() != loop_header) {
       kind_ = NONE;
       block_ = NULL;
       loop_ = NULL;
       loop_header_ = NULL;
       return this;
     } else {
       block_ = block;
       loop_ = NULL;
-      visited->Add(block->block_id());
+      block->MarkAsOrdered();
 
       if (block->IsLoopHeader()) {
         kind_ = SUCCESSORS_OF_LOOP_HEADER;
         loop_header_ = block;
         InitializeSuccessors();
         PostorderProcessor* result = Push(zone);
         return result->SetupLoopMembers(zone, block, block->loop_information(),
                                         loop_header);
       } else {
         ASSERT(block->IsFinished());
@@ skipping 42 matching lines @@
            order->Contains(block_->end()->FirstSuccessor()) ||
            block_->end()->FirstSuccessor()->IsLoopHeader());
     ASSERT(block_->end()->SecondSuccessor() == NULL ||
            order->Contains(block_->end()->SecondSuccessor()) ||
            block_->end()->SecondSuccessor()->IsLoopHeader());
     order->Add(block_, zone);
   }
 
   // This method is the basic block to walk up the stack.
   PostorderProcessor* Pop(Zone* zone,
-                          BitVector* visited,
                           ZoneList<HBasicBlock*>* order) {
     switch (kind_) {
       case SUCCESSORS:
       case SUCCESSORS_OF_LOOP_HEADER:
         ClosePostorder(order, zone);
         return father_;
       case LOOP_MEMBERS:
         return father_;
       case SUCCESSORS_OF_LOOP_MEMBER:
         if (block()->IsLoopHeader() && block() != loop_->loop_header()) {
           // In this case we need to perform a LOOP_MEMBERS cycle so we
           // initialize it and return this instead of father.
           return SetupLoopMembers(zone, block(),
                                   block()->loop_information(), loop_header_);
         } else {
           return father_;
         }
       case NONE:
         return father_;
     }
     UNREACHABLE();
     return NULL;
   }
 
   // Walks up the stack.
   PostorderProcessor* Backtrack(Zone* zone,
-                                BitVector* visited,
                                 ZoneList<HBasicBlock*>* order) {
-    PostorderProcessor* parent = Pop(zone, visited, order);
+    PostorderProcessor* parent = Pop(zone, order);
     while (parent != NULL) {
       PostorderProcessor* next =
-          parent->PerformNonBacktrackingStep(zone, visited, order);
+          parent->PerformNonBacktrackingStep(zone, order);
       if (next != NULL) {
         return next;
       } else {
-        parent = parent->Pop(zone, visited, order);
+        parent = parent->Pop(zone, order);
       }
     }
     return NULL;
   }
 
   PostorderProcessor* PerformNonBacktrackingStep(
       Zone* zone,
-      BitVector* visited,
       ZoneList<HBasicBlock*>* order) {
     HBasicBlock* next_block;
     switch (kind_) {
       case SUCCESSORS:
         next_block = AdvanceSuccessors();
         if (next_block != NULL) {
           PostorderProcessor* result = Push(zone);
-          return result->SetupSuccessors(zone, next_block,
-                                         loop_header_, visited);
+          return result->SetupSuccessors(zone, next_block, loop_header_);
         }
         break;
       case SUCCESSORS_OF_LOOP_HEADER:
         next_block = AdvanceSuccessors();
         if (next_block != NULL) {
           PostorderProcessor* result = Push(zone);
-          return result->SetupSuccessors(zone, next_block,
-                                         block(), visited);
+          return result->SetupSuccessors(zone, next_block, block());
         }
         break;
       case LOOP_MEMBERS:
         next_block = AdvanceLoopMembers();
         if (next_block != NULL) {
           PostorderProcessor* result = Push(zone);
           return result->SetupSuccessorsOfLoopMember(next_block,
                                                      loop_, loop_header_);
         }
         break;
       case SUCCESSORS_OF_LOOP_MEMBER:
         next_block = AdvanceSuccessors();
         if (next_block != NULL) {
           PostorderProcessor* result = Push(zone);
-          return result->SetupSuccessors(zone, next_block,
-                                         loop_header_, visited);
+          return result->SetupSuccessors(zone, next_block, loop_header_);
         }
         break;
       case NONE:
         return NULL;
     }
     return NULL;
   }
 
   // The following two methods implement a "foreach b in successors" cycle.
   void InitializeSuccessors() {
@@ skipping 34 matching lines @@
   HBasicBlock* block_;
   HBasicBlock* loop_header_;
   int loop_index;
   int loop_length;
   HSuccessorIterator successor_iterator;
 };
 
 
 void HGraph::OrderBlocks() {
   CompilationPhase phase("H_Block ordering", info());
-  BitVector visited(blocks_.length(), zone());
 
-  ZoneList<HBasicBlock*> reverse_result(8, zone());
-  HBasicBlock* start = blocks_[0];
+#ifdef DEBUG
+  // Initially the blocks must not be ordered.
+  for (int i = 0; i < blocks_.length(); ++i) {
+    ASSERT(!blocks_[i]->IsOrdered());
+  }
+#endif
+
   PostorderProcessor* postorder =
-      PostorderProcessor::CreateEntryProcessor(zone(), start, &visited);
-  while (postorder != NULL) {
-    postorder = postorder->PerformStep(zone(), &visited, &reverse_result);
+      PostorderProcessor::CreateEntryProcessor(zone(), blocks_[0]);
+  blocks_.Rewind(0);
+  while (postorder) {
+    postorder = postorder->PerformStep(zone(), &blocks_);
   }
-  blocks_.Rewind(0);
-  int index = 0;
-  for (int i = reverse_result.length() - 1; i >= 0; --i) {
-    HBasicBlock* b = reverse_result[i];
-    blocks_.Add(b, zone());
-    b->set_block_id(index++);
+
+#ifdef DEBUG
+  // Now all blocks must be marked as ordered.
+  for (int i = 0; i < blocks_.length(); ++i) {
+    ASSERT(blocks_[i]->IsOrdered());
+  }
+#endif
+
+  // Reverse block list and assign block IDs.
+  for (int i = 0, j = blocks_.length(); --j >= i; ++i) {
+    HBasicBlock* bi = blocks_[i];
+    HBasicBlock* bj = blocks_[j];
+    bi->set_block_id(j);
+    bj->set_block_id(i);
+    blocks_[i] = bj;
+    blocks_[j] = bi;
   }
 }
 
 
 void HGraph::AssignDominators() {
   HPhase phase("H_Assign dominators", this);
   for (int i = 0; i < blocks_.length(); ++i) {
     HBasicBlock* block = blocks_[i];
     if (block->IsLoopHeader()) {
       // Only the first predecessor of a loop header is from outside the loop.
@@ skipping 8205 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal