[DSE] Remove dead stores in end blocks containing fence

[anna]

Summary

In Dead store elimination, we currently do not remove stores in end basic blocks (blocks with no successors), when the basic blocks contains fence.

This patch allows us to remove the stores (and leave the fence as-is) when traversing *safe to remove* stores in end basic blocks.

[reames]

Comments inline. Generally looks correct, but needs a revision before I'm comfortable signing off. Also, added JF as a reviewer since he's usually interested in memory model optimizations.

lib/Transforms/Scalar/DeadStoreElimination.cpp

703

Stylistically, this code should be further down. Just after the call site handling would be reasonable.

Comment wise, the explanation is a bit unclear. The key point is that a fence doesn't make a memory location visible to any other thread. It simply ensures ordering of already visible writes. Thus, skipping over the fence doesn't change whether a store is dead or not. I didn't get that from your comment.

test/Transforms/DeadStoreElimination/fence.ll

52

I'm not familiar with the details of byval parameters. Can you confirm this was copied from an existing test and the only change is adding the fence?

[dexonsmith]

I don't see a patch on the list. Is this a problem with how you created the Phab review?

[anna]

In D22001#474590, @dexonsmith wrote:

I don't see a patch on the list. Is this a problem with how you created the Phab review?

Sent patch separately to @dexonsmith. Response on patch:
isa works on references as well as pointers, so this can just be

if (isa<FenceInst>(*BBI))

Agree with Duncan, but the llvm ref states that this implicit conversion comes at a cost, and at some point in time, may be reverted to mean what standard iterators are. So, I'll leave it as-is to avoid any fix-ups required in future.

"Unfortunately, these implicit conversions come at a cost; they prevent these iterators from conforming to standard iterator conventions, and thus from being usable with standard algorithms and containers. Because of this, these implicit conversions may be removed some day, and operator* changed to return a pointer instead of a reference."
http://llvm.org/docs/ProgrammersManual.html#basic-inspection-and-traversal-routines

lib/Transforms/Scalar/DeadStoreElimination.cpp

703

That's right, updated the comment to say exactly why we do not care about the fence instruction (i.e. we can remove the fence, but we cannot currently remove stores that have ordering constraints).

test/Transforms/DeadStoreElimination/fence.ll

52

No, this test is from an existing test which already contains the fence. The only change is the addition of the byval attribute.
In handleEndBlock, 3 kinds of store locations are considered while traversing the basic block:

1. stack allocated locations
2. attributes passed byval -- there's a check in the handleEndBlock.

if (AI.hasByValOrInAllocaAttr()) DeadStackObjects.insert(&AI);

3. locations generated by calloc-like statements and are not captured.

[anna]

Updated comment on skipping fence, moved the check to below CallSite check.

[jfb]

I'm not sure I understand the mentions of end block. Why is this relevant? A dead store is dead, regardless of successors. Could you explain?

If it is relevant, I'd like to see a test that explains the relevance, and makes sure correctness is retained if there is a successor.

test/Transforms/DeadStoreElimination/fence.ll

80

%P2 is useless here.

[reames]

In D22001#475099, @anna wrote:

In D22001#474590, @dexonsmith wrote:

isa works on references as well as pointers, so this can just be

if (isa<FenceInst>(*BBI))

Agree with Duncan, but the llvm ref states that this implicit conversion comes at a cost, and at some point in time, may be reverted to mean what standard iterators are. So, I'll leave it as-is to avoid any fix-ups required in future.

"Unfortunately, these implicit conversions come at a cost; they prevent these iterators from conforming to standard iterator conventions, and thus from being usable with standard algorithms and containers. Because of this, these implicit conversions may be removed some day, and operator* changed to return a pointer instead of a reference."
http://llvm.org/docs/ProgrammersManual.html#basic-inspection-and-traversal-routines

Given this usage is wide spread through the codebase and would need to be fixed in bulk anyways, I'd rather see the simpler code here.

[reames]

In D22001#476915, @jfb wrote:

I'm not sure I understand the mentions of end block. Why is this relevant? A dead store is dead, regardless of successors. Could you explain?

If it is relevant, I'd like to see a test that explains the relevance, and makes sure correctness is retained if there is a successor.

The relevance is in the context of the existing code. The current code *detects* that stores are dead by walking backwards from the terminator of a block without successors (end block) and looking for unobserved stores to function local objects.

[reames]

LGTM w/ comments addressed.

lib/Transforms/Scalar/DeadStoreElimination.cpp

781

Minor: As JF's question points out, mentioning the end block in the comment implies that the fact it's an end block is important for the reasoning. The important part is that the fence doesn't make a dead store non-dead. The fact that the surrounding code determines deadness only in end blocks is irrelevant to the key logic your documenting.

test/Transforms/DeadStoreElimination/fence.ll

50

Comment is again confusing. The key thing to highlight is that a fence doesn't make an otherwise thread local store visible.

[anna]

addressed Philip and JF comments.

[jfb]

lgtm

[llvm-commits]

anna marked an inline comment as done.
anna added a comment.

In http://reviews.llvm.org/D22001#474590, @dexonsmith wrote:

I don't see a patch on the list. Is this a problem with how you created the Phab review?

