1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/ic/stub-cache.h"
6
7 #include "src/ast/ast.h"
8 #include "src/base/bits.h"
9 #include "src/heap/heap-inl.h" // For InYoungGeneration().
10 #include "src/ic/ic-inl.h"
11 #include "src/logging/counters.h"
12 #include "src/objects/tagged-value-inl.h"
13
14 namespace v8 {
15 namespace internal {
16
StubCache(Isolate * isolate)17 StubCache::StubCache(Isolate* isolate) : isolate_(isolate) {
18 // Ensure the nullptr (aka Smi::zero()) which StubCache::Get() returns
19 // when the entry is not found is not considered as a handler.
20 DCHECK(!IC::IsHandler(MaybeObject()));
21 }
22
Initialize()23 void StubCache::Initialize() {
24 DCHECK(base::bits::IsPowerOfTwo(kPrimaryTableSize));
25 DCHECK(base::bits::IsPowerOfTwo(kSecondaryTableSize));
26 Clear();
27 }
28
29 // Hash algorithm for the primary table. This algorithm is replicated in
30 // the AccessorAssembler. Returns an index into the table that
31 // is scaled by 1 << kCacheIndexShift.
PrimaryOffset(Name name,Map map)32 int StubCache::PrimaryOffset(Name name, Map map) {
33 // Compute the hash of the name (use entire hash field).
34 DCHECK(name.HasHashCode());
35 uint32_t field = name.raw_hash_field();
36 // Using only the low bits in 64-bit mode is unlikely to increase the
37 // risk of collision even if the heap is spread over an area larger than
38 // 4Gb (and not at all if it isn't).
39 uint32_t map_low32bits =
40 static_cast<uint32_t>(map.ptr() ^ (map.ptr() >> kMapKeyShift));
41 // Base the offset on a simple combination of name and map.
42 uint32_t key = map_low32bits + field;
43 return key & ((kPrimaryTableSize - 1) << kCacheIndexShift);
44 }
45
46 // Hash algorithm for the secondary table. This algorithm is replicated in
47 // assembler. This hash should be sufficiently different from the primary one
48 // in order to avoid collisions for minified code with short names.
49 // Returns an index into the table that is scaled by 1 << kCacheIndexShift.
SecondaryOffset(Name name,Map old_map)50 int StubCache::SecondaryOffset(Name name, Map old_map) {
51 uint32_t name_low32bits = static_cast<uint32_t>(name.ptr());
52 uint32_t map_low32bits = static_cast<uint32_t>(old_map.ptr());
53 uint32_t key = (map_low32bits + name_low32bits);
54 key = key + (key >> kSecondaryKeyShift);
55 return key & ((kSecondaryTableSize - 1) << kCacheIndexShift);
56 }
57
PrimaryOffsetForTesting(Name name,Map map)58 int StubCache::PrimaryOffsetForTesting(Name name, Map map) {
59 return PrimaryOffset(name, map);
60 }
61
SecondaryOffsetForTesting(Name name,Map map)62 int StubCache::SecondaryOffsetForTesting(Name name, Map map) {
63 return SecondaryOffset(name, map);
64 }
65
66 #ifdef DEBUG
67 namespace {
68
CommonStubCacheChecks(StubCache * stub_cache,Name name,Map map,MaybeObject handler)69 bool CommonStubCacheChecks(StubCache* stub_cache, Name name, Map map,
70 MaybeObject handler) {
71 // Validate that the name and handler do not move on scavenge, and that we
72 // can use identity checks instead of structural equality checks.
73 DCHECK(!Heap::InYoungGeneration(name));
74 DCHECK(!Heap::InYoungGeneration(handler));
75 DCHECK(name.IsUniqueName());
76 if (handler->ptr() != kNullAddress) DCHECK(IC::IsHandler(handler));
77 return true;
78 }
79
80 } // namespace
81 #endif
82
Set(Name name,Map map,MaybeObject handler)83 void StubCache::Set(Name name, Map map, MaybeObject handler) {
84 DCHECK(CommonStubCacheChecks(this, name, map, handler));
85
86 // Compute the primary entry.
87 int primary_offset = PrimaryOffset(name, map);
88 Entry* primary = entry(primary_, primary_offset);
89 MaybeObject old_handler(
90 TaggedValue::ToMaybeObject(isolate(), primary->value));
91 // If the primary entry has useful data in it, we retire it to the
92 // secondary cache before overwriting it.
93 if (old_handler != MaybeObject::FromObject(
94 isolate()->builtins()->code(Builtin::kIllegal)) &&
95 !primary->map.IsSmi()) {
96 Map old_map =
97 Map::cast(StrongTaggedValue::ToObject(isolate(), primary->map));
98 Name old_name =
99 Name::cast(StrongTaggedValue::ToObject(isolate(), primary->key));
100 int secondary_offset = SecondaryOffset(old_name, old_map);
101 Entry* secondary = entry(secondary_, secondary_offset);
102 *secondary = *primary;
103 }
104
105 // Update primary cache.
106 primary->key = StrongTaggedValue(name);
107 primary->value = TaggedValue(handler);
108 primary->map = StrongTaggedValue(map);
109 isolate()->counters()->megamorphic_stub_cache_updates()->Increment();
110 }
111
Get(Name name,Map map)112 MaybeObject StubCache::Get(Name name, Map map) {
113 DCHECK(CommonStubCacheChecks(this, name, map, MaybeObject()));
114 int primary_offset = PrimaryOffset(name, map);
115 Entry* primary = entry(primary_, primary_offset);
116 if (primary->key == name && primary->map == map) {
117 return TaggedValue::ToMaybeObject(isolate(), primary->value);
118 }
119 int secondary_offset = SecondaryOffset(name, map);
120 Entry* secondary = entry(secondary_, secondary_offset);
121 if (secondary->key == name && secondary->map == map) {
122 return TaggedValue::ToMaybeObject(isolate(), secondary->value);
123 }
124 return MaybeObject();
125 }
126
Clear()127 void StubCache::Clear() {
128 MaybeObject empty =
129 MaybeObject::FromObject(isolate_->builtins()->code(Builtin::kIllegal));
130 Name empty_string = ReadOnlyRoots(isolate()).empty_string();
131 for (int i = 0; i < kPrimaryTableSize; i++) {
132 primary_[i].key = StrongTaggedValue(empty_string);
133 primary_[i].map = StrongTaggedValue(Smi::zero());
134 primary_[i].value = TaggedValue(empty);
135 }
136 for (int j = 0; j < kSecondaryTableSize; j++) {
137 secondary_[j].key = StrongTaggedValue(empty_string);
138 secondary_[j].map = StrongTaggedValue(Smi::zero());
139 secondary_[j].value = TaggedValue(empty);
140 }
141 }
142
143 } // namespace internal
144 } // namespace v8
145