sway icon indicating copy to clipboard operation
sway copied to clipboard
verified publisher icon FuelLabs

Parent issue for IR optimization passes

Open mohammadfawaz opened this issue 3 years ago • 4 comments

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)
  • [ ] https://github.com/FuelLabs/sway/issues/2755
  • [x] Common Sub-expression Elimination (CSE)
    • [x] https://github.com/FuelLabs/sway/pull/6413

Also:

  • [x] https://github.com/FuelLabs/sway/issues/2399

mohammadfawaz avatar Jul 26 '22 13:07 mohammadfawaz

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.

otrho avatar Jul 27 '22 02:07 otrho

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.

tritao avatar Jul 27 '22 12:07 tritao

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.

otrho avatar Sep 12 '22 03:09 otrho

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

mohammadfawaz avatar Feb 02 '23 13:02 mohammadfawaz