EIP-2315: Simple Subroutines for the EVM
Two opcodes for static, safe, and efficient subroutines.
Author | Greg Colvin, Greg Colvin, Martin Holst Swende, Brooklyn Zelenka |
---|---|
Discussions-To | https://ethereum-magicians.org/t/eip-2315-simple-subroutines-for-the-evm/3941 |
Status | Draft |
Type | Standards Track |
Category | Core |
Created | 2019-10-17 |
Requires | 3540, 3670, 3779, 4200 |
Table of Contents
Abstract
This proposal introduces two opcodes to support simple subroutines: RJUMPSUB
and RETURNSUB
.
Taken together with other recent propoposals they provides a static, complete, safe, and efficient control-flow facility.
Motivation
The EVM does not provide subroutines as primitives.
Instead, calls can be synthesized by fetching and pushing the return address and subroutine address on the data stack and executing a JUMP
to the subroutine; returns can be synthesized by getting the return address to the top of the stack and jumping back to it. These conventions cost gas, increase program size, and use stack slots unnecessarily. And they create unnecessary complexity that is borne by the humans and programs writing, reading, and analyzing EVM code.
Prior Art
Facilities to directly support subroutines provided by computers since the start, including by all but one of the real and virtual machines we have programmed or implemented. This includes physical machines like the Burroughs 5000, CDC 7600, IBM 360, DEC PDP 11 and VAX, Motorola 68000, Sun SPARC, ARM, and a few generations of Intel x86; as well as virtual machines for Forth, Pascal, Java, Wasm, and the sole exception – the EVM. The details and complexity vary, but in whatever form these facilities provide for capturing the current context of execution, transferring control to a new context, and returning to the original context.
Over the years, native subroutine operations have proven their value for efficient implementation and straightforward coding of subroutines.
Present Proposal
We propose to provide for subroutines with two simple operations:
RJUMPSUB
to call a subroutine andRETURNSUB
to return from it.
Taken together with other required propoposals they provide an static, complete, safe, and efficient control-flow facility.
Static. All possible jumps are known at contract creation time.
Complete. Together with EIP-4200 it provides a minimal set of static control structures for implementing programs – jumps, conditional jumps, and subroutines.
Safe. EIP-3779 establishes rules for using these control structures such that valid programs will not halt with an exception unless they run out of gas or recursively overflow stack.
Efficient. Substantial reductions in the costs, and complexity of calling and optimizing simple subroutines.
Specification
We are following the the original specification of subroutines for Turing’s Automatic Computing Engine of 1946:
We also wish to be able to arrange for the splitting up of operations into subsidiary operations. This should be done in such a way that once we have written down how an operation is done we can use it as a subsidiary to any other operation. … When we wish to start on a subsidiary operation we need only make a note of where we left off the major operation and then apply the first instruction of the subsidiary. When the subsidiary is over we look up the note [on] a list of these notes in one or more standard size delay lines, (1024) with the most recent last. [Delay lines were made of mercury-filled crystals!]
That is, to call a subroutine the machine
- pushes the address of the next instruction on a
return stack
and - transfers control to the subroutine address.
To return from a subroutine it
- pops the
return stack
and - transfers control to the popped address.
The EVM return stack
, like the EVM data stack
, is limited to 1024
items.
Instructions
RJUMPSUB (0x??) jmpdest: uint16
Transfers control to a subroutine. The destination address is relative to the current PC. The address is encoded as a two-byte, twos-complement signed integer, stored MSB-first.
- Decode the
jmpdest
from the immediate data.- Push
PC + 3
to thereturn stack
.- Set
PC
toPC + jmpdest
.
The cost is low.
RETURNSUB (0x??)
Returns control to the caller of a subroutine.
- Pop the
return stack
toPC
.The cost is verylow.
Notes:
- If a resulting
PC
to be executed is beyond the last instruction then the opcode is implicitly aSTOP
, which is not an error. - Values popped off the
return stack
do not need to be validated, since they are alterable only byRJUMPSUB
andRETURNSUB
. - The description above lays out the semantics of these instructions in terms of a
return stack
. But the actual state of thereturn stack
is not observable by EVM code or consensus-critical to the protocol. (For example, a node implementer may codeRJUMPSUB
to unobservably pushPC
on thereturn stack
rather thanPC + 1
, which is allowed so long asRETURNSUB
observably returns control to thePC + 1
location.) - The
return stack
is the functional equivalent of Turing’s “delay line”.
The low cost of RJUMPSUB
versus JUMP
is justified by needing only to add the immediate two byte destination to the PC
and push the return address on the return stack
, all using native arithmetric, versus using the data stack with emulated 256-bit instructions.
The verylow cost of RETURNSUB
is justified by needing only to pop the return stack
into the PC
. Benchmarking will be needed to tell if the costs are well-balanced.
Rationale
Alternatives
There are at least two designs for a subroutine facility.
Turing’s design keeps return addresses on a dedicated stack.
We have chosen Turing’s design, as have Forth, Java, Wasm, and other stack machines. On these machines almost all computation is done on the data stack.
An alternative design is to keep return addresses on the data stack
.
This design became popular on silicon in the 1970’s and remains so. Examples include the PDP 11, VAX, M68000, SPARC, and x86. These are all register machines, not stack machines. The registers are used for computation, and the stack is kept in memory and used by subroutine calls for return addresses as well as call frames for local variables. For all of these machines instruction addresses fit efficiently into machine words on the stack.
We prefer Turing’s design for a few reasons.
- It maintains a clear separation between calculation and flow of control: the data stack is uncluttered with vulnerable return addresses and it’s impossible to overwrite the return stack.
- It improves efficiency by
- using native arithmetic rather than 256-bit EVM instructions for the return address,
- not using a
data stack
slot for the return address, - and not imposing a need to swap items around return addresses and return addresses around items.
- It has a 76-year history of success, especially on stack machines.
Keeping code simple is good. And keeping control flow opaque has clear safety advantages – the state of the VM – the stack and instruction pointers – is not made visible or mutable as data.
Beyond safety, an advantage of keeping the state opaque is that it allows the implementation to optimize the data and return stacks for their different purposes. This is important for the EVM, with its 256-bit data words and native return addresses.
Finally, given that the EVM is a stack machine the decades of successful use of Turing’s design by similar machines weighed heavily in our decision.
Safety
EIP-3779: Safer Control Flow for the EVM specifies safety rules to ensure that valid contracts will not halt with an exception unless they either
- throw
out of gas
or- recursively overflow stack.
The validation algorithm must have linear complexity to avoid being a DoS vulnerability, which in turn requires that the program control flow be static. In combination with EIP-4200: Static relative jumps this EIP provides the static control flow needed for efficient validation.
Efficiency
We illustrate here how subroutine instructions can be used to reduce the complexity and gas costs of both ordinary and optimized subroutine calls compared to using JUMP
.
Simple Subroutine Call
Consider this example of calling a fairly minimal subroutine.
Subroutine call, using JUMP
:
TEST_SQUARE:
jumpdest ; 1 gas
RTN_SQUARE ; 3 gas
0x02 ; 3 gas
SQUARE ; 3 gas
jump ; 8 gas
RTN_SQUARE:
jumpdest ; 1 gas
swap1 ; 3 gas
jump ; 8 gas
SQUARE:
jumpdest ; 1 gas
dup1 ; 3 gas
mul ; 5 gas
swap1 ; 3 gas
jump ; 8 gas
Total: 50 gas.
Subroutine call, using RJUMPSUB
:
TEST_SQUARE:
0x02 ; 3 gas
rjumpsub SQUARE ; 5 gas
returnsub ; 3 gas
SQUARE:
dup1 ; 3 gas
mul ; 5 gas
returnsub ; 3 gas
Total 22 gas.
Using RJUMPSUB
versus JUMP
saves 50 - 22 = 28 gas – a 56% improvement.
It also saves 7 lines of code out of 13, with their associated complexity.
Tail Call Optimization
Of course in cases like this one we can optimize the tail call, so that the return from SQUARE
actually returns from TEST_SQUARE
.
Tail call optimization, using JUMP
:
TEST_SQUARE:
jumpdest ; 1 gas
0x02 ; 3 gas
SQUARE ; 3 gas
jump ; 8 gas
SQUARE:
jumpdest ; 1 gas
dup1 ; 3 gas
mul ; 5 gas
swap1 ; 3 gas
jump ; 8 gas
Total: 33 gas
Tail call optimization, using RJUMP
and RETURNSUB
:
TEST_SQUARE:
0x02 ; 3 gas
rjump SQUARE ; 3 gas
SQUARE:
dup1 ; 3 gas
mul ; 5 gas
returnsub ; 3 gas
Total: 17 gas
Using RJUMPSUB
versus JUMP
saves 33 - 17 = 16 gas – a 48% improvement.
Efficiency Caveats
We can see that these instructions provide a simpler and more gas-efficient subroutine mechanism than using JUMP
.
Clearly, the benefits of these efficiencies are greater for programs that have been factored into smaller subroutines. How small? A subroutine could use 90 more gas than our first example and RJUMPSUB
would still use better than 20% less gas than JUMP
.
Note: A _stack rotation_ operator to move items on the stack and implicitly shift the intervening items could simplify code using JUMP
. It would be a potentionally expensive operation with a dynamic gas cost.
Backwards Compatibility
These changes affect the semantics of existing EVM code: bytes that would have been interpreted as valid jump destinations may now be interpreted as immediate data. Since this proposal depends on the Ethereum Object Format to signal the change this is not a practical issue.
Test Cases
Simple routine
This should jump into a subroutine, back out and stop.
Bytecode: 0x60045e005b5d
(PUSH1 0x04, JUMPSUB, STOP, JUMPDEST, RETURNSUB
)
Pc | Op | Cost | Stack | RStack |
---|---|---|---|---|
0 | JUMPSUB | 5 | [] | [] |
3 | RETURNSUB | 5 | [] | [0] |
4 | STOP | 0 | [] | [] |
Output: 0x
Consumed gas: 10
Two levels of subroutines
This should execute fine, going into one two depths of subroutines
Bytecode: 0x
00000000000000c5e005b60115e5d5b5d
(PUSH9 0x00000000000000000c, JUMPSUB, STOP, JUMPDEST, PUSH1 0x11, JUMPSUB, RETURNSUB, JUMPDEST, RETURNSUB
)
Pc | Op | Cost | Stack | RStack |
---|---|---|---|---|
0 | JUMPSUB | 5 | [] | [] |
3 | JUMPSUB | 5 | [] | [0] |
4 | RETURNSUB | 5 | [] | [0,3] |
5 | RETURNSUB | 5 | [] | [3] |
6 | STOP | 0 | [] | [] |
Consumed gas: 20
Failure 1: invalid jump
This should fail, since the given location is outside of the code-range. The code is the same as previous example,
except that the pushed location is 0x01000000000000000c
instead of 0x0c
.
Bytecode: (PUSH9 0x01000000000000000c, JUMPSUB,
0x6801000000000000000c5e005b60115e5d5b5d, STOP, JUMPDEST, PUSH1 0x11, JUMPSUB, RETURNSUB, JUMPDEST, RETURNSUB
)
Pc | Op | Cost | Stack | RStack |
---|---|---|---|---|
0 | JUMPSUB | 10 | [18446744073709551628] | [] |
Error: at pc=10, op=JUMPSUB: invalid jump destination
Failure 2: shallow return stack
This should fail at first opcode, due to shallow return_stack
Bytecode: 0x5d5858
(RETURNSUB, PC, PC
)
Pc | Op | Cost | Stack | RStack |
---|---|---|---|---|
0 | RETURNSUB | 5 | [] | [] |
Error: at pc=0, op=RETURNSUB: invalid retsub
Subroutine at end of code
In this example. the JUMPSUB is on the last byte of code. When the subroutine returns, it should hit the ‘virtual stop’ after the bytecode, and not exit with error
Bytecode: 0x6005565b5d5b60035e
(PUSH1 0x05, JUMP, JUMPDEST, RETURNSUB, JUMPDEST, PUSH1 0x03, JUMPSUB
)
Pc | Op | Cost | Stack | RStack |
---|---|---|---|---|
0 | PUSH1 | 3 | [] | [] |
2 | JUMP | 8 | [5] | [] |
5 | JUMPDEST | 1 | [] | [] |
6 | JUMPSUB | 5 | [] | [] |
2 | RETURNSUB | 5 | [] | [2] |
7 | STOP | 0 | [] | [] |
Consumed gas: 30
Security Considerations
These changes introduce new flow control instructions. They do not introduce any new security considerations. In concert with EIP-3779: Safer Control Flow for the EVM they will increase security by providing for validated control flow.
References
A.M. Turing, “Proposals for the development in the Mathematics Division of an Automatic Computing Engine (ACE).” Report E882, Executive Committee, NPL February 1946. Available: http://www.alanturing.net/turing_archive/archive/p/p01/P01-001.htm
B.E. Carpenter, R.W. Doran, “The other Turing machine.” The Computer Journal, Volume 20, Issue 3, January 1977. Available: https://doi.org/10.1093/comjnl/20.3.269
Copyright
Copyright and related rights waived via CC0.
Citation
Please cite this document as:
Greg Colvin, Greg Colvin, Martin Holst Swende, Brooklyn Zelenka, "EIP-2315: Simple Subroutines for the EVM [DRAFT]," Ethereum Improvement Proposals, no. 2315, October 2019. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2315.