[LLVMdev] Why should we have the LoopPass and LoopPassManager? Can we get rid of this complexity?

[Andrew Trick]

On Jan 22, 2014, at 12:05 AM, Chandler Carruth <chandlerc at gmail.com> wrote:

> As came up recently in other threads, loop passes really get in the way. Here are some of the ways:
> 
> - There is only one Loop analysis pass - IVUsers. It seems unlikely that the loop nest walk is critical to computing this or preserving it.

IVUsers is only used by LSR, and would make more sense as an LSR utility IMO.

> - Almost all of the things we think of as "required" and dependencies are actually *transforms* that canonicalize the form of a loop into particular shapes.
> 
> - Because LoopPasses are nested inside of some other pass manager, we can't compute function analyses after transforming loops with LoopSimplify and/or LCSSA, and have these analyses available to other LoopPasses such as the vectorizer and unroller.
> 
> - LoopPasses don't obey the typical "rules" of a pass over a narrow chunk of IR: they routinely access and modify IR outside of the loop.
> 
> 
> There appear to be two chunks of "functionality" provided by loop passes:
> 
> 1) A worklist of loops to process. This is very rarely used:
> 1.1) LoopSimplify and LoopUnswitch add loops to the queue.

I’m making this up without much thought, but we may benefit from iterative loop transforms like Rotate -> LICM -> Unswitch -> Rotate -> LICM. We might need to come up with a preferred alternative: we can either continue to convert transforms into a utilities, or we can invent new pass manager tricks. e.g. iterate over a set of function passes or selectively run a pass on “dirty” regions.

> 1.2) LoopExtractor, LoopDeletion, and LoopUnroll delete loops from the queue (but "no-op" would likely be correct if we didn't have the loop pass manager).

I think the LoopPassManager is historically just a source of bugs in this respect.

> 2) LoopUnswitch and the pass itself use some hooks to update analyses. This is only actually leveraged by LICM though to update the AliasSetTracker
> 
> 
> These don't seem like very serious use cases, and the cost is insanely high. Can we get rid of it?

Traditionally, compilers sometimes apply a pipeline of transforms on the loop tree bottom up, or only on inner loops to avoid recomputing a global analysis like DomTree between each of the transforms (you can locally invalidate some analysis but still safely use it for other loops). This is obviously tricky and would best handled within a single Function pass if anyone did want to do it. So it’s not a good reason to have a LoopPassManager.

I agree that the LoopPassManager cost is very high because it’s something that needs to be worked around almost every time someone wants to improve the pass pipeline.

-Andy