←back to thread

Why SSA Compilers?

(mcyoung.xyz)
185 points transpute | 1 comments | 22 Oct 25 20:13 UTC | HN request time: 0.284s | source
Show context
noelwelsh ◴[22 Oct 25 20:53 UTC] No.45675013[source]▶
The shocking truth is that SSA is functional! That's right, the compiler for your favourite imperative language actually optimizes functional programs. See, for example, https://www.jantar.org/papers/chakravarty03perspective.pdf. In fact, SSA, continuation passing style, and ANF are basically the same thing.
replies(3): >>45675172 #>>45675361 #>>45675764 #
Chabsff ◴[22 Oct 25 21:09 UTC] No.45675172[source]▶
My experience with SSA is extremely limited, so that might be a stupid question. But does that remain true once memory enters the picture?

The llvm tutorials I played with (admittedly a long time ago) made it seem like "just allocate everything and trust mem2reg" basically abstracted SSA pretty completely from a user pov.

replies(2): >>45676689 #>>45678567 #
1. noelwelsh ◴[23 Oct 25 05:50 UTC] No.45678567[source]▶
I think you're asking if SSA is still a functional language in the presence of mutation of memory. Both Scheme and ML (of Standard ML and OCaml fame, not machine learning) allow mutation, so mutation doesn't seem to disqualify a language from being functional.

This naturally leads to the question "what is a functional language?" I've written my thoughts on what FP is at [1]. I argue that FP is about local reasoning and composition. The former is most relevant here: local reasoning means it's easy to reason about code. This is exactly why SSA is used in compiler: it makes it easy for the compiler to reason about code and therefore which optimizations are valid. This is the same argument given in these comments: https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483

[1]: https://noelwelsh.com/posts/what-and-why-fp/