[LLVMdev] EQTDDataStructures omits obvious, direct callee from DSCallGraph

[Ben Liblit]

Vikram Adve wrote:
> As Will suggested, try the TD pass, not EQTD, and see if that works
> better for you.

Hi Vikram!  Yes, TD is definitely working better.  However, there are 
still a few oddities outstanding where (IMHO) TD really ought to be 
doing a better job: 
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042352.html>.

> Having said that, DSA currently doesn't do well with vtables.  It is not a fundamental limitation of the algorithm itself
> and we think we know how to improve it, so if those are important to
> you, let me know.

Doing *something* reasonable to resolve vtable-based calls is definitely 
very important to me.  I am currently handling these myself by 
exploiting knowledge of how vtables are used in C++ and also knowledge 
of the style of bitcode emitted by clang or other front-ends for vtable 
lookups.  I suppose that could be considered a bit of a hack; it might 
be nicer to handle pure bitcode without relying on C++-specific 
knowledge or front-end-specific knowledge.  If you think DSA can learn 
to do that, then I'd be happy to discard my vtable-handling code in 
favor of DSA's.  But I guess I'd say I'm not dead in the water even if 
DSA cannot deal with vtables precisely.

That said, I definitely require an analysis that will not collapse into 
a degenerate "everything can call everything" result in code that uses 
vtables.  So far DSA's TD pass seems to be OK in this regard.  Even if 
it is not good at analyzing vtable uses itself, it at least does not 
fall to pieces if vtable lookups are going on nearby.  So that's very 
encouraging.

> DSA is indeed a unification-style analysis, not inclusion based.  It
> is partially context sensitive (someone else labeled it "bottom-up
> context sensitive" in a later paper), which makes up for unification
> in some cases.  As you probably know, the two are not comparable:
> inclusion style analyses will do better in some cases but
> context-sensitivity will do better in others.

Honestly at this point I do not yet know which analysis features 
(inclusion/unification, context-sensitivity, etc.) will be important for 
me and which will not.  That's going to have to come from further 
experimentation with our real, full analysis on complex programs we 
really care about.  For now I'm just trying to assess whether DSA is 
stable and trustworthy in simple situations.  If it is, then I'll 
continue working to hook it up for use in our "real" analyses.

> Ben Hardekopf and Calvin Lin have a good inclusion-based analysis for
> LLVM that is open source.

Yes, I plan to give that a try as well.  As I said, right now I don't 
really know if inclusion is important or not.  If I can get their code 
up and running with recent LLVM checkouts, then I'll certainly consider 
it as an alternative.  Thanks for the suggestion.

Regards,
Ben