<HTML>
<HEAD>
<TITLE>Re: [LLVMdev] Eliminating gotos</TITLE>
</HEAD>
<BODY>
<FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Hi Mon Ping,<BR>
</SPAN></FONT><BLOCKQUOTE><BLOCKQUOTE><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'> <BR>
</SPAN></FONT></BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>[bg] Ok so I think I’m starting to get it. You are correct in your assertion that we need to insert the end-if instruction at some point and of course else in the case of if-then-else constructs. But we also need to reconstruct while-loops and it is unclear to me if you approach works for all cases of gotos. The other concern here is that as we are targeting an instruction set with virtual registers and register allocation and scheduling will be performed by our assembler not within LLVM and so we are planning on implementing a language style backend, similar in style to the MSIL backend, and as such it is possible to use a machine-level pass? <BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><FONT COLOR="#006312"><SPAN STYLE='font-size:11.5pt'>[ Deleted Text]<BR>
</SPAN></FONT></FONT></BLOCKQUOTE></BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
I don't see why not as you have only a different target. Assuming the incoming graph doesn't have improper intervals, I would think that Owen's approach to have a structural fixup machine level pass to run over the CFG seems to be the right way to go. I assume that the requirement is to end up with structured control flow and its not required (though it might be desirable) that the incoming source graph is preserved. If the incoming code have improper intervals, I think we could reconstruct it but as other people indicated, the CFG could be quite a bit larger (see [1]).<BR>
<BR>
</SPAN></FONT></BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>[bg] I’ve been thinking about this some more and was thinking of implementing some along the following lines:<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
</SPAN></FONT></BLOCKQUOTE><UL><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>translate into machine-level SSA representation;
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>do phi removal (as we have virtual register set conventional register allocation is not important for us; this happens much later down the tool flow); I was initially planning to do phi removal as described in [1] but it has been pointed out to me that this is not correct in all cases and so now plan to implement the algorithm given in [2].
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>do high-level control flow reconstruction
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>insert if-then-else-endif/while-endwhile blocks
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>finish code generation<BR>
</SPAN></FONT></UL><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
Does this make sense?<BR>
<BR>
I agree that it in general conversion of irreducible graphs could be expensive but in our case gotos are not allowed in the original source, break and continue are supported in the target language, and so this implies that we should, in theory, be reconstructing the high-level source that was originally compiled.<BR>
<BR>
[1] Efficiently computing static single assignment form and control dependence graph, Cytron, et. al., 1991. <BR>
[2] P</SPAN></FONT><FONT COLOR="#00007F"><FONT SIZE="2"><FONT FACE="Arial"><SPAN STYLE='font-size:10pt'>ractical Improvements to the Construction and Destruction of Static Single Assignment Form, Briggs, et. al., 1997<BR>
</SPAN></FONT></FONT></FONT><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
Regards,<BR>
<BR>
Ben<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'> -- Mon Ping<BR>
</SPAN></FONT><SPAN STYLE='font-size:11pt'><FONT FACE="Arial"><BR>
<BR>
<B>[1] Folklore confirmed: reducible flow graphs are exponentially larger<BR>
</B></FONT><FONT FACE="Verdana, Helvetica, Arial">Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages<BR>
</FONT><FONT FACE="Calibri, Verdana, Helvetica, Arial"><BR>
<HR ALIGN=CENTER SIZE="3" WIDTH="95%"></FONT></SPAN><FONT SIZE="2"><FONT FACE="Consolas, Courier New, Courier"><SPAN STYLE='font-size:10pt'>_______________________________________________<BR>
LLVM Developers mailing list<BR>
<a href="LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><BR>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><BR>
</SPAN></FONT></FONT></BLOCKQUOTE>
</BODY>
</HTML>