[LLVMdev] Eliminating gotos

[Owen Anderson]

On Aug 12, 2008, at 2:39 AM, Benedict Gaster wrote:
> [bg] Consider the LLVM code:
>
> define i32 @foo(i32 %x, i32 %y) {
> entry:
>     %tobool = icmp eq i32 %x, 0        ; <i1> [#uses=1]
>     br i1 %tobool, label %ifelse, label %ifthen
>
> ifthen:        ; preds = %entry
>     %add = add i32 %x, 10        ; <i32> [#uses=1]
>     ret i32 %add
>
> ifelse:        ; preds = %entry
>     %call = tail call i32 (...)* @bar( )        ; <i32> [#uses=0]
>     ret i32 %y
> }

SNIP

> define i32 @foo(i32 %x, i32 %y) {
> entry:
>     %tobool    = icmp eq i32 %x, 0
>
>     if i1 %tobool
> ifthen:
>       %add = add i32 %x, 10
>       ret i32 %add
>     endif
>
> ifelse:
>     %call = tail call i32 (...)* @bar( )
>     ret i32 %y
> }
>

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.

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.

Seems like a lot simpler than massively altering the IR.

> 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 :-)!
>

I'm still not understanding your point here.  Even if LLVM spells it  
as "br", your target isel can match it to something spelled "if" with  
no problem.  See my suggestions above about inserting other special  
instructions and enforcing block ordering above.

>> Extend LLVM with news ops to support if/loop.
>> 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.
>> Implement some structure of to the side that represents this high- 
>> level flow.
>>
>>
>>  Thoughts?

I missed pointing this one out earlier, but you won't be able to do  
this with intrinsics, as block labels cannot be used as first class  
values, and so cannot be passed to a function call.  You'd actually  
have to add instructions to the IR, or come up with a string-based  
tagging scheme or something


--Owen

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080812/8427320c/attachment.html>