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.<div>
<br></div><div>- Jan</div><div><br><br><div class="gmail_quote">On Wed, Aug 11, 2010 at 2:48 PM, David Greene <span dir="ltr"><<a href="mailto:dag@cray.com">dag@cray.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I just filed bug 7872 about non-scalability of the LSR analysis<br>
algorithms.  It may be related to bug 6727.<br>
<br>
The fundamental problem appears to be re-running SCEV analyses such as<br>
properlyDominates and SCEVComplexityCompare over and over again on large<br>
SCEV expressions.  Memoizing results for SCEVComplexityCompare appears<br>
to help significantly but that is much harder to do with things like<br>
properlyDominates.<br>
<br>
Is anyone actively looking at LSR compile time issues?  LLVM 2.7 is<br>
taking on the order of 30 minutes to optimize some very simple test<br>
cases and that's after doing the memoization work for<br>
SCEVComplexityCompare.  TOT has the same problem.<br>
<br>
                     -Dave<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div>