[InstCombine] Extend peephole DSE to handle unordered atomics

[reames]

Summary

This extends the same line of reasoning used in EarlyCSE w/http://reviews.llvm.org/D15352 to the DSE implementation in InstCombine.

Key points:

• We only remove unordered or simple stores.
• The loads producing values consumed by dead stores don't influence whether the store is dead.

[jfb]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

984

"for ordered atomic stores"

1031

Doesn't this need to test for && LI->isUnordered()? Otherwise it can remove a volatile or ordered load.

1058

"to be audited"

test/Transforms/InstCombine/store.ll

127

Same as in D15352: I think the remaining store should still be atomic, and store the latest value.

136

Same.

196

We could just have a fence, or make it a no-op RMW to the stack top? Maybe worth documenting, not implementing yet.

[reames]

replying to JF's comments, updated diff to follow

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1031

Nope. We can remove the store even if the load is ordered. Removing the load wouldn't be valid, but removing the store is.

test/Transforms/InstCombine/store.ll

127

Same as in that review, the second store is undefined behaviour if access is racy. The location is no longer atomic and we can pick either store.

136

same answer

196

This is documented in EarlyCSE already. I don't see the point in duplicating this in a bunch of places.

[jfb]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1031

An ordered load has ordering semantics that you'd be losing. The *value* stored can be eliminated, but you still need to keep atomic *ordering*.

And you just can't remove volatile :-)

Though it looks like the write-back tests are already correct? I'm confused now.

test/Transforms/InstCombine/store.ll

127

We should at least check that the latest value gets stored (here and below).

[reames]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1031

@JF - I'm 99% certain you're misreading the code and my comments. We're *only* removing the *store* here. The *load* is not being changed. Whether the load is ordered/volatile does not effect the legality of removing the store. In fact, this exact case is covered by the tests @write_back6 and @write_back7.

Or, am I missing something?

test/Transforms/InstCombine/store.ll

127

Will do. I also need to update the comment slightly. The store is well defined; it's the *contents* of the memory location which isn't. The rest is still correct, but the wording was misleading.

[jfb]

Looks good with the 2 suggested updates (assert, and extra check in test).

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1031

Ah yes, you're totally right! Could you assert(SI->isUnordered() && "can't eliminate volatile or ordered store"); here? I know it's checked above, but the intent seems to be to relax this later so the assert will prevent sadness.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (unpackStoreToAggregate(*this, SI))
     return EraseInstFromFunction(SI);
 
   // Replace GEP indices if possible.
   if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
       Worklist.Add(NewGEPI);
       return &SI;
   }
 
-  // Don't hack volatile/atomic stores.
+  // Don't hack volatile/ordered stores.
   // FIXME: Some bits are legal for atomic stores; needs refactoring.
-  if (!SI.isSimple()) return nullptr;
+  if (!SI.isUnordered()) return nullptr;
 
   // If the RHS is an alloca with a single use, zapify the store, making the
   // alloca dead.
   if (Ptr->hasOneUse()) {
     if (isa<AllocaInst>(Ptr))
       return EraseInstFromFunction(SI);
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
       if (isa<AllocaInst>(GEP->getOperand(0))) {
for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
     if (isa<DbgInfoIntrinsic>(BBI) ||
         (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
       ScanInsts++;
       continue;
     }
 
     if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
       // Prev store isn't volatile, and stores to the same location?
-      if (PrevSI->isSimple() && equivalentAddressValues(PrevSI->getOperand(1),
+      if (PrevSI->isUnordered() && equivalentAddressValues(PrevSI->getOperand(1),
                                                         SI.getOperand(1))) {
         ++NumDeadStore;
         ++BBI;
         EraseInstFromFunction(*PrevSI);
         continue;
       }
       break;
     }
 
     // If this is a load, we have to stop.  However, if the loaded value is from
     // the pointer we're loading and is producing the pointer we're storing,
     // then *this* store is dead (X = load P; store X -> P).
     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
-      if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr) &&
-          LI->isSimple())
+      if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr))
         return EraseInstFromFunction(SI);
 
       // Otherwise, this is a load from some other location.  Stores before it
       // may not be dead.
       break;
     }
 
     // Don't skip over loads or things that can modify memory.
