[llvm-dev] Scaling to many basic blocks

[Philip Reames via llvm-dev]

On 08/22/2015 04:51 PM, David Jones via llvm-dev wrote:
> A somewhat more general question:
>
> What characteristics of generated IR contribute to poor 
> optimization/code generation times?
I don't believe we have any documentation on this topic at this point.  
The performance tips for frontend authors page has some information 
(http://llvm.org/docs/Frontend/PerformanceTips.html), but not much.

In general, the farther something is from reasonable C/C++ code 
(including machine generated code from various common frameworks) the 
less likely all the issues are to have been worked out.

If you wanted to start some documentation, that would be a very 
constructive way to gather information that will help you and others.
>
> I recently found a pathological case in my own code of data tables 
> that caused poor performance in the IR verifier.
This was a performance bug.  They exist.  Please file them so they can 
get fixed.

In particular, you may find various passes which need cutoffs added (due 
to the super-linear scaling inherent in them).  Feel free to file bugs - 
preferably with test cases! - for these.  Patches are even better of 
course.  :)
>
> In general, I am not happy with the performance of LLVM on my code, so 
> I know I need to do better. But how? I have a few ideas, but trying 
> any of them could be time-consuming, with no guaranteed return at the 
> end of it.
Honestly, you're the only person who can do these experiments.  You can 
try talking to others in the community, but if you're not willing to run 
experiments, your results will be poor.  Having data to share greatly 
increases the likelihood someone else will be interested enough to help.

Can you share your current numbers?  i.e. Why are you "not happy"?
>
> Currently, I don't emit TBAA metadata. I have a hunch that doing so 
> might speed up compilation, as alias analyses can be reduced in size, 
> but I don't know that for sure, or how much of a benefit it would be. 
> Yes, I need to do this in any case, but if my users complain of long 
> compile times, I'd like to know what to work on first.
I really doubt failing to emit TBAA metadata will help.  In particular, 
my general experience has been that improving compile time happens 
mostly by making the optimizer more effective (so that other passes see 
less code), not by crippling it.
>
> On Sat, Aug 22, 2015 at 6:57 PM, Michael Zolotukhin via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>     Hi,
>
>     Several passes would have troubles with such code (namely, GVN and
>     JumpThreading). Recently we exposed similar issues when new more
>     aggressive unrolling heuristic was implemented - we unrolled big
>     loops expecting that the linear code would be then optimized, and
>     it indeed was optimized, but compile time regressed significantly.
>     But probably some of these issues have been fixed already - I
>     didn’t check.
>
>     Thanks,
>     Michael
>     > On Aug 22, 2015, at 3:03 PM, Russell Wallace via llvm-dev <llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>> wrote:
>     >
>     > How well does LLVM scale to many basic blocks? Let's say you
>     have a single function consisting of a million basic blocks each
>     with a few tens of instructions (and assuming the whole thing
>     isn't trivially repetitive so the number of simultaneously live
>     variables and whatever is large) and you feed that through the
>     optimisers into the backend code generator, will this work okay,
>     or will it take a very long time, or will it run into a scenario
>     of 'look, all compilers are designed on the assumption that nobody
>     is going to write a million lines of code in a single function'?
>     (Not that I'm planning to do so by hand either, I'm just thinking
>     about certain scenarios in automatic code generation.)
>     > _______________________________________________
>     > LLVM Developers mailing list
>     > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     >
>     https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=BQIGaQ&c=eEvniauFctOgLOKGJOplqw&r=ygVmcuuQ1MUhRUoJm-IgPtgjmvM0byfjlHDg99vufEI&m=z0N7FJAyaeJqJqE_W9ltYzHHpYI5tfa3q7x8UoMNaLA&s=mVoa5Fp3pKx6PIZ3F96zYIKlJmBSyzqARoAtuu0ws5A&e=
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150823/fa6d5384/attachment.html>