<div dir="ltr">On 22 August 2013 16:00, Eugene Toder <span dir="ltr"><<a href="mailto:eltoder@gmail.com" target="_blank">eltoder@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div class="im">On Thu, Aug 22, 2013 at 6:40 PM, Nick Lewycky <span dir="ltr"><<a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div>It's a known limitation, see ScalarEvolution.cpp:5568.</div><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>The fundamental problem is that len in your example could be (unsigned) -1, -2 or -3, in which case your loop is infinite.</div>
</div></div></div></blockquote><div><br></div></div><div>Unless I'm missing something, if len is -1 (or otherwise less than 0) the loop has 0 trip count. Did you mean INT_MAX-1, INT_MAX-2 etc? In this case, I believe, the behavior is undefined, because adds are marked with "nsw".</div>
</div></blockquote><div><br></div><div>Doh, 's' was unsigned, 'i' was signed. My mistake.</div><div><br></div><div>Regardless, this part of SCEV isn't looking for NSW bits yet and consequently is optimizing as-if the function were written with 'i' and 'len' as unsigned.</div>
<div><br></div><div>But I'm not sure that we should use nsw to fix this, in spite of the fact that this is exactly what nsw was designed for. We know the answer even for the unsigned case, and we should just use that. Add a new SCEV node which lets us return that it's infinite in this case, and trip count X in the other; along the lines of "SCEVPotentiallyInfinite(m > int_max-3, sdiv(m, 4))".</div>
<div><br></div><div>I've proposed this previously: <a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120917/151250.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120917/151250.html</a></div>
<div><br></div><div>Nick</div><div><br></div></div></div></div>