Option to harden the Yul optimizer against AST-ID based non-determinism.

[ekpyron]

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.

  template<typename NameType>
  struct TIdentifier { std::shared_ptr<DebugData const> debugData; NameType name; };
  using Identifier = TIdentifier<YulString>;
  namespace optimizer { using Identifier = TIdentifer<size_t>; }

  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.

[ekpyron]

Actually, there is a less-invasive, yet messier, variant of the above:

We could leave the Yul AST data structures untouched, but translate all identifiers, excluding builtins, to _1, _2, ... in the beginning of optimization, while still keeping above mapping to original names for a back-translation.