<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi,<br>
<br>
I was looking at some bugs to play with, and I started with
<a 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>
<br>
<br>
Thanks for your comments!<br>
<br>
Mehdi<br>
<br>
</body>
</html>