Layout

An attempt at an IR for layout calculation of Rust datastructures. This separates out a specification of how layouts are supposed to work, from an evaluation of an abstract IR to actually calculate the layout of data structures.

A layout consists of:

• A size.
• A alignment.
• Optionally, a niche.
• A backend representation of the type, this influences whether the type can be passed in for-example a register.
• The shape of fields and variants within ADTs.
• Whether the type is inhabited.

In rustc, all of these separate properties are generated at once for a type, in one large function. This is a large convoluted mess. One goal of this project is to rewrite this code, and make it more understandable. However, what we also hope to gain is:

• A better, declarative specification of what the layout of rust types looks like.
• Better explanations of how layouts were calculated, for diagnostics.
• Unit tests for layouts that use the solver in this codebase directly.
• New features, such as:
  • Extra niches for references to aligned data types.
  • Uninhabited references to uninhabited data types (i.e. a reference to never is itself uninhabited.)

These last two are specifically complicated with current code for a whole host of reasons. Fundamentally, when you try to implement those on top of the current code base, cycles can arise, that are hard to solve. We classify these cycles into three cases:

TODO: examples

• True cycles -> Due to a cycle, a type is actually inhabited / doesn't have a niche.
• False cycles -> Despite a cycle, a type actually is uninhabited / does have a niche.
• Conditional cycles -> Despite a cycle, we can calculate a lower bound on the available niches, and the lower bound provides enough niches to represent the type in a more compact way even if the cycle would otherwise say no niches exist.

To detect the last case, alignment/size/niches need to be calculated as separate properties instead of all together for a single datatype. Separating out the calculation in current code is scary, we want these highly dependent properties to live close together in code so we can reason about them. Building a separate evaluator makes this possible, while giving the evaluator the freedom to decide the calculation order of these properties.

---

Another way of thinking about layout calculation, is that a couple of properties (field and variant shape, and backend representation) largely trivially determine size/alignment/niches/etc. If we had an oracle that told us the first three properties, that'd be great! However, we don't, instead we need to derive it bottom-up from the size/alignment/etc of nested types, until we get to primitives.

This bottom-up calculation presents a lot of choices, points at which we use heuristics to do a "good job" at a final layout. One such heuristic is to sort fields by alignment, bigger alignment first. That way we don't leave any padding in the middle of datastructures. However, you could imagine a better order within enums, that better aligns fields across the various variants. A globally optimal solution has an exponential number of choices to explore. We can't, but we try to make some educated guesses.

With this library, we hope to make it more obvious where we make these choices, and maybe in the future we can even apply better heuristics!