[llvm-dev] flow-sensitive alias analysis

[Daniel Berlin via llvm-dev]

On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> > Perhaps by "value" you mean points-to set?
>
> Thats right! I meant the points-to set. Sorry I didn't mention that.
> I want to track back the value of the parameter to its definition -- an
> "assignment" which could be indirect through a pointer to the value used
> as the function argument.
>
> > Either way, flow-sensitivity can only give you more precise -- but still
> > not necessarily exact -- answers.
>
> I am aware of the inexactness of (flow-sensitive) alias analysis. Is
> there an exact way to accomplish this?
>

No, even the non-flow-sensitive version of the problem is statically
undecidable for may-alias, and not even recursively enumerable for
must-alias.
This is true even when all paths through the program are executable.

If you leave out recursive data structures, it is simply NP complete, and
thus, you could compute an exact answer, very expensively.

The TL;DR is that for most languages, there can be no exact aliasing
computation, only approximations.
See, e.g,  http://dl.acm.org/citation.cfm?doid=161494.161501 and
http://dl.acm.org/citation.cfm?id=186025.186041

(btw, it gets worse.  If you disallow recursive data structures, and allow
multiple levels of pointers, precise flow-sensitive may-alias is NP-hard
even when restricted to intraprocedural and *no* dynamic memory allocation)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170312/eb9b389a/attachment.html>