Yul interpreter subset for side-effect-free evaluation

[cameel]

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 (can handle only ADD, SUB, MUL, EXP, SHL and NOT) and a more full featured Yul interpreter 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, there are bits of code that are designed for fail randomly for fuzzing and has various bits that are just stubs.

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 for detailed description of each EVM instruction. Note that not all instructions are available on all EVM versions.