Irreducible Control-Flow & Loops

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.

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 would also appreciate any additional pointers on how to best represent
such control-flow.

Regards,
Ralf

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

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. We already have SCC iterators etc, is there a specific reason you want to have LoopInfo do this?

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.

-Chris

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

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