[LLVMdev] Irreducible Control-Flow & Loops

[Ralf Karrenberg]

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.

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(), ...).

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

Regards,
Ralf