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 #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>
     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>
     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>
    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