From f46da9d43be69fc3ba16b893d41419f116433657 Mon Sep 17 00:00:00 2001 From: "ishell@chromium.org" Date: Mon, 10 Feb 2014 15:32:54 +0000 Subject: [PATCH] Reland of r19102: Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing implemented with tests. R=verwaest@chromium.org Review URL: https://codereview.chromium.org/146623006 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@19229 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-check-elimination.cc | 81 +++++++++++-- src/hydrogen-instructions.h | 12 +- .../{compare_map_elim.js => compare-map-elim.js} | 0 ...{compare_objeq_elim.js => compare-map-elim2.js} | 131 ++++++++++++++------- 4 files changed, 167 insertions(+), 57 deletions(-) rename test/mjsunit/compiler/{compare_map_elim.js => compare-map-elim.js} (100%) rename test/mjsunit/compiler/{compare_objeq_elim.js => compare-map-elim2.js} (52%) diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc index e12f14a..5d1323b 100644 --- a/src/hydrogen-check-elimination.cc +++ b/src/hydrogen-check-elimination.cc @@ -48,12 +48,12 @@ typedef UniqueSet* MapSet; struct HCheckTableEntry { HValue* object_; // The object being approximated. NULL => invalid entry. - HValue* check_; // The last check instruction. - MapSet maps_; // The set of known maps for the object. + HInstruction* check_; // The last check instruction. + MapSet maps_; // The set of known maps for the object. }; -// The main datastructure used during check elimination, which stores a +// The main data structure used during check elimination, which stores a // set of known maps for each object. class HCheckTable : public ZoneObject { public: @@ -130,6 +130,23 @@ class HCheckTable : public ZoneObject { copy->cursor_ = cursor_; copy->size_ = size_; + // Create entries for succ block's phis. + if (succ->phis()->length() > 0) { + int pred_index = succ->PredecessorIndexOf(from_block); + for (int phi_index = 0; + phi_index < succ->phis()->length(); + ++phi_index) { + HPhi* phi = succ->phis()->at(phi_index); + HValue* phi_operand = phi->OperandAt(pred_index); + + HCheckTableEntry* pred_entry = copy->Find(phi_operand); + if (pred_entry != NULL) { + // Create an entry for a phi in the table. + copy->Insert(phi, NULL, pred_entry->maps_->Copy(phase_->zone())); + } + } + } + // Branch-sensitive analysis for certain comparisons may add more facts // to the state for the successor on the true branch. bool learned = false; @@ -185,17 +202,28 @@ class HCheckTable : public ZoneObject { // Global analysis: Merge this state with the other incoming state. HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, - HBasicBlock* that_block, Zone* zone) { - if (that_block->IsReachable()) { + HBasicBlock* pred_block, Zone* zone) { + if (pred_block->IsReachable()) { if (that->size_ == 0) { // If the other state is empty, simply reset. size_ = 0; cursor_ = 0; } else { + int pred_index = succ->PredecessorIndexOf(pred_block); bool compact = false; for (int i = 0; i < size_; i++) { HCheckTableEntry* this_entry = &entries_[i]; - HCheckTableEntry* that_entry = that->Find(this_entry->object_); + HCheckTableEntry* that_entry; + if (this_entry->object_->IsPhi() && + this_entry->object_->block() == succ) { + HPhi* phi = HPhi::cast(this_entry->object_); + HValue* phi_operand = phi->OperandAt(pred_index); + that_entry = that->Find(phi_operand); + + } else { + that_entry = that->Find(this_entry->object_); + } + if (that_entry == NULL) { this_entry->object_ = NULL; compact = true; @@ -213,7 +241,7 @@ class HCheckTable : public ZoneObject { } if (FLAG_trace_check_elimination) { PrintF("B%d checkmaps-table merged with B%d table:\n", - succ->block_id(), that_block->block_id()); + succ->block_id(), pred_block->block_id()); Print(); } return this; @@ -244,14 +272,41 @@ class HCheckTable : public ZoneObject { } return; } - i = i->Intersect(a, phase_->zone()); - if (i->size() == 0) { + MapSet intersection = i->Intersect(a, phase_->zone()); + if (intersection->size() == 0) { // Intersection is empty; probably megamorphic, which is likely to // deopt anyway, so just leave things as they are. INC_STAT(empty_); } else { - // TODO(titzer): replace the first check with a more strict check - INC_STAT(narrowed_); + // Update set of maps in the entry. + entry->maps_ = intersection; + if (intersection->size() != i->size()) { + // Narrow set of maps in the second check maps instruction. + HGraph* graph = instr->block()->graph(); + if (entry->check_ != NULL && + entry->check_->block() == instr->block() && + entry->check_->IsCheckMaps()) { + // There is a check in the same block so replace it with a more + // strict check and eliminate the second check entirely. + HCheckMaps* check = HCheckMaps::cast(entry->check_); + TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(), + check->block()->block_id())); + check->set_map_set(intersection, graph->zone()); + TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", + instr->id(), instr->block()->block_id(), entry->check_->id())); + instr->DeleteAndReplaceWith(entry->check_); + } else { + TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(), + instr->block()->block_id())); + instr->set_map_set(intersection, graph->zone()); + entry->check_ = instr; + } + + if (FLAG_trace_check_elimination) { + Print(); + } + INC_STAT(narrowed_); + } } } else { // No entry; insert a new one. @@ -426,7 +481,9 @@ class HCheckTable : public ZoneObject { for (int i = 0; i < size_; i++) { HCheckTableEntry* entry = &entries_[i]; ASSERT(entry->object_ != NULL); - PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); + PrintF(" checkmaps-table @%d: %s #%d ", i, + entry->object_->IsPhi() ? "phi" : "object", + entry->object_->id()); if (entry->check_ != NULL) { PrintF("check #%d ", entry->check_->id()); } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index b1dc88a..9073ac3 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -2651,10 +2651,10 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { public: static HCheckMaps* New(Zone* zone, HValue* context, HValue* value, Handle map, CompilationInfo* info, - HValue *typecheck = NULL); + HValue* typecheck = NULL); static HCheckMaps* New(Zone* zone, HValue* context, HValue* value, SmallMapList* maps, - HValue *typecheck = NULL) { + HValue* typecheck = NULL) { HCheckMaps* check_map = new(zone) HCheckMaps(value, zone, typecheck); for (int i = 0; i < maps->length(); i++) { check_map->Add(maps->at(i), zone); @@ -2673,10 +2673,18 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE; HValue* value() { return OperandAt(0); } + HValue* typecheck() { return OperandAt(1); } Unique first_map() const { return map_set_.at(0); } UniqueSet map_set() const { return map_set_; } + void set_map_set(UniqueSet* maps, Zone *zone) { + map_set_.Clear(); + for (int i = 0; i < maps->size(); i++) { + map_set_.Add(maps->at(i), zone); + } + } + bool has_migration_target() const { return has_migration_target_; } diff --git a/test/mjsunit/compiler/compare_map_elim.js b/test/mjsunit/compiler/compare-map-elim.js similarity index 100% rename from test/mjsunit/compiler/compare_map_elim.js rename to test/mjsunit/compiler/compare-map-elim.js diff --git a/test/mjsunit/compiler/compare_objeq_elim.js b/test/mjsunit/compiler/compare-map-elim2.js similarity index 52% rename from test/mjsunit/compiler/compare_objeq_elim.js rename to test/mjsunit/compiler/compare-map-elim2.js index 4492df4..0c0540c 100644 --- a/test/mjsunit/compiler/compare_objeq_elim.js +++ b/test/mjsunit/compiler/compare-map-elim2.js @@ -27,59 +27,104 @@ // Flags: --allow-natives-syntax --check-elimination -function A(x, y) { - this.x = x; - this.y = y; -} -function B(x, y) { - this.x = x; - this.y = y; -} +function test_empty() { + function foo(o) { + return { value: o.value }; + } -function F1(a, b) { - if (a == b) return a.x; - else return b.x; -} + function Base() { + this.v_ = 5; + } + Base.prototype.__defineGetter__("value", function() { return 1; }); -function F2(a, b) { - if (a == b) return a.x; - else return b.x; -} + var a = new Base(); + a.a = 1; + foo(a); -function F3(a, b) { - var f = a.y; - if (a == b) return a.x; - else return b.x; -} + Base.prototype.__defineGetter__("value", function() { return this.v_; }); + + var b = new Base(); + b.b = 1; + foo(b); -function F4(a, b) { - var f = b.y; - if (a == b) return a.x; - else return b.x; + var d = new Base(); + d.d = 1; + d.value; + + %OptimizeFunctionOnNextCall(foo); + + var o = foo(b); } -%NeverOptimizeFunction(test); -function test(f, a, b) { - f(a, a); - f(a, b); - f(b, a); - f(b, c); - f(b, b); - f(c, c); +function test_narrow1() { + function foo(o) { + return { value: o.value }; + } + + function Base() { + this.v_ = 5; + } + Base.prototype.__defineGetter__("value", function() { return 1; }); + + var a = new Base(); + a.a = 1; + foo(a); + + Base.prototype.__defineGetter__("value", function() { return this.v_; }); + + var b = new Base(); + b.b = 1; + foo(b); - %OptimizeFunctionOnNextCall(f) + var c = new Base(); + c.c = 1; + foo(c); - assertEquals(a.x, f(a, a)); - assertEquals(b.x, f(b, b)); + var d = new Base(); + d.d = 1; + d.value; + + %OptimizeFunctionOnNextCall(foo); + + var o = foo(b); } -var a = new A(3, 5); -var b = new B(2, 6); -var c = new A(1, 7); -test(F1, a, c); -test(F2, a, b); -test(F3, a, b); -test(F4, a, b); +function test_narrow2() { + function foo(o, flag) { + return { value: o.value(flag) }; + } + + function Base() { + this.v_ = 5; + } + Base.prototype.value = function(flag) { return flag ? this.v_ : this.v_; }; + + + var a = new Base(); + a.a = 1; + foo(a, false); + foo(a, false); + + var b = new Base(); + b.b = 1; + foo(b, true); + + var c = new Base(); + c.c = 1; + foo(c, true); + + var d = new Base(); + d.d = 1; + d.value(true); + + %OptimizeFunctionOnNextCall(foo); + + var o = foo(b); +} + +test_empty(); +test_narrow1(); +test_narrow2(); -- 2.7.4