EIP-663: SWAPN, DUPN and EXCHANGE instructions
Introduce additional instructions for manipulating the stack which allow accessing the stack at higher depths
Abstract
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.
Motivation
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.
Specification
We introduce three new instructions:
DUPN
(0xe6
)SWAPN
(0xe7
)EXCHANGE
(0xe8
)
If the code is legacy bytecode, any of these instructions result in an exceptional halt. (Note: This means no change to behaviour.)
If the code is valid EOF1, the following rules apply:
- The instructions are followed by an 8-bit immediate value, which we call
imm
, and can have a value of 0 to 255.- In the case of
DUPN
andSWAPN
, we introduce the variablen
which equals toimm + 1
. - In the case of
EXCHANGE
, we introduce the variablen
which is equal toimm >> 4 + 1
, and the variablem
which is equal toimm & 0x0F + 1
(i.e., the first and second nibbles ofimm
, converted to one-indexing).
- In the case of
- Code validation is extended to check that no relative jump instruction (
RJUMP
/RJUMPI
/RJUMPV
) targets immediate values ofDUPN
,SWAPN
orEXCHANGE
. - The stack validation algorithm of EIP-5450 is extended:
- Before
DUPN
if the current stack height is less thann
, code is invalid. AfterDUPN
, the stack height is incremented. - Before
SWAPN
if the current stack height is less thann + 1
, code is invalid. AfterSWAPN
, the stack height is unchanged. - Before
EXCHANGE
if the current stack height is less thann + m + 1
, code is invalid. AfterEXCHANGE
, the stack height is unchanged.
- Before
- Execution rules:
DUPN
: then
'th stack item is duplicated at the top of the stack. (Note: We use 1-based indexing here.)SWAPN
: then + 1
'th stack item is swapped with the top of the stack.EXCHANGE
: then + 1
'th stack item is swapped with then + m + 1
'th stack item.
The gas cost for all three instructions is set at 3.
Rationale
EOF-only
Since this instruction depends on an immediate argument encoding, it can only be enabled within EOF. In legacy bytecode that encoding could contradict jumpdest-analysis.
Size of immediate argument
For DUPN
and SWAPN
a 16-bit size was considered to accommodate the full stack space of 1024 items, however:
- that would require an additional restriction/check (
n < 1024
) - the 256 depth is a large improvement over the current 16 and the overhead of an extra byte would make it less useful
Similarly for EXCHANGE
, the proposed scheme allows addressing of 32 items.
Gas cost
The gas cost for these operations is the same as for existing DUP*
and SWAP*
instructions, because they are just implemented as pointer swaps.
EXCHANGE
vs SWAPN
As 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.
Backwards Compatibility
This has no effect on backwards compatibility because the opcodes were not previously allocated and the feature is only enabled in EOF.
Test Cases
Given stack[]
is a 0-based data structure, and n
, m
and imm
are defined as according to the spec:
DUPN imm
to fail validation ifstack_height < n
.SWAPN imm
to fail validation ifstack_height < n + 1
.EXCHANGE imm
to fail validation ifstack_height < n + m + 1
.DUPN imm
to increment maximum stack height of a function. Validation fails if maximum stack height exceeds limit of 1023.DUPN imm
,SWAPN imm
, andEXCHANGE imm
to fail at run-time if gas available is less than 3.DUPN imm
should duplicate thestack[n - 1]
item and push it to the stackSWAPN imm
should swapstack[n]
withstack[stack.top()]
EXCHANGE imm
should swapstack[n]
withstack[n + m]
.
Security Considerations
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
Copyright and related rights waived via CC0.