1// Copyright 2014 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/compiler/node-cache.h"
6
7#include <cstring>
8
9#include "src/globals.h"
10#include "src/zone/zone-containers.h"
11#include "src/zone/zone.h"
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17namespace {
18
19enum { kInitialSize = 16u, kLinearProbe = 5u };
20
21} // namespace
22
23
24template <typename Key, typename Hash, typename Pred>
25struct NodeCache<Key, Hash, Pred>::Entry {
26 Key key_;
27 Node* value_;
28};
29
30
31template <typename Key, typename Hash, typename Pred>
32bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
33 if (size_ >= max_) return false; // Don't grow past the maximum size.
34
35 // Allocate a new block of entries 4x the size.
36 Entry* old_entries = entries_;
37 size_t old_size = size_ + kLinearProbe;
38 size_ *= 4;
39 size_t num_entries = size_ + kLinearProbe;
40 entries_ = zone->NewArray<Entry>(num_entries);
41 memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
42
43 // Insert the old entries into the new block.
44 for (size_t i = 0; i < old_size; ++i) {
45 Entry* old = &old_entries[i];
46 if (old->value_) {
47 size_t hash = hash_(old->key_);
48 size_t start = hash & (size_ - 1);
49 size_t end = start + kLinearProbe;
50 for (size_t j = start; j < end; ++j) {
51 Entry* entry = &entries_[j];
52 if (!entry->value_) {
53 entry->key_ = old->key_;
54 entry->value_ = old->value_;
55 break;
56 }
57 }
58 }
59 }
60 return true;
61}
62
63
64template <typename Key, typename Hash, typename Pred>
65Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
66 size_t hash = hash_(key);
67 if (!entries_) {
68 // Allocate the initial entries and insert the first entry.
69 size_t num_entries = kInitialSize + kLinearProbe;
70 entries_ = zone->NewArray<Entry>(num_entries);
71 size_ = kInitialSize;
72 memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
73 Entry* entry = &entries_[hash & (kInitialSize - 1)];
74 entry->key_ = key;
75 return &entry->value_;
76 }
77
78 for (;;) {
79 // Search up to N entries after (linear probing).
80 size_t start = hash & (size_ - 1);
81 size_t end = start + kLinearProbe;
82 for (size_t i = start; i < end; i++) {
83 Entry* entry = &entries_[i];
84 if (pred_(entry->key_, key)) return &entry->value_;
85 if (!entry->value_) {
86 entry->key_ = key;
87 return &entry->value_;
88 }
89 }
90
91 if (!Resize(zone)) break; // Don't grow past the maximum size.
92 }
93
94 // If resized to maximum and still didn't find space, overwrite an entry.
95 Entry* entry = &entries_[hash & (size_ - 1)];
96 entry->key_ = key;
97 entry->value_ = nullptr;
98 return &entry->value_;
99}
100
101
102template <typename Key, typename Hash, typename Pred>
103void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
104 if (entries_) {
105 for (size_t i = 0; i < size_ + kLinearProbe; i++) {
106 if (entries_[i].value_) nodes->push_back(entries_[i].value_);
107 }
108 }
109}
110
111
112// -----------------------------------------------------------------------------
113// Instantiations
114
115template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int32_t>;
116template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int64_t>;
117
118template class EXPORT_TEMPLATE_DEFINE(
119 V8_EXPORT_PRIVATE) NodeCache<RelocInt32Key>;
120template class EXPORT_TEMPLATE_DEFINE(
121 V8_EXPORT_PRIVATE) NodeCache<RelocInt64Key>;
122
123} // namespace compiler
124} // namespace internal
125} // namespace v8
126