[LLVMdev] GSoC - Range Analysis

[Duncan Sands]

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