1a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// Copyright 2012 the V8 project authors. All rights reserved. 2a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// Use of this source code is governed by a BSD-style license that can be 3a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// found in the LICENSE file. 4a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 5a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#ifndef V8_STUB_CACHE_H_ 6a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#define V8_STUB_CACHE_H_ 7a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 8a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#include "src/macro-assembler.h" 9a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 10a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgnamespace v8 { 11a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgnamespace internal { 12a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 13a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 14a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// The stub cache is used for megamorphic property accesses. 15a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// It maps (map, name, type) to property access handlers. The cache does not 16a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// need explicit invalidation when a prototype chain is modified, since the 17a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org// handlers verify the chain. 18a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 19a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 20a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgclass SCTableReference { 21a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org public: 22a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Address address() const { return address_; } 23a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 24a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org private: 25a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org explicit SCTableReference(Address address) : address_(address) {} 26a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 27a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Address address_; 28a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 29a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org friend class StubCache; 30a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org}; 31a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 32a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 33a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgclass StubCache { 34a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org public: 35a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org struct Entry { 36a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Name* key; 37a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Code* value; 38a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Map* map; 39a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org }; 40a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 41a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org void Initialize(); 42a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Access cache for entry hash(name, map). 43a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Code* Set(Name* name, Map* map, Code* code); 44a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Code* Get(Name* name, Map* map, Code::Flags flags); 45a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Clear the lookup table (@ mark compact collection). 46a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org void Clear(); 47a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Collect all maps that match the name and flags. 48a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org void CollectMatchingMaps(SmallMapList* types, Handle<Name> name, 49a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Code::Flags flags, Handle<Context> native_context, 50a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Zone* zone); 51a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Generate code for probing the stub cache table. 52a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Arguments extra, extra2 and extra3 may be used to pass additional scratch 53a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // registers. Set to no_reg if not needed. 54e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org // If leave_frame is true, then exit a frame before the tail call. 55e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org void GenerateProbe(MacroAssembler* masm, Code::Flags flags, bool leave_frame, 56e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org Register receiver, Register name, Register scratch, 57e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org Register extra, Register extra2 = no_reg, 58e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org Register extra3 = no_reg); 59a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 60a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org enum Table { kPrimary, kSecondary }; 61a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 62a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org SCTableReference key_reference(StubCache::Table table) { 63a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return SCTableReference( 64a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org reinterpret_cast<Address>(&first_entry(table)->key)); 65a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 66a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 67a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org SCTableReference map_reference(StubCache::Table table) { 68a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return SCTableReference( 69a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org reinterpret_cast<Address>(&first_entry(table)->map)); 70a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 71a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 72a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org SCTableReference value_reference(StubCache::Table table) { 73a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return SCTableReference( 74a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org reinterpret_cast<Address>(&first_entry(table)->value)); 75a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 76a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 77a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org StubCache::Entry* first_entry(StubCache::Table table) { 78a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org switch (table) { 79a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org case StubCache::kPrimary: 80a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return StubCache::primary_; 81a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org case StubCache::kSecondary: 82a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return StubCache::secondary_; 83a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 84a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org UNREACHABLE(); 85a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return NULL; 86a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 87a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 88a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Isolate* isolate() { return isolate_; } 89a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 90a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Setting the entry size such that the index is shifted by Name::kHashShift 91a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // is convenient; shifting down the length field (to extract the hash code) 92a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // automatically discards the hash bit field. 93a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static const int kCacheIndexShift = Name::kHashShift; 94a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 95a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org private: 96a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org explicit StubCache(Isolate* isolate); 97a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 98a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // The stub cache has a primary and secondary level. The two levels have 99a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // different hashing algorithms in order to avoid simultaneous collisions 100a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // in both caches. Unlike a probing strategy (quadratic or otherwise) the 101a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // update strategy on updates is fairly clear and simple: Any existing entry 102a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // in the primary cache is moved to the secondary cache, and secondary cache 103a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // entries are overwritten. 104a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 105a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Hash algorithm for the primary table. This algorithm is replicated in 106a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // assembler for every architecture. Returns an index into the table that 107a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // is scaled by 1 << kCacheIndexShift. 108a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static int PrimaryOffset(Name* name, Code::Flags flags, Map* map) { 109a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org STATIC_ASSERT(kCacheIndexShift == Name::kHashShift); 110a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Compute the hash of the name (use entire hash field). 111a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org DCHECK(name->HasHashCode()); 112a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t field = name->hash_field(); 113a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Using only the low bits in 64-bit mode is unlikely to increase the 114a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // risk of collision even if the heap is spread over an area larger than 115a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // 4Gb (and not at all if it isn't). 116a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t map_low32bits = 117a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static_cast<uint32_t>(reinterpret_cast<uintptr_t>(map)); 118a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // We always set the in_loop bit to zero when generating the lookup code 119a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // so do it here too so the hash codes match. 120a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t iflags = 121a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org (static_cast<uint32_t>(flags) & ~Code::kFlagsNotUsedInLookup); 122a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Base the offset on a simple combination of name, flags, and map. 123a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t key = (map_low32bits + field) ^ iflags; 124a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return key & ((kPrimaryTableSize - 1) << kCacheIndexShift); 125a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 126a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 127a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Hash algorithm for the secondary table. This algorithm is replicated in 128a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // assembler for every architecture. Returns an index into the table that 129a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // is scaled by 1 << kCacheIndexShift. 130a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static int SecondaryOffset(Name* name, Code::Flags flags, int seed) { 131a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Use the seed from the primary cache in the secondary cache. 132a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t name_low32bits = 133a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name)); 134a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // We always set the in_loop bit to zero when generating the lookup code 135a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // so do it here too so the hash codes match. 136a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t iflags = 137a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org (static_cast<uint32_t>(flags) & ~Code::kFlagsNotUsedInLookup); 138a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org uint32_t key = (seed - name_low32bits) + iflags; 139a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return key & ((kSecondaryTableSize - 1) << kCacheIndexShift); 140a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 141a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 142a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Compute the entry for a given offset in exactly the same way as 143a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // we do in generated code. We generate an hash code that already 144a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // ends in Name::kHashShift 0s. Then we multiply it so it is a multiple 145a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // of sizeof(Entry). This makes it easier to avoid making mistakes 146a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // in the hashed offset computations. 147a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static Entry* entry(Entry* table, int offset) { 148a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org const int multiplier = sizeof(*table) >> Name::kHashShift; 149a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return reinterpret_cast<Entry*>(reinterpret_cast<Address>(table) + 150a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org offset * multiplier); 151a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 152a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 153a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static const int kPrimaryTableBits = 11; 154a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static const int kPrimaryTableSize = (1 << kPrimaryTableBits); 155a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static const int kSecondaryTableBits = 9; 156a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static const int kSecondaryTableSize = (1 << kSecondaryTableBits); 157a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 158e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org private: 159a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Entry primary_[kPrimaryTableSize]; 160a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Entry secondary_[kSecondaryTableSize]; 161a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Isolate* isolate_; 162a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 163a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org friend class Isolate; 164a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org friend class SCTableReference; 165a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 166a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org DISALLOW_COPY_AND_ASSIGN(StubCache); 167a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org}; 168a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org} 169a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org} // namespace v8::internal 170a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 171a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#endif // V8_STUB_CACHE_H_ 172