This is an archive of the discontinued LLVM Phabricator instance.

[LSR]: Terminate folding condition use SymbolicMax.
Needs RevisionPublic

Authored by MarkGoncharovAl on Mar 13 2023, 1:30 AM.

Details

Reviewers
eopXD
nikic
Summary

Term-fold-cond does not work with loop that has upredictable break.
For example, algorithm std::find_if.

It is due to calculating ExactBackedgeTakenCount - the condition is too strong.

If previous basic induction variable has use only inside the loop, then we can replace it and use SymbolicMax to calculate BackedgeTakenCount.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptMar 13 2023, 1:30 AM
MarkGoncharovAl requested review of this revision.Mar 13 2023, 1:30 AM

@eopXD , please, make comment to this MR.

@nikic , Please, comment what do you think about using SymbolicMax?

nikic requested changes to this revision.Mar 20 2023, 4:40 AM

Using max exit count is incorrect. The computed max may be larger than the actual trip count of this exit.

What you *can* do though is to use the exact exit count for the latch exit, rather than the BECount for the whole loop, as you are only replacing that one exit. I think that should cover your use-case.

This revision now requires changes to proceed.Mar 20 2023, 4:40 AM