Compute assigned variables and dominance frontiers.

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 5101f81f3c359eb91972da041bd9854262da5416..f6a99d6861d71956c8844e56e073259ad7f85b02 100644
--- a/runtime/vm/flow_graph_builder.cc
+++ b/runtime/vm/flow_graph_builder.cc
@@ -5,6 +5,7 @@
 #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"
@@ -30,7 +31,7 @@ FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
-    catch_entries_() {}
+    catch_entries_() { }
 
 
 void FlowGraphBuilder::AddCatchEntry(intptr_t try_index, Instruction* entry) {
@@ -2491,14 +2492,21 @@ void FlowGraphBuilder::BuildGraph(bool for_optimized) {
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
   GrowableArray<intptr_t> parent;
+  GrowableArray<BitVector*> assigned_vars;
+  intptr_t variable_count = parsed_function_.function().num_fixed_parameters() +
+      parsed_function_.copied_parameter_count() +
+      parsed_function_.stack_local_count();
+  GrowableArray<BitVector*> dominance_frontier;
   for (intptr_t i = 0; i < catch_entries_.length(); i++) {
     Instruction* entry = catch_entries_[i];
     entry->DiscoverBlocks(NULL,  // Entry block predecessor.
                           &preorder_block_entries_,
                           &postorder_block_entries_,
-                          &parent);
+                          &parent,
+                          &assigned_vars,
+                          variable_count);
     if (for_optimized) {
-      ComputeDominators(&preorder_block_entries_, &parent);
+      ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
     }
   }
   if (for_effect.entry() != NULL) {
@@ -2507,9 +2515,11 @@ void FlowGraphBuilder::BuildGraph(bool for_optimized) {
     for_effect.entry()->DiscoverBlocks(NULL,  // Entry block predecessor.
                                        &preorder_block_entries_,
                                        &postorder_block_entries_,
-                                       &parent);
+                                       &parent,
+                                       &assigned_vars,
+                                       variable_count);
     if (for_optimized) {
-      ComputeDominators(&preorder_block_entries_, &parent);
+      ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
     }
   }
   isolate->set_computation_id(prev_cid);
@@ -2527,7 +2537,8 @@ void FlowGraphBuilder::BuildGraph(bool for_optimized) {
 
 void FlowGraphBuilder::ComputeDominators(
     GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<intptr_t>* parent) {
+    GrowableArray<intptr_t>* parent,
+    GrowableArray<BitVector*>* dominance_frontier) {

[srdjan, 2012/05/12 00:00:55]

Maybe add in comment what is the content of parent array (what does the integer
means) and what is the content of dominance_frontier (what do bits mean).

[Kevin Millikin (Google), 2012/05/15 11:51:44]

Done.

   // 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
@@ -2552,11 +2563,14 @@ void FlowGraphBuilder::ComputeDominators(
   // 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.
+  // 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,
+                                          Isolate::Current()->current_zone()));

[Florian Schneider, 2012/05/11 13:19:37]

Maybe it would be useful to have a Zone* zone_ stored in the FlowGraphBuilder
because we will do frequent zone-allocation for auxiliary data structures from
there.

[srdjan, 2012/05/12 00:00:55]

That would premature optimization, IMHO. At some point we may want to cache
Isolate and Zone but right now I would eliminate zone parameter, especially
since we do not pass different zones but the current one.

[Kevin Millikin (Google), 2012/05/15 11:51:44]

I've eliminated the parameter, but I disagree that it is premature optimization.

There's a pretty big constant factor involved in paying for TLS on every zone
allocation.  And I think it is much easier to begin now passing the current
isolate and/or zone around where needed, rather than trying to implement a big
change to retrofit it later.

[srdjan, 2012/05/15 22:05:32]

In the VM we do not pass isolates/zones for performance reasons.

   }
 
   // Loop over the blocks in reverse preorder (not including the graph
@@ -2564,7 +2578,7 @@ void FlowGraphBuilder::ComputeDominators(
   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; i < block->PredecessorCount(); ++i) {
+    for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) {
       BlockEntryInstr* pred = block->PredecessorAt(i);
       ASSERT(pred != NULL);
 
@@ -2586,7 +2600,7 @@ void FlowGraphBuilder::ComputeDominators(
   }
 
   // 2. Compute the immediate dominators as the nearest common ancestor of
-  // spanning tree parent and semidominator, for all nodes except the entry.
+  // 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]) {
@@ -2595,6 +2609,24 @@ void FlowGraphBuilder::ComputeDominators(
     idom[block_index] = dom_index;
     (*preorder)[block_index]->set_dominator((*preorder)[dom_index]);
   }
+
+  // 3. 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();
+      }
+    }
+  }
 }