[LLVMdev] LSR is Unbearably Slow

[David Greene]

I just filed bug 7872 about non-scalability of the LSR analysis
algorithms. It may be related to bug 6727.

The fundamental problem appears to be re-running SCEV analyses such as
properlyDominates and SCEVComplexityCompare over and over again on large
SCEV expressions. Memoizing results for SCEVComplexityCompare appears
to help significantly but that is much harder to do with things like
properlyDominates.

Is anyone actively looking at LSR compile time issues? LLVM 2.7 is
taking on the order of 30 minutes to optimize some very simple test
cases and that's after doing the memoization work for
SCEVComplexityCompare. TOT has the same problem.

-Dave
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Jan Voung]

I also noticed LSR spending a lot of time in GenerateAllReuseFormulae, just to have some cases pruned in NarrowSearchSpaceUsingHeuristics. I'm not familiar enough with the code to comment on how this affects the quality of LSR results, but a hack is to "EstimateSearchSpaceComplexity" inside the loops of GenerateAllReuseFormulae and cut out early.

- Jan

[David Greene]

On Wednesday 11 August 2010 17:05:17 Jan Voung wrote:
> I also noticed LSR spending a lot of time in GenerateAllReuseFormulae, just
> to have some cases pruned in NarrowSearchSpaceUsingHeuristics. I'm not
> familiar enough with the code to comment on how this affects the quality of
> LSR results, but a hack is to "EstimateSearchSpaceComplexity" inside the
> loops of GenerateAllReuseFormulae and cut out early.

I assume you mean NarrowSearchSpaceUsingHeuristics inside the loops.

I tried this and it helped a bit but nowhere near enough to overcome
the algorithmic complexity. Looks like we need another solution.

[copied this to the bug to keep track of it]