[LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?

Christian Convey christian.convey at gmail.com
Mon Jun 15 14:20:23 PDT 2015


On Mon, Jun 15, 2015 at 4:54 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

> > I'm mostly going from Robert Wilson's 1997 phd thesis, although I'm
> pretty
> > sure I've seen a lot of the same ideas elsewhere as well.
>
> Yes, using summary/transfer functions has been tried a lot.
> Note: the numbers in most of these phd thesis do *not* get born out in
> practice.
>
> See, e.g, http://www.cse.unsw.edu.au/~ysui/papers/spe14.pdf
>
> vs
>
> http://impact.crhc.illinois.edu/shared/report/phd-thesis-erik-nystrom.pdf
>
> vs
> the wilson thesis.
>

Cool, I'll give those papers a read, thanks.


> In particular, i expect the wilson algorithm is going to fall over
> very badly on anything of even medium size.
>

Interesting.  Do you mean "fall over" in terms of running time, or
precision, or something else?


> Nowadays, the thing of the day seems to be using cfl reachability
> based formulations and doing context-sensitivity on demand.
>

Out of curiosity, what's the appeal (aside from academic novelty) of the
CFL approaches?

>From a personal perspective, I'm particularly interested in the maximum
analytic precision each AA approach can take, almost without regard to how
much time or memory the computation takes to run.  So one thing I found
appealing about Wilson's thesis was his "location set" approach for
providing field-sensitivity.

I also liked Alain Deutsch's 1994 paper "Interprocedural may-alias analysis
for pointers: Beyond k-limiting" for the same reason.  But I didn't take a
crack at implementing *that* because based on the paper's complexity, I
thought I'd go clinically insane trying to turn it into code :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/f01e8377/attachment.html>


More information about the llvm-dev mailing list