[SCEV][NFC] More efficient caching in CompareValueComplexity

[mkazantsev]

Summary

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.

[mkazantsev]

Reused EquivalenceClasses which is the default implementation of DSU in LLVM instead of the custom one.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

 ///   %e = f(%d, %d)
 ///   %f = f(%e, %e)
 ///
 ///   CompareValueComplexity(%f, %c)
 ///
 /// Since we do not continue running this routine on expression trees once we
 /// have seen unequal values, there is no need to track them in the cache.
 static int
-CompareValueComplexity(SmallSet<std::pair<Value *, Value *>, 8> &EqCache,
+CompareValueComplexity(EquivalenceClasses<Value *> &EqCache,
                        const LoopInfo *const LI, Value *LV, Value *RV,
                        unsigned Depth) {
-  if (Depth > MaxValueCompareDepth || EqCache.count({LV, RV}))
+  if (Depth > MaxValueCompareDepth || EqCache.isEquivalent(LV, RV))
     return 0;
 
   // Order pointer values after integer values. This helps SCEVExpander form
   // GEPs.
   bool LIsPointer = LV->getType()->isPointerTy(),
        RIsPointer = RV->getType()->isPointerTy();
   if (LIsPointer != RIsPointer)
     return (int)LIsPointer - (int)RIsPointer;
for (unsigned Idx : seq(0u, LNumOps)) {
       int Result =
           CompareValueComplexity(EqCache, LI, LInst->getOperand(Idx),
                                  RInst->getOperand(Idx), Depth + 1);
       if (Result != 0)
         return Result;
     }
   }
 
-  EqCache.insert({LV, RV});
+  EqCache.unionSets(LV, RV);
   return 0;
 }
 
 // Return negative, zero, or positive, if LHS is less than, equal to, or greater
 // than RHS, respectively. A three-way result allows recursive comparisons to be
 // more efficient.
 static int CompareSCEVComplexity(
     EquivalenceClasses<const SCEV *> &EqCacheSCEV,
static int CompareSCEVComplexity(
   // Aside from the getSCEVType() ordering, the particular ordering
   // isn't very important except that it's beneficial to be consistent,
   // so that (a + b) and (b + a) don't end up as different expressions.
   switch (static_cast<SCEVTypes>(LType)) {
   case scUnknown: {
     const SCEVUnknown *LU = cast<SCEVUnknown>(LHS);
     const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
 
-    SmallSet<std::pair<Value *, Value *>, 8> EqCache;
+    EquivalenceClasses<Value *> EqCache;
     int X = CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue(),
                                    Depth + 1);
     if (X == 0)
       EqCacheSCEV.unionSets(LHS, RHS);
     return X;
   }
 
   case scConstant: {