[LLVMdev] Irreducible Control-Flow & Loops

[Dan Gohman]

On Sep 28, 2009, at 2:28 AM, Ralf Karrenberg wrote:

> Hello everybody,
>
> I just started implementing a part of my algorithm that deals with
> irreducible control-flow.
> Apparently, the LoopInfo analysis does not recognize loops with  
> multiple
> incoming edges (as of LLVM 2.5).
> On the mailing list archives I found a few discussions related to
> irreducible control-flow, but it was never mentioned if it is  
> planned to
> enhance LoopInfo to also represent such loops. It seems like people
> rather implement a conversion from irreducible to reducible control- 
> flow
> instead.

The discussions I've seen have been motivated by backends which
require reducible control-flow in order to function.  Here, it's  
necessary
to convert the code.  I don't know what work has been done though.

>
> I am considering writing a patch for LoopInfo instead of creating my  
> own
> data structure for irreducible loops.
> Is such an enhancement desired or even already implemented by someone
> (e.g. in the 2.6 branch)?

Currently the way things work is that LoopInfo ignores loops that
have multiple entries, and then loop-oriented optimization passes
never visit them.  For most users, multiple-entry loops are rare
enough that this is a reasonable approach.

Current loop-oriented analysis and transformation passes can assume
that anything with a Loop object has a header, which is a unique
entry-point to the loop.  All these clients could be updated if needed,
but it'd be good to have a good reason for it first.

>
> I would also appreciate any additional pointers on how to best  
> represent
> such control-flow.

It depends on what you're doing.

Dan