[LLVMdev] Eliminating gotos

[Benedict Gaster]

Hi Mon Ping,

Yes I like Eli's approach also.

I was thinking that maybe the approach is to implement the pattern matching
algorithm and in the case when not all gotos have been eliminated, in
particular when a sub-component of the graph is irreducible, apply the more
general transformation to the output. This has the benefit of avoiding
applications of Erosa's (more costly) algorithm to the whole graph but
allows its use when absolutely necessary. Of course, it does mean having to
implement both algorithms but in practice neither are that complicated and
so (hopefully) should not take to much effort.

Ben


On 15/08/2008 18:34, "Mon P Wang" <monping at apple.com> wrote:

> 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
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>