llvm dev - Aug 2011 - [LLVMdev] EQTDDataStructures omits obvious, direct callee from DSCallGraph

Hi, Ben,

As Will suggested, try the TD pass, not EQTD, and see if that works better for
you.  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.

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.

Ben Hardekopf and Calvin Lin have a good inclusion-based analysis for LLVM that
is open source.  They actually have two separate algorithms: flow-insensitive
and flow-sensitive.  I believe the former has been released publicly but Ben may
be able to give you the latter as well.  Neither of them is context-sensitive so
if you want context sensitivity in particular, let's discuss that further.

--Vikram
Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve



On Aug 11, 2011, at 6:24 AM, <llvmdev-request at cs.uiuc.edu>
 wrote:
> Date: Wed, 10 Aug 2011 23:44:14 -0500
> From: Will Dietz <willdtz at gmail.com>
> Subject: Re: [LLVMdev] EQTDDataStructures omits obvious,	direct callee
> 	from DSCallGraph
> To: Ben Liblit <liblit at cs.wisc.edu>
> Cc: llvmdev at cs.uiuc.edu
> Message-ID:
> 	<CAKGWAO-Co6V0VFTHRyjpq9MQNPsv9Wo+36=vFTczhFgwB9Ks5g at
mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
> 
> On Tue, Aug 9, 2011 at 10:45 PM, Ben Liblit <liblit at cs.wisc.edu>
wrote:
>> Andrew Lenharth wrote:
>>> If I remember correctly, it only tries to resolve indirect calls.
?The
>>> analysis doesn't track direct calls because you can do it just
as well
>>> yourself.
>> 
>> DSCallGraph::callee_begin() and DSCallGraph::callee_end() cooperate to
>> iterate over an empty set (EmptyActual) for any call site not found in
>> the ActualCallees map. ?So if direct calls are not tracked, then I
would
>> expect the callee iterators for *both* direct calls to yield this empty
>> set. ?Getting the empty set for one direct call but a correct singleton
>> set for the other direct call is a troubling inconsistency that leaves
>> me unsure which results I can trust and which I cannot.
> 
> Hi Ben,
> 
> I just tested the example you gave, and get the same results--one set
> is empty, the other contains the expected single function.
> 
> As Andrew mentioned, DSA handles indirect and direct callsites
> differently, and for direct callsites it's expected that the user
> simply looks at the function itself to determine what is called.
> 
> In this example, we only track one callsite in test() since as far as
> alias analysis goes, the effects of both callsites are same, and we
> don't need to consider both callsites to build our analysis. This kind
> of optimization is extremely useful in making DSA run on larger codes.
> 
> That said, we probably could more cleanly export this information to
> the user, but for now just handle direct calls yourself.  Sorry for
> the confusion :).
> 
> Hope this helps!
> 
> ~Will

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