[LLVMdev] SCEV implementation and limitations, do we need "pow"?

[Mehdi Amini]

Hi,

I was looking at some bugs to play with, and I started with 
http://llvm.org/bugs/show_bug.cgi?id=18606

As I commented there, a loop is unrolled and exhibit this pattern:

   %mul.1 = mul i32 %mul, %mul
   %mul.2 = mul i32 %mul.1, %mul.1
   ....

With an unroll factor of 32, the last multiply has 2^32 terms in its 
SCEV expression.
(I mean I expect it would have those terms if I was patient enough to 
wait for opt to finish :) )

So I suppose SCEV is lacking some protection, for instance degrading to 
"unknow" when an expression is above a given threshold, or stop 
flattening and keeping only a reference to another SCEV as a term of the 
expression.
Nick and Chandler also mentioned on IRC that SCEV should be extended 
with a "pow" operator to tackle such situation and being able to fold 
multiply-tree.


While looking at SCEV, another thing is puzzling in the implementation. 
Focusing on multiply (ScalarEvolution:3730), the SCEV is computed by 
taking the SCEV of the second operand and then checking if the first one 
is a multiply, if it is it "recurse" (iteratively) and repeat on this 
multiply.
Example :

    a = b * c;
    d = e * f;
    g = a * d;

when computing SCEV(g), (if I got it right)  it is actually computing:

SCEV(g) = getMulExpr(b , SCEV(c), SCEV(d))

There is a lack of symmetry for which I can't see the rational. I would 
expect one of these three possibilities:

1) Just using the SCEV of the operands: SCEV(g) = getMulExpr(SCEV(a), 
SCEV(d));

2) Being "smart" and flatten when operands are multiply, but symmetric : 
SCEV(g) = getMulExpr(SCEV(b), SCEV(c), SCEV(e), SCEV(f));

3) Being "smart" and flatten when the *SCEV of the operands* are 
multiply. So instead of tackling recursively the operand it could use 
the (hopefully already computed) SCEV.

Number 3 is my favorite, but it is already implemented in getMulExpr() 
(line 1963), so I propose to got with Number 1 :)


Thanks for your comments!

Mehdi

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140205/d6d21f16/attachment.html>