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>
> [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.We implemented this in GCC back when we first started GIMPLE (since GIMPLE is based on the IL the authors of that paper used in their compiler), and the code size increases on a bunch of testcases were massive due to extra loop constructs.
Hi, That is interesting. Do you have any pointers to the test cases in question? The problem is that we don't have conditional branches and so we are going to have to do some form of goto elimination and as such do you have any alternatives in mind? Thanks, Ben On 12/08/2008 16:40, "Daniel Berlin" <dberlin at dberlin.org> wrote:>> [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. > > > We implemented this in GCC back when we first started GIMPLE (since > GIMPLE is based on the IL the authors of that paper used in their > compiler), and the code size increases on a bunch of testcases were > massive due to extra loop constructs. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
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>
Hi Owen, On 12/08/2008 16:52, "Owen Anderson" <resistor at mac.com> wrote:> > SNIP > > > 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. >[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?> > 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. > >>> 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. >>> 5. >>> >>> 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 > > Actually I was thinking something along the following lines: > > OpenCL -> LLVM IR > 2 SSA (mem2reg) > LLVM optimizations > 2 !SSA (phi2copy) > Goto elimination with intrinsicsCode gen (without register allocation and so on)> > Where the goto elimination pass would generate something like: > > define i32 @foo(i32 %x, i32 %y) { > entry: > %tobool = icmp eq i32 %x, 0 > > %dummy1 = call i1 %if i1 %tobool > %add = add i32 %x, 10 > ret i32 %add > call void %endif i1 %dummy1 > > %call = tail call i32 (...)* @bar( ) > ret i32 %y > } > > I¹m not sure all this makes sense rather I¹m just thinking about the options > and trying to develop a whole picture. > > Ben > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080812/78e8a17b/attachment.html>