Iterative graph traversal in FlowGraph::DiscoverBlocks()

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, 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/flow_graph.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/growable_array.h"
@@ skipping 132 matching lines @@
   if (use_kind == kValue) {
     ASSERT(instr->IsDefinition());
     AllocateSSAIndexes(instr->AsDefinition());
   }
   ASSERT(instr->env() == NULL);
   if (env != NULL) env->DeepCopyTo(isolate(), instr);
   return prev->AppendInstruction(instr);
 }
 
 
+// A wrapper around block entries including an index of the next successor to
+// be read.
+class BlockTraversalState {
+ public:
+  explicit BlockTraversalState(BlockEntryInstr* block)
+    : block_(block),
+      next_successor_ix_(block->last_instruction()->SuccessorCount() - 1) { }
+
+  bool HasNextSuccessor() const { return next_successor_ix_ >= 0; }
+  BlockEntryInstr* NextSuccessor() {
+    ASSERT(HasNextSuccessor());
+    return block_->last_instruction()->SuccessorAt(next_successor_ix_--);
+  }
+
+  BlockEntryInstr* block() const { return block_; }
+
+ private:
+  BlockEntryInstr* block_;
+  intptr_t next_successor_ix_;
+
+  DISALLOW_ALLOCATION();
+};
+
+
 void FlowGraph::DiscoverBlocks() {
+  StackZone zone(isolate());
+
   // Initialize state.
   preorder_.Clear();
   postorder_.Clear();
   reverse_postorder_.Clear();
   parent_.Clear();
-  // Perform a depth-first traversal of the graph to build preorder and
-  // postorder block orders.
-  graph_entry_->DiscoverBlocks(NULL,  // Entry block predecessor.
-                               &preorder_,
-                               &postorder_,
-                               &parent_,
-                               variable_count(),
-                               num_non_copied_params());
+
+  GrowableArray<BlockTraversalState> block_stack;
+  graph_entry()->DiscoverBlock(NULL, &preorder_, &parent_);
+  block_stack.Add(BlockTraversalState(graph_entry_));

[zerny-google, 2014/10/09 09:53:32]

Nit: consistent use of graph_entry()/graph_entry_

[jgruber1, 2014/10/09 14:08:36]

Done.

+  while (!block_stack.is_empty()) {
+    BlockTraversalState &state = block_stack.Last();
+    BlockEntryInstr* block = state.block();
+    if (state.HasNextSuccessor()) {
+      // Process successors one-by-one.
+      BlockEntryInstr* succ = state.NextSuccessor();
+      if (succ->DiscoverBlock(block, &preorder_, &parent_)) {
+        block_stack.Add(BlockTraversalState(succ));
+      }
+    } else {
+      // All successors have been processed, pop the current block entry node
+      // and add it to the postorder list.
+      block_stack.RemoveLast();
+      block->set_postorder_number(postorder_.length());
+      postorder_.Add(block);
+    }
+  }
+
+  ASSERT(postorder_.length() == preorder_.length());
+
   // Create an array of blocks in reverse postorder.
   intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; ++i) {
     reverse_postorder_.Add(postorder_[block_count - i - 1]);
   }
 
   // Block effects are using postorder numbering. Discard computed information.
   block_effects_ = NULL;
   loop_headers_ = NULL;
   loop_invariant_loads_ = NULL;
@@ skipping 1079 matching lines @@
 }
 
 
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
 }  // namespace dart