[LangRef] Describe memory layout for vectors types

[bjope]

Summary

There are a couple of caveats when it comes to how vectors are
stored to memory, and thereby also how bitcast between vector
and integer types work, in LLVM IR. Specially in relation to
endianess. This patch is an attempt to document such things.

[bjope]

llvm/docs/LangRef.rst

3161

Maybe it is just confusing to talk about sub-byte sized elements and C language here? I mean we need to define how it works for sizes larger than a byte as well. And the IR is source language agnostic (even if the motivation here might origin from C).

We could perhaps just state that the layout is packed. And that the vector could be seen as one large iN scalar (N given by the type store size in bits of the vector), with element zero being in the most significant bits for a big-endian target and in the least significant bits for a little-endian target.

I guess it isn't defined where padding goes if the type size is less than the type store size (e.g. <2 x i6> has a type size that is 12 bits, but the type store size is 16 bits).

10547

I think if it might be good to add a caveat here about bitcasts involving vector types. For example that bitcast <2 x i8> to i16 puts element zero of the vector in the least significant bits of the i16 for little-endian while element zero ends up in the most significant bits for big-endian.

[markus]

That makes sense to me but before acting on it we should probably wait a while to see if the other reviewers have some feedback.

[dmgreen]

Hello. The general idea of documenting what llvm does sounds like a good idea. Alive agrees with this too, which is a good sign: https://alive2.llvm.org/ce/z/XbkTEz.

Do we know which backends support big endian? Arm and AArch64 do. Sparc, PPC, Mips, Lanai. It seems like quite a few do.

[markus]

Right, perhaps we should add maintainers of those targets as reviewers since they may be more interested in documenting endianness differences than the little-endian crowd?

[markus]

Added code owners for big-endian Sparc, PPC and MIPS as reviewers.

[nemanjai]

I am not sure if it is desired or even acceptable in the language reference, but my experience is that a diagram goes a long way towards explaining this. I've had to teach countless new developers here at IBM about the two vector layouts (since PPC supports both).
Something like this tends to resonate with developers:

Use a <4 x i32> vector as an example:
Memory:             Register(LE):          Register(BE):
 0x0 0x4 0x8 0xC     3  2  1  0             0  1  2  3
[A,  B,  C,  D]     [D, C, B, A]           [A, B, C, D]

As it shows both the relationship of the numbering of bytes in memory and the vector and the layout of the elements in the register.

llvm/docs/LangRef.rst

3161

I like the idea of comparing a vector to a scalar of the same width and stating where the elements are placed in terms of bit significance.

10547

+1

[bjope]

I'll try to make some progress here.

[bjope]

Changed the wording quite a bit. Getting rid of references to C ABI etc.

[dmgreen]

llvm/docs/LangRef.rst

3165

together

3177

Does this apply to a v4i1? I thought that worked the same way as any other i1 type. The defined bits end up in the MSBs.

[bjope]

llvm/docs/LangRef.rst

3177

Does this apply to a v4i1? I thought that worked the same way as any other i1 type. The defined bits end up in the MSBs.

I did not know about such rules for i1 (or other non-byte-sized first class types). Is that really specified somewhere?

The description for store, https://llvm.org/docs/LangRef.html#store-instruction , says that "When writing a value of a type like i20 with a size that is not an integral number of bytes, it is unspecified what happens to the extra bits that do not belong to the type, but they will typically be overwritten.". That is not really saying anything about where the padding bits are placed either. I've assumed that the placement is unspecified as well (as I've never seen any definition).

[dmgreen]

llvm/docs/LangRef.rst

3177

I may be wrong about the MSB. It will already be used in certain parts of llvm though, if we have a <X x i1> masked load that is scalarized, it will bitcast the predicate to a iX.

Alive defines it like this:
https://alive2.llvm.org/ce/z/w5BhQa

Which llc seems to agree with, from the mov r0, #4:
https://godbolt.org/z/7Tx6aM

But it was the masked load scalarization that was being fixed in D94765, so it may be worth pinning down the meaning.

[bjope]

llvm/docs/LangRef.rst

3177

