[LLVMdev] creating SCEV taking too long

[Andrew Trick]

On Jul 30, 2013, at 6:46 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

> On Tue, Jul 30, 2013 at 2:20 PM, Andrew Trick <atrick at apple.com> wrote:
>> 
>> On Jul 29, 2013, at 4:08 PM, Guo, Xiaoyi <Xiaoyi.Guo at amd.com> wrote:
>> 
>> Hi,
>> 
>> We have a benchmark where there are 128 MAD computations in a loop. (See the
>> attached IR.) Creating SCEVs for these expressions takes a long time, making
>> the compile time too long. E.g., running opt with the “indvars” pass only
>> takes 45 seconds.
>> 
>> It seems that the majority of the time is spent in comparing the complexity
>> of the expression operands to sort them.
>> 
>> I realize that the expression grows to be really large towards the end of
>> the loop.
>> 
>> I don’t know of all the uses of the built SCEV. But I image it won’t be very
>> useful for such complex expressions. Yet, it’s making the compile time much
>> longer.
>> 
>> So I’m wondering if it would make sense to abort the creation of SCEV when
>> the expression gets really complex and large. Or is there any way to further
>> optimize the performance of SCEV building for such cases.
>> 
>> Thanks in advance for any response.
>> 
>> 
>> Nice test case. I tried printing the SCEV… oops. I haven’t seen a case this
>> bad, but I know you’re not the first to run into this problem.
>> 
>> There are two steps in GroupByComplexity, sorting (std::sort) and grouping
>> (N^2).
>> 
>> The sort calls SCEVComplexityCompare::compare() which can make multiple
>> recursive calls for nodes with multiple operands. This looks like it could
>> be a disaster for expressions that are not strictly trees--exponential in
>> the size of the DAG.
>> 
> Yes, this is why i suggested computing some deterministic "complexity
> hash" on the way, and caching it in the SCEV.
> It would not help if they were all the same, but if they were
> different only at the end, you wouldn't end up comparing every operand
> to get there.
> If they are all the same, you are right that cut-off is the only
> reasonable answer.
> Or calculate "complexity" in a way that does not require operand by
> operand comparison (IE compute a "complexity" number instead of a
> hash, as you build the SCEV).  It's just trying to get a canonical
> sort here.
> This would at least make the sort fast, grouping can't be made linear
> unless you are willing to trust the hash :)

That would be ideal. I wish it were obvious to me how to implement it.

Xiaoyi’s simple fix handled this scenario and was totally consistent with the current implementation. It seems we’re not yet running into the issue of visiting all paths in a DAG. I don’t want to discourage a more general fix/redesign though. We could probably recover more compile time in many cases.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130730/4f0d638d/attachment.html>