Wrong codegen for i1 vector truncating stores

[uweigand]

Bugzilla Link	35520
Resolution	FIXED
Resolved on	Jan 20, 2018 08:10
Version	trunk
OS	Linux
Blocks	#30613
CC	@efriedma-quic,@hfinkel,@bogner,@RKSimon,@arsenm,@JonPsson,@rotateright

Extended Description

The following simple test case generates completely broken code on SystemZ (run with -mcpu=z13 to enable the vector ISA):

define i16 @​test(<16 x i1> %src)
{
%res = bitcast <16 x i1> %src to i16
ret i16 %res
}

What happens is that in the ABI, the <16 x i1> is passed as <16 x i8>, so the code would need to truncate to a real 16-bit vector, and reinterpret the result as i16. For some reason, the code generator attempts to implement this as a truncating store of a <16 x i8> in register to a <16 x i1> in memory, and then loads that memory location as i16.

So far still OK, but the truncating store generates completely broken code: it simply repeatedly stores all 16 bytes of the source vector to the same byte in memory. Looking for the code that does this, I found this in VectorLegalizer::ExpandStore (added by arsenm):

// FIXME: This is completely broken and inconsistent with ExpandLoad
// handling.

// For sub-byte element sizes, this ends up with 0 stride between elements,
// so the same element just gets re-written to the same location. There seem
// to be tests explicitly testing for this broken behavior though.  tests
// for this broken behavior.

which in fact matches exactly what I'm seeing.

What's going on here? Does this not happen on other platforms? Should I be doing something different in the back-end, or should we try to fix this common code issue after all? Any suggestions welcome ...

[bogner]

This definitely looks funny. Looks to me like we get the same behaviour on AArch64, just to confirm. We should probably take a look at the tests Matt mentioned that seem to explicitly test for this and figure out if they're in error.

