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 845 matching lines @@
   // Detect that a block has been visited as part of the current
   // DiscoverBlocks (we can call DiscoverBlocks multiple times).  The block
   // will be 'marked' by (1) having a preorder number in the range of the
   // 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(
+bool BlockEntryInstr::DiscoverBlock(
     BlockEntryInstr* predecessor,
     GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<BlockEntryInstr*>* postorder,
-    GrowableArray<intptr_t>* parent,
-    intptr_t variable_count,
-    intptr_t fixed_parameter_count) {
+    GrowableArray<intptr_t>* parent) {
   // 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);
     AddPredecessor(predecessor);
-    return;
+    return false;
   }
 
   // 2. Otherwise, clear the predecessors which might have been computed on
   // some earlier call to DiscoverBlocks and record this predecessor.
   ClearPredecessors();
   if (predecessor != NULL) AddPredecessor(predecessor);
 
   // 3. The predecessor is the spanning-tree parent.  The graph entry has no
   // parent, indicated by -1.
   intptr_t parent_number =
@@ skipping 11 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.
-  for (intptr_t i = last->SuccessorCount() - 1; i >= 0; --i) {
-    last->SuccessorAt(i)->DiscoverBlocks(this,
-                                         preorder,
-                                         postorder,
-                                         parent,
-                                         variable_count,
-                                         fixed_parameter_count);
-  }
-
-  // 6. Assign postorder number and add the block entry to the list.
-  set_postorder_number(postorder->length());
-  postorder->Add(this);
+  return true;
 }
 
 
 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 2432 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart