[DSE,MSSA] Treat `store 0` after calloc as noop stores.

[fhahn]

Summary

This patch extends storeIsNoop to also detect stores of 0 to an calloced
object. This basically ports the logic from legacy DSE to the MemorySSA
backed version.

It triggers in a few cases on MultiSource, SPEC2000, SPEC2006 with -O3
LTO:

Same hash: 218 (filtered out)
Remaining: 19
Metric: dse.NumNoopStores

Program base patch2 diff
test-suite...CFP2000/177.mesa/177.mesa.test 1.00 15.00 1400.0%
test-suite...6/482.sphinx3/482.sphinx3.test 1.00 14.00 1300.0%
test-suite...lications/ClamAV/clamscan.test 2.00 28.00 1300.0%
test-suite...CFP2006/433.milc/433.milc.test 1.00 8.00 700.0%
test-suite...pplications/oggenc/oggenc.test 2.00 9.00 350.0%
test-suite.../CINT2000/176.gcc/176.gcc.test 6.00 6.00 0.0%
test-suite.../CINT2006/403.gcc/403.gcc.test NaN 137.00 nan%
test-suite...libquantum/462.libquantum.test NaN 3.00 nan%
test-suite...6/464.h264ref/464.h264ref.test NaN 7.00 nan%
test-suite...decode/alacconvert-decode.test NaN 2.00 nan%
test-suite...encode/alacconvert-encode.test NaN 2.00 nan%
test-suite...ications/JM/ldecod/ldecod.test NaN 9.00 nan%
test-suite...ications/JM/lencod/lencod.test NaN 39.00 nan%
test-suite.../Applications/lemon/lemon.test NaN 2.00 nan%
test-suite...pplications/treecc/treecc.test NaN 4.00 nan%
test-suite...hmarks/McCat/08-main/main.test NaN 4.00 nan%
test-suite...nsumer-lame/consumer-lame.test NaN 3.00 nan%
test-suite.../Prolangs-C/bison/mybison.test NaN 1.00 nan%
test-suite...arks/mafft/pairlocalalign.test NaN 30.00 nan%

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1949

One small note here: this query will not cache any result, because it's checking access to the DefLoc. It seems like the scenario of having: store value 0 + calloc as underlying object may be rare enough that it will not kick in often without benefit, but it's also possible to see a compile-time regression if the following pattern is found often.

calloc 
store val, loc
store 0, loc

In contrast, doing getClobbering(Def) will cache and the info could be used by this or subsequent passes. Would it make sense to make this check here instead?

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

113

Negative test: add before ret and check it does not get eliminated:

%p.3.2 = getelementptr i8, i8* %p, i32 3
 store i8 0, i8* %p.3.2, align 1

[fhahn]

Use getClobberingMemoryAccess(Def) and add extra test as suggested, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1949

Thanks for pointing that out, I updated the code to use getClobberingMemoryAcess(Def).

