Compute assigned variables and dominance frontiers.

runtime/vm/flow_graph_builder.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/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"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/parser.h"
 #include "vm/resolver.h"
 #include "vm/stub_code.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph.");
 DECLARE_FLAG(bool, enable_type_checks);
 DEFINE_FLAG(bool, print_ast, false, "Print abstract syntax tree.");
 
 
 FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
   : parsed_function_(parsed_function),
     preorder_block_entries_(),
     postorder_block_entries_(),
     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) {
   catch_entries_.Add(entry);
 }
 
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
@@ skipping 2440 matching lines @@
   Isolate* isolate = Isolate::Current();
   const intptr_t prev_cid = isolate->computation_id();
   isolate->set_computation_id(0);
   const Function& function = parsed_function().function();
   EffectGraphVisitor for_effect(this, 0);
   for_effect.AddInstruction(new TargetEntryInstr());
   parsed_function().node_sequence()->Visit(&for_effect);
   // 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) {
     // Perform a depth-first traversal of the graph to build preorder and
     // postorder block orders.
     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);
   if (FLAG_print_flow_graph) {
     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]);
     }
     FlowGraphPrinter printer(function, reverse_postorder);
     printer.VisitBlocks();
   }
 }
 
 
 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
   // 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.
+  // 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
   // 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; i < block->PredecessorCount(); ++i) {
+    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 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]) {
       dom_index = idom[dom_index];
     }
     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();
+      }
+    }
+  }
 }
 
 
 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);
@@ skipping 11 matching lines @@
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len));
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart