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     1362108 : bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) {
      33     1362108 :   if (size_ >= max_) return false;  // Don't grow past the maximum size.
      34             : 
      35             :   // Allocate a new block of entries 4x the size.
      36      276783 :   Entry* old_entries = entries_;
      37      276783 :   size_t old_size = size_ + kLinearProbe;
      38      276783 :   size_ *= 4;
      39      276783 :   size_t num_entries = size_ + kLinearProbe;
      40      276783 :   entries_ = zone->NewArray<Entry>(num_entries);
      41             :   memset(entries_, 0, sizeof(Entry) * num_entries);
      42             : 
      43             :   // Insert the old entries into the new block.
      44     7783482 :   for (size_t i = 0; i < old_size; ++i) {
      45     7506699 :     Entry* old = &old_entries[i];
      46     7506699 :     if (old->value_) {
      47     3911328 :       size_t hash = hash_(old->key_);
      48     3911328 :       size_t start = hash & (size_ - 1);
      49     3911328 :       size_t end = start + kLinearProbe;
      50     4278398 :       for (size_t j = start; j < end; ++j) {
      51     4278342 :         Entry* entry = &entries_[j];
      52     4278342 :         if (!entry->value_) {
      53     3911272 :           entry->key_ = old->key_;
      54     3911272 :           entry->value_ = old->value_;
      55     3911272 :           break;
      56             :         }
      57             :       }
      58             :     }
      59             :   }
      60             :   return true;
      61             : }
      62             : 
      63             : 
      64             : template <typename Key, typename Hash, typename Pred>
      65    34153010 : Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
      66             :   size_t hash = hash_(key);
      67    34153088 :   if (!entries_) {
      68             :     // Allocate the initial entries and insert the first entry.
      69             :     size_t num_entries = kInitialSize + kLinearProbe;
      70     4572803 :     entries_ = zone->NewArray<Entry>(num_entries);
      71     4572803 :     size_ = kInitialSize;
      72             :     memset(entries_, 0, sizeof(Entry) * num_entries);
      73     4572803 :     Entry* entry = &entries_[hash & (kInitialSize - 1)];
      74     4407981 :     entry->key_ = key;
      75     4572803 :     return &entry->value_;
      76             :   }
      77             : 
      78             :   for (;;) {
      79             :     // Search up to N entries after (linear probing).
      80    29857132 :     size_t start = hash & (size_ - 1);
      81    29857132 :     size_t end = start + kLinearProbe;
      82    45725113 :     for (size_t i = start; i < end; i++) {
      83    44363005 :       Entry* entry = &entries_[i];
      84    44363005 :       if (pred_(entry->key_, key)) return &entry->value_;
      85    30165096 :       if (!entry->value_) {
      86    14294792 :         entry->key_ = key;
      87    14297115 :         return &entry->value_;
      88             :       }
      89             :     }
      90             : 
      91     1362108 :     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     1085325 :   Entry* entry = &entries_[hash & (size_ - 1)];
      96     1085325 :   entry->key_ = key;
      97     1085325 :   entry->value_ = nullptr;
      98     1085325 :   return &entry->value_;
      99             : }
     100             : 
     101             : 
     102             : template <typename Key, typename Hash, typename Pred>
     103    29957959 : void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
     104    29957959 :   if (entries_) {
     105   337239893 :     for (size_t i = 0; i < size_ + kLinearProbe; i++) {
     106   337240633 :       if (entries_[i].value_) nodes->push_back(entries_[i].value_);
     107             :     }
     108             :   }
     109    29957219 : }
     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             : }  // namespace v8