Yul interpreter subset for side-effect-free evaluation
- Dominant language
- C++
- Stars
- 25.7k
- Forks
- 6.2k
- Avg merge
- 1d 11h
- Merged PRs (30d)
- 21
Description
Prerequisite for #15358.
## Abstract
A reliable Yul interpreter that can evaluate expressions with no side-effects and handle basic control flow would be very useful in Yul optimizer.
Currently we only have a [**very** rudimentary EVM-level intepreter in `ConstantOptimiser`](https://github.com/ethereum/solidity/blob/v0.8.27/libyul/backends/evm/ConstantOptimiser.cpp#L41-L89) (can handle only `ADD`, `SUB`, `MUL`, `EXP`, `SHL` and `NOT`) and [a more full featured Yul interpreter](https://github.com/ethereum/solidity/tree/develop/test/tools/yulInterpreter) that was built with testing in mind and is not robust enough for production use. For example it uses [hard-coded values for some built-ins](https://github.com/ethereum/solidity/blob/v0.8.27/test/tools/yulInterpreter/Interpreter.h#L85-L120), [there are bits of code that are designed for fail randomly for fuzzing](https://github.com/ethereum/solidity/blob/v0.8.27/test/tools/yulInterpreter/EVMInstructionInterpreter.cpp#L376-L377) and [has various bits that are just stubs](https://github.com/ethereum/solidity/blob/v0.8.27/test/tools/yulInterpreter/EVMInstructionInterpreter.cpp#L265).
However, the core part of the test interpreter limited to side-effect-free evaluation looks like it should be a good-enough starting point. We could make it reliable.
## Specification
- Extract a subset of `test/tools/yulInterpreter/` into `libyul`.
- Just handle control flow and have aborting conditions for anything that doesn't fall in scope (including memory access, reverts, etc.).
- Don’t handle memory/storage/calldata/returndata.
- Beyond control flow, just handle plain "pure" opcodes, e.g. arithmetic, etc., anything just producing values purely from other values on stack.
- The interpreter should be agnostic to the set of builtins.
- The current interpreter should keep working as is for testing and fuzzing purposes. It should become an extension of the new interpreter, but still be kept in test suite, not `libyul`.
- The side-effect-free part of the interpreter should be covered with enough tests to give us confidence that the behavior exactly matches that of the EVM.
- Use `YulInterpreterTest` for testing and keep test cases small and modular.
- Refer to the [execution spec](https://github.com/ethereum/execution-specs/tree/master/src/ethereum/cancun/vm/instructions) for detailed description of each EVM instruction. Note that not all instructions are available on all EVM versions.
Contributor guide
Research direction
Start by comparing test/tools/yulInterpreter/ with libyul and the limited ConstantOptimiser implementation. Read the YulInterpreterTest cases and the linked execution spec to identify the side-effect-free control-flow and pure-opcode behavior in scope. Done means the extracted interpreter is reliable, the existing test interpreter still works as an extension, and the covered behavior has modular tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100