Hi Chris, On 16 August 2017 at 13:09, Christopher Li <sparse@xxxxxxxxxxx> wrote: > On Wed, Aug 16, 2017 at 5:55 AM, Dibyendu Majumdar > <mobile@xxxxxxxxxxxxxxx> wrote: >> I would argue that the simplest possible solution is what we should >> start with. The solution implemented based on this paper appears to be >> simple and elegant - and if this works correctly then why go for more >> complicated solutions? Theoretical scenarios are not very useful - in > > Because the paper "simple and elegant" only cover the reducible > graph case. When you considering the irreducible graph source file > input, say having "goto", all the sudden it is not simple and elegant > any more. It is more like complex and ad-hoc. > 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? >> my view, if the solution works now with all known inputs then it is >> good enough. > > Know input include "goto", period. > 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. >>> >>> - Cytron might still be worthwhile to implement due to the better >>> worse case complexity. >>> >>> >> >> Certainly you should prototype this - even if just to compare. But I >> would suggest - lets merge the solution we have now. Additional >> solutions are always good to have. > > Yes, I am doing the prototype as the side project. I start with building > the dominator tree as I mention in the list earlier. Another way to > evaluate the complexity of the code, just go take a look at the Clang, > how it promote the memory access into SSA pesudo. That is the > critical piece we are talking about here. It is actually not that complex > at all. > > To fully evaluate the complexity suggest by this paper. I want to see > the full implementations with "gotos". > In my tests Luc's implementation works fine with gotos. I have not tested computed gotos, however. Yet the solution is simple and elegant. > >> 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. Regards Dibyendu -- 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
