<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>
<BR>
Discussing this with others in AMD it came up if it is possible for LLVM to take a program that has a reducible graph (any C code without goto/setjmp) and generate one that is irreducible? If it is the case that the code is actually structured coming in, a simple pattern matcher could turn everything into if/endif and so on. <BR>
<BR>
Ben<BR>
<BR>
On 14/08/2008 18:39, "Mon P Wang" <<a href="wangmp@apple.com">wangmp@apple.com</a>> wrote:<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Hi Ben,<BR>
<BR>
<BR>
On Aug 12, 2008, at 11:36 AM, Benedict Gaster wrote:<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'> Hi Owen,<BR>
<BR>
On 12/08/2008 16:52, "Owen Anderson" <<a href="resistor@mac.com">resistor@mac.com</a>> wrote:<BR>
<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
SNIP<BR>
<BR>
<BR>
I'm still not seeing how these two are any different. You just replace the text of "if" with "br", and add the explicit target labels. I should also point out that, in LLVM IR, the order the blocks are laid out in is not meaningful and could change, so representing them explicitly in the branch or "if" is a requirement. Also, this ordering (and, indeed, the number and structure of basic blocks) is not guaranteed to be preserved into the Machine-level phase of code generation.<BR>
<BR>
What I'm guessing you're getting at is that you need is to insert an end-if instruction at some point. If this is the case, I don't think radically changing the LLVM IR is the path of least resistance. What about having a Machine-level pass that enforces the ordering of blocks that you require and inserts the special instructions based on a high-level control flow reconstruction? At the Machine-level, blocks are allowed to have multiple exits, so you could even implement the non-optimized case you gave first. Also, loop-structure analysis is available at the Machine level as well, which might help.<BR>
<BR>
<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>
-- 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>