[LLVMdev] Eliminating gotos

[Benedict Gaster]

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.

Ben

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:
>>  
>>  
>>> 
>>>  SNIP
>>>  
>>>  
>>>  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 [1]).
> 
>   -- Mon Ping
> 
> 
> [1] Folklore confirmed: reducible flow graphs are exponentially larger
> Proc. of the 30 th ACM SIGPLANSIGACT Symposium on Principles of Programming
> Languages
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080814/e6a0bc13/attachment.html>