On Thu, Sep 7, 2017 at 8:17 AM, Christopher Li <sparse@xxxxxxxxxxx> wrote: > On Thu, Sep 7, 2017 at 12:49 AM, Luc Van Oostenryck > <luc.vanoostenryck@xxxxxxxxx> wrote: > > > 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. That's the difference between 'in practice' and '(in theory) it will have some'. In practice, it will, of course, make a big difference *if* what you have is not at all minimal, like dumb-SSA. But if 99% of your phis are in fact needed and only 1% are part of the non-minimality, you won't see any *significant* differences. It's not as if the presence of a single superfluous phi-node will totally collapse your performance. In practice, it also won't make any significative difference because *even* if you use gotos, this won't make automatically your graph irreducible. To make your graph irreducible you need to have a goto that jump *into* a loop and normally it's not something people write (think about it, when it could make sense?). So in practice, even with gotos, you will rarely have irreducible graphs and so even without implementing the full phi-node simplification, you will have minimal SSA. In practice, it also won't make a difference because the difference in complexity will only show up if you have a very large number of nodes and in this case you have plenty of other problems to worry about (like memory consumption). >> [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. Thing is that these trivial/redundant phis (as defined in the SSSA article) can also happen when phi-nodes are placed at the DF. They happen naturally in some loops. In the article, when talking about these, they explicitly say "This implies a definition of minimality [that is independent of the source program and] *more strict* than the definition by Cytron et al." So it's pretty clear that even with minimal SSA (Cytron's minimality) you can have those redundant phis. In other words, if you eliminate all redundant phi-nodes as described in SSSA not only you will not have more phi-nodes than Cytron but you *can*, in some case, have less! Anyway, the advantages of the SSSA is not here. -- 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
