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

[Mark Lacey via llvm-dev]

> On Jan 19, 2016, at 11:17 AM, Philip Reames via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 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?

It seems like a good idea to track down and understand exactly what is happening here before discussion options. It is entirely possible that the right answer here would be to modify the transformation that is resulting in cycles that are not recognized as loops so that it no longer does so (or alternatively as you say in #2, postpone any transformation that can do this until as late as possible).

Mark