An ode to livelyness analysis; SSA to registers

Nice article. Walking SSA forward for register allocation means determining the last use of a register in order to free it for other allocations. If you walk backwards (say Post-Order) then the single definition is the "last use". There are some classical register allocation problems with lost copies, and dealing with swaps not covered here. I tried to capture what I could in https://arxiv.org/abs/2011.05608 but were I to do the work again, I'd allocate everything backward.

Not impressed by using 3 passes, instead of one. This is a dynamic language, not an AOT compiler.

While this article is about SSA to registers, but I went through hell with SSA, here's some of my two cents:

1. phi node consturction is hard

If you think about it, the phi function actually requires you to know where the control is coming from, that means when you try to interpret it in the mental model, you need to memorize it or have some flags to indicate which contorl flow it is coming from. For a human, phi function is basically an oracle function with your mind and memory, because you can look around and deduce phi assignment naturally (usually with leap of faith), but the machines only follow rules and they don't have an oracle. So then:

2. SSA as a control flow problem

So a first principle solution to phi assignment, the standard text book solution, is turning the program into control-flow graph. This reduced the problem into the field of graph theory, that you want to find the predecessors for each phi node on the control-flow graph, until there is no more. An equivalent form of that is dominator graph, where the phi nodes are reduced to finding out the dominance frontier of the control flows, i.e. finding out where the incoming edges are. This algorithm, unfortunately, while direct, takes quadratic time, asymptotically speaking. During this time, you can also coalesce a continuous program instrucion node in the graph, if they formed a linked list somehow until there is another phi that forked the control flow, this is known as "basic block", so to speak.

But it turns out another way to solve this control flow problem, is by turning it "backward", or let's say, inverted.

3. SSA is closely resembled to continuation passing style in functional programming

It turns out SSA has a functional equivalence to what we call A-Normal Form, which works by predefining variables and all the scopes beneath that shares the same scope (if you think about it, which is also dominance relationship, but designated), so there is some kind of push-pop structure, aka stack relationship, turning it into a continuation of a series of let expressions, then this is easily representable using tree-shaped algebraic data types in a depth-first manner (been through it in Rust enums, looks pretty nice actually), and so you can easily pass the control flow as data, and I believe that is also where basic block, again, naturally emerge, because instead of just assigning variables, why don't you just encircle a block of variables, and take that as a "function pointer" (in a more pedantic sense, a function closure with global id) that is effectively unique and immutable?

And because it is "continuation of a series of let expressions", you can easily turn ANF into CPS too by turning each let expression into a call/cc lambda, which finally closes the SSA->ANF->CPS saga.

(And because of that, a far cousin of SSA is algebraic effect, due to its relationship with delimited continuation, which is also a way to break down control flow into resumable blocks like you see in basic-block SSA. Almost the same idea, but for different context, effect systems are more focused on things like async/await and coroutine, where another contender in this area is ST-monad)

So...you need to know the previous location of control flow for determining what path this phi goes, and the fact that it is quadratic using dominance frontier, and ANF construction isn't really intuitive or easy to do it in first place, are there any ways smarter than quadratic?

3. phi node construction is (relatively) easy, if you don't mind missing out on the best performance

It turns out there is a way to do it in linear time, albeit if you think about it, there is a greedy solution to the SSA assignment problem, the idea is from the paper https://c9x.me/compile/bib/braun13cc.pdf.

I'd try my best to explain what I read with this paper few months before, but it really does sound arcane to me initially, until one night after shower it kind of clicked:

a. initialize a hash set to memorize the "seen" variables and instructions

b. if there current variable is not assigned, occupy it and assign it to "seen" set

c. use tarjan's algorithm to isolate the instructions and phis into its own section if they formed cycles, turning them into essentially strongly connected components

d. do a topological sort on the strongly connected components, forming a partial order

e. prune the extra phis in the sorted components, leveraging the partial order as dominance

That's it. It uses memoization, SCC and topological sort, but while some parts of it uses dynamic programming, the overall solution here is still a greedy one. In fact, if you further take a similar idea in register allocation, that technique is called Linear Scan Register Allocation, which is what this article is about.

And if you combine both Linear SSA construction and Linear Scan Register Allocation, the whole codegen now turns from a quadratic algorithm plus NP-Complete problem (by reducing RA into graph coloring, see Chaitin's algorithm), into much faster algorithms down the line. This is very important, because many Just-In-Time compiler I believe used this combo, and is how you get fast baseline JIT compiler in practice.