[SROA] rewritePartition()/findCommonType(): if uses have conflicting type, try getTypePartition() before falling back to largest integral use type (PR47592)

[lebedev.ri]

Summary

See https://bugs.llvm.org/show_bug.cgi?id=47592

[lebedev.ri]

Fix debuginfo test

[efriedma]

I guess if we're relying on the allocated type of the alloca anyway, preferring it over an integer type isn't terrible.

Really, though, we should avoid relying on the allocated type where possible. Here, we could check if any of the load/store operations use a pointer type, and choose a pointer type in that case.

[chandlerc]

In D88788#2311004, @efriedma wrote:

I guess if we're relying on the allocated type of the alloca anyway, preferring it over an integer type isn't terrible.

Really, though, we should avoid relying on the allocated type where possible. Here, we could check if any of the load/store operations use a pointer type, and choose a pointer type in that case.

FWIW, both of these make lots of sense to me.

[nlopes]

In D88788#2311004, @efriedma wrote:

I guess if we're relying on the allocated type of the alloca anyway, preferring it over an integer type isn't terrible.

Really, though, we should avoid relying on the allocated type where possible. Here, we could check if any of the load/store operations use a pointer type, and choose a pointer type in that case.

Agreed. But until LLVM removes pointer sub-types it's convenient to get the alloca type right to avoid bitcast on every access anyway.
When pointer sub-types goes away, I guess all this code in SROA to find the right type for alloca would go away, but as you say it would have to be replaced with code to get the right load/store type instead. (FWIW Alive2's alloca only takes the number of bytes to allocate as argument)
So I see this patch as a step in the right direction.

[lebedev.ri]

In D88788#2313958, @nlopes wrote:

In D88788#2311004, @efriedma wrote:

I guess if we're relying on the allocated type of the alloca anyway, preferring it over an integer type isn't terrible.

Really, though, we should avoid relying on the allocated type where possible. Here, we could check if any of the load/store operations use a pointer type, and choose a pointer type in that case.

Agreed. But until LLVM removes pointer sub-types it's convenient to get the alloca type right to avoid bitcast on every access anyway.
When pointer sub-types goes away, I guess all this code in SROA to find the right type for alloca would go away, but as you say it would have to be replaced with code to get the right load/store type instead. (FWIW Alive2's alloca only takes the number of bytes to allocate as argument)
So I see this patch as a step in the right direction.

So i don't do this blindly to find out that is'a bad idea, can we agree on the baseline here?
How should this be done properly? Instead of relying on the allocation type, would the D88842's approach be applicable here?

I've looked now that rGe00f189d392d is done, and i see two-ish main origin sources of introduction inttoptr/ptrtoint that weren't there before:

1. instcombine's SimplifyAnyMemTransfer() - given memcpy of a pointer-sized thingy, we lower it to a load+store of an integer
2. instcombine's combineLoadToOperationType() - CastInst::isNoopCast() needs to be updated that these casts are not no-op. (isEliminableCastPair() too, i guess)

[nlopes]

In D88788#2313981, @lebedev.ri wrote:

In D88788#2313958, @nlopes wrote:

In D88788#2311004, @efriedma wrote:

I guess if we're relying on the allocated type of the alloca anyway, preferring it over an integer type isn't terrible.

Really, though, we should avoid relying on the allocated type where possible. Here, we could check if any of the load/store operations use a pointer type, and choose a pointer type in that case.

Agreed. But until LLVM removes pointer sub-types it's convenient to get the alloca type right to avoid bitcast on every access anyway.
When pointer sub-types goes away, I guess all this code in SROA to find the right type for alloca would go away, but as you say it would have to be replaced with code to get the right load/store type instead. (FWIW Alive2's alloca only takes the number of bytes to allocate as argument)
So I see this patch as a step in the right direction.

So i don't do this blindly to find out that is'a bad idea, can we agree on the baseline here?
How should this be done properly? Instead of relying on the allocation type, would the D88842's approach be applicable here?

I don't know SROA's code in detail to answer. I guess the point is that we don't want to introduce type-punning loads. So if the original program did a pointer load, the optimized program should do the same pointer load. Even if that means we can't combine 2 loads from the same address because one is pointer and another int. (see below the byte type proposal, as it allows you to combine loads into byte loads and then do a cast).

I've looked now that rGe00f189d392d is done, and i see two-ish main origin sources of introduction inttoptr/ptrtoint that weren't there before:

1. instcombine's SimplifyAnyMemTransfer() - given memcpy of a pointer-sized thingy, we lower it to a load+store of an integer

This one requires a new byte type. We need it to support C's char anyway. Byte type doesn't have to be 1 byte, so maybe let's do it like integers: b1, b2, b3, etc.
Value with byte type could hold a value (or part of one) of any other LLVM type. No arithmetic operations are allowed on these types, only load/store and non-type punning type casts.

[lebedev.ri]

@nlopes thank you very much!

So since everyone seems to agree that this seems fine as a temporary step in the right direction,
does anyone feel like stamping it?

[lebedev.ri]

Rebased, NFC.

[lebedev.ri]

I've measured, and @ -O3 as of vanilla llvm test-suite + RawSpeed,
this results in +0.05% more bitcasts, -5.51% less inttoptr and -1.05% less ptrtoint
(at the end of middle-end opt pipeline)

[efriedma]

LGTM

[lebedev.ri]

In D88788#2315691, @efriedma wrote:

LGTM

Thank you for the review.

llvm/lib/Transforms/Scalar/SROA.cpp

LLVM_DUMP_METHOD void AllocaSlices::dump(const_iterator I) const {
   print(dbgs(), I);
 }
 LLVM_DUMP_METHOD void AllocaSlices::dump() const { print(dbgs()); }
 
 #endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
 /// Walk the range of a partitioning looking for a common type to cover this
 /// sequence of slices.
-static Type *findCommonType(AllocaSlices::const_iterator B,
-                            AllocaSlices::const_iterator E,
-                            uint64_t EndOffset) {
+static std::pair<Type *, IntegerType *>
+findCommonType(AllocaSlices::const_iterator B, AllocaSlices::const_iterator E,
   Type *Ty = nullptr;
   bool TyIsCommon = true;
   IntegerType *ITy = nullptr;
 
   // Note that we need to look at *every* alloca slice's Use to ensure we
   // always get consistent results regardless of the order of slices.
   for (AllocaSlices::const_iterator I = B; I != E; ++I) {
     Use *U = I->getUse();
for (AllocaSlices::const_iterator I = B; I != E; ++I) {
     // To avoid depending on the order of slices, Ty and TyIsCommon must not
     // depend on types skipped above.
     if (!UserTy || (Ty && Ty != UserTy))
       TyIsCommon = false; // Give up on anything but an iN type.
     else
       Ty = UserTy;
   }
 
-  return TyIsCommon ? Ty : ITy;
+  return {TyIsCommon ? Ty : nullptr, ITy};
 }
 
 /// PHI instructions that use an alloca and are subsequently loaded can be
 /// rewritten to load both input pointers in the pred blocks and then PHI the
 /// results, allowing the load of the alloca to be promoted.
 /// From this:
 ///   %P2 = phi [i32* %Alloca, i32* %Other]
 ///   %V = load i32* %P2

 /// promoted.
 AllocaInst *SROA::rewritePartition(AllocaInst &AI, AllocaSlices &AS,
                                    Partition &P) {
   // Try to compute a friendly type for this partition of the alloca. This
   // won't always succeed, in which case we fall back to a legal integer type
   // or an i8 array of an appropriate size.
   Type *SliceTy = nullptr;
   const DataLayout &DL = AI.getModule()->getDataLayout();
-  if (Type *CommonUseTy = findCommonType(P.begin(), P.end(), P.endOffset()))
-    if (DL.getTypeAllocSize(CommonUseTy).getFixedSize() >= P.size())
-      SliceTy = CommonUseTy;
+  std::pair<Type *, IntegerType *> CommonUseTy =
+      findCommonType(P.begin(), P.end(), P.endOffset());
+  // Do all uses operate on the same type?
+  if (CommonUseTy.first)
+    if (DL.getTypeAllocSize(CommonUseTy.first).getFixedSize() >= P.size())
+      SliceTy = CommonUseTy.first;
+  // If not, can we find an appropriate subtype in the original allocated type?
   if (!SliceTy)
     if (Type *TypePartitionTy = getTypePartition(DL, AI.getAllocatedType(),
                                                  P.beginOffset(), P.size()))
       SliceTy = TypePartitionTy;
+  // If still not, can we use the largest bitwidth integer type used?
+  if (!SliceTy && CommonUseTy.second)
+    if (DL.getTypeAllocSize(CommonUseTy.second).getFixedSize() >= P.size())
+      SliceTy = CommonUseTy.second;
   if ((!SliceTy || (SliceTy->isArrayTy() &&
                     SliceTy->getArrayElementType()->isIntegerTy())) &&
       DL.isLegalInteger(P.size() * 8))
     SliceTy = Type::getIntNTy(*C, P.size() * 8);
   if (!SliceTy)
     SliceTy = ArrayType::get(Type::getInt8Ty(*C), P.size());
   assert(DL.getTypeAllocSize(SliceTy).getFixedSize() >= P.size());
 

llvm/test/DebugInfo/ARM/sroa-complex.ll

 entry:
   %c = alloca { double, double }, align 8
   %0 = bitcast { double, double }* %c to [2 x i64]*
   store [2 x i64] %c.coerce, [2 x i64]* %0, align 8
   call void @llvm.dbg.declare(metadata { double, double }* %c, metadata !14, metadata !15), !dbg !16
   %c.realp = getelementptr inbounds { double, double }, { double, double }* %c, i32 0, i32 0, !dbg !17
   %c.imagp = getelementptr inbounds { double, double }, { double, double }* %c, i32 0, i32 1, !dbg !17
   store double 0.000000e+00, double* %c.realp, align 8, !dbg !17
-  ; SROA will split the complex double into two i64 values, because there is
-  ; no native double data type available.
+  ; SROA will split the complex double into two double values.
   ; Test that debug info for both values survives:
-  ; CHECK: call void @llvm.dbg.value(metadata i64 0,
+  ; CHECK: call void @llvm.dbg.value(metadata double 0.000000e+00,
   ; CHECK-SAME:                      metadata ![[C:[^,]*]],
   ; CHECK-SAME:                      metadata !DIExpression(DW_OP_LLVM_fragment, 0, 64))
   store double 0.000000e+00, double* %c.imagp, align 8, !dbg !17
-  ; CHECK: call void @llvm.dbg.value(metadata i64 0,
+  ; CHECK: call void @llvm.dbg.value(metadata double 0.000000e+00,
   ; CHECK-SAME:                      metadata ![[C]],
   ; CHECK-SAME:                      metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64))
   ret void, !dbg !18
 }
 
 ; Function Attrs: nounwind readnone
 declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
 

llvm/test/Transforms/SROA/ppcf128-no-fold.ll

-; RUN: opt < %s -sroa -S | FileCheck %s 
+; RUN: opt < %s -sroa -S | FileCheck %s
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-unknown-linux-gnu"
 
 %struct.ld2 = type { [2 x ppc_fp128] }
 declare void @bar(i8*, [2 x i128])
 
 define void @foo(i8* %v) #0 {
 entry:
entry:
   %2 = load [2 x i128], [2 x i128]* %1, align 1
   call void @bar(i8* %0, [2 x i128] %2)
   ret void
 }
 
 ; CHECK-LABEL: @foo
 ; CHECK-NOT: i128 4628293042053316608
 ; CHECK-NOT: i128 4653260752096854016
-; CHECK-DAG: i128 bitcast (ppc_fp128 0xM403B0000000000000000000000000000 to i128)
-; CHECK-DAG: i128 bitcast (ppc_fp128 0xM4093B400000000000000000000000000 to i128)
+; CHECK-DAG: bitcast ppc_fp128 0xM403B0000000000000000000000000000 to i128
+; CHECK-DAG: bitcast ppc_fp128 0xM4093B400000000000000000000000000 to i128
 ; CHECK: call void @bar(i8* %v, [2 x i128]
 ; CHECK: ret void
 
 attributes #0 = { nounwind }
 

llvm/test/Transforms/SROA/preserve-nonnull.ll

 ; a pointer load to an integer load.
 ; FIXME: While this doesn't do anythnig actively harmful today, it really
 ; should propagate the !nonnull metadata to range metadata. The irony is, it
 ; *does* initially, but then we lose that !range metadata before we finish
 ; SROA.
 define i8* @propagate_nonnull_to_int() {
 ; CHECK-LABEL: define i8* @propagate_nonnull_to_int(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    %[[A:.*]] = alloca i64
-; CHECK-NEXT:    store i64 42, i64* %[[A]]
-; CHECK-NEXT:    %[[LOAD:.*]] = load volatile i64, i64* %[[A]]
-; CHECK-NEXT:    %[[CAST:.*]] = inttoptr i64 %[[LOAD]] to i8*
-; CHECK-NEXT:    ret i8* %[[CAST]]
+; CHECK-NEXT:    %[[A:.*]] = alloca i8*
+; CHECK-NEXT:    store i8* inttoptr (i64 42 to i8*), i8** %[[A]]
+; CHECK-NEXT:    %[[LOAD:.*]] = load volatile i8*, i8** %[[A]]
+; CHECK-NEXT:    ret i8* %[[LOAD]]
 entry:
   %a = alloca [2 x i8*]
   %a.gep0 = getelementptr [2 x i8*], [2 x i8*]* %a, i32 0, i32 0
   %a.gep1 = getelementptr [2 x i8*], [2 x i8*]* %a, i32 0, i32 1
   %a.gep0.cast = bitcast i8** %a.gep0 to i64*
   %a.gep1.cast = bitcast i8** %a.gep1 to i64*
   store i64 42, i64* %a.gep1.cast
   store i64 0, i64* %a.gep0.cast
   %load = load volatile i8*, i8** %a.gep1, !nonnull !0
   ret i8* %load
 }
 
 ; Make sure we properly handle the !nonnull attribute when we convert
 ; a pointer load to an integer load and immediately promote it to an SSA
 ; register. This can fail in interesting ways due to the rewrite iteration of
 ; SROA, resulting in PR32902.
 define i8* @propagate_nonnull_to_int_and_promote() {
 ; CHECK-LABEL: define i8* @propagate_nonnull_to_int_and_promote(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    %[[PROMOTED_VALUE:.*]] = inttoptr i64 42 to i8*
-; CHECK-NEXT:    ret i8* %[[PROMOTED_VALUE]]
+; CHECK-NEXT:    ret i8* inttoptr (i64 42 to i8*)
 entry:
   %a = alloca [2 x i8*], align 8
   %a.gep0 = getelementptr [2 x i8*], [2 x i8*]* %a, i32 0, i32 0
   %a.gep1 = getelementptr [2 x i8*], [2 x i8*]* %a, i32 0, i32 1
   %a.gep0.cast = bitcast i8** %a.gep0 to i64*
   %a.gep1.cast = bitcast i8** %a.gep1 to i64*
   store i64 42, i64* %a.gep1.cast
   store i64 0, i64* %a.gep0.cast
   %load = load i8*, i8** %a.gep1, align 8, !nonnull !0
   ret i8* %load
 }
 
 !0 = !{}