[GlobalOpt] Fix memset handling in global ctor evaluation (PR55859)

[nikic]

Summary

The global ctor evaluator currently handles by checking whether the memset memory is already zero, and skips it in that case. However, it only actually check the first byte of the memory being set.

This patch extends the code to check all bytes being set. This is done byte-by-byte to avoid converting undef values to zeros in larger reads. However, the handling is still not completely correct, because there might still be padding bytes (though probably this doesn't matter much in practice, as I'd expect global variable padding to be zero-initialized in practice).

Mostly fixes https://github.com/llvm/llvm-project/issues/55859.

[aeubanks]

llvm/lib/Transforms/Utils/Evaluator.cpp

453–454

why is this necessary?

463

are there any tests to test non-zero values?

[nikic]

llvm/lib/Transforms/Utils/Evaluator.cpp

453–454

This is to handle address space casts that change the index size. However, it doesn't look like this needed here (because the called API doesn't require a specific width for the offset). I'll drop this for now.

463

Nope, I've added some in https://github.com/llvm/llvm-project/commit/771c46ad291ce4c2265782c8a89a6771055c65d8.

llvm/include/llvm/Transforms/Utils/Evaluator.h

Function *getCalleeWithFormalArgs(CallBase &CB,
                                     SmallVectorImpl<Constant *> &Formals);
 
   /// Given call site and callee returns list of callee formal argument
   /// values converting them when necessary
   bool getFormalParams(CallBase &CB, Function *F,
                        SmallVectorImpl<Constant *> &Formals);
 
   Constant *ComputeLoadResult(Constant *P, Type *Ty);
+  Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,
+                              const APInt &Offset);
 
   /// As we compute SSA register values, we store their contents here. The back
   /// of the deque contains the current function and the stack contains the
   /// values in the calling frames.
   std::deque<DenseMap<Value*, Constant*>> ValueStack;
 
   /// This is used to detect recursion.  In pathological situations we could hit
   /// exponential behavior, but at least there is nothing unbounded.

llvm/lib/Transforms/Utils/Evaluator.cpp

 
 /// Return the value that would be computed by a load from P after the stores
 /// reflected by 'memory' have been performed.  If we can't decide, return null.
 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
   APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
   P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
       DL, Offset, /* AllowNonInbounds */ true));
   Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
-  auto *GV = dyn_cast<GlobalVariable>(P);
-  if (!GV)
-    return nullptr;
+  if (auto *GV = dyn_cast<GlobalVariable>(P))
+    return ComputeLoadResult(GV, Ty, Offset);
+}
 
+Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty,
+                                       const APInt &Offset) {
   auto It = MutatedMemory.find(GV);
   if (It != MutatedMemory.end())
     return It->second.read(Ty, Offset, DL);
 
   if (!GV->hasDefinitiveInitializer())
     return nullptr;
   return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
 }
if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
 
       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
           if (MSI->isVolatile()) {
             LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
                               << "intrinsic.\n");
             return false;
           }
+
+          auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength()));
+          if (!LenC) {
+            LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
+            return false;
+          }
+
           Constant *Ptr = getVal(MSI->getDest());
+          APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
+          Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
+              DL, Offset, /* AllowNonInbounds */ true));
+          auto *GV = dyn_cast<GlobalVariable>(Ptr);
+          if (!GV) {
+            LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
+            return false;
+          }
+
           Constant *Val = getVal(MSI->getValue());
