node-cache.cc 3.25 KB
Newer Older
1 2 3 4
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#include "src/compiler/node-cache.h"

7 8
#include <cstring>

9
#include "src/zone.h"
10
#include "src/zone-containers.h"
11

12 13 14 15
namespace v8 {
namespace internal {
namespace compiler {

16 17 18 19 20 21 22
namespace {

enum { kInitialSize = 16u, kLinearProbe = 5u };

}  // namespace


23 24 25 26 27
template <typename Key, typename Hash, typename Pred>
struct NodeCache<Key, Hash, Pred>::Entry {
  Key key_;
  Node* value_;
};
28 29


30 31
template <typename Key, typename Hash, typename Pred>
bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
32 33 34 35
  if (size_ >= max_) return false;  // Don't grow past the maximum size.

  // Allocate a new block of entries 4x the size.
  Entry* old_entries = entries_;
36 37 38
  size_t old_size = size_ + kLinearProbe;
  size_ *= 4;
  size_t num_entries = size_ + kLinearProbe;
39
  entries_ = zone->NewArray<Entry>(num_entries);
40 41 42
  memset(entries_, 0, sizeof(Entry) * num_entries);

  // 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 46 47 48 49
    if (old->value_) {
      size_t hash = hash_(old->key_);
      size_t start = hash & (size_ - 1);
      size_t end = start + kLinearProbe;
      for (size_t j = start; j < end; ++j) {
50
        Entry* entry = &entries_[j];
51
        if (!entry->value_) {
52 53 54 55 56 57 58 59 60 61 62
          entry->key_ = old->key_;
          entry->value_ = old->value_;
          break;
        }
      }
    }
  }
  return true;
}


63 64 65 66
template <typename Key, typename Hash, typename Pred>
Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
  size_t hash = hash_(key);
  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 74 75 76
    entry->key_ = key;
    return &entry->value_;
  }

77
  for (;;) {
78
    // Search up to N entries after (linear probing).
79 80 81
    size_t start = hash & (size_ - 1);
    size_t end = start + kLinearProbe;
    for (size_t i = start; i < end; i++) {
82
      Entry* entry = &entries_[i];
83 84
      if (pred_(entry->key_, key)) return &entry->value_;
      if (!entry->value_) {
85 86 87 88 89 90 91 92 93 94 95
        entry->key_ = key;
        return &entry->value_;
      }
    }

    if (!Resize(zone)) break;  // Don't grow past the maximum size.
  }

  // If resized to maximum and still didn't find space, overwrite an entry.
  Entry* entry = &entries_[hash & (size_ - 1)];
  entry->key_ = key;
96
  entry->value_ = nullptr;
97 98 99 100
  return &entry->value_;
}


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 113 114

// -----------------------------------------------------------------------------
// Instantiations


115
template class NodeCache<int32_t>;
116
template class NodeCache<int64_t>;
117

118 119 120
template class NodeCache<RelocInt32Key>;
template class NodeCache<RelocInt64Key>;

121 122 123
}  // namespace compiler
}  // namespace internal
}  // namespace v8