SSA is a representation of closed Cartesian categories that looks like normal code. Closed Cartesian categories model computation. You don't need SSA and modern compiler frameworks like MLIR make better choices that still mostly use SSA but have more sanity when it comes to basic block boundaries (treat them as having arguments, instead of phi nodes).
Why SSA?
51–60 of 106 posts
Re: Why SSA?
#52Every time I see a clean SSA explainer like this, I’m reminded that the “simplicity” of SSA only exists because we’ve decided mutation is evil. It’s not that SSA is simpler — it’s that we’ve engineered our entire optimization pipeline around pretending state doesn’t exist. It’s a brilliant illusion that works… until you hit aliasing, memory models, or concurrency, and suddenly the beautiful DAG collapses into a pile…
> we’ve decided mutation is evil
The functional programmers have decided mutability is evil. The imperative programmers have not.
We functional programmers do crazy stuff and pretend we're not on real hardware - a new variable instead of mutating (how wasteful!) and infinite registers (what real-world machine supports that!?).
Anyway, there's plenty of room for alternatives to SSA/CPS/ANF. It's always possible to come up with something with more mutation.
Re: Why SSA?
#53Every time I see a clean SSA explainer like this, I’m reminded that the “simplicity” of SSA only exists because we’ve decided mutation is evil. It’s not that SSA is simpler — it’s that we’ve engineered our entire optimization pipeline around pretending state doesn’t exist. It’s a brilliant illusion that works… until you hit aliasing, memory models, or concurrency, and suddenly the beautiful DAG collapses into a pile…
You have it backwards. Modern compilers don't use SSA because it's "simpler", we use it because it enables very fast data-flow optimizations (constant prop, CSE, register allocation, etc.) that would otherwise require a lot of state. It doesn't "pretend state doesn't exist", it's actually exactly what makes it possible/practical for the compiler to handle changes in state. As some evidence to the second point: Haskel…
Meanwhile Java Hotspot, where Sea-of-Nodes was originally made mainstream, and GraalVM are doing just fine.
The author of Sea-of-Nodes approach is quite critic of V8's decision, as one would expect.
Re: Why SSA?
#54Earlier quoted context omitted.
> take a look at how V8's move to Sea-of-Nodes has gone for them. Are you implying it hasn't gone well? I thought it bought some performance at least. What are the major issues? Any sources I can follow up on?
V8 blog post from March: "Land ahoy: leaving the Sea of Nodes" https://v8.dev/blog/leaving-the-sea-of-nodes
Feedback from sea of nodes algorithm creator, https://www.youtube.com/watch?v=Zo801M9E--M
Re: Why SSA?
#55I like the style of the blog but a minor nit I'd change is have a definition what SSA is right at the top. It discusses SSA for quite a while "SSA is a property of intermediate representations (IRs)", "it's frequently used" and only 10 paragraphs down actually defines what SSA is > SSA stands for “static single assignment”, and was developed in the 80s as a way to enhance the existing three-argument code (where every…
Yes, this is a problem I see more and more often. Besides the fact that it's always a good habit to spell out an acrostic or abbreviation the first time it's used in an article, there's also the fact that this is, you know, the web, and it's very easy to make a link to a Wikipedia article or something that will explain the term, if you don't want to bother adding your own explanation.
Re: Why SSA?
#56I like this article a lot but it doesn't answer the question of "Why SSA?". Sure, a graph representation is nice, but that isn't a unique property of SSA. You can have graph IRs that aren't SSA at all. And sure, SSA makes some optimizations easy, but it also makes other operations more difficult. When you consider that, plus the fact that going into and out of SSA is quite involved, it doesn't seem like SSA is worth…
In the basic block with arguments variation there is no going in and out of SSA.
Phi-functions and block arguments are just different views of the same thing. Sometimes it is more convenient to use one or the other when thinking of a problem.
If you lay out phi-functions and their parameters on a grid, you'd get a "phi-matrix" where phi-functions are rows and block arguments are the columns.
If you don't do an out-of-SSA transform before register allocation, and effectively treat block parameters like function calls then you're pushing the complexity to the register allocator.
An out-of-SSA transform before register allocation would coalesce not just registers but also variables in spill slots (thus avoiding memory-memory moves), it would reduce the complexity of parallel moves. A more advanced transform could also hoist moves out from before the hottest branch which could potentially lead to un-splitting previously split critical edges.
Re: Why SSA?
#57Earlier quoted context omitted.
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.
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/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 blo…
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.
Re: Why SSA?
#58The 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.
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
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 is worth reading if you haven't seen it yet.
Re: Why SSA?
#59Earlier quoted context omitted.
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.
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…
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".
Re: Why SSA?
#60SSA makes me think of a few interesting points: Considering it's a functional language (bar memory access bits), and most procedural languages can target this, we can say that a lot of procedural code can be compiled down to functional code - so procedural programming is syntactic sugar on top of a functional framework Also functional programmers have a couple of pet peeves - tail recursion to implement infinite recu…
The transition from one basic block to another is to copy the live values to some common location, jump the instruction counter, then copy the values out of that location to give the results of the phi nodes.
The transition from one function to another is to copy the arguments to some common location, jump the instruction counter, then copy the values our of that location to give the initial values of the parameters.
These are the same thing, except that the branch in the first case is always at the end of the block. In the tail position.
Your preferred looping construct of branching between basic blocks is _identically_ tail calls between functions, except that some of the block arguments are represented as phi nodes. This is because the blocks are functions.