Skip site navigation (1)Skip section navigation (2)
Date:      Mon, 6 Mar 2017 21:14:20 +0000 (UTC)
From:      Dimitry Andric <dim@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r314795 - head/contrib/llvm/lib/Analysis
Message-ID:  <201703062114.v26LEKtM064479@repo.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: dim
Date: Mon Mar  6 21:14:20 2017
New Revision: 314795
URL: https://svnweb.freebsd.org/changeset/base/314795

Log:
  Reapply r287232 from upstream llvm trunk (by Daniil Fukalov):
  
    [SCEV] limit recursion depth of CompareSCEVComplexity
  
    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.
  
    Reviewers: sanjoy
  
    Subscribers: mzolotukhin, tstellarAMD, llvm-commits
  
    Differential Revision: https://reviews.llvm.org/D26389
  
  Pull in r296992 from upstream llvm trunk (by Sanjoy Das):
  
    [SCEV] Decrease the recursion threshold for CompareValueComplexity
  
    Fixes PR32142.
  
    r287232 accidentally increased the recursion threshold for
    CompareValueComplexity from 2 to 32.  This change reverses that
    change by introducing a separate flag for CompareValueComplexity's
    threshold.
  
  The latter revision fixes the excessive compile times for skein_block.c.

Modified:
  head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp

Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
==============================================================================
--- head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp	Mon Mar  6 21:06:55 2017	(r314794)
+++ head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp	Mon Mar  6 21:14:20 2017	(r314795)
@@ -127,6 +127,16 @@ static cl::opt<unsigned> MulOpsInlineThr
     cl::desc("Threshold for inlining multiplication operands into a SCEV"),
     cl::init(1000));
 
+static cl::opt<unsigned> MaxSCEVCompareDepth(
+    "scalar-evolution-max-scev-compare-depth", cl::Hidden,
+    cl::desc("Maximum depth of recursive SCEV complexity comparisons"),
+    cl::init(32));
+
+static cl::opt<unsigned> MaxValueCompareDepth(
+    "scalar-evolution-max-value-compare-depth", cl::Hidden,
+    cl::desc("Maximum depth of recursive value complexity comparisons"),
+    cl::init(2));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
@@ -475,8 +485,8 @@ bool SCEVUnknown::isOffsetOf(Type *&CTy,
 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 > MaxValueCompareDepth || EqCache.count({LV, RV}))
     return 0;
 
   // Order pointer values after integer values. This helps SCEVExpander form
@@ -537,21 +547,23 @@ CompareValueComplexity(SmallSet<std::pai
     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;
@@ -561,6 +573,8 @@ static int CompareSCEVComplexity(const L
   if (LType != RType)
     return (int)LType - (int)RType;
 
+  if (Depth > MaxSCEVCompareDepth || 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.
@@ -570,7 +584,11 @@ static int CompareSCEVComplexity(const L
     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: {
@@ -605,11 +623,12 @@ static int CompareSCEVComplexity(const L
 
     // 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;
   }
 
@@ -628,11 +647,13 @@ static int CompareSCEVComplexity(const L
     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: {
@@ -640,10 +661,15 @@ static int CompareSCEVComplexity(const L
     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:
@@ -653,7 +679,11 @@ static int CompareSCEVComplexity(const L
     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:
@@ -675,19 +705,21 @@ static int CompareSCEVComplexity(const L
 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



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201703062114.v26LEKtM064479>