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.