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 131 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 block entry wrapper including an index of the next successor to be read.
+class PostorderBlockEntryWrapper {
+ public:
+  explicit PostorderBlockEntryWrapper(BlockEntryInstr* block)
+    : block_(block),
+      next_successor_ix_(block->last_instruction()->SuccessorCount() - 1) { }
+
+  bool HasNextSuccessor() const { return next_successor_ix_ >= 0; }
+  BlockEntryInstr* NextSuccessor() {
+    return block_->last_instruction()->SuccessorAt(next_successor_ix_--);
+  }
+
+  BlockEntryInstr* block() const { return block_; }
+
+ private:
+  BlockEntryInstr* block_;
+  intptr_t next_successor_ix_;
+
+  DISALLOW_ALLOCATION();
+};
+
+
+// Iterative graph postorder traversal. DiscoverBlocks() must have been called
+// before this in order to set up BlockEntryInstr::last_instruction().
+static void BuildPostorder(Isolate* isolate,
+                           BlockEntryInstr* graph_entry,
+                           GrowableArray<BlockEntryInstr*>* postorder,
+                           intptr_t num_blocks) {
+  GrowableArray<PostorderBlockEntryWrapper> block_stack;
+  block_stack.Add(PostorderBlockEntryWrapper(graph_entry));
+
+  BitVector visited(isolate, num_blocks);
+  while (!block_stack.is_empty()) {
+    PostorderBlockEntryWrapper &last = block_stack.Last();
+    BlockEntryInstr* block = last.block();
+    visited.Add(block->preorder_number());
+    if (last.HasNextSuccessor()) {
+      // Process successors one-by-one.
+      BlockEntryInstr* succ = last.NextSuccessor();
+      if (!visited.Contains(succ->preorder_number())) {
+        block_stack.Add(PostorderBlockEntryWrapper(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);
+    }
+  }
+}
+
+
 void FlowGraph::DiscoverBlocks() {
   // 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.
+
+  // Perform an iterative depth-first traversal of the graph to build preorder
+  // block order, spanning-tree parents, and predecessors for each block entry.
+  GrowableArray<BlockEntryEdge> block_stack;

[Vyacheslav Egorov (Google), 2014/10/07 12:43:17]

I would really like to have this block_stack die after DiscoverBlock(). 

We run DiscoverBlocks multiple times during the optimization phase and if this
stack is big - I don't want it to polute the Zone. 

Maybe we could have a StackZone above it?

[jgruber1, 2014/10/08 15:11:29]

Done. I didn't realize the array memory sticks around since the array is
allocated on the stack, but it's obvious in hindsight.

+  block_stack.Add(BlockEntryEdge(NULL, graph_entry()));
+  while (!block_stack.is_empty()) {
+    BlockEntryEdge pair = block_stack.RemoveLast();
+    pair.child->DiscoverBlocks(pair.parent,
                                &preorder_,
-                               &postorder_,
                                &parent_,
-                               variable_count(),
-                               num_non_copied_params());
+                               &block_stack);
+  }
+
+  // Create an array of blocks in postorder.
+  const intptr_t block_count = preorder_.length();

[Vyacheslav Egorov (Google), 2014/10/07 12:43:17]

Maybe I am missing something but I think you can build both orders with one
loop. 

class State {
  final block;
  int idx;

  State(this.block) : succ = 0;
}

visit(block) {
  // 0. if block already has preorder number return false
  // 1. assign preoder number
  // 2. find last instruction
  // 3. return true
}

discover() {
  final stack = [new State(entry)];
  visit(stack.last);
  while (!stack.isEmpty) {
    final state = stack.last;
    if (state.idx < state.block.successors.length) {
      final succ = state.block.successors[state.idx++];
      if (visit(succ)) {
        if (!state.block.successors.isEmpty) {
          stack.add(new State(succ));
        } else {
          // assign post order number to succ.
        }
      }
    } else {
      // assign post order number to state.block
      stack.removeLast();
    }
  }
}

You can even combine recursion and iteration (e.g. do recursion and then switch
to iteration when reaching certain depth). 

[jgruber1, 2014/10/08 15:11:29]

Good point, done.

+  BuildPostorder(isolate(), graph_entry(), &postorder_, block_count);
+  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 1077 matching lines @@
 }
 
 
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
 }  // namespace dart