On Wed, Sep 6, 2017 at 11:17 PM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: > > Bah ... > Depending on the algorithm you use, irreducible graphs may indeed be a bit > faster to calculate but since you don't know in advance if your graph is ^^^^^^^^ You mean slower here. > reducible or not, you can't take advantage of that. So, at least to me, > this doesn't make it a fast path. Well, if the graph is not reducible, it will have a extra step to get get minimal SSA, that is what I consider the slow path. For Cytron et al, the slowest part is finding dominator tree. If using the Keith Cooper paper, reducible graph will converge faster naturally. You don't need to know it is reducible or not in advance to benefit from it. > >> On way to look at the Simple SSA paper is that, it is taking advanctage >> of that fast path. > > No. It takes advantage at every point where it is known that all the parents > have already been processed. That's all. That is only half of the job. To get minimal SSA there is extra step to remove duplicate phi nodes. That is quadratic if I recall correctly. > The part where reducibility matter is after the conversion is done, if > you whish to simplify what they call trivial phi-nodes. And again, since > you don't know in advance if your graph is reducible or not, there is no > fast path. So you are saying in order to get minimal SSA, you need to run do the remove extra phi node even if it is already minimal? Because we don't know it is reducible or not. 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
