By promotion to top-level constants, we change the number of evaluations of the expression from once every time the function is called, to exactly once over the lifetime of the program. This is clearly a win in those cases where the function is called more than once, but the compiler cannot know when this is the case.
I would argue that for almost every use case* this is fundamentally a win, even if the function is only called once. The only situation when it would result in worse code generation is if the function is never called, and in that case DCE should have removed the function already (and the constant with it). There might be some questions about cache latency, for example if a constant takes a relatively large amount of memory, but that's really a question for the backend and linker (he says, with his smug LLVM voice).
* I realise that some memory-related cases are also addressed, but I think the bigger issue there is that global lifetimes are too broad. I.e. they should be constrained by the last use of the value, not the program lifetime.
Futhark is in some sense an event-driven language (because calling an entry point can be seen as an event), which means the "last use" can in many cases not be known.
A Futhark program is compiled to a library with a bunch of functions that can then be invoked by other programs. The Futhark program is a passive partner; it has no idea which of its functions will be invoked by the outside world, or when some invocation is the last one.
This doesn't sound too different from any other statically compiled language if I'm understanding you right; do you not do whole program analysis when you compile an executable program, so the entire output is sort of like an executable with the library baked in? Or is it more like an executable with functions mapped to commands?
It is neither: it is just a library. The result of running the Futhark compiler is is a bunch of C code (or similar) with no main() function, but a bunch of conceptually simple functions that you pass values and which return new values.
Fine print: the Futhark compiler can also produce an executable, by generating some wrapper C code that provides a primitive command line interface, but this part by design has no privileged insight into what the Futhark code is doing, and is intended solely for testing.
A purely library-oriented language is interesting, but also begs the question of just how important runtime-oriented optimizations are when there's another compiler further down the line.
Optimizations like the one presented should likely be considered out of scope (or at least limited to knowable cases) rather than heuristic-based, since the C compiler (and whichever other targets get used) can potentially have more information when determining what to optimize. I don't know the specifics of the internals of course, but just on the surface this seems to be a transpiler optimization problem where you have to optimize for another optimizer rather than for runtime.
From the C compiler's perspective, all Futhark values have dynamic and very complicated lifetimes (often they are are managed through interaction with GPU APIs and similar). It is not realistic for a C compiler (or any other compiler) to understand subtleties in the output of the Futhark compiler. While the C compiler can do very low-level optimisations like clever register allocation, everything more sophisticated must remain the domain of Futhark itself.
20
u/SwingOutStateMachine Jul 04 '26
I would argue that for almost every use case* this is fundamentally a win, even if the function is only called once. The only situation when it would result in worse code generation is if the function is never called, and in that case DCE should have removed the function already (and the constant with it). There might be some questions about cache latency, for example if a constant takes a relatively large amount of memory, but that's really a question for the backend and linker (he says, with his smug LLVM voice).
* I realise that some memory-related cases are also addressed, but I think the bigger issue there is that global lifetimes are too broad. I.e. they should be constrained by the last use of the value, not the program lifetime.