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
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 > 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
On Sep 28, 2009, at 2:28 AM, Ralf Karrenberg 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. 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