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