lialan
commented
5 years ago After EIP615 died, here is another chance to improve this archaic-ish VM architecture. I myself wholeheartedly wish this can be accepted.
I work on compilers and virtual machines. Here is my personal evaluation:
- Compiler support : very, very simple
- VM support: simple and backward compatible
- Impact: HUGE, though not as big as EIP615, but let's take baby steps
- Gas impact: slightly saves gas.
I also wish SUB could take a parameter -- making it a 3 byte instruction. I don't understand people's fear of instructions longer than one byte.
axic
gcolvin
MrChico
shemnon
fanlong
eip: 2315 title: Simple Subroutines for the EVM description: Introduces two opcodes to support simple subroutines status: Draft type: Standards Track category: Core author: Greg Colvin (@gcolvin), Greg Colvin greg@colvin.org, Martin Holst Swende (@holiman), Brooklyn Zelenka (@expede) discussions-to: https://ethereum-magicians.org/t/eip-2315-simple-subroutines-for-the-evm/3941 created: 2019-10-17 requires: 3540, 3670, 3779, 4200
Abstract
This proposal introduces two opcodes to support simple subroutines:
RJUMPSUBandRETURNSUB.Taken together with other recent propoposals it provides an efficient, static, and safe 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
JUMPto 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 and use stack slots unnecessarily. And they create unnecessary complexity that is borne by the humans and programs writing, reading, and analyzing EVM code.Subroutines
As an alternative, we propose to provide for subroutines with two simple operations:
RJUMPSUBto call a subroutine andRETURNSUBto return from it.Taken together with other required propoposals they provide an efficient, static, complete, and safe control-flow facility.
Efficient. Substantial reductions in the complexity and the gas costs of calling and optimizing simple subroutines -- as much as 56% savings in gas in the analysis below. Substantial performance advantages for static jumps are reported elsewhere.
Static. All possible jumps are known at contract creation time.
Complete. Together with EIP-4200 it provides a minimal set of control structures for implementing programs -- jumps, conditional jumps, and subroutines.
Safe. Valid programs will not halt with an exception unless they run out of gas or recursively overflow stack.
Prior Art
Facilities to directly support subroutines are provided by all but one of the real and virtual machines we have programmed. 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 Lisp, Pascal, Java, Wasm, and the sole exception -- the EVM. The details and complexity vary, but in whatever form these facilities provide for
Over the years, for the machines we have programmed, native subroutine operations have proven their value for efficient implementation and simple coding of subroutines.
Original Design
The first specification of subroutines for a real machine goes back to Turing's Automatic Computing Engine of 1946:
Turings's machine held data in delay lines made of mercury-filled crystals. We have better hardware now, but the concept is simple and by now familiar. In less archaic language, Turing's full specification is that:
This design still sees use by virtual machines for Lisp, Forth, Java, Wasm and others.
Specification
We propose to follow Turing's original specification, as applied to the EVM architecture. We support calls and returns with a
return stackof return addresses. The EVMreturn stack, like the EVMdata stack, is limited to1024items. Thisreturn stackis accessed via two new subroutine instructions.Instructions
RJUMPSUB (0x5e) jmpdestThe cost is low.
RETURNSUB (0x5f)Notes:
PCto be executed is beyond the last instruction then the opcode is implicitly aSTOP, which is not an error.return stackdo not need to be validated, since they are alterable only byRJUMPSUBandRETURNSUB.return stack. But the actual state of thereturn stackis not observable by EVM code or consensus-critical to the protocol. (For example, a node implementer may codeRJUMPSUBto unobservably pushPCon thereturn stackrather thanPC + 1, which is allowed so long asRETURNSUBobservably returns control to thePC + 1location.)return stackis the functional equivalent of Turing's "delay line".The low cost of
RJUMPSUBversusJUMPis justified by needing only to add the immediate two byte destination to thePCand push the return address on thereturn stack, all using native arithmetric, versus using the data stack with emulated 256-bit instructions.The verylow cost of
RETURNSUBis justified by needing only to pop thereturn stackinto thePC. Benchmarking will be needed to tell if the costs are well-balanced.Safety
We define safety here as avoiding exceptional halting states, as defined in the Yellow Paper. A validator can always detect three of these states at validation time:
A validator can detect stack overflow only for non-recursive programs, so two states will still require tests at runtime:
EIP-3779: Safer Control Flow for the EVM specifies initialization-time validation to detect invalid contracts.
Rationale
Below we explore the advantages of have a subroutines as primitives, design alternatives, and the reasons for our choice of specification.
Efficiency Analysis
We show 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:Total: 50 gas
Subroutine call, using
RJUMPSUB:Total 22 gas.
Using
RJUMPSUBversusJUMPsaves 50 - 22 = 28 gas -- a 56% improvement.Tail Call Optimization
Of course in cases like this one we can optimize the tail call, so that the return from
SQUAREactually returns fromTEST_SQUARE.Tail call optimization, using
JUMP:Total: 33 gas
Tail call optimization, using
RJUMPandRETURNSUB:Total: 17 gas
Using
RJUMPSUBversusJUMPsaves 33 - 17 = 16 gas -- a 48% improvement.Call Using Data Stack
We can also consider an alternative call mechanism -- call it
DATASUB-- that pushes its return address on thedata_stack:Total 26 gas.
Using
DATASUBversusJUMPsaves 50 - 26 = 24 gas -- a 48% improvement.By comparison, the
RJUMPSUBversion saves 28 gas -- a 56% improvement._Note: The gas cost for
DATASUBis 6 here versus 5 forRJUMPSUBbecause using the wide-integerdata_stackis less efficient than using a stack of native integers._Conlusion
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, but a routine could use 200 more gas than our first example and
RJUMPSUBwould still use better than 10% less gas thanJUMP._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._Design Alternatives
There are at least two designs for a subroutine facility.
Turing's design keeps return addresses on a dedicated stack.
As specified above, the instruction to call a subroutine will
And the instruction to return from a subroutine will
We have chosen Turing's design, as have Forth, Java, Wasm, and others. On a stack machine almost all computation is done on the stack, and on these machines the return information is not conveniently
For these machines, an advantage of keeping a separate return stack is that it leaves to the implementation the representation of the data stack, which can remain opaque to the user. All that matters is that calls and returns work.
An alternative design is to keep return addresses on the
data stack.The instruction to call a subroutine will:
data stack.The instruction to return from a subroutine will:
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 used by subroutine calls for return addresses and call frames.
For all of these machines instruction addresses fit efficiently into machine words on the
data stack.We give an example of this alternative design above.
We prefer Turing's design for a few reasons.
data stackslot for the return address,Keeping code simple is good. And keeping control flow opaque has clear safety advantages -- the state of the VM -- the stack, frame, and instruction pointers -- is not made visible or mutable as data.
Finally, given that the EVM is a stack machine with very wide words, the performance advantages and the decades of successful use of Turing's design by similar machines weighed heavily in our decision.
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)Output: 0x Consumed gas:
10Two 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)Consumed gas:
20Failure 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
0x01000000000000000cinstead of0x0c.Bytecode: (
PUSH9 0x01000000000000000c, JUMPSUB,0x6801000000000000000c5e005b60115e5d5b5d, STOP, JUMPDEST, PUSH1 0x11, JUMPSUB, RETURNSUB, JUMPDEST, RETURNSUB)Failure 2: shallow
return stackThis should fail at first opcode, due to shallow
return_stackBytecode:
0x5d5858(RETURNSUB, PC, PC)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)Consumed gas:
30Security 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.