I don't think the result from a backend (even alive in this case) really say if it is defined in the IR. I believe a target is likely to define where the padding goes if loading/storing non-byte-sized types, but LLVM does not know about it. Transformations on LLVM IR should therefore be extra careful when handling types with different "type size" and "type store size" (and several passes for example use DataLayout::typeSizeEqualsStoreSize to avoid certain transformations).

Here is an example using "opt -O3" that show differences between little/big endian, and also that opt isn't able to simplify your example "src2" with <4 x i1>:
https://godbolt.org/z/rvMxd1

Another way to see it is that you may bitcast <4 x i1> to i4 (from one first class non-agg type to another one with the same size), but you can't bitcast i4 to i8 (and bitcast is basically defined as a store (using the src type) followed by a load (using the dst type).

[nlopes]

Overall LGTM. Thanks for documenting this! It was painful to reverse-engineer this when implementing it in Alive2..

My only concern is about leaving vector sizes not multiple of a byte as unspecified. Doing so is the same as saying those are illegal; can't be used in practice. Can we define those as being padded, where the padding is poison, like in structs? That allows using vectors where padding isn't easy, like <8 x i3>. How do you store that to memory if the direct store is left unspecified? And with people using weird integer sizes for ML & FPGAs, I think it's a good idea to define this case.
Alive2 is being conservative here and defining the padding as zero, but it should be poison IMHO.

[tschuett]

I like the idea of ASCII-Art. My mind works better with examples and "pictures" then with long hard to read text.

[tschuett]

Clang introduced _ExtInt exactly for those people:
http://blog.llvm.org/2020/04/the-new-clang-extint-feature-provides.html

What is a vector of _ExtInt(6)?

[bjope]

In D94964#2632569, @nlopes wrote:

Overall LGTM. Thanks for documenting this! It was painful to reverse-engineer this when implementing it in Alive2..

My only concern is about leaving vector sizes not multiple of a byte as unspecified. Doing so is the same as saying those are illegal; can't be used in practice. Can we define those as being padded, where the padding is poison, like in structs? That allows using vectors where padding isn't easy, like <8 x i3>. How do you store that to memory if the direct store is left unspecified? And with people using weird integer sizes for ML & FPGAs, I think it's a good idea to define this case.
Alive2 is being conservative here and defining the padding as zero, but it should be poison IMHO.

The idea I used for describing the layout of the vectors was to base it on the fact that bitcast is allowed between first class (non-agg) types of the same size. And bitcast is defined as doing store/load. IMO the reasoning for padding should be the same for vectors and scalars that has a store size that is larger than the type size (for example, <3 x i3> should be handled just like i9).

A type such as i9 has a type store size of 16 bits according to DataLayout. So when doing a store i9 it could be seen as if 16 bits are written. The content of the seven padding bits is not defined after the store, so saying that they contain "poison" is probably ok. As long as you load/store the same size things should be ok. If you for example do store i9, followed by load i9, then you should get the same i9 value back. Similarly if you store i9, load <3 x i3> and bitcast to i9, then you should also get the same result back. But I also believe that you could store i9, load i16, store i16, load i9 and get the same result back (so that would copy the padding). I figure the latter is similar to what happens when doing memcpy on a struct (if the padding in the struct is defined as poison).

However, what I referred to when writing "unspecified" was that the position of the padding bits isn't described (and defined) by the language reference. Afaict different targets are allowed to put the padding at different positions, not only depending on endianness, when the type size is smaller than the type store size. If the position of the padding needs to be defined, then it will be interesting to find out how different targets are doing it. There could even be some target out there that for example is padding differently for i4 and i12. Maybe it has to be defined by the DataLayout somehow, if it is needed.

Btw, the target I'm working with is one of those weird targets with support for vectors with none byte-sized elements. It had probably been a lot simpler for us if each vector element was padded to the size of a byte when storing the vector to memory (similar to how it works for arrays), but that is not how it works in LLVM IR (although the load/store in the DSP is padding between each element when dealing with such vectors).

[nlopes]

Thanks for expanding on the padding. Sounds good to me.
LGTM.

llvm/docs/LangRef.rst

3158

isn't -> aren't

[bjope]

