This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] recognize logical and/or pattern
ClosedPublic

Authored by aqjune on Dec 28 2020, 6:55 PM.

Details

Summary

This patch makes SCEV recognize 'select A, B, false' and 'select A, true, B'.
This is a performance improvement that will be helpful after unsound select -> and/or transformation is removed, as discussed in D93065.

SCEV's answers for the select form should be a bit more conservative than the equivalent and A, B / or A, B.
Take this example: https://alive2.llvm.org/ce/z/NsP9ue .
To check whether it is valid for SCEV's computeExitLimit to return min(n, m) as ExactNotTaken value, I put llvm.assume at tgt.
It fails because the exit limit becomes poison if n is zero and m is poison. This is problematic if e.g. the exit value of i is replaced with min(n, m).
If either n or m is constant, we can revive the analysis again. I added relevant tests and put alive2 links there.

If and is used instead, this is okay: https://alive2.llvm.org/ce/z/K9rbJk . Hence the existing analysis is sound.

Diff Detail

Event Timeline

aqjune created this revision.Dec 28 2020, 6:55 PM
aqjune requested review of this revision.Dec 28 2020, 6:55 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 28 2020, 6:55 PM
aqjune added inline comments.Dec 28 2020, 7:00 PM
llvm/test/Analysis/ScalarEvolution/trip-count-andor-selectform.ll
1

This file is copied from test/Analysis/ScalarEvolution/trip-count-andor.ll .
It shows that the result does not degenerate even if select form is used instead of and/or.

nikic added inline comments.Dec 29 2020, 1:28 AM
llvm/test/Analysis/ScalarEvolution/exit-count-select.ll
124

Is there a test where we actually infer something from the first condition? i < 10 && i < m for example?

Unfortunately we don't currently track symbolic max exit count per-exit, so it would have to be constant.

aqjune updated this revision to Diff 313951.Dec 29 2020, 2:44 AM

make SCEV work if either n or m is constant

aqjune marked an inline comment as done.Dec 29 2020, 2:49 AM
aqjune added inline comments.
llvm/test/Analysis/ScalarEvolution/exit-count-select.ll
124

Oh yes, actually there were quite a few cases where SCEV can return an exact trip count.
I updated the SCEV code & added relevant tests.

nikic added inline comments.Dec 29 2020, 6:52 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7617

I think we can still do slightly better here: Even if the exact count is non-constant, we should still be able to take the min of the max (constant) counts in any case, right? In which case I would move this check into the EitherMayExit branch below and only adjust the BECount calculation, while keeping MaxBECount the same.

I think the condition you use here may also need more comment, as I would have expected the check to be only !isa<SCEVConstant>(EL1.ExactNotTaken) initially. Is the reasoning here that if EL0.ExactNotTaken is constant but EL1.ExactNotTaken is not, then either EL0.ExactNotTaken is zero, in which case umin will fold to zero and we won't use the second (potentially poison exit count), or it is non-zero, in which case we know that the other condition will be checked at least once and thus can't be poison.

So basically the general condition here would be if (isKnownNotPoison(EL1.ExactNotTaken) || isKnownNonZero(EL0.ExactNotTaken) || isConstantZero(EL0.ExactNotTaken), where the last case is only safe if we do fold down to zero.

aqjune updated this revision to Diff 314063.Dec 29 2020, 9:13 PM
aqjune marked an inline comment as done.

Calculate MaxBECount, add more comments, guarantee that BECount is folded into zero

aqjune marked an inline comment as done.Dec 29 2020, 9:20 PM
aqjune added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
7617

I think it depends on the meaning of MaxNotTaken. If it is always safe to introduce llvm.assume(i < MaxNotTaken) after exiting the loop, then the same rule will be applied, making umin(EL0.MaxNotTaken, EL1.MaxNotTaken) unsafe.
But, it *seems* MaxNotTaken is okay to be relaxed to allow poison because unlike ExactNotTaken it is unlikely to introduce such assumption or any equation that is equivalent to it. I imagined whether loop versioning would introduce something like that, but loop vectorization needs ExactNotTaken, and for other optimizations there might be other workarounds for this.

aqjune marked an inline comment as done.Dec 29 2020, 9:20 PM
nikic accepted this revision.Dec 31 2020, 3:03 AM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
7634

This will warn about unused BECC in release builds. There is an SCEV::isZero() helper though that checks for SCEVConstant that is zero.

I think you can simplify this whole block to something like:

// Make sure that if EL0.ExactNotTaken was zero, BECount is folded to zero,
// to satisfy condition (3) above.
assert(!EL0.ExactNotTaken->isZero() || BECount->isZero())
This revision is now accepted and ready to land.Dec 31 2020, 3:03 AM
aqjune updated this revision to Diff 314198.Dec 31 2020, 11:32 AM

Update assertion

aqjune marked an inline comment as done.Dec 31 2020, 11:32 AM
aqjune edited the summary of this revision. (Show Details)Dec 31 2020, 11:37 AM
This revision was landed with ongoing or failed builds.Dec 31 2020, 11:38 AM
This revision was automatically updated to reflect the committed changes.
nikic added a comment.Jan 1 2021, 2:15 AM

Something that crossed my mind: While we now handle logical and/or correctly, the same underlying problem also exists for multi-exit loops. In that case we'd combine exit limits from multiple branches via umin(), even though some of them may be poisonous.

aqjune added a comment.Jan 3 2021, 7:15 AM

Something that crossed my mind: While we now handle logical and/or correctly, the same underlying problem also exists for multi-exit loops. In that case we'd combine exit limits from multiple branches via umin(), even though some of them may be poisonous.

Would the place be computeSymbolicMaxBackedgeTakenCount ?
I think UMinUsingSelect or something like that is needed. Expander can lower it into instructions with select performing whether the first argument is non-zero.

Allen added a subscriber: Allen.Mar 8 2022, 6:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2022, 6:14 AM