More general dead phi elimination.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 7250 matching lines @@
 };
 
 
 void DeadStoreElimination::Optimize(FlowGraph* graph) {
   if (FLAG_dead_store_elimination) {
     StoreOptimizer::OptimizeGraph(graph);
   }
 }
 
 
+void DeadCodeElimination::EliminateDeadPhis(FlowGraph* flow_graph) {
+  GrowableArray<PhiInstr*> live_phis;
+  for (BlockIterator b = flow_graph->postorder_iterator();
+       !b.Done();
+       b.Advance()) {
+    JoinEntryInstr* join = b.Current()->AsJoinEntry();
+    if (join != NULL) {
+      for (PhiIterator it(join); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        // Phis that have uses and phis inside try blocks are
+        // marked as live.
+        if (phi->HasUses() || join->InsideTryBlock()) {
+          live_phis.Add(phi);
+          phi->mark_alive();
+        } else {
+          phi->mark_dead();
+        }
+      }
+    }
+  }
+
+  while (!live_phis.is_empty()) {
+    PhiInstr* phi = live_phis.RemoveLast();
+    for (intptr_t i = 0; i < phi->InputCount(); i++) {
+      Value* val = phi->InputAt(i);
+      PhiInstr* used_phi = val->definition()->AsPhi();
+      if ((used_phi != NULL) && !used_phi->is_alive()) {
+        used_phi->mark_alive();
+        live_phis.Add(used_phi);
+      }
+    }
+  }
+
+  for (BlockIterator it(flow_graph->postorder_iterator());
+       !it.Done();
+       it.Advance()) {
+    JoinEntryInstr* join = it.Current()->AsJoinEntry();
+    if (join != NULL) {

[srdjan, 2014/05/12 21:21:44]

if ((join != NULL ) && (join->phis_ != NULL)) {

+      if (join->phis_ == NULL) continue;
+
+      // Eliminate dead phis and compact the phis_ array of the block.
+      intptr_t to_index = 0;
+      for (intptr_t i = 0; i < join->phis_->length(); ++i) {
+        PhiInstr* phi = (*join->phis_)[i];
+        if (phi != NULL) {
+          if (!phi->is_alive()) {
+            phi->ReplaceUsesWith(flow_graph->constant_null());
+            phi->UnuseAllInputs();
+            (*join->phis_)[i] = NULL;
+            if (FLAG_trace_optimization) {
+              OS::Print("Removing dead phi v%" Pd "\n", phi->ssa_temp_index());
+            }
+          } else if (phi->IsRedundant()) {
+            phi->ReplaceUsesWith(phi->InputAt(0)->definition());
+            phi->UnuseAllInputs();
+            (*join->phis_)[i] = NULL;
+            if (FLAG_trace_optimization) {
+              OS::Print("Removing redundant phi v%" Pd "\n",
+                         phi->ssa_temp_index());
+            }
+          } else {
+            (*join->phis_)[to_index++] = phi;
+          }
+        }
+      }
+      if (to_index == 0) {
+        join->phis_ = NULL;
+      } else {
+        join->phis_->TruncateTo(to_index);
+      }
+    }
+  }
+}
+
+
 class CSEInstructionMap : public ValueObject {
  public:
   // Right now CSE and LICM track a single effect: possible externalization of
   // strings.
   // Other effects like modifications of fields are tracked in a separate load
   // forwarding pass via Alias structure.
   COMPILE_ASSERT(EffectSet::kLastEffect == 1, single_effect_is_tracked);
 
   CSEInstructionMap() : independent_(), dependent_() { }
   explicit CSEInstructionMap(const CSEInstructionMap& other)
@@ skipping 1484 matching lines @@
 }
 
 
 void ConstantPropagator::Transform() {
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== Before constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 
-  GrowableArray<PhiInstr*> redundant_phis(10);
-
   // We will recompute dominators, block ordering, block ids, block last
   // instructions, previous pointers, predecessors, etc. after eliminating
   // unreachable code.  We do not maintain those properties during the
   // transformation.
   for (BlockIterator b = graph_->reverse_postorder_iterator();
        !b.Done();
        b.Advance()) {
     BlockEntryInstr* block = b.Current();
     if (!reachable_->Contains(block->preorder_number())) {
       if (FLAG_trace_constant_propagation) {
@@ skipping 731 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart