Home | History | Annotate | Download | only in ic 
      1 // Copyright 2012 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 #ifndef V8_IC_STUB_CACHE_H_
      6 #define V8_IC_STUB_CACHE_H_
      7 
      8 #include "src/macro-assembler.h"
      9 #include "src/objects/name.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 
     14 // The stub cache is used for megamorphic property accesses.
     15 // It maps (map, name, type) to property access handlers. The cache does not
     16 // need explicit invalidation when a prototype chain is modified, since the
     17 // handlers verify the chain.
     18 
     19 
     20 class SCTableReference {
     21  public:
     22   Address address() const { return address_; }
     23 
     24  private:
     25   explicit SCTableReference(Address address) : address_(address) {}
     26 
     27   Address address_;
     28 
     29   friend class StubCache;
     30 };
     31 
     32 
     33 class StubCache {
     34  public:
     35   struct Entry {
     36     Name* key;
     37     MaybeObject* value;
     38     Map* map;
     39   };
     40 
     41   void Initialize();
     42   // Access cache for entry hash(name, map).
     43   MaybeObject* Set(Name* name, Map* map, MaybeObject* handler);
     44   MaybeObject* Get(Name* name, Map* map);
     45   // Clear the lookup table (@ mark compact collection).
     46   void Clear();
     47 
     48   enum Table { kPrimary, kSecondary };
     49 
     50   SCTableReference key_reference(StubCache::Table table) {
     51     return SCTableReference(
     52         reinterpret_cast<Address>(&first_entry(table)->key));
     53   }
     54 
     55   SCTableReference map_reference(StubCache::Table table) {
     56     return SCTableReference(
     57         reinterpret_cast<Address>(&first_entry(table)->map));
     58   }
     59 
     60   SCTableReference value_reference(StubCache::Table table) {
     61     return SCTableReference(
     62         reinterpret_cast<Address>(&first_entry(table)->value));
     63   }
     64 
     65   StubCache::Entry* first_entry(StubCache::Table table) {
     66     switch (table) {
     67       case StubCache::kPrimary:
     68         return StubCache::primary_;
     69       case StubCache::kSecondary:
     70         return StubCache::secondary_;
     71     }
     72     UNREACHABLE();
     73   }
     74 
     75   Isolate* isolate() { return isolate_; }
     76 
     77   // Setting the entry size such that the index is shifted by Name::kHashShift
     78   // is convenient; shifting down the length field (to extract the hash code)
     79   // automatically discards the hash bit field.
     80   static const int kCacheIndexShift = Name::kHashShift;
     81 
     82   static const int kPrimaryTableBits = 11;
     83   static const int kPrimaryTableSize = (1 << kPrimaryTableBits);
     84   static const int kSecondaryTableBits = 9;
     85   static const int kSecondaryTableSize = (1 << kSecondaryTableBits);
     86 
     87   // Some magic number used in the secondary hash computation.
     88   static const int kSecondaryMagic = 0xb16ca6e5;
     89 
     90   static int PrimaryOffsetForTesting(Name* name, Map* map) {
     91     return PrimaryOffset(name, map);
     92   }
     93 
     94   static int SecondaryOffsetForTesting(Name* name, int seed) {
     95     return SecondaryOffset(name, seed);
     96   }
     97 
     98   // The constructor is made public only for the purposes of testing.
     99   explicit StubCache(Isolate* isolate);
    100 
    101  private:
    102   // The stub cache has a primary and secondary level.  The two levels have
    103   // different hashing algorithms in order to avoid simultaneous collisions
    104   // in both caches.  Unlike a probing strategy (quadratic or otherwise) the
    105   // update strategy on updates is fairly clear and simple:  Any existing entry
    106   // in the primary cache is moved to the secondary cache, and secondary cache
    107   // entries are overwritten.
    108 
    109   // Hash algorithm for the primary table.  This algorithm is replicated in
    110   // assembler for every architecture.  Returns an index into the table that
    111   // is scaled by 1 << kCacheIndexShift.
    112   static int PrimaryOffset(Name* name, Map* map);
    113 
    114   // Hash algorithm for the secondary table.  This algorithm is replicated in
    115   // assembler for every architecture.  Returns an index into the table that
    116   // is scaled by 1 << kCacheIndexShift.
    117   static int SecondaryOffset(Name* name, int seed);
    118 
    119   // Compute the entry for a given offset in exactly the same way as
    120   // we do in generated code.  We generate an hash code that already
    121   // ends in Name::kHashShift 0s.  Then we multiply it so it is a multiple
    122   // of sizeof(Entry).  This makes it easier to avoid making mistakes
    123   // in the hashed offset computations.
    124   static Entry* entry(Entry* table, int offset) {
    125     const int multiplier = sizeof(*table) >> Name::kHashShift;
    126     return reinterpret_cast<Entry*>(reinterpret_cast<Address>(table) +
    127                                     offset * multiplier);
    128   }
    129 
    130  private:
    131   Entry primary_[kPrimaryTableSize];
    132   Entry secondary_[kSecondaryTableSize];
    133   Isolate* isolate_;
    134 
    135   friend class Isolate;
    136   friend class SCTableReference;
    137 
    138   DISALLOW_COPY_AND_ASSIGN(StubCache);
    139 };
    140 }  // namespace internal
    141 }  // namespace v8
    142 
    143 #endif  // V8_IC_STUB_CACHE_H_
    144