[LLVMdev] Eliminating gotos

[Eli Friedman]

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