-          Constant *DestVal =
-              ComputeLoadResult(getVal(Ptr), MSI->getValue()->getType());
-          if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
-            // This memset is a no-op.
-            LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
-            ++CurInst;
-            continue;
-          }
-        }
+          APInt Len = LenC->getValue();
+          while (Len != 0) {
+            Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset);
+            if (DestVal != Val) {
+              LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
+                                << Offset << " of " << *GV << ".\n");
+              return false;
+            }
+            ++Offset;
+            --Len;
+          }
+
 
         if (II->isLifetimeStartOrEnd()) {
           LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
           ++CurInst;
           continue;
         }
 
         if (II->getIntrinsicID() == Intrinsic::invariant_start) {

llvm/test/Transforms/GlobalOpt/ctor-memset.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
 ; RUN: opt -S -globalopt < %s | FileCheck %s
 
[e-mail]_ctors = appending global [8 x { i32, ptr, ptr }] [
+target datalayout = "p1:32:32"
+
[e-mail]_ctors = appending global [9 x { i32, ptr, ptr }] [
   { i32, ptr, ptr } { i32 65535, ptr @ctor0, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor1, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor2, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor3, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor4, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor5, ptr null },
   { i32, ptr, ptr } { i32 65535, ptr @ctor6, ptr null },
-  { i32, ptr, ptr } { i32 65535, ptr @ctor7, ptr null }
+  { i32, ptr, ptr } { i32 65535, ptr @ctor7, ptr null },
+  { i32, ptr, ptr } { i32 65535, ptr @ctor8, ptr null }
 ]
 
 ;.
-; CHECK: @[[LLVM_GLOBAL_CTORS:[a-zA-Z0-9_$"\\.-]+]] = appending global [2 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @ctor6, ptr null }, { i32, ptr, ptr } { i32 65535, ptr @ctor7, ptr null }]
+; CHECK: @[[LLVM_GLOBAL_CTORS:[a-zA-Z0-9_$"\\.-]+]] = appending global [3 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @ctor3, ptr null }, { i32, ptr, ptr } { i32 65535, ptr @ctor4, ptr null }, { i32, ptr, ptr } { i32 65535, ptr @ctor7, ptr null }]
 ; CHECK: @[[G0:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32 } zeroinitializer
 ; CHECK: @[[G1:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32, i32 } { i32 0, i32 0, i32 1 }
 ; CHECK: @[[G2:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32, i32 } { i32 1, i32 0, i32 0 }
 ; CHECK: @[[G3:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32 } { i32 0, i32 1 }
 ; CHECK: @[[G4:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32 } { i32 0, i32 undef }
 ; CHECK: @[[G5:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i16, i32 } { i16 0, i32 1 }
 ; CHECK: @[[G6:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32 } { i32 -1, i32 -1 }
 ; CHECK: @[[G7:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr global { i32, i32 } { i32 -1, i32 1 }
+; CHECK: @[[G8:[a-zA-Z0-9_$"\\.-]+]] = local_unnamed_addr addrspace(1) global { i32, i32 } zeroinitializer
 ;.
 
 ; memset of all-zero global
 @g0 = global { i32, i32 } zeroinitializer
-
 define internal void @ctor0() {
   call void @llvm.memset.p0.i64(ptr @g0, i8 0, i64 8, i1 false)
   ret void
 }
 
 ; memset of zero prefix
 @g1 = global { i32, i32, i32 } { i32 0, i32 0, i32 1 }
 
define internal void @ctor2() {
   call void @llvm.memset.p0.i64(ptr getelementptr (i32, ptr @g2, i64 1), i8 0, i64 8, i1 false)
   ret void
 }
 
 ; memset of some non-zero bytes
 @g3 = global { i32, i32 } { i32 0, i32 1 }
 
 define internal void @ctor3() {
+; CHECK-LABEL: @ctor3(
+; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr @g3, i8 0, i64 8, i1 false)
+; CHECK-NEXT:    ret void
+;
   call void @llvm.memset.p0.i64(ptr @g3, i8 0, i64 8, i1 false)
   ret void
 }
 
 ; memset of some undef bytes
 @g4 = global { i32, i32 } { i32 0, i32 undef }
 
 define internal void @ctor4() {
+; CHECK-LABEL: @ctor4(
+; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr @g4, i8 0, i64 8, i1 false)
+; CHECK-NEXT:    ret void
+;
   call void @llvm.memset.p0.i64(ptr @g4, i8 0, i64 8, i1 false)
   ret void
 }
 
 ; memset including padding bytes
+; FIXME: We still incorrectly optimize the memset away here, even though code
+; might access the padding.
 @g5 = global { i16, i32 } { i16 0, i32 1 }
 
 define internal void @ctor5() {
   call void @llvm.memset.p0.i64(ptr @g5, i8 0, i64 4, i1 false)
   ret void
 }
 
 ; memset of non-zero value (matching initializer)
 @g6 = global { i32, i32 } { i32 -1, i32 -1 }
 
 define internal void @ctor6() {
-; CHECK-LABEL: @ctor6(
-; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr @g6, i8 -1, i64 8, i1 false)
-; CHECK-NEXT:    ret void
-;
   call void @llvm.memset.p0.i64(ptr @g6, i8 -1, i64 8, i1 false)
   ret void
 }
 
 ; memset of non-zero value (not matching initializer)
 @g7 = global { i32, i32 } { i32 -1, i32 1 }
 
 define internal void @ctor7() {
 ; CHECK-LABEL: @ctor7(
 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr @g7, i8 -1, i64 8, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0.i64(ptr @g7, i8 -1, i64 8, i1 false)
   ret void
 }
 
+; memset of zero value in differently-sized address space
+@g8 = addrspace(1) global { i32, i32 } zeroinitializer
+
+define internal void @ctor8() {
+  call void @llvm.memset.p0.i64(ptr addrspacecast (ptr addrspace(1) @g8 to ptr), i8 0, i64 8, i1 false)
+  ret void
+}
+
 declare void @llvm.memset.p0.i64(ptr, i8, i64, i1)
 ;.
 ; CHECK: attributes #[[ATTR0:[0-9]+]] = { argmemonly nofree nounwind willreturn writeonly }
 ;.