[LLVMdev] Irreducible Control-Flow & Loops

Chris Lattner clattner at apple.com
Tue Sep 29 18:31:34 PDT 2009

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.


More information about the llvm-dev mailing list