From d2a2f835748148520494dc42df3f118aff2d6eef Mon Sep 17 00:00:00 2001 From: "hpayer@chromium.org" Date: Wed, 5 Feb 2014 17:21:34 +0000 Subject: [PATCH] Perform a fix point iteration for GVN. BUG= R=danno@chromium.org Review URL: https://codereview.chromium.org/149573014 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@19115 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 1 + src/hydrogen-gvn.cc | 18 ++++++++++++++++-- src/hydrogen-gvn.h | 11 +++++------ src/hydrogen-instructions.cc | 20 +++++++++++--------- src/hydrogen-instructions.h | 14 +++++++++----- 5 files changed, 42 insertions(+), 22 deletions(-) diff --git a/src/flag-definitions.h b/src/flag-definitions.h index efd8d53..25af921 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -247,6 +247,7 @@ DEFINE_bool(crankshaft, true, "use crankshaft") DEFINE_string(hydrogen_filter, "*", "optimization filter") DEFINE_bool(use_range, true, "use hydrogen range analysis") DEFINE_bool(use_gvn, true, "use hydrogen global value numbering") +DEFINE_int(gvn_iterations, 3, "maximum number of GVN fix-point iterations") DEFINE_bool(use_canonicalizing, true, "use hydrogen instruction canonicalizing") DEFINE_bool(use_inlining, true, "use function inlining") DEFINE_bool(use_escape_analysis, true, "use hydrogen escape analysis") diff --git a/src/hydrogen-gvn.cc b/src/hydrogen-gvn.cc index 3ad9312..905fd86 100644 --- a/src/hydrogen-gvn.cc +++ b/src/hydrogen-gvn.cc @@ -374,7 +374,19 @@ HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) zone()); loop_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(), zone()); - } +} + + +void HGlobalValueNumberingPhase::Reset() { + block_side_effects_.Clear(); + loop_side_effects_.Clear(); + visited_on_paths_.Clear(); + block_side_effects_.AddBlock(GVNFlagSet(), graph()->blocks()->length(), + zone()); + loop_side_effects_.AddBlock(GVNFlagSet(), graph()->blocks()->length(), + zone()); +} + void HGlobalValueNumberingPhase::Analyze() { removed_side_effects_ = false; @@ -791,7 +803,9 @@ void HGlobalValueNumberingPhase::AnalyzeGraph() { instr->Mnemonic(), other->id(), other->Mnemonic()); - instr->HandleSideEffectDominator(changes_flag, other); + if (instr->HandleSideEffectDominator(changes_flag, other)) { + removed_side_effects_ = true; + } } } } diff --git a/src/hydrogen-gvn.h b/src/hydrogen-gvn.h index fdbad99..23b2440 100644 --- a/src/hydrogen-gvn.h +++ b/src/hydrogen-gvn.h @@ -42,17 +42,16 @@ class HGlobalValueNumberingPhase : public HPhase { explicit HGlobalValueNumberingPhase(HGraph* graph); void Run() { - Analyze(); - // Trigger a second analysis pass to further eliminate duplicate values - // that could only be discovered by removing side-effect-generating - // instructions during the first pass. - if (FLAG_smi_only_arrays && removed_side_effects_) { + int max_fixpoint_iteration_count = FLAG_gvn_iterations; + for (int i = 0; i < max_fixpoint_iteration_count; i++) { Analyze(); - // TODO(danno): Turn this into a fixpoint iteration. + if (!removed_side_effects_) break; + Reset(); } } private: + void Reset(); void Analyze(); GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock( HBasicBlock* dominator, diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index c25dff1..ed506be 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -1514,7 +1514,7 @@ void HCheckInstanceType::GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag) { } -void HCheckMaps::HandleSideEffectDominator(GVNFlag side_effect, +bool HCheckMaps::HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) { ASSERT(side_effect == kChangesMaps); // TODO(mstarzinger): For now we specialize on HStoreNamedField, but once @@ -1522,13 +1522,14 @@ void HCheckMaps::HandleSideEffectDominator(GVNFlag side_effect, // for which the map is known. if (HasNoUses() && dominator->IsStoreNamedField()) { HStoreNamedField* store = HStoreNamedField::cast(dominator); - if (!store->has_transition() || store->object() != value()) return; + if (!store->has_transition() || store->object() != value()) return false; HConstant* transition = HConstant::cast(store->transition()); if (map_set_.Contains(transition->GetUnique())) { DeleteAndReplaceWith(NULL); - return; + return true; } } + return false; } @@ -3409,11 +3410,11 @@ Representation HUnaryMathOperation::RepresentationFromInputs() { } -void HAllocate::HandleSideEffectDominator(GVNFlag side_effect, +bool HAllocate::HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) { ASSERT(side_effect == kChangesNewSpacePromotion); Zone* zone = block()->zone(); - if (!FLAG_use_allocation_folding) return; + if (!FLAG_use_allocation_folding) return false; // Try to fold allocations together with their dominating allocations. if (!dominator->IsAllocate()) { @@ -3421,7 +3422,7 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect, PrintF("#%d (%s) cannot fold into #%d (%s)\n", id(), Mnemonic(), dominator->id(), dominator->Mnemonic()); } - return; + return false; } HAllocate* dominator_allocate = HAllocate::cast(dominator); @@ -3435,12 +3436,12 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect, PrintF("#%d (%s) cannot fold into #%d (%s), dynamic allocation size\n", id(), Mnemonic(), dominator->id(), dominator->Mnemonic()); } - return; + return false; } dominator_allocate = GetFoldableDominator(dominator_allocate); if (dominator_allocate == NULL) { - return; + return false; } ASSERT((IsNewSpaceAllocation() && @@ -3477,7 +3478,7 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect, id(), Mnemonic(), dominator_allocate->id(), dominator_allocate->Mnemonic(), new_dominator_size); } - return; + return false; } HInstruction* new_dominator_size_constant = HConstant::CreateAndInsertBefore( @@ -3525,6 +3526,7 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect, id(), Mnemonic(), dominator_allocate->id(), dominator_allocate->Mnemonic()); } + return true; } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index c351687..27fa3b9 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -875,9 +875,11 @@ class HValue : public ZoneObject { // This function must be overridden for instructions which have the // kTrackSideEffectDominators flag set, to track instructions that are // dominating side effects. - virtual void HandleSideEffectDominator(GVNFlag side_effect, + // It returns true if it removed an instruction which had side effects. + virtual bool HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) { UNREACHABLE(); + return false; } // Check if this instruction has some reason that prevents elimination. @@ -2680,7 +2682,7 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE { return Representation::Tagged(); } - virtual void HandleSideEffectDominator(GVNFlag side_effect, + virtual bool HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) V8_OVERRIDE; virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE; @@ -5349,7 +5351,7 @@ class HAllocate V8_FINAL : public HTemplateInstruction<2> { flags_ = static_cast(flags_ | ALLOCATE_DOUBLE_ALIGNED); } - virtual void HandleSideEffectDominator(GVNFlag side_effect, + virtual bool HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) V8_OVERRIDE; virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE; @@ -6461,10 +6463,11 @@ class HStoreNamedField V8_FINAL : public HTemplateInstruction<3> { } return Representation::Tagged(); } - virtual void HandleSideEffectDominator(GVNFlag side_effect, + virtual bool HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) V8_OVERRIDE { ASSERT(side_effect == kChangesNewSpacePromotion); new_space_dominator_ = dominator; + return false; } virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE; @@ -6691,10 +6694,11 @@ class HStoreKeyed V8_FINAL return value()->IsConstant() && HConstant::cast(value())->IsTheHole(); } - virtual void HandleSideEffectDominator(GVNFlag side_effect, + virtual bool HandleSideEffectDominator(GVNFlag side_effect, HValue* dominator) V8_OVERRIDE { ASSERT(side_effect == kChangesNewSpacePromotion); new_space_dominator_ = dominator; + return false; } HValue* new_space_dominator() const { return new_space_dominator_; } -- 2.7.4