First step to SSA construction: Phi insertion.

vm/flow_graph_builder.cc

Index: vm/flow_graph_builder.cc
===================================================================
--- vm/flow_graph_builder.cc	(revision 8546)
+++ vm/flow_graph_builder.cc	(working copy)
@@ -59,8 +59,8 @@
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
   DeallocateTempIndex(instruction->InputCount());
-  if (instruction->IsBindInstr()) {
-    instruction->AsBindInstr()->set_temp_index(AllocateTempIndex());
+  if (instruction->IsDefinition()) {
+    instruction->AsDefinition()->set_temp_index(AllocateTempIndex());
   }
   if (is_empty()) {
     entry_ = exit_ = instruction;
@@ -2337,6 +2337,11 @@
   if (for_optimized) {
     GrowableArray<BitVector*> dominance_frontier;
     ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
+    InsertPhis(preorder_block_entries_,
+               assigned_vars,
+               variable_count,
+               dominance_frontier);
+    // TODO(fschneider): Perform SSA renaming.
   }
   if (FLAG_print_flow_graph || (Dart::flow_graph_writer() != NULL)) {
     intptr_t length = postorder_block_entries_.length();
@@ -2445,6 +2450,7 @@
     }
     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
@@ -2481,6 +2487,62 @@
 }
 
 
+void FlowGraphBuilder::InsertPhis(
+    const GrowableArray<BlockEntryInstr*>& preorder,
+    const GrowableArray<BitVector*>& assigned_vars,
+    const intptr_t var_count,
+    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 < var_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, var_count);
+          has_already[index] = var_index;
+          if (work[index] < var_index) {
+            work[index] = var_index;
+            worklist.Add(block);
+          }
+        }
+      }
+    }
+  }
+}
+
+
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();