[LLVMdev] Irreducible Control-Flow & Loops
gohman at apple.com
Mon Sep 28 09:21:07 PDT 2009
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
> 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-
The discussions I've seen have been motivated by backends which
require reducible control-flow in order to function. Here, it's
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
> 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
> such control-flow.
It depends on what you're doing.
More information about the llvm-dev