The nitty-gritty of Ethereum and Solidity : EVM Stack.

The Stack is one of the four data locations a solidity smart contract has (the others are : storage, memory and calldata). It is a LIFO queue used by the EVM to retrieve the input arguments of its opcodes and store their results.

Stack definition

The Stack is simply a pile of “words” or “slots” (256 bits long) that can contain a maximum of 1024 items.

The EVM behaves as a “stack machine”, it uses the stack to look for its opcodes input arguments and to store its opcodes outputs.

Value type variables declared in a function’s body are added to the stack, each variable takes a whole 256 bits slot, even if the variable’s data type requires less than 256 bits no packaging is performed (as it happens in the storage).

Stack usage

The Stack behaves like a LIFO queue, values are extracted/added from/to the top.

Some EVM opcodes need input arguments, some might need only one argument (e.g. “NOT”), other might need multiple arguments (e.g. “ADD”), but they all get their values from the top of the stack and they remove them as soon as they consume them.

Some EVM opcodes might generate an output result which is always added to the top of the stack.

For a full list of EVM opcodes and how they interact with the stack you can check the Ethereum official EVM codes website.

Stack too deep error

A very common compiler error that developers face when implementing smart contracts is “Stack too deep error”. It might seem like this error is thrown because at some point we are trying to add more than 1024 items to the stack, however it is not really related to that size limit.

The truth of the matter here is that, despite the stack been 1024 words deep, the EVM can only reach the top 16 words of it.

This is because the “DUP” and “SWAP” opcodes, that “DUPLICATE” a value from the “n-th” position of the stack at the top of it, or “SWAP” a value from the “n-th” position of the stack with the value at the top of it, can reach at most the 16th position of the stack. These two opcodes are the ones Solidity uses to bring back to the top of the stack, values that are required for future operations.

Indeed we have the following DUP opcodes : DUP1, DUP2, …, DUP16 (which duplicate respectively the value at position 1,2,…,16 at the top) and the following SWAP opcodes : SWAP1, SWAP2, …, SWAP16 (which swap respectively the value at position 1,2,…,16 with the value at the top). There is no DUP17 or SWAP17 and beyond, making the values below the 16th position “too deep to be reached”.

Solutions

The only way to solve this error is to make sure that we do not need to access values that are to deep down the stack. This can be done by either simply getting rid of some variables (easiest solution but not always possible), moving them to other storage locations or accessing them in specific ways.

Let’s take the example of a method that is receiving a lot of value type input arguments.

// This method won't compile : Stack too deep
function method(uint256 a,uint256 b,uint256 c,uint256 d,uint256 e,uint256 f,uint256 g,uint256 h,uint256 i) external returns(uint256){
   return a+b+c+d+e+f+g+h+i;
}

When compiling it, this method will throw the stack too deep error message because at some point we will need to reach position 17th of the stack :

• First the 9 input arguments will be copied to the top of the stack. They are copied in order, first argument “a”, then “b” and so on.
• Then the compiler will try to DUPlicate all the required items to process the total sum. It will duplicate them in reverse order, first item “i”, then “h” and so on.
• By the time it will try to duplicate item “a”, the stack will have 17 items (9 + 8) on top of “a”, which makes it too deep to be reached.

The easiest solution that comes to mind is to switch the order in which the compiler will duplicate the variables, let’s start by “a” and finish with “i”.

// This method will compile
function method(uint256 a,uint256 b,uint256 c,uint256 d,uint256 e,uint256 f,uint256 g,uint256 h, uint256 i) external pure returns(uint256){
   return i+h+g+f+e+d+c+b+a;
}

Now at no point the compiler will try to reach position 17th of the stack.

There are however other ways to deal with this issue, for instance we could define a struct with all those variables inside, and adapt the method input arguments accordingly.

// This method will compile
function method(Input calldata input) external returns(uint256){
    return input.a + input.b + input.c + input.d + input.e + input.f + input.g + input.h + input.i;
 }

struct Input{
            uint256 a;
            uint256 b;
            uint256 c;
            uint256 d;
            uint256 e;
            uint256 f;
            uint256 g;
            uint256 h;
            uint256 i;
}

The struct is moving the set of uint256 to the “calldata” location, “decoupling” our process from the stack (not really but you get my point…).

A different solution would be to split the sum in two consecutive sums.

// This method will compile
function method(uint256 a,uint256 b,uint256 c,uint256 d,uint256 e,uint256 f,uint256 g,uint256 h,uint256 i) external pure returns(uint256){
        uint256 result = a+b+c+d+e;
        
        result = result+f+g+h+i;
        
        return result;
 }

By doing that, the compiler will not try to reach all variables at once, it will instead first process part of the operation, then remove the already used values, and finally process the second part of the operation with a stack that is not as deep as at the beginning.

A very similar solution to the one before would be to split the method’s functionality into sub-methods and invoke them.

// This method will compile
function method(uint256 a,uint256 b,uint256 c,uint256 d,uint256 e,uint256 f,uint256 g,uint256 h,uint256 i) external returns(uint256){
        return add_2(a,b) + add_2(c,d) + add_2(e,f) + add_2(g,h) + i;
}

function add_2(uint256 a, uint256 b) internal returns (uint256){
  return a+b;
}

This technique is splitting the method’s process into multiple sub-processes, each running an internal function that requires less items from the stack.

Another possible solution would be to use block scoping. Indeed in Solidity, variables declared inside a certain scope are only accessible within that scope. The scope of a variable is determined by the curly braces {} that define a block of code, such as within a function, a loop, or a conditional statement. Variables declared inside a block are said to have block scope, and they are not accessible outside of that block.

This trick would only make sense if the problem is coming from variables that are declared within the method (instead of input arguments), it could indeed be a good idea to move the variable declarations to different scopes if the use case allows it.

// This method will compile
function method() external view returns(uint256){
        uint256 result;
        {
            uint256 a = 1;
            uint256 b = 2;
            uint256 c = 3;
            uint256 d = 4;
            uint256 e = 5;
            result = a+b+c+d+e;
        }
        
        uint256 f = 6;
        uint256 g = 7;
        uint256 h = 8;
        uint256 i = 9;
        return result+f+g+h+i;
 }    

This method does not implement the same functionality as the previous ones but it helps understanding how block scoping could help us deal with the stack too deep issue.

These are just some tricks that help solve the problem, but it is important to understand the root cause of the issue and address it in the most appropriate way depending on the use case.