[LLVMdev] Contribute a new precise pointer analysis to LLVM

[Will Dietz]

I would be very interested in a maintained precise pointer analysis
with decent scalability!

My research group routinely does various kinds of analysis that would directly
benefit from a reliable pointer analysis.  While scalability is indeed
important,
correctness (especially on edge cases that occur in 'real' code) is the
biggest failure point of the precise analyses we've used (and built) to date.

On that, what sort of work has been done to ensure the results of your
analysis are correct?

LLVM's optimizations are a good litmus test for whether the analysis gets
basic things right, but last time I checked they only query for simple
relations.  This means they don't tend to be good checks for ensuring
correctness, something that's critical but also difficult to check
for something as complicated as a precise pointer analysis on
something as non-trivial as LLVM IR.

As an aside, this *might* mean LLVM is not tailored to maximally benefit
from a more precise analysis: it would be a waste of engineering
effort and compile time to have optimization passes that make queries
about properties our current analyses will never be able to prove.
Just a thought.

Regarding correctnes, our group has had great success teasing out
analysis bugs with instrumentation passes that add code to dynamically
assert the properties claimed by the analysis or by clients
of the analysis.  Callgraph checking is a great example
that can involve some rather tricky situations while
being cheap to check dynamically.  More powerful checks
are also useful, but have a higher runtime cost.

My co-worker Joshua (on this thread) implemented these as
part of one of our projects, and we've previously discussed
spending some time to make it available to the community.
Please let either of us know if this sounds useful :).

~Will


On Wed, Oct 23, 2013 at 9:15 AM, Joshua Cranmer 🐧 <Pidgeot18 at gmail.com> wrote:
> On 10/23/2013 7:52 AM, lian li wrote:
>>
>> According to our experiments with SPEC, we haven't observed significant
>> impact in terms of execution performance. In our experiments, we run a list
>> of 8 optimizations that require alias analysis (including -licm, -gvn,
>> -bb-vectorize,...), and for each optimization we rerun our analysis so that
>> its result can be used by the optimization pass. The biggest performance
>> improvement we observed is close to 3%, but for some benchmarks we also have
>> a slow down of 2%. The overall performance improvement is less than 0.5%.
>
>
> Would it be possible to measure performance improvement for a large
> application or two that compiles with -fno-strict-aliasing?
>
> --
> Joshua Cranmer
> Thunderbird and DXR developer
> Source code archæologist
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev