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

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.

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} * {B1,+,B2,+,…,+,Bn}

// = {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(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.

Correct me if I’m wrong, is the code trying to expand geometric series into polynomial expression? (that doesn’t sound like a very good thing to do, it would spend so much time computing coefficients)

Wouldn’t this be better to transform as below:

mult *= n++ // 30 times

; into

mult = mult (n)…(n+29)

= mult 1…(n+29)/((1)…(n-1))
= mult * geo_sum(n+29) / geo_sum(n-1) ; is this more expensive than leaving as geo series?

Regards,

Kevin

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

Hi,

I generally don't like cutoffs / "max depths", but I can't think of a
better solution here (other than perhaps not doing this simplification
at all, but that will affect things that depend on this
simplification). I'd be okay with adding a "SimplificationDepth" type
cl::opt to SCEV that controls the point where we bail out of
simplifying further.

-- Sanjoy

Hi Kevin,

Sorry,

I mistook product for sum.

Hi Mehdi,

Thank you for finding this dup, I did some search but wasn’t able to locate a dup.

-Li Huang

Hi Sanjoy,

Thank you for your suggestion. Looks like someone is already working on a solution in this direction, as Mehdi pointed out: https://reviews.llvm.org/D3127. But this patch is old and was not reviewed until recently.

- Li Huang