From 7c1036d4241690c8a7deda9be24ea495d0156dde Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 5 May 2014 06:53:19 +0000 Subject: [PATCH] Various cleanups in check elimination. - Move IsMapAccess() to HObjectAccess. - Collect the actual objects instead of HStoreNamedFields in effects, and also consider HTransitionElementsKind. - Fix ownership of HCheckMaps::maps() and HLoadNamedField::maps(). - Avoid heavy copying of the same map sets all the time during check elimination, and do something useful with the memory instead by slightly bumping the maximum number of tracked objects. - Slightly optimize UniqueSet::Contains(). R=svenpanne@chromium.org Review URL: https://codereview.chromium.org/264693011 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@21133 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/lithium-codegen-arm.cc | 8 +-- src/arm64/lithium-codegen-arm64.cc | 8 +-- src/hydrogen-check-elimination.cc | 116 ++++++++++++++++++------------------- src/hydrogen-escape-analysis.cc | 2 +- src/hydrogen-instructions.cc | 19 +++--- src/hydrogen-instructions.h | 92 ++++++++++++++--------------- src/hydrogen-load-elimination.cc | 4 +- src/ia32/lithium-codegen-ia32.cc | 8 +-- src/mips/lithium-codegen-mips.cc | 8 +-- src/unique.h | 36 ++++++++---- src/x64/lithium-codegen-x64.cc | 8 +-- 11 files changed, 159 insertions(+), 150 deletions(-) diff --git a/src/arm/lithium-codegen-arm.cc b/src/arm/lithium-codegen-arm.cc index 606d492..3eda962 100644 --- a/src/arm/lithium-codegen-arm.cc +++ b/src/arm/lithium-codegen-arm.cc @@ -5155,15 +5155,15 @@ void LCodeGen::DoCheckMaps(LCheckMaps* instr) { __ bind(deferred->check_maps()); } - const UniqueSet* map_set = instr->hydrogen()->map_set(); + const UniqueSet* maps = instr->hydrogen()->maps(); Label success; - for (int i = 0; i < map_set->size() - 1; i++) { - Handle map = map_set->at(i).handle(); + for (int i = 0; i < maps->size() - 1; i++) { + Handle map = maps->at(i).handle(); __ CompareMap(map_reg, map, &success); __ b(eq, &success); } - Handle map = map_set->at(map_set->size() - 1).handle(); + Handle map = maps->at(maps->size() - 1).handle(); __ CompareMap(map_reg, map, &success); if (instr->hydrogen()->has_migration_target()) { __ b(ne, deferred->entry()); diff --git a/src/arm64/lithium-codegen-arm64.cc b/src/arm64/lithium-codegen-arm64.cc index 1e4754a..76dd52a 100644 --- a/src/arm64/lithium-codegen-arm64.cc +++ b/src/arm64/lithium-codegen-arm64.cc @@ -2132,14 +2132,14 @@ void LCodeGen::DoCheckMaps(LCheckMaps* instr) { __ Bind(deferred->check_maps()); } - const UniqueSet* map_set = instr->hydrogen()->map_set(); + const UniqueSet* maps = instr->hydrogen()->maps(); Label success; - for (int i = 0; i < map_set->size() - 1; i++) { - Handle map = map_set->at(i).handle(); + for (int i = 0; i < maps->size() - 1; i++) { + Handle map = maps->at(i).handle(); __ CompareMap(map_reg, map); __ B(eq, &success); } - Handle map = map_set->at(map_set->size() - 1).handle(); + Handle map = maps->at(maps->size() - 1).handle(); __ CompareMap(map_reg, map); // We didn't match a map. diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc index 5d4b33b..fb7812e 100644 --- a/src/hydrogen-check-elimination.cc +++ b/src/hydrogen-check-elimination.cc @@ -21,7 +21,7 @@ namespace v8 { namespace internal { -typedef UniqueSet* MapSet; +typedef const UniqueSet* MapSet; struct HCheckTableEntry { HValue* object_; // The object being approximated. NULL => invalid entry. @@ -34,7 +34,7 @@ struct HCheckTableEntry { // set of known maps for each object. class HCheckTable : public ZoneObject { public: - static const int kMaxTrackedObjects = 10; + static const int kMaxTrackedObjects = 16; explicit HCheckTable(HCheckEliminationPhase* phase) : phase_(phase), @@ -80,7 +80,8 @@ class HCheckTable : public ZoneObject { } default: { // If the instruction changes maps uncontrollably, drop everything. - if (instr->CheckChangesFlag(kMaps) || + if (instr->CheckChangesFlag(kElementsKind) || + instr->CheckChangesFlag(kMaps) || instr->CheckChangesFlag(kOsrEntries)) { Kill(); } @@ -127,13 +128,13 @@ class HCheckTable : public ZoneObject { private: // Copy state to successor block. HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { - HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_); + HCheckTable* copy = new(zone) HCheckTable(phase_); for (int i = 0; i < size_; i++) { HCheckTableEntry* old_entry = &entries_[i]; ASSERT(old_entry->maps_->size() > 0); HCheckTableEntry* new_entry = ©->entries_[i]; new_entry->object_ = old_entry->object_; - new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); + new_entry->maps_ = old_entry->maps_; // Keep the check if the existing check's block dominates the successor. if (old_entry->check_ != NULL && old_entry->check_->block()->Dominates(succ)) { @@ -159,7 +160,7 @@ class HCheckTable : public ZoneObject { 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())); + copy->Insert(phi, NULL, pred_entry->maps_); } } } @@ -179,15 +180,15 @@ class HCheckTable : public ZoneObject { if (entry == NULL) { copy->Insert(object, cmp, cmp->map()); } else { - MapSet list = new(phase_->zone()) UniqueSet(); - list->Add(cmp->map(), phase_->zone()); - entry->maps_ = list; + entry->maps_ = new(zone) UniqueSet(cmp->map(), zone); entry->check_ = cmp; } } else { // Learn on the false branch of if(CompareMap(x)). if (entry != NULL) { - entry->maps_->Remove(cmp->map()); + UniqueSet* maps = entry->maps_->Copy(zone); + maps->Remove(cmp->map()); + entry->maps_ = maps; } } learned = true; @@ -201,14 +202,12 @@ class HCheckTable : public ZoneObject { HCheckTableEntry* re = copy->Find(right); if (le == NULL) { if (re != NULL) { - copy->Insert(left, NULL, re->maps_->Copy(zone)); + copy->Insert(left, NULL, re->maps_); } } else if (re == NULL) { - copy->Insert(right, NULL, le->maps_->Copy(zone)); + copy->Insert(right, NULL, le->maps_); } else { - MapSet intersect = le->maps_->Intersect(re->maps_, zone); - le->maps_ = intersect; - re->maps_ = intersect->Copy(zone); + le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone); } learned = true; } @@ -254,7 +253,7 @@ class HCheckTable : public ZoneObject { compact = true; } else { this_entry->maps_ = - this_entry->maps_->Union(that_entry->maps_, phase_->zone()); + this_entry->maps_->Union(that_entry->maps_, zone); if (this_entry->check_ != that_entry->check_) { this_entry->check_ = NULL; } @@ -278,7 +277,7 @@ class HCheckTable : public ZoneObject { if (entry != NULL) { // entry found; MapSet a = entry->maps_; - const UniqueSet* i = instr->map_set(); + const UniqueSet* i = instr->maps(); if (a->IsSubset(i)) { // The first check is more strict; the second is redundant. if (entry->check_ != NULL) { @@ -297,7 +296,8 @@ class HCheckTable : public ZoneObject { } return; } - MapSet intersection = i->Intersect(a, phase_->zone()); + HGraph* graph = instr->block()->graph(); + MapSet intersection = i->Intersect(a, graph->zone()); if (intersection->size() == 0) { // Intersection is empty; probably megamorphic, which is likely to // deopt anyway, so just leave things as they are. @@ -307,7 +307,6 @@ class HCheckTable : public ZoneObject { 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()) { @@ -317,7 +316,7 @@ class HCheckTable : public ZoneObject { TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(), check->block()->block_id())); // Update map set and ensure that the check is alive. - check->set_map_set(intersection, graph->zone()); + check->set_maps(intersection); check->ClearFlag(HValue::kIsDead); TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", instr->id(), instr->block()->block_id(), entry->check_->id())); @@ -325,7 +324,7 @@ class HCheckTable : public ZoneObject { } else { TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(), instr->block()->block_id())); - instr->set_map_set(intersection, graph->zone()); + instr->set_maps(intersection); entry->check_ = instr; } @@ -337,16 +336,16 @@ class HCheckTable : public ZoneObject { } } else { // No entry; insert a new one. - Insert(object, instr, instr->map_set()->Copy(phase_->zone())); + Insert(object, instr, instr->maps()); } } void ReduceLoadNamedField(HLoadNamedField* instr) { // Reduce a load of the map field when it is known to be a constant. - if (!IsMapAccess(instr->access())) { + if (!instr->access().IsMap()) { // Check if we introduce field maps here. - if (instr->map_set()->size() != 0) { - Insert(instr, instr, instr->map_set()->Copy(phase_->zone())); + if (instr->maps()->size() != 0) { + Insert(instr, instr, instr->maps()); } return; } @@ -371,9 +370,8 @@ class HCheckTable : public ZoneObject { HCheckTableEntry* entry = Find(object); if (entry != NULL) { - MapSet maps = entry->maps_; - if (maps->Contains(map)) { - if (maps->size() == 1) { + if (entry->maps_->Contains(map)) { + if (entry->maps_->size() == 1) { // Object is known to have exactly this map. if (entry->check_ != NULL) { instr->DeleteAndReplaceWith(entry->check_); @@ -386,8 +384,7 @@ class HCheckTable : public ZoneObject { INC_STAT(removed_); } else { // Only one map survives the check. - maps->Clear(); - maps->Add(map, phase_->zone()); + entry->maps_ = new(zone()) UniqueSet(map, zone()); entry->check_ = instr; } } @@ -411,7 +408,7 @@ class HCheckTable : public ZoneObject { // This store transitions the object to a new map. Kill(object); Insert(object, NULL, MapConstant(instr->transition())); - } else if (IsMapAccess(instr->access())) { + } else if (instr->access().IsMap()) { // This is a store directly to the map field of the object. Kill(object); if (!instr->value()->IsConstant()) return; @@ -455,7 +452,7 @@ class HCheckTable : public ZoneObject { if (maps_left == NULL) return; MapSet maps_right = FindMaps(instr->right()->ActualValue()); if (maps_right == NULL) return; - MapSet intersection = maps_left->Intersect(maps_right, phase_->zone()); + MapSet intersection = maps_left->Intersect(maps_right, zone()); if (intersection->size() > 0) return; TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n", @@ -468,13 +465,15 @@ class HCheckTable : public ZoneObject { } void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { - MapSet maps = FindMaps(instr->object()->ActualValue()); + HCheckTableEntry* entry = Find(instr->object()->ActualValue()); // Can only learn more about an object that already has a known set of maps. - if (maps == NULL) return; - if (maps->Contains(instr->original_map())) { + if (entry == NULL) return; + if (entry->maps_->Contains(instr->original_map())) { // If the object has the original map, it will be transitioned. + UniqueSet* maps = entry->maps_->Copy(zone()); maps->Remove(instr->original_map()); - maps->Add(instr->transitioned_map(), phase_->zone()); + maps->Add(instr->transitioned_map(), zone()); + entry->maps_ = maps; } else { // Object does not have the given map, thus the transition is redundant. instr->DeleteAndReplaceWith(instr->object()); @@ -575,9 +574,7 @@ class HCheckTable : public ZoneObject { } void Insert(HValue* object, HInstruction* check, Unique map) { - MapSet list = new(phase_->zone()) UniqueSet(); - list->Add(map, phase_->zone()); - Insert(object, check, list); + Insert(object, check, new(zone()) UniqueSet(map, zone())); } void Insert(HValue* object, HInstruction* check, MapSet maps) { @@ -590,14 +587,12 @@ class HCheckTable : public ZoneObject { if (size_ < kMaxTrackedObjects) size_++; } - bool IsMapAccess(HObjectAccess access) { - return access.IsInobject() && access.offset() == JSObject::kMapOffset; - } - Unique MapConstant(HValue* value) { return Unique::cast(HConstant::cast(value)->GetUnique()); } + Zone* zone() const { return phase_->zone(); } + friend class HCheckMapsEffects; friend class HCheckEliminationPhase; @@ -614,26 +609,28 @@ class HCheckTable : public ZoneObject { class HCheckMapsEffects : public ZoneObject { public: explicit HCheckMapsEffects(Zone* zone) - : maps_stored_(false), - stores_(5, zone) { } + : objects_(0, zone), maps_stored_(false) {} - inline bool Disabled() { - return false; // Effects are _not_ disabled. - } + // Effects are _not_ disabled. + inline bool Disabled() const { return false; } // Process a possibly side-effecting instruction. void Process(HInstruction* instr, Zone* zone) { switch (instr->opcode()) { case HValue::kStoreNamedField: { - stores_.Add(HStoreNamedField::cast(instr), zone); + HStoreNamedField* store = HStoreNamedField::cast(instr); + if (store->access().IsMap() && store->has_transition()) { + objects_.Add(store->object(), zone); + } break; } - case HValue::kOsrEntry: { - // Kill everything. Loads must not be hoisted past the OSR entry. - maps_stored_ = true; + case HValue::kTransitionElementsKind: { + objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone); + break; } default: { maps_stored_ |= (instr->CheckChangesFlag(kMaps) | + instr->CheckChangesFlag(kOsrEntries) | instr->CheckChangesFlag(kElementsKind)); } } @@ -647,26 +644,23 @@ class HCheckMapsEffects : public ZoneObject { return; } - // Kill maps for each store contained in these effects. - for (int i = 0; i < stores_.length(); i++) { - HStoreNamedField* s = stores_[i]; - if (table->IsMapAccess(s->access()) || s->has_transition()) { - table->Kill(s->object()->ActualValue()); - } + // Kill maps for each object contained in these effects. + for (int i = 0; i < objects_.length(); ++i) { + table->Kill(objects_[i]->ActualValue()); } } // Union these effects with the other effects. void Union(HCheckMapsEffects* that, Zone* zone) { maps_stored_ |= that->maps_stored_; - for (int i = 0; i < that->stores_.length(); i++) { - stores_.Add(that->stores_[i], zone); + for (int i = 0; i < that->objects_.length(); ++i) { + objects_.Add(that->objects_[i], zone); } } private: + ZoneList objects_; bool maps_stored_ : 1; - ZoneList stores_; }; diff --git a/src/hydrogen-escape-analysis.cc b/src/hydrogen-escape-analysis.cc index 14e8bbf..8514d88 100644 --- a/src/hydrogen-escape-analysis.cc +++ b/src/hydrogen-escape-analysis.cc @@ -132,7 +132,7 @@ HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state, // TODO(mstarzinger): This will narrow a map check against a set of maps // down to the first element in the set. Revisit and fix this. HCheckValue* check = HCheckValue::New( - zone, NULL, value, mapcheck->first_map(), false); + zone, NULL, value, mapcheck->maps()->at(0), false); check->InsertBefore(mapcheck); return check; } diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 59b43b6..6cc704b 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -1671,9 +1671,9 @@ void HCheckInstanceType::GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag) { void HCheckMaps::PrintDataTo(StringStream* stream) { value()->PrintNameTo(stream); - stream->Add(" [%p", *map_set_.at(0).handle()); - for (int i = 1; i < map_set_.size(); ++i) { - stream->Add(",%p", *map_set_.at(i).handle()); + stream->Add(" [%p", *maps()->at(0).handle()); + for (int i = 1; i < maps()->size(); ++i) { + stream->Add(",%p", *maps()->at(i).handle()); } stream->Add("]%s", CanOmitMapChecks() ? "(omitted)" : ""); } @@ -3362,10 +3362,10 @@ void HLoadNamedField::PrintDataTo(StringStream* stream) { object()->PrintNameTo(stream); access_.PrintTo(stream); - if (map_set_.size() != 0) { - stream->Add(" [%p", *map_set_.at(0).handle()); - for (int i = 1; i < map_set_.size(); ++i) { - stream->Add(",%p", *map_set_.at(i).handle()); + if (maps()->size() != 0) { + stream->Add(" [%p", *maps()->at(0).handle()); + for (int i = 1; i < maps()->size(); ++i) { + stream->Add(",%p", *maps()->at(i).handle()); } stream->Add("]"); } @@ -3383,8 +3383,9 @@ HCheckMaps* HCheckMaps::New(Zone* zone, Handle map, CompilationInfo* info, HValue* typecheck) { - HCheckMaps* check_map = new(zone) HCheckMaps(value, zone, typecheck); - check_map->Add(map, zone); + HCheckMaps* check_map = new(zone) HCheckMaps(value, new(zone) UniqueSet( + Unique::CreateImmovable(map), zone), typecheck); + // TODO(bmeurer): Get rid of this shit! if (map->CanOmitMapChecks() && value->IsConstant() && HConstant::cast(value)->HasMap(map)) { diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index c38b248..696b2c9 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -2747,13 +2747,13 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { Handle map, CompilationInfo* info, HValue* typecheck = NULL); static HCheckMaps* New(Zone* zone, HValue* context, - HValue* value, SmallMapList* maps, + HValue* value, SmallMapList* map_list, 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); + UniqueSet* maps = new(zone) UniqueSet(map_list->length(), zone); + for (int i = 0; i < map_list->length(); ++i) { + maps->Add(Unique::CreateImmovable(map_list->at(i)), zone); } - return check_map; + return new(zone) HCheckMaps(value, maps, typecheck); } bool CanOmitMapChecks() { return omit_; } @@ -2767,15 +2767,8 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { HValue* value() { return OperandAt(0); } HValue* typecheck() { return OperandAt(1); } - Unique first_map() const { return map_set_.at(0); } - const 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); - } - } + const UniqueSet* maps() const { return maps_; } + void set_maps(const UniqueSet* maps) { maps_ = maps; } bool has_migration_target() const { return has_migration_target_; @@ -2785,37 +2778,36 @@ class HCheckMaps V8_FINAL : public HTemplateInstruction<2> { protected: virtual bool DataEquals(HValue* other) V8_OVERRIDE { - return this->map_set_.Equals(&HCheckMaps::cast(other)->map_set_); + return this->maps()->Equals(HCheckMaps::cast(other)->maps()); } virtual int RedefinedOperandIndex() { return 0; } private: - void Add(Handle map, Zone* zone) { - map_set_.Add(Unique(map), zone); - SetDependsOnFlag(kMaps); - SetDependsOnFlag(kElementsKind); - - if (!has_migration_target_ && map->is_migration_target()) { - has_migration_target_ = true; - SetChangesFlag(kNewSpacePromotion); - } - } - // Clients should use one of the static New* methods above. - HCheckMaps(HValue* value, Zone *zone, HValue* typecheck) - : HTemplateInstruction<2>(value->type()), + HCheckMaps(HValue* value, const UniqueSet* maps, HValue* typecheck) + : HTemplateInstruction<2>(value->type()), maps_(maps), omit_(false), has_migration_target_(false) { + ASSERT_NE(0, maps->size()); SetOperandAt(0, value); // Use the object value for the dependency if NULL is passed. - SetOperandAt(1, typecheck != NULL ? typecheck : value); + SetOperandAt(1, typecheck ? typecheck : value); set_representation(Representation::Tagged()); SetFlag(kUseGVN); + SetDependsOnFlag(kMaps); + SetDependsOnFlag(kElementsKind); + for (int i = 0; i < maps->size(); ++i) { + if (maps->at(i).handle()->is_migration_target()) { + SetChangesFlag(kNewSpacePromotion); + has_migration_target_ = true; + break; + } + } } - bool omit_; - bool has_migration_target_; - UniqueSet map_set_; + const UniqueSet* maps_; + bool omit_ : 1; + bool has_migration_target_ : 1; }; @@ -5830,6 +5822,10 @@ class HObjectAccess V8_FINAL { return portion() == kStringLengths; } + inline bool IsMap() const { + return portion() == kMaps; + } + inline int offset() const { return OffsetField::decode(value_); } @@ -6142,23 +6138,27 @@ class HObjectAccess V8_FINAL { class HLoadNamedField V8_FINAL : public HTemplateInstruction<2> { public: - DECLARE_INSTRUCTION_FACTORY_P3(HLoadNamedField, HValue*, HValue*, - HObjectAccess); static HLoadNamedField* New(Zone* zone, HValue* context, HValue* object, HValue* dependency, - HObjectAccess access, SmallMapList* maps, + HObjectAccess access) { + return new(zone) HLoadNamedField( + object, dependency, access, new(zone) UniqueSet()); + } + static HLoadNamedField* New(Zone* zone, HValue* context, + HValue* object, HValue* dependency, + HObjectAccess access, SmallMapList* map_list, CompilationInfo* info) { - HLoadNamedField* load_named_field = HLoadNamedField::New( - zone, context, object, dependency, access); - for (int i = 0; i < maps->length(); ++i) { - Handle map(maps->at(i)); - load_named_field->map_set_.Add(Unique(map), zone); + UniqueSet* maps = new(zone) UniqueSet(map_list->length(), zone); + for (int i = 0; i < map_list->length(); ++i) { + Handle map = map_list->at(i); + maps->Add(Unique::CreateImmovable(map), zone); + // TODO(bmeurer): Get rid of this shit! if (map->CanTransition()) { Map::AddDependentCompilationInfo( map, DependentCode::kPrototypeCheckGroup, info); } } - return load_named_field; + return new(zone) HLoadNamedField(object, dependency, access, maps); } HValue* object() { return OperandAt(0); } @@ -6172,7 +6172,7 @@ class HLoadNamedField V8_FINAL : public HTemplateInstruction<2> { return access_.representation(); } - const UniqueSet* map_set() const { return &map_set_; } + const UniqueSet* maps() const { return maps_; } virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; } virtual bool HasOutOfBoundsAccess(int size) V8_OVERRIDE { @@ -6193,15 +6193,15 @@ class HLoadNamedField V8_FINAL : public HTemplateInstruction<2> { protected: virtual bool DataEquals(HValue* other) V8_OVERRIDE { HLoadNamedField* b = HLoadNamedField::cast(other); - return access_.Equals(b->access_) && this->map_set_.Equals(&b->map_set_); + return access_.Equals(b->access_) && this->maps()->Equals(b->maps()); } private: HLoadNamedField(HValue* object, HValue* dependency, HObjectAccess access, - Handle map = Handle::null()) - : access_(access) { + const UniqueSet* maps) + : access_(access), maps_(maps) { ASSERT(object != NULL); SetOperandAt(0, object); SetOperandAt(1, dependency != NULL ? dependency : object); @@ -6235,7 +6235,7 @@ class HLoadNamedField V8_FINAL : public HTemplateInstruction<2> { virtual bool IsDeletable() const V8_OVERRIDE { return true; } HObjectAccess access_; - UniqueSet map_set_; + const UniqueSet* maps_; }; diff --git a/src/hydrogen-load-elimination.cc b/src/hydrogen-load-elimination.cc index ed559dd..836bd2d 100644 --- a/src/hydrogen-load-elimination.cc +++ b/src/hydrogen-load-elimination.cc @@ -57,8 +57,8 @@ class HLoadEliminationTable : public ZoneObject { result->type().Equals(instr->type()) && result->representation().Equals(instr->representation()) && (!result->IsLoadNamedField() || - HLoadNamedField::cast(instr)->map_set()->IsSubset( - HLoadNamedField::cast(result)->map_set()))) { + HLoadNamedField::cast(instr)->maps()->IsSubset( + HLoadNamedField::cast(result)->maps()))) { // The load can be replaced with a previous load or a value. TRACE((" replace L%d -> v%d\n", instr->id(), result->id())); instr->DeleteAndReplaceWith(result); diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc index b12d44e..1f90a4a 100644 --- a/src/ia32/lithium-codegen-ia32.cc +++ b/src/ia32/lithium-codegen-ia32.cc @@ -5606,15 +5606,15 @@ void LCodeGen::DoCheckMaps(LCheckMaps* instr) { __ bind(deferred->check_maps()); } - const UniqueSet* map_set = instr->hydrogen()->map_set(); + const UniqueSet* maps = instr->hydrogen()->maps(); Label success; - for (int i = 0; i < map_set->size() - 1; i++) { - Handle map = map_set->at(i).handle(); + for (int i = 0; i < maps->size() - 1; i++) { + Handle map = maps->at(i).handle(); __ CompareMap(reg, map); __ j(equal, &success, Label::kNear); } - Handle map = map_set->at(map_set->size() - 1).handle(); + Handle map = maps->at(maps->size() - 1).handle(); __ CompareMap(reg, map); if (instr->hydrogen()->has_migration_target()) { __ j(not_equal, deferred->entry()); diff --git a/src/mips/lithium-codegen-mips.cc b/src/mips/lithium-codegen-mips.cc index 680f07a..d95f0c3 100644 --- a/src/mips/lithium-codegen-mips.cc +++ b/src/mips/lithium-codegen-mips.cc @@ -5177,13 +5177,13 @@ void LCodeGen::DoCheckMaps(LCheckMaps* instr) { __ bind(deferred->check_maps()); } - const UniqueSet* map_set = instr->hydrogen()->map_set(); + const UniqueSet* maps = instr->hydrogen()->maps(); Label success; - for (int i = 0; i < map_set->size() - 1; i++) { - Handle map = map_set->at(i).handle(); + for (int i = 0; i < maps->size() - 1; i++) { + Handle map = maps->at(i).handle(); __ CompareMapAndBranch(map_reg, map, &success, eq, &success); } - Handle map = map_set->at(map_set->size() - 1).handle(); + Handle map = maps->at(maps->size() - 1).handle(); // Do the CompareMap() directly within the Branch() and DeoptimizeIf(). if (instr->hydrogen()->has_migration_target()) { __ Branch(deferred->entry(), ne, map_reg, Operand(map)); diff --git a/src/unique.h b/src/unique.h index 82ed652..8ed2682 100644 --- a/src/unique.h +++ b/src/unique.h @@ -134,6 +134,19 @@ class UniqueSet V8_FINAL : public ZoneObject { // Constructor. A new set will be empty. UniqueSet() : size_(0), capacity_(0), array_(NULL) { } + // Capacity constructor. A new set will be empty. + UniqueSet(int capacity, Zone* zone) + : size_(0), capacity_(capacity), + array_(zone->NewArray >(capacity)) { + ASSERT(capacity <= kMaxCapacity); + } + + // Singleton constructor. + UniqueSet(Unique uniq, Zone* zone) + : size_(1), capacity_(1), array_(zone->NewArray >(1)) { + array_[0] = uniq; + } + // Add a new element to this unique set. Mutates this set. O(|this|). void Add(Unique uniq, Zone* zone) { ASSERT(uniq.IsInitialized()); @@ -178,8 +191,11 @@ class UniqueSet V8_FINAL : public ZoneObject { // TODO(titzer): use binary search for large sets to make this O(log|this|) template bool Contains(const Unique elem) const { - for (int i = 0; i < size_; i++) { - if (this->array_[i] == elem) return true; + for (int i = 0; i < this->size_; ++i) { + Unique cand = this->array_[i]; + if (cand.raw_address_ >= elem.raw_address_) { + return cand.raw_address_ == elem.raw_address_; + } } return false; } @@ -201,11 +217,11 @@ class UniqueSet V8_FINAL : public ZoneObject { // Returns a new set representing the intersection of this set and the other. // O(|this| + |that|). - UniqueSet* Intersect(UniqueSet* that, Zone* zone) const { + UniqueSet* Intersect(const UniqueSet* that, Zone* zone) const { if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet(); - UniqueSet* out = new(zone) UniqueSet(); - out->Grow(Min(this->size_, that->size_), zone); + UniqueSet* out = new(zone) UniqueSet( + Min(this->size_, that->size_), zone); int i = 0, j = 0, k = 0; while (i < this->size_ && j < that->size_) { @@ -228,12 +244,12 @@ class UniqueSet V8_FINAL : public ZoneObject { // Returns a new set representing the union of this set and the other. // O(|this| + |that|). - UniqueSet* Union(UniqueSet* that, Zone* zone) const { + UniqueSet* Union(const UniqueSet* that, Zone* zone) const { if (that->size_ == 0) return this->Copy(zone); if (this->size_ == 0) return that->Copy(zone); - UniqueSet* out = new(zone) UniqueSet(); - out->Grow(this->size_ + that->size_, zone); + UniqueSet* out = new(zone) UniqueSet( + this->size_ + that->size_, zone); int i = 0, j = 0, k = 0; while (i < this->size_ && j < that->size_) { @@ -261,10 +277,8 @@ class UniqueSet V8_FINAL : public ZoneObject { // Makes an exact copy of this set. O(|this|). UniqueSet* Copy(Zone* zone) const { - UniqueSet* copy = new(zone) UniqueSet(); + UniqueSet* copy = new(zone) UniqueSet(this->size_, zone); copy->size_ = this->size_; - copy->capacity_ = this->size_; - copy->array_ = zone->NewArray >(this->size_); memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique)); return copy; } diff --git a/src/x64/lithium-codegen-x64.cc b/src/x64/lithium-codegen-x64.cc index bfeffd3..b3a1c30 100644 --- a/src/x64/lithium-codegen-x64.cc +++ b/src/x64/lithium-codegen-x64.cc @@ -5025,15 +5025,15 @@ void LCodeGen::DoCheckMaps(LCheckMaps* instr) { __ bind(deferred->check_maps()); } - const UniqueSet* map_set = instr->hydrogen()->map_set(); + const UniqueSet* maps = instr->hydrogen()->maps(); Label success; - for (int i = 0; i < map_set->size() - 1; i++) { - Handle map = map_set->at(i).handle(); + for (int i = 0; i < maps->size() - 1; i++) { + Handle map = maps->at(i).handle(); __ CompareMap(reg, map); __ j(equal, &success, Label::kNear); } - Handle map = map_set->at(map_set->size() - 1).handle(); + Handle map = maps->at(maps->size() - 1).handle(); __ CompareMap(reg, map); if (instr->hydrogen()->has_migration_target()) { __ j(not_equal, deferred->entry()); -- 2.7.4