[llvm-dev] flow-sensitive alias analysis

[Oliver Braunsdorf via llvm-dev]

> 
> On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev
> <llvm-dev at lists.llvm.org <mailto: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)
> 

Okay, so thats is what I expected...no exact static alias analysis in
polynomial time.
We can only get (over-)approxmations for the may-alias problem by the
algorithms implemented in LLVM. Thats fine for me. But all those
implementations are flow-insensitive.
So my original question was: Are there implementations of flow-sensitive
algorithms that are usable in LLVM (through AA-Interface,
MemorySSA/MemoryDependenceAnalysis)?
Because my assumption is: (sparse) flow-sensitive algorithms can have
nearly the same time requirements as flow-insensitive ones but are a
little more precise.


-Oliver