Eliminate phis that do not reach any non-environment uses.

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 4fe2fe4ba33a7a900a78aadbaabe050dca6e109f..fb35605df70c7704f429d4b4f6c3c8189d85b061 100644
--- a/runtime/vm/flow_graph_builder.cc
+++ b/runtime/vm/flow_graph_builder.cc
@@ -2342,7 +2342,15 @@ void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) {
     InsertPhis(preorder_block_entries_,
                assigned_vars,
                dominance_frontier);
-    Rename();
+
+    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);
   }
   if (FLAG_print_flow_graph || (Dart::flow_graph_writer() != NULL)) {
     intptr_t length = postorder_block_entries_.length();
@@ -2543,7 +2551,7 @@ void FlowGraphBuilder::InsertPhis(
 }
 
 
-void FlowGraphBuilder::Rename() {
+void FlowGraphBuilder::Rename(GrowableArray<PhiInstr*>* live_phis) {
   // TODO(fschneider): Support catch-entry.
   if (graph_entry_->SuccessorCount() > 1) {
     Bailout("Catch-entry support in SSA.");
@@ -2569,7 +2577,7 @@ void FlowGraphBuilder::Rename() {
   ASSERT(normal_entry != NULL);  // Must have entry.
   GrowableArray<Value*> env(variable_count());
   env.AddArray(start_env);
-  RenameRecursive(normal_entry, &env);
+  RenameRecursive(normal_entry, &env, live_phis);
 }
 
 
@@ -2582,7 +2590,8 @@ static Value* CopyValue(Value* value) {
 
 
 void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
-                                       GrowableArray<Value*>* env) {
+                                       GrowableArray<Value*>* env,
+                                       GrowableArray<PhiInstr*>* live_phis) {
   // 1. Process phis first.
   if (block_entry->IsJoinEntry()) {
     JoinEntryInstr* join = block_entry->AsJoinEntry();
@@ -2609,26 +2618,21 @@ void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
     // Update expression stack environment for each use.
     // For each use of a LoadLocal or StoreLocal: Replace it with the value
     // from the environment.
-    for (intptr_t i = 0; i < current->InputCount(); ++i) {
+    for (intptr_t i = current->InputCount() - 1; i >= 0; --i) {
       Value* v = current->InputAt(i);
       if (!v->IsUse()) continue;
       // Update expression stack.
       ASSERT(env->length() > variable_count());
+
+      Value* input_value = env->Last();
+      ASSERT(input_value->IsUse());
       env->RemoveLast();
+
       BindInstr* as_bind = v->AsUse()->definition()->AsBind();
-      if ((as_bind != NULL) && as_bind->computation()->IsLoadLocal()) {
-        Computation* comp = as_bind->computation();
-        intptr_t index = comp->AsLoadLocal()->local().BitIndexIn(
-            non_copied_parameter_count_);
-        current->SetInputAt(i, CopyValue((*env)[index]));
-      }
-      if ((as_bind != NULL) && as_bind->computation()->IsStoreLocal()) {
-        // For each use of a StoreLocal: Replace it with the value from the
-        // environment.
-        Computation* comp = as_bind->computation();
-        intptr_t index = comp->AsStoreLocal()->local().BitIndexIn(
-            non_copied_parameter_count_);
-        current->SetInputAt(i, CopyValue((*env)[index]));
+      if ((as_bind != NULL) &&
+          (as_bind->computation()->IsLoadLocal() ||
+           as_bind->computation()->IsStoreLocal())) {
+        current->SetInputAt(i, CopyValue(input_value));
       }
     }
 
@@ -2655,6 +2659,15 @@ void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
           // computation.
           ASSERT(bind->is_used());
           index = load->local().BitIndexIn(non_copied_parameter_count_);
+
+          Value* value = (*env)[index];
+          if (value->IsUse()) {
+            PhiInstr* phi = value->AsUse()->definition()->AsPhi();
+            if ((phi != NULL) && !phi->is_alive()) {
+              phi->mark_alive();
+              live_phis->Add(phi);
+            }
+          }
         }
         // Update expression stack and remove from graph.
         if (bind->is_used()) {
@@ -2683,7 +2696,7 @@ void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
     BlockEntryInstr* block = block_entry->dominated_blocks()[i];
     GrowableArray<Value*> new_env(env->length());
     new_env.AddArray(*env);
-    RenameRecursive(block, &new_env);
+    RenameRecursive(block, &new_env, live_phis);
   }
 
   // 4. Process successor block. We have edge-split form, so that only blocks
@@ -2710,6 +2723,22 @@ void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
 }
 
 
+void FlowGraphBuilder::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) {
+  while (!live_phis->is_empty()) {
+    PhiInstr* phi = live_phis->Last();
+    live_phis->RemoveLast();
+    for (intptr_t i = 0; i < phi->InputCount(); i++) {
+      Value* val = phi->InputAt(i);
+      if (!val->IsUse()) continue;
+      PhiInstr* used_phi = val->AsUse()->definition()->AsPhi();
+      if ((used_phi != NULL) && !used_phi->is_alive()) {
+        used_phi->mark_alive();
+        live_phis->Add(used_phi);
+      }
+    }
+  }
+}
+
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();