Reviewers: titzer, danno,
Description:
Perform a fix point iteration for GVN.
BUG=
Please review this at https://codereview.chromium.org/149573014/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+42, -22 lines):
M src/flag-definitions.h
M src/hydrogen-gvn.h
M src/hydrogen-gvn.cc
M src/hydrogen-instructions.h
M src/hydrogen-instructions.cc
Index: src/flag-definitions.h
diff --git a/src/flag-definitions.h b/src/flag-definitions.h
index
efd8d53509e8b344e27f1f56f1411bdfdcda561e..25af921196baa61e85d0414129d454ddfa5a75ef
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")
Index: src/hydrogen-gvn.cc
diff --git a/src/hydrogen-gvn.cc b/src/hydrogen-gvn.cc
index
3ad93129cd9c981fd9d61784ce1011335a21d4a9..905fd86c99034175836445d3379ee701f3c387ab
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;
+ }
}
}
}
Index: src/hydrogen-gvn.h
diff --git a/src/hydrogen-gvn.h b/src/hydrogen-gvn.h
index
fdbad99c6bb4de6d2250dd427ef05ef5b6877ead..23b24404084d76c0471c6551999732a3f4d53b18
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,
Index: src/hydrogen-instructions.cc
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index
c25dff121734a72538da33a13daec2db7110459c..ed506be8c064b2462ec5a9fb80d7ba81e4c6bf2c
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;
}
Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index
a6da1c3a75e9b3ceb3abc8264608687180e8f9da..c0ca21cbabf65fb7b961585dc862a1fb6712ae7e
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.
@@ -2664,7 +2666,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;
@@ -5332,7 +5334,7 @@ class HAllocate V8_FINAL : public
HTemplateInstruction<2> {
flags_ = static_cast<HAllocate::Flags>(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;
@@ -6444,10 +6446,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;
@@ -6674,10 +6677,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_; }
--
--
v8-dev mailing list
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