getClobberingMemoryAccess(Access, Loc) is also used in getDomMemoryDef and profiling indicates that this is where 50%+ of the time in DSE with MemorySSA is spent. getClobberingMemoryAcess(Def)` could be used for the check in the first iteration, but for subsequent ones we need to pass in the original location I think. Any thoughts/suggestions on how to improve things compile-time wise there would be greatly appreciated. But that's for separate changes :)

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

113

Done, I've added it as a separate test. Currently only the last store is left over, but as it is a store of 0, it could also be eliminated. We currently don't do that, because of the order in which we perform the eliminations.

[asbirlea]

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

113

I was suggesting a test where the store would intentionally not be eliminated (negative test), and this seems correct below. There is a store of 5, then the store of 0 should not be eliminated because it would overwrite the 5.
Add a check that the store of value 5 is also there?

If you mean the store is the last before ret, and it should be eliminated because of *that*, then add another method call afterwards to defeat it. This way, we'll have a unit test to check that DSE works correctly on the particular feature added in this patch, the pattern:

calloc
store non-zero value
store zero is not eliminated (i.e. clobbering correctly find the non-zero store, not the calloc)

Does this make sense?

[fhahn]

Add additional test with read between non-zero and zero store.

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

113

I was suggesting a test where the store would intentionally not be eliminated (negative test), and this seems correct below. There is a store of 5, then the store of 0 should not be eliminated because it would overwrite the 5.
Add a check that the store of value 5 is also there?

I might be missing something, but store i8 5, i8* %p.3 in @test11 is eliminated because it gets overwritten by the last store store i8 0, i8* %p.3.2. The check lines ensure that it is gone.

If you mean the store is the last before ret, and it should be eliminated because of *that*, then add another method call afterwards to defeat it.

We are already returning the pointer returned from calloc, which should be enough to ensure that non-zero stores cannot be removed because they are not read at the end of the function I think.

This way, we'll have a unit test to check that DSE works correctly on the particular feature added in this patch, the pattern:

calloc
store non-zero value
store zero is not eliminated (i.e. clobbering correctly find the non-zero store, not the calloc)
Does this make sense?

IIUC in the scenario above (which is should be reflected in @test11) we could eliminate both stores. The non-zero value is overwritten by 0 before it is read or the function returns, so calloc would already ensure the location is zero.

I'll add a test case with a read between the non-zero and zero store. This way, neither can be eliminated.

Does that make sense?

[fhahn]

Move a calloc test from simple-todo.ll to simple.ll

[asbirlea]

lgtm

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

113

Yes, that's perfect. You're right, I missed the need for a use inbetween, otherwise the 5 stored also gets eliminated. Thank you for adding this.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (NI->isAtomic()) {
       if (auto *LI = dyn_cast<LoadInst>(NI))
         return isStrongerThanMonotonic(LI->getOrdering());
       if (auto *SI = dyn_cast<StoreInst>(NI))
         return isStrongerThanMonotonic(SI->getOrdering());
       llvm_unreachable("other instructions should be skipped in MemorySSA");
     }
     return false;
   }
-};
 
-/// \returns true if \p KillingDef stores the result of \p Load to the source of
-/// \p Load.
-static bool storeIsNoop(MemorySSA &MSSA, LoadInst *Load,
-                        MemoryDef *KillingDef) {
-  Instruction *Store = KillingDef->getMemoryInst();
-  // If the load's operand isn't the destination of the store, bail.
-  if (Load->getPointerOperand() != Store->getOperand(1))
-    return false;
+  /// \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, MemoryLocation DefLoc, const Value *DefUO) {
+    StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
+    if (!Store)
+      return false;
+
+    if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
+      if (LoadI->getPointerOperand() == Store->getOperand(1)) {
+        auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
+        // If both accesses share the same defining access, no instructions
+        // between them can modify the memory location.
+        return LoadAccess == Def->getDefiningAccess();
+      }
+    }
 
-  // Get the defining access for the load.
-  auto *LoadAccess = MSSA.getMemoryAccess(Load)->getDefiningAccess();
-  // The store is dead if the defining accesses are the same.
-  return LoadAccess == KillingDef->getDefiningAccess();
+    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 eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                   MemorySSA &MSSA, DominatorTree &DT,
                                   PostDominatorTree &PDT,
                                   const TargetLibraryInfo &TLI) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   bool MadeChange = false;
 
   DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *SI = KillingDef->getMemoryInst();
 
-    // Check if we're storing a value that we just loaded.
-    if (auto *Load = dyn_cast<LoadInst>(SI->getOperand(0))) {
-      if (storeIsNoop(MSSA, Load, KillingDef)) {
-        LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *SI
-                          << '\n');
-        State.deleteDeadInstruction(SI);
-        NumNoopStores++;
-        MadeChange = true;
-        continue;
-      }
-    }
-
     auto MaybeSILoc = State.getLocForWriteEx(SI);
     if (!MaybeSILoc) {
       LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
                         << *SI << "\n");
       continue;
     }
     MemoryLocation SILoc = *MaybeSILoc;
     assert(SILoc.Ptr && "SILoc should not be null");
     const Value *SILocUnd = GetUnderlyingObject(SILoc.Ptr, DL);
+
+    // Check if the store is a no-op.
+    if (State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
+      LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *SI << '\n');
+      State.deleteDeadInstruction(SI);
+      NumNoopStores++;
+      MadeChange = true;
+      continue;
+    }
+
     Instruction *DefObj =
         const_cast<Instruction *>(dyn_cast<Instruction>(SILocUnd));
     bool DefVisibleToCallerBeforeRet =
         !State.InvisibleToCallerBeforeRet.count(SILocUnd);
     bool DefVisibleToCallerAfterRet =
         !State.InvisibleToCallerAfterRet.count(SILocUnd);
     if (DefObj && isAllocLikeFn(DefObj, &TLI)) {
       if (DefVisibleToCallerBeforeRet)

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

-; XFAIL: *
-
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 
 declare noalias i8* @calloc(i64, i64)
 
 define i32* @test1() {
 ; CHECK-LABEL: test1
   %1 = tail call noalias i8* @calloc(i64 1, i64 4)
   %2 = bitcast i8* %1 to i32*

 
 define i8* @test7(i8 %arg) {
 ; CHECK-LABEL: test7
   %1 = tail call noalias i8* @calloc(i64 1, i64 4)
   store i8 %arg, i8* %1, align 4
 ; CHECK: store i8 %arg, i8* %1, align 4
   ret i8* %1
 }
+
+define i8* @test8() {
+; CHECK-LABEL: test8
+; CHECK-NOT: store
+  %p = tail call noalias i8* @calloc(i64 1, i64 4)
+  store i8 0, i8* %p, align 1
+  %p.1 = getelementptr i8, i8* %p, i32 1
+  store i8 0, i8* %p.1, align 1
+  %p.3 = getelementptr i8, i8* %p, i32 3
+  store i8 0, i8* %p.3, align 1
+  %p.2 = getelementptr i8, i8* %p, i32 2
+  store i8 0, i8* %p.2, align 1
+  ret i8* %p
+}
+
+define i8* @test9() {
+; CHECK-LABEL: test9
+; CHECK-NEXT:    %p = tail call noalias i8* @calloc(i64 1, i64 4)
+; CHECK-NEXT:    store i8 5, i8* %p, align 1
+; CHECK-NEXT:    ret i8* %p
+
+  %p = tail call noalias i8* @calloc(i64 1, i64 4)
+  store i8 5, i8* %p, align 1
+  %p.1 = getelementptr i8, i8* %p, i32 1
+  store i8 0, i8* %p.1, align 1
+  %p.3 = getelementptr i8, i8* %p, i32 3
+  store i8 0, i8* %p.3, align 1
+  %p.2 = getelementptr i8, i8* %p, i32 2
+  store i8 0, i8* %p.2, align 1
+  ret i8* %p
+}
+
+define i8* @test10() {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:    [[P:%.*]] = tail call noalias i8* @calloc(i64 1, i64 4)
+; CHECK-NEXT:    [[P_3:%.*]] = getelementptr i8, i8* [[P]], i32 3
+; CHECK-NEXT:    store i8 5, i8* [[P_3]], align 1
+; CHECK-NEXT:    ret i8* [[P]]
+;
+
+  %p = tail call noalias i8* @calloc(i64 1, i64 4)
+  store i8 0, i8* %p, align 1
+  %p.1 = getelementptr i8, i8* %p, i32 1
+  store i8 0, i8* %p.1, align 1
+  %p.3 = getelementptr i8, i8* %p, i32 3
+  store i8 5, i8* %p.3, align 1
+  %p.2 = getelementptr i8, i8* %p, i32 2
+  store i8 0, i8* %p.2, align 1
+  ret i8* %p
+}
+
+; TODO: we could also eliminate the last store i8 0, i8* %p.3.2, but currently
+; don't because those are eliminated before eliminating killed stores.
+define i8* @test11() {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:    [[P:%.*]] = tail call noalias i8* @calloc(i64 1, i64 4)
+; CHECK-NEXT:    [[P_3_2:%.*]] = getelementptr i8, i8* [[P]], i32 3
+; CHECK-NEXT:    store i8 0, i8* [[P_3_2]], align 1
+; CHECK-NEXT:    ret i8* [[P]]
+;
+
+  %p = tail call noalias i8* @calloc(i64 1, i64 4)
+  store i8 0, i8* %p, align 1
+  %p.1 = getelementptr i8, i8* %p, i32 1
+  store i8 0, i8* %p.1, align 1
+  %p.3 = getelementptr i8, i8* %p, i32 3
+  store i8 5, i8* %p.3, align 1
+  %p.2 = getelementptr i8, i8* %p, i32 2
+  store i8 0, i8* %p.2, align 1
+  %p.3.2 = getelementptr i8, i8* %p, i32 3
+  store i8 0, i8* %p.3.2, align 1
+  ret i8* %p
+}
+
+define i8* @test12() {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    [[P:%.*]] = tail call noalias i8* @calloc(i64 1, i64 4)
+; CHECK-NEXT:    [[P_3:%.*]] = getelementptr i8, i8* [[P]], i32 3
+; CHECK-NEXT:    store i8 5, i8* [[P_3]], align 1
+; CHECK-NEXT:    call void @use(i8* [[P]])
+; CHECK-NEXT:    [[P_3_2:%.*]] = getelementptr i8, i8* [[P]], i32 3
+; CHECK-NEXT:    store i8 0, i8* [[P_3_2]], align 1
+; CHECK-NEXT:    ret i8* [[P]]
+;
+
+  %p = tail call noalias i8* @calloc(i64 1, i64 4)
+  %p.3 = getelementptr i8, i8* %p, i32 3
+  store i8 5, i8* %p.3, align 1
+  call void @use(i8* %p)
+  %p.3.2 = getelementptr i8, i8* %p, i32 3
+  store i8 0, i8* %p.3.2, align 1
+  ret i8* %p
+}
+
+declare void @use(i8*) readonly

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

;
   %storage = alloca [10 x i8], align 16    ; <[10 x i8]*> [#uses=1]
   %cast = getelementptr [10 x i8], [10 x i8]* %storage, i32 0, i32 0    ; <i8*> [#uses=1]
   call void @llvm.init.trampoline( i8* %cast, i8* bitcast (void ()* @test11f to i8*), i8* null )    ; <i8*> [#uses=1]
   ret void
 }
 
 
 declare noalias i8* @malloc(i32)
-declare noalias i8* @calloc(i32, i32)
 
 define void @test14(i32* %Q) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:    ret void
 ;
   %P = alloca i32
   %DEAD = load i32, i32* %Q
   store i32 %DEAD, i32* %P
   ret void
 
 }
 
 define void @test20() {
 ; CHECK-LABEL: @test20(
 ; CHECK-NEXT:    ret void
 ;
   %m = call i8* @malloc(i32 24)
   store i8 0, i8* %m
   ret void
 }
 
-define void @test21() {
-; CHECK-LABEL: @test21(
-; CHECK-NEXT:    ret void
-;
-  %m = call i8* @calloc(i32 9, i32 7)
-  store i8 0, i8* %m
-  ret void
-}
-
 define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
 ; CHECK-LABEL: @test22(
 ; CHECK-NEXT:    ret void
 ;
   %k.addr = alloca i32
   %m.addr = alloca i32
   %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
   store i32 0, i32* %k.addr.m.addr, align 4

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

 bb:
   %tmp7 = getelementptr inbounds {i32}, {i32}* %arg5, i32 0, i32 0
   store i32 912, i32* %tmp7
   call void @test19f({i32}* byval align 4 %arg5)
   ret void
 
 }
 
+define void @test21() {
+; CHECK-LABEL: @test21(
+; CHECK-NEXT:    ret void
+;
+  %m = call i8* @calloc(i32 9, i32 7)
+  store i8 0, i8* %m
+  ret void
+}
+
 ; PR13547
 declare noalias i8* @strdup(i8* nocapture) nounwind
 define noalias i8* @test23() nounwind uwtable ssp {
 ; CHECK-LABEL: @test23(
 ; CHECK-NEXT:    [[X:%.*]] = alloca [2 x i8], align 1
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8], [2 x i8]* [[X]], i64 0, i64 0
 ; CHECK-NEXT:    store i8 97, i8* [[ARRAYIDX]], align 1
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i8], [2 x i8]* [[X]], i64 0, i64 1