Refactored FlowGraphBuilder into a separate FlowGraph representation.

runtime/vm/flow_graph_builder.cc

Index: runtime/vm/flow_graph_builder.cc
diff --git a/runtime/vm/flow_graph_builder.cc b/runtime/vm/flow_graph_builder.cc
index 3cf0ae006179539c3cc2c3c8ff511d201f815bf3..af5b86daa4bcd6c4849f670833615c75b7a6cf9e 100644
--- a/runtime/vm/flow_graph_builder.cc
+++ b/runtime/vm/flow_graph_builder.cc
@@ -5,7 +5,6 @@
 #include "vm/flow_graph_builder.h"
 
 #include "vm/ast_printer.h"
-#include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
 #include "vm/flags.h"
@@ -31,21 +30,15 @@ DECLARE_FLAG(bool, enable_type_checks);
 DECLARE_FLAG(bool, use_ssa);
 
 
-FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
-  : parsed_function_(parsed_function),
-    copied_parameter_count_(parsed_function.copied_parameter_count()),
-    // All parameters are copied if any parameter is.
-    non_copied_parameter_count_((copied_parameter_count_ == 0)
-        ? parsed_function.function().num_fixed_parameters()
-        : 0),
-    stack_local_count_(parsed_function.stack_local_count()),
-    preorder_block_entries_(),
-    postorder_block_entries_(),
+FlowGraphBuilder::FlowGraphBuilder(const FlowGraph& flow_graph)
+  : parsed_function_(flow_graph.parsed_function()),

[Kevin Millikin (Google), 2012/08/16 08:09:57]

These can also be stored in the flow graph instead of copied here, with
accessors in this class (unless you make the change that it is the builder that
creates the graph).

+    copied_parameter_count_(flow_graph.copied_parameter_count()),
+    non_copied_parameter_count_(flow_graph.non_copied_parameter_count()),
+    stack_local_count_(flow_graph.stack_local_count()),
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
-    graph_entry_(NULL),
-    current_ssa_temp_index_(0) { }
+    graph_entry_(NULL) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(TargetEntryInstr* entry) {
@@ -2389,7 +2382,7 @@ void EffectGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) {
 }
 
 
