[LLVMdev] Eliminating gotos

[Eli Friedman]

On Mon, Aug 11, 2008 at 2:02 PM, Benedict Gaster
<benedict.gaster at amd.com> wrote:
> ... the problem is how to best represent the resulting IL
> within the LLVM framework:
>
> Extend LLVM with news ops to support if/loop.
> 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.
> Implement some structure of to the side that represents this high-level
> flow.

The way I'd do this is to establish a restricted subset of the LLVM IL
with control flow that the converter can easily deal with, then write
a transformation pass to ensure that the necessary invariants hold.
This approach allows separating the transformation step and the actual
conversion code, which should make developing and debugging them
easier.

Introducing new control-flow constructs into the LLVM IL would require
such massive changes that I don't think it's worth considering.

For the transformation step, requiring reg2mem will probably make
writing the pass a bit easier; if you do that, the pass doesn't have
to deal with PHI nodes.  Also, the functions in
llvm/Transforms/Utils/Cloning.h are likely to be useful.

Being able to run general CFG-modifying LLVM optimization passes on
the transformed code without breaking the invariants would be a pain,
so I don't think it's worth bothering with it.  If it turns out that
you really need some CFG-modifying pass, you can revisit it later.
Non-CFG-modifying passes, like instcombine and GVN, are safe because
they can't break CFG-based invariants.

The alternative would be to delay eliminating gotos until after the
conversion... this might be easier to implement if you're basing your
implementation on the paper you cited.

And another alternative, depending on your language, would be to split
up irreducible chunks into separate functions, essentially turning
gotos into tail calls.

-Eli