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

[Renato Golin via llvm-dev]

On Tue, 21 Jan 2020 at 23:54, Michael Kruse <llvmdev at meinersbur.de> wrote:
> Am Mi., 15. Jan. 2020 um 03:30 Uhr schrieb Renato Golin <rengolin at gmail.com>:
> > > I see it as an advantage in respect of adoption: It can be switched on and off without affecting other parts.
> >
> > That's not necessarily true.
>
> This applies literally to any pass.

Precisely why I don't think adding more passes is an advantage to adoption. :)


> I don't find the argument "there might be bugs" very convincing.

Sorry, it wasn't an argument, just a jest at the expense of some old
commercial front-ends.

Pass ordering is complex no matter how you slice it.


> This was relevant to the discussion that /all/ front-ends would have
> to generate good-enough annotations for loop transformations. Only the
> ones that do might enable loop optimization passes.

This doesn't scale. You end up with a few metadata from a single
front-end justifying a huge new pass that does a few things in even
fewer cases.

VPlan is still crawling, requiring small incremental improvements,
because we're trying to replace an existing pass.

Your proposal is a new pass, that does some new things and therefore
shouldn't need to be incremental (only when the correct info is
present).

But that means now we have two loop transformation infrastructures
that could radically change the IR (and the loop metadata, if any).

Which one passes first will have the advantage, as I think we agreed,
pass ordering is not trivial.

If you restrict this new pass to only doing transformations that are
guaranteed to be valid and better (for some definition of both), then
you'll end like Polly that does wonders to a very small selection of
loops and nothing at all to most of them, just wasted time looking at
all the possibilities.

If you want to be more aggressive, then the IR will change more often
and the pass ordering problem gets worse, requiring changes in later
passes to cope with the changes.

For better or worse, we already have such a pass, the VPlan
infrastructure. It might not be perfect, but it's the path we took
years ago and I'd strongly encourage people to make it better before
throwing it away and coming up with a completely new idea.

VPlan is a simple idea, to represent loops in a more meaningful way,
to represent transformations in a composable way, and to find a
sequence of transforms that would yield the best result.

To me, your proposal is identical in its meaning, but has different
implementation details:
 * Tree instead of VPobjects, with additional benefits for new cases.
 * Heuristics search of transforms wih cheap state copies.

To me, it sounds like we could do both in VPlan, and even call it
LTPlan (Loop Transformation plan) to make it clear it's more generic
than just SIMD vectorisation.

More importantly, it would be a series of incremental steps towards a
better loop infrastructure, building on the work of the last many
years and likely show real benefits much sooner and with a lot less
conflicts than starting from scratch.

--renato