> > 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 --
> "assignment" which could be indirect through a pointer to the value
> as the function argument.
> > Either way, flow-sensitivity can only give you more precise -- but
> > 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
> 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
Okay, so thats is what I expected...no exact static alias analysis in
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.
Yes, because flow-sensitivity doesn't really buy much for the cost.
So my original question was: Are there implementations of flow-sensitive
algorithms that are usable in LLVM (through AA-Interface,
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.
This assumption is very wrong, AFAIK
The best known precise flow-insensitive algorithms easily handle pretty
much any scale these days.
GCC's points-to is field-sensitive precise flow-insensitive, and it pretty
much never shows up on profiles.
By contrast, the best sparse known sparse flow-sensitive analysis varies
(quite wildly, in fact), is usually between 10x and 100x slower.
This is true even when, for example, parallelized on GPU's (see, e.g.,
If you only care about certain pointers, you would be better off with a
See, e.g., "Demand-Driven pointer analysis with Strong updates using