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

[Doerfert, Johannes via llvm-dev]

On 07/24, Michael Kruse via llvm-dev wrote:
> Am Di., 23. Juli 2019 um 17:16 Uhr schrieb Kaylor, Andrew
> <andrew.kaylor at intel.com>:
> > Can someone put together some concrete examples that fully describe
> > how this would look in terms of both the intrinsic proposal and the
> > GEP extension you worked out with Johannes?
> 
> The closest we have is the RFC document
> (https://github.com/bollu/llvm-multidim-array-indexing-proposal/blob/master/RFC.md).
> We are in the RFC phase to explore the problem and design space. Do
> you have any concrete questions you would like the be answered?

I just have ideas how we could preserve more information, no fully
described examples. While they are not thought through, they might help
to explore the space here:

Access-centric:
 - new "operand/metadata" to encode the multi-dim coordinate:
     %coord_3D = llvm.coord.3d(%N, %M, %K, %i, %j, %p)
     %val = load %p, [coord] %coord_3D
   Benefits: pointer computation is not disturbed, even if it is
             transformed, e.g., part of the pointer computation is
             hoisted and coalesced. Annotated operations are known to
             be UB if the bounds are violated.
   Caveats: New load operand need to be hidden, e.g., as operand bundle
   operands for calls. Alternatively, coord can be passed as metadata.
 - new "operand/metadata" to encode a shape:
     %shape_3D = llvm.shape.3d(%N, %M, %K)
     %val = load %p, [shape] %shape_3D
   Benefits: see above. When a shape and `inrange` is provided it
             applies to all dimensions of the shape.
   Caveats: see above. Reconstruction of coordinate needs to happen
            still. Though, statically complex parts, e.g., guessing the
            shape and computing when offsets would be "out-of-range",
            is much simpler.

Type-based:
 - Have multi-dimensional variable sized arrays. This was discussed in
   various contexts and I cannot summarize all the pros and cons.
 
GEP-centric:
 - an intrinsic-based solutions applied to GEPs
 - add the multi-dim coordinate inputs directly to GEPs (no intrinsic)
 - build the coordinate as above and assume it equal to the GEP:
     call @llvm.assume(icmp eq %gep, %coord_3D)

I think sth. type-based would the cleanest but also most complicated
solution. Coordinate-based solutions are probably the simplest. Neither
of the above solutions should be too intrusive wrt. unaware passes.



-- 

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190724/c537ab72/attachment.sig>