llvm dev - Jul 2019 - [RFC] A new multidimensional array indexing intrinsic

On Jul 25, 2019, at 7:20 AM, Michael Kruse via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> Am Mi., 24. Juli 2019 um 16:13 Uhr schrieb Tim Northover
> <t.p.northover at gmail.com>:
…
Siddharth’s original RFC
<https://github.com/bollu/llvm-multidim-array-indexing-proposal/blob/master/RFC.md>
...
>> Apart from all that, I'm pretty disappointed to see this as an
>> intrinsic though. GEP is such a fundamental part of addressing in LLVM
>> that bifurcating it into an intrinsic for either a language or an
>> analysis seems like we'd be papering over a language deficiency.
> 
> What is your preferred approach?

+mlir mailing list, even though I generally hate cross posting.

Have you been following what is happening on the MLIR side of the world?  It
directly supports multi-dimensional arrays with both value and buffer semantics
(e.g. load
<https://github.com/tensorflow/mlir/blob/master/g3doc/LangRef.md#load-operation>,
store
<https://github.com/tensorflow/mlir/blob/master/g3doc/LangRef.md#store-operation>,
and DMA
<https://github.com/tensorflow/mlir/blob/master/g3doc/LangRef.md#dma_start-operation>
operations).  It is specifically focused on solving these sorts of problems, and
is the current proposed direction for the flang compiler IR
<https://github.com/flang-compiler/f18/blob/master/documentation/Investigating-FIR-as-an-MLIR-dialect.md>
(as well as a bunch of HPC applications that haven’t gone public yet).  Even if
it isn’t directly relevant to this work, it is worth checking out to see if some
of the ideas can be borrowed.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190728/a236bdd4/attachment.html>

Am So., 28. Juli 2019 um 17:34 Uhr schrieb Chris Lattner <clattner at
nondot.org>:
>
> On Jul 25, 2019, at 7:20 AM, Michael Kruse via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>
> Am Mi., 24. Juli 2019 um 16:13 Uhr schrieb Tim Northover
> <t.p.northover at gmail.com>:
>
> …
> Siddharth’s original RFC
> ...
>
> Apart from all that, I'm pretty disappointed to see this as an
> intrinsic though. GEP is such a fundamental part of addressing in LLVM
> that bifurcating it into an intrinsic for either a language or an
> analysis seems like we'd be papering over a language deficiency.
>
>
> What is your preferred approach?
>
>
> +mlir mailing list, even though I generally hate cross posting.
>
> Have you been following what is happening on the MLIR side of the world? 
It directly supports multi-dimensional arrays with both value and buffer
semantics (e.g. load, store, and DMA operations).  It is specifically focused on
solving these sorts of problems, and is the current proposed direction for the
flang compiler IR (as well as a bunch of HPC applications that haven’t gone
public yet).  Even if it isn’t directly relevant to this work, it is worth
checking out to see if some of the ideas can be borrowed.
I have been following MLIR and even pointed the flang team towards it
since this kind of access is more important in Fortran than in C/C++.

IMHO the issue is representation since LLVM-IR does not have the
primitives that MLIR has, specifically there is no Memref type that --
in contrast to LLVM-IR pointer types are multi-dimensional, and -- in
contrast to LLVM-IR array types can have dependent and dynamic shape.

Adding a MemRef type this would go quite deep into LLVM-IR
fundamentals. Do you think it would be worth it?

Michael

On Jul 29, 2019, at 1:30 PM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
>> Have you been following what is happening on the MLIR side of the
world?  It directly supports multi-dimensional arrays with both value and buffer
semantics (e.g. load, store, and DMA operations).  It is specifically focused on
solving these sorts of problems, and is the current proposed direction for the
flang compiler IR (as well as a bunch of HPC applications that haven’t gone
public yet).  Even if it isn’t directly relevant to this work, it is worth
checking out to see if some of the ideas can be borrowed.
> 
> I have been following MLIR and even pointed the flang team towards it
> since this kind of access is more important in Fortran than in C/C++.
Oh cool.
> IMHO the issue is representation since LLVM-IR does not have the
> primitives that MLIR has, specifically there is no Memref type that --
> in contrast to LLVM-IR pointer types are multi-dimensional, and -- in
> contrast to LLVM-IR array types can have dependent and dynamic shape.
> 
> Adding a MemRef type this would go quite deep into LLVM-IR
> fundamentals. Do you think it would be worth it?
That’s the challenge, and no, I don’t think that will make sense in LLVM IR. 
Similarly, I’m very concerned about the other high level abstraction concepts
that are being proposed for LLVM IR - this is muddling the concerns and making
the system more complicated and less predictable, and it isn’t clear that the
end result of this work will ever be “truly great”.

LLVM doesn’t have the same abstractions as MLIR in multiple ways: it doesn’t
have the other things that you need to do higher level loop transformations
(e.g. affine abstractions or a layout independent memory buffer).  Without those
it is unclear whether we’ll get much benefit in practice from (e.g.) a
multidimensional index.  You can’t even really do SoA to AoS transformations
without truly heroic work (e.g. like my phd thesis :).  The places I’ve seen
higher level transformations be successful in the LLVM context are in places
like Poly (and MLIR) which have higher level abstractions, or in higher level
IRs that lower to LLVM (e.g. XLA, SIL, and many many other domain specific
examples).

This is why I ask whether its makes sense to add this to LLVM IR:  If you want
HPC style loop transformations, I don’t think that LLVM IR itself will ever be
great, even with this.  This might make some narrow set of cases slightly
better, but this is far from a solution, and isn’t contiguous with getting to a
real solution.

That said, this is just my opinion - I have no data to back this up.  Adding
‘experiemental’ intrinsics is cheap and easy, so if you think this direction has
promise, I’d recommend starting with that, building out the optimizers that you
expect to work and measure them in practice.

-Chris