Home | History | Annotate | Download | only in compiler 
      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
    121