[LLVMdev] creating SCEV taking too long

[Daniel Berlin]

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 :)