Initial work on computing SSA.

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 8d42478a2718c660f04d445b681ccb511afaaa4b..eb2a1ef873745add448c7051be1359c42484a500 100644
--- a/runtime/vm/flow_graph_builder.cc
+++ b/runtime/vm/flow_graph_builder.cc
@@ -2279,6 +2279,85 @@ void FlowGraphBuilder::CompressPath(intptr_t start_index,
 }
 
 
+void FlowGraphBuilder::InsertPhis(GrowableArray<BlockEntryInstr*>* preorder,
+                                  GrowableArray<BitVector*>* assigned_vars,
+                                  intptr_t var_count,
+                                  GrowableArray<BitVector*>* dom_frontier) {
+  int 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.
+  int* has_already = new int[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.
+  int* work = new int[block_count];
+
+  // Initialize has_already and work.
+  for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
+    has_already[block_index] = -1;
+    work[block_index] = -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.
+      BitVector::Iterator it((*dom_frontier)[current->preorder_number()]);
+      while (!it.Done()) {
+        int index = it.Current();
+        if (has_already[index] < var_index) {
+          BlockEntryInstr* block = (*preorder)[index];
+          ASSERT(block->IsJoinEntry());
+          block->AsJoinEntry()->InsertPhi(var_index);
+          has_already[index] = var_index;
+          if (work[index] < var_index) {
+            work[index] = var_index;
+            worklist.Add(block);
+          }
+        }
+      }
+    }
+  }
+
+  delete[] work;
+  delete[] has_already;
+}
+
+
+void FlowGraphBuilder::RenameLocals(intptr_t var_count) {
+  // Renaming environment is an array of values or NULL.
+
+  // Top-down recursive traversal of the dominator tree.  Pass a copy of the
+  // renaming environment to all children but the last one.
+
+  // Visit each instruction in the block.
+
+  // For each StoreLocal at current context level that is not captured,
+  // remove it from the graph and add it's rhs to the renaming environment.
+
+  // For each LoadLocal at current context level that is not captured,
+  // remove it from the graph.
+
+  // For each use of a load local or store local, replace it with the value
+  // in the environment.
+
+  // If the node does not dominate anything, process any phis in the
+  // successor.
+}
+
+
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();