[llvm-dev] CFG SCCs vs Loops and loop breaking transformations

[Philip Reames via llvm-dev]

I ran across an interesting case and wanted to share it.  I'm not 
proposing any particular changes, but the experience seemed interesting 
to discuss.

First, a bit of background.  An LLVM Loop models a specific type of 
cycle in the CFG.  Not all cycles are Loops.  Many of our optimization 
transforms are phrased over loops, which means that a non-loop cycle 
tends to be less well optimized.

I had some initial IR that had a very complex, oddly written loop. After 
running this through my pass order, I discovered that there was no 
longer a Loop representing the loop.  One of the transforms - 
SimplifyCFG is my guess, but I haven't confirmed - had taken something 
representable as a Loop and converted into a non-Loop SCC.  This seems 
unfortunate and raises a general issue with how we model and 
canonicalize loops.

Long term, I see a couple of options:
1) Introduce a new notion for SCCs in the CFG, and rephrase select 
optimizations like LICM over them.  A Loop then becomes a particular 
special case of our more generic SCC concept.
2) Avoid breaking loops until some point late in the optimizer. 
Essentially, we designate the Loop representable form as being canonical 
and then lower later.
3) Introduce a SCC to Loop conversion pass which tries to take non-loop 
SCCs and make them representable as Loops.  We probably don't want to go 
full out here, but catching the "easy" cases might help a lot in 
practice.  Running this at the start of each LoopPassManager pipeline 
might be an option.  I was slightly surprised to notice we didn't 
already have this.

None of these seem great.  Anyone have another idea on how we could 
approach this?

Philip

p.s. Thankfully, the code I noticed this in is not performance sensitive 
so I don't need a near term answer here.