Port the Scala 2 bytecode-optimizer to Dotty

[hamzaremmal]

TL;DR: All in the title!

The Scala 2 compiler has an implementation of a bytecode optimizer for the JVM. Unfortunately, as of today, we haven't yet ported that part of the Scala 2 compiler to Dotty. Now that we are working on having the stdlib fully compiled with Dotty (#22043), it should be time to also port the optimizer. An entry point to the optimizer would be to investigate the content of the following package: https://github.com/scala/scala/tree/86b9e84ea254cc294cd7b16fe0948631dbb41403/src/compiler/scala/tools/nsc/backend/jvm

[lrytz]

cc @bishabosha who asked me about this last summer

Here's a copy of my reply from back then

---

Jamie
Hey Lukas, hope you are doing well - i wanted to ask if you were to estimate how long it would take to make a bytecode optimiser for Scala 3? I’m asking because i think you were involved with the scala 2 optimiser

lukas
Hi Jamie, yes I wrote most of the optimizer. I would not replicate the Scala 2 approach in Scala 3. The usefuleness of the optimizer is severly hampered because it runs at compile time instead of link time. The main issues are:

1. it only optimizes code currently being compiled, binary dependencies on the classpath are unchanged
2. it cannot change the binary API (e.g. eliminate unreachable code)
3. it cannot assume a closed world, which prevents many optimizations (with a closed world assumption, any method which doesn't have an override on the classpath can be inlined; we can't do that)
4. Inlining creates tight coupling between the code being compiled and the dependencies on the classpath. The compiled code can end up invoking (public) binary API that is not part of the Scala API (e.g., protected in Scala is public in bytecode). The runtime classpath needs to match the compiletime classpath exactly, a MiMa-binary-compatible new version is not OK.

As a result, library authors cannot use the inliner, it would lock the classpath to exactly the dependency versions that they used when compiling their library. The optimizer without inlining can be used safely, but that's basically useless.
What we want is optimizing across the whole classpath at link time, like scala-js. This means library code will be optimized and we can make a closed world assumption (modulo dynamic class loading).
Prototyping a linker has been on my long-term todo/wishlist for a while. I think reusing what we wrote for Scala 2 would be ideal, not only for the prototype. The Scala 2 optimizer is implemented in ASM and all supporting data structures are completely separate from the compiler frontend and can be populated from bytecode. All the local optimizations (which are important, eliminiation of closures, boxes etc, cleaning up the bytecode) can be used, inlining as well. The call graph representation is probably also a good start, what we would need is a reachability analysis to be able to identify non-overridden methods (for inlining) and unreachable code (for elimination / tree shaking).

scala/scala-dev#396 for an older ticket.

[lrytz]

cc @sjrd