This is an archive of the discontinued LLVM Phabricator instance.

[LoopIdiom] Don't transform loop into memmove when load from body has more than one use
ClosedPublic

Authored by yurai007 on Aug 12 2021, 7:53 AM.

Details

Summary

This change fixes issue found by Markus: https://reviews.llvm.org/rG11338e998df1
Before this patch following code was transformed to memmove:

for (int i = 15; i >= 1; i--) {
  p[i] = p[i-1];
  sum += p[i-1];
}

However load from p[i-1] is used not only by store to p[i] but also by sum computation.
Therefore we cannot emit memmove in loop header.

Diff Detail

Event Timeline

yurai007 created this revision.Aug 12 2021, 7:53 AM
yurai007 requested review of this revision.Aug 12 2021, 7:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 12 2021, 7:53 AM
yurai007 updated this revision to Diff 365998.Aug 12 2021, 7:57 AM
lebedev.ri added a subscriber: lebedev.ri.EditedAug 12 2021, 8:01 AM

The description doesn't actually describe the problem.
That being said, alive agrees this is a miscompile.
That being said, if load has extra uses,
can we retain the transform by querying AA that there's no overlap?

Not sure about the timing of base patch, but maybe this patch is also candidate for llvm 13 (backport)?

yurai007 edited the summary of this revision. (Show Details)Aug 12 2021, 8:24 AM
efriedma added inline comments.
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1316

I think this belongs earlier, with the other mayLoopAccessLocation check? It's basically a variation of the same check.

@efriedma @lebedev.ri:

I think this belongs earlier, with the other mayLoopAccessLocation check? It's basically a variation of the same check.

can we retain the transform by querying AA that there's no overlap?

I'm not sure if I follow your comments regarding AA (done in mayLoopAccessLocation). The problem in UT is not about 'load'-'store' relationship but about 'load'-'add' pair.
'Load' has 2 users - 'store' and 'add'. How AA can help in case when 'add' instruction is not seen by getModRefInfo at all? Currently getModRefInfo says always NoModRef when reaching 'add'.

yurai007 added inline comments.Aug 13 2021, 6:49 AM
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1316

Reffering to my previous comment - if you mean just moving this check before mayLoopAccessLocation then yes, I agree and you may ignore what I said about AA there :)

Not sure about the timing of base patch, but maybe this patch is also candidate for llvm 13 (backport)?

Indeed I can see base patch on release/13.x. I can cherry-pick change if it get acceptance.

yurai007 updated this revision to Diff 366275.Aug 13 2021, 7:28 AM
yurai007 updated this revision to Diff 366409.Aug 14 2021, 1:03 AM

If the review is going to take a while maybe it is best to revert the offending patch in the meantime.

yurai007 updated this revision to Diff 366952.Aug 17 2021, 10:45 AM

@markus: Since all comments are addressed maybe it's just matter of sending ping to Roman and Eli. @lebedev.ri @eli.friedman can you take a second look please?

Adding proper Eli's account @efriedma.

lebedev.ri added inline comments.Aug 20 2021, 8:47 AM
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1310–1311

The new bailout needs some similar comment.

llvm/test/Transforms/LoopIdiom/basic.ll
1303

Please precommit the test

yurai007 updated this revision to Diff 368361.Aug 24 2021, 8:56 AM
yurai007 marked an inline comment as done.
lebedev.ri accepted this revision.Aug 24 2021, 9:24 AM

LG
I believe this fix needs to be cherry-picked into 13.0 branch?

This revision is now accepted and ready to land.Aug 24 2021, 9:24 AM

LG
I believe this fix needs to be cherry-picked into 13.0 branch?

Thanks. Yes, it's under preparation.