<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 2/8/14, 1:05 AM, Andrew Trick wrote:<br>
</div>
<blockquote
cite="mid:EA2CD528-1039-4079-86A1-671FE5FD140E@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
Going back to llvm-dev because it’s a good clarification...</blockquote>
I have to get use to "reply-all".<br>
<br>
<blockquote
cite="mid:EA2CD528-1039-4079-86A1-671FE5FD140E@apple.com"
type="cite">
<div><br>
<div>
<div>On Feb 8, 2014, at 12:36 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 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>
</blockquote>
<br>
OK so basically if there is an opportunity for a "pow" after
flattening, revert back to the non flatten expression.<br>
I'll have a look at that.<br>
<blockquote
cite="mid:EA2CD528-1039-4079-86A1-671FE5FD140E@apple.com"
type="cite">
<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>
</blockquote>
<br>
Unfortunately I mixed two independent questions in my email, sorry
for the confusion.<br>
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.<br>
So my 1), 2), and 3) does not address the exponential at all. <br>
<br>
<br>
Mehdi<br>
<br>
</body>
</html>