# Pre-proposal. EVM Performance: From Stack Machine to Register Machine to Machine Code

Better EVM performance has been desired since before I first joined the Ethereum community in 2016. Martin Becze, Vitalik Buterin, Paweł Bylica, Martin Swende, the eWasm/Ipsilon team and others have been actively working on EVM perforance since before I arrived. The EVM is at the very core of the Ethereum execution layer and its performance affects the entirety of our technology stack and our community.

With the advent of the Etherum Object Format suite -- especially its validated stack use and static control flow -- it is now possible to resume an important piece of my work towards creating a more performant EVM. I envision two phases of development, and am seeking funding for the first phase.
* Phase 1. I want to craft a compiler from EVM code to an executabe intermediate representation. Rather than code for a virtual stack machine, this will be code for a high-performance virtual register machine.
* Phase 2. I want to craft a compiler from this executable IR to actual machine code, with an initial target of 64-bit AMD/Intel CPUs.

## Why we need better EVM performance.

For many smart contracts we don't need better performance -- the vast majority of gas is spent on `SLOAD`. But where it matters -- especially the execution of cryptographic codes -- it really matters.

Programmers will go to extraordinary lengths to optimize EVM performance, crafting assembly by hand and inventing low-level languages like [Huff](https://docs.huff.sh/). When that will not suffice they may propose precompiles -- [EIP-152](https://eips.ethereum.org/EIPS/eip-152), [EIP-196](https://eips.ethereum.org/EIPS/eip-196), [EIP-197](https://eips.ethereum.org/EIPS/eip-197), [EIP-665](https://eips.ethereum.org/EIPS/eip-665), [EIP-1108](https://eips.ethereum.org/EIPS/eip-1108), [EIP-1109](https://eips.ethereum.org/EIPS/eip-1109), [EIP-1352](https://eips.ethereum.org/EIPS/eip-1352), [EIP-1829](https://eips.ethereum.org/EIPS/eip-1829), [EIP-2046](https://eips.ethereum.org/EIPS/eip-2046), [EIP-2537](https://eips.ethereum.org/EIPS/eip-2537), [EIP-2666](https://eips.ethereum.org/EIPS/eip-2666), [EIP-3068](https://eips.ethereum.org/EIPS/eip-3068), [EIP-5988](https://eips.ethereum.org/EIPS/eip-5988) and others -- with no apparent end in sight.

The very need for precompiles highlights the shortcomings of the EVM. They are implemented in non-trivial native code, and exact a price on every aspect of development and deployment for every client. It really woud be best if people could solve their problems directly using the EVM. In too many cases, they can't.

*Note: a rapidly emerging community that needs better EVM performance is that of artists creating [NFTs that generate art, even animations, directly with contract code](https://thevideoanimationcompany.com/nft-animated-videos-what-they-are-and-how-to-create-one/).*

## How I plan to achieve better performance.

### Previous VM work

Years ago I was engaged in R&D on improved performance for the Oracle Java VM. I quadrupled its speed in three stages.

* First, I replaced the traditional "big switch" interpreter with a "threaded" interpreter and made other improvements to reduce the large overhead of running interpreted code.
* Next, I translated code for the JVM stack machine to code for a virtual register machine.
* That work was trade secret, but has since been replicated in the open literature: c.f. [The Case for Virtual Register Machines](https://mural.maynoothuniversity.ie/10191/1/KC-Case-2003.pdf) and [Virtual Machine Showdown: Stack Versus Registers](https://www.usenix.org/legacy/events/vee05/full_papers/p153-yunhe.pdf0).
* Finally, I used the virtual register machine code as an Intermediate Representation for generating code for real CPUs.

I propose to apply the lessons learned and the latest research to the EVM. Our [evmone](https://github.com/ethereum/evmone) interpreter has already moved to threaded code, so for Phase 1 work I am proposing to augment the EVM's virtual stack machine with a virtual register machine.

### Current EVM status

For the current EVM, translation to register code is not possible in linear time, meaning that the compiler would be vulnerable to denial of service. This is not just a theoretical danger -- the eWasm team demonstrated that avaiable Wasm compilers are indeed subject to attack, with some programs taking orders of magnitude more time to compile than others of the same size. So in 2016 I set aside attempting to translate EVM code to register code, and concentrated on removing the obstacles: dynamic jumps.

Wasm, like JVM, does not have dynamic jumps. So they are both amenable to linear-time compilation, but that has not been a market requirement. For Ethereum, it is. We now have multiple proposals -- my own [EIP-615](https://eips.ethereum.org/EIPS/eip-615) and [EIP-2315](https://eips.ethereum.org/EIPS/eip-2315), and the Ipsilon group's [Etherum Object Format](https://eips.ethereum.org/EIPS/eip-3540) suite ([EIP-4200](https://eips.ethereum.org/EIPS/eip-4200), [EIP-4750](https://eips.ethereum.org/EIPS/eip-4750), and [EIP-5450](https://eips.ethereum.org/EIPS/eip-5450)) -- which support linear-time compilation of EVM code.

At this time the EOF proposals are slotted for the Cancun upgrade and implemented in evmone and most clients, so it is a good time for me to resume my work on an EVM compiler.

### Phase 1 work

First I will need to fork the [evmone](https://github.com/ethereum/evmone) codebase. I will not need to modify much of the code outside of the interpreter -- it will continue to provide the [EVMC](https://evmc.ethereum.org/) interface supported by clients like Geth, Erigon, and Silkworm.

What I will do is implement a virtual register machine and extend the validation code to

This initial translation begins by simply "unrolling" the stack onto memory.
* On stack machines all addresses are implicit -- the machine keeps a pointer to the top of a stack and most operations consume the top two stack items and leave one resulting item on top, moving the stack pointer each time.
* Register machines use explicit addresses. This takes more space, but eliminates the need to move data (for, e.g. `SWAP` and `DUP`) and the overhead of using and maintaining the stack pointer.

As we unroll the stack we replace stack operations operations on implicit addresses with 2- and 3-address code that directly references the unrolled stack in memory. VMs with this architecture are much closer to real CPUs, making eventual generation of machine code much easier.

Research questions include the nature and degree of further optimization possible at this phase. Prior research indicates that even without compilation to machine code this should be a highly performant EVM.

### Phase 2 work

Getting past the intrinsic limits of interpreted execution requires native code. If we don't want to write it by hand in we need a compiler to do it, and the Phase 1 register machine code should be a good starting point. In my experince even a simple transliteration from such code to native instructions gives good improvements. This transliteration can be improved from there into full compilation by incorporating more of the usual optimizations. Which is reseearch I won't try to anticipate here and now.

## Deliverables

By the completion of Phase 1 we will have
* a production-quality fork of evmone that
* implements a high-performance virtual register machine,
* and a compiler of EVM bytecode to code for that machine.

This VM will be compatible with the Geth, Erigon, Silkworm, and any other client supporting the [EVMC](https://evmc.ethereum.org/) interface.

*All code will be released -- like evmone -- with the open and permissive Apache license.

## The ask

At this time I am seeking funding funding for Phase 1:

* $30,000 for six months of half-time work.

Six months is a reasonable amount of time, given that all R&D for this work on a JVM took me a year and I don't need to redo the research. I don't want to devote my full time because I have other Ethereum volunteer work and because that leaves room to stay on schedule by working more hours. I believe that this project will be a clear contribution to the Ethereum technology base, and an enjoyable opportunity to work with other EVM engineers.

Phase 2 can be funded with one or more follow-on small grants, a project grant, or some other source of funding, depending on the emerging scope of work and team of people involved.