Improvements in the Yul-EVM Code transform

[NunoFilipeSantos]

What

Improve Yul-EVM code transform and remove stack-too-deep errors as blockers to via IR.

Why

Currently, the via-IR compilation pipeline is not viable as default compilation mode for two reasons:

• Without optimizer hardly any non-trivial project compiles due to stack-too-deep errors.
• Even with optimizer, some more complex projects suffer from stack-too-deep errors.
• The performance of the via-IR pipeline still significantly lower than the legacy pipeline.

Tasks

• Further improve stack shuffling performance
• The current stack layout generation algorithm attempts to find the best stack layout based on minimum gas cost by performing the shuffling of stack slots. We should be able to improve the performance of the stack layout generation if we are able to determine the minimum stack layout prefix before shuffling, reducing the number of permutations, or even replacing the current shuffling step completely.
  • Create a Dominator tree from the CFG.
    • Implementation of Lengauer-Tarjan algorithm to find dominators #14460
  • Generate the stack layout prefix based on the dominator tree and perform the shuffling for the remaining slots if any.
    It turned out that this approach would not work as we initially thought and we decided to go for doing proper SSA form.
  • Implement minimal or pruned-SSA form using dominators for control flow analysis.
  • Evaluate performance of the approach in term of compilation time and gas usage.
  • Improve stack to memory (we need to minimize stack to memory moves).
  • Ensure all codegen tests pass :)
• Lift down stack-to-memory from code-transform-Yul-optimizer interplay to being handled in the code transform directly.

Out of scope

• Avoiding stack too deep errors:
  • under all circumstances: Like in recursive functions.
  • in the presence of memory unsafe assembly

[cameel]

#12865 likely should also be considered a part of this. It does not cause "stack too deep" on its own but unnecessary unlinked references have similar impact on tools in terms of blocking via IR adoption.

[ekpyron]

#12865 likely should also be considered a part of this. It does not cause "stack too deep" on its own but unnecessary unlinked references have similar impact on tools in terms of blocking via IR adoption.

1. We shouldn't cross-scope these things, so I categorically wouldn't consider this as a part here.
2. We likely won't solve this issue here without optimizer anyways, and with optimizer the other one is a non-issue. So the main thing to consider here would be a minimal optimization sequence by default for via-IR, which we'll probably do, but yeah, this is off-topic here.

[NunoFilipeSantos]

#12865 likely should also be considered a part of this. It does not cause "stack too deep" on its own but unnecessary unlinked references have similar impact on tools in terms of blocking via IR adoption.

1. We shouldn't cross-scope these things, so I categorically wouldn't consider this as a part here.
2. We likely won't solve this issue here without optimizer anyways, and with optimizer the other one is a non-issue. So the main thing to consider here would be a minimal optimization sequence by default for via-IR, which we'll probably do, but yeah, this is off-topic here.

1. Absolutely. If it's tangent, it shouldn't belong here.
2. I'm in favor of heavily scoping down initially and seeing where we land in Q1, rather than expanding immensely and missing such a large goalposts (a full quarter).

Remember that we don't plan for 100% of our time, meaning all the other day to day "sidequests" also take time.