On Sat, 31 Mar 2012, John Criswell wrote:> One thing you could do to mitigate that problem is to do an experiment > that *shows* that your analysis has the potential to find more > optimization opportunities than what LLVM does today.I strongly agree. If the analysis doesn't provide a good value proposition, almost nobody will care about it. A great use case for value range analysis (that I'm personally very interested in) is improving the performance of codes that check for integer overflows: http://embed.cs.utah.edu/ioc/ The synergy should be obvious. To improve the performance of these codes, someone will need to write a pass that uses value ranges to optimize the LLVM intrinsics that check for math overflows. Ideally, the overhead of overflow checking could be reduced to the point where some users might enable it in production codes. John Regehr
Hi John, On 31/03/12 23:18, John Regehr wrote:> On Sat, 31 Mar 2012, John Criswell wrote: > >> One thing you could do to mitigate that problem is to do an experiment >> that *shows* that your analysis has the potential to find more >> optimization opportunities than what LLVM does today. > > I strongly agree. If the analysis doesn't provide a good value > proposition, almost nobody will care about it. > > A great use case for value range analysis (that I'm personally very > interested in) is improving the performance of codes that check for > integer overflows: > > http://embed.cs.utah.edu/ioc/from what I understand of the analysis, to come to its conclusions it assumes that there is no overflow. That doesn't make it useless for removing integer overflow checks: you can successively walk variables, and if you can prove that there is no overflow of a variable X given your analysis of previously seen variables, then X can safely be added to the set of analysed variables. Rinse and repeat. However this probably doesn't work for variables inside loops. Hopefully Victor can clarify. Ciao, Duncan.> > The synergy should be obvious. To improve the performance of these codes, > someone will need to write a pass that uses value ranges to optimize the > LLVM intrinsics that check for math overflows. > > Ideally, the overhead of overflow checking could be reduced to the point > where some users might enable it in production codes. > > John Regehr > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> from what I understand of the analysis, to come to its conclusions it assumes > that there is no overflow. That doesn't make it useless for removing integer > overflow checks: you can successively walk variables, and if you can prove that > there is no overflow of a variable X given your analysis of previously seen > variables, then X can safely be added to the set of analysed variables. Rinse > and repeat. However this probably doesn't work for variables inside loops.I'd also be interested to hear more from the range analysis authors about this. Remaining faithful to the C/C++ overflow rules while operating on LLVM IR may be very tricky, particularly with respect to integer promotions and similar constructs, which may have no representation in the IR (even before optimization). An analysis that is not sound with respect to the original C/C++ semantics would be of little use to anyone. John