[EarlyCSE] DSE of stores which write back loaded values

[reames]

Summary

Extend EarlyCSE with an additional style of dead store elimination. If we write back a value just read from that memory location, we can eliminate the store under the assumption that the value hasn't changed.

I'd really appreciate someone taking a close look at my "dse5" test case. I want to make sure the logic involved holds up. For normal loads and stores it clearly does - for the store to change the value, there must be a race. I believe it also holds for unordered atomics, but would really like a second opinion.

I'm implementing this mostly because I noticed the omission when looking at the code. It seemed strange to have InstCombine have a peephole which was more powerful than EarlyCSE. :)

[hfinkel]

LGTM.

lib/Transforms/Scalar/EarlyCSE.cpp

711 ↗

(On Diff #42350)

Comments should be sentences (start with a capital, end with a period).

test/Transforms/EarlyCSE/basic.ll

252 ↗

(On Diff #42350)

I agree this makes sense. Regardless of what else happens (for %P == %Q), we're always free to pick an ordering in which %v == %a and where we always observe our own store, implying %a == %b.

[jfb]

Technically you could even remove seq_cst load/store pairs if they're not synchronizing with anything in the middle. You'd still have to preserve the effect with a fence, but the access is dead since it must have raced if it didn't synchronize with anything else.

Just to confirm (even though this optimization happens elsewhere): we don't care about memory accesses which normalize FP values, e.g. canonicalizing NaNs or flushing denormals to zero?

test/Transforms/EarlyCSE/basic.ll

248 ↗

(On Diff #42350)

Clarify: "that's okay because we're using relaxed memory ordering".

[reames]

In D15397#307456, @jfb wrote:

Technically you could even remove seq_cst load/store pairs if they're not synchronizing with anything in the middle. You'd still have to preserve the effect with a fence, but the access is dead since it must have raced if it didn't synchronize with anything else.

Not going to argue this. I don't care to optimize this case and reasoning about it in enough detail to agree or disagree is more investment than I want to make right now.

Just to confirm (even though this optimization happens elsewhere): we don't care about memory accesses which normalize FP values, e.g. canonicalizing NaNs or flushing denormals to zero?

Hm. Good question. I don't know the answer to this. In practice, we side step the question by not allowing atomic stores of floating point at all - the verifier will reject - but given I'm planning on changing that soon, that's an interesting question.

[jfb]

In D15397#307728, @reames wrote:

In D15397#307456, @jfb wrote:

Technically you could even remove seq_cst load/store pairs if they're not synchronizing with anything in the middle. You'd still have to preserve the effect with a fence, but the access is dead since it must have raced if it didn't synchronize with anything else.

Not going to argue this. I don't care to optimize this case and reasoning about it in enough detail to agree or disagree is more investment than I want to make right now.

Sounds good.

Just to confirm (even though this optimization happens elsewhere): we don't care about memory accesses which normalize FP values, e.g. canonicalizing NaNs or flushing denormals to zero?

Hm. Good question. I don't know the answer to this. In practice, we side step the question by not allowing atomic stores of floating point at all - the verifier will reject - but given I'm planning on changing that soon, that's an interesting question.

Dead non-atomic FP stores get eliminated, so I'm assuming this is fine.

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

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // to advance the generation.  We do need to prevent DSE across the fence,
     // but that's handled above.
     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
       if (FI->getOrdering() == Release) {
         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
         continue;
       }
 
+    // write back DSE - If we write back the same value we just loaded from
+    // the same location and haven't passed any intervening writes or ordering
+    // operations, we can remove the write.  The primary benefit is in allowing
+    // the available load table to remain valid and value forward past where
+    // the store originally was.
+    if (MemInst.isValid() && MemInst.isStore()) {
+      LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
+      if (InVal.Data &&
+          InVal.Data == getOrCreateResult(Inst, InVal.Data->getType()) &&
+          InVal.Generation == CurrentGeneration &&
+          InVal.MatchingId == MemInst.getMatchingId() &&
+          // We don't yet handle removing stores with ordering of any kind.
+          !MemInst.isVolatile() && MemInst.isUnordered()) {
+        assert((!LastStore ||
+                ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
+                MemInst.getPointerOperand()) &&
+               "can't have an intervening store!");
+        DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
+        Inst->eraseFromParent();
+        Changed = true;
+        ++NumDSE;
+        // We can avoid incrementing the generation count since we were able
+        // to eliminate this store.
+        continue;
+      }
+    }
+
     // Okay, this isn't something we can CSE at all.  Check to see if it is
     // something that could modify memory.  If so, our available memory values
     // cannot be used so bump the generation count.
     if (Inst->mayWriteToMemory()) {
       ++CurrentGeneration;
 
       if (MemInst.isValid() && MemInst.isStore()) {
         // We do a trivial form of DSE if there are two stores to the same

llvm/trunk/test/Transforms/EarlyCSE/basic.ll

define i32 @test12(i1 %B, i32* %P1, i32* %P2) {
   %load0 = load i32, i32* %P1
   %1 = load atomic i32, i32* %P2 seq_cst, align 4
   %load1 = load i32, i32* %P1
   %sel = select i1 %B, i32 %load0, i32 %load1
   ret i32 %sel
   ; CHECK: load i32, i32* %P1
   ; CHECK: load i32, i32* %P1
 }
+
+define void @dse1(i32 *%P) {
+; CHECK-LABEL: @dse1
+; CHECK-NOT: store
+  %v = load i32, i32* %P
+  store i32 %v, i32* %P
+  ret void
+}
+
+define void @dse2(i32 *%P) {
+; CHECK-LABEL: @dse2
+; CHECK-NOT: store
+  %v = load atomic i32, i32* %P seq_cst, align 4
+  store i32 %v, i32* %P
+  ret void
+}
+
+define void @dse3(i32 *%P) {
+; CHECK-LABEL: @dse3
+; CHECK-NOT: store
+  %v = load atomic i32, i32* %P seq_cst, align 4
+  store atomic i32 %v, i32* %P unordered, align 4
+  ret void
+}
+
+define i32 @dse4(i32 *%P, i32 *%Q) {
+; CHECK-LABEL: @dse4
+; CHECK-NOT: store
+; CHECK: ret i32 0
+  %a = load i32, i32* %Q
+  %v = load atomic i32, i32* %P unordered, align 4
+  store atomic i32 %v, i32* %P unordered, align 4
+  %b = load i32, i32* %Q
+  %res = sub i32 %a, %b
+  ret i32 %res
+}
+
+; Note that in this example, %P and %Q could in fact be the same
+; pointer.  %v could be different than the value observed for %a
+; and that's okay because we're using relaxed memory ordering.  
+; The only guarantee we have to provide is that each of the loads 
+; has to observe some value written to that location.  We  do 
+; not have to respect the order in which those writes were done.  
+define i32 @dse5(i32 *%P, i32 *%Q) {
+; CHECK-LABEL: @dse5
+; CHECK-NOT: store
+; CHECK: ret i32 0
+  %v = load atomic i32, i32* %P unordered, align 4
+  %a = load atomic i32, i32* %Q unordered, align 4
+  store atomic i32 %v, i32* %P unordered, align 4
+  %b = load atomic i32, i32* %Q unordered, align 4
+  %res = sub i32 %a, %b
+  ret i32 %res
+}
+
+
+define void @dse_neg1(i32 *%P) {
+; CHECK-LABEL: @dse_neg1
+; CHECK: store
+  %v = load i32, i32* %P
+  store i32 5, i32* %P
+  ret void
+}
+
+; Could remove the store, but only if ordering was somehow
+; encoded.
+define void @dse_neg2(i32 *%P) {
+; CHECK-LABEL: @dse_neg2
+; CHECK: store
+  %v = load i32, i32* %P
+  store atomic i32 %v, i32* %P seq_cst, align 4
+  ret void
+}
+