<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 29, 2017, at 10:38 AM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="">sanjoy@playingwithpointers.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">Hi Peter,</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">On Thu, Jun 29, 2017 at 8:41 AM, Peter Lawrence</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class=""><</span><a href="mailto:peterl95124@sbcglobal.net" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">peterl95124@sbcglobal.net</a><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">> wrote:</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">Here’s another way to look at it, no one has ever filed a bug that reads<br class="">“I used undefined behavior in my program, but the optimizer isn’t taking advantage of it”<br class="">But if they do I think the response should be<br class="">“you should not expect that, standard says nothing positive about what undefined behavior does"<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">Of course no one would file such a bug (since if your program has UB,</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">the first thing you do is fix your program). However, there are</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">plenty of bugs where people complain about: "LLVM does not optimize my</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">(UB-free) program under the assumption that it does not have UB"</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; display: inline !important;" class="">(which is what poison allows):</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""></div></blockquote><div><br class=""></div><div>Sanjoy,</div><div> I copied the bug reports below for reference.</div><div><br class=""></div><div>The way I read the first report is that the reason this problem exists today is the </div><div>existence of “poison” in the LangRef, IE. we have to call isSCEVExprNeverPoison()</div><div>which returns true in this case.</div><div><br class=""></div><div><div class="">So this is a reason to not have “poison”, “poison” is not enabling anything</div><div class="">here, it is actually making it harder to do this optimization.</div><div class=""><br class=""></div><div class=""><div>This entire problem disappears in the alternate proposal</div><div>(Fix “undef”, delete “poison” and “freeze”, no hoisting of nsw attributes)</div></div><div class="">because the function isSCEVExprNeverPoison() would be deleted.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">The way I read the second report is that a special case needs to be added for "+nsw"</div><div class="">This does not seem to have any thing to do with “undef” or “poison"</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Note that I don’t consider optimizing “nsw” as an example of optimizing “undefined</div><div class="">Behavior”, “nsw” is simply an attribute that we take advantage of, so</div><div class=""><br class=""></div><div class="">I am still waiting for someone to come up with a real source code example</div><div class="">were “undef” / “poison” occurs in the IR and the optimizer takes advantage.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter Lawrence.</div></div><div><br class=""></div><div><br class=""></div><div><br class=""></div><div><div id="c2" class="bz_comment" style="margin-bottom: 2em; font-family: Verdana, sans-serif;"></div></div><blockquote type="cite" class=""><div class=""><a href="https://bugs.llvm.org/show_bug.cgi?id=28429" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://bugs.llvm.org/show_bug.cgi?id=28429</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""></div></blockquote><div><br class=""></div><div><span style="white-space: pre-wrap; font-size: 14px;" class=""><font face="Menlo" class="">The following loop is not unrolled because the trip count is not simple constant: </font></span></div><div><div id="c2" class="bz_comment" style="margin-bottom: 2em;"><pre class="bz_comment_text" id="comment_text_2" style="white-space: pre-wrap; width: 50em;"><font face="Menlo" style="font-size: 14px;" class="">
void foo(int x, int *p) {
x += 2; //any value bigger than 1
for (int i = x; i <= x+1; ++i) p[i] = i;
}
The attached IR is generated compiling the above source with:
./bin/clang --target=aarch64-arm-none-eabi -mllvm -debug-only=loop-unroll -O3
SCEV find the trip count as: (-2 + (-1 * %x) + ((2 + %x) smax (3 + %x)))
This expression can be simplified into a constant if the arguments of smax are not wrapping. But while the original source has non-wrapping expressions, they are not marked as such by SCEV. Reason is that SCEV considers these expressions possible poison values and marks them as wrapping. This seem to be a limitation in the llvm::ScalarEvolution::isSCEVExprNeverPoison function.
Analysis so far:
The actual add instructions have the nsw flags and reside in a basic block just before the loop body. The isSCEVExprNeverPoison function is called on them but assumes the instruction must be part of a loop. If the instruction is not part of any loop it is reported as a possible poison value.
A possible fix would be to assume the instruction is loop independent if it is not part of any loop. But I am not sure if the loop information is complete (does absence of loop info on a basic block means there is no loop in the code in the scalar evolution pass?). With such a fix the resulting expression would be:
(-2 + (-1 * %x) + ((2 + %x)<nsw> smax (3 + %x)<nsw>)
This is foldable, although the current folding expression constructors don’t handle this case yet.</font></pre><div style="font-family: Verdana, sans-serif;" class=""><span style="font-size: 14px;" class=""><br class=""></span></div></div></div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><a href="https://groups.google.com/forum/#!topic/llvm-dev/JGsDrfvS5wc" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://groups.google.com/forum/#!topic/llvm-dev/JGsDrfvS5wc</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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;" class=""></div></blockquote><br class=""></div><div><br class=""></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">It looks like ScalarEvolution bails out of loop backedge computation</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">if it cannot prove the IV stride as either positive or negative </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">(based on loop control condition). </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">I think this logic can be refined for signed IVs.</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""></span><br class=""></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">Consider this simple loop-</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""></span><br class=""></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">void foo(int *A, int n, int s) {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class=""> int I;</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class=""> for(i=0; i<n; i += s) {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class=""> A[i]++;</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class=""> }</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">} </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""></span><br class=""></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""> </span><br class="webkit-block-placeholder"></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">The IV of this loop has this SCEV form-</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""></span><br class=""></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">{0,+,%s}<nsw><%for.body></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""></span><br class=""></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255); min-height: 16px;" class=""><span style="font-size: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures;" class=""> </span><br class="webkit-block-placeholder"></span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">Can someone please clarify why it is not ok to deduce the stride to be </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">positive based on the assumption that the IV cannot have a signed </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">underflow due to the presence of the NSW flag otherwise the program </span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="font-variant-ligatures: no-common-ligatures; font-size: 14px;" class="">has undefined behavior?</span></div></div><br class=""></body></html>