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     1999545 : bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
      33     1999545 :   if (size_ >= max_) return false;  // Don't grow past the maximum size.
      34             : 
      35             :   // Allocate a new block of entries 4x the size.
      36      258741 :   Entry* old_entries = entries_;
      37      258741 :   size_t old_size = size_ + kLinearProbe;
      38      258741 :   size_ *= 4;
      39      258741 :   size_t num_entries = size_ + kLinearProbe;
      40      258741 :   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     7225848 :   for (size_t i = 0; i < old_size; ++i) {
      45     6967108 :     Entry* old = &old_entries[i];
      46     6967108 :     if (old->value_) {
      47     3696403 :       size_t hash = hash_(old->key_);
      48     3697505 :       size_t start = hash & (size_ - 1);
      49     3697505 :       size_t end = start + kLinearProbe;
      50     4053228 :       for (size_t j = start; j < end; ++j) {
      51     4053098 :         Entry* entry = &entries_[j];
      52     4053098 :         if (!entry->value_) {
      53     3696272 :           entry->key_ = old->key_;
      54     3697375 :           entry->value_ = old->value_;
      55     3697375 :           break;
      56             :         }
      57             :       }
      58             :     }
      59             :   }
      60             :   return true;
      61             : }
      62             : 
      63             : 
      64             : template <typename Key, typename Hash, typename Pred>
      65    40105552 : Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
      66             :   size_t hash = hash_(key);
      67    40105209 :   if (!entries_) {
      68             :     // Allocate the initial entries and insert the first entry.
      69             :     size_t num_entries = kInitialSize + kLinearProbe;
      70     3969196 :     entries_ = zone->NewArray<Entry>(num_entries);
      71     3969196 :     size_ = kInitialSize;
      72             :     memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
      73     3969196 :     Entry* entry = &entries_[hash & (kInitialSize - 1)];
      74     3949986 :     entry->key_ = key;
      75     3969196 :     return &entry->value_;
      76             :   }
      77             : 
      78             :   for (;;) {
      79             :     // Search up to N entries after (linear probing).
      80    36394702 :     size_t start = hash & (size_ - 1);
      81    36394702 :     size_t end = start + kLinearProbe;
      82    56726279 :     for (size_t i = start; i < end; i++) {
      83    54726733 :       Entry* entry = &entries_[i];
      84    54726733 :       if (pred_(entry->key_, key)) return &entry->value_;
      85    35511422 :       if (!entry->value_) {
      86    15160666 :         entry->key_ = key;
      87    15179845 :         return &entry->value_;
      88             :       }
      89             :     }
      90             : 
      91     1999546 :     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     1740804 :   Entry* entry = &entries_[hash & (size_ - 1)];
      96     1740804 :   entry->key_ = key;
      97     1740804 :   entry->value_ = nullptr;
      98     1740804 :   return &entry->value_;
      99             : }
     100             : 
     101             : 
     102             : template <typename Key, typename Hash, typename Pred>
     103    41934019 : void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
     104    41934019 :   if (entries_) {
     105   336390945 :     for (size_t i = 0; i < size_ + kLinearProbe; i++) {
     106   336391273 :       if (entries_[i].value_) nodes->push_back(entries_[i].value_);
     107             :     }
     108             :   }
     109    41933691 : }
     110             : 
     111             : 
     112             : // -----------------------------------------------------------------------------
     113             : // Instantiations
     114             : 
     115             : template class V8_EXPORT_PRIVATE NodeCache<int32_t>;
     116             : template class V8_EXPORT_PRIVATE NodeCache<int64_t>;
     117             : 
     118             : template class V8_EXPORT_PRIVATE NodeCache<RelocInt32Key>;
     119             : template class V8_EXPORT_PRIVATE NodeCache<RelocInt64Key>;
     120             : 
     121             : }  // namespace compiler
     122             : }  // namespace internal
     123      178779 : }  // namespace v8