[llvm-dev] [SCEV] getMulExpr could be extremely slow when creating SCEVs for a long chain of add/mul instructions

[Mehdi Amini via llvm-dev]

> On Aug 3, 2016, at 11:46 AM, Huang, Li1 via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Hi,
>  
> I’m working on a slow-compile problem caused by SCEV (PR28830), and I need your suggestions on how to fix it. The loop below causes ScalarEvolution::getMulExpr to hang.

I believe this is a dup of https://llvm.org/bugs/show_bug.cgi?id=18606

See also this patch: https://reviews.llvm.org/D3127

— 
Mehdi


>  
> int get(unsigned n)
> {
>     unsigned i, j, mult = 1;
>     for (i = 0; i < 1; i++) {
>         for (j = 0; j < 30; j++) {
>             mult *= n++;
>         }
>     }
>     return mult;
> }
>  
> the inner loop is completed unrolled (by 30) to a long chain of “add” and “mult” instructions, then indvars follows loop-unroll and triggers SCEV creations for this long instruction chain. When it comes to getMulExpr, it tries to fold multiplications of AddRecs of the same induction variable recursively, this could be very slow if the expression tree is deep.
>  
> Code responsible for this problem starts here (in ScalarEvolution.cpp):
>  
>    // Okay, if there weren't any loop invariants to be folded, check to see if
>     // there are multiple AddRec's with the same loop induction variable being
>     // multiplied together.  If so, we can fold them.
>  
>     // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>
>     // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
>     //       choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
>     //   ]]],+,...up to x=2n}.
>     // Note that the arguments to choose() are always integers with values
>     // known at compile time, never SCEV objects.
>     //
>     // The implementation avoids pointless extra computations when the two
>     // addrec's are of different length (mathematically, it's equivalent to
>     // an infinite stream of zeros on the right).
>     bool OpsModified = false;
>     for (unsigned OtherIdx = Idx+1;
>          OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
> ...
> ...
>  
> One way I thought about to fix this is to have a threshold for the number of terms in each AddRec when folding them. For example, we only fold AddRec1 * AddRec2 when  (#terms in AddRec1 + #terms in AddRec2) < threshold. I tried setting the threshold to 8, and it stops early for this case. Another way is to limit the depth of this folding, but this might require change of API.
> _______________________________________________
> 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 <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/20160803/04bfe259/attachment.html>