From 51047312542a4a8e0c5e5724638dd83925c0b219 Mon Sep 17 00:00:00 2001
From: "titzer@chromium.org"
 <titzer@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 10 Oct 2013 08:50:44 +0000
Subject: [PATCH] Simplify redundant phi elimination and use during
 canonicalization too.

BUG=
R=verwaest@chromium.org

Review URL: https://codereview.chromium.org/25896006

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@17124 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/hydrogen-canonicalize.cc  |  8 +++++
 src/hydrogen-redundant-phi.cc | 70 +++++++++++++++++++++++++------------------
 src/hydrogen-redundant-phi.h  |  3 ++
 3 files changed, 52 insertions(+), 29 deletions(-)

diff --git a/src/hydrogen-canonicalize.cc b/src/hydrogen-canonicalize.cc
index 4d96415..d3f72e9 100644
--- a/src/hydrogen-canonicalize.cc
+++ b/src/hydrogen-canonicalize.cc
@@ -26,6 +26,7 @@
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include "hydrogen-canonicalize.h"
+#include "hydrogen-redundant-phi.h"
 
 namespace v8 {
 namespace internal {
@@ -57,8 +58,15 @@ void HCanonicalizePhase::Run() {
       }
     }
   }
+
   // Perform actual Canonicalization pass.
+  HRedundantPhiEliminationPhase redundant_phi_eliminator(graph());
   for (int i = 0; i < blocks->length(); ++i) {
+    // Eliminate redundant phis in the block first; changes to their inputs
+    // might have made them redundant, and eliminating them creates more
+    // opportunities for constant folding and strength reduction.
+    redundant_phi_eliminator.ProcessBlock(blocks->at(i));
+    // Now canonicalize each instruction.
     for (HInstructionIterator it(blocks->at(i)); !it.Done(); it.Advance()) {
       HInstruction* instr = it.Current();
       HValue* value = instr->Canonicalize();
diff --git a/src/hydrogen-redundant-phi.cc b/src/hydrogen-redundant-phi.cc
index 9c38200..1263833 100644
--- a/src/hydrogen-redundant-phi.cc
+++ b/src/hydrogen-redundant-phi.cc
@@ -31,37 +31,18 @@ namespace v8 {
 namespace internal {
 
 void HRedundantPhiEliminationPhase::Run() {
-  // We do a simple fixed point iteration without any work list, because
-  // machine-generated JavaScript can lead to a very dense Hydrogen graph with
-  // an enormous work list and will consequently result in OOM. Experiments
-  // showed that this simple algorithm is good enough, and even e.g. tracking
-  // the set or range of blocks to consider is not a real improvement.
-  bool need_another_iteration;
+  // Gather all phis from all blocks first.
   const ZoneList<HBasicBlock*>* blocks(graph()->blocks());
-  ZoneList<HPhi*> redundant_phis(blocks->length(), zone());
-  do {
-    need_another_iteration = false;
-    for (int i = 0; i < blocks->length(); ++i) {
-      HBasicBlock* block = blocks->at(i);
-      for (int j = 0; j < block->phis()->length(); j++) {
-        HPhi* phi = block->phis()->at(j);
-        HValue* replacement = phi->GetRedundantReplacement();
-        if (replacement != NULL) {
-          // Remember phi to avoid concurrent modification of the block's phis.
-          redundant_phis.Add(phi, zone());
-          for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
-            HValue* value = it.value();
-            value->SetOperandAt(it.index(), replacement);
-            need_another_iteration |= value->IsPhi();
-          }
-        }
-      }
-      for (int i = 0; i < redundant_phis.length(); i++) {
-        block->RemovePhi(redundant_phis[i]);
-      }
-      redundant_phis.Clear();
+  ZoneList<HPhi*> all_phis(blocks->length(), zone());
+  for (int i = 0; i < blocks->length(); ++i) {
+    HBasicBlock* block = blocks->at(i);
+    for (int j = 0; j < block->phis()->length(); j++) {
+      all_phis.Add(block->phis()->at(j), zone());
     }
-  } while (need_another_iteration);
+  }
+
+  // Iteratively reduce all phis in the list.
+  ProcessPhis(&all_phis);
 
 #if DEBUG
   // Make sure that we *really* removed all redundant phis.
@@ -73,4 +54,35 @@ void HRedundantPhiEliminationPhase::Run() {
 #endif
 }
 
+
+void HRedundantPhiEliminationPhase::ProcessBlock(HBasicBlock* block) {
+  ProcessPhis(block->phis());
+}
+
+
+void HRedundantPhiEliminationPhase::ProcessPhis(const ZoneList<HPhi*>* phis) {
+  bool updated;
+  do {
+    // Iterately replace all redundant phis in the given list.
+    updated = false;
+    for (int i = 0; i < phis->length(); i++) {
+      HPhi* phi = phis->at(i);
+      if (phi->CheckFlag(HValue::kIsDead)) continue;  // Already replaced.
+
+      HValue* replacement = phi->GetRedundantReplacement();
+      if (replacement != NULL) {
+        phi->SetFlag(HValue::kIsDead);
+        for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
+          HValue* value = it.value();
+          value->SetOperandAt(it.index(), replacement);
+          // Iterate again if used in another non-dead phi.
+          updated |= value->IsPhi() && !value->CheckFlag(HValue::kIsDead);
+        }
+        phi->block()->RemovePhi(phi);
+      }
+    }
+  } while (updated);
+}
+
+
 } }  // namespace v8::internal
diff --git a/src/hydrogen-redundant-phi.h b/src/hydrogen-redundant-phi.h
index 6291fa5..960ae69 100644
--- a/src/hydrogen-redundant-phi.h
+++ b/src/hydrogen-redundant-phi.h
@@ -42,8 +42,11 @@ class HRedundantPhiEliminationPhase : public HPhase {
       : HPhase("H_Redundant phi elimination", graph) { }
 
   void Run();
+  void ProcessBlock(HBasicBlock* block);
 
  private:
+  void ProcessPhis(const ZoneList<HPhi*>* phis);
+
   DISALLOW_COPY_AND_ASSIGN(HRedundantPhiEliminationPhase);
 };
 
-- 
2.7.4