Page MenuHomePhabricator

[LV] Try to sink users recursively for first-order recurrences.
Needs ReviewPublic

Authored by fhahn on Jul 30 2020, 9:20 AM.

Details

Summary

Update isFirstOrderRecurrence to explore all uses of a recurrence phi
and check if we can sink them. If there are multiple users to sink, they
are all mapped to the previous instruction.

Consumers of SinkAfter now have to make sure they apply the mappings for
SinkAfter so that the relative order of the sunk instructions is
preserved. We can order them by the reverse comes-before predicate, as
sinking is limited to a single BB for now.

Fixes PR44286 (and another PR or two).

Diff Detail

Event Timeline

fhahn created this revision.Jul 30 2020, 9:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 30 2020, 9:20 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn requested review of this revision.Jul 30 2020, 9:20 AM

https://godbolt.org/z/nXCxW8

This should help to vectorize this code as well, or?

fhahn added a comment.Aug 15 2020, 8:14 AM

https://godbolt.org/z/nXCxW8

This should help to vectorize this code as well, or?

I think the unidentified PHI node in the example above is a pointer induction, not a first order recurrence? Looks like the actual problem is that LV only sees the inner loop fully unrolled and the SLP vectorizer does not vectorize the body of the unrolled loop. If built with -fno-unroll-loops, LV will vectorize the inner loop, but it would probably be better if the SLP vectorizer can just vectorize the unrolled body.

bmahjour added inline comments.Aug 24 2020, 7:06 AM
llvm/lib/Analysis/IVDescriptors.cpp
703

update comment

Does this patch improve some public benchmarks?

fhahn updated this revision to Diff 293552.Sep 22 2020, 12:33 PM
fhahn marked an inline comment as done.

Rebased, updated comment, added additional tests.

Does this patch improve some public benchmarks?

It does not really impact the number of vectorized loops in SPEC2000/SPEC2006/MultiSource. But I think it should have a strictly positive impact (module exposing some existing cost model limitations due to vectorizing more complex loops).

Any futher comments, @bmahjour?

Any futher comments, @bmahjour?

Nope, I'm fine with the changes.

Any futher comments, @bmahjour?

Nope, I'm fine with the changes.

So probably ok to land this now..