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 | |
13 | namespace v8 { |
14 | namespace internal { |
15 | namespace compiler { |
16 | |
17 | namespace { |
18 | |
19 | enum { kInitialSize = 16u, kLinearProbe = 5u }; |
20 | |
21 | } // namespace |
22 | |
23 | |
24 | template <typename Key, typename Hash, typename Pred> |
25 | struct NodeCache<Key, Hash, Pred>::Entry { |
26 | Key key_; |
27 | Node* value_; |
28 | }; |
29 | |
30 | |
31 | template <typename Key, typename Hash, typename Pred> |
32 | bool 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 | |
64 | template <typename Key, typename Hash, typename Pred> |
65 | Node** 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 | |
102 | template <typename Key, typename Hash, typename Pred> |
103 | void 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 | |
115 | template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int32_t>; |
116 | template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int64_t>; |
117 | |
118 | template class EXPORT_TEMPLATE_DEFINE( |
119 | V8_EXPORT_PRIVATE) NodeCache<RelocInt32Key>; |
120 | template class EXPORT_TEMPLATE_DEFINE( |
121 | V8_EXPORT_PRIVATE) NodeCache<RelocInt64Key>; |
122 | |
123 | } // namespace compiler |
124 | } // namespace internal |
125 | } // namespace v8 |
126 | |