Initial implementation of sparse conditional constant propagation.

runtime/vm/flow_graph.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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 16 matching lines @@
     preorder_(),
     postorder_(),
     reverse_postorder_(),
     exits_(NULL) {
   DiscoverBlocks();
 }
 
 
 void FlowGraph::DiscoverBlocks() {
   // Initialize state.
-  preorder_.TruncateTo(0);
-  postorder_.TruncateTo(0);
-  reverse_postorder_.TruncateTo(0);
-  parent_.TruncateTo(0);
-  assigned_vars_.TruncateTo(0);
+  preorder_.Clear();
+  postorder_.Clear();
+  reverse_postorder_.Clear();
+  parent_.Clear();
+  assigned_vars_.Clear();
   // Perform a depth-first traversal of the graph to build preorder and
   // postorder block orders.
   graph_entry_->DiscoverBlocks(NULL,  // Entry block predecessor.
                                &preorder_,
                                &postorder_,
                                &parent_,
                                &assigned_vars_,
                                variable_count(),
                                num_non_copied_params());
   // Number blocks in reverse postorder.
@@ skipping 240 matching lines @@
     ClearUseLists(graph_entry_->start_env()->ValueAt(i)->definition());
   }
   ComputeUseListsRecursive(graph_entry_);
   DEBUG_ASSERT(ValidateUseLists());
 }
 
 
 void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) {
   current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
-  ComputeDominators(&preorder_, &parent_, &dominance_frontier);
+  ComputeDominators(&dominance_frontier);
   InsertPhis(preorder_, 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);
 }
 
 
 // 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 FlowGraph::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();
+  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]);
+    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];
+    BlockEntryInstr* block = preorder_[block_index];
+    // Clear the immediately dominated blocks in case ComputeDominators is
+    // used to recompute them.
+    block->ClearDominatedBlocks();
     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);
+        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]);
+    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];
+    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();
       }
     }
   }
@@ skipping 375 matching lines @@
     // TODO(zerny): Support multiple exits.
     UNREACHABLE();
   }
 
   // TODO(zerny): Adjust pre/post orders.
   // TODO(zerny): Update dominator tree.
 }
 
 
 }  // namespace dart