This is an archive of the discontinued LLVM Phabricator instance.

[instcombine] Collapse trivial or/and recurrences
ClosedPublic

Authored by reames on Feb 26 2021, 1:38 PM.

Details

Summary

If we have a recurrence of the form <Start, Or, Step> or <Start, And, Step> we know that the value taken by the recurrence stabilizes on the first iteration (provided step is loop invariant). We can exploit that fact to remove the loop carried dependence in the recurrence.

The motivation is mostly consistency and demonstrating some recently added infrastructure for identifying recurrences, but as shown in the test change, we do seem to see them outside contrived examples as well.

Diff Detail

Event Timeline

reames created this revision.Feb 26 2021, 1:38 PM
reames requested review of this revision.Feb 26 2021, 1:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 26 2021, 1:38 PM
nikic added inline comments.Feb 27 2021, 12:36 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1991

DT is required in InstCombine. You should also be able to use DT directly without going through SimplifyQuery.

reames updated this revision to Diff 327821.Mar 3 2021, 9:11 AM

address review comment

This looks reasonable to me, but is this falling into the traditional pitfail of not dealing with all of the commutative variants, etc?
What happens if BinaryOperator's both operands are recurrences, and the first one isn't the one we can deal with? (DT.dominates(Step, PN))

This looks reasonable to me, but is this falling into the traditional pitfail of not dealing with all of the commutative variants, etc?
What happens if BinaryOperator's both operands are recurrences, and the first one isn't the one we can deal with? (DT.dominates(Step, PN))

Honestly, I wouldn't bother to handle this case. It really seems like perfection being the enemy of the good.

lebedev.ri accepted this revision.Mar 8 2021, 8:59 AM

LG, please commit and and or parts as two separate patches.

This revision is now accepted and ready to land.Mar 8 2021, 8:59 AM
reames closed this revision.Mar 8 2021, 3:59 PM

Landed in two parts, see comments on review for links.