[SCEV] limit recursion depth of CompareSCEVComplexity

[dfukalov]

Summary

CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time.

Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter.

[dfukalov]

current test input .ll is quite big (~1000 lines). I'm trying to reduce it, but not sure I'll be able to. Should I add it's big version to the change?

[sanjoy]

Hi Dmitry,

Please upload the patch with context (http://llvm.org/docs/Phabricator.html)

Have you checked if this is solely due to the depth of the expressions, or if this is due to some exponential behavior? Can this be solved using a cache, like in CompareValueComplexity (though it also has a Depth so perhaps it isn't a good example).

As far as the test case goes, you can always add a C++ test case to unittests/ that generates the IR or SCEV expression in memory. I agree with you in that we should avoid adding excessively large test files to tests/

[• tstellarAMD]

Can you check if this fixes the tests cases from these bugs:
https://llvm.org/bugs/show_bug.cgi?id=28721
https://llvm.org/bugs/show_bug.cgi?id=30257

[dfukalov]

Hi Sanjoy,

the issue is in SLSR pass when it tries to construct with getAddExpr and getMulExpr on a source that is similar to test case from https://llvm.org/bugs/show_bug.cgi?id=28721 but much more bigger: >1000 lines of muls+adds in main block and has 8 phis instead of 2.

Tom,
as I mentioned above, the input caused issue is very similar to test case of bug 28721 and in my case it hangs in SLSR pass too. But both bugs are not reproducible for me.

I'll try to create a test case by expanding one from bug 28721.

[dfukalov]

Hi Sanjoy,

I've reduced testcase to 400 lines. Then I tried to use cache as you suggested and it fixes the issue indeed. I'm going to re-test and up[date patch.

But I would add recursion depth control since there is no guarantee the cache will help in all possible cases. For example, during test case reduction I had input variants of input that caused hangs in CompareSCEVComplexity called from other (not SLSR) passes. What do you think? If you agree with recursion depth, should it be new parameter (as in my first implementation) or a hard-coded value as for CompareValueComplexity?

[sanjoy]

Hi Daniil,

In D26389#590731, @dfukalov wrote:

I've reduced testcase to 400 lines. Then I tried to use cache as you suggested and it fixes the issue indeed. I'm going to re-test and up[date patch.

Great!

As I said before, if the test case is repetitive then it is probably better to generate the IR in memory using IRBuilder and put the test case in unittests/. Otherwise a 400 line file does not sound that bad.

But I would add recursion depth control since there is no guarantee the cache will help in all possible cases. For example, during test case reduction I had input variants of input that caused hangs in CompareSCEVComplexity called from other (not SLSR) passes.

I think a recursion depth as a stopgap measure is fine. For now I'd add a max depth as a cl::opt and use the same depth in both CompareValueComplexity and CompareSCEVComplexity (that is, don't "forget" the depth when CompareSCEVComplexity calls into CompareValueComplexity).

I'd make this max depth fairly high by default (perhaps 64 or something) since, as I understand it, the caching should take care of avoiding any exponential behavior, and if the we're spending lots of time in CompareSCEVComplexity then the SCEV expression itself is very complex. In this (latter) case it is defensible for CompareSCEVComplexity to take time (it simply has more work to do), but only up to a point.

What do you think? If you agree with recursion depth, should it be new parameter (as in my first implementation) or a hard-coded value as for CompareValueComplexity?

[dfukalov]

Hi Sanjoy,

I've updated the change and added unittest. I made it since reduced to 400 lines testcase can be compiled by ~10 sec on a fast machine without the fix, but the suggested unittest has "softhang" behavior.

For my initial big testcase recursion depth was up to 50+ an I never completed the compilation on a quite fast CPU. So I suggest to set it 32 by default.

[dfukalov]

Hi Sanjoy, would you please check the updated diff and test?

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

IMO a slightly better pattern would have been to have EqCache be a SmallSet of std::pair<PointerUnion<Value *, const SCEV *>, PointerUnion<Value *, const SCEV *>> and to re-use the same cache in CompareValueComplexity.

If you agree, can you do that as a followup change?

[dfukalov]

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

I'm not sure this will actually be a re-use: any correct SCEV * is not equal to any correct Value * (except nullptr values), so the combined cache will contain all of items from both current caches, without memory usage reducing. And if it so, any search in a combined cache will be the same or slower.
E.g. there is an edge case: we can try to find actual value typed std::pair<const SCEV*, const SCEV*> in a set that contains std::pair<Value*, Value*> only. Do you agree?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

We might win in some edge cases by since we'll persist the same value cache across multiple SCEVUnknown instances in the same SCEV tree. That is:

%x = ...
%y = ...
%x1 = add %x, 20
%y1 = add %y, 20

If LHS has SCEVUnknowns for %x and %x1, and RHS has SCEVUnknowns for %y and %y1, and then a combined cache will save us from recomputing CompareValueComplexity(%x, %y) twice.

But this is a minimal gain -- please don't block the commit on getting this right.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

So, for instance, persisting a (Value *, Value *) set for the entirety of CompareSCEVComplexity will also do the same thing (and will probably be mildly cleaner).

[dfukalov]

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

Yes, I got it. I'll try to get a statistic on my hard case to check actual sizes of both caches (for an entire CompareSCEVComplexity call tree). It seems if they will be quite big and will have almost same size it will be better to combine caches of pairs (Value *, Value *) separately.

What do you think about improving caches further to cache all already estimated values, not only zeros?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

704 ↗

(On Diff #77530)

What do you think about improving caches further to cache all already estimated values, not only zeros?

IIUC that won't help as much since (by design) only the last leaf query and the "path" from the last leaf query to the root query in CompareXXXComplexity returns a non-zero value, so it sound less "bang for the buck" to me. The big gains are by speeding up expressions that look "almost" equal which you've already addressed in this patch.

However, if you want to do the work to cache non-zero complexity differences then I won't stop you. :)

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

VerifySCEVMap("verify-scev-maps",
                   cl::desc("Verify no dangling value in ScalarEvolution's "
                            "ExprValueMap (slow)"));
 
 static cl::opt<unsigned> MulOpsInlineThreshold(
     "scev-mulops-inline-threshold", cl::Hidden,
     cl::desc("Threshold for inlining multiplication operands into a SCEV"),
     cl::init(1000));
 
+static cl::opt<unsigned>
+    MaxCompareDepth("scalar-evolution-max-compare-depth", cl::Hidden,
+                    cl::desc("Maximum depth of recursive compare complexity"),
+                    cl::init(32));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 

 ///
 ///   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,
                        const LoopInfo *const LI, Value *LV, Value *RV,
-                       unsigned DepthLeft = 2) {
-  if (DepthLeft == 0 || EqCache.count({LV, RV}))
+                       unsigned Depth) {
+  if (Depth > MaxCompareDepth || EqCache.count({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;
if (const auto *LInst = dyn_cast<Instruction>(LV)) {
     unsigned LNumOps = LInst->getNumOperands(),
              RNumOps = RInst->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 
     for (unsigned Idx : seq(0u, LNumOps)) {
       int Result =
           CompareValueComplexity(EqCache, LI, LInst->getOperand(Idx),
-                                 RInst->getOperand(Idx), DepthLeft - 1);
+                                 RInst->getOperand(Idx), Depth + 1);
       if (Result != 0)
         return Result;
-      EqCache.insert({LV, RV});
     }
   }
 
+  EqCache.insert({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(const LoopInfo *const LI, const SCEV *LHS,
-                                 const SCEV *RHS) {
+static int CompareSCEVComplexity(
+    SmallSet<std::pair<const SCEV *, const SCEV *>, 8> &EqCacheSCEV,
+    const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS,
+    unsigned Depth = 0) {
   // Fast-path: SCEVs are uniqued so we can do a quick equality check.
   if (LHS == RHS)
     return 0;
 
   // Primarily, sort the SCEVs by their getSCEVType().
   unsigned LType = LHS->getSCEVType(), RType = RHS->getSCEVType();
   if (LType != RType)
     return (int)LType - (int)RType;
 
+  if (Depth > MaxCompareDepth || EqCacheSCEV.count({LHS, RHS}))
+    return 0;
   // 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;
-    return CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue());
+    int X = CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue(),
+                                   Depth + 1);
+    if (X == 0)
+      EqCacheSCEV.insert({LHS, RHS});
+    return X;
   }
 
   case scConstant: {
     const SCEVConstant *LC = cast<SCEVConstant>(LHS);
     const SCEVConstant *RC = cast<SCEVConstant>(RHS);
 
     // Compare constant values.
     const APInt &LA = LC->getAPInt();
case scAddRecExpr: {
 
     // Addrec complexity grows with operand count.
     unsigned LNumOps = LA->getNumOperands(), RNumOps = RA->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 
     // Lexicographically compare.
     for (unsigned i = 0; i != LNumOps; ++i) {
-      long X = CompareSCEVComplexity(LI, LA->getOperand(i), RA->getOperand(i));
+      int X = CompareSCEVComplexity(EqCacheSCEV, LI, LA->getOperand(i),
+                                    RA->getOperand(i), Depth + 1);
       if (X != 0)
         return X;
     }
-
+    EqCacheSCEV.insert({LHS, RHS});
     return 0;
   }
 
   case scAddExpr:
   case scMulExpr:
   case scSMaxExpr:
   case scUMaxExpr: {
     const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
     const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 
     // Lexicographically compare n-ary expressions.
     unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 
     for (unsigned i = 0; i != LNumOps; ++i) {
       if (i >= RNumOps)
         return 1;
-      long X = CompareSCEVComplexity(LI, LC->getOperand(i), RC->getOperand(i));
+      int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(i),
+                                    RC->getOperand(i), Depth + 1);
       if (X != 0)
         return X;
     }
-    return (int)LNumOps - (int)RNumOps;
+    EqCacheSCEV.insert({LHS, RHS});
+    return 0;
   }
 
   case scUDivExpr: {
     const SCEVUDivExpr *LC = cast<SCEVUDivExpr>(LHS);
     const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
 
     // Lexicographically compare udiv expressions.
-    long X = CompareSCEVComplexity(LI, LC->getLHS(), RC->getLHS());
+    int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getLHS(), RC->getLHS(),
+                                  Depth + 1);
     if (X != 0)
       return X;
-    return CompareSCEVComplexity(LI, LC->getRHS(), RC->getRHS());
+    X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getRHS(), RC->getRHS(),
+                              Depth + 1);
+    if (X == 0)
+      EqCacheSCEV.insert({LHS, RHS});
+    return X;
   }
 
   case scTruncate:
   case scZeroExtend:
   case scSignExtend: {
     const SCEVCastExpr *LC = cast<SCEVCastExpr>(LHS);
     const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
 
     // Compare cast expressions by operand.
-    return CompareSCEVComplexity(LI, LC->getOperand(), RC->getOperand());
+    int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(),
+                                  RC->getOperand(), Depth + 1);
+    if (X == 0)
+      EqCacheSCEV.insert({LHS, RHS});
+    return X;
   }
 
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 /// Given a list of SCEV objects, order them by their complexity, and group
 /// objects of the same complexity together by value.  When this routine is
 /// finished, we know that any duplicates in the vector are consecutive and that
 /// complexity is monotonically increasing.
 ///
 /// Note that we go take special precautions to ensure that we get deterministic
 /// results from this routine.  In other words, we don't want the results of
 /// this to depend on where the addresses of various SCEV objects happened to
 /// land in memory.
 ///
 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
                               LoopInfo *LI) {
   if (Ops.size() < 2) return;  // Noop
+
+  SmallSet<std::pair<const SCEV *, const SCEV *>, 8> EqCache;
   if (Ops.size() == 2) {
     // This is the common case, which also happens to be trivially simple.
     // Special case it.
     const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
-    if (CompareSCEVComplexity(LI, RHS, LHS) < 0)
+    if (CompareSCEVComplexity(EqCache, LI, RHS, LHS) < 0)
       std::swap(LHS, RHS);
     return;
   }
 
   // Do the rough sort by complexity.
   std::stable_sort(Ops.begin(), Ops.end(),
-                   [LI](const SCEV *LHS, const SCEV *RHS) {
-                     return CompareSCEVComplexity(LI, LHS, RHS) < 0;
+                   [&EqCache, LI](const SCEV *LHS, const SCEV *RHS) {
+                     return CompareSCEVComplexity(EqCache, LI, LHS, RHS) < 0;
                    });
 
   // Now that we are sorted by complexity, group elements of the same
   // complexity.  Note that this is, at worst, N^2, but the vector is likely to
   // be extremely short in practice.  Note that we take this approach because we
   // do not want to depend on the addresses of the objects we are grouping.
   for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
     const SCEV *S = Ops[i];

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
   for (StringRef FuncName : {"f_2", "f_3", "f_4"})
     runWithFunctionAndSE(*M, FuncName, [&](Function &F, ScalarEvolution &SE) {
       CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")),
                                SE.getSCEV(getInstructionByName(F, "y")),
                                SE.getSCEV(getInstructionByName(F, "z")));
     });
 }
 
+TEST_F(ScalarEvolutionsTest, SCEVCompareComplexity) {
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+  BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F);
+  BranchInst::Create(LoopBB, EntryBB);
+
+  auto *Ty = Type::getInt32Ty(Context);
+  SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);
+
+  Acc[0] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[1] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[2] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[3] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[4] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[5] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[6] = PHINode::Create(Ty, 2, "", LoopBB);
+  Acc[7] = PHINode::Create(Ty, 2, "", LoopBB);
+
+  for (int i = 0; i < 20; i++) {
+    Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB);
+    NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB);
+    Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB);
+    NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB);
+    Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB);
+    NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB);
+    Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB);
+    NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB);
+
+    Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB);
+    NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB);
+    Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB);
+    NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB);
+    Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB);
+    NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB);
+    Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB);
+    NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB);
+    Acc = NextAcc;
+  }
+
+  auto II = LoopBB->begin();
+  for (int i = 0; i < 8; i++) {
+    PHINode *Phi = cast<PHINode>(&*II++);
+    Phi->addIncoming(Acc[i], LoopBB);
+    Phi->addIncoming(UndefValue::get(Ty), EntryBB);
+  }
+
+  BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F);
+  BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
+                     LoopBB);
+
+  Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
+  Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
+  Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB);
+  Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB);
+  Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
+  Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
+  Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
+
+  ReturnInst::Create(Context, nullptr, ExitBB);
+
+  ScalarEvolution SE = buildSE(*F);
+
+  EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm