[DSE] Remove noop stores after killing stores for a MemoryDef.

[fhahn]

Summary

Currently we fail to eliminate some noop stores if there is a kill-able
store between the starting def and the load. This is because we
eliminate noop stores first.

In practice it seems like eliminating noop stores after the main
elimination for a def covers slightly more cases.

This patch improves the number of stores slightly in 2 cases for X86 -O3
-flto

Same hash: 235 (filtered out)
Remaining: 2
Metric: dse.NumRedundantStores

Program base patch diff
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 2.00 3.00 50.0%
test-suite...006/453.povray/453.povray.test 18.00 21.00 16.7%

There might be other phase ordering issues, but it appears that they do
not show up in the test-suite/SPEC2000/SPEC2006. We can always tune the
ordering later.

Partly fixes PR47887.

[xbolva00]

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

291

Update comment?

[zoecarver]

This LGTM. I wonder if there are any cases where passing the killing memory def in storeIsNoop to storeIsNoop would benefit us. I can't think of one off the top of my head, because it doesn't really matter what order the noop stores come in. But maybe if there was a weird block ordering. I'll see if I can come up with an example.

[fhahn]

In D89650#2353901, @zoecarver wrote:

This LGTM. I wonder if there are any cases where passing the killing memory def in storeIsNoop to storeIsNoop would benefit us. I can't think of one off the top of my head, because it doesn't really matter what order the noop stores come in. But maybe if there was a weird block ordering. I'll see if I can come up with an example.

Yes there might be some other cases we still miss with this ordering, but so far from the testing I did those did not seem to really show up.

We can always further improve this if additional cases surface.

[fhahn]

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

291

Thanks, I updated the comment.

[fhahn]

rebase & ping :)

[zoecarver]

We can always further improve this if additional cases surface.

Sounds good to me.

This patch looks good to me.

[xbolva00]

In D89650#2362347, @zoecarver wrote:

We can always further improve this if additional cases surface.

Sounds good to me.

This patch looks good to me.

Click on Accept to formally approve it.

[zoecarver]

Click on Accept to formally approve it.

I wasn't sure if I was allowed to. For example, in libc++ for a while (not anymore), only maintainers were allowed to approve patches.

[fhahn]

In D89650#2362379, @zoecarver wrote:

Click on Accept to formally approve it.

I wasn't sure if I was allowed to. For example, in libc++ for a while (not anymore), only maintainers were allowed to approve patches.

Thanks for taking a look! There are no hard rules I am aware of and generally all comments are very welcome!

As for the 'official' approval, I think it depends a lot on the complexity of the patch and if in doubt it is probably best to wait for feedback from a reviewer that already reviewed patches in the area, in addition to other approvals.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

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);
 
-    // Check if the store is a no-op.
-    if (isRemovable(SI) && State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
-      LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *SI << '\n');
-      State.deleteDeadInstruction(SI);
-      NumRedundantStores++;
-      MadeChange = true;
-      continue;
-    }
-
     MemoryAccess *Current = KillingDef;
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
                       << *KillingDef << " (" << *SI << ")\n");
 
     unsigned ScanLimit = MemorySSAScanLimit;
     unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
     unsigned PartialLimit = MemorySSAPartialStoreLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
     SetVector<MemoryAccess *> ToCheck;
+
+    if (SILocUnd)
       ToCheck.insert(KillingDef->getDefiningAccess());
 
-    if (!SILocUnd)
-      continue;
+    bool Shortend = false;
     bool IsMemTerm = State.isMemTerminatorInst(SI);
     DSEState::CheckCache Cache;
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       Current = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
for (unsigned I = 0; I < ToCheck.size(); I++) {
                     Earlier, Later, InstWriteOffset, DepWriteOffset, State.DL,
                     State.BatchAA, &DT)) {
 
               // Update stored value of earlier store to merged constant.
               Earlier->setOperand(0, Merged);
               ++NumModifiedStores;
               MadeChange = true;
 
+              Shortend = true;
               // Remove later store and remove any outstanding overlap intervals
               // for the updated store.
               State.deleteDeadInstruction(Later);
               auto I = State.IOLs.find(Earlier->getParent());
               if (I != State.IOLs.end())
                 I->second.erase(Earlier);
               break;
             }
           }
         }
 
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
                             << "\n  KILLER: " << *SI << '\n');
           State.deleteDeadInstruction(NI);
           ++NumFastStores;
           MadeChange = true;
         }
       }
     }
+
+    // Check if the store is a no-op.
+    if (!Shortend && isRemovable(SI) &&
+        State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
+      LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *SI << '\n');
+      State.deleteDeadInstruction(SI);
+      NumRedundantStores++;
+      MadeChange = true;
+      continue;
+    }
   }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;

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

;
   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

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

;
   %a = load i32, i32* %Q
   store i32 %a, i32* %Q
   call void @unkown_write(i32* %Q)
   ret void
 }
 
 define void @test45(i32* %Q) {
 ; CHECK-LABEL: @test45(
-; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[Q:%.*]], align 4
-; CHECK-NEXT:    store i32 [[A]], i32* [[Q]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %a = load i32, i32* %Q
   store i32 10, i32* %Q
   store i32 %a, i32* %Q
   ret void
 }
 

 
 bb1:
   store i32 %v, i32* %p, align 4
   br i1 %c, label %bb2, label %bb0
 bb2:
   ret i32 0
 }
 
-; TODO: Remove both redundant stores if loaded value is in another block inside a loop.
 define i32 @test47(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test47(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[C]], label [[BB3:%.*]], label [[BB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %v = load i32, i32* %p, align 4
   br label %bb1
 bb1:

 ;
 entry:
   %lv = load i32, i32* %x, align 4
   store i32 0, i32* %y, align 4
   store i32 %lv, i32* %x, align 4
   ret void
 }
 
 ; Test case from PR47887. Currently we eliminate the dead `store i32 %inc, i32* %x`,
 ; but not the no-op `store i32 %lv, i32* %x`. That is because no-op stores are
 ; eliminated before dead stores for the same def.
 define void @test_noalias_store_between_load_and_store_elimin_order(i32* noalias %x, i32* noalias %y) {
 ; CHECK-LABEL: @test_noalias_store_between_load_and_store_elimin_order(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[X:%.*]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[Y:%.*]], align 4
-; CHECK-NEXT:    store i32 [[LV]], i32* [[X]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %lv = load i32, i32* %x, align 4
   %inc = add nsw i32 %lv, 1
   store i32 %inc, i32* %x, align 4
   store i32 0, i32* %y, align 4
   store i32 %lv, i32* %x, align 4
   ret void
 }