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.

A spill slot is not a variable

The two kinds are asked about separately, because the reason a frame ever lays two things out apart that could share is the debugger, and that reason covers one kind and not the other. A local is a variable somebody wrote down and can ask the value of, so two locals sharing bytes means a variable that is out of scope reads as whatever took its place, which is what -O0 exists not to do and what -fstack-reuse=none turns off at every level. A spill slot holds a value the allocator ran out of registers for, it has no name, nothing can ask for it, and the only thing that ever reads it is the instruction the allocator wrote. Laying those out one each buys a debugger nothing and costs a frame everything, since most frames are mostly spill slots.

So spill slots share at every level and locals share only where the level says they may. What says which is whether this pass is handed a Reach: with one, the locals it followed join in, and without one every local gets bytes of its own and the spill slots are fitted around them.

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 whose things mostly cannot share costs the square of how many there are. What bounds that is a budget of comparisons rather than a count of things: the fit spends BUDGET of them and lays out whatever is left one cell each. A function whose things do share never comes near it, because what each one is compared against is the cells and not the things, and the whole point of sharing is that there are far fewer cells than things. lua’s interpreter, which is 2802 slots fitted into 144 cells and the largest function in the corpus, spends an eighth of the budget and adds a seventh of a second to the file it is in. A function with that many slots that are all live at once would spend the lot, and it gets the layout it would have got anyway.

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

BUDGET

How many cells the fit may look at before it stops pairing things up and gives everything left a cell of its own.

Functions

reach

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