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