src/v8/src/compiler/node-cache.cc

   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 namespace v8 {
   8 namespace internal {
   9 namespace compiler {
  10
  11 #define INITIAL_SIZE 16
  12 #define LINEAR_PROBE 5
  13
  14 template <typename Key>
  15 int32_t NodeCacheHash(Key key) {
  16   UNIMPLEMENTED();
  17   return 0;
  18 }
  19
  20 template <>
  21 inline int32_t NodeCacheHash(int32_t key) {
  22   return ComputeIntegerHash(key, 0);
  23 }
  24
  25
  26 template <>
  27 inline int32_t NodeCacheHash(int64_t key) {
  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.
  47
  48   // Allocate a new block of entries 4x the size.
  49   Entry* old_entries = entries_;
  50   int old_size = size_ + LINEAR_PROBE;
  51   size_ = size_ * 4;
  52   int num_entries = size_ + LINEAR_PROBE;
  53   entries_ = zone->NewArray<Entry>(num_entries);
  54   memset(entries_, 0, sizeof(Entry) * num_entries);
  55
  56   // Insert the old entries into the new block.
  57   for (int i = 0; i < old_size; i++) {
  58     Entry* old = &old_entries[i];
  59     if (old->value_ != NULL) {
  60       int hash = NodeCacheHash(old->key_);
  61       int start = hash & (size_ - 1);
  62       int end = start + LINEAR_PROBE;
  63       for (int j = start; j < end; j++) {
  64         Entry* entry = &entries_[j];
  65         if (entry->value_ == NULL) {
  66           entry->key_ = old->key_;
  67           entry->value_ = old->value_;
  68           break;
  69         }
  70       }
  71     }
  72   }
  73   return true;
  74 }
  75
  76
  77 template <typename Key>
  78 Node** NodeCache<Key>::Find(Zone* zone, Key key) {
  79   int32_t hash = NodeCacheHash(key);
  80   if (entries_ == NULL) {
  81     // Allocate the initial entries and insert the first entry.
  82     int num_entries = INITIAL_SIZE + LINEAR_PROBE;
  83     entries_ = zone->NewArray<Entry>(num_entries);
  84     size_ = INITIAL_SIZE;
  85     memset(entries_, 0, sizeof(Entry) * num_entries);
  86     Entry* entry = &entries_[hash & (INITIAL_SIZE - 1)];
  87     entry->key_ = key;
  88     return &entry->value_;
  89   }
  90
  91   while (true) {
  92     // Search up to N entries after (linear probing).
  93     int start = hash & (size_ - 1);
  94     int end = start + LINEAR_PROBE;
  95     for (int i = start; i < end; i++) {
  96       Entry* entry = &entries_[i];
  97       if (entry->key_ == key) return &entry->value_;
  98       if (entry->value_ == NULL) {
  99         entry->key_ = key;
 100         return &entry->value_;
 101       }
 102     }
 103
 104     if (!Resize(zone)) break;  // Don't grow past the maximum size.
 105   }
 106
 107   // If resized to maximum and still didn't find space, overwrite an entry.
 108   Entry* entry = &entries_[hash & (size_ - 1)];
 109   entry->key_ = key;
 110   entry->value_ = NULL;
 111   return &entry->value_;
 112 }
 113
 114
 115 template class NodeCache<int64_t>;
 116 template class NodeCache<int32_t>;
 117 template class NodeCache<void*>;
 118 }
 119 }
 120 }  // namespace v8::internal::compiler