From 12ba2dd435e54ac4f5c2767a66940378fb1f2cf6 Mon Sep 17 00:00:00 2001 From: "fschneider@chromium.org" Date: Tue, 8 Mar 2011 10:04:23 +0000 Subject: [PATCH] Improve dead phi elimination. This change splits the existing phi elimination into two phases: 1. Remove redundant phis 2. Remove dead phis with a fixed point iteration. The new approach allows us to remove dead phis that are connected in a cycle. Review URL: http://codereview.chromium.org/6624061 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7085 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-instructions.cc | 8 ++++++ src/hydrogen-instructions.h | 23 ++++++++++------ src/hydrogen.cc | 65 ++++++++++++++++++++++++++++++++------------ src/hydrogen.h | 1 + 4 files changed, 71 insertions(+), 26 deletions(-) diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index c2e5c8b..2e4d7ed 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -933,6 +933,14 @@ void HPhi::AddInput(HValue* value) { } +bool HPhi::HasRealUses() { + for (int i = 0; i < uses()->length(); i++) { + if (!uses()->at(i)->IsPhi()) return true; + } + return false; +} + + HValue* HPhi::GetRedundantReplacement() { HValue* candidate = NULL; int count = OperandCount(); diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index cc75354..f3e3815 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -461,9 +461,9 @@ class HValue: public ZoneObject { int id() const { return id_; } void set_id(int id) { id_ = id; } - const ZoneList* uses() const { return &uses_; } + ZoneList* uses() { return &uses_; } - virtual bool EmitAtUses() const { return false; } + virtual bool EmitAtUses() { return false; } Representation representation() const { return representation_; } void ChangeRepresentation(Representation r) { // Representation was already set and is allowed to be changed. @@ -1800,7 +1800,8 @@ class HPhi: public HValue { explicit HPhi(int merged_index) : inputs_(2), merged_index_(merged_index), - phi_id_(-1) { + phi_id_(-1), + is_live_(false) { for (int i = 0; i < Representation::kNumRepresentations; i++) { non_phi_uses_[i] = 0; indirect_uses_[i] = 0; @@ -1834,6 +1835,7 @@ class HPhi: public HValue { virtual HValue* OperandAt(int index) { return inputs_[index]; } HValue* GetRedundantReplacement(); void AddInput(HValue* value); + bool HasRealUses(); bool IsReceiver() { return merged_index_ == 0; } @@ -1872,6 +1874,8 @@ class HPhi: public HValue { return indirect_uses_[Representation::kDouble]; } int phi_id() { return phi_id_; } + bool is_live() { return is_live_; } + void set_is_live(bool b) { is_live_ = b; } protected: virtual void DeleteFromGraph(); @@ -1886,6 +1890,7 @@ class HPhi: public HValue { int non_phi_uses_[Representation::kNumRepresentations]; int indirect_uses_[Representation::kNumRepresentations]; int phi_id_; + bool is_live_; }; @@ -1916,7 +1921,7 @@ class HConstant: public HTemplateInstruction<0> { return Representation::None(); } - virtual bool EmitAtUses() const { return !representation().IsDouble(); } + virtual bool EmitAtUses() { return !representation().IsDouble(); } virtual void PrintDataTo(StringStream* stream); virtual HType CalculateInferredType(); bool IsInteger() const { return handle_->IsSmi(); } @@ -2191,7 +2196,7 @@ class HCompare: public HBinaryOperation { void SetInputRepresentation(Representation r); - virtual bool EmitAtUses() const { + virtual bool EmitAtUses() { return !HasSideEffects() && (uses()->length() <= 1); } @@ -2232,7 +2237,7 @@ class HCompareJSObjectEq: public HBinaryOperation { SetFlag(kUseGVN); } - virtual bool EmitAtUses() const { + virtual bool EmitAtUses() { return !HasSideEffects() && (uses()->length() <= 1); } @@ -2255,7 +2260,7 @@ class HUnaryPredicate: public HUnaryOperation { SetFlag(kUseGVN); } - virtual bool EmitAtUses() const { + virtual bool EmitAtUses() { return !HasSideEffects() && (uses()->length() <= 1); } @@ -2315,7 +2320,7 @@ class HIsConstructCall: public HTemplateInstruction<0> { SetFlag(kUseGVN); } - virtual bool EmitAtUses() const { + virtual bool EmitAtUses() { return !HasSideEffects() && (uses()->length() <= 1); } @@ -2437,7 +2442,7 @@ class HInstanceOf: public HTemplateInstruction<3> { HValue* left() { return OperandAt(1); } HValue* right() { return OperandAt(2); } - virtual bool EmitAtUses() const { + virtual bool EmitAtUses() { return !HasSideEffects() && (uses()->length() <= 1); } diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 308a2c3..ed963dc 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -92,7 +92,7 @@ void HBasicBlock::AddPhi(HPhi* phi) { 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); @@ -703,8 +703,7 @@ void HGraph::AssignDominators() { void HGraph::EliminateRedundantPhis() { - HPhase phase("Phi elimination", this); - ZoneList uses_to_replace(2); + HPhase phase("Redundant phi elimination", this); // Worklist of phis that can potentially be eliminated. Initialized // with all phi nodes. When elimination of a phi node modifies @@ -727,26 +726,57 @@ void HGraph::EliminateRedundantPhis() { if (value != NULL) { // Iterate through uses finding the ones that should be // replaced. - const ZoneList* uses = phi->uses(); - for (int i = 0; i < uses->length(); ++i) { - HValue* use = uses->at(i); - if (!use->block()->IsStartBlock()) { - uses_to_replace.Add(use); + ZoneList* uses = phi->uses(); + while (!uses->is_empty()) { + HValue* use = uses->RemoveLast(); + if (use != NULL) { + phi->ReplaceAtUse(use, value); + if (use->IsPhi()) worklist.Add(HPhi::cast(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::EliminateUnreachablePhis() { + HPhase phase("Unreachable phi elimination", this); + + // Initialize worklist. + ZoneList phi_list(blocks_.length()); + ZoneList 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 unreachable phis. + for (int i = 0; i < phi_list.length(); i++) { + HPhi* phi = phi_list[i]; + if (!phi->is_live()) { + HBasicBlock* block = phi->block(); block->RemovePhi(phi); block->RecordDeletedPhi(phi->merged_index()); } @@ -2174,6 +2204,7 @@ HGraph* HGraphBuilder::CreateGraph() { graph()->OrderBlocks(); graph()->AssignDominators(); graph()->EliminateRedundantPhis(); + if (FLAG_eliminate_dead_phis) graph()->EliminateUnreachablePhis(); if (!graph()->CollectPhis()) { Bailout("Phi-use of arguments object"); return NULL; diff --git a/src/hydrogen.h b/src/hydrogen.h index 510ba70..5606fb3 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -234,6 +234,7 @@ class HGraph: public HSubgraph { void ComputeMinusZeroChecks(); bool ProcessArgumentsObject(); void EliminateRedundantPhis(); + void EliminateUnreachablePhis(); void Canonicalize(); void OrderBlocks(); void AssignDominators(); -- 2.7.4