[LLVMdev] Eliminating gotos
benedict.gaster at amd.com
Thu Aug 14 14:55:06 PDT 2008
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.
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:
>>> 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 ).
> -- Mon Ping
>  Folklore confirmed: reducible flow graphs are exponentially larger
> Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev