This is an archive of the discontinued LLVM Phabricator instance.

Look through invertible recurrences in isKnownNonEqual
ClosedPublic

Authored by reames on Apr 5 2021, 7:07 PM.

Details

Summary

This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle.

(Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.)

Diff Detail

Event Timeline

reames created this revision.Apr 5 2021, 7:07 PM
reames requested review of this revision.Apr 5 2021, 7:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 5 2021, 7:07 PM
reames updated this revision to Diff 335376.Apr 5 2021, 7:25 PM

Rebase over test updates following ashr/lshr change

nikic added a comment.Apr 14 2021, 1:44 PM

I think you're missing an important precondition here: You need that Step1 == Step2. Otherwise you could have <0,+,2> and <1,+,1>, which have non-equal start values, but are still equal on the second iteration.

Something the implementation does account for, but doesn't appear to be tested, is if the second operand is invertible rather than the first.

llvm/test/Analysis/ValueTracking/known-non-equal.ll
792

This doesn't test what you want it to because %A/%B are unknown. You need to make them non-equal so that the nowrap flags are the *only* thing that prevents the fold.

926

Same here.

1061

Same here.

1196

Same here.

nikic added a comment.Apr 14 2021, 1:50 PM

I think you're missing an important precondition here: You need that Step1 == Step2. Otherwise you could have <0,+,2> and <1,+,1>, which have non-equal start values, but are still equal on the second iteration.

Ah no, getInvertibleOperand() would fail if the steps didn't match. I think your code is correct, it's just missing test coverage for this case.

reames updated this revision to Diff 338907.Apr 20 2021, 9:48 AM

Rebase over requested test changes - thanks btw, good catch.

reames updated this revision to Diff 338910.Apr 20 2021, 10:01 AM

Rebase over a couple added tests to cover cases which caused reviewer confusion. (For good cause.)

nikic accepted this revision.Apr 20 2021, 10:40 AM

LGTM, thanks!

This revision is now accepted and ready to land.Apr 20 2021, 10:40 AM
This revision was landed with ongoing or failed builds.Apr 20 2021, 10:52 AM
This revision was automatically updated to reflect the committed changes.
nikic added inline comments.Apr 20 2021, 11:53 AM
llvm/lib/Analysis/ValueTracking.cpp
2622

Guess there isn't really a reason why it should be the same operand on both. We could restrict to the case where it is, or else make getInvertibleOperand not return an operand index, and instead return a pair of value to which the (in)equality relation propagates.

reames added inline comments.Apr 20 2021, 11:59 AM
llvm/lib/Analysis/ValueTracking.cpp
2622

Oh, duh. Thanks for this comment, I'd been staring at the assertion failures without having this occur to me. Thanks.

I'll probably do the restrictive form first, then generalize in a separate patch.