On Wed, Sep 6, 2017 at 10:03 PM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: > > Mmmm, I think you're confused. > The dominator tree is a function of the whole graph, not just > some blocks. Also, after linearization, there is no more for(), > while() & do-while() or gotos: all CFG edges are alike. I am not confused. I might jump my sentence too fast. > What was written here above is that, *during linearization*, > when you have a branch from a structured-programming statement, > you know what are all the possible parents of the current block. > For branches coming from goto, it's not the case. > This has nothing to do with the dominance tree as such. I am referring to the "A Simple, Fast Dominance Algorithm" If there is no goto. The function CFG is reducible graph. For reducible graph that algorithm converge in constant iteration. So finding the dominator tree is pretty much linear if the graph is reducible. > [Of course, the presence of gotos *can* create irreducible graphs > and for those calculating their dominance tree *can* take a bit > more time, but that's all.] Right, the irreducible graphs is the trouble maker account for those nasty worse case performance. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
