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>
On Thursday 14 August 2008 16:55, Benedict Gaster wrote:> 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?Oh, absolutely. Simply implementing short-circuited evaluation efficiently can do that. Not to mention optimization passes massively restructuring the code in unique and unintelligible ways. My favorite optimization moment came when someone here was searching for a user message to output after he implemented some fancy tricks. His first suggestion was, "The loop at line X was vectorized beyond your comprehension." :) -Dave
On Thu, Aug 14, 2008 at 2:55 PM, Benedict Gaster <benedict.gaster at amd.com> wrote:> 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.Yes, at least some passes can; the most obvious example is jump threading, but there are quite a few other passes that could blast apart the structure in non-obvious ways. You do have control over which passes you run, so it's possible to avoid passes that modify the CFG; however, that excludes a lot of useful passes, like SimplifyCFG and a lot of the loop passes. I would suggest an approach that uses something like the pattern matcher like you're suggesting plus a transformation that enforces the necessary structure restrictions; that should allow you to test conversion both ways immediately and give you the most flexibility in how to use the various LLVM transformation passes. The only downside is the difficultly of writing the structuring pass; I have a feeling it'll be tricky to do effectively. Oh, and depending on how much you trust the compiler you're outputting to, you can use the Reg2Mem pass for PHI elimination; it's really simplistic relative to a real PHI elimination pass, but it might not matter since you're not actually outputting machine code. -Eli
Hi, I like Eli approach here. Phases like SimplifyCFG and various loop transformations are just to useful to cleanup code and generate much high quality output. If we look at the passes, I hope we might be able to quantify what changes they make. My hope is that since the incoming graph is reducible that it doesn't cost that much after running these phases to make them reducible again. Eli's approach reminds me of some loop transformations techniques where one compute a matrix of legal transformations, try them, and then potentially undo them if they are not profitable. In this case, I don't think we want to go this far but it is a nice model to use as it allows us to leverage as much as possible of LLVM phases to cleanup the code. -- Mon Ping On Aug 14, 2008, at 7:07 PM, Eli Friedman wrote:> On Thu, Aug 14, 2008 at 2:55 PM, Benedict Gaster > <benedict.gaster at amd.com> wrote: >> 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. > > Yes, at least some passes can; the most obvious example is jump > threading, but there are quite a few other passes that could blast > apart the structure in non-obvious ways. You do have control over > which passes you run, so it's possible to avoid passes that modify the > CFG; however, that excludes a lot of useful passes, like SimplifyCFG > and a lot of the loop passes. > > I would suggest an approach that uses something like the pattern > matcher like you're suggesting plus a transformation that enforces the > necessary structure restrictions; that should allow you to test > conversion both ways immediately and give you the most flexibility in > how to use the various LLVM transformation passes. The only downside > is the difficultly of writing the structuring pass; I have a feeling > it'll be tricky to do effectively. > > Oh, and depending on how much you trust the compiler you're outputting > to, you can use the Reg2Mem pass for PHI elimination; it's really > simplistic relative to a real PHI elimination pass, but it might not > matter since you're not actually outputting machine code. > > -Eli > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev