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

After having spoken to Johannes, I think we had a classic
misunderstanding on what "extending" means.


1.
The most obvious why for me was changing GEP to allow variable-sized
multi-dimensional arrays in the first argument, such as

    %1 = getelementptr double, double* %ptr, inrange i64 %i, inrange i64 %j

(normally GEP would only allow a single index argument for a
pointer-typed base pointer).
Since %A has variable size, there is not enough information to compute
the result, we need to pass at least the stride of the innermost
dimension, such as:

    %1 = getelementptr double, double* %A, inrange i64 %i, inrange i64
%j, i64 %n

It should be clear that this breaks a lot of assumptions then went
into writing code that handle GEPs, not only the number of arguments
the GEP should have. As a result, existing code may trigger
assertions, crash, or miscompile when encountering such a modified
GEP. I think it is unfeasible to change all code to properly handle
the new form at once.


2.
Johannes' interpretation is to add some kind of metadata to GEPs, in
addition to the naive computation, such as:

    %offset1= mul i64. %i, %n
    %offset2 = add i64, %j, %offset1
    %1 = getelementptr double, double* %A, inrange i64 %offset2 [
"multi-dim"(i64 %n) ]

This was not obvious to me. The code above uses operand bundle syntax.
During our discussing for this RFC we briefly discussed metadata,
which unfortunately do not allow referencing local SSA values.


3.
For completeness, here is Johannes other suggestion without modifying
GEP/Load/Store:

    %offset1= mul i64. %i, %n
    %offset2= add i64, %j, %offset1
    %1 = getelementptr double, double* %A, inrange i64 %offset2
    %2 = llvm.multidim.access.pdouble.pdouble.i64.i64.i64.i64(double*
%A, i64 %n, i64 %m, i64 %i, i64 %j)
    %cmp = icmp eq %1, %2
    call void @llvm.assume(i1 %cmp)


The main motivation is to avoid that unprepared analyses such as
BasicAA have to give up when encountering the new intrinsic. 2. and 3.
only add things around as they were before such multidimensional
accesses.

Subjectively, I don't think that having to give up is such a big
problem. In the beginning, there will be no frontend that generates
the new intrinsic. More important passes such as BasicAA and
ScalarEvolution can be adapted before even Chapel would emit such
intrinsics. In the long term I would indeed try to fuse it with GEP
when all there is to do is changing the code determining whether it is
a multi-dimensional intrinsic to determining whether it has
variable-length form.


Michael

Er, why not use our existing first class array types?

getelementptr double, [0 x [0 x double]]* %ptr, inrange i64 %i, inrange 
i64 %j

Philip


On 7/22/19 6:05 PM, Michael Kruse via llvm-dev wrote:
> After having spoken to Johannes, I think we had a classic
> misunderstanding on what "extending" means.
>
>
> 1.
> The most obvious why for me was changing GEP to allow variable-sized
> multi-dimensional arrays in the first argument, such as
>
>      %1 = getelementptr double, double* %ptr, inrange i64 %i, inrange i64
%j
>
> (normally GEP would only allow a single index argument for a
> pointer-typed base pointer).
> Since %A has variable size, there is not enough information to compute
> the result, we need to pass at least the stride of the innermost
> dimension, such as:
>
>      %1 = getelementptr double, double* %A, inrange i64 %i, inrange i64
> %j, i64 %n
>
> It should be clear that this breaks a lot of assumptions then went
> into writing code that handle GEPs, not only the number of arguments
> the GEP should have. As a result, existing code may trigger
> assertions, crash, or miscompile when encountering such a modified
> GEP. I think it is unfeasible to change all code to properly handle
> the new form at once.
>
>
> 2.
> Johannes' interpretation is to add some kind of metadata to GEPs, in
> addition to the naive computation, such as:
>
>      %offset1= mul i64. %i, %n
>      %offset2 = add i64, %j, %offset1
>      %1 = getelementptr double, double* %A, inrange i64 %offset2 [
> "multi-dim"(i64 %n) ]
>
> This was not obvious to me. The code above uses operand bundle syntax.
> During our discussing for this RFC we briefly discussed metadata,
> which unfortunately do not allow referencing local SSA values.
>
>
> 3.
> For completeness, here is Johannes other suggestion without modifying
> GEP/Load/Store:
>
>      %offset1= mul i64. %i, %n
>      %offset2= add i64, %j, %offset1
>      %1 = getelementptr double, double* %A, inrange i64 %offset2
>      %2 = llvm.multidim.access.pdouble.pdouble.i64.i64.i64.i64(double*
> %A, i64 %n, i64 %m, i64 %i, i64 %j)
>      %cmp = icmp eq %1, %2
>      call void @llvm.assume(i1 %cmp)
>
>
> The main motivation is to avoid that unprepared analyses such as
> BasicAA have to give up when encountering the new intrinsic. 2. and 3.
> only add things around as they were before such multidimensional
> accesses.
>
> Subjectively, I don't think that having to give up is such a big
> problem. In the beginning, there will be no frontend that generates
> the new intrinsic. More important passes such as BasicAA and
> ScalarEvolution can be adapted before even Chapel would emit such
> intrinsics. In the long term I would indeed try to fuse it with GEP
> when all there is to do is changing the code determining whether it is
> a multi-dimensional intrinsic to determining whether it has
> variable-length form.
>
>
> Michael
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Am Di., 23. Juli 2019 um 12:34 Uhr schrieb Philip Reames
<listmail at philipreames.com>:
> Er, why not use our existing first class array types?
>
> getelementptr double, [0 x [0 x double]]* %ptr, inrange i64 %i, inrange
> i64 %j
This is lowered to the equivalent of

      ((double*)ptr) + i*0 + j

where we want

      ((double*)ptr) + i*n + j


Michael