argotorg / argotorg/solidity

Yul interpreter subset for side-effect-free evaluation

Open
#15,435 0 comments 0 reactions 0 assignees View on GitHub
medium effort medium impact nice to have optimizer
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.