Improve dead phi elimination....

src/hydrogen.cc

Index: src/hydrogen.cc
===================================================================
--- src/hydrogen.cc	(revision 7081)
+++ src/hydrogen.cc	(working copy)
@@ -92,7 +92,7 @@
 void HBasicBlock::RemovePhi(HPhi* phi) {
   ASSERT(phi->block() == this);
   ASSERT(phis_.Contains(phi));
-  ASSERT(phi->HasNoUses());
+  ASSERT(phi->HasNoUses() || !phi->is_live());
   phi->ClearOperands();
   phis_.RemoveElement(phi);
   phi->SetBlock(NULL);
@@ -723,9 +723,8 @@
       const ZoneList<HValue*>* uses = phi->uses();
       for (int i = 0; i < uses->length(); ++i) {

[Kevin Millikin (Chromium), 2011/03/08 08:51:03]

This pair of loops that copies the uses off to the side drives me nuts.  I
wonder if we could just write

  while (!uses->is_empty()) {
    HValue* use = uses->RemoveLast();
    if (use != NULL) {
      phi->ReplaceAtUse(use, value);
      if (use->IsPhi()) worklist.Add(HPhi::cast(use));
    }
  }

[fschneider, 2011/03/08 10:03:39]

Done.

         HValue* use = uses->at(i);
-        if (!use->block()->IsStartBlock()) {
-          uses_to_replace.Add(use);
-        }
+        ASSERT(!use->block()->IsStartBlock());
+        uses_to_replace.Add(use);
       }
       // Replace the uses and add phis modified to the work list.
       for (int i = 0; i < uses_to_replace.length(); ++i) {
@@ -735,11 +734,49 @@
       }
       uses_to_replace.Rewind(0);
       block->RemovePhi(phi);
-    } else if (FLAG_eliminate_dead_phis && phi->HasNoUses() &&
-               !phi->IsReceiver()) {
+    }
+  }
+}
+
+
+void HGraph::EliminateDeadPhis() {
+  HPhase phase("Dead phi elimination", this);
+
+  // Initialize worklist.
+  ZoneList<HPhi*> phi_list(blocks_.length());
+  ZoneList<HPhi*> worklist(blocks_.length());
+  for (int i = 0; i < blocks_.length(); ++i) {
+    for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
+      HPhi* phi = blocks_[i]->phis()->at(j);
+      phi_list.Add(phi);
       // We can't eliminate phis in the receiver position in the environment
       // because in case of throwing an error we need this value to
       // construct a stack trace.
+      if (phi->HasRealUses() || phi->IsReceiver())  {
+        phi->set_is_live(true);
+        worklist.Add(phi);
+      }
+    }
+  }
+
+  // Iteratively mark live phis.
+  while (!worklist.is_empty()) {
+    HPhi* phi = worklist.RemoveLast();
+    for (int i = 0; i < phi->OperandCount(); i++) {
+      HValue* operand = phi->OperandAt(i);
+      if (operand->IsPhi() && !HPhi::cast(operand)->is_live()) {
+        HPhi::cast(operand)->set_is_live(true);
+        worklist.Add(HPhi::cast(operand));
+      }
+    }
+  }
+
+  // Remove dead phis.
+  for (int i = 0; i < phi_list.length(); i++) {
+    HPhi* phi = phi_list[i];
+    if (!phi->is_live()) {
+      if (FLAG_trace_hydrogen) PrintF("Removing dead phi %d\n", phi->id());
+      HBasicBlock* block = phi->block();
       block->RemovePhi(phi);
       block->RecordDeletedPhi(phi->merged_index());
     }
@@ -2167,6 +2204,7 @@
   graph()->OrderBlocks();
   graph()->AssignDominators();
   graph()->EliminateRedundantPhis();
+  if (FLAG_eliminate_dead_phis) graph()->EliminateDeadPhis();
   if (!graph()->CollectPhis()) {
     Bailout("Phi-use of arguments object");
     return NULL;