<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 Nov 16, 2012, at 10:56 AM, Brendon Cahoon <<a href="mailto:bcahoon@codeaurora.org">bcahoon@codeaurora.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">Hi,<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">I have a question about some code in ScalarEvolution.cpp, in the function HowManyLessThans. Specifically, this function returns CouldNotCompute if the iteration step is greater than one even when the NoWrap flags are set (if the step goes past the limit and wraps). Here’s the comment:<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> } else if (isKnownPositive(Step)) {<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // Test whether a positive iteration can step past the limit<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // value and past the maximum value for its type in a single step.<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // Note that it's not sufficient to check NoWrap here, because even<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // though the value after a wrap is undefined, it's not undefined<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // behavior, so if wrap does occur, the loop could either terminate or<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // loop infinitely, but in either case, the loop is guaranteed to<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> // iterate at least until the iteration where the wrapping occurs.<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> <o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">I have no doubt that there is a good reason for this code to work this way (there is a specific check in trip-count9.ll). I’m just trying to understand it better. I’m assuming that when the previous version of this code checked the NoWrap flag, that it caused a problem with some optimization pass? If so, does anyone recall the pass.<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">I’m also curious if the –f[no]-strict-overflow flag has any impact on the assumptions? Or, could the function check NoWrap for the unsigned case only?<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">The motivating example for this question occurs because we’re not unrolling loops with a run-time trip count when the loop induction variable is a pointer and the loop end check is another pointer. For example,<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> void ex( int n, int* a, int* c ) {<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> int b = 1; int *ae = a + n;<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> while ( a < ae) {<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> c ++; b += *c; *a++ = b;<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> }<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"> }<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">Thanks,<o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;">Brendon</div></div></div></blockquote><br></div>Someone pointed me to this message that lacked a response. Sorry for not reading llvmdev that week in the distant past, but for the record...<div><br></div><div>‘a’ can exceed ‘ae’ without undefined behavior if the pointers were somehow misaligned. Then hypothetically ‘a’ can step off the end of the address space (unsigned wrap).</div><div><br></div><div>The key to understanding the problem is that SCEV NoWrap flag guarantees that ‘a’ can never surpass its original value, regardless of signed or unsigned wrapping. It’s doesn’t mean that signed/unsigned wrap can’t occur.</div><div><br></div><div>SCEV’s thinking here is that the loop may continue to iterate at this point, modifying program state in some valid way, then later terminate via some other mechanism. Then there’s the whole issue of what undefined behavior means in LLVM. Are we beholden to execute all well-defined loop iterations even if we can prove that undefined behavior will eventually occur?</div><div><br></div><div>What SCEV doesn’t realize is: comparing a < ae is already undefined if ‘a’ just unsigned-wrapped since it’s a pointer comparison and the step was positive (pointers unsigned-wrap all the time with negative steps). It also can’t see that dereferencing ‘a’ would result in undefined behavior if a positive step led to unsigned wrap (I guess I’m assuming that a single object can’t span more than half the address space).</div><div><br></div><div>SCEV also has no way to communicate to a client, like unrolling, that if the loop test is the only possible way for the loop to terminate in a well-defined way, then the trip count can be guaranteed.</div><div><br></div><div>So, I *do* think we could handle this case. But to do it we need to either add intelligence to SCEV (which is tricky to reason about) or add some knowledge about the whole loop when asking for the trip count (which is tricky to engineer).</div><div><br></div><div>It wouldn’t hurt to file a bug. I don’t see a lot of people hacking on SCEV, but you never know.</div><div><br></div><div>-Andy</div><div><br></div></body></html>