From c0a0c82b70f98e074988382735ae3ab288359ead Mon Sep 17 00:00:00 2001 From: "jkummerow@chromium.org" Date: Mon, 6 Jun 2011 13:15:11 +0000 Subject: [PATCH] Per-Isolate cache for polymorphic stubs BUG=1385 TEST=Existing tests still pass; running d8 with --dump-counters shows fewer polymorphic stubs being compiled Review URL: http://codereview.chromium.org/7094003 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@8183 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- include/v8.h | 2 +- src/heap.cc | 13 +++ src/heap.h | 4 + src/ic.cc | 77 ++++------------ src/objects-debug.cc | 6 ++ src/objects-inl.h | 8 ++ src/objects-printer.cc | 7 ++ src/objects.cc | 239 ++++++++++++++++++++++++++++++++++++++++--------- src/objects.h | 69 ++++++++++++-- 9 files changed, 320 insertions(+), 105 deletions(-) diff --git a/include/v8.h b/include/v8.h index 3ce6b87..b4598c6 100644 --- a/include/v8.h +++ b/include/v8.h @@ -3703,7 +3703,7 @@ class Internals { static const int kFullStringRepresentationMask = 0x07; static const int kExternalTwoByteRepresentationTag = 0x02; - static const int kJSObjectType = 0xa1; + static const int kJSObjectType = 0xa2; static const int kFirstNonstringType = 0x80; static const int kForeignType = 0x85; diff --git a/src/heap.cc b/src/heap.cc index aa728fd..3202240 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -877,6 +877,9 @@ void Heap::MarkCompactPrologue(bool is_compacting) { CompletelyClearInstanceofCache(); if (is_compacting) FlushNumberStringCache(); + if (FLAG_cleanup_code_caches_at_gc) { + polymorphic_code_cache()->set_cache(undefined_value()); + } ClearNormalizedMapCaches(); } @@ -1661,6 +1664,11 @@ MaybeObject* Heap::AllocateCodeCache() { } +MaybeObject* Heap::AllocatePolymorphicCodeCache() { + return AllocateStruct(POLYMORPHIC_CODE_CACHE_TYPE); +} + + const Heap::StringTypeTable Heap::string_type_table[] = { #define STRING_TYPE_ELEMENT(type, size, name, camel_name) \ {type, size, k##camel_name##MapRootIndex}, @@ -2168,6 +2176,11 @@ bool Heap::CreateInitialObjects() { } set_non_monomorphic_cache(NumberDictionary::cast(obj)); + { MaybeObject* maybe_obj = AllocatePolymorphicCodeCache(); + if (!maybe_obj->ToObject(&obj)) return false; + } + set_polymorphic_code_cache(PolymorphicCodeCache::cast(obj)); + set_instanceof_cache_function(Smi::FromInt(0)); set_instanceof_cache_map(Smi::FromInt(0)); set_instanceof_cache_answer(Smi::FromInt(0)); diff --git a/src/heap.h b/src/heap.h index a6455e5..aadfd9d 100644 --- a/src/heap.h +++ b/src/heap.h @@ -120,6 +120,7 @@ inline Heap* _inline_get_heap_(); V(Foreign, prototype_accessors, PrototypeAccessors) \ V(NumberDictionary, code_stubs, CodeStubs) \ V(NumberDictionary, non_monomorphic_cache, NonMonomorphicCache) \ + V(PolymorphicCodeCache, polymorphic_code_cache, PolymorphicCodeCache) \ V(Code, js_entry_code, JsEntryCode) \ V(Code, js_construct_entry_code, JsConstructEntryCode) \ V(FixedArray, natives_source_cache, NativesSourceCache) \ @@ -477,6 +478,9 @@ class Heap { // Allocates an empty code cache. MUST_USE_RESULT MaybeObject* AllocateCodeCache(); + // Allocates an empty PolymorphicCodeCache. + MUST_USE_RESULT MaybeObject* AllocatePolymorphicCodeCache(); + // Clear the Instanceof cache (used when a prototype changes). inline void ClearInstanceofCache(); diff --git a/src/ic.cc b/src/ic.cc index 8cea2eb..64a0850 100644 --- a/src/ic.cc +++ b/src/ic.cc @@ -1636,79 +1636,40 @@ MaybeObject* KeyedIC::ComputeStub(JSObject* receiver, return generic_stub; } - // TODO(1385): Currently MEGAMORPHIC stubs are cached in the receiver map stub - // cache, but that can put receiver types together from unrelated call sites - // into the same stub--they always handle the union of all receiver maps seen - // at all call sites involving the receiver map. This is only an - // approximation: ideally, there would be a global cache that mapped sets of - // receiver maps to MEGAMORPHIC stubs. The complexity of the MEGAMORPHIC stub - // computation also leads to direct manipulation of the stub cache from the IC - // code, which the global cache solution would avoid. - Code::Kind kind = this->kind(); - Code::Flags flags = Code::ComputeFlags(kind, - NOT_IN_LOOP, - MEGAMORPHIC, - strict_mode); - String* megamorphic_name = GetStubNameForCache(MEGAMORPHIC); - Object* maybe_cached_stub = receiver->map()->FindInCodeCache(megamorphic_name, - flags); - - // Create a set of all receiver maps that have been seen at the IC call site - // and those seen by the MEGAMORPHIC cached stub, if that's the stub that's - // been selected. - MapList receiver_maps; - if (!maybe_cached_stub->IsUndefined()) { - GetReceiverMapsForStub(Code::cast(maybe_cached_stub), &receiver_maps); - } - bool added_map = false; - for (int i = 0; i < target_receiver_maps.length(); ++i) { - if (AddOneReceiverMapIfMissing(&receiver_maps, - target_receiver_maps.at(i))) { - added_map = true; - } - } - ASSERT(receiver_maps.length() > 0); - - // If the maximum number of receiver maps has been exceeded, use the Generic + // If the maximum number of receiver maps has been exceeded, use the generic // version of the IC. - if (receiver_maps.length() > KeyedIC::kMaxKeyedPolymorphism) { + if (target_receiver_maps.length() > KeyedIC::kMaxKeyedPolymorphism) { return generic_stub; } - // If no maps have been seen at the call site that aren't in the cached - // stub, then use it. - if (!added_map) { - ASSERT(!maybe_cached_stub->IsUndefined()); + PolymorphicCodeCache* cache = isolate()->heap()->polymorphic_code_cache(); + Code::Flags flags = Code::ComputeFlags(this->kind(), + NOT_IN_LOOP, + MEGAMORPHIC, + strict_mode); + Object* maybe_cached_stub = cache->Lookup(&target_receiver_maps, flags); + // If there is a cached stub, use it. + if (!maybe_cached_stub->IsUndefined()) { ASSERT(maybe_cached_stub->IsCode()); return Code::cast(maybe_cached_stub); } - - // Lookup all of the receiver maps in the cache, they should all already - // have MONOMORPHIC stubs. - CodeList handler_ics(KeyedIC::kMaxKeyedPolymorphism); - for (int current = 0; current < receiver_maps.length(); ++current) { - Map* receiver_map(receiver_maps.at(current)); + // Collect MONOMORPHIC stubs for all target_receiver_maps. + CodeList handler_ics(target_receiver_maps.length()); + for (int i = 0; i < target_receiver_maps.length(); ++i) { + Map* receiver_map(target_receiver_maps.at(i)); MaybeObject* maybe_cached_stub = ComputeMonomorphicStubWithoutMapCheck( - receiver_map, - strict_mode, - generic_stub); + receiver_map, strict_mode, generic_stub); Code* cached_stub; - if (!maybe_cached_stub->To(&cached_stub)) { - return maybe_cached_stub; - } + if (!maybe_cached_stub->To(&cached_stub)) return maybe_cached_stub; handler_ics.Add(cached_stub); } - - Code* stub; // Build the MEGAMORPHIC stub. - maybe_stub = ConstructMegamorphicStub(&receiver_maps, + Code* stub; + maybe_stub = ConstructMegamorphicStub(&target_receiver_maps, &handler_ics, strict_mode); if (!maybe_stub->To(&stub)) return maybe_stub; - - MaybeObject* maybe_update = receiver->UpdateMapCodeCache( - megamorphic_name, - stub); + MaybeObject* maybe_update = cache->Update(&target_receiver_maps, flags, stub); if (maybe_update->IsFailure()) return maybe_update; return stub; } diff --git a/src/objects-debug.cc b/src/objects-debug.cc index 4072f8f..acb0a9f 100644 --- a/src/objects-debug.cc +++ b/src/objects-debug.cc @@ -289,6 +289,12 @@ void CodeCache::CodeCacheVerify() { } +void PolymorphicCodeCache::PolymorphicCodeCacheVerify() { + VerifyHeapPointer(cache()); + ASSERT(cache()->IsUndefined() || cache()->IsPolymorphicCodeCacheHashTable()); +} + + void FixedArray::FixedArrayVerify() { for (int i = 0; i < length(); i++) { Object* e = get(i); diff --git a/src/objects-inl.h b/src/objects-inl.h index 2b5d18f..72dca22 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -688,6 +688,11 @@ bool Object::IsCodeCacheHashTable() { } +bool Object::IsPolymorphicCodeCacheHashTable() { + return IsHashTable(); +} + + bool Object::IsMapCache() { return IsHashTable(); } @@ -1903,6 +1908,7 @@ CAST_ACCESSOR(JSFunctionResultCache) CAST_ACCESSOR(NormalizedMapCache) CAST_ACCESSOR(CompilationCacheTable) CAST_ACCESSOR(CodeCacheHashTable) +CAST_ACCESSOR(PolymorphicCodeCacheHashTable) CAST_ACCESSOR(MapCache) CAST_ACCESSOR(String) CAST_ACCESSOR(SeqString) @@ -3338,6 +3344,8 @@ void SharedFunctionInfo::set_native(bool value) { ACCESSORS(CodeCache, default_cache, FixedArray, kDefaultCacheOffset) ACCESSORS(CodeCache, normal_type_cache, Object, kNormalTypeCacheOffset) +ACCESSORS(PolymorphicCodeCache, cache, Object, kCacheOffset) + bool Script::HasValidSource() { Object* src = this->source(); if (!src->IsString()) return true; diff --git a/src/objects-printer.cc b/src/objects-printer.cc index 60028c0..dca500e 100644 --- a/src/objects-printer.cc +++ b/src/objects-printer.cc @@ -472,6 +472,13 @@ void CodeCache::CodeCachePrint(FILE* out) { } +void PolymorphicCodeCache::PolymorphicCodeCachePrint(FILE* out) { + HeapObject::PrintHeader(out, "PolymorphicCodeCache"); + PrintF(out, "\n - cache: "); + cache()->ShortPrint(out); +} + + void FixedArray::FixedArrayPrint(FILE* out) { HeapObject::PrintHeader(out, "FixedArray"); PrintF(out, " - length: %d", length()); diff --git a/src/objects.cc b/src/objects.cc index 0c4dcbc..9857f2a 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -2613,10 +2613,12 @@ MaybeObject* NormalizedMapCache::Get(JSObject* obj, PropertyNormalizationMode mode) { Isolate* isolate = obj->GetIsolate(); Map* fast = obj->map(); - int index = Hash(fast) % kEntries; + int index = fast->Hash() % kEntries; Object* result = get(index); - if (result->IsMap() && CheckHit(Map::cast(result), fast, mode)) { + if (result->IsMap() && + Map::cast(result)->EquivalentToForNormalization(fast, mode)) { #ifdef DEBUG + Map::cast(result)->SharedMapVerify(); if (FLAG_enable_slow_asserts) { // The cached map should match newly created normalized map bit-by-bit. Object* fresh; @@ -2652,43 +2654,6 @@ void NormalizedMapCache::Clear() { } -int NormalizedMapCache::Hash(Map* fast) { - // For performance reasons we only hash the 3 most variable fields of a map: - // constructor, prototype and bit_field2. - - // Shift away the tag. - int hash = (static_cast( - reinterpret_cast(fast->constructor())) >> 2); - - // XOR-ing the prototype and constructor directly yields too many zero bits - // when the two pointers are close (which is fairly common). - // To avoid this we shift the prototype 4 bits relatively to the constructor. - hash ^= (static_cast( - reinterpret_cast(fast->prototype())) << 2); - - return hash ^ (hash >> 16) ^ fast->bit_field2(); -} - - -bool NormalizedMapCache::CheckHit(Map* slow, - Map* fast, - PropertyNormalizationMode mode) { -#ifdef DEBUG - slow->SharedMapVerify(); -#endif - return - slow->constructor() == fast->constructor() && - slow->prototype() == fast->prototype() && - slow->inobject_properties() == ((mode == CLEAR_INOBJECT_PROPERTIES) ? - 0 : - fast->inobject_properties()) && - slow->instance_type() == fast->instance_type() && - slow->bit_field() == fast->bit_field() && - slow->bit_field2() == fast->bit_field2() && - (slow->bit_field3() & ~(1<bit_field3(); -} - - MaybeObject* JSObject::UpdateMapCodeCache(String* name, Code* code) { if (map()->is_shared()) { // Fast case maps are never marked as shared. @@ -4219,6 +4184,7 @@ class CodeCacheHashTableKey : public HashTableKey { private: String* name_; Code::Flags flags_; + // TODO(jkummerow): We should be able to get by without this. Code* code_; }; @@ -4238,7 +4204,7 @@ MaybeObject* CodeCacheHashTable::Put(String* name, Code* code) { if (!maybe_obj->ToObject(&obj)) return maybe_obj; } - // Don't use this, as the table might have grown. + // Don't use |this|, as the table might have grown. CodeCacheHashTable* cache = reinterpret_cast(obj); int entry = cache->FindInsertionEntry(key.Hash()); @@ -4284,6 +4250,165 @@ static bool HasKey(FixedArray* array, Object* key) { } +MaybeObject* PolymorphicCodeCache::Update(MapList* maps, + Code::Flags flags, + Code* code) { + // Initialize cache if necessary. + if (cache()->IsUndefined()) { + Object* result; + { MaybeObject* maybe_result = + PolymorphicCodeCacheHashTable::Allocate( + PolymorphicCodeCacheHashTable::kInitialSize); + if (!maybe_result->ToObject(&result)) return maybe_result; + } + set_cache(result); + } else { + // This entry shouldn't be contained in the cache yet. + ASSERT(PolymorphicCodeCacheHashTable::cast(cache()) + ->Lookup(maps, flags)->IsUndefined()); + } + PolymorphicCodeCacheHashTable* hash_table = + PolymorphicCodeCacheHashTable::cast(cache()); + Object* new_cache; + { MaybeObject* maybe_new_cache = hash_table->Put(maps, flags, code); + if (!maybe_new_cache->ToObject(&new_cache)) return maybe_new_cache; + } + set_cache(new_cache); + return this; +} + + +Object* PolymorphicCodeCache::Lookup(MapList* maps, Code::Flags flags) { + if (!cache()->IsUndefined()) { + PolymorphicCodeCacheHashTable* hash_table = + PolymorphicCodeCacheHashTable::cast(cache()); + return hash_table->Lookup(maps, flags); + } else { + return GetHeap()->undefined_value(); + } +} + + +// Despite their name, object of this class are not stored in the actual +// hash table; instead they're temporarily used for lookups. It is therefore +// safe to have a weak (non-owning) pointer to a MapList as a member field. +class PolymorphicCodeCacheHashTableKey : public HashTableKey { + public: + // Callers must ensure that |maps| outlives the newly constructed object. + PolymorphicCodeCacheHashTableKey(MapList* maps, int code_flags) + : maps_(maps), + code_flags_(code_flags) {} + + bool IsMatch(Object* other) { + MapList other_maps(kDefaultListAllocationSize); + int other_flags; + FromObject(other, &other_flags, &other_maps); + if (code_flags_ != other_flags) return false; + if (maps_->length() != other_maps.length()) return false; + // Compare just the hashes first because it's faster. + int this_hash = MapsHashHelper(maps_, code_flags_); + int other_hash = MapsHashHelper(&other_maps, other_flags); + if (this_hash != other_hash) return false; + + // Full comparison: for each map in maps_, look for an equivalent map in + // other_maps. This implementation is slow, but probably good enough for + // now because the lists are short (<= 4 elements currently). + for (int i = 0; i < maps_->length(); ++i) { + bool match_found = false; + for (int j = 0; j < other_maps.length(); ++j) { + if (maps_->at(i)->EquivalentTo(other_maps.at(j))) { + match_found = true; + break; + } + } + if (!match_found) return false; + } + return true; + } + + static uint32_t MapsHashHelper(MapList* maps, int code_flags) { + uint32_t hash = code_flags; + for (int i = 0; i < maps->length(); ++i) { + hash ^= maps->at(i)->Hash(); + } + return hash; + } + + uint32_t Hash() { + return MapsHashHelper(maps_, code_flags_); + } + + uint32_t HashForObject(Object* obj) { + MapList other_maps(kDefaultListAllocationSize); + int other_flags; + FromObject(obj, &other_flags, &other_maps); + return MapsHashHelper(&other_maps, other_flags); + } + + MUST_USE_RESULT MaybeObject* AsObject() { + Object* obj; + // The maps in |maps_| must be copied to a newly allocated FixedArray, + // both because the referenced MapList is short-lived, and because C++ + // objects can't be stored in the heap anyway. + { MaybeObject* maybe_obj = + HEAP->AllocateUninitializedFixedArray(maps_->length() + 1); + if (!maybe_obj->ToObject(&obj)) return maybe_obj; + } + FixedArray* list = FixedArray::cast(obj); + list->set(0, Smi::FromInt(code_flags_)); + for (int i = 0; i < maps_->length(); ++i) { + list->set(i + 1, maps_->at(i)); + } + return list; + } + + private: + static MapList* FromObject(Object* obj, int* code_flags, MapList* maps) { + FixedArray* list = FixedArray::cast(obj); + maps->Rewind(0); + *code_flags = Smi::cast(list->get(0))->value(); + for (int i = 1; i < list->length(); ++i) { + maps->Add(Map::cast(list->get(i))); + } + return maps; + } + + MapList* maps_; // weak. + int code_flags_; + static const int kDefaultListAllocationSize = + KeyedIC::kMaxKeyedPolymorphism + 1; +}; + + +Object* PolymorphicCodeCacheHashTable::Lookup(MapList* maps, int code_flags) { + PolymorphicCodeCacheHashTableKey key(maps, code_flags); + int entry = FindEntry(&key); + if (entry == kNotFound) return GetHeap()->undefined_value(); + return get(EntryToIndex(entry) + 1); +} + + +MaybeObject* PolymorphicCodeCacheHashTable::Put(MapList* maps, + int code_flags, + Code* code) { + PolymorphicCodeCacheHashTableKey key(maps, code_flags); + Object* obj; + { MaybeObject* maybe_obj = EnsureCapacity(1, &key); + if (!maybe_obj->ToObject(&obj)) return maybe_obj; + } + PolymorphicCodeCacheHashTable* cache = + reinterpret_cast(obj); + int entry = cache->FindInsertionEntry(key.Hash()); + { MaybeObject* maybe_obj = key.AsObject(); + if (!maybe_obj->ToObject(&obj)) return maybe_obj; + } + cache->set(EntryToIndex(entry), obj); + cache->set(EntryToIndex(entry) + 1, code); + cache->ElementAdded(); + return cache; +} + + MaybeObject* FixedArray::AddKeysFromJSArray(JSArray* array) { ASSERT(!array->HasExternalArrayElements()); switch (array->GetElementsKind()) { @@ -5929,6 +6054,40 @@ void Map::ClearNonLiveTransitions(Heap* heap, Object* real_prototype) { } +int Map::Hash() { + // For performance reasons we only hash the 3 most variable fields of a map: + // constructor, prototype and bit_field2. + + // Shift away the tag. + int hash = (static_cast( + reinterpret_cast(constructor())) >> 2); + + // XOR-ing the prototype and constructor directly yields too many zero bits + // when the two pointers are close (which is fairly common). + // To avoid this we shift the prototype 4 bits relatively to the constructor. + hash ^= (static_cast( + reinterpret_cast(prototype())) << 2); + + return hash ^ (hash >> 16) ^ bit_field2(); +} + + +bool Map::EquivalentToForNormalization(Map* other, + PropertyNormalizationMode mode) { + return + constructor() == other->constructor() && + prototype() == other->prototype() && + inobject_properties() == ((mode == CLEAR_INOBJECT_PROPERTIES) ? + 0 : + other->inobject_properties()) && + instance_type() == other->instance_type() && + bit_field() == other->bit_field() && + bit_field2() == other->bit_field2() && + (bit_field3() & ~(1<bit_field3() & ~(1< { + public: + Object* Lookup(MapList* maps, int code_kind); + MUST_USE_RESULT MaybeObject* Put(MapList* maps, int code_kind, Code* code); + + static inline PolymorphicCodeCacheHashTable* cast(Object* obj); + + static const int kInitialSize = 64; + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(PolymorphicCodeCacheHashTable); +}; + + enum AllowNullsFlag {ALLOW_NULLS, DISALLOW_NULLS}; enum RobustnessFlag {ROBUST_STRING_TRAVERSAL, FAST_STRING_TRAVERSAL}; -- 2.7.4