[LLVMdev] Irreducible Control-Flow & Loops

[Chris Lattner]

On Sep 29, 2009, at 12:29 AM, Ralf Karrenberg wrote:

> Hey,
>
> Thank you for your replies, Chris and Dan.
>
> Chris Lattner wrote:
>>> 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)?
>> I'm not sure that this is a good idea. LoopInfo is clearly defined to
>> represent "natural" loops (where the header dominates the body of the
>> loop). Natural loops have a lot of very useful properties like loop
>> headers etc that the loop optimizers depend on.
> This makes perfect sense of course.
>> We already have SCC iterators etc, is there a specific reason you  
>> want
>> to have LoopInfo do this?
> No, this was just the first idea to incorporate my code directly  
> into LLVM.
>> If you're writing a pass that converts irreducible control flow to
>> reducible loops, I'd think it would be based on SCC iterators, not on
>> LoopInfo.
> No, supporting irreducible control-flow is just a feature of my
> transformation.
>
> I need a lot of information about loops: all headers/preheaders/ 
> latches,
> nesting levels, which blocks are part of what level of which loop etc.
> LoopInfo gives me everything I need for the reducible case, but I  
> agree
> that it is not very convenient to make it more complicated for rather
> uncommon cases.

Right.  I don't think these even make sense for irreducible loops,  
they very much hang on the definition of a reducible loop.

>
> I think I will implement an independent "IrreducibleLoopInfo" pass  
> that
> discovers loops in the presence of multiple entries and offers an
> interface similar to LoopInfo (iterators, getHeaders(),  
> getLoopFor(), ...).

I think the best way to handle this is to write a pass that converts  
irreducible control flow to reducible loops.  This is fairly straight  
forward (through code duplication).  That way your "interesting" pass  
can just use loopinfo.

> A question that is related: do the available SCC iterators provide
> nested SCCs as well or do I have to compute them manually?

There is no such thing as a nested SCC :).  An SCC is where every node  
in the scc can reach every other node.  There is no priority  
associated with any of the nodes in an SCC.

-Chris