Simplify basic block discovery -- handle all blcoks uniformly.

runtime/vm/intermediate_language.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/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 684 matching lines @@
                      GrowableArray<BlockEntryInstr*>* preorder) {
   // 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);
 }
 
 
-void GraphEntryInstr::DiscoverBlocks(
-    BlockEntryInstr* current_block,
+// Base class implementation used for JoinEntry and TargetEntry.
+void BlockEntryInstr::DiscoverBlocks(
+    BlockEntryInstr* predecessor,
     GrowableArray<BlockEntryInstr*>* preorder,
     GrowableArray<BlockEntryInstr*>* postorder,
     GrowableArray<intptr_t>* parent,
     GrowableArray<BitVector*>* assigned_vars,
     intptr_t variable_count,
     intptr_t fixed_parameter_count) {
-  // We only visit this block once, first of all blocks.
-  ASSERT(!IsMarked(this, preorder));
-  ASSERT(current_block == NULL);
-  ASSERT(preorder->is_empty());
-  ASSERT(postorder->is_empty());
-  ASSERT(parent->is_empty());
-
-  // This node has no parent, indicated by -1.  The preorder number is 0.
-  parent->Add(-1);
-  set_preorder_number(0);
-  preorder->Add(this);
-  BitVector* vars =
-      (variable_count == 0) ? NULL : new BitVector(variable_count);
-  assigned_vars->Add(vars);
-
-  // The graph entry consists of only one instruction.
-  set_last_instruction(this);
-
-  // Iteratively traverse all successors.  In the unoptimized code, we will
-  // enter the function at the first successor in reverse postorder, so we
-  // must visit the normal entry last.
-  for (intptr_t i = catch_entries_.length() - 1; i >= 0; --i) {
-    catch_entries_[i]->DiscoverBlocks(this, preorder, postorder,
-                                      parent, assigned_vars,
-                                      variable_count, fixed_parameter_count);
-  }
-  normal_entry_->DiscoverBlocks(this, preorder, postorder,
-                                parent, assigned_vars,
-                                variable_count, fixed_parameter_count);
-
-  // Assign postorder number.
-  set_postorder_number(postorder->length());
-  postorder->Add(this);
-}
-
-
-// Base class implementation used for JoinEntry and TargetEntry.
-void BlockEntryInstr::DiscoverBlocks(
-    BlockEntryInstr* current_block,
-    GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<BlockEntryInstr*>* postorder,
-    GrowableArray<intptr_t>* parent,
-    GrowableArray<BitVector*>* assigned_vars,
-    intptr_t variable_count,
-    intptr_t fixed_parameter_count) {
-  // We have already visited the graph entry, so we can assume current_block
-  // is non-null and preorder array is non-empty.
-  ASSERT(current_block != NULL);
-  ASSERT(!preorder->is_empty());
+  // 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(!IsTargetEntry() || !IsMarked(this, preorder));
+  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)) {
-    AddPredecessor(current_block);
+    ASSERT(predecessor != NULL);
+    AddPredecessor(predecessor);
     return;
   }
 
   // 2. Otherwise, clear the predecessors which might have been computed on
-  // some earlier call to DiscoverBlocks and record this predecessor.  For
-  // joins save the original predecessors, if any, so we can garbage collect
-  // phi inputs from unreachable predecessors without recomputing SSA.
+  // some earlier call to DiscoverBlocks and record this predecessor.
   ClearPredecessors();
-  AddPredecessor(current_block);
+  if (predecessor != NULL) AddPredecessor(predecessor);
 
-  // 3. The current block is the spanning-tree parent.
-  parent->Add(current_block->preorder_number());
+  // 3. The predecessor is the spanning-tree parent.  The graph entry has no
+  // parent, indicated by -1.
+  intptr_t parent_number =
+      (predecessor == NULL) ? -1 : predecessor->preorder_number();
+  parent->Add(parent_number);
 
-  // 4. Assign preorder number and add the block entry to the list.
+  // 4. Assign the preorder number and add the block entry to the list.
   // Allocate an empty set of assigned variables for the block.
   set_preorder_number(preorder->length());
   preorder->Add(this);
   BitVector* vars =
       (variable_count == 0) ? NULL : new BitVector(variable_count);
   assigned_vars->Add(vars);
   // The preorder, parent, and assigned_vars arrays are all indexed by
   // preorder block number, so they should stay in lockstep.
   ASSERT(preorder->length() == parent->length());
   ASSERT(preorder->length() == assigned_vars->length());
 
-  // 5. Iterate straight-line successors until a branch instruction or
-  // another basic block entry instruction, and visit that instruction.
-  ASSERT(next() != NULL);
-  ASSERT(!next()->IsBlockEntry());
-  Instruction* next_instr = next();
-  while ((next_instr != NULL) &&
-         !next_instr->IsBlockEntry() &&
-         !next_instr->IsControl()) {
+  // 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();
     if (vars != NULL) {
-      next_instr->RecordAssignedVars(vars, fixed_parameter_count);
+      last->RecordAssignedVars(vars, fixed_parameter_count);
     }
-    set_last_instruction(next_instr);
-    GotoInstr* goto_instr = next_instr->AsGoto();
-    next_instr =
-        (goto_instr != NULL) ? goto_instr->successor() : next_instr->next();
   }
-  if (next_instr != NULL) {
-    next_instr->DiscoverBlocks(this, preorder, postorder,
-                               parent, assigned_vars,
-                               variable_count, fixed_parameter_count);
+  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, assigned_vars,
+                                         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);
 }
 
 
 bool BlockEntryInstr::Dominates(BlockEntryInstr* other) const {
   // TODO(fschneider): Make this faster by e.g. storing dominators for each
   // block while computing the dominator tree.
   ASSERT(other != NULL);
   BlockEntryInstr* current = other;
   while (current != NULL && current != this) {
     current = current->dominator();
   }
   return current == this;
 }
 
 
-void ControlInstruction::DiscoverBlocks(
-    BlockEntryInstr* current_block,
-    GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<BlockEntryInstr*>* postorder,
-    GrowableArray<intptr_t>* parent,
-    GrowableArray<BitVector*>* assigned_vars,
-    intptr_t variable_count,
-    intptr_t fixed_parameter_count) {
-  current_block->set_last_instruction(this);
-  // Visit the false successor before the true successor so they appear in
-  // true/false order in reverse postorder used as the block ordering in the
-  // nonoptimizing compiler.
-  ASSERT(true_successor_ != NULL);
-  ASSERT(false_successor_ != NULL);
-  false_successor_->DiscoverBlocks(current_block, preorder, postorder,
-                                   parent, assigned_vars,
-                                   variable_count, fixed_parameter_count);
-  true_successor_->DiscoverBlocks(current_block, preorder, postorder,
-                                  parent, assigned_vars,
-                                  variable_count, fixed_parameter_count);
-}
-
-
 void JoinEntryInstr::InsertPhi(intptr_t var_index, intptr_t var_count) {
   // Lazily initialize the array of phis.
   // Currently, phis are stored in a sparse array that holds the phi
   // for variable with index i at position i.
   // TODO(fschneider): Store phis in a more compact way.
   if (phis_ == NULL) {
     phis_ = new ZoneGrowableArray<PhiInstr*>(var_count);
     for (intptr_t i = 0; i < var_count; i++) {
       phis_->Add(NULL);
     }
@@ skipping 1905 matching lines @@
     default:
       UNREACHABLE();
       return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart