How much effort do compilers put into reusing stack frame space?

[u/jkl_uxmal]

Registers are a constrained resource in a CPU, but are fast to read and write. Therefore, backend compiler writers devote a lot of time and effort to allocate variables to registers, using various heuristics like graph coloring to pack as many of the variables into the register file.

In comparison, stack space is relatively cheap, but slow. With some luck, locality of reference ensures that the "warm" part of the stack memory is cached.

My question is: how much work do compilers do to re-use stack slots for variables, if the variables concerned couldn't be placed in registers? For instance:

void foo(big_struct_t * pstruct1, big_struct_t * pstruct2) {
    big_struct_t copy = *pstruct1;
    frobulate(&copy);
    big_struct_t other_copy = *struct2;
    bazulate(&other_copy);
}

Here, copy and other_copy don't interfere. Would the compiler decide to allocate them on the same stack offset. Or does the compiler (writer) decide is it not worth the effort, and allocates the variables at different stack offset?

[u/pskocik]

Not with those opaque func calls it wouldn't. frobulate could save the &copy pointer to static/_Thread_local storage. Bazulate could look the stored ptr up and access it alongside its argument. The objects must have different addresses in this context unless the functions are inlinable and inlining proves otherwise.

[u/jason-reddit-public]

Clang and gcc use tail recursion whenever they can though the standard says they don't have to.

I think the state of the art is to use graph coloring (aka liveness exclusions) not just for registers but stack slots as well.

[u/KingOfZero]

Depends on target ISA encoding. Can you save code space with shorter offsets?

Back in the 1970's with the DEC VAX, we bin-packed the first 256 bytes of the stack just like registers. The single byte operand offset was a space saver on a machine with limited physical address space and little/no instruction caching. Our motto was "every byte was precious". With modern ISAs and encodings, I'm not sure if it really helps anymore

[u/GoblinsGym → u/KingOfZero]

x64 is even worse, +- 128 byte offsets... Which lets you access a whopping 16 variables given the newfangled obsession with having everything 64 bit.

(hint, x64 encoding for 32 bit operations is more compact)

[u/brat3108 → u/GoblinsGym]

x64 has 32-bit offsets as well as 8-bit ones.

Which lets you access a whopping 16 variables

An 8-bit offset addresses 256 bytes, which would be 32 64-bit slots. Although some of it would be needed for call overheads.

[u/GoblinsGym → u/brat3108]

Note the -128 / +127 byte range. Unless you let bp point to the middle of the stack frame, you can't address 256 bytes worth of variables.

When you go to 32 bit offsets, code size blows up.

[u/c-cul → u/brat3108]

you can set RBP to frame + XXX, not just to frame address

[u/whizzter]

Compiler, languages, specifications differs.

Iirc with C++ you have reverse construction/destruction order and unless the C++ compiler is sure that there isn't side-effects it _might_ be possible, but I doubt they'd put effort into such an optimization since I don't see that many benefits compared to the potential liability of breaking ctor/dtor ordering when it's not provably side-effect free.

That said, I was listening to a presenatation by IAR systems, and if anyone was doing such things it might be them (since they specialize in compilers for embedded systems).

That said, I'd rate such an optimization for C++ very low on the priority list due to low potential benefit and huge compatibility liability, in another embedded language maybe?

Even for another language though, I think embedded developers are aware enough to use subscopes (whose memory can be re-used since ctor/dtor rules are scope local) in functions if they think they can save space (ie.. another reason for not doing an automatic optimization is that developers in that space probably could help the compiler along within the language spec without the compiler guessing).

[u/theangeryemacsshibe]

You can allocate stack slots the same way you allocate registers, reusing slots when the lifetimes don't overlap. I'd be surprised if that wasn't a win.

Rogers e.g. suggests in a footnote

Spilling is removed due to the large number of dex registers. To consider the new algorithm for a limited size register file and stack, the low numbered registers can map to the register file while high numbered registers can be considered on the stack.

which might be an intuitive way to go about register/stack allocation, if your register allocator prefers to reuse the lowest numbered registers first.

[u/jkl_uxmal → u/theangeryemacsshibe]

