[LLVMdev] LSR is Unbearably Slow

Jan Voung jvoung at google.com
Wed Aug 11 15:05:17 PDT 2010


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


On Wed, Aug 11, 2010 at 2:48 PM, David Greene <dag at cray.com> wrote:

> 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
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100811/176fe664/attachment.html>


More information about the llvm-dev mailing list