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. 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.
Thoughts?
Ben
[1] "Taming Control Flow: A structured approach to eliminating goto
statements", A.M. Erosa and L.J. Hedren, ICCL 1994
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080811/562dc304/attachment.html>
On Aug 11, 2008, at 2:02 PM, Benedict Gaster 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?> 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: > > 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?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. --Owen -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080811/4ccf9104/attachment.html>
On Mon, Aug 11, 2008 at 2:02 PM, Benedict Gaster <benedict.gaster at amd.com> wrote:> ... the problem is how to best represent the resulting IL > within the LLVM framework: > > 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.The way I'd do this is to establish a restricted subset of the LLVM IL with control flow that the converter can easily deal with, then write a transformation pass to ensure that the necessary invariants hold. This approach allows separating the transformation step and the actual conversion code, which should make developing and debugging them easier. Introducing new control-flow constructs into the LLVM IL would require such massive changes that I don't think it's worth considering. For the transformation step, requiring reg2mem will probably make writing the pass a bit easier; if you do that, the pass doesn't have to deal with PHI nodes. Also, the functions in llvm/Transforms/Utils/Cloning.h are likely to be useful. Being able to run general CFG-modifying LLVM optimization passes on the transformed code without breaking the invariants would be a pain, so I don't think it's worth bothering with it. If it turns out that you really need some CFG-modifying pass, you can revisit it later. Non-CFG-modifying passes, like instcombine and GVN, are safe because they can't break CFG-based invariants. The alternative would be to delay eliminating gotos until after the conversion... this might be easier to implement if you're basing your implementation on the paper you cited. And another alternative, depending on your language, would be to split up irreducible chunks into separate functions, essentially turning gotos into tail calls. -Eli
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>