Revision: 7085
Author: [email protected]
Date: Tue Mar 8 02:04:23 2011
Log: 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
http://code.google.com/p/v8/source/detail?r=7085
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/hydrogen.h
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Fri Mar 4
04:09:54 2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Mar 8
02:04:23 2011
@@ -931,6 +931,14 @@
SetFlag(kIsArguments);
}
}
+
+
+bool HPhi::HasRealUses() {
+ for (int i = 0; i < uses()->length(); i++) {
+ if (!uses()->at(i)->IsPhi()) return true;
+ }
+ return false;
+}
HValue* HPhi::GetRedundantReplacement() {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Fri Mar 4 04:09:54
2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Tue Mar 8 02:04:23
2011
@@ -461,9 +461,9 @@
int id() const { return id_; }
void set_id(int id) { id_ = id; }
- const ZoneList<HValue*>* uses() const { return &uses_; }
-
- virtual bool EmitAtUses() const { return false; }
+ ZoneList<HValue*>* uses() { return &uses_; }
+
+ 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 @@
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 @@
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 @@
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 @@
int non_phi_uses_[Representation::kNumRepresentations];
int indirect_uses_[Representation::kNumRepresentations];
int phi_id_;
+ bool is_live_;
};
@@ -1916,7 +1921,7 @@
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 @@
void SetInputRepresentation(Representation r);
- virtual bool EmitAtUses() const {
+ virtual bool EmitAtUses() {
return !HasSideEffects() && (uses()->length() <= 1);
}
@@ -2232,7 +2237,7 @@
SetFlag(kUseGVN);
}
- virtual bool EmitAtUses() const {
+ virtual bool EmitAtUses() {
return !HasSideEffects() && (uses()->length() <= 1);
}
@@ -2255,7 +2260,7 @@
SetFlag(kUseGVN);
}
- virtual bool EmitAtUses() const {
+ virtual bool EmitAtUses() {
return !HasSideEffects() && (uses()->length() <= 1);
}
@@ -2315,7 +2320,7 @@
SetFlag(kUseGVN);
}
- virtual bool EmitAtUses() const {
+ virtual bool EmitAtUses() {
return !HasSideEffects() && (uses()->length() <= 1);
}
@@ -2437,7 +2442,7 @@
HValue* left() { return OperandAt(1); }
HValue* right() { return OperandAt(2); }
- virtual bool EmitAtUses() const {
+ virtual bool EmitAtUses() {
return !HasSideEffects() && (uses()->length() <= 1);
}
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Mon Mar 7 11:23:46 2011
+++ /branches/bleeding_edge/src/hydrogen.cc Tue Mar 8 02:04:23 2011
@@ -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);
@@ -703,8 +703,7 @@
void HGraph::EliminateRedundantPhis() {
- HPhase phase("Phi elimination", this);
- ZoneList<HValue*> 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 @@
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) {
- HValue* use = uses->at(i);
- if (!use->block()->IsStartBlock()) {
- uses_to_replace.Add(use);
+ ZoneList<HValue*>* 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<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 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 @@
graph()->OrderBlocks();
graph()->AssignDominators();
graph()->EliminateRedundantPhis();
+ if (FLAG_eliminate_dead_phis) graph()->EliminateUnreachablePhis();
if (!graph()->CollectPhis()) {
Bailout("Phi-use of arguments object");
return NULL;
=======================================
--- /branches/bleeding_edge/src/hydrogen.h Mon Mar 7 07:42:23 2011
+++ /branches/bleeding_edge/src/hydrogen.h Tue Mar 8 02:04:23 2011
@@ -234,6 +234,7 @@
void ComputeMinusZeroChecks();
bool ProcessArgumentsObject();
void EliminateRedundantPhis();
+ void EliminateUnreachablePhis();
void Canonicalize();
void OrderBlocks();
void AssignDominators();
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
