Does LLVM hoist bounds checks out of inner loops? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e
On Nov 30, 2007, at 5:59 PM, Jon Harrop wrote:> > Does LLVM hoist bounds checks out of inner loops?LLVM does loop unswitching, so yes in some cases it does. -Chris
LLVM itself doesn't do any bounds checks, but if the language front end puts in any, they may be optimized (and hoisted) just as other comparison operators and branches might. In other words, the LLVM passes don't recognize any bounds checks specifically. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.org/ On Nov 30, 2007, at 10:28 PM, Chris Lattner wrote:> > On Nov 30, 2007, at 5:59 PM, Jon Harrop wrote: > >> >> Does LLVM hoist bounds checks out of inner loops? > > LLVM does loop unswitching, so yes in some cases it does. > > -Chris > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20071130/fcd4dca5/attachment.html>
On Nov 30, 2007, at 20:59, Jon Harrop wrote:> Does LLVM hoist bounds checks out of inner loops?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: struct array { int length; int values[]; }; extern void x(void); void f(struct array *arr) { for (int i = 0; i < arr->length; ++i) { if (i < 0 || i >= arr->length) throw; // trivially unreachable x(); if (i < 0 || i >= arr->length) throw; // unreachable only if 'x() changed arr->length' is provably false } } You can make alias analysis stronger by: • using -anders-aa instead of -basic-aa • performing link-time optimization • using the new 'readonly' and 'readnone' function attributes whenever possible 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. — Gordon -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20071201/1986f441/attachment.html>
On Saturday 01 December 2007 16:07, Gordon Henriksen wrote:> ... > 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.Brilliant, thanks. I'm extremely busy ATM but my plan is to implement a compiler for a pure first-order language and use it to benchmark various different approaches. I might even reuse my ray tracer benchmark for this... :-) -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e