[DSE] Eliminate zero memset after calloc

[xbolva00]

Summary

Solves PR11896

As noted, this can be improved futher (calloc -> malloc) in some cases. But for know, this is the first step.

[xbolva00]

As I worked on this PR, I found a regression where we fail to eliminate stores/memset due to inaccessiblememonly on calloc. (store_zero_after_calloc_inaccessiblememonly & zero_memset_after_calloc_inaccessiblememonly)

Please check https://bugs.llvm.org/show_bug.cgi?id=50143 (but this patch can be reviewed and pushed separately).

[nikic]

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1783

nit: unnecessary newline.

[xbolva00]

In D101391#2720758, @nikic wrote:

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

zero_memset_and_store_after_calloc?
store is killed by memset and then we have a calloc with memset.

In D101391#2720758, @nikic wrote:

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

Yes, good idea. Prepared partial_zero_memset_and_store_after_calloc and zero_memset_and_store_with_dyn_index_after_calloc.

[xbolva00]

New testcases + fixed nit.

[xbolva00]

Cleanup tests for easier review.

[nikic]

LGTM

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll

436

I'd suggest adding a variant that stores a constant but non-zero value (e.g. i8 1).

It may also be worthwhile to make sure that passing i1 true for the volatile flag will prevent DSE (this should be covered by the isRemovable check in the caller).

[xbolva00]

Added suggested tests

[xbolva00]

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll

436

Sure, I will add such tests.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

bool eliminateDeadWritesAtEndOfFunction() {
     return MadeChange;
   }
 
   /// \returns true if \p Def is a no-op store, either because it
   /// directly stores back a loaded value or stores zero to a calloced object.
   bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc,
                    const Value *DefUO) {
     StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
+    MemSetInst *MemSet = dyn_cast<MemSetInst>(Def->getMemoryInst());
+    Constant *StoredConstant = nullptr;
+    if (Store)
+      StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
+    if (MemSet)
+      StoredConstant = dyn_cast<Constant>(MemSet->getValue());
+
+    if (StoredConstant && StoredConstant->isNullValue()) {
+      auto *DefUOInst = dyn_cast<Instruction>(DefUO);
+      if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
+        auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
+        // If UnderlyingDef is the clobbering access of Def, no instructions
+        // between them can modify the memory location.
+        auto *ClobberDef =
+            MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
+        return UnderlyingDef == ClobberDef;
+      }
+    }
+
     if (!Store)
       return false;
 
     if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
       if (LoadI->getPointerOperand() == Store->getOperand(1)) {
         // Get the defining access for the load.
         auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
         // Fast path: the defining accesses are the same.
if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
           // noop. Otherwise, fail.
           if (LoadAccess != Current)
             return false;
         }
         return true;
       }
     }
 
-    Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
-    if (StoredConstant && StoredConstant->isNullValue()) {
-      auto *DefUOInst = dyn_cast<Instruction>(DefUO);
-      if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
-        auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
-        // If UnderlyingDef is the clobbering access of Def, no instructions
-        // between them can modify the memory location.
-        auto *ClobberDef =
-            MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
-        return UnderlyingDef == ClobberDef;
-      }
-    }
     return false;
   }
 };
 
 bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                          DominatorTree &DT, PostDominatorTree &PDT,
                          const TargetLibraryInfo &TLI) {
   bool MadeChange = false;

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll

;
   %call = tail call i8* @calloc(i64 1, i64 10)  inaccessiblememonly
   store i8 0, i8* %call
   ret i8* %call
 }
 
 define i8* @zero_memset_after_calloc()  {
 ; CHECK-LABEL: @zero_memset_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }
 
+define i8* @volatile_zero_memset_after_calloc()  {
+; CHECK-LABEL: @volatile_zero_memset_after_calloc(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 true)
+; CHECK-NEXT:    ret i8* [[CALL]]
+;
+  %call = tail call i8* @calloc(i64 10000, i64 4)
+  call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 true)
+  ret i8* %call
+}
+
 define i8* @zero_memset_and_store_after_calloc(i8 %v)  {
 ; CHECK-LABEL: @zero_memset_and_store_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   store i8 %v, i8* %call
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }
 
 define i8* @partial_zero_memset_after_calloc() {
 ; CHECK-LABEL: @partial_zero_memset_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 20, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
   ret i8* %call
 }
 
 define i8* @partial_zero_memset_and_store_after_calloc(i8 %v)  {
 ; CHECK-LABEL: @partial_zero_memset_and_store_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 30
 ; CHECK-NEXT:    store i8 [[V:%.*]], i8* [[GEP]], align 1
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 20, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   %gep = getelementptr inbounds i8, i8* %call, i64 30
   store i8 %v, i8* %gep
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
   ret i8* %call
 }
 
 define i8* @zero_memset_and_store_with_dyn_index_after_calloc(i8 %v, i64 %idx)  {
 ; CHECK-LABEL: @zero_memset_and_store_with_dyn_index_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   %gep = getelementptr inbounds i8, i8* %call, i64 %idx
   store i8 %v, i8* %gep
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }

 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4) inaccessiblememonly
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }
 
+define i8* @cst_nonzero_memset_after_calloc() {
+; CHECK-LABEL: @cst_nonzero_memset_after_calloc(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 1, i64 40000, i1 false)
+; CHECK-NEXT:    ret i8* [[CALL]]
+;
+  %call = tail call i8* @calloc(i64 10000, i64 4)
+  call void @llvm.memset.p0i8.i64(i8* %call, i8 1, i64 40000, i1 false)
+  ret i8* %call
+}
 
 define i8* @nonzero_memset_after_calloc(i8 %v) {
 ; CHECK-LABEL: @nonzero_memset_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 [[V:%.*]], i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4)
   call void @llvm.memset.p0i8.i64(i8* %call, i8 %v, i64 40000, i1 false)
   ret i8* %call
 }
 
 ; PR11896
 ; The first memset is dead, because calloc provides zero-filled memory.
 ; TODO: This could be replaced with a call to malloc + memset_pattern16.
 define i8* @memset_pattern16_after_calloc(i8* %pat) {
 ; CHECK-LABEL: @memset_pattern16_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    call void @memset_pattern16(i8* [[CALL]], i8* [[PAT:%.*]], i64 40000)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4) #1
   call void @llvm.memset.p0i8.i64(i8* align 4 %call, i8 0, i64 40000, i1 false)
   call void @memset_pattern16(i8* %call, i8* %pat, i64 40000) #1
   ret i8* %call
 }