EIP3337 - Frame pointer support for memory load and store operations

# Simple Summary

Introduces four new opcodes for loading data from and storing data to memory offset by a frame pointer.

# Abstract

This EIP introduces four new opcodes, MLOADFP, MSTOREFP, GETFP and SETFP that allow for more efficient memory access offset by a user-controlled quantity called the "frame pointer". This permits compilers to more efficiently offload ephemeral data such as local variables to memory instead of the EVM's evaluation stack, which has a number of benefits, including the effective elimination of restrictions on the number of local variables in a function.

# Motivation

In most commonly used VMs, ephemeral data such as local variables, function arguments, and return addresses is stored in a region of memory called the stack. In contrast to the EVM's evaluation stack, this area of memory is randomly accessible, and thus can store an arbitrary amount of data, which can be referenced from anywhere they remain in scope. Although this model is possible in the current EVM design, it is made difficult by the linear model of memory (addressed in EIP-3336) and by the lack of opcodes for relative memory access commonly found in other architectures. This EIP proposes new opcodes that permit this form of memory use, without imposing undue burden on EVM implementers or on runtime efficiency.

In the current EVM model, a compiler wishing to use this pattern would have to store the frame pointer - which points to the start or end of the current memory stack frame - in memory, and load it each time they wish to reference it. For example, loading a value from memory offset by the frame pointer would require the following sequence of operations:

Opcode	Gas used
`PUSHn x`	3
`PUSH1 0`	3
`MLOAD`	3
`ADD`	3
`MLOAD`	3

This consumes a total of 15 gas, and takes up at least 7 bytes of bytecode each time it is referenced. In contrast, after this EIP, the equivalent sequence of operations is:

Opcode	Gas used
`PUSH1 x`	3
`MLOADFP`	3

This consumes only 6 gas, and takes at least 3 bytes of bytecode. The effort required from the EVM implementation is equivalent, costing only one extra addition operation over a regular MLOAD. The alternative of storing values on the stack, which requires 3 gas and 1 byte of bytecode for a DUPn operation, but it is now at most twice as efficient rather than 5 times as efficient, making storing values in memory a viable alternative.

Likewise, before this EIP a frame-pointer relative store requires the following sequence of operations:

Opcode	Gas used
`PUSHn x`	3
`PUSH1 0`	3
`MLOAD`	3
`ADD`	3
`MSTORE`	3

This consumes 15 gas and at least 7 bytes of bytecode. After this EIP, the equivalent sequence of operations is:

Opcode	Gas used
`PUSHn x`	3
`MSTOREFP`	3

Consuming only 6 gas and at least 3 bytes of bytecode, while once again only requiring EVM implementations to do one extra addition operation. The alternative of storing values on the stack requires 6 gas and 2 bytes of bytecode for the sequence SWAPn POP, making it no more efficient than memory storage.

# Specification

# Parameters

Constant	Value
`FORK_BLOCK`	TBD

For blocks where block.number >= FORK_BLOCK, the following changes apply.

# Frame pointer

A new EVM internal state variable called the "frame pointer" is introduced. This is a signed integer that starts at 0.

# `SETFP` opcode

A new opcode, SETFP is introduced with value 0x5c. This opcode costs G_low (3 gas) and takes one argument from the stack. The argument is stored as the new value of the frame pointer.

# `GETFP` opcode

A new opcode, GETFP is introduced with value 0x5d. This opcode costs G_low (3 gas) and takes no arguments. It takes the current value of the frame pointer and pushes it to the stack.

# `MLOADFP` opcode

A new opcode MLOADFP is introduced with value 0x5e. This opcode acts in all ways identical to MLOAD, except that the value of the frame pointer is added to the address before loading data from memory. An attempt to load data from a negative address should be treated identically to an invalid opcode, consuming all gas and reverting the current execution context.

# `MSTOREFP` opcode

A new opcode MSTOREFP is introduced with value 0x5f. This opcode acts in all ways identical to MSTORE, except that the value of the frame pointer is added to the address before storing data to memory. An attempt to store data to a negative address should be treated identically to an invalid opcode, consuming all gas and reverting the current execution context.

# Rationale

# Cost of new opcodes

The cost of the new opcodes MLOADFP and MSTOREFP reflects the cost of MLOAD and MSTORE. They are generally equivalent in cost with the exception of an extra addition operation, which imposes negligible cost.

The cost of the new opcodes SETFP and GETFP is based on other common low-cost opcodes such as PUSH and POP.

# Absence of `MSTORE8FP`

MSTORE8FP opcode was not included because it is expected that it would be used infrequently, and there is a desire to minimise the size of the instruction set and to conserve opcodes for future use.

# Backwards Compatibility

This EIP exclusively introduces new opcodes, and as a result should not impact any existing programs unless they operate under the assumption that these opcodes are undefined, which we believe will not be the case.

# Security Considerations

DoS risks are mitigated by correct pricing of opcodes to reflect current execution costs. No other security considerations pertain to this EIP.