Efficiently Computing SSA Form and the Control Dependence Graph (1991) [pdf](cs.utexas.edu)
cs.utexas.edu
Efficiently Computing SSA Form and the Control Dependence Graph (1991) [pdf]
https://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf
6 comments
It seems that the exact opposite problem (phi elimination / translating out of SSA form) is rarely discussed in depth, especially in introductory material.
From what I've seen, most compilers rely on the register allocator to deal with this problem (which makes total sense), or just don't bother at all and instead keep SSA in "conventional" form.
But the problem isn't really that difficult. In Sreedhar/Boissinot et al.'s paper (which btw has a typo in the copy sequentialization algorithm), the idea is quite simple: create copies for each phi argument, plus an additional copy for the phi result, then coalesce those copies to the same variable if their live-ranges don't intersect. The devil is on the details of course, and it just takes a lot more effort to implement compared to the text book construction algorithm.
From what I've seen, most compilers rely on the register allocator to deal with this problem (which makes total sense), or just don't bother at all and instead keep SSA in "conventional" form.
But the problem isn't really that difficult. In Sreedhar/Boissinot et al.'s paper (which btw has a typo in the copy sequentialization algorithm), the idea is quite simple: create copies for each phi argument, plus an additional copy for the phi result, then coalesce those copies to the same variable if their live-ranges don't intersect. The devil is on the details of course, and it just takes a lot more effort to implement compared to the text book construction algorithm.
I remember reading this paper, implementing the algorithm in Factor and finding the typo some 13 years ago… http://hal.archives-ouvertes.fr/docs/00/34/99/25/PDF/OutSSA-...
That’s a pretty great algorithm.
Here’s why I use Cytron’s: you’ll want dominator trees anyway since they provide amazing short-circuit solutions to lots of otherwise annoying problems. Once you have an implementation of dom trees, it’s so easy to implement dominance frontiers, and then it’s trivial to just compute the optimal phi placement from the frontiers.
And then you can reuse the results of the dom analysis for other optimizations downstream from SSA conversion.
So, it’s not that Braun et al is a bad algorithm or that it’s harder to implement in isolation. It’s that Braun’s is harder to implement if you have already built a dom analysis, and you’ll eventually want the dom analysis anyway. So might as well start there.
Here’s why I use Cytron’s: you’ll want dominator trees anyway since they provide amazing short-circuit solutions to lots of otherwise annoying problems. Once you have an implementation of dom trees, it’s so easy to implement dominance frontiers, and then it’s trivial to just compute the optimal phi placement from the frontiers.
And then you can reuse the results of the dom analysis for other optimizations downstream from SSA conversion.
So, it’s not that Braun et al is a bad algorithm or that it’s harder to implement in isolation. It’s that Braun’s is harder to implement if you have already built a dom analysis, and you’ll eventually want the dom analysis anyway. So might as well start there.
Classic paper. I’ve always implemented SSA conversion using roughly this approach (though the details in my code might be different). Bottom line though: dominator trees and dominance frontiers are your friend.
I"m sure it's not quite that simple (and it's been over a decade, so i may be misremembering some details anyway), but still pretty funny.
Also explained why the paper often feels like two papers - it kinda is.
Nowadays, of course, plenty of linear time algorithms exist for this. In fact, there is basically a whole class of linear time transforms that, when applied to code, will reduce some group of polynomial time algorithms to linear (like SSA does).
LLVM, at least when i ran out of time to contribute a few years ago, was using a Sreedhar and Gao's computation algorithm. This is the fastest way to compute it i'm aware of on larger programs.
Which is also interesting itself for a few reasons:
1. The paper/algorithm was ignored for many years because some more well known researchers painted it as "very slow in practice" in their papers/comparison charts - it turns out they had just done a really bad implementation.
2. The algorithm is dramatically easier to implement than the paper makes out once you understand what is going on. It's <100 lines of code:
https://github.com/llvm/llvm-project/blob/main/llvm/include/...
(and this is the refactored version i made to support both forward and reverse iterated dominance frontiers. Cameron's original code was even simpler)