Page MenuHomePhabricator

[DSE] Remove dead stores in end blocks containing fence
ClosedPublic

Authored by anna on Jul 5 2016, 10:06 AM.

Details

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.

Diff Detail

Event Timeline

anna updated this revision to Diff 62769.Jul 5 2016, 10:06 AM
anna retitled this revision from to [DSE] Remove dead stores in end blocks containing fence.
anna updated this object.
anna updated this object.Jul 5 2016, 10:42 AM
anna added reviewers: reames, dexonsmith, sanjoy.
anna set the repository for this revision to rL LLVM.
anna added a subscriber: llvm-commits.
reames requested changes to this revision.Jul 5 2016, 1:40 PM
reames added a reviewer: jfb.
reames edited edge metadata.

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
695

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?

This revision now requires changes to proceed.Jul 5 2016, 1:41 PM
dexonsmith edited edge metadata.Jul 5 2016, 2:28 PM
dexonsmith added a subscriber: dexonsmith.

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

anna marked an inline comment as done.Jul 6 2016, 6:18 AM

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
695

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);
  1. locations generated by calloc-like statements and are not captured.
anna updated this revision to Diff 62856.Jul 6 2016, 6:33 AM
anna edited edge metadata.
anna marked an inline comment as done.
anna updated this object.

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

jfb edited edge metadata.Jul 7 2016, 10:23 AM

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.

In D22001#475099, @anna 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.

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 accepted this revision.Jul 7 2016, 10:35 AM
reames edited edge metadata.

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.

This revision is now accepted and ready to land.Jul 7 2016, 10:35 AM
anna updated this revision to Diff 63115.Jul 7 2016, 12:07 PM
anna edited edge metadata.
anna marked an inline comment as done.

addressed Philip and JF comments.

jfb accepted this revision.Jul 7 2016, 12:40 PM
jfb edited edge metadata.

lgtm

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
llvm-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

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

anna marked 2 inline comments as done.Jul 7 2016, 1:28 PM

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 added a subscriber: anna.Jul 7 2016, 1:43 PM

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 updated this revision to Diff 63132.Jul 7 2016, 1:48 PM
anna edited edge metadata.

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

This revision was automatically updated to reflect the committed changes.