On Wed, Aug 16, 2017 at 8:24 AM, Dibyendu Majumdar <mobile@xxxxxxxxxxxxxxx> wrote: > > The paper says that the algorithm creates correct SSA for all > programs. Specifically quoting: > > <quote> > prove that the SSA construction algorithm constructs pruned SSA form > for all programs and minimal SSA form for programs with reducible > control flow > <endquote> > > Secondly even for irreducible control flow, it provides an algorithm > for creating minimal SSA in section 3.2, right? It do provide a solution. and the price is high. The complexity is O(B*B*V*V). Go look at page 15 of the paper. > > Luc's implementation seems to work fine with gotos? Have you tested > Luc's implementation? I think it is better to try out the solution and > see if there is a problem. I haven't, as I said I try to finish reading the paper before looking that the implementation. If Luc is the paper suggestion to fix up the irreducible case. , then we are down the road for O(B*B*V*V) complexity. >>> The great thing about Sparse I find is that it is smaller and simpler >>> than gcc or clang - and I would urge that this should be maintained. >> >> Exactly. I am totally agree with you. My worries are the hidden complexity >> dealing with gotos in that paper. >> > > I am wondering if the complexity is only because Luc's implementation > creates SSA on the fly rather than as a second phase. I posted another > question on that topic. My way of seeing it, the complexity is introduced when you have input source contain irreducible grahy. This paper doe not have good way to deal with it. It can solve it, but that is O(B*B*V*V) complexity. In other words, we can some input source that cause the method describe in this paper quadruple to the size of the input. 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