-void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) {
+GraphEntryInstr* FlowGraphBuilder::BuildGraph() {
   if (FLAG_print_ast) {
     // Print the function ast before IL generation.
     AstPrinter::PrintFunctionNodes(parsed_function());
@@ -2407,440 +2400,10 @@ void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) {
   AppendFragment(normal_entry, for_effect);
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
-  GrowableArray<intptr_t> parent;
-  GrowableArray<BitVector*> assigned_vars;
-
-  // Perform a depth-first traversal of the graph to build preorder and
-  // postorder block orders.
-  graph_entry_->DiscoverBlocks(NULL,  // Entry block predecessor.
-                               &preorder_block_entries_,
-                               &postorder_block_entries_,
-                               &parent,
-                               &assigned_vars,
-                               variable_count(),
-                               non_copied_parameter_count_);
-  // Number blocks in reverse postorder.
-  intptr_t block_count = postorder_block_entries_.length();
-  for (intptr_t i = 0; i < block_count; ++i) {
-    postorder_block_entries_[i]->set_block_id(block_count - i - 1);
-  }
-
-  if (for_optimized) {
-    // Link instructions backwards for optimized compilation.
-    for (intptr_t i = 0; i < block_count; ++i) {
-      BlockEntryInstr* entry = postorder_block_entries_[i];
-      Instruction* previous = entry;
-      for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
-        Instruction* current = it.Current();
-        current->set_previous(previous);
-        previous = current;
-      }
-    }
-  }
-
-  if (for_optimized && use_ssa) {
-    GrowableArray<BitVector*> dominance_frontier;
-    ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
-    InsertPhis(preorder_block_entries_,
-               assigned_vars,
-               dominance_frontier);
-
-    GrowableArray<PhiInstr*> live_phis;
-
-    // Rename uses to reference inserted phis where appropriate.
-    // Collect phis that reach a non-environment use.
-    Rename(&live_phis);
-
-    // Propagate alive mark transitively from alive phis.
-    MarkLivePhis(&live_phis);
-  }
-  if (FLAG_print_flow_graph || (Dart::flow_graph_writer() != NULL)) {
-    intptr_t length = postorder_block_entries_.length();
-    GrowableArray<BlockEntryInstr*> reverse_postorder(length);
-    for (intptr_t i = length - 1; i >= 0; --i) {
-      reverse_postorder.Add(postorder_block_entries_[i]);
-    }
-    if (FLAG_print_flow_graph) {
-      // Print flow graph to stdout.
-      FlowGraphPrinter printer(function, reverse_postorder);
-      printer.PrintBlocks();
-    }
-    if (Dart::flow_graph_writer() != NULL) {
-      // Write flow graph to file.
-      FlowGraphVisualizer printer(function, reverse_postorder);
-      printer.PrintFunction();
-    }
-  }
-}
-
-
-// Compute immediate dominators and the dominance frontier for each basic
-// block.  As a side effect of the algorithm, sets the immediate dominator
-// of each basic block.
-//
-// preorder: an input list of basic block entries in preorder.  The
-//     algorithm relies on the block ordering.
-//
-// parent: an input parameter encoding a depth-first spanning tree of
-//     the control flow graph.  The array maps the preorder block
-//     number of a block to the preorder block number of its spanning
-//     tree parent.
-//
-// dominance_frontier: an output parameter encoding the dominance frontier.
-//     The array maps the preorder block number of a block to the set of
-//     (preorder block numbers of) blocks in the dominance frontier.
-void FlowGraphBuilder::ComputeDominators(
-    GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<intptr_t>* parent,
-    GrowableArray<BitVector*>* dominance_frontier) {
-  // Use the SEMI-NCA algorithm to compute dominators.  This is a two-pass
-  // version of the Lengauer-Tarjan algorithm (LT is normally three passes)
-  // that eliminates a pass by using nearest-common ancestor (NCA) to
-  // compute immediate dominators from semidominators.  It also removes a
-  // level of indirection in the link-eval forest data structure.
-  //
-  // The algorithm is described in Georgiadis, Tarjan, and Werneck's
-  // "Finding Dominators in Practice".
-  // See http://www.cs.princeton.edu/~rwerneck/dominators/ .
-
-  // All arrays are maps between preorder basic-block numbers.
-  intptr_t size = parent->length();
-  GrowableArray<intptr_t> idom(size);  // Immediate dominator.
-  GrowableArray<intptr_t> semi(size);  // Semidominator.
-  GrowableArray<intptr_t> label(size);  // Label for link-eval forest.
-
-  // 1. First pass: compute semidominators as in Lengauer-Tarjan.
-  // Semidominators are computed from a depth-first spanning tree and are an
-  // approximation of immediate dominators.
-
-  // Use a link-eval data structure with path compression.  Implement path
-  // compression in place by mutating the parent array.  Each block has a
-  // label, which is the minimum block number on the compressed path.
-
-  // Initialize idom, semi, and label used by SEMI-NCA.  Initialize the
-  // dominance frontier output array.
-  for (intptr_t i = 0; i < size; ++i) {
-    idom.Add((*parent)[i]);
-    semi.Add(i);
-    label.Add(i);
-    dominance_frontier->Add(new BitVector(size));
-  }
-
-  // Loop over the blocks in reverse preorder (not including the graph
-  // entry).
-  for (intptr_t block_index = size - 1; block_index >= 1; --block_index) {
-    // Loop over the predecessors.
-    BlockEntryInstr* block = (*preorder)[block_index];
-    for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) {
-      BlockEntryInstr* pred = block->PredecessorAt(i);
-      ASSERT(pred != NULL);
-
-      // Look for the semidominator by ascending the semidominator path
-      // starting from pred.
-      intptr_t pred_index = pred->preorder_number();
-      intptr_t best = pred_index;
-      if (pred_index > block_index) {
-        CompressPath(block_index, pred_index, parent, &label);
-        best = label[pred_index];
-      }
-
-      // Update the semidominator if we've found a better one.
-      semi[block_index] = Utils::Minimum(semi[block_index], semi[best]);
-    }
-
-    // Now use label for the semidominator.
-    label[block_index] = semi[block_index];
-  }
-
-  // 2. Compute the immediate dominators as the nearest common ancestor of
-  // spanning tree parent and semidominator, for all blocks except the entry.
-  for (intptr_t block_index = 1; block_index < size; ++block_index) {
-    intptr_t dom_index = idom[block_index];
-    while (dom_index > semi[block_index]) {
-      dom_index = idom[dom_index];
-    }
-    idom[block_index] = dom_index;
-    (*preorder)[block_index]->set_dominator((*preorder)[dom_index]);
-    (*preorder)[dom_index]->AddDominatedBlock((*preorder)[block_index]);
-  }
-
-  // 3. Now compute the dominance frontier for all blocks.  This is
-  // algorithm in "A Simple, Fast Dominance Algorithm" (Figure 5), which is
-  // attributed to a paper by Ferrante et al.  There is no bookkeeping
-  // required to avoid adding a block twice to the same block's dominance
-  // frontier because we use a set to represent the dominance frontier.
-  for (intptr_t block_index = 0; block_index < size; ++block_index) {
-    BlockEntryInstr* block = (*preorder)[block_index];
-    intptr_t count = block->PredecessorCount();
-    if (count <= 1) continue;
-    for (intptr_t i = 0; i < count; ++i) {
-      BlockEntryInstr* runner = block->PredecessorAt(i);
-      while (runner != block->dominator()) {
-        (*dominance_frontier)[runner->preorder_number()]->Add(block_index);
-        runner = runner->dominator();
-      }
-    }
-  }
-}
-
-
-void FlowGraphBuilder::CompressPath(intptr_t start_index,
-                                    intptr_t current_index,
-                                    GrowableArray<intptr_t>* parent,
-                                    GrowableArray<intptr_t>* label) {
-  intptr_t next_index = (*parent)[current_index];
-  if (next_index > start_index) {
-    CompressPath(start_index, next_index, parent, label);
-    (*label)[current_index] =
-        Utils::Minimum((*label)[current_index], (*label)[next_index]);
-    (*parent)[current_index] = (*parent)[next_index];
-  }
-}
-
-
-void FlowGraphBuilder::InsertPhis(
-    const GrowableArray<BlockEntryInstr*>& preorder,
-    const GrowableArray<BitVector*>& assigned_vars,
-    const GrowableArray<BitVector*>& dom_frontier) {
-  const intptr_t block_count = preorder.length();
-  // Map preorder block number to the highest variable index that has a phi
-  // in that block.  Use it to avoid inserting multiple phis for the same
-  // variable.
-  GrowableArray<intptr_t> has_already(block_count);
-  // Map preorder block number to the highest variable index for which the
-  // block went on the worklist.  Use it to avoid adding the same block to
-  // the worklist more than once for the same variable.
-  GrowableArray<intptr_t> work(block_count);
-
-  // Initialize has_already and work.
-  for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
-    has_already.Add(-1);
-    work.Add(-1);
-  }
-
-  // Insert phis for each variable in turn.
-  GrowableArray<BlockEntryInstr*> worklist;
-  for (intptr_t var_index = 0; var_index < variable_count(); ++var_index) {
-    // Add to the worklist each block containing an assignment.
-    for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
-      if (assigned_vars[block_index]->Contains(var_index)) {
-        work[block_index] = var_index;
-        worklist.Add(preorder[block_index]);
-      }
-    }
-
-    while (!worklist.is_empty()) {
-      BlockEntryInstr* current = worklist.Last();
-      worklist.RemoveLast();
-      // Ensure a phi for each block in the dominance frontier of current.
-      for (BitVector::Iterator it(dom_frontier[current->preorder_number()]);
-           !it.Done();
-           it.Advance()) {
-        int index = it.Current();
-        if (has_already[index] < var_index) {
-          BlockEntryInstr* block = preorder[index];
-          ASSERT(block->IsJoinEntry());
-          block->AsJoinEntry()->InsertPhi(var_index, variable_count());
-          has_already[index] = var_index;
-          if (work[index] < var_index) {
-            work[index] = var_index;
-            worklist.Add(block);
-          }
-        }
-      }
-    }
-  }
+  return graph_entry_;
 }
 
 