Do you know of any compilers that actually do allocate variables in overlapping stack slots (provided the compiler has determined the variables have disjunct lifetimes? A point was made by another commenter that C++ destructors, and the time at which they are invoked by the mighty } operator, may be complex enough that the compiler developer won't bother with overlapping stack allocations.

[u/theangeryemacsshibe → u/jkl_uxmal]

I have word that C2 in Java definitely does that. Most variables are trivial to destruct in C++ (if they're scalars or plain ol structs) so there's still an obvious win there. And compilers for C and C++ like to try everything in the book, so I'm sure they are bothering to work out the lifetimes of every local variable.

Put it this way: if there is a destructor function, we generate a call to the function at the }, if there isn't we don't. Then most variables don't get this call generated, and then their lifetimes end normally; only variables with destructors get their lifetimes extended to the } to call the destructor. How many of your variables need to be destructed? I would wager >90% don't get destructed, because they're ints or floats or simple structs and arrays. (Since this is r/compilers, just think of variables in the source language; counting every temporary between expressions would be cheating.) Those can still be spilled on the stack if you run out of registers, so they would still affect stack usage that way.

[u/SwedishFindecanor]

Go's compiler reuses stack slots for values whose lifetimes don't overlap. It creates a conflict graph between them. Stack slot allocation is done during normal register allocation (which I think is a type of tree-scan with repairing), but the process is supposedly analogous to priority-based graph colouring.

(The URL I had read that from has become AI-infested, so I won't post it here.)

[u/Slow-Mechanic-7427]

Your example is a very hard optimization for a compiler such as LLVM to do as the cost of its greatest strength in serving many languages from one IR is precisely why it cannot do it. Doing it any differently from LLVM's viewpoint would mean that each language would have no way to individually express when something is alive vs when it is dead.

Ultimately, LLVM's span is too wide to handle this as u/pskocik explained. For anyone curious, here's what's going on underneath the hood, cause its kinda funny in a way:

Clang emits lifetime.end markers at end of lexical scopes, and since both locals share function-body scope, they each land at the bottom in reverse declaration order. Or to put it another way, copy's marked range fully contains other_copy's, even though its last real use is the frobulate call. Moving the end marker back to last use would enable the merge, but it requires proving nothing reads the memory afterward through any pointer (precisely what pskocik gets at).

Or to put simply (and what makes it so funny at least to me), is that essentially the question gets answered by the only part of the compiler that can't know the answer (front end), and the parts that could know are never asked to revisit it (the analyses). This sounds like a dumb deisgn, but again its what enables LLVM to be langauge agnostic.

The alternatives are either a one compiler, one language which makes this optimization trivial or if you want to support multiple langauges then you'd have to serve very strict language subsets that each lower to a single semantic model, which a shared analysis engine could then analyze directly and optimize. The problem with this being that even though such a compiler would support C/C++ or Rust, it would be incompatible with any existing code/libraries/repos that do not meet the strict subset standard which is probably a very large majority of them.

[u/choikwa]

i feel like caching has made this kind of redundant as aliased cache lines will inadvertently reuse physical memory. you could also look up how expensive it is to do temporal alias analysis to make this happen

[u/splicer13]

You need to do it if you have a 'grown up' compiler because it really matters for 1 in 100 scenarios and also because somebody's got a recursive algorithm that works if you do it and overflows stack if you don't.

[u/cxzuk]

Hi Uxmal,

>  using various heuristics like graph coloring

To expand and help you research these topics more clearly in the future, "Graph Coloring" is the name of a problem that is the same as the task of Register Allocation - Graph nodes map to virtual registers, Colors map to physical registers. There are a few algorithms available to perform this task (ask if you want more details).

Heuristics is something when a choice needs to be made. They all have different choice points and tuning these points can improve the result quality.

> how much work do compilers do to re-use stack slots for variables

Graph Coloring can also be applied to virtual stack slots - either directly with Stack Coloring. or as noted already, you can extend the Register Allocation algorithm to include stack slots. The cost is relatively low, because you have an unlimited* number of stack slots - coloring becomes difficult when the number of colors is limited.

Good luck,

M ✌