Iterative graph traversal in FlowGraph::DiscoverBlocks()

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
 #include "vm/handles_impl.h"
 #include "vm/locations.h"
 #include "vm/method_recognizer.h"
 #include "vm/object.h"
 #include "vm/parser.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, throw_on_javascript_int_overflow);
 
 class BitVector;
 class BlockEntryInstr;
+class BlockEntryEdge;
 class BoxIntNInstr;
 class BufferFormatter;
 class CatchBlockEntryInstr;
 class ComparisonInstr;
 class Definition;
 class Environment;
 class FlowGraph;
 class FlowGraphBuilder;
 class FlowGraphCompiler;
 class FlowGraphVisitor;
@@ skipping 1097 matching lines @@
     return parallel_move_ != NULL;
   }
 
   ParallelMoveInstr* GetParallelMove() {
     if (parallel_move_ == NULL) {
       parallel_move_ = new ParallelMoveInstr();
     }
     return parallel_move_;
   }
 
-  // Discover basic-block structure by performing a recursive depth first
+  // Discover basic-block structure by performing an iterative depth first
   // traversal of the instruction graph reachable from this instruction.  As
   // a side effect, the block entry instructions in the graph are assigned
-  // numbers in both preorder and postorder.  The array 'preorder' maps
-  // preorder block numbers to the block entry instruction with that number
-  // and analogously for the array 'postorder'.  The depth first spanning
+  // preorder numbers.  The array 'preorder' maps preorder block numbers to
+  // the block entry instruction with that number.  The depth first spanning
   // tree is recorded in the array 'parent', which maps preorder block
   // numbers to the preorder number of the block's spanning-tree parent.
   // The array 'assigned_vars' maps preorder block numbers to the set of
   // assigned frame-allocated local variables in the block.  As a side
   // effect of this function, the set of basic block predecessors (e.g.,
   // block entry instructions of predecessor blocks) and also the last
   // instruction in the block is recorded in each entry instruction.
   void 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);
 
   // Perform a depth first search to prune code not reachable from an OSR
   // entry point.
   bool PruneUnreachable(FlowGraphBuilder* builder,
                         GraphEntryInstr* graph_entry,
                         Instruction* parent,
                         intptr_t osr_id,
                         BitVector* block_marks);
 
   virtual intptr_t InputCount() const { return 0; }
@@ skipping 7241 matching lines @@
       Isolate* isolate, bool opt) const {                                     \
     UNIMPLEMENTED();                                                          \
     return NULL;                                                              \
   }                                                                           \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_