-void FlowGraphBuilder::Rename(GrowableArray<PhiInstr*>* live_phis) {
-  // TODO(fschneider): Support catch-entry.
-  if (graph_entry_->SuccessorCount() > 1) {
-    Bailout("Catch-entry support in SSA.");
-  }
-
-  // Initialize start environment.
-  GrowableArray<Value*> start_env(variable_count());
-  for (intptr_t i = 0; i < parameter_count(); ++i) {
-    ParameterInstr* param = new ParameterInstr(i);
-    param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
-    start_env.Add(new UseVal(param));
-  }
-
-  // All locals are initialized with #null.
-  Value* null_value = new ConstantVal(Object::ZoneHandle());
-  while (start_env.length() < variable_count()) {
-    start_env.Add(null_value);
-  }
-  graph_entry_->set_start_env(
-      new Environment(start_env, non_copied_parameter_count_));
-
-  BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0);
-  ASSERT(normal_entry != NULL);  // Must have entry.
-  GrowableArray<Value*> env(variable_count());
-  env.AddArray(start_env);
-  RenameRecursive(normal_entry, &env, live_phis);
-}
-
-
-// Helper to a copy a value iff it is a UseVal.
-static Value* CopyValue(Value* value) {
-  return value->IsUse()
-      ? new UseVal(value->AsUse()->definition())
-      : value;
-}
-
-
-void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
-                                       GrowableArray<Value*>* env,
-                                       GrowableArray<PhiInstr*>* live_phis) {
-  // 1. Process phis first.
-  if (block_entry->IsJoinEntry()) {
-    JoinEntryInstr* join = block_entry->AsJoinEntry();
-    if (join->phis() != NULL) {
-      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
-        PhiInstr* phi = (*join->phis())[i];
-        if (phi != NULL) {
-          (*env)[i] = new UseVal(phi);
-          phi->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
-        }
-      }
-    }
-  }
-
-  // 2. Process normal instructions.
-  for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
-    Instruction* current = it.Current();
-    // Attach current environment to the instruction. First, each instruction
-    // gets a full copy of the environment. Later we optimize this by
-    // eliminating unnecessary environments.
-    current->set_env(new Environment(*env, non_copied_parameter_count_));
-
-    // 2a. Handle uses:
-    // Update expression stack environment for each use.
-    // For each use of a LoadLocal or StoreLocal: Replace it with the value
-    // from the environment.
-    for (intptr_t i = current->InputCount() - 1; i >= 0; --i) {
-      Value* v = current->InputAt(i);
-      if (!v->IsUse()) continue;
-      // Update expression stack.
-      ASSERT(env->length() > variable_count());
-
-      Value* input_value = env->Last();
-      ASSERT(input_value->IsUse());
-      env->RemoveLast();
-
-      BindInstr* as_bind = v->AsUse()->definition()->AsBind();
-      if ((as_bind != NULL) &&
-          (as_bind->computation()->IsLoadLocal() ||
-           as_bind->computation()->IsStoreLocal())) {
-        current->SetInputAt(i, CopyValue(input_value));
-      }
-    }
-
-    // Drop pushed arguments for calls.
-    for (intptr_t j = 0; j < current->ArgumentCount(); j++) {
-      env->RemoveLast();
-    }
-
-    // 2b. Handle LoadLocal and StoreLocal.
-    // For each LoadLocal: Remove it from the graph.
-    // For each StoreLocal: Remove it from the graph and update the environment.
-    BindInstr* bind = current->AsBind();
-    if (bind != NULL) {
-      LoadLocalComp* load = bind->computation()->AsLoadLocal();
-      StoreLocalComp* store = bind->computation()->AsStoreLocal();
-      if ((load != NULL) || (store != NULL)) {
-        intptr_t index;
-        if (store != NULL) {
-          index = store->local().BitIndexIn(non_copied_parameter_count_);
-          // Update renaming environment.
-          (*env)[index] = store->value();
-        } else {
-          // The graph construction ensures we do not have an unused LoadLocal
-          // computation.
-          ASSERT(bind->is_used());
-          index = load->local().BitIndexIn(non_copied_parameter_count_);
-
-          Value* value = (*env)[index];
-          if (value->IsUse()) {
-            PhiInstr* phi = value->AsUse()->definition()->AsPhi();
-            if ((phi != NULL) && !phi->is_alive()) {
-              phi->mark_alive();
-              live_phis->Add(phi);
-            }
-          }
-        }
-        // Update expression stack and remove from graph.
-        if (bind->is_used()) {
-          env->Add(CopyValue((*env)[index]));
-        }
-        it.RemoveCurrentFromGraph();
-      } else {
-        // Not a load or store.
-        if (bind->is_used()) {
-          // Assign fresh SSA temporary and update expression stack.
-          bind->set_ssa_temp_index(alloc_ssa_temp_index());
-          env->Add(new UseVal(bind));
-        }
-      }
-    }
-
-    // 2c. Handle pushed argument.
-    PushArgumentInstr* push = current->AsPushArgument();
-    if (push != NULL) {
-      env->Add(new UseVal(push));
-    }
-  }
-
-  // 3. Process dominated blocks.
-  for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
-    BlockEntryInstr* block = block_entry->dominated_blocks()[i];
-    GrowableArray<Value*> new_env(env->length());
-    new_env.AddArray(*env);
-    RenameRecursive(block, &new_env, live_phis);
-  }
-
-  // 4. Process successor block. We have edge-split form, so that only blocks
-  // with one successor can have a join block as successor.
-  if ((block_entry->last_instruction()->SuccessorCount() == 1) &&
-      block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
-    JoinEntryInstr* successor =
-        block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry();
-    intptr_t pred_index = successor->IndexOfPredecessor(block_entry);
-    ASSERT(pred_index >= 0);
-    if (successor->phis() != NULL) {
-      for (intptr_t i = 0; i < successor->phis()->length(); ++i) {
-        PhiInstr* phi = (*successor->phis())[i];
-        if (phi != NULL) {
-          // Rename input operand and make a copy if it is a UseVal.
-          Value* new_val = (*env)[i]->IsUse()
-              ? new UseVal((*env)[i]->AsUse()->definition())
-              : (*env)[i];
-          phi->SetInputAt(pred_index, new_val);
-        }
-      }
-    }
-  }
-}
-
-
-void FlowGraphBuilder::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) {
-  while (!live_phis->is_empty()) {
-    PhiInstr* phi = live_phis->Last();
-    live_phis->RemoveLast();
-    for (intptr_t i = 0; i < phi->InputCount(); i++) {
-      Value* val = phi->InputAt(i);
-      if (!val->IsUse()) continue;
-      PhiInstr* used_phi = val->AsUse()->definition()->AsPhi();
-      if ((used_phi != NULL) && !used_phi->is_alive()) {
-        used_phi->mark_alive();
-        live_phis->Add(used_phi);
-      }
-    }
-  }
-}
-
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();