[LLVMdev] Eliminating gotos

[Mon P Wang]

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