Module slots 

One stack slot allocator: every byte a function asks for itself, placed together.

Design: spec/optimizer/36-lowering-and-isel.md section 36.7.

A frame holds two kinds of thing the function asked for. Locals are what an alloca becomes and the lowering knows about them before anything else runs. Spill slots are what the allocator gives a value it ran out of registers for, and nothing knows how many of those there are until it has finished. Placed apart, the frame is the sum of the two areas. Placed together it is the most either of them needs at any one moment, because two things that are never both wanted can be the same bytes. That is the same answer the allocator gives about registers and it is the same reason.

This runs after allocation and reads the allocator’s own liveness rather than working one out. Running before it would mean guessing which values are spilled, and a guess has to be either conservative or wrong. Asking again afterwards would mean two answers about one function that are free to disagree, and the one the machine runs is the allocator’s.

What a cell is

A Cell is a run of bytes in the frame, as wide and as aligned as the widest and strictest thing in it. Slots says which cell every local and every spill slot went in, and crate::frame is what turns cells into offsets. Nothing else changes: an instruction reading a local still asks the frame where that local is and gets back an offset, and two locals sharing a cell get the same one.

What may share

A spill slot holds one value, so where the slot is wanted is where that value is live, and the allocator has already said where that is.

A local is harder, because what a local is wanted over is not the live range of anything. The bytes are reached through an address, the address is a value like any other, and the bytes go on meaning something for exactly as long as anything can still come by that address. So the question asked here is where the address gets to, and the answer has to be the whole of it or the local does not share at all. reach asks it. An address read as the base of a load or a store is a read of the local at that instruction and goes no further. An address read by another address computation is the same local under a second name and is followed. An address read any other way is one this pass cannot follow to the end, and the local it belongs to is left out.

Left out is therefore the answer for every local whose address is handed to a call, stored into memory, or carried between blocks as an argument. That is what section 36.7 means by an address taken local: not one the program wrote an & in front of, which is a question the types answered and the types are gone by here, but one whose bytes something can reach at a moment liveness does not know about.

Where a local is wanted is not where its address is live

Knowing which instructions reach a local is only half of it. The address that reaches it is a value and the object is not, so an address register that dies right after the store through it says nothing about how long those bytes have to go on holding what was stored. A local written at one point and read at another has to hold its contents through everything in between, however little of what is in between mentions the local at all.

So the area of a local is worked out as its own question over the control flow graph: its bytes matter at every point that has a touch behind it and a touch in front of it. A point with nothing in front is one where the object is finished with, and a point with nothing behind is one where it holds nothing anybody may read, since the contents of a local nothing has written yet are not contents. The two halves of that question are reachability over the graph rather than over the line the function was laid out in. Over the line would be wrong for a loop: a local written at the bottom of a body and read at the top of the next turn is one whose bytes matter across the header too, and the header is laid out before either of the two touches.

The moves count too

Where a spilled value is live is not quite everywhere its slot is touched. The store that fills the slot goes after the instruction that wrote the value, the reload that empties it goes before the instruction that reads it, and the moves an edge turns into go at the end of a block or the start of one, none of which is a point the value is live at. The edge moves are the ones that matter: the sequencer put them in an order that works because it was told every place in them was a different place, and two slots it was told apart are two this pass must not put together behind its back.

So the moves are read as well as the liveness. Every edit that names a slot puts a point either side of where it stands into that slot’s area, which is the gap between two points the edit really sits in, and after that the question is the same question everywhere else in this file.

How big it is allowed to get

Fitting each thing into the first cell it does not clash with compares it against the cells so far, so a function with a very large number of them costs the square of that number. Past CROWDED the frame is laid out the old way, one cell each, because a function with that many slots is rare and a compile that takes a visible pause over one is not worth the bytes.

Structs

Cell

One run of bytes in the frame, holding one local, one spill slot, or several of each.

Reach

What carries the address of each of a function’s locals, or None for one whose address gets away somewhere this pass cannot follow.

Slots

Which cell of the frame every local and every spill slot of a function is in.

Constants

CROWDED

How many locals and spill slots a function may have before its frame is laid out the old way.

Functions

reach

Follows the address of every local of a function as far as it goes.