Description
I've been thinking about a new approach for computing the layout of generators, since I merged #59897. Actually, I've been thinking about it before that, but the approach there felt a bit safer to start with.
The idea is that we use the struct layout computation, rather than the enum computation, as a starting point, and add in the fact that fields can overlap. The basic algorithm is simple:
- We iterate through every field, in descending order of alignment and number of conflicts with other fields*.
- For each field, pick the first offset (with respect to its alignment) that it's still allowed to occupy, given the other fields that we've already placed.
Because we're working in descending order of alignment (and alignments are all powers of 2), we should be able to use a "segment-tree-like" data structure with a bitset of fields that are still allowed to be placed at a given position. This means that updating the tree is logarithmic in the number of alignment levels, and so is searching for the first position a field is allowed to occupy.
This greedy algorithm should be an improvement over the current algorithm, which doesn't attempt to overlap any fields that are live across more than one yield in the generator. It also wouldn't force "overlap-zone" fields to always come after "non-overlap" fields, which means we can do a better job of eliminating padding. Finally, the logic should be easier to follow in code than the current optimization (once the data structure is written).
This problem is NP-complete, so there might be better algorithms than this out there. I'd love to hear suggestions!
(*) The number of conflicts is the number of other fields in this struct that cannot be overlapped with the current field. The exact heuristic may change. Today, we use number of conflicts to help us decide which fields get to stay in an "overlap zone" and which get kicked out. Then, we use order of alignment to lay out the fields in each zone.