[GlobalOpt] Disable heap SROA when GEP of the only storer is used

[MaskRay]

Summary

heap-sra-2.ll and heap-sra-phi.ll test that we can perform SROA on a global
variable with only one storer (malloc).

The code does not consider that if a GEP of the storer is used, an arbitrary
element in the allocated array can be modified and we cannot correctly represent
it with a synthesized load of the global variable (some trivial usage e.g.
hasAllZeroIndices can be represented by ad-hoc code but it is clear the
optimization is worth the code complexity). For PR50027 we will get an assertion error
when creating GEP, but we could have correctness issues as well. Simply
disable the unsafe optimization.

Fix PR50027

[aeubanks]

I'm not familiar with the terminology of "storer", so the description is confusing to me.
Trying to understand the test case and description, is the issue that Heap SROA isn't handling a store of the entire struct (as opposed to initializing the struct element by element)?

[MaskRay]

In D101245#2717561, @aeubanks wrote:

I'm not familiar with the terminology of "storer", so the description is confusing to me.

I mean the instruction which stores to the malloc return value. I don't know an appropriate term.

Trying to understand the test case and description, is the issue that Heap SROA isn't handling a store of the entire struct (as opposed to initializing the struct element by element)?

If the malloc allocates an array, say {a, b}{a, b}{a, b}{a, b}. The heap SROA makes it [a,a,a,a] [b,b,b,b] (i.e. elements are shuffled).
With GEP poking different indexes, this can either cause misoptimizations or trigger assertion failures (indexes are not properly converted). PR50027 is an assertion failure.

[aeubanks]

In D101245#2719956, @MaskRay wrote:

In D101245#2717561, @aeubanks wrote:

I'm not familiar with the terminology of "storer", so the description is confusing to me.

I mean the instruction which stores to the malloc return value. I don't know an appropriate term.

"the store into the malloc return value/pointer" seems clearer to me

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1016

seems like this doesn't take into account when the global variable is an array.
normally, if we just have a normal struct, the GEP's first operand is the GV, second operand is something like 0, and the third operand indexes into the struct itself, which is fine for SROA. having fewer than 3 operands can directly reference the struct
with an array, we need to account for an extra index to index into the array

[MaskRay]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1016

Do you have specific suggestion to the diff? :)

I am thinking the value of array heap SROA is low but I don't want to just remove the implementation, so drop GEP - see the tests like heap-sra-phi.ll, heap SROA still works if the function allocates and forgets the array.

[aeubanks]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1016

maybe check the GV type to see if it's an array, and in that case use 4 instead of 3?
supporting GEPs seems natural, I'm not sure why we wouldn't want to, seems like code would probably use GEPs into global values to do things

[MaskRay]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1016

For heap-sra-negative.ll, GV is @X = internal global %struct.foo* null (decayed array). Inst->getNumOperands() >= 4 cannot catch the case.

This function is only used to check CI - the only store instruction. Load instructions are not subject to the constraint, so dropping the support here will not punish the load site GEP.

[MaskRay]

🙄

[aeubanks]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1016

Inst->getNumOperands() >= 4 does catch the case, heap SROA doesn't trigger in your test case when we change 3 to 4.
I'm pretty sure "// Must index into the array and into the struct." is what I explained in the first comment of this thread.

This function is only used to check CI - the only store instruction.

CI is the malloc call, not the store (unless I'm misunderstanding your comment).

Load instructions are not subject to the constraint, so dropping the support here will not punish the load site GEP.

I don't understand. With this patch, if there's a GEP of the malloc anywhere, even if it's used for a load, it gives up.

But it does look like you're right and this is probably never actually hit in practice. Running your example through -O2, the store gets split by instcombine and the global isn't considered "once stored" when GlobalOpt runs. I bootstrapped LLVM with a crash in PerformHeapAllocSRoA and it was never hit. We should either go with the 3 -> 4, or completely remove heap SROA.

[MaskRay]

Thanks for testing that this does not trigger during bootstrapping. Now I am more confident that we should drop the current implementation: D102257.
I have kept some tests in case someone wants to create a better implementation in the future.

[MaskRay]

Abandon in favor of D102257 (removing heap SROA).

llvm/lib/Transforms/IPO/GlobalOpt.cpp

for (const User *U : V->users()) {
     }
 
     if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
         return false;  // Storing the pointer itself... bad.
       continue; // Otherwise, storing through it, or storing into GV... fine.
     }
 
-    // Must index into the array and into the struct.
-    if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) {
-      if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
-        return false;
-      continue;
-    }
+    // Cannot handle GEP.
+    if (isa<GetElementPtrInst>(Inst))
 
     if (const PHINode *PN = dyn_cast<PHINode>(Inst)) {
       // PHIs are ok if all uses are ok.  Don't infinitely recurse through PHI
       // cycles.
       if (PHIs.insert(PN).second)
         if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs))
           return false;
       continue;

