[LLVMdev] creating SCEV taking too long

[Andrew Trick]

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.

If you just have a very large tree with many similar looking subexpressions, then I’m not sure what to do except cut it into reasonable subtrees. 

AFAICT, it’s not just sorting that’s a problem but also grouping? Also, I think the shear depth of the createSCEV recursion is itself a problem.
I don’t see any reason not to limit the size of SCEV expressions, but I also don’t have a brilliant idea for how to do it at the moment (other than the obvious depth cutoff).

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