Reviewers: Toon Verwaest,
Description:
Simplify redundant phi elimination and use during canonicalization too.
BUG=
Please review this at https://codereview.chromium.org/25896006/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+49, -29 lines):
M src/hydrogen-canonicalize.cc
M src/hydrogen-redundant-phi.h
M src/hydrogen-redundant-phi.cc
Index: src/hydrogen-canonicalize.cc
diff --git a/src/hydrogen-canonicalize.cc b/src/hydrogen-canonicalize.cc
index
4d96415e6a8142b40a2e74ed6c17011bb18bf071..faeba2b4c29568e199f2bd2a973b0a28f56927e2
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,13 @@ 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.
+ 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();
Index: src/hydrogen-redundant-phi.cc
diff --git a/src/hydrogen-redundant-phi.cc b/src/hydrogen-redundant-phi.cc
index
9c38200577d4994e79f5e1925039ca10a8c8a8c2..753da01897a856f69cdfcf094fb378a38f381144
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,34 @@ 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) {
+ for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
+ HValue* value = it.value();
+ value->SetOperandAt(it.index(), replacement);
+ updated |= value->IsPhi(); // Iterate again if used in another
phi.
+ }
+ phi->SetFlag(HValue::kIsDead);
+ phi->block()->RemovePhi(phi);
+ }
+ }
+ } while (updated);
+}
+
+
} } // namespace v8::internal
Index: src/hydrogen-redundant-phi.h
diff --git a/src/hydrogen-redundant-phi.h b/src/hydrogen-redundant-phi.h
index
6291fa5b7871e4d0612e8e680ce4e5e7db8f6685..960ae69c95f15b9dfaad4ae2322fa9a7a82a5a1f
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);
};
--
--
v8-dev mailing list
v8-dev@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to v8-dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.