Line data    Source code

       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/globals.h"
      10             : #include "src/zone/zone-containers.h"
      11             : #include "src/zone/zone.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17             : namespace {
      18             : 
      19             : enum { kInitialSize = 16u, kLinearProbe = 5u };
      20             : 
      21             : }  // namespace
      22             : 
      23             : 
      24             : template <typename Key, typename Hash, typename Pred>
      25             : struct NodeCache<Key, Hash, Pred>::Entry {
      26             :   Key key_;
      27             :   Node* value_;
      28             : };
      29             : 
      30             : 
      31             : template <typename Key, typename Hash, typename Pred>
      32     1694603 : bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
      33     1694603 :   if (size_ >= max_) return false;  // Don't grow past the maximum size.
      34             : 
      35             :   // Allocate a new block of entries 4x the size.
      36      299089 :   Entry* old_entries = entries_;
      37      299089 :   size_t old_size = size_ + kLinearProbe;
      38      299089 :   size_ *= 4;
      39      299089 :   size_t num_entries = size_ + kLinearProbe;
      40      299091 :   entries_ = zone->NewArray<Entry>(num_entries);
      41             :   memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
      42             : 
      43             :   // Insert the old entries into the new block.
      44    15631189 :   for (size_t i = 0; i < old_size; ++i) {
      45     7666050 :     Entry* old = &old_entries[i];
      46     7666050 :     if (old->value_) {
      47     3969178 :       size_t hash = hash_(old->key_);
      48     3970373 :       size_t start = hash & (size_ - 1);
      49     3970373 :       size_t end = start + kLinearProbe;
      50     4689675 :       for (size_t j = start; j < end; ++j) {
      51     4329910 :         Entry* entry = &entries_[j];
      52     4329910 :         if (!entry->value_) {
      53     3969063 :           entry->key_ = old->key_;
      54     3970259 :           entry->value_ = old->value_;
      55     3970259 :           break;
      56             :         }
      57             :       }
      58             :     }
      59             :   }
      60             :   return true;
      61             : }
      62             : 
      63             : 
      64             : template <typename Key, typename Hash, typename Pred>
      65    43559668 : Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
      66             :   size_t hash = hash_(key);
      67    43564482 :   if (!entries_) {
      68             :     // Allocate the initial entries and insert the first entry.
      69             :     size_t num_entries = kInitialSize + kLinearProbe;
      70     5912276 :     entries_ = zone->NewArray<Entry>(num_entries);
      71     5912276 :     size_ = kInitialSize;
      72             :     memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
      73     5912276 :     Entry* entry = &entries_[hash & (kInitialSize - 1)];
      74     5781573 :     entry->key_ = key;
      75     5912276 :     return &entry->value_;
      76             :   }
      77             : 
      78             :   for (;;) {
      79             :     // Search up to N entries after (linear probing).
      80    37950971 :     size_t start = hash & (size_ - 1);
      81    37950971 :     size_t end = start + kLinearProbe;
      82    77515805 :     for (size_t i = start; i < end; i++) {
      83    56038778 :       Entry* entry = &entries_[i];
      84    56038778 :       if (pred_(entry->key_, key)) return &entry->value_;
      85    36185425 :       if (!entry->value_) {
      86    16383428 :         entry->key_ = key;
      87    16403008 :         return &entry->value_;
      88             :       }
      89             :     }
      90             : 
      91     1694610 :     if (!Resize(zone)) break;  // Don't grow past the maximum size.
      92             :   }
      93             : 
      94             :   // If resized to maximum and still didn't find space, overwrite an entry.
      95     1395519 :   Entry* entry = &entries_[hash & (size_ - 1)];
      96     1395519 :   entry->key_ = key;
      97     1395519 :   entry->value_ = nullptr;
      98     1395519 :   return &entry->value_;
      99             : }
     100             : 
     101             : 
     102             : template <typename Key, typename Hash, typename Pred>
     103    42484137 : void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
     104    42484137 :   if (entries_) {
     105   695672657 :     for (size_t i = 0; i < size_ + kLinearProbe; i++) {
     106   341199171 :       if (entries_[i].value_) nodes->push_back(entries_[i].value_);
     107             :     }
     108             :   }
     109    42483967 : }
     110             : 
     111             : 
     112             : // -----------------------------------------------------------------------------
     113             : // Instantiations
     114             : 
     115             : template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int32_t>;
     116             : template class EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) NodeCache<int64_t>;
     117             : 
     118             : template class EXPORT_TEMPLATE_DEFINE(
     119             :     V8_EXPORT_PRIVATE) NodeCache<RelocInt32Key>;
     120             : template class EXPORT_TEMPLATE_DEFINE(
     121             :     V8_EXPORT_PRIVATE) NodeCache<RelocInt64Key>;
     122             : 
     123             : }  // namespace compiler
     124             : }  // namespace internal
     125             : }  // namespace v8