[LLVMdev] Eliminating gotos

[Benedict Gaster]

Hi,

Comments inline.

Ben


On 12/08/2008 03:14, "Owen Anderson" <resistor at mac.com> wrote:

>>  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.

What's the difference between an "if" and a conditional branch?

[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
}

We cannot express this as it uses the conditional branch br but applying
goto elimination it is possible to re-write as:

define i32 @foo(i32 %x, i32 %y) {
entry:    
    %tobool    = icmp eq i32 %x, 0

    if i1 %tobool
      %nottobool = icmp eq i1 %tobool, false
      if i1 %notobool
      endif
ifthen:
      %add = add i32 %x, 10
      ret i32 %add
    endif

ifelse:
    %call = tail call i32 (...)* @bar( )
    ret i32 %y
}

Of course, this can be optimized to be:

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

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

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.

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

    if(x) goto L2;
L1: 
    stmt_1;
L2: 
    stmt_2;
    if(y) goto L1;

Using the algorithm described for goto elimination this can be re-written
as:

    goto_L2 = x;
    do {
        if (!goto_L2) {
            goto_L1 = 0;
            stmt_1;
        }
        goto_L2=0;
        stmt_2;
        goto_L1=y;
    } while (goto_L1);

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.
>> --Owen

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