<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 7, 2014, at 9:51 PM, 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, 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><div>-Andy</div><div><br><blockquote type="cite"><div bgcolor="#FFFFFF" text="#000000">
    <br>
    Thank,<br>
    <br>
    -- <br>
    Mehdi<br>
    <br>
  </div>

</blockquote></div><br></body></html>