<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;"><br><div><div>On Feb 5, 2014, at 12:54 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 http-equiv="content-type" content="text/html; charset=ISO-8859-1">
  
  <div 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></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><div><br><blockquote type="cite"><div bgcolor="#FFFFFF" text="#000000">
    <br>
    <br>
    Thanks for your comments!<br>
    <br>
    Mehdi<br>
    <br>
  </div>

_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></body></html>