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