Reapply "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 131 matching lines @@
       ValidateUseListsInInstruction(it.Current());
     }
   }
   return true;  // Return true so we can ASSERT validation.
 }
 #endif  // DEBUG
 
 
 static void ClearUseLists(Definition* defn) {
   ASSERT(defn != NULL);
-  DEBUG_ASSERT(defn->input_use_list() == NULL);
-  DEBUG_ASSERT(defn->env_use_list() == NULL);
+  ASSERT(defn->input_use_list() == NULL);
+  ASSERT(defn->env_use_list() == NULL);
   defn->set_input_use_list(NULL);
   defn->set_env_use_list(NULL);
 }
 
 
 static void RecordInputUses(Instruction* instr) {
   ASSERT(instr != NULL);
   for (intptr_t i = 0; i < instr->InputCount(); ++i) {
     Value* use = instr->InputAt(i);
-    DEBUG_ASSERT(use->instruction() == NULL);
-    DEBUG_ASSERT(use->use_index() == -1);
-    DEBUG_ASSERT(use->next_use() == NULL);
+    ASSERT(use->instruction() == NULL);
+    ASSERT(use->use_index() == -1);
+    ASSERT(use->next_use() == NULL);
     DEBUG_ASSERT(0 == MembershipCount(use,
                                       use->definition()->input_use_list()));
     use->set_instruction(instr);
     use->set_use_index(i);
     use->AddToInputUseList();
   }
 }
 
 
 static void RecordEnvUses(Instruction* instr) {
   ASSERT(instr != NULL);
   if (instr->env() == NULL) return;
   intptr_t use_index = 0;
   for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
     Value* use = it.CurrentValue();
-    DEBUG_ASSERT(use->instruction() == NULL);
-    DEBUG_ASSERT(use->use_index() == -1);
-    DEBUG_ASSERT(use->next_use() == NULL);
+    ASSERT(use->instruction() == NULL);
+    ASSERT(use->use_index() == -1);
+    ASSERT(use->next_use() == NULL);
     DEBUG_ASSERT(0 == MembershipCount(use, use->definition()->env_use_list()));
     use->set_instruction(instr);
     use->set_use_index(use_index++);
     use->AddToEnvUseList();
   }
 }
 
 
 static void ComputeUseListsRecursive(BlockEntryInstr* block) {
   // Clear phi definitions.
@@ skipping 20 matching lines @@
       block->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
     JoinEntryInstr* join =
         block->last_instruction()->SuccessorAt(0)->AsJoinEntry();
     intptr_t pred_index = join->IndexOfPredecessor(block);
     ASSERT(pred_index >= 0);
     if (join->phis() != NULL) {
       for (intptr_t i = 0; i < join->phis()->length(); ++i) {
         PhiInstr* phi = (*join->phis())[i];
         if (phi == NULL) continue;
         Value* use = phi->InputAt(pred_index);
-        DEBUG_ASSERT(use->instruction() == NULL);
-        DEBUG_ASSERT(use->use_index() == -1);
-        DEBUG_ASSERT(use->next_use() == NULL);
+        ASSERT(use->instruction() == NULL);
+        ASSERT(use->use_index() == -1);
+        ASSERT(use->next_use() == NULL);
         DEBUG_ASSERT(0 == MembershipCount(use,
                                           use->definition()->input_use_list()));
         use->set_instruction(phi);
         use->set_use_index(pred_index);
         use->AddToInputUseList();
       }
     }
   }
 }
 
 
 void FlowGraph::ComputeUseLists() {
   DEBUG_ASSERT(ResetUseLists());
   // Clear initial definitions.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
     ClearUseLists((*graph_entry_->initial_definitions())[i]);
   }
   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).
+  // entry).  Clear the dominated blocks in the graph entry in case
+  // ComputeDominators is used to recompute them.
+  preorder_[0]->ClearDominatedBlocks();
   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 384 matching lines @@
     // TODO(zerny): Support multiple exits.
     UNREACHABLE();
   }
 
   // TODO(zerny): Adjust pre/post orders.
   // TODO(zerny): Update dominator tree.
 }
 
 
 }  // namespace dart