[LLVMdev] SROA is slow when compiling a large basic block

[Akira Hatanaka]

On Wed, May 14, 2014 at 8:15 PM, Chandler Carruth <chandlerc at google.com>wrote:

>
> On Wed, May 14, 2014 at 7:02 PM, Akira Hatanaka <ahatanak at gmail.com>wrote:
>
>> If I understand this code correctly. LoadAndStorePromoter::run is called
>> once per every promotable alloca and iterates over the whole list to
>> determine the order of loads and stores in the basic block that access the
>> alloca.
>>
>
> Yes, this is a long standing problem of SROA.
>
>
>>
>> This is the list of ideas I have considered or implemented that can
>> possibly solve my problem:
>>
>>
>> 1. In SROA::getAnalysisUsage, always require DominatorTreeWrapperPass.
>> This will enable SROA::promoteAllocas to use mem2reg, which is fast because
>> it caches the per basic-block ordering of the relevant loads and stores. If
>> it's important to avoid always computing the dominator tree, computing it
>> conditionally based on whether there is a huge basic block in the function
>> is another idea, but I am not sure if that is possible (I don't think this
>> is currently supported).
>>
>>
>> This brings down the compilation time (using clang -emit-llvm) from 350s
>> to 30s (it still takes about 23s to do GVN). It also might fix PR17855 (the
>> program that used to take 65s to compile now takes just 11s):
>>
>>
>> http://llvm.org/bugs/show_bug.cgi?id=17855
>>
>
> This is my plan, but before doing it there are a bunch of *huge*
> performance improvements we can make in the more common case so that
> mem2reg isn't actually slower. Also, we need to be able to preserve
> analyses further which the new pass manager will allow.
>
> Is this a pressing matter for you?
>

It's not really pressing, but there are users complaining about the long
compilation time, so I would like to see this fixed soon, if that is
possible.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140515/5a3e4ca9/attachment.html>