This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] teach SCEV symbolical execution about overflow intrinsics folding.
ClosedPublic

Authored by shchenz on Jul 9 2019, 8:48 AM.

Details

Summary

Teach SCEV computeExitCountExhaustively() function about folding overflow intrinsics, so we can get trip count.

With this patch, we can get trip count smaller than MaxBruteForceIterations in computeExitCountExhaustively().

SCEV should also be able to get loop trip count for overflow intrinsics loop even the trip count is bigger than the MaxBruteForceIterations(default value is 100). Need another patch for it.

Diff Detail

Repository
rL LLVM

Event Timeline

shchenz created this revision.Jul 9 2019, 8:48 AM

Philip's patch in D64509 sounds related (haven't looked closely at either yet).

reames accepted this revision.Jul 10 2019, 10:23 AM

LGTM. As Nikita points out, this solves many of the same cases as my patch, but it comes at it differently. I think both are useful.

llvm/lib/Analysis/ScalarEvolution.cpp
7675 ↗(On Diff #208702)

It looks like this list is generally more limited than it needs to be. A nice follow up patch would be to look at merging this with the actual constant folding logic somehow and arranging it so they have to stay in sink. (Optional, follow up)

This revision is now accepted and ready to land.Jul 10 2019, 10:23 AM
This revision was automatically updated to reflect the committed changes.