Option to harden the Yul optimizer against AST-ID based non-determinism.
- Dominant language
- C++
- Stars
- 25.7k
- Forks
- 6.2k
- Avg merge
- 1d 11h
- Merged PRs (30d)
- 21
Description
**Note: this issue is meant to lay out a solution that will take a good amount of refactoring merely for consideration and may not be what we end up doing.**
We keep running into issues like https://github.com/ethereum/solidity/issues/14494 with the Yul optimizer.
The symptom is differences in bytecode between one compilation of a contract and another compilation with additional, but unrelated source files. In these cases the compiler-generated metadata is identical, which is supposed to guarantee identical compiler output. However, this guarantee is violated.
There are potential causes already in IR code generation, this issue means to address causes in the Yul optimizer.
- All source files supplied to the Compiler are parsed together and in the process assigned unique AST-IDs. Hence, the compiler may assign different AST-IDs in the presence of additional source files.
- Via-IR code generation needs to generate unique Yul identifiers for expressions and statements in Solidity. It currently does so on the basis of the most obvious choice of unique identifiers available, which is the AST ID of the Solidity AST node triggering the generation of the respective Yul identifier. This results in the Yul identifiers to differ if AST IDs differ!
- Due to the last point, the Yul optimizer may never depend on the comparison of Yul identifiers. This is exacerbated due to the fact that ``YulString`` comparison does not coincide with lexicographic string comparison (although even the latter would only result in monotonic comparison if left-padded with zeroes).
The following would be an option to evade this issue once and for all, while potentially allowing to increase the optimizer performance in the process (however, the actual expected improvement is hard to estimate and may not be significant):
- Templatize the Yul AST over the type of Identifiers. Split between a regular Yul AST and an optimizer variant of the Yul AST.
```c++
template
struct TIdentifier { std::shared_ptr debugData; NameType name; };
using Identifier = TIdentifier;
namespace optimizer { using Identifier = TIdentifer; }
```
Note: the template argument will be inherited by all Yul AST nodes.
- Parse Yul as usual into a regular Yul AST.
- At the beginning of optimization translate the regular Yul AST to an optimizer Yul AST by mapping names to a deterministic sequence of indices. Store the association of the indices with original names.
- When generating new identifiers in the optimizer, take care to do so in deterministic order (this is still an unavoidable source of errors in this model), while inheriting the associated original name of the "source identifier", if applicable (similarly to the current "name hint" mechanism).
- Side-Advantage: during optimization comparison of Yul identifiers is cheap; associative maps can potentially even be replaced by sequential containers/vectors (accounting for the possibility of new identifiers being generated in the process)
- At the end of optimization translate the optimizer Yul AST back to a regular Yul AST while generating unique human-readable names based on the associated original names of the indices (note that due to potentially generating new identifiers, these names need to be disambiguated)
Complications:
- The Yul dialects identify builtins based on their string-based name and need to be accounted for in the process. They could potentially produce a fixed static const vector of builtin identifiers that is used to map the builtins to specific fixed indices.
- Debugging output between steps would have to involve the translation from optimizer Yul AST to regular Yul AST.
- There is a significant amount of refactoring involved in this and potential sources of errors in the ordering of generating fresh identifiers remains.
Contributor guide
Research direction
No files or tests are named. Start by tracing the Yul optimizer and via-IR code-generation paths described in the issue, then assess how AST-derived identifiers are created and compared. Done would require a decided approach that preserves deterministic output while accounting for builtins, debugging output, and generated names.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, solidity
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100