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

On Mon, Jun 15, 2015 at 3:29 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Mon, Jun 15, 2015 at 10:33 AM, Christian Convey
> <christian.convey at gmail.com> wrote:
> > On Mon, Jun 15, 2015 at 11:02 AM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
> Which paper are you using?
>
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.

> IE we propagate the various "unknown/points-to-anything/etc"
flags as
>
fast as possible, to the exclusion of discovering other
points-to
> sets.
>
> This is because once something points-to anything, it doesn't matter
> what else it points to :)
>
Nice to know that the idea has been vetted in at least one AA
implementation.  Thanks for the info.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/c11d3d88/attachment.html>

On Mon, Jun 15, 2015 at 1:46 PM, Christian Convey
<christian.convey at gmail.com> wrote:
> On Mon, Jun 15, 2015 at 3:29 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>>
>> On Mon, Jun 15, 2015 at 10:33 AM, Christian Convey
>> <christian.convey at gmail.com> wrote:
>> > On Mon, Jun 15, 2015 at 11:02 AM, Daniel Berlin <dberlin at
dberlin.org>
>> > wrote:
>> Which paper are you using?
>
>
> 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.


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

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

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>