Re:Efficiently Computing SSA Form and the Control Dependence...
by DannyBee on Wednesday August 03, 2022 @09:11AM
(#32331231)
Ken Zadeck was my office mate at IBM Research for a bit, and told me these groups of people (Ron, etc and Mark/Kenny) essentially discovered they had solved each others problems (Ken/Mark needed a formalism and efficient computation, Ron, etc were looking to understand how to use this stuff more broadly) while wandering the halls of watson research and seeing a group of people whiteboarding something at the end of one of the halls.
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:
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)