Improve dead phi elimination....

src/hydrogen.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 74 matching lines @@
 void HBasicBlock::AddPhi(HPhi* phi) {
   ASSERT(!IsStartBlock());
   phis_.Add(phi);
   phi->SetBlock(this);
 }
 
 
 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);
 }
 
 
 void HBasicBlock::AddInstruction(HInstruction* instr) {
   ASSERT(!IsStartBlock() || !IsFinished());
   ASSERT(!instr->IsLinked());
   ASSERT(!IsFinished());
@@ skipping 608 matching lines @@
     // Skip phi node if it was already replaced.
     if (block == NULL) continue;
 
     // Get replacement value if phi is redundant.
     HValue* value = phi->GetRedundantReplacement();
 
     if (value != NULL) {
       // Iterate through uses finding the ones that should be
       // replaced.
       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) {
         HValue* use = uses_to_replace[i];
         phi->ReplaceAtUse(use, value);
         if (use->IsPhi()) worklist.Add(HPhi::cast(use));
       }
       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());
     }
   }
 }
 
 
 bool HGraph::CollectPhis() {
   const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
   phi_list_ = new ZoneList<HPhi*>(blocks->length());
@@ skipping 1407 matching lines @@
     if (current_block() != NULL) {
       HReturn* instr = new HReturn(graph()->GetConstantUndefined());
       current_block()->FinishExit(instr);
       set_current_block(NULL);
     }
   }
 
   graph()->OrderBlocks();
   graph()->AssignDominators();
   graph()->EliminateRedundantPhis();
+  if (FLAG_eliminate_dead_phis) graph()->EliminateDeadPhis();
   if (!graph()->CollectPhis()) {
     Bailout("Phi-use of arguments object");
     return NULL;
   }
 
   HInferRepresentation rep(graph());
   rep.Analyze();
 
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(graph());
@@ skipping 3759 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify();
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal