Currently, SWAP* and DUP* instructions are limited to a stack depth of 16. Introduce three new instructions, SWAPN, DUPN and EXCHANGE which lift this limitation and allow accessing the stack at higher depths.
While the stack is 1024 items deep, easy access is only possible for the top 16 items. Supporting more local variables is possible via manually keeping them in memory or through a "stack to memory elevation" in a compiler. This can result in complex and inefficient code.
Furthermore, implementing higher level constructs, such as functions, on top of EVM will result in a list of input and output parameters as well as an instruction offset to return to.
The number of these arguments (or stack items) can easily exceed 16 and thus will require extra care from a compiler to lay them out in a way that all of them are still accessible.
Lastly, swapping items besides the 1st and Nth items in the stack is very important for compilers implementing stack scheduling algorithms (the analog of register allocation for stack machines), which try to minimize stack traffic given a set of variables and usage analysis.
Introducing SWAPN, DUPN, and EXCHANGE will provide an option to compilers to simplify accessing deep stack items.
We introduce three new instructions:
DUPN (0xe6)SWAPN (0xe7)EXCHANGE (0xe8)Each instruction carries one or two immediate operands. Informally, using 1-based indexing, the semantics are:
DUPN n: The n'th stack item is duplicated at the top of the stack.SWAPN n: The n + 1'th stack item is swapped with the top of the stack.EXCHANGE n m: The n + 1'th stack item is swapped with the m + 1'th stack item.Formally, when code[pc] is one of these opcodes, the VM executes as follows:
DUPN:x = code[pc + 1].90 < x < 128 revert, consuming all gas.n = decode_single(x).stack[top - n + 1] on the stack.pc = pc + 2.SWAPN:x = code[pc + 1].90 < x < 128 revert, consuming all gas.n = decode_single(x).stack[top - n] and stack[top].pc = pc + 2.EXCHANGE:x = code[pc + 1].79 < x < 128 revert, consuming all gas.n, m = decode_pair(x).stack[top - n] and stack[top - m].pc = pc + 2.
topdenotes the index of the value at the top of the stack.
JUMPDEST analysis is unchanged. In particular, if code[i] is at an instruction boundary and is one of these opcodes, and code[i + 1] is 0x5b (JUMPDEST), then code[i + 1] is a valid jump target. Note that in this case the execution of code[i] would halt at step 2 above (because x = code[i + 1] = 0x5b = 91). Disassemblers must decode such code[i] as INVALID (or INVALID_DUPN, etc.) and code[i + 1] as JUMPDEST.
The auxiliary functions decode_single and decode_pair are defined by the following Python code:
def decode_single(x: int) -> int:
assert 0 <= x <= 90 or 128 <= x <= 255
if x <= 90:
return x + 17
else:
return x - 20
def decode_pair(x: int) -> tuple[int, int]:
assert 0 <= x <= 79 or 128 <= x <= 255
k = x if x <= 79 else x - 48
q, r = divmod(k, 16)
if q < r:
return q + 2, r + 2
else:
return r + 2, 30 - q
Assemblers and compilers must emit a 1-byte immediate after each of these opcodes that decodes to the required n, m operands. For reference, this can be done by encode_single and encode_pair:
def encode_single(n: int) -> int:
assert 17 <= n <= 235
if n <= 107:
return n - 17
else:
return n + 20
def encode_pair(n: int, m: int) -> int:
assert 2 <= n <= 14 and n < m <= 30 and n + m <= 32
if m <= 17:
q, r = n - 2, m - 2
else:
q, r = 30 - m, n - 2
k = 16 * q + r
return k if k <= 79 else k + 48
Allowing dynamic selection of the arguments to swap or dup could be used to prevent static analysis of the contents of the stack. Since static analysis is an important tool for security auditors we want to do what we can to make their jobs easier. Hence, the operands require an immediate operand that is not dynamic in nature.
Allowing the encoding of the immediate operand to take the values 0x5b or 0x60 to 0x7f would create a backwards incompatibility. These values correspond to the JUMPDEST and PUSH1 to PUSH32 opcodes. Consider the bytecode sequence e6 5b that currently decodes to INVALID JUMPDEST. If the DUPN opcode accepted any subsequent byte as an immediate, once the instruction is introduced to the EVM the same bytecode sequence would then decode to DUPN 0x5b, eliminating a previously present JUMPDEST and possibly invalidating jumps necessary for the functioning of the contract. A similar thing can happen with push opcodes, for example, e6 60 5b would transform from INVALID PUSH1 0x5b to DUPN 0x60 JUMPDEST upon introduction of such an instruction, creating a new valid jump target. Furthermore, this may have a cascading effect on arbitrarily many subsequent instructions.
Since the EVM doesn't offer a dedicated section for data, arbitrary data may be embedded in code and serve as immutable data storage accessed via CODECOPY. Therefore, we must assume that arbitrary byte sequences may be found in contracts that have been deployed or are "counterfactual" deployments-in-waiting.
The current version of the EIP is designed to uphold the following backwards compatibility guarantee: every possible execution trace on a given bytecode that does not attempt to execute an undefined opcode must continue to produce the same effect after the introduction of an instruction. No new JUMPDESTs must be created in a given bytecode by the introduction of an instruction and none may be removed.
While it would be safe to allow the values 0x5c to 0x5f, these were also omitted to simplify decoding, and wouldn't significantly increase the reachable stack items.
EXCHANGE immediateA previous formulation of EXCHANGE allowed swapping stack elements only if they were within some distance. As a result, it would be possible to swap the elements at indices 30 and 29, but not possible to move an element from index 30 to 2 with a single instruction. The current formulation prioritizes the latter, on the assumption that it is more valuable to move elements closer to the top of the stack than it is to rearrange elements deeper in the stack.
In addition, the exact formulation was chosen to make decode_pair a simple function using only basic arithmetic, bitwise operations (division by 16), and few branches. A small trade-off in the number of addressable pairs was made to reduce the number of necessary branches; this implies some of the immediate range is not allocated, and it could be used to add a dozen more addressable pairs at the cost of more decoding complexity, potentially in a future network upgrade.
For DUPN and SWAPN a 16-bit size was considered to accommodate the full stack space of 1024 items, however:
n < 1024)Similarly for EXCHANGE, the proposed scheme allows addressing of 30 items.
The gas cost for these operations is the same as for existing DUP* and SWAP* instructions, because they are just implemented as pointer swaps and immediate decoding is negligible.
EXCHANGE vs SWAPNAs mentioned before, EXCHANGE is important to compilers implementing stack scheduling algorithms. Specifically, in the case that a stack item is scheduled to be consumed deeper in the stack (for instance, the 3rd item in the stack needs to be moved into 2nd position in order to be consumed by the next operation), that currently takes three instructions, SWAP2 SWAP3 SWAP2. However, in the EVM implementation, the implementation is just a pointer swap, so it could be implemented in a single instruction at no extra runtime cost to the client.
This has no effect on contracts that would never attempt to execute the opcodes allocated by this EIP. The jump targets of existing contracts are preserved.
e600 is [DUPN 17]e780 is [SWAPN 108]e6005b is [DUPN 17, JUMPDEST]e75b is [INVALID_SWAPN, JUMPDEST]e6605b is [INVALID_DUPN, PUSH1 0x5b]e7610000 is [INVALID_SWAPN, PUSH2 0x0000]e65f is [INVALID_DUPN, PUSH0]e812 is [EXCHANGE 3 4]e8d0 is [EXCHANGE 2 20]e850 is [INVALID_EXCHANGE, POP]60016000808080808080808080808080808080e600 results in 18 stack items, the top of the stack valued 1, the bottom of the stack valued 1, the rest valued 0600160008080808080808080808080808080806002e700 results in 18 stack items, the top of the stack valued 1, the bottom of the stack valued 2, the rest valued 0600060016002e801 results in 3 stack items, from top to bottom: [2, 0, 1]e75b reverts 600456e65b executes successfully (PUSH 04 JUMP INVALID_DUPN JUMPDEST)The authors are not aware of any additional risks introduced here. The EVM stack is fixed at 1024 items and most implementations keep that in memory at all times. This change will increase the number of stack items accessible via single instruction.
Copyright and related rights waived via CC0.