Remove dead zero store to calloc initialized memory

[reames]

Summary

Optimize the following IR:

%1 = tail call noalias i8* @calloc(i64 1, i64 4)
%2 = bitcast i8* %1 to i32*
; This store is dead and should be removed
store i32 0, i32* %2, align 4

Memory returned by calloc is guaranteed to be zero initialized. If the value being stored is the constant zero (and the store is not otherwise observable across threads), we can delete the store.

Note: I do not have commit rights and will need someone to commit this change after review.

[meadori]

In general I understand the intent of the optimization, but is this really that common of a case to warrant optimization? Was this inspired by real world code patterns?

lib/Transforms/Scalar/DeadStoreElimination.cpp

550 ↗

(On Diff #9889)

A few minor formatting nits:

1. Space between 'if' and '('.
2. No spaces around the expression.
3. Looks like the full expression can fit on one line.

Also, in practice I am not sure if this is a problem, but in theory shouldn't this only apply to integer zero? The C Standard notes that the zero representation for floating point and null pointers can be different than all bits zero. Again, not sure if that is actually an issue, but wanted to raise the point anyway.

572 ↗

(On Diff #9889)

Not sure if it is worth it to merge, but this code is very similar to the block before it.

[reames]

In D3942#4, @meadori wrote:

In general I understand the intent of the optimization, but is this really that common of a case to warrant optimization? Was this inspired by real world code patterns?

For C, not really. For other languages yes. For example, most Java implementations zero initialize all memory (since the default value of every field is defined to be zero), but is common for programmers to write manual initializers anyways. While the allocation function isn't actually calloc, the semantics are quite similar. In practice, we use a "is-calloc-like" attribute on the allocation function. I may propose this for upstreaming at some point, but wanted to get supporting optimizations in first and calloc provides a good stand in.

lib/Transforms/Scalar/DeadStoreElimination.cpp

550 ↗

(On Diff #9889)

Will fix the formatting.

The constant zero point is a good one. However, LLVM widely appears to mix null and zero. I'm furthering an existing problem, not creating a new one. Also, this is purely a theoretical issue at the moment. No system I'm aware of as NULL as anything other than the zero address.

572 ↗

(On Diff #9889)

The code is in fact nearly identical, but the handling is slightly different. I would resist the merge for the moment, but if you really want it, I will do so.

[reames]

Updated to reflect review comments. Sorry for the delay, this fell off my mental todo list.

[nicholas]

LGTM

lib/Transforms/Scalar/DeadStoreElimination.cpp

537 ↗

(On Diff #10572)

"Value* V" -> "Value *V"

[reames]

Closed by commit rL214897 (authored by @reames).

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
 
     MemDepResult InstDep = MD->getDependency(Inst);
 
     // Ignore any store where we can't find a local dependence.
     // FIXME: cross-block DSE would be fun. :)
     if (!InstDep.isDef() && !InstDep.isClobber())
       continue;
 
+    // Check for cases where the store is redundant.
+    if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+      bool DeleteStore = false;
       // If we're storing the same value back to a pointer that we just
       // loaded from, then the store can be removed.
-    if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
             SI->getOperand(0) == DepLoad && isRemovable(SI)) {
           DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
                        << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
+          DeleteStore = true;
+        }
+      }
 
-          // DeleteDeadInstruction can delete the current instruction.  Save BBI
-          // in case we need it.
-          WeakVH NextInst(BBI);
+      // If we find a store to memory which was defined by calloc
+      // we can remove the store if the value being stored is a
+      // constant zero (since calloc initialized the memory to
+      // that same value) or the store is undefined (if out of
+      // bounds).  
+      if (isCallocLikeFn(InstDep.getInst(), TLI) && isRemovable(SI)) {
+        Value *V = SI->getValueOperand();
+        if (isa<Constant>(V) && cast<Constant>(V)->isNullValue()) {
+          DEBUG(dbgs() << "DSE: Remove Store Of Zero to Calloc:\n  "
+                << "CALLOC: " << *InstDep.getInst() << "\n"
+                << "STORE: " << *SI << '\n');
+          DeleteStore = true;
+        }
+      }
+
+      if (DeleteStore) {
         
-          DeleteDeadInstruction(SI, *MD, TLI);
         
-          if (!NextInst)  // Next instruction deleted.
-            BBI = BB.begin();
-          else if (BBI != BB.begin())  // Revisit this instruction if possible.
-            --BBI;
-          ++NumFastStores;
-          MadeChange = true;
-          continue;
-        }
-      }
-    }
 
     // Figure out what location is being stored to.
     AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA);
 
     // If we didn't get a useful location, fail.
     if (!Loc.Ptr)
       continue;
 

llvm/trunk/test/Transforms/DeadStoreElimination/calloc-store.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind
+declare noalias i8* @calloc(i64, i64)
+
+; Function Attrs: nounwind uwtable
+define noalias i32* @test_store() {
+; CHECK-LABEL: test_store
+  %1 = tail call noalias i8* @calloc(i64 1, i64 4)
+  %2 = bitcast i8* %1 to i32*
+  ; This store is dead and should be removed
+  store i32 0, i32* %2, align 4
+; CHECK-NOT: store i32 0, i32* %2, align 4
+  ret i32* %2
+}