This is an archive of the discontinued LLVM Phabricator instance.

[SCEV][NFC] More efficient caching in CompareSCEVComplexity
ClosedPublic

Authored by mkazantsev on Nov 24 2017, 4:48 AM.

Details

Summary

Currently, we use a set of pairs to cache responces like CompareSCEVComplexity(X, Y) == 0. If we had
proved that CompareSCEVComplexity(S1, S2) == 0 and CompareSCEVComplexity(S2, S3) == 0,
this cache does not allow us to prove that CompareSCEVComplexity(S1, S3) is also 0.

This patch replaces this set with EquivalenceClasses any two values from the same set are equal from
point of CompareSCEVComplexity . This, in particular, allows us to prove the fact from example above.

This gives a significant compile time speedup on an internal test with huge SCEVs.

Diff Detail

Event Timeline

mkazantsev edited the summary of this revision. (Show Details)Nov 24 2017, 4:51 AM
sanjoy accepted this revision.Nov 24 2017, 1:30 PM
This revision is now accepted and ready to land.Nov 24 2017, 1:30 PM
mkazantsev edited the summary of this revision. (Show Details)
mkazantsev added a reviewer: dberlin.

I've replaced the caching structure with EquivalenceClasses which is existing implementation of DSU in LLVM (the logic remains the same).

This revision was automatically updated to reflect the committed changes.