# Look through invertible recurrences in isKnownNonEqualClosedPublicActions

Authored by reames on Mon, Apr 5, 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.Mon, Apr 5, 7:07 PM
Herald added a reviewer: bollu. Mon, Apr 5, 7:07 PM
reames requested review of this revision.Mon, Apr 5, 7:07 PM
Herald added a project: Restricted Project. Mon, Apr 5, 7:07 PM
reames updated this revision to Diff 335376.Mon, Apr 5, 7:25 PM

Rebase over test updates following ashr/lshr change

nikic added a comment.Wed, Apr 14, 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
998

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.

1134

Same here.

1270

Same here.

1406

Same here.

nikic added a comment.Wed, Apr 14, 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.Tue, Apr 20, 9:48 AM

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

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

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

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

LGTM, thanks!

This revision is now accepted and ready to land.Tue, Apr 20, 10:40 AM
This revision was landed with ongoing or failed builds.Tue, Apr 20, 10:52 AM
This revision was automatically updated to reflect the committed changes.