Iterative graph traversal in FlowGraph::DiscoverBlocks()

runtime/vm/intermediate_language.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
@@ skipping 820 matching lines @@
   // preorder array and (2) being in the preorder array at that index.
   intptr_t i = block->preorder_number();
   return (i >= 0) && (i < preorder->length()) && ((*preorder)[i] == block);
 }
 
 
 // Base class implementation used for JoinEntry and TargetEntry.
 void BlockEntryInstr::DiscoverBlocks(
     BlockEntryInstr* predecessor,
     GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<BlockEntryInstr*>* postorder,
     GrowableArray<intptr_t>* parent,
-    intptr_t variable_count,
-    intptr_t fixed_parameter_count) {
+    GrowableArray<BlockEntryEdge>* block_stack) {
   // If this block has a predecessor (i.e., is not the graph entry) we can
   // assume the preorder array is non-empty.
   ASSERT((predecessor == NULL) || !preorder->is_empty());
   // Blocks with a single predecessor cannot have been reached before.
   ASSERT(IsJoinEntry() || !IsMarked(this, preorder));
 
   // 1. If the block has already been reached, add current_block as a
   // basic-block predecessor and we are done.
   if (IsMarked(this, preorder)) {
     ASSERT(predecessor != NULL);
@@ skipping 23 matching lines @@
   // 5. Iterate straight-line successors to record assigned variables and
   // find the last instruction in the block.  The graph entry block consists
   // of only the entry instruction, so that is the last instruction in the
   // block.
   Instruction* last = this;
   for (ForwardInstructionIterator it(this); !it.Done(); it.Advance()) {
     last = it.Current();
   }
   set_last_instruction(last);
 
-  // Visit the block's successors in reverse so that they appear forwards
-  // the reverse postorder block ordering.
+  // Push the block's successors in reverse so that they are visited from left
+  // to right.
   for (intptr_t i = last->SuccessorCount() - 1; i >= 0; --i) {
-    last->SuccessorAt(i)->DiscoverBlocks(this,
-                                         preorder,
-                                         postorder,
-                                         parent,
-                                         variable_count,
-                                         fixed_parameter_count);
+    block_stack->Add(BlockEntryEdge(this, last->SuccessorAt(i)));
   }
-
-  // 6. Assign postorder number and add the block entry to the list.
-  set_postorder_number(postorder->length());
-  postorder->Add(this);
 }
 
 
 bool BlockEntryInstr::PruneUnreachable(FlowGraphBuilder* builder,
                                        GraphEntryInstr* graph_entry,
                                        Instruction* parent,
                                        intptr_t osr_id,
                                        BitVector* block_marks) {
   // Search for the instruction with the OSR id.  Use a depth first search
   // because basic blocks have not been discovered yet.  Prune unreachable
@@ skipping 2408 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart