[GlobalOpt] Use generic type when converting malloc to global

[nikic]

Summary

The malloc to global transform currently determines the type of the global by looking at bitcasts of the malloc. This is limited (the transform fails if there are multiple different types) and incompatible with opaque pointers.

My initial approach was to construct an appropriate struct type based on usage in loads/stores (and I can go back to that if desired). What this patch does instead is to always create an [i8 x AllocSize] global, without trying to guess types at all.

This does mean that other transforms that require a certain global type may break. I fixed one such case in D117034, which is the only one that came up in tests. From a philosophical perspective, I think that fixing transforms to not depend on global type is generally preferable.

[reames]

Ok, we collided. Clearly we both thought this was reasonable. I think I like my version (D117249) slightly better due to the use of getObjectSize. Can you land your test and approve that one?

[nikic]

Use getObjectSize().

[nikic]

I've marked this as dependent on D117223, see the globalsra-generic-type.ll test there for why. Without that change, we would not be able to perform global SRA on the produced global. There are other transforms that might fail, but I think having global SRA should go a long way towards avoiding regressions, as it will end up splitting the global into natural types, and all other optimizations should apply at that point.

@reames I can't precommit the test because it currently crashes. I've folded the getObjectSize() change into here.

[nikic]

As the SRA patch is now a dependency, update tests accordingly (malloc-promote-opaque-ptr.ll is affected -- the non-overlapping cases get decomposed into individual globals).

[reames]

LGTM with minor comments.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1078

I think we also want the size > 0 guard. I don't believe that case is reachable for any of our current allocators, but if we generalizing..

1175

Please add back the first part of this comment.

[nikic]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1175

Probably got lost in the diff, but this comment has been moved to the top of the function, as an overall description of the transform.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

if (Instruction *I = dyn_cast<Instruction>(*UI++))
       }
 }
 
 /// This function takes the specified global variable, and transforms the
 /// program as if it always contained the result of the specified malloc.
 /// Because it is always the result of the specified malloc, there is no reason
 /// to actually DO the malloc.  Instead, turn the malloc into a global, and any
 /// loads of GV as uses of the new global.
 static GlobalVariable *
-OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
-                              ConstantInt *NElements, const DataLayout &DL,
+OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI,
+                              ConstantInt *AllocSize, const DataLayout &DL,
                               TargetLibraryInfo *TLI) {
   LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CI
                     << '\n');
 
-  Type *GlobalType;
-  if (NElements->getZExtValue() == 1)
-    GlobalType = AllocTy;
-  else
-    // If we have an array allocation, the global variable is of an array.
-    GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
+  // Create global of type [i8 x AllocSize].
+  Type *GlobalType = ArrayType::get(
+      Type::getInt8Ty(GV->getContext()), AllocSize->getZExtValue());
 
   // Create the new global variable.  The contents of the malloc'd memory is
   // undefined, so initialize with an undef value.
   GlobalVariable *NewGV = new GlobalVariable(
       *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage,
       UndefValue::get(GlobalType), GV->getName() + ".body", nullptr,
       GV->getThreadLocalMode());
 
for (const Use &VUse : V->uses()) {
 
       return false;
     }
   }
 
   return true;
 }
 
-/// getMallocType - Returns the PointerType resulting from the malloc call.
-/// The PointerType depends on the number of bitcast uses of the malloc call:
-///   0: PointerType is the calls' return type.
-///   1: PointerType is the bitcast's result type.
-///  >1: Unique PointerType cannot be determined, return NULL.
-static PointerType *getMallocType(const CallInst *CI,
-                                  const TargetLibraryInfo *TLI) {
-  assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
-
-  PointerType *MallocType = nullptr;
-  unsigned NumOfBitCastUses = 0;
-
-  // Determine if CallInst has a bitcast use.
-  for (const User *U : CI->users())
-    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
-      MallocType = cast<PointerType>(BCI->getDestTy());
-      NumOfBitCastUses++;
-    }
-
-  // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
-  if (NumOfBitCastUses == 1)
-    return MallocType;
-
-  // Malloc call was not bitcast, so type is the malloc function's return type.
-  if (NumOfBitCastUses == 0)
-    return cast<PointerType>(CI->getType());
-
-  // Type could not be determined.
-  return nullptr;
-}
-
-/// getMallocAllocatedType - Returns the Type allocated by malloc call.
-/// The Type depends on the number of bitcast uses of the malloc call:
-///   0: PointerType is the malloc calls' return type.
-///   1: PointerType is the bitcast's result type.
-///  >1: Unique PointerType cannot be determined, return NULL.
-static Type *getMallocAllocatedType(const CallInst *CI,
-                                    const TargetLibraryInfo *TLI) {
-  PointerType *PT = getMallocType(CI, TLI);
-  return PT ? PT->getElementType() : nullptr;
-}
-
-static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
-                               const TargetLibraryInfo *TLI,
-                               bool LookThroughSExt = false) {
-  if (!CI)
-    return nullptr;
-
-  // The size of the malloc's result type must be known to determine array size.
-  Type *T = getMallocAllocatedType(CI, TLI);
-  if (!T || !T->isSized())
-    return nullptr;
-
-  unsigned ElementSize = DL.getTypeAllocSize(T);
-  if (StructType *ST = dyn_cast<StructType>(T))
-    ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
-
-  // If malloc call's arg can be determined to be a multiple of ElementSize,
-  // return the multiple.  Otherwise, return NULL.
-  Value *MallocArg = CI->getArgOperand(0);
-  Value *Multiple = nullptr;
-  if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
-    return Multiple;
-
-  return nullptr;
-}
-
-/// getMallocArraySize - Returns the array size of a malloc call.  If the
-/// argument passed to malloc is a multiple of the size of the malloced type,
-/// then return that multiple.  For non-array mallocs, the multiple is
-/// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
-/// determined.
-static Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
-                                 const TargetLibraryInfo *TLI,
-                                 bool LookThroughSExt) {
-  assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
-  return computeArraySize(CI, DL, TLI, LookThroughSExt);
-}
-
-
-/// This function is called when we see a pointer global variable with a single
-/// value stored it that is a malloc or cast of malloc.
+/// If we have a global that is only initialized with a fixed size malloc,
+/// transform the program to use global memory instead of malloc'd memory.
+/// This eliminates dynamic allocation, avoids an indirection accessing the
+/// data, and exposes the resultant global to further GlobalOpt.
 static bool tryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI,
-                                               Type *AllocTy,
                                                AtomicOrdering Ordering,
                                                const DataLayout &DL,
                                                TargetLibraryInfo *TLI) {
-  // If this is a malloc of an abstract type, don't touch it.
-  if (!AllocTy->isSized())
+  assert(isMallocLikeFn(CI, TLI) && "Must be malloc-like call");
+
+  // TODO: Don't assume location of size argument.
+  ConstantInt *AllocSize = dyn_cast<ConstantInt>(CI->getArgOperand(0));
+  if (!AllocSize)
+    return false;
+
+  // Restrict this transformation to only working on small allocations
+  // (2048 bytes currently), as we don't want to introduce a 16M global or
+  // something.
+  if (AllocSize->getValue().uge(2048))
     return false;
 
   // We can't optimize this global unless all uses of it are *known* to be
   // of the malloc value, not of the null initializer value (consider a use
   // that compares the global's value against zero to see if the malloc has
   // been reached).  To do this, we check to see if all uses of the global
   // would trap if the global were null: this proves that they must all
   // happen after the malloc.
   if (!allUsesOfLoadedValueWillTrapIfNull(GV))
     return false;
 
   // We can't optimize this if the malloc itself is used in a complex way,
   // for example, being stored into multiple globals.  This allows the
   // malloc to be stored into the specified global, loaded, gep, icmp'd.
   // These are all things we could transform to using the global for.
   if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV))
     return false;
 
-  // If we have a global that is only initialized with a fixed size malloc,
-  // transform the program to use global memory instead of malloc'd memory.
-  // This eliminates dynamic allocation, avoids an indirection accessing the
-  // data, and exposes the resultant global to further GlobalOpt.
-  // We cannot optimize the malloc if we cannot determine malloc array size.
-  Value *NElems = getMallocArraySize(CI, DL, TLI, true);
-  if (!NElems)
-    return false;
-
-  if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
-    // Restrict this transformation to only working on small allocations
-    // (2048 bytes currently), as we don't want to introduce a 16M global or
-    // something.
-    if (NElements->getZExtValue() * DL.getTypeAllocSize(AllocTy) < 2048) {
-      OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
-      return true;
-    }
+  OptimizeGlobalAddressOfMalloc(GV, CI, AllocSize, DL, TLI);
 
-  return false;
-}
-
 // Try to optimize globals based on the knowledge that only one value (besides
 // its initializer) is ever stored to the global.
 static bool
 optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
                          AtomicOrdering Ordering, const DataLayout &DL,
                          function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
   // Ignore no-op GEPs and bitcasts.
   StoredOnceVal = StoredOnceVal->stripPointerCasts();
if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
         SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
 
       // Optimize away any trapping uses of the loaded value.
       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, GetTLI))
         return true;
     } else if (isMallocLikeFn(StoredOnceVal, GetTLI)) {
       if (auto *CI = dyn_cast<CallInst>(StoredOnceVal)) {
         auto *TLI = &GetTLI(*CI->getFunction());
-        Type *MallocType = getMallocAllocatedType(CI, TLI);
-        if (MallocType && tryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType,
-                                                             Ordering, DL, TLI))
+        if (tryToOptimizeStoreOfMallocToGlobal(GV, CI, Ordering, DL, TLI))
           return true;
       }
     }
   }
 
   return false;
 }
 

llvm/test/Transforms/GlobalOpt/2021-08-03-StoreOnceLoadMultiCasts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=globalopt -S < %s | FileCheck %s
 ; RUN: opt -passes=globalopt -S < %s | FileCheck %s
 
 @g = internal global i32* null, align 8
 
 define signext i32 @f() local_unnamed_addr {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    call void @f1()
-; CHECK-NEXT:    store i32 1, i32* @g.body, align 4
+; CHECK-NEXT:    store i32 1, i32* bitcast ([4 x i8]* @g.body to i32*), align 4
 ; CHECK-NEXT:    call void @f1()
-; CHECK-NEXT:    store i8 2, i8* bitcast (i32* @g.body to i8*), align 4
+; CHECK-NEXT:    store i8 2, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @g.body, i32 0, i32 0), align 4
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   %call = call i8* @malloc(i64 4)
   %b = bitcast i8* %call to i32*
   store i32* %b, i32** @g, align 8
   call void @f1()
   %0 = load i32*, i32** @g, align 8
   store i32 1, i32* %0, align 4
   call void @f1()
   %1 = load i8*, i8** bitcast (i32** @g to i8**), align 8
   store i8 2, i8* %1, align 4
   ret i32 1
 }
 
 define signext i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CALL:%.*]] = call signext i32 @f()
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @g.body, align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* bitcast ([4 x i8]* @g.body to i32*), align 4
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %call = call signext i32 @f()
   %0 = load i32*, i32** @g, align 8
   %1 = load i32, i32* %0, align 4
   ret i32 %1
 }
 
 declare noalias align 16 i8* @malloc(i64)
 declare void @f1()

llvm/test/Transforms/GlobalOpt/malloc-promote-opaque-ptr.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
+; RUN: opt -S -globalopt -opaque-pointers < %s | FileCheck %s
+
+@g1 = internal global ptr null
+@g2 = internal global ptr null
+@g3 = internal global ptr null
+
+declare noalias i8* @malloc(i64)
+
+;.
+; CHECK: @[[G1_BODY:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [8 x i8] undef
+; CHECK: @[[G2_BODY:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [16 x i8] undef
+; CHECK: @[[G3_BODY:[a-zA-Z0-9_$"\\.-]+]] = internal unnamed_addr global [8 x i8] undef
+;.
+define void @test_store(i64 %a, i32 %b) {
+; CHECK-LABEL: @test_store(
+; CHECK-NEXT:    store i64 [[A:%.*]], ptr @g1.body, align 4
+; CHECK-NEXT:    store i32 [[B:%.*]], ptr @g2.body, align 4
+; CHECK-NEXT:    store i32 [[B]], ptr getelementptr inbounds ([16 x i8], ptr @g2.body, i64 0, i64 4), align 4
+; CHECK-NEXT:    store i32 [[B]], ptr getelementptr inbounds ([16 x i8], ptr @g2.body, i64 0, i64 10), align 2
+; CHECK-NEXT:    store i64 [[A]], ptr @g3.body, align 4
+; CHECK-NEXT:    store i32 [[B]], ptr @g3.body, align 4
+; CHECK-NEXT:    ret void
+;
+  %m1 = call ptr @malloc(i64 8)
+  store ptr %m1, ptr @g1
+  %a1 = load ptr, ptr @g1
+
+  %m2 = call ptr @malloc(i64 16)
+  store ptr %m2, ptr @g2
+  %a2 = load ptr, ptr @g2
+
+  %m3 = call ptr @malloc(i64 8)
+  store ptr %m3, ptr @g3
+  %a3 = load ptr, ptr @g3
+
+  store i64 %a, ptr %a1
+
+  ; Access types at different offsets.
+  store i32 %b, ptr %a2
+  %a2.4 = getelementptr i8, ptr %a2, i64 4
+  store i32 %b, ptr %a2.4
+  %a2.10 = getelementptr i8, ptr %a2, i64 10
+  store i32 %b, ptr %a2.10, align 2
+
+  ; Access two different types at the same offset.
+  store i64 %a, ptr %a3
+  store i32 %b, ptr %a3
+
+  ret void
+}
+
+define void @test_load() {
+; CHECK-LABEL: @test_load(
+; CHECK-NEXT:    [[TMP1:%.*]] = load i64, ptr @g1.body, align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr @g2.body, align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr getelementptr inbounds ([16 x i8], ptr @g2.body, i64 0, i64 4), align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr getelementptr inbounds ([16 x i8], ptr @g2.body, i64 0, i64 10), align 2
+; CHECK-NEXT:    [[TMP5:%.*]] = load i64, ptr @g3.body, align 4
+; CHECK-NEXT:    ret void
+;
+  %a1 = load ptr, ptr @g1
+  load i64, ptr %a1
+
+  %a2 = load ptr, ptr @g2
+  load i32, ptr %a2
+  %a2.4 = getelementptr i8, ptr %a2, i64 4
+  load i32, ptr %a2.4
+  %a2.10 = getelementptr i8, ptr %a2, i64 10
+  load i32, ptr %a2.10, align 2
+
+  %a3 = load ptr, ptr @g3
+  load i64, ptr %a3
+  ret void
+}