>
>
> > 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.
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,
MemorySSA/MemoryDependenceAnalysis)?
Nope.
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.,
http://dl.acm.org/citation.cfm?id=2555296).
If you only care about certain pointers, you would be better off with a
demand-driven technique.
See, e.g., "Demand-Driven pointer analysis with Strong updates using
value-flow refinement"
