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

[Michael Kruse via llvm-dev]

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