svn commit: r314708 - head/contrib/llvm/lib/Analysis
Dimitry Andric
dim at FreeBSD.org
Sun Mar 5 19:56:21 UTC 2017
Author: dim
Date: Sun Mar 5 19:56:20 2017
New Revision: 314708
URL: https://svnweb.freebsd.org/changeset/base/314708
Log:
For now, revert 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
This commit is the cause of excessive compile times on skein_block.c
(and possibly other files) during kernel builds on amd64.
We never saw the problematic behavior described in this upstream commit,
so for now it is better to revert it. An upstream bug has been filed
here: https://bugs.llvm.org/show_bug.cgi?id=32142
Reported by: mjg
Modified:
head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
==============================================================================
--- head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Sun Mar 5 18:37:25 2017 (r314707)
+++ head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Sun Mar 5 19:56:20 2017 (r314708)
@@ -127,11 +127,6 @@ static cl::opt<unsigned> MulOpsInlineThr
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
//===----------------------------------------------------------------------===//
@@ -480,8 +475,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 Depth) {
- if (Depth > MaxCompareDepth || EqCache.count({LV, RV}))
+ unsigned DepthLeft = 2) {
+ if (DepthLeft == 0 || EqCache.count({LV, RV}))
return 0;
// Order pointer values after integer values. This helps SCEVExpander form
@@ -542,23 +537,21 @@ CompareValueComplexity(SmallSet<std::pai
for (unsigned Idx : seq(0u, LNumOps)) {
int Result =
CompareValueComplexity(EqCache, LI, LInst->getOperand(Idx),
- RInst->getOperand(Idx), Depth + 1);
+ RInst->getOperand(Idx), DepthLeft - 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(
- SmallSet<std::pair<const SCEV *, const SCEV *>, 8> &EqCacheSCEV,
- const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS,
- unsigned Depth = 0) {
+static int CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS,
+ const SCEV *RHS) {
// Fast-path: SCEVs are uniqued so we can do a quick equality check.
if (LHS == RHS)
return 0;
@@ -568,8 +561,6 @@ static int CompareSCEVComplexity(
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.
@@ -579,11 +570,7 @@ static int CompareSCEVComplexity(
const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
SmallSet<std::pair<Value *, Value *>, 8> EqCache;
- int X = CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue(),
- Depth + 1);
- if (X == 0)
- EqCacheSCEV.insert({LHS, RHS});
- return X;
+ return CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue());
}
case scConstant: {
@@ -618,12 +605,11 @@ static int CompareSCEVComplexity(
// Lexicographically compare.
for (unsigned i = 0; i != LNumOps; ++i) {
- int X = CompareSCEVComplexity(EqCacheSCEV, LI, LA->getOperand(i),
- RA->getOperand(i), Depth + 1);
+ long X = CompareSCEVComplexity(LI, LA->getOperand(i), RA->getOperand(i));
if (X != 0)
return X;
}
- EqCacheSCEV.insert({LHS, RHS});
+
return 0;
}
@@ -642,13 +628,11 @@ static int CompareSCEVComplexity(
for (unsigned i = 0; i != LNumOps; ++i) {
if (i >= RNumOps)
return 1;
- int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(i),
- RC->getOperand(i), Depth + 1);
+ long X = CompareSCEVComplexity(LI, LC->getOperand(i), RC->getOperand(i));
if (X != 0)
return X;
}
- EqCacheSCEV.insert({LHS, RHS});
- return 0;
+ return (int)LNumOps - (int)RNumOps;
}
case scUDivExpr: {
@@ -656,15 +640,10 @@ static int CompareSCEVComplexity(
const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
// Lexicographically compare udiv expressions.
- int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getLHS(), RC->getLHS(),
- Depth + 1);
+ long X = CompareSCEVComplexity(LI, LC->getLHS(), RC->getLHS());
if (X != 0)
return X;
- X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getRHS(), RC->getRHS(),
- Depth + 1);
- if (X == 0)
- EqCacheSCEV.insert({LHS, RHS});
- return X;
+ return CompareSCEVComplexity(LI, LC->getRHS(), RC->getRHS());
}
case scTruncate:
@@ -674,11 +653,7 @@ static int CompareSCEVComplexity(
const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
// Compare cast expressions by operand.
- int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(),
- RC->getOperand(), Depth + 1);
- if (X == 0)
- EqCacheSCEV.insert({LHS, RHS});
- return X;
+ return CompareSCEVComplexity(LI, LC->getOperand(), RC->getOperand());
}
case scCouldNotCompute:
@@ -700,21 +675,19 @@ static int CompareSCEVComplexity(
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(EqCache, LI, RHS, LHS) < 0)
+ if (CompareSCEVComplexity(LI, RHS, LHS) < 0)
std::swap(LHS, RHS);
return;
}
// Do the rough sort by complexity.
std::stable_sort(Ops.begin(), Ops.end(),
- [&EqCache, LI](const SCEV *LHS, const SCEV *RHS) {
- return CompareSCEVComplexity(EqCache, LI, LHS, RHS) < 0;
+ [LI](const SCEV *LHS, const SCEV *RHS) {
+ return CompareSCEVComplexity(LI, LHS, RHS) < 0;
});
// Now that we are sorted by complexity, group elements of the same
More information about the svn-src-all
mailing list