semi-organized thoughts on AOT ICs

aot_ics.txt

On AOT ICs:

I'm beginning to appreciate how IC stubs resemble tiny
programs. Compared to the deterministic codegen, like in
blinterp and builtins, there is much more combinatorial
variability. Some stub traits have proved more
challenging than others to provide relocations for.
Here is a brief, informal taxonomy, ordered from least
to most difficult:

Solved:

- Class Pointers (23 kinds): Reduced to adding more
  slots in the `AOTIndirectionTable`. 

- Stubs reference a much larger set of Cpp functions in
  CallWithABI. Large enough to motivate filling the
  table with an iter-macro to avoid repetition.

- Pointers to GC things: IC Stubs can embed pointers to
  things which move. Solved by routing through the
  indirection table - GC-movable pointers become
  table slot loads instead of embedded immediates.

Unsolved: 

- Embedded Shape Pointers: The document Matt shared
  with me on Tuesday turned out to be super pertinent.
  The following day I confirmed that this category of
  IC stubs (those which specialize and guard around
  objects of a particular Shape) were all failing. The
  issue seems to be that guarding shapes is done by
  identity (pointer comparison), rather than content.
  The remainder of this document is an early proposal
  for what an AOT-relocation friendly `Shape` _could_
  look like.

Shape Table:

The `Shape` class touches various components of the
engine:

- Shape Pointers exist in the Object header [1] as a
  word. Would be replaced with a ShapeIndex (half word).

- Shapes are Guarded against by identity in ICs. A table
  would require an extra load. However, a ShapeIndex scheme
  which encodes common properties in bit-flags could make
  some checks cheaper (e.g isNative or isDictionary)
  by passing directly in the ShapeIndex stubField rather
  than through the `Shape*` 

- GC compaction can move shapes, updating their pointers
  [2]. In a ShapeTable + ShapeIndex setting, the GC would need
  to target the table values, rather than the index.
  This could actually be faster (?) Updating one table
  slot which N objects share, rather than N object
  headers.

- Shared shapes already are content addressed, which
  guarantees the same shapes get the same pointer _within
  a zone_.

- Dictionary Shapes are mutable and private. Mutability
  would make content hashes unstable, however, being
  private means stubs specializing on dictionary
  objects have low reuse value anyways (?)

Potential ShapeIndex Mechanisms:

1. Counter: ShapeIndex as sequential counter: brittle to
   allocation orderings and the guest program. The
   non-determinism means this doesn't quite solve the
   problem.

2. Source-bucketed counter: One way to make counters
   locally stable would be to prefix counters with a
   "bucket" - a hash based on source context, such as
   the script source or bytecode offset. This kind of
   reminds me of context sensitive hashing for
   identifying useful branch prediction patterns.
    
   However, wouldn't we want two objects with identical
   shape to attach to the same stub, despite coming from
   different buckets? I think source info would be
   useful if we were trying to eagerly _pre-attach_
   stubs at startup, which could be an interesting
   direction, though I don't have an intuition for cost
   savings.

3. Content Hash: ShapeIndex as hash of content.
   Deterministic for a given shape, but collisions will
   require probing, which adds comparison overhead but
   no pointer chasing.

4. A way to combine a content hash (2) while reserving
   some lower bits as flags for common shape properties
   such as isNative or isDictionary. Both of these exist
   in `immutableFlags`, but are attained through a load.
   ShapeGuards could read these properties quickly just
   from the index if encoded as bit-flags.
    
5. A way to combine source bucketing (2) with content
   hashing (3). If collisions are an issue, the bucket
   size can act like a parameter - 0 bits for one bucket
   serving a global content hash space, n bits would
   mean 2^n local buckets. However, source bucketing
   fragments identical shapes across buckets, which
   hurts AOT IC reuse - structurally identical shapes
   from different allocation sites get different indices.
   This may only make sense if content-hash collisions
   are observed to be both high and costly enough to
   outweigh the fragmentation.

Refs:
[1] JSObject<Shape>: https://searchfox.org/firefox-main/rev/662d18616bbb2da4c5a8758da50fc9d591d18c19/js/src/vm/JSObject.h#89
[2] ShapeZone::fixupPropMapShapeTableAfterMovingGC: https://searchfox.org/firefox-main/rev/662d18616bbb2da4c5a8758da50fc9d591d18c19/js/src/vm/ShapeZone.cpp#15

• Pointers to GC things: IC Stubs can embed pointers to
  things which move. Solved by routing through the
  indirection table - GC-movable pointers become
  table slot loads instead of embedded immediates.

-- isn't the point of stub fields?