5 ms·

The shocking truth is that SSA is functional! That's right, the compiler for your favourite imperative language actually optimizes functional programs. See, for

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 https://www.jantar.org/papers/chakravarty03perspective.pdf. In fact, SSA, continuation passing style, and ANF are basically the same thing.

Chabsff 1y ago
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.
- PhilipRoman 1y ago
  If you're hell bent on functional style, you can represent memory writes as ((Address, Value, X) -> X), where X is a compile-time-only linear type representing the current memory state, which can be manipulated like any other SSA variable. It makes some things more elegant, like two reads of the same address naturally being the same value (as long as it's reading from the same memory state). Doesn't help at all with aliasing analysis or write reordering though so I don't think any serious compilers do this.
  - titzer 1y ago
    The sea-of-nodes representation renames memory as just another dependence edge in a somewhat analogous manner.
  - JonChesterfield 1y ago
    It helps _lots_ with aliasing analysis if you've got multiple instances of X representing disjoint areas of the address space. Could call them "heaps".
- noelwelsh 1y ago
  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 https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483 https://news.ycombinator.com/item?id=45678483 [1]: https://noelwelsh.com/posts/what-and-why-fp/ https://noelwelsh.com/posts/what-and-why-fp/
- superlopuh 1y ago
  In MLIR, there are two representations of memory, `tensor` and `memref`, which enables you to do some high-level things[0] in SSA before "bufferizing" to memrefs, which are eventually lowered to LLVM pointers. [0]: https://mlir.llvm.org/docs/Dialects/TensorOps/ https://mlir.llvm.org/docs/Dialects/TensorOps/
pizlonator 1y ago
No they're not. The essence of functional languages is that names are created by lambdas, labmdas are first class, and names might not alias themselves (within the same scope, two references to X may be referencing two instances of X that have different values). The essence of SSA is that names must-alias themselves (X referenced twice in the same scope will definitely give the same value). There are lots of other interesting differences. But perhaps the most important difference is just that when folks implement SSA, or CPS, or ANF, they end up with things that look radically different with little opportunity for skills transfer (if you're an SSA compiler hacker then you'll feel like a fish out of water in a CPS compiler). Folks like to write these "cute" papers that say things that sound nice but aren't really true.
- zozbot234 1y ago
  The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.
  - pizlonator 1y ago
    Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form. https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963 https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea... But even if you used block arguments, it's so very different from a lambda. Lambdas allow dynamic creation of variables, while SSA doesn't. Therefore, in SSA, variables must-alias themselves, while in the lambda calculus they don't. If you think that a block that takes arguments is the same as a lambda because you're willing to ignore such huge differences, then what's the limiting principle that would make you say that two languages really are different from one another? Remember, all Turing complete languages are "conceptually the same" in the sense that you can compile them to one another
    - JonChesterfield 1y ago
      Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were. It's storing to a "shadow variable" that you "load from" in the phi, i.e. it's exactly the same "store to ABI specified location in caller, load from it in callee" as a function call.
aatd86 1y ago
The same thing I don't know... but a long time ago, I remember reading that SSA and CPS were isomorphic. Basically CPS being used for functional languages. edit: actually even discussed on here CPS is formally equivalent to SSA, is it not? What are advantages of using CPS o... | Hacker News https://share.google/PkSUW97GIknkag7WY https://share.google/PkSUW97GIknkag7WY
- JonChesterfield 1y ago
  CPS has book keeping related to nested structures whereas SSA has the dominator tree. CPS is usually higher order and SSA usually first order. As in the continuation you're passing in CPS is probably a closure with some state attached. In SSA you'd have expanded that to pass a function and some explicit state argument, making the allocation explicit. I think the big thing in favour of CPS was it came first but I could be wrong about that. The lambda people came up with CPS and the imperative people came up with SSA. A while later Appel pointed out that they're views on very similar things. https://www.cs.princeton.edu/~appel/papers/ssafun.pdf https://www.cs.princeton.edu/~appel/papers/ssafun.pdf is worth reading if you haven't seen it yet.
  - cryptonector 1y ago
    > CPS has book keeping related to nested structures whereas SSA has the dominator tree. CPS compilers have to do a lot of work to get rid of pessimization due to unnecessary closures. Inlining, contification, and lambda lifting are some of the things they have to do. IIUC SSA compilers don't have to do that, which is their main advantage (i.e., they are naturally faster).

