<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">Going back to llvm-dev because it’s a good clarification...<div><br><div><div>On Feb 8, 2014, at 12:36 AM, Mehdi Amini <<a href="mailto:mehdi.amini@silkan.com">mehdi.amini@silkan.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
<div bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 2/7/14, 9:59 PM, Andrew Trick wrote:<br>
</div>
<blockquote cite="mid:986B5EB6-3638-47B1-A0D0-1921FBCAD6DB@apple.com" type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<br>
<div>
<div>On Feb 7, 2014, at 9:51 PM, Mehdi Amini <<a moz-do-not-send="true" href="mailto:mehdi.amini@silkan.com">mehdi.amini@silkan.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
<div bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 2/7/14, 10:24 AM, Andrew
Trick wrote:<br>
</div>
<blockquote cite="mid:8A533BD9-BB0C-41A8-B11D-3C350A85DFC4@apple.com" type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<br>
<div>
<div>On Feb 5, 2014, at 12:54 AM, Mehdi Amini <<a moz-do-not-send="true" href="mailto:mehdi.amini@silkan.com">mehdi.amini@silkan.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<meta http-equiv="content-type" content="text/html;
charset=windows-1252">
<div bgcolor="#FFFFFF" text="#000000"> Hi,<br>
<br>
I was looking at some bugs to play with, and I
started with <a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://llvm.org/bugs/show_bug.cgi?id=18606">http://llvm.org/bugs/show_bug.cgi?id=18606</a><br>
<br>
As I commented there, a loop is unrolled and exhibit
this pattern:<br>
<br>
%mul.1 = mul i32 %mul, %mul<br>
%mul.2 = mul i32 %mul.1, %mul.1<br>
<meta charset="utf-8">
....<br>
<br>
With an unroll factor of 32, the last multiply has
2^32 terms in its SCEV expression. <br>
(I mean I expect it would have those terms if I was
patient enough to wait for opt to finish :) )<br>
<br>
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.<br>
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.<br>
<br>
<br>
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.<br>
Example :<br>
<br>
a = b * c;<br>
d = e * f;<br>
g = a * d;<br>
<br>
when computing SCEV(g), (if I got it right) it is
actually computing:<br>
<br>
SCEV(g) = getMulExpr(b , SCEV(c), SCEV(d))<br>
<br>
There is a lack of symmetry for which I can't see
the rational. I would expect one of these three
possibilities:<br>
<br>
1) Just using the SCEV of the operands: SCEV(g) =
getMulExpr(SCEV(a), SCEV(d));<br>
<br>
2) Being "smart" and flatten when operands are
multiply, but symmetric : SCEV(g) =
getMulExpr(SCEV(b), SCEV(c), SCEV(e), SCEV(f));<br>
<br>
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.<br>
<br>
Number 3 is my favorite, but it is already
implemented in getMulExpr() (line 1963), so I
propose to got with Number 1 :)<br>
</div>
</blockquote>
<div><br>
</div>
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.</div>
<div>-Andy</div>
</blockquote>
<br>
Do you mean that for this sequence:<br>
<br>
a = b * c<br>
d = b * c<br>
e = a * d<br>
<br>
you are expecting SCEV(e) to be "a * d" instead of "b * c *
b * c" ?<br>
<br>
I ask because I used the term "flatten" earlier to describe
the transformation of "(b*c) * (b*c)" to "b*c*b*c”.<br>
</div>
</blockquote>
<div><br>
</div>
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.</div>
</blockquote>
<br>
I'm not convinced right now by the identical operands criteria, what
about a pattern like:<br>
<br>
int a1 = zz1 * 3;<br>
zz *= a1;<br>
int a2 = zz * 3;<br>
zz *= a2;<br>
int a3 = zz * 3;<br>
zz *= a3;<br>
int a4 = zz * 3;<br>
zz *= a4;<br>
....<br>
<br>
The operands are not the same, ie: SCEV(zz1) = (zz0) * (zz0 *3)<br></div></blockquote><br></div><div>A better way to state it: you would avoid flattening if it would immediately lead to duplicate terms.</div><div><br></div><div>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.</div><div><br></div><div>-Andy</div><br></div></body></html>