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

Renato Golin via llvm-dev
2020-01-13T09:51:42Z

On Mon, 13 Jan 2020 at 06:07, Chris Lattner via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Overall, I think that this discussion would be easier to process if we
broke it into a few pieces.  There seems to be consensus that LLVM IR (as is) is
not the right representation for aggressive loop transformations.  If we don’t
have consensus on this, then I’d make sure to start there.

>From all meetings we had about parallelism representations in IR over
the past few dev meetings, this was pretty much the only agreement. :)

We couldn't find a clear way to represent most parallel concepts in IR
(without breaking the others), but there wasn't a single format on top
of LLVM IR that we could all agree on.


> If you propose introducing a brand new data structure, please expect me to
push back on that pretty hard.  This is a perfect application of MLIR, and using
it provides a lot of value (including amazing testing tools, round-tripping,
location tracking, etc) which would otherwise would have to be reinvented, and
doesn’t not dictate the IR structure otherwise.  MLIR absolutely supports nested
loop structures etc, as is seen in the affine dialect.

Today, I believe MLIR can serve that purpose, with (possibly)
overlapping dialects, and have cheap copies.

Cheap copies are required for heuristic searches, which have at least
polynomial compute/memory cost, but sometimes exponential.

Copying the whole module N^2 times (N = some pre-defined large budget)
won't work, that's why overlays (like the red/green tree idea) are
needed.

Journaling and snap-shooting are also possible ways to make memory
almost constant (and not exploding compute), and that should be
possible with MLIR dialects, I think.


> Once you have the data structure and the dialect within it decided, you
have the set of transformations.  Again, you’ve given a lot of thought to this,
and that all sounds great to me, but the priorities can be driven by whoever
wants to contribute and what concrete problems they have to solve.

If we don't have a generic enough representation, early designs will
change how later ones will be implemented.

That's why I think MLIR would be the right choice, as it's much more
flexible and composable.

cheers,
--renato