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

I am using EQTDDataStructures (from the poolalloc project) to resolve 
indirect function calls to over-approximated sets of possible callees. 
Unfortunately I find that it yields incorrect results even on a very 
simple test input.  My LLVM and poolalloc sources are Subversion trunk 
checkouts, no more than a day older than the current trunk head.  My 
test input is the following C source, compiled to bitcode using Clang:

	void foo();

	void test()
	{
	  foo();
	  foo();
	}

It should be rather obvious that each of the two call sites in test() 
must have exactly one callee: foo().  However, DSCallGraph reports 
*zero* possible callees at the first call site.  (It does correctly 
report foo() as the one possible callee at the second call site.)

Why is the analysis getting this wrong?  Of course I am trying to build 
up to more complex, indirect calls.  But right now this very simple case 
has me stuck.

Attached below is the complete source code for my pass which prints out 
the possible callees at each call site.  The important logic is at the 
end, in ShowCallGraph::runOnBasicBlock().  It seems simple enough.  Am I 
doing something wrong here?

Thanks,
Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ShowCallGraph.cpp
Type: text/x-c++src
Size: 1404 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110809/8286eed9/attachment.cpp>

On Tue, Aug 9, 2011 at 6:19 PM, Ben Liblit <liblit at cs.wisc.edu>
wrote:
> I am using EQTDDataStructures (from the poolalloc project) to resolve
> indirect function calls to over-approximated sets of possible callees.
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.

Andrew
> Unfortunately I find that it yields incorrect results even on a very simple
> test input.  My LLVM and poolalloc sources are Subversion trunk checkouts,
> no more than a day older than the current trunk head.  My test input is the
> following C source, compiled to bitcode using Clang:
>
>        void foo();
>
>        void test()
>        {
>          foo();
>          foo();
>        }
>
> It should be rather obvious that each of the two call sites in test() must
> have exactly one callee: foo().  However, DSCallGraph reports *zero*
> possible callees at the first call site.  (It does correctly report foo()
as
> the one possible callee at the second call site.)
>
> Why is the analysis getting this wrong?  Of course I am trying to build up
> to more complex, indirect calls.  But right now this very simple case has
me
> stuck.
>
> Attached below is the complete source code for my pass which prints out the
> possible callees at each call site.  The important logic is at the end, in
> ShowCallGraph::runOnBasicBlock().  It seems simple enough.  Am I doing
> something wrong here?
>
> Thanks,
> Ben
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

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.