I have spend some time reading the paper http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf "Simple and Efficient SSA Construction". Which is luc's SSA conversion is based on: Here is some random thoughts about the paper I might just share with you guys. If I make a mistake some where along the line, I am very glad if some one can point it out to me. - I think the main point of the paper doing SSA without the CFG is not particular useful to us. We need to generate CFG *anyway*. - The "Simple and Efficient" part has obvious limitation on reducible graph. Once go over the fence of irreducible graph, the solution is no longer simple nor efficient. For irreducible graph it do need the CFG. That means the CFG is actuall unavoidable consider source can have irreducible graph. - It is actually not fair to compare the fast and simple part with Cytron et al because - Cytron etc al can handle irreducible graph without extra complication. - For reducible graph, Cytron el has fast way to do it as well. "A Simple, Fast Dominance Algorithm" can find dominator for reducible graph in O(N). Once having the dominator tree, finding DF and inserting phi node is very straight forward. - For handling irreducible graph, the "Simple" paper need to do extra steps to clean up unneeded phi nodes. which runs on O(P + B ·(B + E)· V*V), so basiclly O(B*B*V*V) I think that is worse than Cytron's method. Because sparse need to handle irreducible graph. The worse case behavior need to be considered. BTW that is I think why the paper don't discuss handle of "goto" statement. "goto" can lead to irreducible graph. - We might have a way to tell if function contain goto before linearized the function. - Cytron might still be worthwhile to implement due to the better worse case complexity. 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
