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

Am Di., 23. Juli 2019 um 17:16 Uhr schrieb Kaylor, Andrew
<andrew.kaylor at intel.com>:
> Do we really have code that uses the suffix of an intrinsic for semantic
information? That seems like a bad idea. My understanding was that the suffix
was just there to provide a unique name and the function signature took care of
everything else.
I agree that this is also not my preferred option, but more an
illustration that the information is not lost. If, for any reason, we
would still use an intrinsics for this purpose, we can pass the byte
of the element type as an argument. In any case, I don't think this is
a critical issue.

> Implementing an intrinsic that later got promoted to a new instruction
might be a possibility. Does anyone have a sense for how far out typeless
pointers are?
I haven't seen any discussion about this for a long time and I would
not count on that this change will be made in the foreseeable future.
Similar to the idea of basic block arguments instead of PHI nodes.

> 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?

Michael

Am Mi., 24. Juli 2019 um 10:21 Uhr schrieb Michael Kruse
<llvmdev at meinersbur.de>:
> > Implementing an intrinsic that later got promoted to a new instruction
might be a possibility. Does anyone have a sense for how far out typeless
pointers are?
>
> I haven't seen any discussion about this for a long time and I would
> not count on that this change will be made in the foreseeable future.
> Similar to the idea of basic block arguments instead of PHI nodes.
Mmmh, looks like Tim Northover is actively working on typeless/opaque
pointers, e.g. https://reviews.llvm.org/D64203

Michael

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>

Hi all,

On Wed, 24 Jul 2019 at 16:14, Michael Kruse via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Mmmh, looks like Tim Northover is actively working on typeless/opaque
> pointers, e.g. https://reviews.llvm.org/D64203
Yep, I'm spending as much time as I can on the project. I think
there's not really much chance that it'll be required in this cycle
(i.e. when we fork in ~Jan pointers will be distinct IMO).

On intrinsics as they affect opaque pointers, I took a look earlier
and didn't notice any target-independent ones that would need a
separate type parameter, but a couple of target-specific ones did.
Unless they were particularly anomalous and implementable by other
means, intrinsics will need to develop the ability to specify an
abstract "notable type" anyway.

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.

Cheers.

Tim.