This is an archive of the discontinued LLVM Phabricator instance.

[ZoneAlgo] Allow two writes that write identical values into same array slot
AbandonedPublic

Authored by grosser on Aug 7 2017, 12:58 PM.

Details

Summary

Two write statements which write into the very same array slot generally are
conflicting. However, in case the value that is written is identical, this
does not cause any problem. Hence, allow such write pairs in this specific
situation.

Event Timeline

grosser created this revision.Aug 7 2017, 12:58 PM
grosser updated this revision to Diff 110070.Aug 7 2017, 1:25 PM

Improve style

grosser updated this revision to Diff 110075.Aug 7 2017, 1:28 PM

Update formatting II

grosser updated this revision to Diff 110077.Aug 7 2017, 1:29 PM

Update formatting III

Harbormaster completed remote builds in B9100: Diff 110077.
Meinersbur accepted this revision.Aug 7 2017, 2:58 PM
Meinersbur added inline comments.
lib/CodeGen/PPCGCodeGeneration.cpp
199–200

[Nit] unrelated?

228

[Nit] unrelated?

237

[Nit] unrelated?

lib/Transform/ZoneAlgo.cpp
291

[Suggestion] This will reject as soon as there is a third store that writes a different value somewhere unrelated. Maybe add a TODO comment and/or add a FAIL: * test case to improve this some day?

292–293

[Suggestion] Does either isLatestArrayKind() or MA->isOriginalArrayKind() suffice?
(I think we only implemented changing scalar to array access, not the other way around; scalar accesses are assumed to either at the beginning or end of the statement, never associated with a LoadInst/StoreInst)

test/ForwardOpTree/forward_load_double_write.ll
3
  • Update the comment what's tested here.
This revision is now accepted and ready to land.Aug 7 2017, 2:58 PM
etherzhhb added inline comments.
test/ForwardOpTree/forward_load_double_write.ll
21–22

Isn't this could be "canonicalized" by gvn?

etherzhhb added inline comments.Aug 7 2017, 3:39 PM
test/ForwardOpTree/forward_load_double_write.ll
21–22

or dead store elimination

grosser added inline comments.Aug 7 2017, 3:47 PM
test/ForwardOpTree/forward_load_double_write.ll
21–22

Maybe then this is a non-optimal test case. In case there are other memory accesses between these two stores, gvn and dead store elimination is often not effective. Clearly, this is not very visible in this simple test case.

etherzhhb added inline comments.Aug 7 2017, 3:55 PM
test/ForwardOpTree/forward_load_double_write.ll
21–22

Ok

Meinersbur added inline comments.Aug 8 2017, 4:46 AM
test/ForwardOpTree/forward_load_double_write.ll
21–22

This covers a special situation occurring in Polybench's covariance/correlation (and typical in algorithms that cover symmetric matrices):

for (int i = 0; i < n; i+=1)
  for (int j = 0; j <= i; j+=1) {
    double x = ...;
    C[i][j] = x;
    C[j][i] = x;
  }

For i==j, the same value is written twice to the same element. Double writes to the same element are not allowed in DeLICM because its algorithm does not see which of the writes is effective. But if its the same value anyway, it doesn't matter.

LLVM passes, however, cannot simplify this because the write is necessary for i != j (unless it would add a condition for one of the writes to occur only if i != j)

etherzhhb added inline comments.Aug 9 2017, 12:15 AM
test/ForwardOpTree/forward_load_double_write.ll
21–22

Maybe we could also add a reduced case from this, and put your comments to the reduced case?

Meinersbur added inline comments.Aug 9 2017, 2:21 AM
test/ForwardOpTree/forward_load_double_write.ll
21–22

Isn't forward_load_double_write.ll such a test case?

Meinersbur added inline comments.Aug 9 2017, 2:31 AM
test/ForwardOpTree/forward_load_double_write.ll
21–22

I added the motivation for onlySameValueWrites() into its comment.

singam-sanjay edited edge metadata.Aug 22 2017, 7:39 AM

Could you suggest a paper I could read to get to know this Zone Algorithm ?

grosser abandoned this revision.Sep 1 2017, 10:56 PM

I think this is not needed any more!