[SROA] Assert the AllocSize of i8 to be 1

[jsilvanus]

Summary

When SROA rewrites GEPs, it tries to generate "natural"
GEPs that apply to the underlying type of the alloca.
If that fails, SROA falls back to using an i8-based GEP
with the byte-offset as index.

This however requires the AllocSize of i8 to be 1, which
is not the case with nontrivial alignment requirements,
which may e.g. occur with DXIL.
Add assertions checking this assumption.

[lebedev.ri]

Test?

[jsilvanus]

Are you interested in a lit test checking that the assertion fires? Are we testing individual asserts this way?

[lebedev.ri]

In D138708#3950830, @jsilvanus wrote:

Are you interested in a lit test checking that the assertion fires? Are we testing individual asserts this way?

I'm mainly unconvinced as to why this change is correct..

[jsilvanus]

In these places, we try to obtain a pointer based on a base pointer and a byte offset, and do so using a GEP on i8, using the offset as index.
This will fail if the AllocSize of i8 is not 1. The added assertions detect such cases instead of generating wrong code.

I can't comment on whether the existing behavior is correct, that is, whether overaligned i8 should be supported.

[lebedev.ri]

I would still like to see a test for this change, and an end-to-end micompile, to better understand where things go wrong.

[jsilvanus]

Add test case that triggers the assert.

If we want to keep it, we'd need change it in some way to pass again, e.g. mark as XFAIL, or check for the assert. I'm not sure on what's the recommended way to do such things, but for now it should suffice to demonstrate the issue.

[jsilvanus]

Fix constant in test case.

[lebedev.ri]

Ok, that is weird. I'm guessing the test case should return 2? https://alive2.llvm.org/ce/z/BMccF9
I think this is hinting that a pretty fundamental assumption about i8's in LLVM does not hold,
and there are likely many more problems like this.

Does it work if you assert that the offset is a multiple of getTypeAllocSize and divide it by that?

[jsilvanus]

Yes, you are right, I miscalculated by one bit :) Updated the test accordingly.

I was expecting this assumption to be rather wide-spread, and I am not even sure
SROA is supposed to correctly handle such cases. This why I just added an assertion
that at least uncovers the issue, rather than reporting a bug in SROA.

The offset in the example is not a multiple of the AllocSize of i8:
The offset is 5 (coming from the corresponding GEP in the test case),
but the alloc size of i8 is 4.

[lebedev.ri]

I would say that backend/front-end is essentially non-conforming
as far as LLVM is concerned - there is a very hard sentiment that
LLVM should only support the cases where byte is 8 bits,
which is essentially not the case here. If this doesn't hold,
e.g. the "simple GEPs" proposal, which does this same expansion,
goes out of the window.

I would suggest posting to discuss.

TBN, this wouldn't be a problem if we had a true byte type, @nlopes.

[jsilvanus]

I don't need support for overaligned i8s, it is fine for me to have LLVM require natural alignment on i8.

But having explicit asserts maybe helps save some people's time in the future -- it certainly would have for me.
Also, it explicitly documents the assumption underlying these GEPs.

I'm not the sure the test brings additional value beyond motivating this change.
There are probably many other places that can be broken by using such a data layout, and as long as
there is no effort to make overaligned i8s work I see little value in documenting these.

Thus, I'd propose to not commit the test and just add the assertions.
But if you feel this issue should be discussed further, I'm fine to open a thread on that.

For what it's worth, I ran into a similar, separate issue with incorrect GEP offsets during SROA with vectors of overaligned elements that I *do* intend to fix, because that should work.

[lebedev.ri]

In D138708#3951468, @jsilvanus wrote:

I don't need support for overaligned i8s, it is fine for me to have LLVM require natural alignment on i8.

But having explicit asserts maybe helps save some people's time in the future -- it certainly would have for me.
Also, it explicitly documents the assumption underlying these GEPs.

I'm not the sure the test brings additional value beyond motivating this change.
There are probably many other places that can be broken by using such a data layout, and as long as
there is no effort to make overaligned i8s work I see little value in documenting these.

Thus, I'd propose to not commit the test and just add the assertions.
But if you feel this issue should be discussed further, I'm fine to open a thread on that.

For what it's worth, I ran into a similar, separate issue with incorrect GEP offsets during SROA with vectors of overaligned elements that I *do* intend to fix, because that should work.

Thank you for looking into this.
I do agree that this looks like a problem that needs to be improved.
There is a caveat here: while we should assert liberally, reachable assertions should be fixed in some way.

