[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

372

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

372

Sure, I will add such tests.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

     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.

           // 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

;
   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:    [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
-; 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)
   %l0 = bitcast i8* %call to i32*
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   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:    [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
-; 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
   %l0 = bitcast i8* %call to i32*
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }

 ; CHECK-LABEL: @nonzero_memset_after_calloc(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
 ; CHECK-NEXT:    [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
 ; 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)
   %l0 = bitcast i8* %call to i32*
   call void @llvm.memset.p0i8.i64(i8* %call, i8 %v, i64 40000, i1 false)
   ret i8* %call
 }
 
 define i8* @zero_memset_after_calloc_smaller_size() {
 ; CHECK-LABEL: @zero_memset_after_calloc_smaller_size(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
 ; CHECK-NEXT:    [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
-; 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)
   %l0 = bitcast i8* %call to i32*
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, 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:    [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
-; 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
   %l0 = bitcast i8* %call to i32*
   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
 }