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

[Andrew Trick]

Going back to llvm-dev because it’s a good clarification...

On Feb 8, 2014, at 12:36 AM, Mehdi Amini <mehdi.amini at silkan.com> wrote:

> On 2/7/14, 9:59 PM, Andrew Trick wrote:
>> 
>> On Feb 7, 2014, at 9:51 PM, Mehdi Amini <mehdi.amini at silkan.com> wrote:
>> 
>>> 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> 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”.
>> 
>> Yes, that's what I meant. The moment you flatten the same expression on multiple operands it’s exponential, unless we implement pow. I’m not sure if that fits what you suggested above.
> 
> I'm not convinced right now by the identical operands criteria, what about a pattern like:
> 
>     int a1 = zz1 * 3;
>     zz *= a1;
>     int a2 = zz * 3;
>     zz *= a2;
>     int a3 = zz * 3;
>     zz *= a3;
>     int a4 = zz * 3;
>     zz *= a4;
>     ....
> 
> The operands are not the same, ie: SCEV(zz1) = (zz0) * (zz0 *3)

A better way to state it: you would avoid flattening if it would immediately lead to duplicate terms.

Your suggestions may be better. I’m just not sure I fully understand. If #3 is implemented why are you doing something else? I would be nervous about disabling flattening without knowing if any expression evaluation is benefiting from it.

-Andy

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