Chabsff 1y ago

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.

PhilipRoman 1y ago
If you're hell bent on functional style, you can represent memory writes as ((Address, Value, X) -> X), where X is a compile-time-only linear type representing the current memory state, which can be manipulated like any other SSA variable. It makes some things more elegant, like two reads of the same address naturally being the same value (as long as it's reading from the same memory state). Doesn't help at all with aliasing analysis or write reordering though so I don't think any serious compilers do this.
- titzer 1y ago
  The sea-of-nodes representation renames memory as just another dependence edge in a somewhat analogous manner.
- JonChesterfield 1y ago
  It helps _lots_ with aliasing analysis if you've got multiple instances of X representing disjoint areas of the address space. Could call them "heaps".
noelwelsh 1y ago
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 https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483 https://news.ycombinator.com/item?id=45678483 [1]: https://noelwelsh.com/posts/what-and-why-fp/ https://noelwelsh.com/posts/what-and-why-fp/
superlopuh 1y ago
In MLIR, there are two representations of memory, `tensor` and `memref`, which enables you to do some high-level things[0] in SSA before "bufferizing" to memrefs, which are eventually lowered to LLVM pointers. [0]: https://mlir.llvm.org/docs/Dialects/TensorOps/ https://mlir.llvm.org/docs/Dialects/TensorOps/

pizlonator 1y ago

No they're not. The essence of functional languages is that names are created by lambdas, labmdas are first class, and names might not alias themselves (within the same scope, two references to X may be referencing two instances of X that have different values). The essence of SSA is that names must-alias themselves (X referenced twice in the same scope will definitely give the same value). There are lots of other interesting differences. But perhaps the most important difference is just that when folks implement SSA, or CPS, or ANF, they end up with things that look radically different with little opportunity for skills transfer (if you're an SSA compiler hacker then you'll feel like a fish out of water in a CPS compiler). Folks like to write these "cute" papers that say things that sound nice but aren't really true.

zozbot234 1y ago
The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.
- pizlonator 1y ago
  Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form. https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963 https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea... But even if you used block arguments, it's so very different from a lambda. Lambdas allow dynamic creation of variables, while SSA doesn't. Therefore, in SSA, variables must-alias themselves, while in the lambda calculus they don't. If you think that a block that takes arguments is the same as a lambda because you're willing to ignore such huge differences, then what's the limiting principle that would make you say that two languages really are different from one another? Remember, all Turing complete languages are "conceptually the same" in the sense that you can compile them to one another
  - JonChesterfield 1y ago
    Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were. It's storing to a "shadow variable" that you "load from" in the phi, i.e. it's exactly the same "store to ABI specified location in caller, load from it in callee" as a function call.

aatd86 1y ago

The same thing I don't know... but a long time ago, I remember reading that SSA and CPS were isomorphic. Basically CPS being used for functional languages. edit: actually even discussed on here CPS is formally equivalent to SSA, is it not? What are advantages of using CPS o... | Hacker News https://share.google/PkSUW97GIknkag7WY https://share.google/PkSUW97GIknkag7WY

JonChesterfield 1y ago
CPS has book keeping related to nested structures whereas SSA has the dominator tree. CPS is usually higher order and SSA usually first order. As in the continuation you're passing in CPS is probably a closure with some state attached. In SSA you'd have expanded that to pass a function and some explicit state argument, making the allocation explicit. I think the big thing in favour of CPS was it came first but I could be wrong about that. The lambda people came up with CPS and the imperative people came up with SSA. A while later Appel pointed out that they're views on very similar things. https://www.cs.princeton.edu/~appel/papers/ssafun.pdf https://www.cs.princeton.edu/~appel/papers/ssafun.pdf is worth reading if you haven't seen it yet.
- cryptonector 1y ago
  > CPS has book keeping related to nested structures whereas SSA has the dominator tree. CPS compilers have to do a lot of work to get rid of pessimization due to unnecessary closures. Inlining, contification, and lambda lifting are some of the things they have to do. IIUC SSA compilers don't have to do that, which is their main advantage (i.e., they are naturally faster).