<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On Nov 30, 2007, at 20:59, Jon Harrop wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Does LLVM hoist bounds checks out of inner loops?<br></blockquote><br></div><div>In practice, LLVM is frequently going to have conservative behaviors which will prevent hoisting the explicit bounds checks your front-end must generate. Specifically, LLVM must use alias analysis to disprove the hypothesis that the array length variable is updated by the body of the loop. Consider:</div><div><br class="webkit-block-placeholder"></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" color="#000080">struct</font> array { <font class="Apple-style-span" color="#000080">int</font> length; <font class="Apple-style-span" color="#000080">int</font> values[]; };<br></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" color="#000080">extern void</font> x(<font class="Apple-style-span" color="#000080">void</font>);<br><br></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" color="#000080">void</font> f(<span class="Apple-style-span" style="color: rgb(0, 0, 128); ">struct</span> array *arr) {</blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"> <font class="Apple-style-span" color="#000080">for</font> (<font class="Apple-style-span" color="#000080">int</font> i = 0; i < arr->length; ++i) {</blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> <font class="Apple-style-span" color="#000080">if</font> (i < 0 || i >= arr->length)</blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> <span class="Apple-style-span" style="color: rgb(0, 0, 128); ">throw</span>; <font class="Apple-style-span" color="#FF0000"> // trivially unreachable</font></blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> x();</blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"> <font class="Apple-style-span" color="#000080">if</font> (i < 0 || i >= arr->length)</blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"> <span class="Apple-style-span" style="color: rgb(0, 0, 128); ">throw</span>; <font class="Apple-style-span" color="#FF0000"> // unreachable only if 'x() changed arr->length' is provably false</font></blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> }</blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">}</blockquote><br><div>You can make alias analysis stronger by:</div><div><div><div><br class="webkit-block-placeholder"></div><div>• using -anders-aa instead of -basic-aa</div><div>• performing link-time optimization</div><div>• using the new 'readonly' and 'readnone' function attributes whenever possible</div><div><br></div><div>Since you're working with a functional language, you may be able to know that 'arr' itself and 'arr.length' are both immutable (based on properties of your language/object model). If so, use only a single SSA value for each rather than 'load'ing them over again at each use. This eliminates the dependency on alias analysis (at the cost of increased register pressure). With that out of the way, it becomes a matter of building a pass pipeline which either hoists or eliminates the checks. opt -mem2reg -gvn -predsimplify -licm -dce -simplifycfg may be a starting point for elimination. Any of the passes in lib/Transforms/Scalar which include the string 'SCEV' may be helpful for hoisting.</div></div></div><div><div><br class="webkit-block-placeholder"></div><div>— Gordon</div></div><div apple-content-edited="true"> </div><br></body></html>