xref: /third_party/node/deps/v8/src/ic/stub-cache.cc (revision 1cb0ef41) 
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
14namespace v8 {
15namespace internal {
16
17StubCache::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
23void 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.
32int 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.
50int 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
58int StubCache::PrimaryOffsetForTesting(Name name, Map map) {
59  return PrimaryOffset(name, map);
60}
61
62int StubCache::SecondaryOffsetForTesting(Name name, Map map) {
63  return SecondaryOffset(name, map);
64}
65
66#ifdef DEBUG
67namespace {
68
69bool 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
83void 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
112MaybeObject 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
127void 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