On Thu, Sep 7, 2017 at 12:49 AM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: >> >> That is only half of the job. > > No, it's the main job. >From the time complexity point of the view, it is the not the main job. The later part is. >> To get minimal SSA there is extra step >> to remove duplicate phi nodes. That is quadratic if I recall correctly. > > Quadratic in what? Simple SSA paper 4.1 Time Complexity. O(P + B(B +E)*V*V). that is O( B*B*V*V + B*E*V*V), where B is basic block, E is edge, V is variables. That is why I consider it quadratic. The first half or the part you consider the main job is not nearly as bad. > 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. The Keith et al paper is related to reducible. The simple SSA in the O() form is not relate to reducible. > 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 Minimal SSA is actually nice to have. Not minimal SSA will make the optimization run less effectively. Cytron el al give minimal form. > practice it won't make any noticeable difference. I think it will have some difference there in terms of optimizations. If we implement Cytron et al in the future, we can compare the result. > OTOH, there is a huge number of things that can be done on sparse > which *make* a lot of differences. Sure, that is a separate patch. > [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]. I think trivial phi can't happen in minimal SSA. If you place phi node in DF, it will need to have more than one parent and more than one define. OTOH, minimal SSA can have *dead* phi nodes. Liveness is independent from the SSA form. 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
