Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 7 | #include <cstring> |
| 8 | |
| 9 | #include "src/zone.h" |
| 10 | #include "src/zone-containers.h" |
| 11 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | namespace compiler { |
| 15 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 16 | namespace { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 17 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 18 | enum { kInitialSize = 16u, kLinearProbe = 5u }; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 19 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 20 | } // namespace |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 21 | |
| 22 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 23 | template <typename Key, typename Hash, typename Pred> |
| 24 | struct NodeCache<Key, Hash, Pred>::Entry { |
| 25 | Key key_; |
| 26 | Node* value_; |
| 27 | }; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 28 | |
| 29 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 30 | template <typename Key, typename Hash, typename Pred> |
| 31 | bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 36 | size_t old_size = size_ + kLinearProbe; |
| 37 | size_ *= 4; |
| 38 | size_t num_entries = size_ + kLinearProbe; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 39 | entries_ = zone->NewArray<Entry>(num_entries); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 40 | memset(entries_, 0, sizeof(Entry) * num_entries); |
| 41 | |
| 42 | // Insert the old entries into the new block. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 43 | for (size_t i = 0; i < old_size; ++i) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 44 | Entry* old = &old_entries[i]; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 50 | Entry* entry = &entries_[j]; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 51 | if (!entry->value_) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 52 | entry->key_ = old->key_; |
| 53 | entry->value_ = old->value_; |
| 54 | break; |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | } |
| 59 | return true; |
| 60 | } |
| 61 | |
| 62 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 63 | template <typename Key, typename Hash, typename Pred> |
| 64 | Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) { |
| 65 | size_t hash = hash_(key); |
| 66 | if (!entries_) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 67 | // Allocate the initial entries and insert the first entry. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 68 | size_t num_entries = kInitialSize + kLinearProbe; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 69 | entries_ = zone->NewArray<Entry>(num_entries); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 70 | size_ = kInitialSize; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 71 | memset(entries_, 0, sizeof(Entry) * num_entries); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 72 | Entry* entry = &entries_[hash & (kInitialSize - 1)]; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 73 | entry->key_ = key; |
| 74 | return &entry->value_; |
| 75 | } |
| 76 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 77 | for (;;) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 78 | // Search up to N entries after (linear probing). |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 79 | size_t start = hash & (size_ - 1); |
| 80 | size_t end = start + kLinearProbe; |
| 81 | for (size_t i = start; i < end; i++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 82 | Entry* entry = &entries_[i]; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 83 | if (pred_(entry->key_, key)) return &entry->value_; |
| 84 | if (!entry->value_) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 96 | entry->value_ = nullptr; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 97 | return &entry->value_; |
| 98 | } |
| 99 | |
| 100 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 101 | template <typename Key, typename Hash, typename Pred> |
| 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 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 115 | template class NodeCache<int32_t>; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 116 | template class NodeCache<int64_t>; |
| 117 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 118 | template class NodeCache<RelocInt32Key>; |
| 119 | template class NodeCache<RelocInt64Key>; |
| 120 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 121 | } // namespace compiler |
| 122 | } // namespace internal |
| 123 | } // namespace v8 |