[SROA] fix assetion failure

[inouehrs]

Summary

This patch fixes the assertion failure in SROA reported in PR35657.
PR35657 reports the assertion failure due to r319522 (splitting for non-whole-alloca slices), but this problem can happen even without r319522.

The problem exists in a check for reusing an existing alloca when rewriting partitions. As the original comment said, we can reuse the existing alloca if the new alloca has the same type and offset with the existing one. But the code checks only type of the alloca and then check the offset using an assert.
In a corner case with out-of-bounds access (e.g. @PR35657 function added in unit test), it is possible that the two allocas have the same type but different offsets.

This patch makes the check of the offset in the if condition, and re-enables the splitting for non-whole-alloca slices.

[rnk]

lib/Transforms/Scalar/SROA.cpp

130 ↗

(On Diff #129580)

Can you delete this flag instead and simplify the logic that checks it?

test/Transforms/SROA/basictest.ll

1712 ↗

(On Diff #129580)

WOW, I guess this isn't UB because the storage size of i48 is 8 bytes, right? Crazy.

[inouehrs]

• eliminated SROASplitNonWholeAllocaSlices flag

[efriedma]

test/Transforms/SROA/basictest.ll

1712 ↗

(On Diff #129580)

No, this is UB; an i48 has a storage size of 6 bytes.

Granted, we still shouldn't crash.

[efriedma]

It looks like this doesn't properly fix PR35657; it fixes the crash, yes, but it looks like the optimizer is introducing undefined behavior.

[inouehrs]

fixed an unit test to avoid emitting undef values.

[inouehrs]

In D41981#975406, @efriedma wrote:

It looks like this doesn't properly fix PR35657; it fixes the crash, yes, but it looks like the optimizer is introducing undefined behavior.

I updated the test case to avoid undef in the generated code due to loads from uninitialized alloca.
Do you expect other behavior (such as not applying SROA for out-of-bounds accesses)?

[efriedma]

LGTM, but don't close PR35657 until you track down the miscompile. (csmith should not be generating code with out-of-bounds accesses, so there's probably another bug somewhere.)

lib/Transforms/Scalar/SROA.cpp

3933 ↗

(On Diff #129752)

Please add a comment explaining that beginOffset() != 0 can happen for out-of-bounds accesses. (We want to transform anyway because we don't want undefined behavior in unreachable code to block optimizations in other code.)

llvm/trunk/lib/Transforms/Scalar/SROA.cpp

 static cl::opt<bool> SROARandomShuffleSlices("sroa-random-shuffle-slices",
                                              cl::init(false), cl::Hidden);
 
 /// Hidden option to experiment with completely strict handling of inbounds
 /// GEPs.
 static cl::opt<bool> SROAStrictInbounds("sroa-strict-inbounds", cl::init(false),
                                         cl::Hidden);
 
-/// Hidden option to allow more aggressive splitting.
-static cl::opt<bool>
-SROASplitNonWholeAllocaSlices("sroa-split-nonwhole-alloca-slices",
-                              cl::init(false), cl::Hidden);
-
 namespace {
 
 /// \brief A custom IRBuilder inserter which prefixes all names, but only in
 /// Assert builds.
 class IRBuilderPrefixedInserter : public IRBuilderDefaultInserter {
   std::string Prefix;
 
   const Twine getNameWithPrefix(const Twine &Name) const {
VectorType *VecTy =
       IsIntegerPromotable ? nullptr : isVectorPromotionViable(P, DL);
   if (VecTy)
     SliceTy = VecTy;
 
   // Check for the case where we're going to rewrite to a new alloca of the
   // exact same type as the original, and with the same access offsets. In that
   // case, re-use the existing alloca, but still run through the rewriter to
   // perform phi and select speculation.
+  // P.beginOffset() can be non-zero even with the same type in a case with
+  // out-of-bounds access (e.g. @PR35657 function in SROA/basictest.ll).
   AllocaInst *NewAI;
-  if (SliceTy == AI.getAllocatedType()) {
-    assert(P.beginOffset() == 0 &&
-           "Non-zero begin offset but same alloca type");
+  if (SliceTy == AI.getAllocatedType() && P.beginOffset() == 0) {
     NewAI = &AI;
     // FIXME: We should be able to bail at this point with "nothing changed".
     // FIXME: We might want to defer PHI speculation until after here.
     // FIXME: return nullptr;
   } else {
     unsigned Alignment = AI.getAlignment();
     if (!Alignment) {
       // The minimum alignment which users can rely on when the explicit
bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &AS) {
   // We leave a slice splittable if all other slices are disjoint or fully
   // included in the slice, such as whole-alloca loads and stores.
   // If we fail to split these during pre-splitting, we want to force them
   // to be rewritten into a partition.
   bool IsSorted = true;
 
   uint64_t AllocaSize = DL.getTypeAllocSize(AI.getAllocatedType());
   const uint64_t MaxBitVectorSize = 1024;
-  if (SROASplitNonWholeAllocaSlices && AllocaSize <= MaxBitVectorSize) {
+  if (AllocaSize <= MaxBitVectorSize) {
     // If a byte boundary is included in any load or store, a slice starting or
     // ending at the boundary is not splittable.
     SmallBitVector SplittableOffset(AllocaSize + 1, true);
     for (Slice &S : AS)
       for (unsigned O = S.beginOffset() + 1;
            O < S.endOffset() && O < AllocaSize; O++)
         SplittableOffset.reset(O);
 

llvm/trunk/test/DebugInfo/X86/sroasplit-2.ll

 ;    int foo(Outer outer) {
 ;      Inner i1 = outer.inner[1];
 ;      return i1.a;
 ;    }
 ;
 
 ; Verify that SROA creates a variable piece when splitting i1.
 ; CHECK:  call void @llvm.dbg.value(metadata i64 %outer.coerce0, metadata ![[O:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_fragment, 0, 64)),
-; CHECK:  call void @llvm.dbg.value(metadata i64 %outer.coerce1, metadata ![[O]], metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64)),
+; CHECK:  call void @llvm.dbg.value(metadata i32 {{.*}}, metadata ![[O]], metadata !DIExpression(DW_OP_LLVM_fragment, 64, 32)),
+; CHECK:  call void @llvm.dbg.value(metadata i32 {{.*}}, metadata ![[O]], metadata !DIExpression(DW_OP_LLVM_fragment, 96, 32)),
 ; CHECK:  call void @llvm.dbg.value({{.*}}, metadata ![[I1:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)),
 ; CHECK-DAG: ![[O]] = !DILocalVariable(name: "outer",{{.*}} line: 10
 ; CHECK-DAG: ![[I1]] = !DILocalVariable(name: "i1",{{.*}} line: 11
 
 ; ModuleID = 'sroasplit-2.c'
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.9.0"
 

llvm/trunk/test/Transforms/SROA/basictest.ll

entry:
   %load = load atomic volatile i64, i64* %ptr seq_cst, align 8
   ret void
 }
 
 define i16 @PR24463() {
 ; Ensure we can handle a very interesting case where there is an integer-based
 ; rewrite of the uses of the alloca, but where one of the integers in that is
 ; a sub-integer that requires extraction *and* extends past the end of the
-; alloca. In this case, we should extract the i8 and then zext it to i16.
+; alloca. SROA can split the alloca to avoid shift or trunc.
 ;
 ; CHECK-LABEL: @PR24463(
 ; CHECK-NOT: alloca
-; CHECK: %[[SHIFT:.*]] = lshr i16 0, 8
-; CHECK: %[[TRUNC:.*]] = trunc i16 %[[SHIFT]] to i8
-; CHECK: %[[ZEXT:.*]] = zext i8 %[[TRUNC]] to i16
+; CHECK-NOT: trunc
+; CHECK-NOT: lshr
+; CHECK: %[[ZEXT:.*]] = zext i8 {{.*}} to i16
 ; CHECK: ret i16 %[[ZEXT]]
 entry:
   %alloca = alloca [3 x i8]
   %gep1 = getelementptr inbounds [3 x i8], [3 x i8]* %alloca, i64 0, i64 1
   %bc1 = bitcast i8* %gep1 to i16*
   store i16 0, i16* %bc1
   %gep2 = getelementptr inbounds [3 x i8], [3 x i8]* %alloca, i64 0, i64 2
   %bc2 = bitcast i8* %gep2 to i16*

 ; CHECK-NEXT: ret void
 bb1:
   %e.7.sroa.6.i = alloca i32, align 1
   %e.7.sroa.6.0.load81.i = load i32, i32* %e.7.sroa.6.i, align 1
   %0 = bitcast i32* %e.7.sroa.6.i to i8*
   call void @llvm.lifetime.end.p0i8(i64 2, i8* %0)
   ret void
 }
+
+; PR35657 reports assertion failure with this code
+define void @PR35657(i64 %v) {
+; CHECK-LABEL: @PR35657
+; CHECK: call void @callee16(i16 %{{.*}})
+; CHECK: call void @callee48(i48 %{{.*}})
+; CHECK: ret void
+entry:
+  %a48 = alloca i48
+  %a48.cast64 = bitcast i48* %a48 to i64*
+  store i64 %v, i64* %a48.cast64
+  %a48.cast16 = bitcast i48* %a48 to i16*
+  %b0_15 = load i16, i16* %a48.cast16
+  %a48.cast8 = bitcast i48* %a48 to i8*
+  %a48_offset2 = getelementptr inbounds i8, i8* %a48.cast8, i64 2
+  %a48_offset2.cast48 = bitcast i8* %a48_offset2 to i48*
+  %b16_63 = load i48, i48* %a48_offset2.cast48, align 2
+  call void @callee16(i16 %b0_15)
+  call void @callee48(i48 %b16_63)
+  ret void
+}
+
+declare void @callee16(i16 %a)
+declare void @callee48(i48 %a)
+
+define void @test28(i64 %v) #0 {
+; SROA should split the first i64 store to avoid additional and/or instructions
+; when storing into i32 fields
+
+; CHECK-LABEL: @test28(
+; CHECK-NOT: alloca
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK:      %[[shift:.*]] = lshr i64 %v, 32
+; CHECK-NEXT: %{{.*}} = trunc i64 %[[shift]] to i32
+; CHECK-NEXT: ret void
+
+entry:
+  %t = alloca { i64, i32, i32 }
+
+  %b = getelementptr { i64, i32, i32 }, { i64, i32, i32 }* %t, i32 0, i32 1
+  %0 = bitcast i32* %b to i64*
+  store i64 %v, i64* %0
+
+  %1 = load i32, i32* %b
+  %c = getelementptr { i64, i32, i32 }, { i64, i32, i32 }* %t, i32 0, i32 2
+  store i32 %1, i32* %c
+  ret void
+}

llvm/trunk/test/Transforms/SROA/big-endian.ll

 
 ; CHECK-NOT: store
 ; CHECK-NOT: load
 
   %a0i16ptr = bitcast i8* %a0ptr to i16*
   store i16 1, i16* %a0i16ptr
 
   store i8 1, i8* %a2ptr
-; CHECK:      %[[mask1:.*]] = and i40 undef, 4294967295
-; CHECK-NEXT: %[[insert1:.*]] = or i40 %[[mask1]], 4294967296
 
   %a3i24ptr = bitcast i8* %a3ptr to i24*
   store i24 1, i24* %a3i24ptr
-; CHECK-NEXT: %[[mask2:.*]] = and i40 %[[insert1]], -4294967041
-; CHECK-NEXT: %[[insert2:.*]] = or i40 %[[mask2]], 256
 
   %a2i40ptr = bitcast i8* %a2ptr to i40*
   store i40 1, i40* %a2i40ptr
-; CHECK-NEXT: %[[ext3:.*]] = zext i40 1 to i56
-; CHECK-NEXT: %[[mask3:.*]] = and i56 undef, -1099511627776
-; CHECK-NEXT: %[[insert3:.*]] = or i56 %[[mask3]], %[[ext3]]
+
+; the alloca is splitted into multiple slices
+; Here, i8 1 is for %a[6]
+; CHECK: %[[ext1:.*]] = zext i8 1 to i40
+; CHECK-NEXT: %[[mask1:.*]] = and i40 undef, -256
+; CHECK-NEXT: %[[insert1:.*]] = or i40 %[[mask1]], %[[ext1]]
+
+; Here, i24 0 is for %a[3] to %a[5]
+; CHECK-NEXT: %[[ext2:.*]] = zext i24 0 to i40
+; CHECK-NEXT: %[[shift2:.*]] = shl i40 %[[ext2]], 8
+; CHECK-NEXT: %[[mask2:.*]] = and i40 %[[insert1]], -4294967041
+; CHECK-NEXT: %[[insert2:.*]] = or i40 %[[mask2]], %[[shift2]]
+
+; Here, i8 0 is for %a[2]
+; CHECK-NEXT: %[[ext3:.*]] = zext i8 0 to i40
+; CHECK-NEXT: %[[shift3:.*]] = shl i40 %[[ext3]], 32
+; CHECK-NEXT: %[[mask3:.*]] = and i40 %[[insert2]], 4294967295
+; CHECK-NEXT: %[[insert3:.*]] = or i40 %[[mask3]], %[[shift3]]
+
+; CHECK-NEXT: %[[ext4:.*]] = zext i40 %[[insert3]] to i56
+; CHECK-NEXT: %[[mask4:.*]] = and i56 undef, -1099511627776
+; CHECK-NEXT: %[[insert4:.*]] = or i56 %[[mask4]], %[[ext4]]
 
 ; CHECK-NOT: store
 ; CHECK-NOT: load
 
   %aiptr = bitcast [7 x i8]* %a to i56*
   %ai = load i56, i56* %aiptr
   %ret = zext i56 %ai to i64
   ret i64 %ret
-; CHECK-NEXT: %[[ext4:.*]] = zext i16 1 to i56
-; CHECK-NEXT: %[[shift4:.*]] = shl i56 %[[ext4]], 40
-; CHECK-NEXT: %[[mask4:.*]] = and i56 %[[insert3]], 1099511627775
-; CHECK-NEXT: %[[insert4:.*]] = or i56 %[[mask4]], %[[shift4]]
-; CHECK-NEXT: %[[ret:.*]] = zext i56 %[[insert4]] to i64
+; Here, i16 1 is for %a[0] to %a[1]
+; CHECK-NEXT: %[[ext5:.*]] = zext i16 1 to i56
+; CHECK-NEXT: %[[shift5:.*]] = shl i56 %[[ext5]], 40
+; CHECK-NEXT: %[[mask5:.*]] = and i56 %[[insert4]], 1099511627775
+; CHECK-NEXT: %[[insert5:.*]] = or i56 %[[mask5]], %[[shift5]]
+; CHECK-NEXT: %[[ret:.*]] = zext i56 %[[insert5]] to i64
 ; CHECK-NEXT: ret i64 %[[ret]]
 }
 
 define i64 @PR14132(i1 %flag) {
 ; CHECK-LABEL: @PR14132(
 ; Here we form a PHI-node by promoting the pointer alloca first, and then in
 ; order to promote the other two allocas, we speculate the load of the
 ; now-phi-node-pointer. In doing so we end up loading a 64-bit value from an i8