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>
Andrew Trick
2014-Feb-08 05:59 UTC
[LLVMdev] SCEV implementation and limitations, do we need "pow"?
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. -Andy> > Thank, > > -- > Mehdi >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140207/970818bc/attachment.html>
Andrew Trick
2014-Feb-08 09:05 UTC
[LLVMdev] SCEV implementation and limitations, do we need "pow"?
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>
Mehdi Amini
2014-Feb-08 21:34 UTC
[LLVMdev] SCEV implementation and limitations, do we need "pow"?
On 2/8/14, 1:05 AM, Andrew Trick wrote:> Going back to llvm-dev because it’s a good clarification...I have to get use to "reply-all".> > On Feb 8, 2014, at 12:36 AM, Mehdi Amini <mehdi.amini at silkan.com > <mailto: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 >>> <mailto: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 >>>>> <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”. >>> >>> 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.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.> 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.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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140208/2cf3529f/attachment.html>