Line data Source code
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 1699072 : bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
33 1699072 : if (size_ >= max_) return false; // Don't grow past the maximum size.
34 :
35 : // Allocate a new block of entries 4x the size.
36 299656 : Entry* old_entries = entries_;
37 299656 : size_t old_size = size_ + kLinearProbe;
38 299656 : size_ *= 4;
39 299656 : size_t num_entries = size_ + kLinearProbe;
40 299659 : 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 15910377 : for (size_t i = 0; i < old_size; ++i) {
45 7805360 : Entry* old = &old_entries[i];
46 7805360 : if (old->value_) {
47 3986807 : size_t hash = hash_(old->key_);
48 3988002 : size_t start = hash & (size_ - 1);
49 3988002 : size_t end = start + kLinearProbe;
50 4692076 : for (size_t j = start; j < end; ++j) {
51 4339968 : Entry* entry = &entries_[j];
52 4339968 : if (!entry->value_) {
53 3986735 : entry->key_ = old->key_;
54 3987931 : entry->value_ = old->value_;
55 3987931 : break;
56 : }
57 : }
58 : }
59 : }
60 : return true;
61 : }
62 :
63 :
64 : template <typename Key, typename Hash, typename Pred>
65 43698796 : Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
66 : size_t hash = hash_(key);
67 43703198 : if (!entries_) {
68 : // Allocate the initial entries and insert the first entry.
69 : size_t num_entries = kInitialSize + kLinearProbe;
70 5933927 : entries_ = zone->NewArray<Entry>(num_entries);
71 5933927 : size_ = kInitialSize;
72 : memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
73 5933927 : Entry* entry = &entries_[hash & (kInitialSize - 1)];
74 5803147 : entry->key_ = key;
75 5933927 : return &entry->value_;
76 : }
77 :
78 : for (;;) {
79 : // Search up to N entries after (linear probing).
80 38068614 : size_t start = hash & (size_ - 1);
81 38068614 : size_t end = start + kLinearProbe;
82 77779772 : for (size_t i = start; i < end; i++) {
83 56225119 : Entry* entry = &entries_[i];
84 56225119 : if (pred_(entry->key_, key)) return &entry->value_;
85 36313853 : if (!entry->value_) {
86 16438681 : entry->key_ = key;
87 16458274 : return &entry->value_;
88 : }
89 : }
90 :
91 1699074 : 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 1399418 : Entry* entry = &entries_[hash & (size_ - 1)];
96 1399418 : entry->key_ = key;
97 1399418 : entry->value_ = nullptr;
98 1399418 : return &entry->value_;
99 : }
100 :
101 :
102 : template <typename Key, typename Hash, typename Pred>
103 42521368 : void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
104 42521368 : if (entries_) {
105 701372553 : for (size_t i = 0; i < size_ + kLinearProbe; i++) {
106 344042110 : if (entries_[i].value_) nodes->push_back(entries_[i].value_);
107 : }
108 : }
109 42521067 : }
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
|