llvm dev - Jan 2014 - [LLVMdev] Why should we have the LoopPass and LoopPassManager? Can we get rid of this complexity?

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.

- 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.
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).

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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140122/ef52e5e9/attachment.html>

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

On Wed, Jan 22, 2014 at 12:33 AM, Andrew Trick <atrick at apple.com>
wrote:
> > 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.

This is a really good point. Owen pointed it out to me as well in another
guise: when we unroll a loop, we need to re-run a bunch of the passes, but
re-running them when we *haven't* successfully unrolled a loop is a total
waste.

I'd like to think more about this, so a simpler option: what if we *just*
extract LoopSimplify and LCSSA? If all the LoopPasses preserve these, then
them being function passes would be fine. This would allow us to at least
*start* writing function passes over loops (like the LoopVectorizer) rather
than being forced to phrase them as LoopPasses.

I think I could implement this simpler option right away, and that would
unblock a lot of our efforts around unrolling, vectorizing, and PGO.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140122/93f989ae/attachment.html>