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:

Cycles

We want to make certain layout properties of references depend on the properties of the pointee. However, in the current rustc architecture this is not possible due to cycles.

Note how without references a cycle (type containing itself) would always cause an error ("infinite size"), while with references you can trivially have a type containing a reference to itself.

Specifically we want to support:

1. alignment niches
   • i.e. &u32's address needs to be divisible by 4 (size(u32)), thus 1..4 can be used as a niche
2. size niche / end of address space niche
   • objects cannot wrap around the address space
   • the maximum address is thus usize::MAX + 1 - size(T)
   • combined with alignment niches (and nonnull niches) this gives a niche usize::MAX + 1 - size(T) .. align(T) (wrapping around the end of the address space)
   • in practice this gives size(T) + align(T) number of niches for &T
3. slice length niches
   • rust objects have to have a size <= usize::MAX/2
   • ... thus slice length has to be <= (usize::MAX / 2) / size(Elem) (for non zst Elem)
4. references to uninhabited types are uninhabited

We classify cycles into 4 types:

• 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.
• Coinductive cycles

To detect the conditional cycle 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.

Here are examples of all types of cycles:

Coinductive cycle (affects inhabitedness calculations)

struct A {
    f: &'static A,
}

// Q: is A inhabited?
// A: A is inhabited

References are inhabited if their pointee is, which can create cycles. Cycles "don't matter" in this case because they don't disprove inhabitedness.

struct A {
    f: &'static A,
    n: !,
}

// Q: is A inhabited?
// A: A is *not* inhabited

Similar to the above, but we have an uninhabited field as well, making A uninhabited. The cycle does not change this fact.

struct A {
    b: &'static B,
}

struct B {
    a: &'static A,
    n: !,
}

// Q: is A inhabited?
// A: A is *not* inhabited

You need to look through cycles, but the cycle itself doesn't matter.

False cycle

struct A {
    a: &'static A,
}

// Q: what are the niches in A? (given alignment niches exist)

If the interface for getting layout properties of a type returns all layout properties of said type at the same time, you get an unresolvable cycle:

layout(A)    -> layout(&A)   -> layout(A)       |- (cycle)
(for niches)    (for niches)    (for alignment)

However, if you separate the properties into separate functions, there is no cycle:

niches(A) -> niches(&A) -> alignment(A) -> alignment(&A)
                                           (trivial, does not depend on `A`)

Conditial cycles

enum E {
    A(&'static [E]),
    B,
    C,
}

// Q: what is the size of E? (no alignment niches, slice length niches exist)

size(E) --+---> size(&'static [E]) (trivial, does not depend on `E`)
          |
          +---> niches(&'static [E]) --------------> size(E) |- (cycle)
                (size depends on descriminant,       (niches of slice length depend on element size)
                 and whether it fits in niches)

This cycle can be solved by noticing that the condition for whether the descriminant fits in the niche (or needs a separate descriminant increasing the size), can be solved without knowing the exact number of niches of the type:

• Descriminant fits in the niche if niche has at least 2 available values (there are 2 variants except E::A)
• The number of available values in a slice length niche is usize::MAX - ((usize::MAX / 2) / size(Elem))
• size(E) is >= size(&'static [E])
• therefore, the number of niches is at least usize::MAX - ((usize::MAX / 2) / size(&'static [E]))
• which is usize::MAX - ((usize::MAX / 2) / 2*size(usize))
• assuming size(usize) = 8, it is 2**64 - ((2**64 / 2) / 2*8) (without loss of generality)
• which is 2**64 - (2**64 / 2**5)
• which is 2**64 - 2**59
• which is 17870283321406128000
• 17870283321406128000 is bigger than 2

Even though we couldn't traverse the cycle, and don't know the total number of niches (while calculating size of E), using the lower bound on the size, we can know that the descriminant will fit in the niches regardless. As such, we never need to evaluate the cycle at all.

---

enum E {
    A(&'static E),
    B,
    C,
}

// Q: what is the size of E? (no alignment niches, slice length niches exist)

Trivial cycle

This one is boring, but it exists.

struct A {
    a: A,
    b: u8,
}

size(A) -> size(A) |- (cycle)

True cycle

For a true cycle the assumption of a lower bound from a conditional cycle is incorrect.

In other words, a true cycle is when no matter the assumptions you make, a contradiction is reached.

// size(&_) = 8 
// align(&_) = 8

enum E {
    E(&'static E),
    _0 to _15, // fills the "default" niches
    _16,       // ... does not fit in the default niches
}

// Q: what is the size of E?

size(E) --+------> size(&'static E) (trivial, does not depend on `E`)
          |
          | (size depends on descriminant,
          |  and whether it fits in niches)
          |
          |                                 (end of address space niches)
          +------> niches(&'static E) --+-----------------------------------> size(E) |- (cycle)
                    ^                   |
                    |                   | (align niches)
                    |                   |
                    |                   +--> align(E) ----+----> align(&E) (trivial)
                    |                                     |
                    +-------------------------------------+
                      (technically align depends on align
                       of the discriminant, if present.
                       does not matter in this case.
                       we can assume `align >= 8` from
                       `align(&E)` and this does not cause
                       a change of align later)

• Using the conditional cycle resolution from above we can assume size(E) >= size(&_) = 8
• That is not enough to fit all non-E variants (we need 17 niches but only have 16)
• Which causes the discriminant to be present
• Rising the size of E to 16
• Rising the number of niches to 24
• Which is more than 17
• Which would allow us to niche the discriminant
• ... which would drop the size to 8
• ... which would make it not possible to niche the discriminant
• Assuming size = 8 makes the size grow to 16, which makes it shrink to 8. This is not stable.

The solution is to never change our previous decisions (?) (i.e. after we decided to not niche a discriminant, we can't go back on this decision). TODO: this might be hard with multiple cycle entrances. TODO: we might have a big problem if we can't always consistently agree if there is a true cycle depending on where we start from (if going A->B makes us do a series of assumptions which always succeed, while B->A would make assumptions that never succeed).

---

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!