<HTML>
<HEAD>
<TITLE>Re: [LLVMdev] Eliminating gotos</TITLE>
</HEAD>
<BODY>
<FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Hi,<BR>
<BR>
Comments inline.<BR>
<BR>
Ben<BR>
<BR>
<BR>
On 12/08/2008 03:14, "Owen Anderson" <<a href="resistor@mac.com">resistor@mac.com</a>> wrote:<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'> We would like to develop a code generator using LLVM for a target language that does not support conditional branches and in fact only supports structured control flow, eg. If and while. <BR>
</SPAN></FONT></BLOCKQUOTE></BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
What's the difference between an "if" and a conditional branch?<BR>
<BR>
[bg] Consider the LLVM code:<BR>
<BR>
define i32 @foo(i32 %x, i32 %y) {<BR>
entry:<BR>
%tobool = icmp eq i32 %x, 0 ; <i1> [#uses=1]<BR>
br i1 %tobool, label %ifelse, label %ifthen<BR>
<BR>
ifthen: ; preds = %entry<BR>
%add = add i32 %x, 10 ; <i32> [#uses=1]<BR>
ret i32 %add<BR>
<BR>
ifelse: ; preds = %entry<BR>
%call = tail call i32 (...)* @bar( ) ; <i32> [#uses=0]<BR>
ret i32 %y<BR>
}<BR>
<BR>
We cannot express this as it uses the conditional branch br but applying goto elimination it is possible to re-write as:<BR>
<BR>
define i32 @foo(i32 %x, i32 %y) {<BR>
entry: <BR>
%tobool = icmp eq i32 %x, 0 <BR>
<BR>
if i1 %tobool<BR>
%nottobool = icmp eq i1 %tobool, false<BR>
if i1 %notobool<BR>
endif<BR>
ifthen:<BR>
%add = add i32 %x, 10<BR>
ret i32 %add<BR>
endif<BR>
<BR>
ifelse:<BR>
%call = tail call i32 (...)* @bar( ) <BR>
ret i32 %y<BR>
}<BR>
<BR>
Of course, this can be optimized to be:<BR>
<BR>
define i32 @foo(i32 %x, i32 %y) {<BR>
entry: <BR>
%tobool = icmp eq i32 %x, 0 <BR>
<BR>
if i1 %tobool<BR>
ifthen:<BR>
%add = add i32 %x, 10<BR>
ret i32 %add<BR>
endif<BR>
<BR>
ifelse:<BR>
%call = tail call i32 (...)* @bar( ) <BR>
ret i32 %y<BR>
}<BR>
<BR>
I agree that in some sense this is an argument over syntax but the issue for us is that our ISA represents control flow using structured ops and so we have no option but to re-write the code into this form or change the hardware :-)!<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>As far as I can tell that the problem with doing this in LLVM today, is that it does not support these high-level constructs and instead all control flow is implemented as branches. <BR>
<BR>
It is “fairly” straightforward to restructure a program written with conditional/unconditional branches into to one that uses completely high-level control flow structures, the algorithm I have in mind is described in [1], the problem is how to best represent the resulting IL within the LLVM framework:<BR>
<BR>
<BR>
</SPAN></FONT><OL><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Extend LLVM with news ops to support if/loop.
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Implement this with the insertion of intrinsics to represent high-level control-flow, introducing “false” dependencies if necessary to allow optimizations to be applied without changing the semantics.
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Implement some structure of to the side that represents this high-level flow.
</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'> <BR>
</SPAN></FONT></OL><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
Thoughts?<BR>
</SPAN></FONT></BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>
One downside of this is that it means eliminating all instances of irreducible control flow, which can lead to an exponential increase in code size.<BR>
<BR>
[bg] Actually this does not need to be the case. The paper that I sighted does not use code replication to resolve irreducible control flow but instead introduces a loop construct. For example, consider the following irreducible loop (taken directly from the paper):<BR>
<BR>
if(x) goto L2;<BR>
L1: <BR>
stmt_1;<BR>
L2: <BR>
stmt_2;<BR>
if(y) goto L1;<BR>
<BR>
Using the algorithm described for goto elimination this can be re-written as:<BR>
<BR>
goto_L2 = x;<BR>
do {<BR>
if (!goto_L2) {<BR>
goto_L1 = 0;<BR>
stmt_1;<BR>
}<BR>
goto_L2=0;<BR>
stmt_2;<BR>
goto_L1=y;<BR>
} while (goto_L1);<BR>
<BR>
In this case there is additional code for condition variables and the loop itself but there is no duplication of stmt_1 or stmt_2.<BR>
</SPAN></FONT><BLOCKQUOTE><BLOCKQUOTE><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>--Owen<BR>
</SPAN></FONT></BLOCKQUOTE></BLOCKQUOTE>
</BODY>
</HTML>