llvm/test/Transforms/GlobalOpt/heap-sra-2-no-null-opt.ll

 ; RUN: opt < %s -globalopt -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 %struct.foo = type { i32, i32 }
 @X = internal global %struct.foo* null    ; <%struct.foo**> [#uses=2]
 ; CHECK: @X
 ; CHECK-NOT: @X.f0
 
 define void @bar(i32 %Size) nounwind noinline #0 {
 entry:
   %malloccall = tail call i8* @malloc(i64 8000000) ; <i8*> [#uses=1]
-  %0 = bitcast i8* %malloccall to [1000000 x %struct.foo]* ; <[1000000 x %struct.foo]*> [#uses=1]
-  %.sub = getelementptr [1000000 x %struct.foo], [1000000 x %struct.foo]* %0, i32 0, i32 0    ; <%struct.foo*> [#uses=1]
+  %.sub = bitcast i8* %malloccall to %struct.foo*
   store %struct.foo* %.sub, %struct.foo** @X, align 4
   ret void
 }
 
 declare noalias i8* @malloc(i64)
 
 define i32 @baz() nounwind readonly noinline #0 {
 bb1.thread:

llvm/test/Transforms/GlobalOpt/heap-sra-2.ll

 ; RUN: opt < %s -globalopt -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
   %struct.foo = type { i32, i32 }
 @X = internal global %struct.foo* null    ; <%struct.foo**> [#uses=2]
 ; CHECK: @X.f0
 ; CHECK: @X.f1
 
 define void @bar(i32 %Size) nounwind noinline {
 entry:
   %malloccall = tail call i8* @malloc(i64 8000000) ; <i8*> [#uses=1]
-  %0 = bitcast i8* %malloccall to [1000000 x %struct.foo]* ; <[1000000 x %struct.foo]*> [#uses=1]
-  %.sub = getelementptr [1000000 x %struct.foo], [1000000 x %struct.foo]* %0, i32 0, i32 0    ; <%struct.foo*> [#uses=1]
+  %.sub = bitcast i8* %malloccall to %struct.foo*
   store %struct.foo* %.sub, %struct.foo** @X, align 4
   ret void
 }
 
 declare noalias i8* @malloc(i64)
 
 define i32 @baz() nounwind readonly noinline {
 bb1.thread:

llvm/test/Transforms/GlobalOpt/heap-sra-negative.ll

+; RUN: opt < %s -S -passes=globalopt | FileCheck %s
+
+;; PR50027: Suppress SROA because we cannot represent GEP of the only storer.
+; CHECK: @X = internal unnamed_addr global %struct.foo* null
+
+target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
+
+%struct.foo = type { i32, i32 }
+
+@X = internal global %struct.foo* null
+
+declare noalias i8* @malloc(i64)
+
+define void @test(i32 %Size) {
+entry:
+  %buf = tail call i8* @malloc(i64 8000000)
+  %buf1 = bitcast i8* %buf to [1000000 x %struct.foo]*
+
+  ;; GEP of the only storer.
+  %buf.gep = getelementptr [1000000 x %struct.foo], [1000000 x %struct.foo]* %buf1, i32 0, i32 0
+  store %struct.foo zeroinitializer, %struct.foo* %buf.gep, align 4
+
+  store %struct.foo* %buf.gep, %struct.foo** @X, align 4
+  ret void
+}
+
+define i32 @user() {
+entry:
+  %unused = load %struct.foo*, %struct.foo** @X, align 4
+  ret i32 0
+}

llvm/test/Transforms/GlobalOpt/heap-sra-phi-no-null-opt.ll

 ; RUN: opt < %s -globalopt -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 %struct.foo = type { i32, i32 }
 
 @X = internal global %struct.foo* null    ; <%struct.foo**> [#uses=2]
 ; CHECK: @X
 ; CHECK-NOT: @X.f0
 
 define void @bar(i32 %Size) nounwind noinline #0 {
 ;  CHECK-LABEL: @bar(
 entry:
   %malloccall = tail call i8* @malloc(i64 8000000) ; <i8*> [#uses=1]
-  %tmp = bitcast i8* %malloccall to [1000000 x %struct.foo]* ; <[1000000 x %struct.foo]*> [#uses=1]
-  %.sub = getelementptr [1000000 x %struct.foo], [1000000 x %struct.foo]* %tmp, i32 0, i32 0    ; <%struct.foo*> [#uses=1]
+  %.sub = bitcast i8* %malloccall to %struct.foo*
   store %struct.foo* %.sub, %struct.foo** @X, align 4
   ret void
 }
 
 declare noalias i8* @malloc(i64)
 
 define i32 @baz() nounwind readonly noinline #0 {
 ; CHECK-LABEL: @baz(

llvm/test/Transforms/GlobalOpt/heap-sra-phi.ll

 ; RUN: opt < %s -globalopt -S | FileCheck %s
 ; CHECK: tmp.f1 = phi i32*
 ; CHECK: tmp.f0 = phi i32*
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
   %struct.foo = type { i32, i32 }
 @X = internal global %struct.foo* null    ; <%struct.foo**> [#uses=2]
 
 define void @bar(i32 %Size) nounwind noinline {
 entry:
   %malloccall = tail call i8* @malloc(i64 8000000) ; <i8*> [#uses=1]
-  %tmp = bitcast i8* %malloccall to [1000000 x %struct.foo]* ; <[1000000 x %struct.foo]*> [#uses=1]
-  %.sub = getelementptr [1000000 x %struct.foo], [1000000 x %struct.foo]* %tmp, i32 0, i32 0    ; <%struct.foo*> [#uses=1]
+  %.sub = bitcast i8* %malloccall to %struct.foo*
   store %struct.foo* %.sub, %struct.foo** @X, align 4
   ret void
 }
 
 declare noalias i8* @malloc(i64)
 
 define i32 @baz() nounwind readonly noinline {
 bb1.thread: