On Thu, Sep 7, 2017 at 6:04 AM, Christopher Li <sparse@xxxxxxxxxxx> wrote: > 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. Of course. >> 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. OK, it's just faster on reducible graphs. >> >>> 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. No, it's the main job. > To get minimal SSA there is extra step > to remove duplicate phi nodes. That is quadratic if I recall correctly. Quadratic in what? If you have plenty of phi-nodes with plenty of operands, you will have more work to do, irrespectively of the size of the graph and its reducibility. Also, even if the reducibility is a property of the whole graph, it's not really what matters here because each phi-chain is to be taken independently. In other words, what matters here is if the *subgraph* involved in the phi-chain is reducible or not. So even if the graph is irreducible, you can have 99% of the phi as if the graph was reducible. Anyway, this minimal SSA and irreducibility is a nice theoretical question you seem a bit obsessed with. I absolutely don't care about because in practice it won't make any noticeable difference. OTOH, there is a huge number of things that can be done on sparse which *make* a lot of differences. >> 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. Yes and no. There are a lot of cases where you can simplify away the phi-nodes by simple ways. For the remaining ones, yes, most probably. [Warning, I'm only talking here about the situation with Simple SSA, with the classic methods you have minimal SSA almost by definition but again 'minimal SSA' is 'minimal' only in this very narrow sense and it doesn't mean that no phi-nodes can be removed. For example, I'm pretty sure that what the "Simple SSA" article call 'trivial phi' *can* also happen even in minimal SSA]. -- Luc -- 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
