compiler-constructionssa

Fast calculation of dominators


It is said that when converting intermediate code to static single assignment form,

  1. It is necessary to calculate the dominators of basic blocks

  2. The somewhat obvious way to do this as a fixed point of equations is slow

  3. To do it fast, you need to use the fairly complicated Lengauer-Tarjan algorithm

I can see the first two points, but I'm not clear about the reasoning behind the third. In particular, is there any reason why you can't do it just in the process of calculating the preorder dominator tree? I've implemented a version of that in JavaScript and it seems to work:

var domPreorder = [];

function doms(b) {
    b.children = [];
    for (var c of b[b.length - 1].targets)
        if (c.i == null) {
            c.i = domPreorder.length
            domPreorder.push(c)
            b.children.push(c)
            c.parent = b
            doms(c)
        }
}

f[0].i = 0
domPreorder.push(f[0])
doms(f[0])

Is there some disadvantage to this method that I'm not seeing?


Solution

  • While calculating dominators quickly and correctly is indeed not trivial, there are much simpler algorithms than Lengauer-Tarjan that are as fast or faster in practice (i.e. on the kinds of control flow graphs that occur in most programs), even though the worst-case complexity sounds scary. See: Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). "A Simple, Fast Dominance Algorithm"