Indeed, the problem appears to happen the moment we create a datalayout with overaligned byte type.
So let's just detect that there, diagnose it as invalid, and refuse to create it?

[jsilvanus]

I've started a discourse discussion on the topic: https://discourse.llvm.org/t/status-of-overaligned-i8/66913

[lebedev.ri]

In D138708#3959899, @jsilvanus wrote:

I've started a discourse discussion on the topic: https://discourse.llvm.org/t/status-of-overaligned-i8/66913

Thanks!

[jsilvanus]

This is the patch for the mentioned issue of GEPs into vectors of overaligned elements: https://reviews.llvm.org/D139034

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[jsilvanus]

Abandoning, we will require i8 to be naturally aligned in the datalayout as discussed on discourse. Sorry for leaving it open for so long.

llvm/lib/Transforms/Scalar/SROA.cpp

 /// properties. The algorithm tries to fold as many constant indices into
 /// a single GEP as possible, thus making each GEP more independent of the
 /// surrounding code.
 static Value *getAdjustedPtr(IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr,
                              APInt Offset, Type *PointerTy,
                              const Twine &NamePrefix) {
   // Create i8 GEP for opaque pointers.
   if (Ptr->getType()->isOpaquePointerTy()) {
-    if (Offset != 0)
-      Ptr = IRB.CreateInBoundsGEP(IRB.getInt8Ty(), Ptr, IRB.getInt(Offset),
+    if (Offset != 0) {
+      Type *Int8Ty = IRB.getInt8Ty();
+      // This may fail due to alignment
+      assert(DL.getTypeAllocSize(Int8Ty) == 1 && "Unexpected I8 size!");
+      Ptr = IRB.CreateInBoundsGEP(Int8Ty, Ptr, IRB.getInt(Offset),
                                   NamePrefix + "sroa_idx");
+    }
     return IRB.CreatePointerBitCastOrAddrSpaceCast(Ptr, PointerTy,
                                                    NamePrefix + "sroa_cast");
   }
 
   // Even though we don't look through PHI nodes, we could be called on an
   // instruction in an unreachable block, which may be on a cycle.
   SmallPtrSet<Value *, 4> Visited;
   Visited.insert(Ptr);
static Value *getAdjustedPtr(IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr,
   if (!OffsetPtr) {
     if (!Int8Ptr) {
       Int8Ptr = IRB.CreateBitCast(
           Ptr, IRB.getInt8PtrTy(PointerTy->getPointerAddressSpace()),
           NamePrefix + "sroa_raw_cast");
       Int8PtrOffset = Offset;
     }
 
-    OffsetPtr = Int8PtrOffset == 0
-                    ? Int8Ptr
-                    : IRB.CreateInBoundsGEP(IRB.getInt8Ty(), Int8Ptr,
-                                            IRB.getInt(Int8PtrOffset),
-                                            NamePrefix + "sroa_raw_idx");
+    Type *Int8Ty = IRB.getInt8Ty();
+    // This may fail due to alignment
+    assert(DL.getTypeAllocSize(Int8Ty) == 1 && "Unexpected I8 size!");
+    OffsetPtr =
+        Int8PtrOffset == 0
+            : IRB.CreateInBoundsGEP(Int8Ty, Int8Ptr, IRB.getInt(Int8PtrOffset),
   }
   Ptr = OffsetPtr;
 
   // On the off chance we were targeting i8*, guard the bitcast here.
   if (cast<PointerType>(Ptr->getType()) != TargetPtrTy) {
     Ptr = IRB.CreatePointerBitCastOrAddrSpaceCast(Ptr,
                                                   TargetPtrTy,
                                                   NamePrefix + "sroa_cast");

llvm/test/Transforms/SROA/overaligned-datalayout.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes sroa -S | FileCheck %s --check-prefix=OVERALIGNED
+; RUN: grep -v "target datalayout" %s | opt -passes sroa -S | FileCheck %s --check-prefix=NATURAL
+
+; Test case demonstrating an SROA issue in case of overaligned i8s.
+; It is not clear whether SROA should support such cases,
+; but the test case at least demonstrates the issue.
+
+; Non-vectors require at least 32-bit alignment.
+target datalayout = "e-m:e-p:64:64-i8:32-i16:32-i32:32-i64:32-f16:32-f32:32-f64:32-n8:16:32"
+
+; Pack the byte to be accessed into a vector within a struct.
+; For some reason, this is necessary to trigger the problematic behavior.
+%AllocStruct = type { <3 x i16> }
+; The <1 x i8> has an alignment of 8 bits, even if i8 has an alignment of 32 bits,
+; so we can use it to access individual bytes.
+%ByteAccessStruct = type { <1 x i8> }
+
+; Alloca a struct containing a <3 x i16>, then access its last byte using ByteAccessStruct.
+define i8 @test_i8_access() {
+; Note: This returns poison, but should return 2. This is caused by SROA transforming the byte
+; access into an i8-based GEP using a byte-offset as index, which is incorrect (and out-of-bounds)
+; because i8s have an alignment of 32 bits, and hence an AllocSize of 32 bits.
+; OVERALIGNED-LABEL: @test_i8_access(
+; OVERALIGNED-NEXT:    [[INTVEC:%.*]] = insertelement <3 x i16> undef, i16 513, i32 2
+; OVERALIGNED-NEXT:    [[LASTBYTESTR_FCA_0_INSERT:%.*]] = insertvalue [[BYTEACCESSSTRUCT:%.*]] poison, <1 x i8> poison, 0
+; OVERALIGNED-NEXT:    [[LASTBYTEVEC:%.*]] = extractvalue [[BYTEACCESSSTRUCT]] [[LASTBYTESTR_FCA_0_INSERT]], 0
+; OVERALIGNED-NEXT:    [[LASTBYTEI8:%.*]] = extractelement <1 x i8> [[LASTBYTEVEC]], i32 0
+; OVERALIGNED-NEXT:    ret i8 [[LASTBYTEI8]]
+;
+; NATURAL-LABEL: @test_i8_access(
+; NATURAL-NEXT:    [[ALLOCA_SROA_0:%.*]] = alloca <3 x i16>, align 16
+; NATURAL-NEXT:    [[INTVEC:%.*]] = insertelement <3 x i16> undef, i16 513, i32 2
+; NATURAL-NEXT:    store <3 x i16> [[INTVEC]], <3 x i16>* [[ALLOCA_SROA_0]], align 16
+; NATURAL-NEXT:    [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_RAW_CAST1:%.*]] = bitcast <3 x i16>* [[ALLOCA_SROA_0]] to i8*
+; NATURAL-NEXT:    [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_RAW_IDX2:%.*]] = getelementptr inbounds i8, i8* [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_RAW_CAST1]], i64 5
+; NATURAL-NEXT:    [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_CAST3:%.*]] = bitcast i8* [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_RAW_IDX2]] to <1 x i8>*
+; NATURAL-NEXT:    [[ALLOCA_SROA_0_5_ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_LOAD:%.*]] = load <1 x i8>, <1 x i8>* [[ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_GEP_SROA_CAST3]], align 1
+; NATURAL-NEXT:    [[LASTBYTESTR_FCA_0_INSERT:%.*]] = insertvalue [[BYTEACCESSSTRUCT:%.*]] poison, <1 x i8> [[ALLOCA_SROA_0_5_ALLOCA_SROA_0_5_LASTBYTESTR_FCA_0_LOAD]], 0
+; NATURAL-NEXT:    [[LASTBYTEVEC:%.*]] = extractvalue [[BYTEACCESSSTRUCT]] [[LASTBYTESTR_FCA_0_INSERT]], 0
+; NATURAL-NEXT:    [[LASTBYTEI8:%.*]] = extractelement <1 x i8> [[LASTBYTEVEC]], i32 0
+; NATURAL-NEXT:    ret i8 [[LASTBYTEI8]]
+;
+  %alloca = alloca %AllocStruct, align 16
+  %intvec = insertelement <3 x i16> undef, i16 513, i32 2
+  %intvecptr = getelementptr %AllocStruct, %AllocStruct* %alloca, i32 0, i32 0
+  store <3 x i16> %intvec, <3 x i16>* %intvecptr
+  %allocaBytePtr = bitcast %AllocStruct* %alloca to %ByteAccessStruct*
+  %allocaBytePtrLastByte = getelementptr %ByteAccessStruct, %ByteAccessStruct* %allocaBytePtr, i32 5
+  %lastByteStr = load %ByteAccessStruct, %ByteAccessStruct* %allocaBytePtrLastByte
+  %lastByteVec = extractvalue %ByteAccessStruct %lastByteStr, 0
+  %lastByteI8 = extractelement <1 x i8> %lastByteVec, i32 0
+  ret i8 %lastByteI8
+}