[llvm-dev] Writing loop transformations on the right representation is more productive

Tue Jan 14 20:39:13 PST 2020

Am Sa., 11. Jan. 2020 um 07:43 Uhr schrieb Renato Golin <rengolin at gmail.com
>:
> On Sat, 11 Jan 2020 at 00:34, Michael Kruse <llvmdev at meinersbur.de> wrote:
> > Yes, as mentioned in the Q&A. Unfortunately VPlan is able to represent
> > arbitrary code not has cheap copies.
>
> Orthogonal, but we should also be looking into implementing the cheap
> copies in VPlan if we want to search for composable plans.

VPlan structures have many references to neighboring structures such as
parents and use-def chains. This makes adding cheap copies as an
afterthought really hard.

> > This conversion is a possibility and certainly not the main motivation
> > for a loop hierarchy.
>
> I know. There are many things that can be done with what you propose,
> but we should focus on what's the main motivation.
>
> From what I can tell, the tree representation is a concrete proposal
> for the many year discussion about parallel IR.

As I recall, the Parallel IR approaches were trying to add parallel
constructs to the existing LLVM-IR. This added the issue that the current
infrastructure suddenly need to handle those as well, becoming a major
problem for adoption.

> The short paper doesn't mention that, nor it discusses other
> opportunities to fix pipeline complexity (that is inherent of any
> compiler).
>
> I still believe that many of the techniques you propose are meaningful
> ways to solve them, but creating another IR will invariably create
> some adoption barriers.

I see it as an advantage in respect of adoption: It can be switched on and
off without affecting other parts.

> > Are you arguing against code versioning? It is already done today by
> > multiple passes such as LoopVersioningLICM, LoopDistribute,
> > LoopUnrollAndJam and LoopVectorize. The proposal explicitly tries to
> > avoid code bloat by having just one fallback copy. Runtime conditions
> > can be chosen more or less optimistically, but I don't see how this
> > should be an argument for all kinds of versioning.
>
> No. I'm cautious to the combination of heuristics search and
> versioning, especially when the conditions are runtime based. It may
> be hard to CSE them later.
>
> The paths found may not be the most optimal in terms of intermediate
states.

Versioning is always a trade-off between how likely the preconditions apply
and code size (and maybe how expensive the runtime checks are). IMHO this
concern is separate from how code versioning is implemented.

> > > Don't get me wrong, I like the idea, it's a cool experiment using some
> > > cool data structures and algorithms. But previous experiences with the
> > > pass manager have, well, not gone smooth in any shape or form.
> >
> > What experiments? I don't see a problem if the pass manger has to
> > invalidate analysis are re-run canonicalization passes. This happens
> > many times in the default pass pipelines. In addition, this
> > invalidation is only necessary if the loop optimization pass optimizes
> > something, in which case the additional cost should be justified.
>
> My point goes back to doing that in VPlan, then tree. The more
> back-and-forth IR transformations we add to the pipeline, the more
> brittle it will be.

Agreed, but IMHO this is the price to pay for better loop optimizations.

> The original email also proposes, for the future, to do all sorts of
> analyses and transformations in the tree representation, and that will
> likely be incompatible with (or at least not propagated through) the
> conversions.

Correct, but I'd argue these are different kinds of analyses not
necessarily even useful for different representations. MLIR also has its
set of analyses separate to those on MLIR.

> > In a previous RFC [8] I tried to NOT introduce a data structure but to
> > re-use LLVM-IR. The only discussion there was about the RFC, was about
> > not to 'abuse' the LLVM-IR.
> >
> > https://lists.llvm.org/pipermail/llvm-dev/2017-October/118169.html
> > https://lists.llvm.org/pipermail/llvm-dev/2017-October/118258.html
> >
> > I definitely see the merits of using fewer data structures, but it is
> > also hard to re-use something existing for a different purpose (in
> > this case: VPlan) without making both more complex.
>
> My point about avoiding more structures and IRs was related to VPlan
> and MLIR, not LLVM-IR.
>
> I agree there should be an abstraction layer to do parallelisation
> analysis, but we already have two, and I'd rather add many of your
> good proposals on those than create a third.
>
> Perhaps it's not clear how we could do that now, but we should at
> least try to weigh the options.
>
> I'd seriously look at adding a tree-like annotation as an MLIR
> dialect, and use it for lean copies.

Like VPlan, MLIR is a representation with many references between objects
from different levels. I do not see how to add cheap copies as an
afterthought.

> > For the foreseeable future, Clang will generate LLVM-IR, but our
> > motivation is to (also) optimize C/C++ code. That is, I do not see a
> > way to not (also) handle LLVM-IR until Clang is changed to generate
> > MLIR (which then again will be another data struture in the system).
>
> Even if/when Clang generates MLIR, there's no guarantee the high-level
> dialects will be preserved until the vectorisation pass.

I'd put loop optimizations earlier into the pipeline than vectorization.
Where exactly is a phase ordering problem. I'd want to at least preserve
multi-dimensional subscripts. Fortunately MemRef is a core MLIR construct
and unlikely to be lowered before lowering to another representation
(likely LLVM-IR).

> And other
> front-ends may not generate the same quality of annotations.
> We may have to re-generate what we need anyway, so no point in waiting
> all the front-ends to do what we need as well as all the previous
> passes to guarantee to keep it.

I don't see how this is relevant for a Clang-based pipeline. Other
languages likely need a different pipeline than one intended for C/C++ code.

There are not a lot of high-level semantics required to be preserved to
build a loop hierarchy.

Thanks for the productive discussion,
Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200114/a658d69e/attachment.html>