On Thu, Aug 22, 2013 at 6:40 PM, Nick Lewycky <nlewycky at google.com> wrote:> It's a known limitation, see ScalarEvolution.cpp:5568. > > The fundamental problem is that len in your example could be (unsigned) > -1, -2 or -3, in which case your loop is infinite. >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". Eugene -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/74d2c0f9/attachment.html>
On 22 August 2013 16:00, Eugene Toder <eltoder at gmail.com> wrote:> On Thu, Aug 22, 2013 at 6:40 PM, Nick Lewycky <nlewycky at google.com> wrote: > >> It's a known limitation, see ScalarEvolution.cpp:5568. >> >> The fundamental problem is that len in your example could be (unsigned) >> -1, -2 or -3, in which case your loop is infinite. >> > > 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". >Doh, 's' was unsigned, 'i' was signed. My mistake. 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. 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))". I've proposed this previously: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120917/151250.html Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/efd655af/attachment.html>
On Thu, Aug 22, 2013 at 7:10 PM, Nick Lewycky <nlewycky at google.com> wrote:> 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))". >I think SCEV should use nsw when possible (that's exactly what the flag is for, as you've said). For unsigned cases, "potentially infinite" sounds reasonable, but transforms will have to be updated to handle it. E.g. for vectorization infinite loop is probably OK to vectorize. For closed form computation a check will have to be inserted. Another thought is that we can prove this particular loop is finite even if i was unsigned. It has *a++ in the body. If a is infinitely incremented the dereference will, at some point, cause undefined behavior. Eugene -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/99d7089e/attachment.html>