I poked around a little, and it looks like this may have been a bug introduced in r142060 back in 2011 and then worked around / codified into tests since then. Before that change there were a few more tests for legality of the scalar types involved that probably prevented us from legalizing this at all in the problematic cases (but I didn't read the old code all that closely).

[JonPsson]

Running the test case:

Optimized lowered selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
t0: ch = EntryToken
t2: v16i8,ch = CopyFromReg t0, Register:v16i8 %0
t3: v16i1 = truncate t2
t4: i16 = bitcast t3
t5: i32 = any_extend t4
t7: ch,glue = CopyToReg t0, Register:i32 %r2l, t5
t8: ch = SystemZISD::RET_FLAG t7, Register:i32 %r2l, t7:1

Type-legalized selection DAG: %bb.0 'test:'
SelectionDAG has 10 nodes:
t0: ch = EntryToken
t2: v16i8,ch = CopyFromReg t0, Register:v16i8 %0
t14: ch = store<ST2FixedStack0, trunc to v16i1> t0, t2, FrameIndex:i64<0>, undef:i64
t15: i32,ch = load<LD2[FixedStack0], anyext from i16> t14, FrameIndex:i64<0>, undef:i64
t7: ch,glue = CopyToReg t0, Register:i32 %r2l, t15
t8: ch = SystemZISD::RET_FLAG t7, Register:i32 %r2l, t7:1

• The truncating store -> load trick is the rescue method of the bitcast, which means the v16i1 vector really must be stored as 16 bits - it could not be stored as a legal target vector (v16i8).

• Unless target can do this somehow, the v16i1 vector must therefore first be built in common-code by using vector element extracts / shifts / inserts etc. This seems to be simply missing.

• scalarizeVectorStore() seems the right place for this, given that this is where this node gets handled unless it is either legal or custom handled by target.

The comment above that method says:

// FIXME: This relies on each element having a byte size, otherwise the stride
// is 0 and just overwrites the same location. ExpandStore currently expects
// this broken behavior.
SDValue TargetLowering::scalarizeVectorStore(StoreSDNode *ST,
SelectionDAG &DAG) const {

, which is what we already knew, although I am not sure how ExpandStore 'expects' this.

Adding

diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index 1dff66f..a5d355c 100644
--- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -3434,6 +3434,7 @@ SDValue TargetLowering::scalarizeVectorStore(StoreSDNode *ST,

// Store Stride in bytes
unsigned Stride = MemSclVT.getSizeInBits() / 8;

• assert (Stride && "Zero stride!");
  EVT IdxVT = getVectorIdxTy(DAG.getDataLayout());
  unsigned NumElem = StVT.getVectorNumElements();

, caused many test fails, which there shouldn't be:

LLVM :: CodeGen/AArch64/setcc-type-mismatch.ll
LLVM :: CodeGen/AMDGPU/load-constant-i1.ll
LLVM :: CodeGen/AMDGPU/load-global-i1.ll
LLVM :: CodeGen/AMDGPU/load-local-i1.ll
LLVM :: CodeGen/ARM/setcc-type-mismatch.ll
LLVM :: CodeGen/SystemZ/vec-move-17.ll
LLVM :: CodeGen/X86/bitcast-and-setcc-512.ll
LLVM :: CodeGen/X86/bitcast-setcc-512.ll
LLVM :: CodeGen/X86/clear_upper_vector_element_bits.ll
LLVM :: CodeGen/X86/pr20011.ll
LLVM :: CodeGen/X86/pr20012.ll
LLVM :: CodeGen/X86/pr32108.ll
LLVM :: CodeGen/X86/trunc-store.ll
LLVM :: CodeGen/X86/vector-compare-results.ll

CodeGen/SystemZ/vec-move-17.ll:

; Test a v16i8->v16i1 truncation.
define void @​f1(<16 x i8> %val, <16 x i1> *%ptr) {
; No expected output, but must compile.
%trunc = trunc <16 x i8> %val to <16 x i1>
store <16 x i1> %trunc, <16 x i1> *%ptr
ret void
}

Looking at the output, this also just overwrites the same memory location over and over again. So this is a test that does not care about the output, which explains why it passed in the first place. Haven't looked at the others...

My current idea then is to add code in scalarizeVectorStore() that in the case of non-byte sized elements, extracts vector elements and builds the correct
value before storing it with shifts etc. I am quite unsure about the requirements on such a fix - I suppose there might be multiple stores? What would the correct MVT of those store operands be - some legal integer type?
Is there any code somewhere that is similar?

Does this make sense?

[efriedma-quic]

I am quite unsure about the requirements on such a fix - I suppose there might be multiple stores? What would the correct MVT of those store operands be - some legal integer type?

Just generate one store, and don't worry whether the scalar types are legal; type legalization will clean it up for you. I mean, you could try to get fancy like VectorLegalizer::ExpandLoad does, but you don't have to; we run type legalization afterwards because it's difficult to avoid generating illegal scalar ops when scalarizing vector ops.

If you're trying to fix this completely, VectorLegalizer::ExpandStore and DAGTypeLegalizer::SplitVecOp_STORE probably also need changes.

[JonPsson]

If you're trying to fix this completely, VectorLegalizer::ExpandStore and DAGTypeLegalizer::SplitVecOp_STORE probably also need changes.

I am not sure if I am missing something, but it seems to me that in ExpandStore, the element width is (if needed) extended to the next power of two - e.g. 18bits -> 32bits, and then a vector with the same number of elements is stored. How could this be a truncating store of that value? It seems extending, to me. Yet, getTruncStore() is called, which has an assert that checks for this which does not trigger. The reason seems to be that the whole

if (!isPowerOf2_32(ScalarSize)) {}

is dead!? At least all tests seems to pass without it. I wish somebody would supply a test for this, or else give ok to remove it. Matthew..?

To be honest, I really don't see how ExpandStore ever should change the vector type. This will always be wrong if a bitcast has been implemented by first storing the vector to memory and then reading it back as an integer, or?

scalarizeVectorStore() should store the vector with scalar stores of elements, or if needed with vector element extracts to build an integer to store. The result in memory must look like the original vector, or the bitcast will not work.

For example, a bitcast of an i1 vector escapes this problem since 1 is a power of two. What would happen for e.g. an i2? If one would bitcast an v8i2 to i16 by doing a store + load which I guess is what would happen, then it would certainly be wrong to extend each element to i8 and do scalar stores.

SplitVecOp_STORE(): Tried to find a relevant test case, but could not. Not sure how non-byte sized vector elements come into play here... This will simply split the vector into two. Do you have a test case?

[JonPsson]

Patch that removes the powerOf2 handling in ExpandStore()

[efriedma-quic]

Try the following to test the functions I mentioned?

target triple="aarch64"
define void @​VectorLegalizer_ExpandStore_test(<4 x i31> %src, <4 x i31>* %p)
{
store <4 x i31> %src, <4 x i31>* %p
ret void
}
define void @​DAGTypeLegalizer_SplitVecOp_STORE_test(<8 x i31> %src, <8 x i31>* %p)
{
store <8 x i31> %src, <8 x i31>* %p
ret void
}

[JonPsson]

Thanks for the test cases.

Again, my first question is if you agree that any vector must be stored as-is in memory, due to the bitcast load/store trick?

I suppose it would however be OK to add padding bytes after the vector to such a store, to round the stored number of bytes to the next power-of-2?

In that case, these test cases seem to fail because they are in effect putting a 1-bit padding after each element instead inside the vector, by treating them as 32 bits elements.

Any comment on my concern about the code in ExpandStore()?

[efriedma-quic]

Again, my first question is if you agree that any vector must be stored as-is in memory, due to the bitcast load/store trick?

Yes. At least, we have a bunch of code which assumes that's how vectors work.

I suppose it would however be OK to add padding bytes after the vector to such a store, to round the stored number of bytes to the next power-of-2?

The DataLayout code currently computes the size of <24 x i1> as three bytes. If you want to match that, you can't round the stored number of bytes.

Any comment on my concern about the code in ExpandStore()?

VectorLegalizer::ExpandStore should not change the memory VT.

[JonPsson]

I suppose it would however be OK to add padding bytes after the vector to such a store, to round the stored number of bytes to the next power-of-2?

The DataLayout code currently computes the size of <24 x i1> as three bytes.
If you want to match that, you can't round the stored number of bytes.

I guess my first question was if this is always expected, so that common code really should and must do this?

Next question was if it would be actually legal to store this vector as 4 bytes, which I suppose it would. It should at least not disturb the bitcast store/load.

VectorLegalizer::ExpandStore should not change the memory VT.
I guess then I basically don't understand the point of the code that rounds up to the next power-of-2... As mentioned, there is not even a test for it.

I would like to:

1. Remove the code that modifies the memory VT in ExpandStore. Any objections?
2. Add code in scalarizeVectorStore to painstakingly build an integer to be stored out of extracted elements, with the same size as the input vector. This would be done for any vector that does not have elements that are at least one byte in size which is also a power-of-2. In other words, any weird vectors with i1, i7, i24, ... elements get this special treatment, which should be rare and therefore does not have to be efficient.
3. Any vectors that have a weird number of elements, or otherwise do not have a power-of-2 size, are trusted to be handled later. A <24 x i1> vector would result in building a 24 bit integer per (2), but a <3 x i8> vector would be let through to the type legalizer.

Does this plan look good?

[efriedma-quic]

1. Remove the code that modifies the memory VT in ExpandStore. Any
   objections?

Please do.

2. Add code in scalarizeVectorStore to painstakingly build an integer to be
   stored out of extracted elements, with the same size as the input vector.
   This would be done for any vector that does not have elements that are at
   least one byte in size which is also a power-of-2. In other words, any weird
   vectors with i1, i7, i24, ... elements get this special treatment, which
   should be rare and therefore does not have to be efficient.

Yes, this is right.

3. Any vectors that have a weird number of elements, or otherwise do not
   have a power-of-2 size, are trusted to be handled later. A <24 x i1> vector
   would result in building a 24 bit integer per (2), but a <3 x i8> vector
   would be let through to the type legalizer.

There are basically three things the type legalizer can do with a vector type: widen, split or promote.

The type legalizer widens any vector where the number of elements isn't a power of two. (We do this even when the wider type isn't legal to simplify vector splitting.) For a store, this goes through DAGTypeLegalizer::WidenVecOp_STORE... which should use the special treatment from (2) if the element type isn't byte-sized.

If the number of elements is a power of two, and there's a legal vector type with the same number of elements and a wider integer type, we promote. For a store, the type legalizer generates a truncstore; this eventually gets legalized in VectorLegalizer::ExpandStore, which should use the special treatment from (2) if the element type isn't byte-sized.

Otherwise, we split the vector. For a store, this goes through DAGTypeLegalizer::SplitVecOp_STORE, which should use the special treatment from (2) if the element type isn't byte-sized.

I think that covers all the relevant codepaths.

[JonPsson]

Please take a look at:

https://reviews.llvm.org/D42100

[JonPsson]

trunk@323042