[SCEV][NFC] More efficient caching in CompareValueComplexity
authorMax Kazantsev <max.kazantsev@azul.com>
Tue, 28 Nov 2017 08:26:43 +0000 (08:26 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Tue, 28 Nov 2017 08:26:43 +0000 (08:26 +0000)
commit6e78ad35cc155ad838ed9eda1d319b4eab5c454f
tree298c49aa12b2cf0e3a9dcca5f6002139f02ef90e
parent2d614ced553bd9288959f8d5194e5463aa27d60e
[SCEV][NFC] More efficient caching in CompareValueComplexity

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

This patch replaces this set with `EquivalenceClasses` that merges Values into equivalence sets so that
any two values from the same set are equal from point of `CompareValueComplexity`. This, in particular,
allows us to prove the fact from example above.

Differential Revision: https://reviews.llvm.org/D40429

llvm-svn: 319153
llvm/lib/Analysis/ScalarEvolution.cpp