[LLVMdev] EQTDDataStructures omits obvious, direct callee from DSCallGraph

[Adve, Vikram Sadanand]

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