• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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