svn commit: r314795 - head/contrib/llvm/lib/Analysis
Dimitry Andric
dim at FreeBSD.org
Mon Mar 6 21:14:22 UTC 2017
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
More information about the svn-src-head
mailing list