Census of binaryen/`wasm-opt` passes that might be relevant to Cranelift

What is Cranelift's job (in the context of Wasmtime)? To take Wasm that is produced by LLVM and already optimized 99% of the time and do the architecture-specific code generation that LLVM cannot do when targeting Wasm (e.g. instruction selection, regalloc). We don't want to duplicate *all* of LLVM's mid-end optimizations, only the ones that are beneficial for cleaning up and improving code after we've lowered Wasm memory operations into raw base + offset memory operations, etc. This is an interesting place for a compiler to be, and it means the set of passes and trade offs we have are different from what one might assume by default.

There is another compiler that is in a similar space, at least as far as consuming already-optimized-by-LLVM Wasm binaries and attempting to further optimize them: binaryen and `wasm-opt`. The big difference is that `wasm-opt` is emitting another Wasm binary while we are emitting machine code. But maybe they have passes that are not specific to targeting Wasm and which are beneficial to run on already-optimized-by-LLVM Wasm binaries? AIUI, the LLVM IR to Wasm lowering introduces some suboptimal code patterns.

So I did an informal census of what passes are run by `wasm-opt`, filtering out anything that looked overly specific to targeting Wasm. Results are summarized in the table below, and might give us some food for thought as we start looking into Cranelift's code quality some more. (FWIW, I wasn't 100% sure about some things below, so if you see something that you know is incorrect, feel free to edit this issue and correct it!)

| Pass | Description | Cranelift has equivalent? | Discussion |
|------|-------------|-------------------|------------|
| local-cse | Perform common-subexpression elimination within a block | **Yes** | Our GVN should cover all of this. |
| dce | Perform dead code elimination to remove unreachable blocks and unused expressions | **Yes** | |
| optimize-instructions | Peephole optimizations | **Partial** | We have some peepholes, but not as many as `wasm-opt`, and could definitely add more. Although, they care a lot about Wasm encoding tricks for peepholes where we do not. Probably better to look at LLVM itself here for inspiration. Finally, they also have some Souper-synthesized peepholes, and we should really add some of our own once the e-graphs work lands. |
| pick-load-signs | Look at uses of a load to determine whether to use sign extension or zero extension for the load (e.g. if the load instruction is `i32.load8_u` but a majority of uses are prefixed with `i32.extend8_s`, then change the load to `i32.load8_s`, remove the now-redundant sign extends from the majority of uses, and insert zero extends for the other uses.) | **No** | Unclear how much this is worth it in practice, especially if our primary goal is code speed rather than code size. |
| precompute[-propagate] | Constant propagation and folding | **Partial** | We have a couple peepholes in `simple_preopt` that do some of this, but only 2 levels deep. Should investigate doing this more completely once the WIP e-graphs work merges. |
| code-pushing | Push defs down towards uses. Might move the def into a block on the other side of a conditional, making it so that it is not executed unless needed. | **No** | Unsure whether their pass is aware of loop boundaries, and whether this might "undo" some manual LICM the programmer/LLVM did (this comes before their LICM in their phase ordering; our LICM won't create partially dead code, fwiw.) Although maybe we start (or can start) doing this with the new e-graphs work? |
| code-folding | Merge common tails of all of a block's predecessors into the block itself. | **No** | I don't believe we do any block-level optimizations that look at multiple predecessors or multiple successors at the same time (i.e. we can merge one successor block into its sole predecessor). FWIW, I don't see a dual pass for merging common heads of successor blocks into their predecessor block in `wasm-opt`, but that seems like an obvious thing to implement if you've implemented merging common tails of successor blocks. Totally possible it exists and I missed it. |
| merge-blocks | Sort of Wasm-specific, but essentially merge a block into its sole predecessor. | **Yes** | |
| duplicate-function-elimination | Interprocedural optimization to deduplicate identical functions. | **No** | When the new incremental caching infra is enabled, I *guess* we *could* get this for free? But also depends on implementation (which I am not personally familiar with) and order of function compilation scheduling in the face of our parallelism. |
| inlining | Inline a callee function into its caller, removing function call overhead and, more importantly, providing opportunity for more optimization based on the actual arguments to the call. | **No** | We probably don't want this for regular core Wasm modules right now, since LLVM did all the profitable inlining already and has way better heuristics than anything we are going to come up with on the first try. If something is both small and not inlined into callers by the time we see it, then it was probably either marked no-inline or cold or something like that and we just don't have those annotations anymore. However, with the component model this is going to change: callees will remain a black box until after component linking time (so LLVM won't ever have had a chance to inline these calls) and we will have lots of oppotunities to do some nice cross-module inlining ourselves. |
| directize | Turn `call_indirect`s into `call`s. Devirtualization. | **No** | Probably not profitable for us to do this, since LLVM already does it, but could be very profitable when done optimistically in concert with PGO data and then inline the callee into the caller. |