Explore how stack type metadata can be 'compiled' as code, not pre-elaborated into struct types

[stephenrkell]

Recently we observed that stackframe struct types should not be exposed to clients (#82).

But also, stackframe struct types are space-inefficient anyway because a given frame has so many variants. These are a principal component of excessive uniqtype size on disk (see also #12).

Taking inspiration from the 'compiled' approach of eh_elfs (#83), can we devise a similar approach? This would mean some generated code computes the frame layout on demand, or perhaps computes the answers to the query "given an offset in the frame, what lives there?".

I think this would be very similar to the eh_elfs approach, although note that a big 'compiled' binary search tree is not space-efficient either, so maybe a custom table is the way (#83 again) and the only compiled code snippets are somehow outlined/commoned parts. Or maybe they disappear entirely and it's just a custom table! The main idea is pooling over all functions and all layouts thereof, to save space opportunistically.

[stephenrkell]

One simple, not-so-compiled approach here might just be to pool the field definitions into one big list -- each entry being "local x of type t at location loc" -- and then record each frame layout as a set of indices into this list. Or it could also be a list of displacements (e.g. "start at 0, then forward 3, then back 1, then...").

There is then a little optimisation problem: how should we order the list to maximise efficiency? Efficiency includes compactness of the indices/displacements -- imagine that we can have some kind of run-length encoding, e.g. "block of 4 starting at 0" -- but also efficiency of search/traversal. We like to do the latter binary search... and we can still do that as long as we have a frame representation ordered by offset (e.g. the list is really an array, with records ordered by offset). The pool does not need to be ordered globally by offset... maybe cache locality / chunking would be sane. Only go there if we can actually measure this... this only makes sense for query-intensive, stack-intensive workloads.

[stephenrkell]

Then there is a question of how wide the pooling can go. It might make sense to pool across many functions, because functions in (e.g.) the same file often have a common pattern. Pool across the whole DSO? This might make for big offsets/displacements. But if we have a clever locality/chunking approach we can recover common-case sanity.

[stephenrkell]

If each entry in a frame layout is "(name, type, offset)" then the domain we are coding is a list of these -- for each program-counter key, there is such a list as a value.. But offset varies a lot, while name and type recur. I was thinking about Huffman coding here, but I wonder if there's a variation of it for more structured data. We would not get far with just assigning Huffman prefix codes to distinct lists of 3-tuples... only that the layouts that spanned the most program counter values would get the lowest codes.

With each (name, type) pair, we could append a list of offsets. (We could Huffman-code that list somehow, so that common offsets get a low index. Is that even useful? No because we'd never consume these codewords in sequence.)

Then a frame is a compact array of pairs <pair-id>, <location-id>. To get the offset we need to look up the location-id in the per-pair list. They are still kept sorted, though, so we can still binary-search. Each array entry likely fits in 32 bits at most, say 20 bits for the pair (1M name-type pairs per DSO) and 12 for the offset (4096 distinct frame/reg locations for any given pair). A frame layout with 10 entries is then taking 40 bytes to encode... hmm. Layouts that are subsequences of one another can be overlapped/merged, but that still feels a bit fragile.

[stephenrkell]

I've started doing this.

Instead of location-id and pooling all locations, we probably want a compact representation covering three cases: fixed offset, numbered register, or "index into an oddball table". The oddballs are pooled, but the others are immediate.

If we need to we can make registers and oddball indices the negative portion of a signed integer space, and bona fide stack offsets the positive.

Oddballs probably include stuff computed by a function, living at "no offset" (another arbitrary large/negative number).

Does each entry need a size? This would allow binary search to identify "holes" quickly. But holes may not be a common case and we can identify them at the end.

[stephenrkell]

The name-type pairs should really be name-type-piece triples. That way, each has a knowable size.

Ideally we would thread together pieces so that given one, we can find the others. That will probably make the decompositions we're considering blow up... might be better to require such a client to do a full search.