Mehdi Amini
2014-Feb-05 08:54 UTC
[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>
Andrew Trick
2014-Feb-07 18:24 UTC
[LLVMdev] SCEV implementation and limitations, do we need "pow"?
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>
Mehdi Amini
2014-Feb-08 05:51 UTC
[LLVMdev] SCEV implementation and limitations, do we need "pow"?
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. > -AndyDo 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>
Maybe Matching Threads
- [LLVMdev] SCEV implementation and limitations, do we need "pow"?
- [SCEV] getMulExpr could be extremely slow when creating SCEVs for a long chain of add/mul instructions
- [LLVMdev] SCEV getMulExpr() not propagating Wrap flags
- [LLVMdev] SCEV getMulExpr() not propagating Wrap flags
- [LLVMdev] SCEV bottom value