<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 Sep 22, 2015, at 2:36 PM, Owen Anderson via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Sep 22, 2015, at 2:02 PM, Jingyue Wu <<a href="mailto:jingyue@google.com" class="">jingyue@google.com</a>> wrote:</div><div class=""><div dir="ltr" class=""><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">Is LLVM allowed to unroll</span></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">for (int i = 0; i < 4; ++i) {</span></div><div class=""><span style="font-size:12.8px" class=""> if (i < c) // c is loop invariant</span></div><div class=""><span style="font-size:12.8px" class=""> convergent();</span></div><div class=""><span style="font-size:12.8px" class="">}</span></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">to</span></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">if (0 < c)</span></div><div class=""><span style="font-size:12.8px" class=""> convergent();</span></div><div class=""><div class=""><span style="font-size:12.8px" class="">if (1 < c)</span></div><div class=""><span style="font-size:12.8px" class=""> convergent();</span></div></div><div class=""><div class=""><span style="font-size:12.8px" class="">if (2 < c)</span></div><div class=""><span style="font-size:12.8px" class=""> convergent();</span></div></div><div class=""><div class=""><span style="font-size:12.8px" class="">if (3 < c)</span></div><div class=""><span style="font-size:12.8px" class=""> convergent();</span></div></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">?</span></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">Is "0 < c" considered "an additional value"? I'd vote no, but one can argue the other way. </span></div></div></div></blockquote><div class=""><br class=""></div><div class="">My intuition agrees with you here, but I don’t know how to formalize it.</div><br class=""></div></div></div></blockquote><div><br class=""></div><div>Introducing intermediate steps in the transformation? If the first transformation is valid, it seems trivial to get the end one:</div><div><br class=""></div><div><div>for (int i = 0; i < 1; ++i) {<br class=""> if (i < c) // c is loop invariant<br class=""> convergent();<br class="">}<br class=""><div>for (int i = 1; i < 2; ++i) {<br class=""> if (i < c) // c is loop invariant<br class=""> convergent();<br class="">}<br class=""><div>for (int i = 2; i < 3; ++i) {<br class=""> if (i < c) // c is loop invariant<br class=""> convergent();<br class="">}<br class=""><div>for (int i = 3; i < 4; ++i) {<br class=""> if (i < c) // c is loop invariant<br class=""> convergent();<br class="">}<br class=""><br class=""></div><div><div>— </div><div>Mehdi</div><div><br class=""></div><div><br class=""></div></div><div><div><div><div><br class=""></div></div></div></div></div></div></div></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><span style="font-size:12.8px" class="">One approach (Bjarke's idea) to work around such ambiguities is to define: a program is convergent-correct if everything marked convergent are indeed convergent. Then a transformation is convergent-correct unless it transforms a convergent-correct program to a convergent-incorrect one. However, defining "convergent-correct" involves SIMT concepts which you want to avoid here. </span></div></div></div></blockquote><br class=""></div><div class="">There are situations where this is over-conservative as well. Some convergent operations do not require uniformity per se. For example, a gradient operation in graphics programming models requires that all four threads in a given quad are either all executing or all not executing, though a warp is generally larger than that. Restricting convergent code motion to only be between uniform control flow points in the program would penalize that use case.</div></div></div></blockquote><div><br class=""></div></div><br class=""></body></html>