[LLVMdev] DominanceFrontier/PostDominanceFrontier for PRE

[Daniel Berlin]

On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org> wrote:
> Is there a reason this is better than the modified algorithm created
> by Ferrante?
> It looks like yours has as bad a worst case time bound in reality.
> That is, the algorithm runs in O(sum of the size of all the dominance
> frontiers).
>
> http://www.cs.rice.edu/~keith/Embed/dom.pdf
>
> See figure 5. It will only touch nodes actually in the dominance frontier.
>

Note this is mostly rhetorical, as that the paper asserts about the
dominance frontier algorithm in figure 5: "we contend that the sets
cannot be built any more efficiently".
Given the paper's authors, I have a tendency to trust this assertion.