Reviewers: Kevin Millikin,
Description:
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.
Please review this at http://codereview.chromium.org/6624061/
SVN Base: http://v8.googlecode.com/svn/branches/bleeding_edge/
Affected files:
M src/hydrogen-instructions.h
M src/hydrogen-instructions.cc
M src/hydrogen.h
M src/hydrogen.cc
Index: src/hydrogen-instructions.cc
===================================================================
--- src/hydrogen-instructions.cc (revision 7081)
+++ src/hydrogen-instructions.cc (working copy)
@@ -933,6 +933,18 @@
}
+bool HPhi::HasRealUses() {
+ bool result = false;
+ for (int i = 0; i < uses()->length(); i++) {
+ if (!uses()->at(i)->IsPhi()) {
+ result = true;
+ break;
+ }
+ }
+ return result;
+}
+
+
HValue* HPhi::GetRedundantReplacement() {
HValue* candidate = NULL;
int count = OperandCount();
Index: src/hydrogen-instructions.h
===================================================================
--- src/hydrogen-instructions.h (revision 7081)
+++ src/hydrogen-instructions.h (working copy)
@@ -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_;
};
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) {
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;
Index: src/hydrogen.h
===================================================================
--- src/hydrogen.h (revision 7081)
+++ src/hydrogen.h (working copy)
@@ -234,6 +234,7 @@
void ComputeMinusZeroChecks();
bool ProcessArgumentsObject();
void EliminateRedundantPhis();
+ void EliminateDeadPhis();
void Canonicalize();
void OrderBlocks();
void AssignDominators();
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