if (isa<ConstantPointerNull>(Ptr) && SI.getPointerAddressSpace() == 0) {
     }
     return nullptr;  // Do not modify these!
   }
 
   // store undef, Ptr -> noop
   if (isa<UndefValue>(Val))
     return EraseInstFromFunction(SI);
 
+  // The code below needs audited and adjusted for unordered atomics
+  if (!SI.isSimple())
+    return nullptr;
+
   // If this store is the last instruction in the basic block (possibly
   // excepting debug info instructions), and if the block ends with an
   // unconditional branch, try to move it to the successor block.
   BBI = SI.getIterator();
   do {
     ++BBI;
   } while (isa<DbgInfoIntrinsic>(BBI) ||
            (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy()));

test/Transforms/InstCombine/store.ll

 for.end:                                          ; preds = %for.cond
   ret void
 ; CHECK-LABEL: @test6(
 ; CHECK: for.cond:
 ; CHECK-NEXT: phi i32 [ 42
 ; CHECK-NEXT: store i32 %storemerge, i32* %gi, align 4, !tbaa !0
 }
 
+define void @dse1(i32* %p) {
+; CHECK-LABEL: dse1
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 0, i32* %p
+  store i32 0, i32* %p
+  ret void
+} 
+
+define void @dse2(i32* %p) {
+; CHECK-LABEL: dse2
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store atomic i32 0, i32* %p unordered, align 4
+  store i32 0, i32* %p
+  ret void
+} 
+
+define void @dse3(i32* %p) {
+; CHECK-LABEL: dse3
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 0, i32* %p
+  store atomic i32 0, i32* %p unordered, align 4
+  ret void
+} 
+
+define void @dse4(i32* %p) {
+; CHECK-LABEL: dse4
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store atomic i32 0, i32* %p unordered, align 4
+  store atomic i32 0, i32* %p unordered, align 4
+  ret void
+} 
+
+; Implementation limit - could remove unordered store here, but
+; currently don't.
+define void @dse5(i32* %p) {
+; CHECK-LABEL: dse5
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store atomic i32 0, i32* %p unordered, align 4
+  store atomic i32 0, i32* %p seq_cst, align 4
+  ret void
+}
+
+define void @write_back1(i32* %p) {
+; CHECK-LABEL: write_back1
+; CHECK-NEXT: ret
+  %v = load i32, i32* %p
+  store i32 %v, i32* %p
+  ret void
+} 
+
+define void @write_back2(i32* %p) {
+; CHECK-LABEL: write_back2
+; CHECK-NEXT: ret
+  %v = load atomic i32, i32* %p unordered, align 4
+  store i32 %v, i32* %p
+  ret void
+} 
+
+define void @write_back3(i32* %p) {
+; CHECK-LABEL: write_back3
+; CHECK-NEXT: ret
+  %v = load i32, i32* %p
+  store atomic i32 %v, i32* %p unordered, align 4
+  ret void
+} 
+
+define void @write_back4(i32* %p) {
+; CHECK-LABEL: write_back4
+; CHECK-NEXT: ret
+  %v = load atomic i32, i32* %p unordered, align 4
+  store atomic i32 %v, i32* %p unordered, align 4
+  ret void
+} 
+
+; Can't remove store due to ordering side effect
+define void @write_back5(i32* %p) {
+; CHECK-LABEL: write_back5
+; CHECK-NEXT: load
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  %v = load atomic i32, i32* %p unordered, align 4
+  store atomic i32 %v, i32* %p seq_cst, align 4
+  ret void
+}
+
+define void @write_back6(i32* %p) {
+; CHECK-LABEL: write_back6
+; CHECK-NEXT: load
+; CHECK-NEXT: ret
+  %v = load atomic i32, i32* %p seq_cst, align 4
+  store atomic i32 %v, i32* %p unordered, align 4
+  ret void
+}
+
 !0 = !{!4, !4, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"float", !1}
 !4 = !{!"int", !1}