[GlobalOpt] Drop SRA split limit for struct types.

[fhahn]

Summary

4796b4ae7bccc7 limited the SRA to 16 types for all globals, while the
code previously did not have a similar limit for globals with
struct-typed initializers AFAICT.

This is causing notable size regressions for some large workloads. This
patch skips the size check for struct types, similar to code before
4796b4ae7bccc7 to recover the regression.

[nikic]

This will also bypass the check if you have an array that is nested inside a struct. Besides, I don't think we should be making decisions based on the global value type here, which is a another vacuous concept that shouldn't exist (e.g. in rust the global type will often be something like [N x i8], in "bag of bytes" representation).

Does raising the limit to the next power of two cover your test case?

[fhahn]

In D129525#3644388, @nikic wrote:

This will also bypass the check if you have an array that is nested inside a struct. Besides, I don't think we should be making decisions based on the global value type here, which is a another vacuous concept that shouldn't exist (e.g. in rust the global type will often be something like [N x i8], in "bag of bytes" representation).

Right , I think this should be similar to the previous cut-off for struct with arrays inside, e.g.: https://llvm.godbolt.org/z/crje3aYzW . I added additional tests with a struct containing an array and a plain array.

I agree that the type shouldn't really matter. But I think changing the way the cut-off is handled should be done independently of the change to use an offset-based approach.

Does raising the limit to the next power of two cover your test case?

Unfortunately the struct has stores to 100+ fields in the workload.

[nikic]

@fhahn I think your last update is missing the code changes :)

I assume that you don't actually care about SRA as such, but rather about some follow-on transforms it enables. I've been thinking that we might want to make GlobalOpt in general work on the SRAd representation internally, which might remove the need to actually materialize it in some cases. So if some parts of the global are never written, it will certainly always be profitable to replace them with (part of) the initializer, regardless of how many parts there are. The limit is only relevant for cases where we actually do leave behind the globals. Do you know which optimization in particular is important for your workload?

[fhahn]

In D129525#3649361, @nikic wrote:

@fhahn I think your last update is missing the code changes :)

I didn't make any code changes to the original version and it looks like the original code change is still there. Am I missing something? :)

I assume that you don't actually care about SRA as such, but rather about some follow-on transforms it enables. I've been thinking that we might want to make GlobalOpt in general work on the SRAd representation internally, which might remove the need to actually materialize it in some cases. So if some parts of the global are never written, it will certainly always be profitable to replace them with (part of) the initializer, regardless of how many parts there are. The limit is only relevant for cases where we actually do leave behind the globals. Do you know which optimization in particular is important for your workload?

Yeah, ideally SRA would not materialize each transform it applies straight away, e.g. for the test cases the split up globals will get removed after materializing them.

I think the main regression comes from SRA not removing stores of function pointers that are never read, which in turn prevents LLVM from removing those functions.

[nikic]

In D129525#3649499, @fhahn wrote:

In D129525#3649361, @nikic wrote:

@fhahn I think your last update is missing the code changes :)

I didn't make any code changes to the original version and it looks like the original code change is still there. Am I missing something? :)

Oh sorry, I misread your comment. I thought you wanted to add a check for nested arrays, but you were only referring to new tests.

I think the main regression comes from SRA not removing stores of function pointers that are never read, which in turn prevents LLVM from removing those functions.

Okay, that's a particularly simple case. It's probably worthwhile to give skipping parts that are only stored a try, as we expect them to be dropped (it's not strictly guaranteed due to leak checker roots, but close enough). I can take a look.

[fhahn]

Just a rebase on top of a test added in 91e67c074922cc667fa1c43fc1f01acb96faa0f9 that can't be handled by D129857.

[fhahn]

ping :)

[fhahn]

Ping, any additional thoughts on how to best resolve the regression soon?

[nikic]

I've updated D129857 to handle the new case -- I'd still generally prefer not to special case struct types if we can avoid it.

[fhahn]

We should be able to handle all cases with D129857 + follow-on changes. let's go down that route!

llvm/lib/Transforms/IPO/GlobalOpt.cpp

static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
   DenseMap<uint64_t, Type *> Types;
   if (!collectSRATypes(Types, GV, DL) || Types.empty())
     return nullptr;
 
   // Make sure we don't SRA back to the same type.
   if (Types.size() == 1 && Types.begin()->second == GV->getValueType())
     return nullptr;
 
+  Constant *OrigInit = GV->getInitializer();
   // Don't perform SRA if we would have to split into many globals.
-  if (Types.size() > 16)
+  if (!isa<StructType>(OrigInit->getType()) && Types.size() > 16)
     return nullptr;
 
   // Sort by offset.
   SmallVector<std::pair<uint64_t, Type *>, 16> TypesVector;
   append_range(TypesVector, Types);
   sort(TypesVector,
        [](const auto &A, const auto &B) { return A.first < B.first; });
 
   // Check that the types are non-overlapping.
   uint64_t Offset = 0;
   for (const auto &Pair : TypesVector) {
     // Overlaps with previous type.
     if (Pair.first < Offset)
       return nullptr;
 
     Offset = Pair.first + DL.getTypeAllocSize(Pair.second);
   }
 
   // Some accesses go beyond the end of the global, don't bother.
   if (Offset > DL.getTypeAllocSize(GV->getValueType()))
     return nullptr;
 
   // Collect initializers for new globals.
-  Constant *OrigInit = GV->getInitializer();
   DenseMap<uint64_t, Constant *> Initializers;
   for (const auto &Pair : Types) {
     Constant *NewInit = ConstantFoldLoadFromConst(OrigInit, Pair.second,
                                                   APInt(64, Pair.first), DL);
     if (!NewInit) {
       LLVM_DEBUG(dbgs() << "Global SRA: Failed to evaluate initializer of "
                         << *GV << " with type " << *Pair.second << " at offset "
                         << Pair.first << "\n");

llvm/test/Transforms/GlobalOpt/sra-many-stores.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
 ; RUN: opt -passes=globalopt -S %s | FileCheck %s
 
 %struct.widget = type { ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr }
 
 @global = internal global %struct.widget zeroinitializer
 
-;.
-; CHECK: @[[GLOBAL:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [[STRUCT_WIDGET:%.*]] zeroinitializer
-;.
 define internal i32 @fn1() {
-; CHECK-LABEL: @fn1(
-; CHECK-NEXT:    ret i32 0
-;
   ret i32 0
 }
 
 define internal void @fn2() {
 ; CHECK-LABEL: @fn2(
-; CHECK-NEXT:    [[TMP:%.*]] = load ptr, ptr getelementptr inbounds ([[STRUCT_WIDGET:%.*]], ptr @global, i64 0, i32 16), align 8
 ; CHECK-NEXT:    ret void
 ;
   %tmp = load ptr, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 16), align 8
   ret void
 }
 
 define internal void @write() {
 ; CHECK-LABEL: @write(
-; CHECK-NEXT:    store ptr null, ptr @global, align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET:%.*]], ptr @global, i64 0, i32 1), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 2), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 3), align 8
-; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 4), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 5), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 6), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 7), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 8), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 9), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 10), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 11), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 12), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 13), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 14), align 8
-; CHECK-NEXT:    store ptr null, ptr getelementptr inbounds ([[STRUCT_WIDGET]], ptr @global, i64 0, i32 15), align 8
 ; CHECK-NEXT:    tail call fastcc void @fn2()
 ; CHECK-NEXT:    ret void
 ;
   store ptr null, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 0), align 8
   store ptr null, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 1), align 8
   store ptr null, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 2), align 8
   store ptr null, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 3), align 8
   store ptr @fn1, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 4), align 8