# SCEV implementation and limitations, do we need "pow"?

Hi,

I was looking at some bugs to play with, and I started with 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

Hi,

I was looking at some bugs to play with, and I started with 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 “(bc) * (bc)” to “bcb*c”. Thank, – Mehdi

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 “(bc) * (bc)” to "bcb*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.
-Andy

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

I have to get use to “reply-all”. OK so basically if there is an opportunity for a “pow” after flattening, revert back to the non flatten expression. I’ll have a look at that. Unfortunately I mixed two independent questions in my email, sorry for the confusion. I mentioned the issue with the exponential, and then I raised an independent question on the implementation, which is not symmetric when it comes to flattening the argument. The second part the begins with “While looking at SCEV, another thing is puzzling in the implementation…” describes it. So my 1), 2), and 3) does not address the exponential at all. Mehdi