Profile-Guided Optimization (PGO) support for Futhark

[zamazan4ik]

Hi!

Recently I started to evaluate the Profile-Guided Optimization (PGO) state across multiple programming languages and ecosystems. I did a lot of PGO measurements and benchmarks - all the results are available here. According to my experience, PGO helps with achieving better optimization levels in many real-world applications. That's why I think having PGO support for compiling Futhark programs is a nice feature to have since the language cares a lot about performance.

Multiple languages already support PGO like:

• C, C++, Fortran (in Clang, GCC, MSVC, ICC)
• Rust (Rustc)
• Go (was recently added in the 1.21 release)
• Java (via GraalVM)
• C#

In this issue, I suggest evaluating the idea about adding PGO support to the Futhark compiler. With this optimization, it will be possible to perform more data-driven optimizations for Futhark programs and get better performance.

[athas]

Which specific profile-guided optimisations would be useful for Futhark? Futhark does have workload-sensitive autotuning, in the form of incremental flattening, but it does not depend on information flowing back into the compiler. In principle it could do so, and for some programs it might result in a meagre advantage.

One idea would be to use array sizes observed at run-time. The Futhark compiler sometimes makes bad choices because it assumes all arrays are "large", even if they turn out not to be at runtime.

[zamazan4ik]

Which specific profile-guided optimisations would be useful for Futhark?

Honestly, I don't know which optimizations now are performed by the Futhark compiler. For "regular" compilers PGO largely improves inlining decisions, hot/cold code splitting, etc. I don't know how many of these optimizations are useful/implemented in the compiler. If you have some documentation about the implemented optimizations or can explain me quickly - it would be great!

One idea would be to use array sizes observed at run-time. The Futhark compiler sometimes makes bad choices because it assumes all arrays are "large", even if they turn out not to be at runtime.

Yep, the idea sounds promising!

[athas]

Futhark mostly does structural optimisation on small programs - fusion etc. Inlining of structurally relevant functions must always be done, and inlining of smaller functions can be left for the C compiler that runs after. Futhark doesn't have a notion of hold/cold code paths, and I'm not sure it's applicable to the numerical domain. The main challenge that depends on statically unknown data is how much to parallelise, and incremental flattening is a pretty decent solution to that (and it is very similar to PGO, except that it doesn't require rerunning the compiler).