[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 ↗

(On Diff #42231)

"for ordered atomic stores"

1031 ↗

(On Diff #42231)

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

1058 ↗

(On Diff #42231)

"to be audited"

test/Transforms/InstCombine/store.ll

127 ↗

(On Diff #42231)

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

136 ↗

(On Diff #42231)

Same.

196 ↗

(On Diff #42231)

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 ↗

(On Diff #42231)

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 ↗

(On Diff #42231)

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 ↗

(On Diff #42231)

same answer

196 ↗

(On Diff #42231)

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

1089 ↗

(On Diff #42951)

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 ↗

(On Diff #42951)

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

[reames]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1089 ↗

(On Diff #42951)

@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 ↗

(On Diff #42951)

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

1089 ↗

(On Diff #42951)

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.

llvm/trunk/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.
-  // FIXME: Some bits are legal for atomic stores; needs refactoring.
-  if (!SI.isSimple()) return nullptr;
+  // Don't hack volatile/ordered stores.
+  // FIXME: Some bits are legal for ordered atomic stores; needs refactoring.
+  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)) {
+        assert(SI.isUnordered() && "can't eliminate ordering operation");
         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 (BBI->mayWriteToMemory() || BBI->mayReadFromMemory())
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 to be 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()));

llvm/trunk/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
+} 
+
+; Slightly subtle: if we're mixing atomic and non-atomic access to the
+; same location, then the contents of the location are undefined if there's
+; an actual race.  As such, we're free to pick either store under the 
+; assumption that we're not racing with any other thread.
+define void @dse2(i32* %p) {
+; CHECK-LABEL: dse2
+; CHECK-NEXT: store i32 0, i32* %p
+; 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 atomic i32 0, i32* %p unordered, align 4
+; 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 atomic i32 0, i32* %p unordered, align 4
+; 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
+}
+
+define void @write_back7(i32* %p) {
+; CHECK-LABEL: write_back7
+; CHECK-NEXT: load
+; CHECK-NEXT: ret
+  %v = load atomic volatile 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}