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>
Hi Ben, On Aug 12, 2008, at 11:36 AM, Benedict Gaster wrote:> 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? >> [ Deleted Text]I don't see why not as you have only a different target. Assuming the incoming graph doesn't have improper intervals, I would think that Owen's approach to have a structural fixup machine level pass to run over the CFG seems to be the right way to go. I assume that the requirement is to end up with structured control flow and its not required (though it might be desirable) that the incoming source graph is preserved. If the incoming code have improper intervals, I think we could reconstruct it but as other people indicated, the CFG could be quite a bit larger (see [1]). -- Mon Ping [1] Folklore confirmed: reducible flow graphs are exponentially larger Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080814/a6089de6/attachment.html>
Hi Mon Ping,>>> >> [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? >> >>> [ Deleted Text] > > I don't see why not as you have only a different target. Assuming the > incoming graph doesn't have improper intervals, I would think that Owen's > approach to have a structural fixup machine level pass to run over the CFG > seems to be the right way to go. I assume that the requirement is to end up > with structured control flow and its not required (though it might be > desirable) that the incoming source graph is preserved. If the incoming code > have improper intervals, I think we could reconstruct it but as other people > indicated, the CFG could be quite a bit larger (see [1]). >[bg] I¹ve been thinking about this some more and was thinking of implementing some along the following lines:>* translate into machine-level SSA representation; * do phi removal (as we have virtual register set conventional register allocation is not important for us; this happens much later down the tool flow); I was initially planning to do phi removal as described in [1] but it has been pointed out to me that this is not correct in all cases and so now plan to implement the algorithm given in [2]. * do high-level control flow reconstruction * insert if-then-else-endif/while-endwhile blocks * finish code generation Does this make sense? I agree that it in general conversion of irreducible graphs could be expensive but in our case gotos are not allowed in the original source, break and continue are supported in the target language, and so this implies that we should, in theory, be reconstructing the high-level source that was originally compiled. [1] Efficiently computing static single assignment form and control dependence graph, Cytron, et. al., 1991. [2] Practical Improvements to the Construction and Destruction of Static Single Assignment Form, Briggs, et. al., 1997 Regards, Ben> -- Mon Ping > > > [1] Folklore confirmed: reducible flow graphs are exponentially larger > Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming > Languages > > > _______________________________________________ > 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/20080814/3c4551a9/attachment.html>
Hi Mon Ping, Discussing this with others in AMD it came up if it is possible for LLVM to take a program that has a reducible graph (any C code without goto/setjmp) and generate one that is irreducible? If it is the case that the code is actually structured coming in, a simple pattern matcher could turn everything into if/endif and so on. Ben On 14/08/2008 18:39, "Mon P Wang" <wangmp at apple.com> wrote:> Hi Ben, > > > On Aug 12, 2008, at 11:36 AM, Benedict Gaster wrote: > >> 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? >> >>> [ Deleted Text] > > I don't see why not as you have only a different target. Assuming the > incoming graph doesn't have improper intervals, I would think that Owen's > approach to have a structural fixup machine level pass to run over the CFG > seems to be the right way to go. I assume that the requirement is to end up > with structured control flow and its not required (though it might be > desirable) that the incoming source graph is preserved. If the incoming code > have improper intervals, I think we could reconstruct it but as other people > indicated, the CFG could be quite a bit larger (see [1]). > > -- Mon Ping > > > [1] Folklore confirmed: reducible flow graphs are exponentially larger > Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming > Languages > > > _______________________________________________ > 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/20080814/e6a0bc13/attachment.html>