Sent patch separately to @dexonsmith. Response on patch:
isa works on references as well as pointers, so this can just be

if (isa<FenceInst>(*BBI))

Agree with Duncan, but the llvm ref states that this implicit conversion comes at a cost, and at some point in time, may be reverted to mean what standard iterators are. So, I'll leave it as-is to avoid any fix-ups required in future.

What implicit conversion??

"Unfortunately, these implicit conversions come at a cost; they prevent these iterators from conforming to standard iterator conventions, and thus from being usable with standard algorithms and containers. Because of this, these implicit conversions may be removed some day, and operator* changed to return a pointer instead of a reference."
http://llvm.org/docs/ProgrammersManual.html#basic-inspection-and-traversal-routines

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[dexonsmith]

I still think this should be the version of isa<> that takes a reference.

[anna]

In D22001#477281, @dexonsmith wrote:

I still think this should be the version of isa<> that takes a reference.

Yes, I've changed it to directly take the reference (as done in other dyn_cast checks such as LoadInst, MemTransferInst just below the fenceInst check).

if (isa<FenceInst>(BBI))
      continue;

It's better to have it as a reference, as the same is done in all other checks for BBI.

The implicit conversion cost as stated in the lang ref:
Unfortunately, these implicit conversions come at a cost; they prevent these iterators from conforming to standard iterator conventions, and thus from being usable with standard algorithms and containers. For example, they prevent the following code, where B is a BasicBlock, from compiling:

llvm::SmallVector<llvm::Instruction *, 16>(B->begin(), B->end());
Because of this, these implicit conversions may be removed some day, and operator* changed to return a pointer instead of a reference.

[anna]

That’s right Duncan. The implicit conversion is not present when we take the reference version of isa:

isa<FenceInst>(*BBI)

Was thinking of the pointer version.

So, I’ve changed it to the above instead of isa<FenceInst>(BBI)

Anna

[anna]

use reference version of isa<> for the FenceInst check.

lib/Transforms/Scalar/DeadStoreElimination.cpp

if (AI.hasByValOrInAllocaAttr())
       DeadStackObjects.insert(&AI);
 
   const DataLayout &DL = BB.getModule()->getDataLayout();
 
   // Scan the basic block backwards
   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
     --BBI;
 
     // If we find a store, check to see if it points into a dead stack value.
     if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
       // See through pointer-to-pointer bitcasts
       SmallVector<Value *, 4> Pointers;
       GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
 
       // Stores to stack values are valid candidates for removal.
       bool AllDead = true;
       for (Value *Pointer : Pointers)
if (auto CS = CallSite(&*BBI)) {
       // If all of the allocas were clobbered by the call then we're not going
       // to find anything else to process.
       if (DeadStackObjects.empty())
         break;
 
       continue;
     }
 
+    // We can remove the dead stores, irrespective of the fence and its ordering
+    // (release/acquire/seq_cst). Fences only constraints the ordering of
+    // already visible stores, it does not make a store visible to other
+    // threads. So, skipping over a fence does not change a store from being
+    // dead.
+    if (isa<FenceInst>(*BBI))
+      continue;
+
     MemoryLocation LoadedLoc;
 
     // If we encounter a use of the pointer, it is no longer considered dead
     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
       if (!L->isUnordered()) // Be conservative with atomic/volatile load
         break;
       LoadedLoc = MemoryLocation::get(L);
     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {

test/Transforms/DeadStoreElimination/fence.ll

 ; CHECK: fence
 ; CHECK: store
 ; CHECK: ret
   store i32 5, i32* %addr.i, align 4
   fence acquire
   store i32 5, i32* %addr.i, align 4
   ret void
 }
+
+; We DSE stack alloc'ed and byval locations, in the presence of fences.
+; Fence does not make an otherwise thread local store visible.
+; Right now the DSE in presence of fence is only done in end blocks (with no successors),
+; but the same logic applies to other basic blocks as well.
+; The store to %addr.i can be removed since it is a byval attribute
+define void @test3(i32* byval %addr.i) {
+; CHECK-LABEL: @test3
+; CHECK-NOT: store
+; CHECK: fence
+; CHECK: ret
+  store i32 5, i32* %addr.i, align 4
+  fence release
+  ret void
+}
+
+declare void @foo(i8* nocapture %p)
+
+declare noalias i8* @malloc(i32)
+
+; DSE of stores in locations allocated through library calls.
+define void @test_nocapture() {
+; CHECK-LABEL: @test_nocapture
+; CHECK: malloc
+; CHECK: foo
+; CHECK-NOT: store
+; CHECK: fence
+  %m  =  call i8* @malloc(i32 24)
+  call void @foo(i8* %m)
+  store i8 4, i8* %m
+  fence release
+  ret void
+}
+
+
+; This is a full fence, but it does not make a thread local store visible.
+; We can DSE the store in presence of the fence.
+define void @fence_seq_cst() {
+; CHECK-LABEL: @fence_seq_cst
+; CHECK-NEXT: fence seq_cst
+; CHECK-NEXT: ret void
+  %P1 = alloca i32
+  store i32 0, i32* %P1, align 4
+  fence seq_cst
+  store i32 4, i32* %P1, align 4
+  ret void
+}
+