This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Eliminates redundant store of an exisiting value (PR16520)
ClosedPublic

Authored by yurai007 on Oct 13 2021, 8:25 AM.

Details

Summary

That's https://reviews.llvm.org/D90328 follow-up.

This change eliminates writes to variables where the value that is being written is already stored in the variable. This achieves the goal by looping through all memory definitions in the current state and getting defining access from each of them. When there is defining access where the write instruction is identical to the original instruction it will remove this redundant write.

For example:

void f() {

x = 1;
if foo() {
   x = 1;
   g();
} else {
  h();
}

}
void g();
void h();

The second x=1 will be eliminated since it is rewriting 1 to x. This pass will produce this:

void f() {

x = 1;
if foo() {
   g();
} else {
  h();
}

}
void g();
void h();

Diff Detail

Event Timeline

yurai007 created this revision.Oct 13 2021, 8:25 AM
yurai007 requested review of this revision.Oct 13 2021, 8:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 13 2021, 8:25 AM
yurai007 updated this revision to Diff 379412.Oct 13 2021, 8:32 AM
xbolva00 added inline comments.Oct 13 2021, 8:49 AM
llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll
314–341

Is this top of trunk?

nikic added a comment.Oct 13 2021, 9:54 AM

This looks reasonable to me.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1947

Exisiting -> Existing

1948

This is a bool.

1950

Also exisiting -> existing

1955

auto *

All comments from the original review still apply.

yurai007 updated this revision to Diff 380285.Oct 18 2021, 12:38 AM
yurai007 marked 5 inline comments as done.Oct 18 2021, 12:42 AM

All comments from the original review still apply.

Do you have something specific in mind? It looks like all comments from old review are done (even if not marked as "fixed" which is quite confusing) except one from Nikita addressed in this change.

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll
314–341

Oops, sorry. Now should be fine.

yurai007 marked an inline comment as done.Oct 18 2021, 12:43 AM

Worth to mention that patch cannot help in resolving pr49927 because stores aren't identical. In theory pr50339 test could be fixed. However for now memcpyies are treated as clobbering ones and this is the reason why elimination is rejected.

https://reviews.llvm.org/D90328#2428525

All comments from the original review still apply.

Do you have something specific in mind? It looks like all comments from old review are done (even if not marked as "fixed" which is quite confusing) except one from Nikita addressed in this change.

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

Yep, it would be better to refer to redundant or no-op stores.

yurai007 updated this revision to Diff 380654.Oct 19 2021, 5:18 AM
yurai007 retitled this revision from [DSE] Eliminates dead store of an exisiting value (PR16520) to [DSE] Eliminates redundant store of an exisiting value (PR16520).

All comments addressed.

fhahn added a comment.Oct 19 2021, 8:11 AM

This achieves the goal by looping through all memory definitions in the current state & each definitions uses.

Does the patch description need updating? Looks like it refers to looping over all uses, but the patch here looks at the defining access of each memdef?

yurai007 edited the summary of this revision. (Show Details)Oct 19 2021, 11:43 AM
fhahn added inline comments.Oct 19 2021, 12:43 PM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1955

can the defining access ever be null?

nikic accepted this revision.Oct 19 2021, 12:48 PM

LGTM with @fhahn's comment addressed.

This revision is now accepted and ready to land.Oct 19 2021, 12:48 PM
fhahn accepted this revision.Oct 19 2021, 1:58 PM

Results in terms of additionally removed stores look good, thanks for picking up the patch!

LGTM as well with the commit addressed.

yurai007 updated this revision to Diff 380967.Oct 20 2021, 8:27 AM
yurai007 marked an inline comment as done.
yurai007 updated this revision to Diff 381498.Oct 22 2021, 3:05 AM
fhahn added a comment.Oct 23 2021, 1:07 AM

Thanks for the updates. I left 2 more additional suggestions, please feel free to address them directly in the commit version.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1965

for debugging purposes it would be helpful if we had a debug message for removed stores here, like we have in other places.

2131

It might be better to eliminate the redundant stores after removePartiallyOverlappedStores, as this might shorten memsets based on state collected earlier. This will become an issue once we support eliminating stores made redundant by a memset, as in D112321

yurai007 updated this revision to Diff 381715.Oct 23 2021, 1:08 AM

@fhahn: Finally there is green light from CI for this change (that's why I hesitated with closing it even if CI failures were irrelevant to patch). Ok, before I push it I can address those 2 remaining comments here.

nikic added inline comments.Oct 23 2021, 7:05 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1962

Actually, why do we need this isReadClobber() check? I don't think we care whether the instruction also reads the value, removing the redundant store is still fine. This would allow us to catch the @pr50339 case as well.

yurai007 updated this revision to Diff 381740.Oct 23 2021, 7:23 AM
yurai007 marked 2 inline comments as done.
yurai007 added inline comments.Oct 25 2021, 1:08 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1962

It's redundant and can be removed. I thought it was needed to ensure correctness for cases with intermediate clobbering (like tests3/test4). I will get rid of check and adjust tests.

yurai007 added inline comments.Oct 25 2021, 2:04 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1962

Ok. Actually we cannot simply get rid of it. Now I see why it is needed. It's for self-reads like:

call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)

Without check memmove is eliminated which is wrong when P and Q alias.

yurai007 marked an inline comment as done.Oct 25 2021, 2:17 AM
nikic added inline comments.Oct 25 2021, 3:29 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1962

Oh right. It's okay to ignore the clobber for memcpy, but not for memmove. Let's leave it as-is for now.

This probably also prevents removing strcat(x, y); strcat(x, y);(with x, y noalias) as the second one will read x as well to find the insertion point. Might be worth adding a test for that case as well.

yurai007 updated this revision to Diff 382251.Oct 26 2021, 3:35 AM
yurai007 marked an inline comment as done.

Addressed comments.

Since all comments are addressed and it has already double LGTM I'm going to close it today.