Minor update (using a bit more graphical examples instead of only text, even though it isn't exactly ascii art as someone suggested).

Also made some clarification related to the unspecifiedness of non-byte-sized stores. Thought it might be nice to say something more about it, as it was asked about in the review.

[danilaml]

llvm/docs/LangRef.rst

3204

Why is the least significant byte is placed at the largest memory address here, if it's little endian, just like for big endian?
Shouldn't it be reversed?

[bjope]

llvm/docs/LangRef.rst

3204

@danilaml : Right, that indeed looks like a typo.

store i16 0x5321, i16* %ptr

would ofcourse put the 0x21 at the lower memory address. So this should say

;    [%ptr + 0]: 00100001  (0x21)
;    [%ptr + 1]: 01010011  (0x53)

[danilaml]

llvm/docs/LangRef.rst

3204

@bjope should I submit the fix as NFC or will you do it?

[bjope]

llvm/docs/LangRef.rst

3204

I've pushed a fixup here: https://reviews.llvm.org/rG9a53fe50f4355e6dfcd6af534cb394a62128963b

[danilaml]

llvm/docs/LangRef.rst

3204

Great, thanks!

llvm/docs/LangRef.rst

 A vector type is a simple derived type that represents a vector of
 elements. Vector types are used when multiple primitive data are
 operated in parallel using a single instruction (SIMD). A vector type
 requires a size (number of elements), an underlying primitive data type,
 and a scalable property to represent vectors where the exact hardware
 vector length is unknown at compile time. Vector types are considered
 :ref:`first class <t_firstclass>`.
 
+:Memory Layout:
+
+In general vector elements are laid out in memory in the same way as
+:ref:`array types <t_array>`. That is vector element ``N`` resides at an
+address that is lower than or equal to (in case of sub-byte sized elements)
+that of vector element ``N+1``.
+
+For vectors with sub-byte sized elements these rules are extended in the spirit
+of the rules governing bit field layout in the C language. Consider
+
+::
+
+  struct { char b0 : 1; char b1 : 1; ... char b15 : 1 }
+
+In C the platform ABI defines where to find the bits ``b0 .. b15``. On (most)
+little-endian machines, ``b0`` is placed in the least-significant bit of the
+word in memory, while on (most) big-endian machines, ``b0`` is placed in the
+most-significant bit.
+
+Extrapolating this to vector types means that, on a little-endian machine, the
+first element of a ``<16 x i1>`` is found in the least-significant bit of the
+corresponding ``i16`` (i.e. the byte with lowest address) and on a big-endian
+machine the first element of the vector would be found in the most-significant
+bit of the corresponding ``i16`` (again the byte with the lowest address).
+
 :Syntax:
 
 ::
 
       < <# elements> x <elementtype> >          ; Fixed-length vector
       < vscale x <# elements> x <elementtype> > ; Scalable vector
 
 The number of elements is a constant integer value larger than 0;

 
 +------------------------+----------------------------------------------------+
 | ``<4 x i32>``          | Vector of 4 32-bit integer values.                 |
 +------------------------+----------------------------------------------------+
 | ``<8 x float>``        | Vector of 8 32-bit floating-point values.          |
 +------------------------+----------------------------------------------------+
 | ``<2 x i64>``          | Vector of 2 64-bit integer values.                 |
 +------------------------+----------------------------------------------------+
 | ``<4 x i64*>``         | Vector of 4 pointers to 64-bit integer values.     |
 +------------------------+----------------------------------------------------+
 | ``<vscale x 4 x i32>`` | Vector with a multiple of 4 32-bit integer values. |
 +------------------------+----------------------------------------------------+
 
 .. _t_label:
 
 Label Type
 ^^^^^^^^^^

 The '``bitcast``' instruction converts ``value`` to type ``ty2``. It
 is always a *no-op cast* because no bits change with this
 conversion. The conversion is done as if the ``value`` had been stored
 to memory and read back as type ``ty2``. Pointer (or vector of
 pointers) types may only be converted to other pointer (or vector of
 pointers) types with the same address space through this instruction.
 To convert pointers to other types, use the :ref:`inttoptr <i_inttoptr>`
 or :ref:`ptrtoint <i_ptrtoint>` instructions first.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       %X = bitcast i8 255 to i8              ; yields i8 :-1
       %Y = bitcast i32* %x to sint*          ; yields sint*:%x
       %Z = bitcast <2 x int> %V to i64;        ; yields i64: %V