llvm dev - Feb 2014 - [LLVMdev] SCEV implementation and limitations, do we need "pow"?

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>

On Feb 5, 2014, at 12:54 AM, Mehdi Amini <mehdi.amini at silkan.com>
wrote:
> 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 :)
I haven’t fully processed your suggestions. Hopefully someone else will comment.
My initial thought is that we should never flatten an operand if its SCEV is
identical to a previous operand.
-Andy
> 
> 
> Thanks for your comments!
> 
> Mehdi
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140207/ae5170d3/attachment.html>

On 2/7/14, 10:24 AM, Andrew Trick wrote:
>
> On Feb 5, 2014, at 12:54 AM, Mehdi Amini <mehdi.amini at silkan.com 
> <mailto:mehdi.amini at silkan.com>> wrote:
>
>> 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 :)
>
> I haven’t fully processed your suggestions. Hopefully someone else 
> will comment. My initial thought is that we should never flatten an 
> operand if its SCEV is identical to a previous operand.
> -Andy
Do you mean that for this sequence:

a = b * c
d = b * c
e = a * d

you are expecting SCEV(e) to be "a * d" instead of "b * c * b *
c" ?

I ask because I used the term "flatten" earlier to describe the 
transformation of "(b*c) * (b*c)"  to  "b*c*b*c".

Thank,

-- 
Mehdi

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