[LLVMdev] AliasAnalysis update interface - a tale of sorrow and woe

[Daniel Berlin]

The vast majority of stateful AA probably doesn't/won't care about the
vast majority of updates.

For example, unless globalsmodref is going to recompute the transitive
closure, it can't actually give better than "i don't know" answers in
most cases, which is equivalent to telling it "you should delete this
pointer and pretend you know nothing about it".  Humorously, you can
see that's what it did with addEscapingUse. It deleted anything it
knew about the pointer.

Further, once that delete has happened once, there is no point in ever
tracking anything about that value ever again for globalsmodref.  It
will never regain that info.

Even for those that do care, there are other issues:
The AA may never be queried again.  Or the IR may change 6 or 7 times
before it gets queried again.  The only thing any AA needs to know in
general is "what is the net result of those changes" (IE added uses,
etc). For example, if you were to add and then remove a use before
querying AA, no AA will care. Telling it an add and then remove is not
only pointless and expensive, it is probably worse than telling it
"nothing happened" (which is the net effect).

In any case, i think we need to sit down and think "which of these
AA's do we want to cache/make stateful, and how".
Because the original use case for building a stateful API, from what i
can tell, is globalsmodref.  This is not a great use case, since
incremental updating may require a complete callgraph walk.  That
seems like a non-starter :-)

Nowadays, i expect the stateful use cases are more like "caching
CFL-AA or caching expensive parts of BasicAA" (both of which are
O(pointer chain) to update incrementally).
Even andersen's can be incrementally computed quicker in practice (For
additional uses, delete variable from sets, add new constraints,
fixpoint.  In most cases, you can prove the new constraint doesn't
change the results, so you do nothing.  Or it takes one iteration of
propagation.  Worst case is N^3 like the callgraph walk, but in
practice, it's probably closer to O(pointer chain))





On Thu, Jul 2, 2015 at 2:05 PM, Pete Cooper <peter_cooper at apple.com> wrote:
>
> On Jul 2, 2015, at 1:17 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
> I should add that I'm somewhat afraid, however, of the compile-time
> implications of adding the necessary hook.
>
> I was just going to say this myself.
>
> In fact, even if you don’t add a hook for tracking new values, just using
> value handles in AA could prove to be expensive.
>
> A typical optimized piece of code has more load instructions than binary
> instructions.  If you only cached loads with value handles, you’re already
> creating a huge number of handles, and these are currently entries in a map
> (pImpl->ValueHandles[V] if you’re curious).
>
> TL;DR: If we are going to create this many value handles, we should strongly
> consider finding a way to represent them more cheaply.
>
> Cheers,
> Pete
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>