[HN Gopher] Efficiently Computing SSA Form and the Control Depen...
___________________________________________________________________
Efficiently Computing SSA Form and the Control Dependence Graph
(1991) [pdf]
Author : hasheddan
Score : 30 points
Date : 2022-07-31 14:20 UTC (3 days ago)
(HTM) web link (www.cs.utexas.edu)
(TXT) w3m dump (www.cs.utexas.edu)
| pizlonator wrote:
| 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.
| dubiousconst281 wrote:
| 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.
| slavapestov wrote:
| 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-...
| tekknolagi wrote:
| I prefer https://pp.info.uni-
| karlsruhe.de/uploads/publikationen/braun...
| pizlonator wrote:
| 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.
| DannyBee wrote:
| 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:
|
| 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)
___________________________________________________________________
(page generated 2022-08-03 23:02 UTC)