Heap vector based inline caches

[aapoalas]

Try an inline caching strategy as follows:

Three(?) heap vectors are introduced, one for each of the following inline cache structs:

struct PropertyLookupCacheHeapData {
  shape: Option<Shape>, // Option<NonZeroU32> index to ShapeHeapData heap vector; None means this cache is not used.
  index: u32, // index into object property entries; TODO: Split this into its own cache line to help matching
}

struct PrototypePropertyLookupCacheHeapData {
  property_cache: PropertyLookupCacheHeapData,
  prototype: Object, // The prototype object to load property from; TODO: Split into its own cache line again
}

struct MixedPropertyLookupCacheHeapData {
  property_cache: PropertyLookupCacheHeapData,
  prototype: Option<Object>, // None signifies that the property is found in the object itself, not in prototype
}

In functions the property lookup methods get a new parameter that is used to index into a Box<[Option<LookupCache>]>.

// TODO: Computed property access needs its own setup of key-to-cache?
enum LookupCache {
  Property(PropertyLookupCache), // index into PropertyLookupCacheHeapData heap vector
  Prototype(PrototypePropertyLookupCache),
  Mixed(MixedPropertyLookupCache),
  Megamorphic, // Stop trying to cache this lookup
}

Each index "owns" a known number of cache entries. eg. Property would be four PropertyLookupCacheHeapData entries in the vector, each initially pushed and prepared as None caches in the heap vector. Prototype and Mixed would be two. These numbers are based upon lookup-sites-by-cache-line calculation, each coming to 2 sites by cache line. These can be changed as needed and becomes possible based on the "split into own cache line" work. Additionally, extra LookupCache variants like PrototypeLarge can be added that "owns" more lines.

Initially the LookupCache for a property lookup is None. When the lookup is performed, an on-stack entity may be populated by the lookup code. If the entity points to a direct property, then a PropertyLookupCache is created and is written into the LookupCache slot. If it points to prototype, a PrototypePropertyLookupCache is created.

If the LookupCache already exists, its "owned" slots are checked for matches against the object shape. If none is found, then a new lookup is done and again an on-stack entity may be populated by the lookup code. If the lookup produces a property access and the existing LookupCache is Prototype, or vice versa and there is room in the lookup cache then the LookupCache is converted into a Mixed lookup cache.

During GC marking live functions mark their LookupCaches as live. Live LookupCaches do not mark their Shapes or prototype Objects as live. During GC sweeping, lookup cache heap vectors are compacted just like any other heap vector and functions' references to them are updated. Lookup cache entries that refer to dead Shapes are removed, and the cache entries are removed. Compaction "within" the owned lookup cache entries may or may not happen...

Not-found-caches

When a given shape does not contain a property key, it would be nice to cache that information in a PropertyLookupCache. But: If we do that, it means that prototype object changes affect not only PrototypePropertyLookupCache data but also PropertyLookupCache properties. A lookup that failed could turn into a successful lookup with an addition to a prototype. This would make the performance of prototype changes worse. This may be a problem.

Not-found-cache entries are still a potentially very interesting proposition.