Parent issue for IR optimization passes

[mohammadfawaz]

This is a parent issue for all the basic optimization passes that we plan on adding. Please feel free to modify this description if you'd like to add more to it or remove some that you don't think are useful.

• [x] Dead Code Elimination (DCE):
  • [x] https://github.com/FuelLabs/sway/issues/1786
• [x] Constant folding and propagation
  • [x] https://github.com/FuelLabs/sway/pull/2615
  • [x] https://github.com/FuelLabs/sway/pull/2621
• [x] Simplify CFG:
  • [x] https://github.com/FuelLabs/sway/issues/2398
• [x] Memory to registers (mem2reg)
  • [x] https://github.com/FuelLabs/sway/issues/2770
• [x] Scalar Replacement of Aggregates (SROA)
  • [x] https://github.com/FuelLabs/sway/issues/3136
• [ ] Loop Invariant Code Motion (LICM)
• [x] https://github.com/FuelLabs/sway/issues/2755
• [ ] Common Sub-expression Elimination (CSE)
  • [ ] https://github.com/FuelLabs/sway/pull/6413

Also:

• https://github.com/FuelLabs/sway/issues/2399

[otrho]

Cool. The above list is of optimisation pass categories really, and we can add sublists as we go. E.g., there's already function inlining but it needs improvement as it currently inlines everything -- it needs heuristics to decide what & when to inline. And we already have some constant folding but only for the intialisation of structs -- there are dozens of different areas where constant combining can be added separately.

As we add more passes there will arise the need for a pass manager too, but that can probably go in another issue. I have had a few ideas for making a modern pass manager. Might be worth creating an RFC for.

[tritao]

It might also be useful to take a look at Binaryen's set of optimizations, as well as their implementations, as the code is more self-contained and dependency-free, as compared to LLVM.

[otrho]

Slide 19 in this presentation from Graydon Hoare: http://venge.net/graydon/talks/CompilerTalk-2019.pdf

Frances Allen Got All The Good Ones

• 1971: "A Catalogue of Optimizing Transformations".
• The ~8 passes to write if you're going to bother.
• Inline, Unroll (& Vectorize), CSE, DCE, Code Motion, Constant Fold, Peephole.
• That's it. You're welcome.
• Many compilers just do those, get ~80% best-case perf.

[mohammadfawaz]

@vaivaswatha I will keep this issue assigned to you as you own all its subtasks.