Spilling in the EVM

In this post I cover what spilling is, how it relates to “stack too deep” errors, why it can be necessary for EVM programs, whether current compilers do it, and how they could be improved.

Most common computer architectures include a set of registers. This is the most efficient place a program can store values, but registers are limited in number. The process of deciding how to efficiently use them is an important responsibility of compilers called register allocation. This is a computationally difficult problem, complicated by the fact that the set of live values at some point in the program can be much larger than the set of registers, so if this is the only value store that’s available a solution will be impossible.

In a previous post I discussed how Solidity’s legacy approach to codegen fails to compile some otherwise valid programs with a “stack too deep” error. While the EVM is stack rather than register-based, only a small section of the stack is reachable, with a similar effect as having a small set of registers. “Stack too deep” is analogous to what a register allocator would output if it tried to use registers exclusively.

Instead of failing to compile, the register allocator can also decide to move values from registers to memory as a backup store. This is called spilling, and some form of it is necessary when compiling for the EVM too, in order to prevent “stack too deep” errors. Indeed, both Vyper and the IR pipeline in Solidity do something like spilling, but it is different from the traditional kind in an important way.

In both compilers the issue is addressed by statically allocating memory for variables. In the case of Solidity, variables are put on the stack by default and those that are out of reach at some point of the program are moved to memory, whereas Vyper puts all variables in memory by default and later moves some of them to the stack as an optimization. “Statically allocated” roughly means that a variable declaration in the source code is assigned a fixed location in memory. Notably this implies that functions with such variables cannot be recursive or reentrant, as correctly enforced by both compilers, because reentering the function would overwrite their values mid-execution. This is arguably an acceptable compromise but is strictly a reduction in language expressiveness. The remainder of this post explains how we can overcome this limitation and implement true spilling in the EVM with good characteristics.

Traditional computer programs construct the call stack in memory, and spill values into a dedicated portion of each call frame. Thus, each invocation of a function spills into a separate area of memory, avoiding issues with reentrant and recursive functions. Remember that the traditional call stack is in memory and has abundant reachable space, unlike the EVM stack. Remember also from the previous post that trying to apply this approach in the EVM setting (i.e., building a call stack in EVM memory) has poor characteristics: quadratic memory expansion cost makes call frames more expensive as the stack grows, and it seems impossible (or at least significantly more complex and expensive) to use memory as both a heap and a stack without leaks.

If dynamically allocating memory for spills is problematic, we have to settle for a statically allocated fixed amount, just like Vyper and Solidity currently do. However, to recover the full expressive power of reentrant and recursive functions, we should treat this memory like a set of callee-save virtual registers. This means that functions are free to use it but must restore it to its previous state upon return. The key insight to implement this is that the unreachable part of the stack is not entirely useless, it’s a perfectly fine place to hold values while they’re not required, and this is exactly what we need to do for a callee-save register. Before a relevant value becomes unreachable in the stack, we can swap it into one of the (always reachable!) virtual registers in memory, saving the previous value it held on the stack where we don’t mind it becoming temporarily unreachable. As soon as this value is again within reach, we restore it back into the virtual register, completing the callee-save pattern of use.

The compiler can implement this in three passes. First, it generates code assuming the stack is infinitely reachable. Second, it identifies exactly where to insert spills. Third, it inserts them and converts out of bounds stack operations into memory operations on the appropriate virtual registers. A final step of the compiler finds the maximum number of virtual registers a function needs and makes enough room for them in memory by setting the initial free memory pointer appropriately.

A proof of concept of the above can be found at github.com/frangio/evm-spilling.

Note that this procedure only removes out of bounds stack accesses, it does not try to minimize them. A compiler that intends to optimize for gas efficiency should first decide on an ordering of operations that maximizes in-bounds stack use, and insert spills only as a way to guarantee that programs compile. In most cases spills may not be necessary at all, but in the edge cases where they are the compiler should not just give up!

While I think this is a really nice technique, we should consider a few things before committing to it. The EVM stack (on Ethereum at least) is limited to a maximum size of 1024, so we may want to be wary of writing and generating code that makes heavy use of it and brings us closer to this limit. (Ideally, the compiler should ensure that programs stay below the limit, though this is not possible in general if we allow recursion.) Memory expansion costs, while quadratic, are not concretely that high, so it may be fine to create call frames in memory. Finally, SWAPN and DUPN instructions as introduced in EIP-663 will eventually make the need for spilling a lot less pressing, by increasing the reachable portion of the stack up to size 256.