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

[Michael Kruse via llvm-dev]

Am Mi., 15. Jan. 2020 um 20:27 Uhr schrieb Chris Lattner <
clattner at nondot.org>:

> One you achieve consensus on data structure, there is the question of what
>> IR to use within it.  I would recommend starting with some combination of
>> “existing LLVM IR operations + high level control flow representation”,
>> e.g. parallel and affine loops.  The key here is that you need to always be
>> able to lower in a simple and predictable way to LLVM IR (this is one of
>> the things that classic polyhedral systems did sub optimally, making it
>> difficult to reason about the cost model of various transformations), and
>> this is a natural incremental starting point anyway.  Over time, more high
>> level concepts can be gradually introduced.  FYI, MLIR already has a
>> reasonable LLVM dialect <https://mlir.llvm.org/docs/Dialects/LLVM/> and
>> can generate LLVM IR from it, so we’d just need an “LLVM IR -> MLIR LLVM
>> dialect” conversion, which should be straightforward to build.
>>
>
> Adding a LLVM-IR -> MLIR -> LLVM-IR round-trip would at the beginning just
> introduce compile-time overhead and what Renato described as brittleness. I
> fear this hurts adaption.
>
>
> Isn’t this true of *any* higher level IR?  Unless I’m missing something
> big, this seems inherent to your proposal.
>

No. A loop hierarchy may be created on-demand and can be skipped if, e.g.,
the function does not contain a loop. For IRs that are translation-unit
based, the entire module will have to do a round-trip whether changed or
not. To improve the situation, one could e.g. add a "has been changed" flag
to each function. But it has to be added somewhere into the MLIR data
structure and kept up-to-date on modifications. In a
loop-hierarchical structure only the node(s) that has been changed needs to
be lowered (e.g. an innermost loop) and versioned with the original IR
depending on taken assumptions.


This is definitely subjective question. I think that MLIR is closer to
> LLVM-IR for how it is processed. Both have a sequence of passes running
> over a single source of truth. Both allow walking the entire structure from
> every instruction/operation/block. Analyses are on function or module
> level. Both have CFGs (I think for a certain kind of transformations it is
> an advantage that control flow is handled implicitly).
>
>
> Right, but a frequent way that MLIR is used is without its CFG: most
> machine learning kernels use nests of loops and ifs, not CFGs.  CFGs are
> exposed when those are lowered out.  See some simple examples like:
>
> https://github.com/llvm/llvm-project/blob/master/mlir/test/Transforms/affine-data-copy.mlir
>
>
I agree that a loop nest can be represented in MLIR. What is missing IMHO
is being able to have multiple versions of the same code. For instance,
raising emitted C++ to such representation to make it more optimizable may
only be possible under preconditions and by itself making the code slower.
If the raised representation cannot be optimized, we will want to use the
original one.


> The possibility to make local changes speculatively without copying the
> entire data structure. IMHO this is a central idea that allows applying a
> transformations speculatively to pass it to a legality check and cost
> heuristic without committing to apply it. As a consequence, passes do not
> need to implement to implement these in a transformation-specific manner,
> drastically reducing the burden of implementation.
>
> For instance, more loop transformations are feasible if instructions are
> moved into the innermost loops. With speculative transformations, we can
> canonicalize the representation to sink computations into loops -- the
> opposite of what LICM does -- and then see whether a transformation can
> applied. If not, the speculative representation is discarded without having
> an effect on the original representation (and not needing to hoist those
> computations again).
>
> Because the MLIR classes have many references to related objects (such as
> pointer to parents and use-def chains), I don't think it is feasible to
> implement on top of MLIR.
>
>
> Ah yes, I see what you mean.  One way to do that is to represent multiple
> options as an op with region for each option.  This means you only fork the
> part of the IR that you’re producing variants of.  I think this is the
> red/green tree technique you mentioned, but I’m not sure.
>
>
The red-green tree technique even allows re-inserting entire unchanged
subtrees (e.g. loop bodies after an interchange). If op takes multiple
regions, each region still must be deep copies.


> An advantage is that
>> loops and multi-dimensional arrays can be represented in the language
>> without the need of being rediscovered, but have to be inserted by a
>> front-end.
>>
>>
>> This is correct, but I don’t see how this helps if your focus is raising
>> code that has already been lowered to LLVM IR, e.g. by Clang or some other
>> frontend that generates LLVM IR today.
>>
>
> Indeed, I would hope that LLVM-IR can preserve multi-dimensional array
> accesses in some fashion as well (
> https://lists.llvm.org/pipermail/llvm-dev/2019-July/134063.html).
> However, currently MLIR has the advantage of being able represent it.
>
>
> I don’t think LLVM IR will ever get there without a massive design
> change.  It is possible that it will support static shaped accesses in
> limited ways though.
>
>
Static sized rectangular multi-dimensional arrays are already possible
using a standard GetElementPtr and its inrange qualifier. For dynamic sized
multi-dimensional sized arrays what is needed is to convey the dimensions
of the array in form of an llvm::Value. In the RFC we discussed an
intrinsic and operand bundles, neither looks like massive design changes to
me.

On the other side, natural loop detection on CFGs is quite mature (with a
> remaining issue of irreducible loops that might appear, but can also be
> eliminated again). As a plus, optimization does depend less on how the
> source code is written.
>
>
> Yep totally.  The question is whether you lose semantic information from
> lowering to a CFG and reconstructing back up.  This can affect you when you
> have higher level language semantics (e.g. Fortran parallel loops, openmp
> or other concurrency constructs etc).  This is where MLIR excels of course.
>
>
Indeed it is easier to not lower these constructs, but not impossible (as
shown in https://reviews.llvm.org/D69930). I think the relevant difference
is that these constructs come with additional guarantees (e.g.
Single-Entry-Single-Exit regions) and optimization hurdles (e.g. thread
synchronization; where programmers do not expect the compiler to do a lot
of things) compared to C++ loop constructs.


Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200121/93b37eab/attachment.html>