[LLVMbugs] [Bug 7872] New: LSR Does Not Finish
bugzilla-daemon at llvm.org
bugzilla-daemon at llvm.org
Wed Aug 11 14:42:31 PDT 2010
http://llvm.org/bugs/show_bug.cgi?id=7872
Summary: LSR Does Not Finish
Product: libraries
Version: trunk
Platform: PC
OS/Version: Linux
Status: NEW
Severity: normal
Priority: P
Component: Loop Optimizer
AssignedTo: unassignedbugs at nondot.org
ReportedBy: greened at obbligato.org
CC: llvmbugs at cs.uiuc.edu
Created an attachment (id=5362)
--> (http://llvm.org/bugs/attachment.cgi?id=5362)
bugpoint-reduced testcase
Attached is a bugpoint-reduced version of a testcase that's been running in LSR
for over 11 minutes. It appears to be a problem with LSR re-analyzing SCEVs
over and over again. It does not appear to be an infinite loop, just a very
expensive analysis that doesn't scale.
The backtrace at an arbitrary point in time compiling the original (large)
testcase looks like this:
(gdb) where
#0 (anonymous namespace)::SCEVComplexityCompare::operator()
(this=0x7fff7a564200, LHS=0x1174bb0, RHS=0x1593870) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:609
#1 0x0000000000b2ad94 in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x1174c80, RHS=0x1593940) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:613
#2 0x0000000000b2ad94 in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x1174ce0, RHS=0x15939a0) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:613
#3 0x0000000000b2adbb in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x1594010, RHS=0x1175680) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:615
#4 0x0000000000b2ad94 in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x1594070, RHS=0x11756e0) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:613
#5 0x0000000000b2ad94 in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x15b8220, RHS=0x15ad490) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:613
#6 0x0000000000b2ad94 in (anonymous
namespace)::SCEVComplexityCompare::operator() (this=0x7fff7a564200,
LHS=0x1a0e4b0, RHS=0x1a0e580) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:613
#7 0x0000000000b2b509 in std::merge<llvm::SCEV const**, llvm::SCEV const**,
llvm::SCEV const**, (anonymous namespace)::SCEVComplexityCompare>
(__first1=0x1400d28, __last1=0x1400d40, __first2=0x13df590, __last2=0x13df5e0,
__result=0x13df578, __comp=...) at /usr/include/c++/4.1.2/bits/stl_algo.h:3198
#8 0x0000000000b2b8b1 in std::__merge_adaptive<llvm::SCEV const**, long,
llvm::SCEV const**, (anonymous namespace)::SCEVComplexityCompare>
(__first=0x13df540, __middle=0x13df590, __last=0x13df5e0, __len1=10, __len2=10,
__buffer=0x1400cf0, __buffer_size=20, __comp=...) at
/usr/include/c++/4.1.2/bits/stl_algo.h:3535
#9 0x0000000000b2bbcf in std::__stable_sort_adaptive<llvm::SCEV const**,
llvm::SCEV const**, long, (anonymous namespace)::SCEVComplexityCompare>
(__first=0x13df540, __last=0x13df5e0, __buffer=0x1400cf0, __buffer_size=20,
__comp=...) at /usr/include/c++/4.1.2/bits/stl_algo.h:3735
#10 0x0000000000b2be5f in std::stable_sort<llvm::SCEV const**, (anonymous
namespace)::SCEVComplexityCompare> (__first=0x13df540, __last=0x13df5e0,
__comp=...) at /usr/include/c++/4.1.2/bits/stl_algo.h:3821
#11 0x0000000000b0aa67 in GroupByComplexity (Ops=..., LI=0x14eeb60) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:671
#12 0x0000000000b0b328 in llvm::ScalarEvolution::getAddExpr (this=0x14f7470,
Ops=..., HasNUW=false, HasNSW=false) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/ScalarEvolution.cpp:1347
#13 0x0000000000962e80 in (anonymous
namespace)::LSRInstance::GenerateReassociations (this=0x7fff7a565480, LU=...,
LUIdx=0, Base=..., Depth=2) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:2313
#14 0x0000000000962f4f in (anonymous
namespace)::LSRInstance::GenerateReassociations (this=0x7fff7a565480, LU=...,
LUIdx=0, Base=..., Depth=1) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:2322
#15 0x0000000000962f4f in (anonymous
namespace)::LSRInstance::GenerateReassociations (this=0x7fff7a565480, LU=...,
LUIdx=0, Base=..., Depth=0) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:2322
#16 0x0000000000963fc8 in (anonymous
namespace)::LSRInstance::GenerateAllReuseFormulae (this=0x7fff7a565480) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:2778
#17 0x000000000096a365 in LSRInstance (this=0x7fff7a565480, tli=0x0,
l=0x1309840, P=0x14ed0e0) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:3634
#18 0x000000000096a5da in (anonymous namespace)::LoopStrengthReduce::runOnLoop
(this=0x14ed0e0, L=0x1309840) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp:3777
#19 0x0000000000abe9b0 in llvm::LPPassManager::runOnFunction (this=0x14f7ed0,
F=...) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/Analysis/LoopPass.cpp:269
#20 0x0000000000c59c8a in llvm::FPPassManager::runOnFunction (this=0x110b020,
F=...) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/VMCore/PassManager.cpp:1450
#21 0x0000000000c59e5f in llvm::FPPassManager::runOnModule (this=0x110b020,
M=...) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/VMCore/PassManager.cpp:1470
#22 0x0000000000c5994b in llvm::MPPassManager::runOnModule (this=0x110adc0,
M=...) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/VMCore/PassManager.cpp:1524
#23 0x0000000000c5b0d1 in llvm::PassManagerImpl::run (this=0x110cb90, M=...) at
/ptmp/dag/llvm-project.official/llvm/trunk/lib/VMCore/PassManager.cpp:1605
#24 0x0000000000c5b133 in llvm::PassManager::run (this=0x7fff7a56adc0, M=...)
at /ptmp/dag/llvm-project.official/llvm/trunk/lib/VMCore/PassManager.cpp:1649
#25 0x000000000089e608 in main (argc=12, argv=0x7fff7a56afc8) at
/ptmp/dag/llvm-project.official/llvm/trunk/tools/opt/opt.cpp:553
One of the SCEVs being compared look like this:
(-1 * (sext i32 %r1313 to i64) * (6 + (2 * (((sext i32 ((-1 * (%r1331 +
%r1319)) + %r1328 + %r1316) to i64) * (sext i32 %r1322 to i64)) +
((sext i32 (((1 + %r1322) * ((-1 * %r1331) + %r1328)) + (((-1 * %r1328) +
%r1331) * %r1325)) to i64) * (sext i32 %r1316 to i64)) + ((sext
i32 (((1 + %r1322) * ((-1 * %r1328) + %r1331)) + (((-1 * %r1331) + %r1328) *
%r1325)) to i64) * (sext i32 %r1319 to i64)) + ((sext i32 %r1
325 to i64) * (-1 + ((sext i32 %r1316 to i64) * ((sext i32 %r1331 to i64) + (-1
* (sext i32 %r1328 to i64)))) + ((sext i32 %r1319 to i64)
* ((sext i32 %r1328 to i64) + (-1 * (sext i32 %r1331 to i64)))))))) + (-2 *
((sext i32 %r1319 to i64) + ((sext i32 (%r1328 + %r1316) to i6
4) * (sext i32 %r1325 to i64)))) + (-1 * (((sext i32 (((1 + %r1322) * %r1331) +
(%r1328 * %r1325)) to i64) * (sext i32 %r1316 to i64)) + (
(sext i32 (((2 + %r1322) * %r1328) + (%r1331 * %r1325)) to i64) * (sext i32
%r1319 to i64)) + ((sext i32 (%r1331 + %r1319) to i64) * (1 +
(sext i32 (2 * %r1322) to i64))) + ((sext i32 %r1331 to i64) * (2 + (sext i32
%r1316 to i64))))) + ((sext i32 %r1322 to i64) * (6 + (sext
i32 %r1328 to i64) + (2 * (sext i32 %r1319 to i64) * ((sext i32 %r1331 to i64)
+ (-1 * (sext i32 %r1328 to i64)))) + ((sext i32 %r1316 to
i64) * (2 + (sext i32 (2 * ((-1 * %r1331) + %r1328)) to i64))))) + ((sext i32
%r1316 to i64) * (6 + (2 * ((sext i32 %r1322 to i64) + (-1 *
(sext i32 %r1325 to i64)))))) + ((sext i32 %r1328 to i64) * (6 + (-1 * (sext
i32 (2 * %r1325) to i64)) + ((sext i32 %r1322 to i64) * (3 +
(sext i32 %r1316 to i64))) + ((sext i32 %r1316 to i64) * (4 + (sext i32 %r1322
to i64) + (-1 * (sext i32 %r1325 to i64)))) + ((sext i32 %
r1319 to i64) * ((sext i32 (2 * %r1325) to i64) + (-1 * (sext i32 (2 + %r1322)
to i64)))))) + ((sext i32 %r1325 to i64) * (-4 + (sext i32
((3 * (%r1331 + %r1319)) + (-2 * (%r1328 + %r1316))) to i64))) + ((sext i32
%r1319 to i64) * (-3 + (sext i32 (3 * %r1325) to i64) + (-1 *
(sext i32 (2 * %r1322) to i64)))) + ((sext i32 %r1331 to i64) * (-3 + (sext i32
(3 * %r1325) to i64) + (-1 * (sext i32 (2 * %r1322) to i64
)) + ((sext i32 %r1319 to i64) * (4 + (2 * (sext i32 %r1322 to i64)) + (-1 *
(sext i32 %r1325 to i64)))) + ((sext i32 %r1316 to i64) * ((s
ext i32 (2 * %r1325) to i64) + (-1 * (sext i32 (2 + %r1322) to i64))))))))
The other looks similar. So there are some very complex SCEVs that are
expensive to analyze due to the recursive nature of the analysis
(SCEVComplexityCompare in this case).
LSRInstance::GenerateAllReuseFormulae is very expensive as it re-analyzes SCEVs
over and over. I hacked in a cache to remember results of
SCEVComplexityCompare and that seems to disappear from the profile. But
SCEV::properlyDominates takes its place and there doesn't seem to be an easy
way to cache those results. I'm sure there are other SCEV analyses that have
the same problem when used by LSR.
I believe we need a more general solution than simply memoizing all of these
analyses.
The attached reduced testcase of 136 instructions takes 5 seconds to optimize
with a Debug+Asserts LLVM.
--
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.
More information about the llvm-bugs
mailing list