[GlobalOpt] Ignore only loaded / only stored global parts in global SRA heuristic

[nikic]

Summary

When limiting the number of parts we split a global into, ignore any parts that are either only loaded or only stored, because we expect these to be optimized away after SRA.

This is intended as an alternative to D129525.

[fhahn]

I just tried this on the original reproducer and it's not sufficient unfortunately. I'll extract an updated reproducer.

[fhahn]

I added a reduced test case from https://github.com/llvm/llvm-project/issues/56762 which has a single store to the global which makes the logic here not trigger unfortunately: https://github.com/llvm/llvm-project/commit/91e67c074922cc667fa1c43fc1f01acb96faa0f9

To solve this in general, we could probably track which fields of a global are never modified and then ignore such loads from the count. I'm still wondering if we should re-introduce the previous logic until we are able to completely address this properly to avoid regressions.

[nikic]

I've updated the patch to treat loads and stores symmetrically: We only count the part if it is both loaded and stored. In other cases, we expect it to be optimized away.

[fhahn]

In D129857#3852044, @nikic wrote:

I've updated the patch to treat loads and stores symmetrically: We only count the part if it is both loaded and stored. In other cases, we expect it to be optimized away.

Thanks, I finally had some time to track down the cases missed by the current version of the heuristic for the larger reproducer. I added a set of test case, rebased the change here (https://github.com/fhahn/llvm-project/commit/1053ab2c24811bfc2bdf4b8b0bf5da15c2772de3) and put up D144468, D144476, D144477. With those, we get the expected optimizations without D129525. So I think we should move ahead with this patch and the follow-ups.

[nikic]

Rebase

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/IPO/GlobalOpt.cpp

339

might be good to document the struct

llvm/lib/Transforms/IPO/GlobalOpt.cpp

static bool CleanupConstantGlobalUsers(GlobalVariable *GV,
   }
 
   Changed |=
       RecursivelyDeleteTriviallyDeadInstructionsPermissive(MaybeDeadInsts);
   GV->removeDeadConstantUsers();
   return Changed;
 }
 
 struct GlobalPart {
   Type *Ty;
+  bool IsLoaded = false;
 };
 
 /// Look at all uses of the global and determine which (offset, type) pairs it
 /// can be split into.
 static bool collectSRATypes(DenseMap<uint64_t, GlobalPart> &Parts,
                             GlobalValue *GV, const DataLayout &DL) {
   SmallVector<Use *, 16> Worklist;
   SmallPtrSet<Use *, 16> Visited;
if (Value *Ptr = getLoadStorePointerOperand(V)) {
         return false;
 
       // TODO: We currently require that all accesses at a given offset must
       // use the same type. This could be relaxed.
       Type *Ty = getLoadStoreType(V);
       auto It = Parts.try_emplace(Offset.getZExtValue(), GlobalPart{Ty}).first;
       if (Ty != It->second.Ty)
         return false;
+      It->second.IsLoaded |= isa<LoadInst>(V);
       continue;
     }
 
     // Ignore dead constant users.
     if (auto *C = dyn_cast<Constant>(V)) {
       if (!isSafeToDestroyConstant(C))
         return false;
       continue;
static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
   DenseMap<uint64_t, GlobalPart> Parts;
   if (!collectSRATypes(Parts, GV, DL) || Parts.empty())
     return nullptr;
 
   // Make sure we don't SRA back to the same type.
   if (Parts.size() == 1 && Parts.begin()->second.Ty == GV->getValueType())
     return nullptr;
 
-  // Don't perform SRA if we would have to split into many globals.
-  if (Parts.size() > 16)
+  // Don't perform SRA if we would have to split into many globals. Ignore
+  // parts that are never loaded, because we expect them to be optimized away.
+  unsigned NumParts = count_if(Parts, [](const auto &Pair) {
+    return Pair.second.IsLoaded;
+  });
+  if (NumParts > 16)
     return nullptr;
 
   // Sort by offset.
   SmallVector<std::pair<uint64_t, Type *>, 16> TypesVector;
   for (const auto &Pair : Parts)
     TypesVector.push_back({Pair.first, Pair.second.Ty});
   sort(TypesVector,
        [](const auto &A, const auto &B) { return A.first < B.first; });

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
-; CHECK: @[[GLOBAL_ARRAY_IN_STRUCT:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [[STRUCT_WITH_ARRAY:%.*]] zeroinitializer
-; CHECK: @[[GLOBAL_ARRAY:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [100 x i64] zeroinitializer
-;.
 define internal void @read_struct() {
 ; CHECK-LABEL: @read_struct(
-; 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 void @write_struct() {
 ; CHECK-LABEL: @write_struct(
-; 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 null, 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 @read_struct()
 ; 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 null, ptr getelementptr inbounds (%struct.widget, ptr @global, i64 0, i32 4), align 8

 
 
 %struct.with.array = type { [100 x i64], i64 }
 
 @global.array_in_struct = internal global %struct.with.array zeroinitializer
 
 define internal void @read_non_array_field() {
 ; CHECK-LABEL: @read_non_array_field(
-; CHECK-NEXT:    [[TMP:%.*]] = load i64, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY:%.*]], ptr @global.array_in_struct, i64 0, i32 1), align 8
 ; CHECK-NEXT:    ret void
 ;
   %tmp = load i64, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 1), align 8
   ret void
 }
 
 define void @store_to_struct_array() {
 ; CHECK-LABEL: @store_to_struct_array(
-; CHECK-NEXT:    store i64 0, ptr @global.array_in_struct, align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY:%.*]], ptr @global.array_in_struct, i64 0, i32 0, i32 1), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 2), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 3), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 4), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 5), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 6), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 7), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 8), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 9), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 10), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 11), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 12), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 13), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 14), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([[STRUCT_WITH_ARRAY]], ptr @global.array_in_struct, i64 0, i32 0, i32 15), align 8
 ; CHECK-NEXT:    tail call fastcc void @read_non_array_field()
 ; CHECK-NEXT:    ret void
 ;
   store i64 0, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 0, i32 0), align 8
   store i64 0, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 0, i32 1), align 8
   store i64 0, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 0, i32 2), align 8
   store i64 0, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 0, i32 3), align 8
   store i64 0, ptr getelementptr inbounds (%struct.with.array, ptr @global.array_in_struct, i64 0, i32 0, i32 4), align 8
;
   tail call void @read_non_array_field()
   ret void
 }
 
 @global.array = internal global [100 x i64] zeroinitializer
 
 define internal void @read_array() {
 ; CHECK-LABEL: @read_array(
-; CHECK-NEXT:    [[TMP:%.*]] = load i64, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 99), align 8
 ; CHECK-NEXT:    ret void
 ;
   %tmp = load i64, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 99), align 8
   ret void
 }
 
 define void @store_to_array() {
 ; CHECK-LABEL: @store_to_array(
-; CHECK-NEXT:    store i64 0, ptr @global.array, align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 1), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 2), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 3), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 4), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 5), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 6), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 7), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 8), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 9), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 10), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 11), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 12), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 13), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 14), align 8
-; CHECK-NEXT:    store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 15), align 8
 ; CHECK-NEXT:    tail call fastcc void @read_array()
 ; CHECK-NEXT:    ret void
 ;
   store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 0), align 8
   store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 1), align 8
   store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 2), align 8
   store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 3), align 8
   store i64 0, ptr getelementptr inbounds ([100 x i64], ptr @global.array, i64 0, i32 4), align 8