[LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby

[Ben Liblit]

In an earlier message 
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042298.html), 
Andrew Lenharth suggested that EQTDDataStructures (from the poolalloc 
project) may only try to resolve indirect function calls.  However, I am 
now finding that the generated DSCallGraph over-approximates the callees 
in a very simple indirect call.  Some over-approximation is unavoidable, 
but this case seems simple enough that any reasonable analysis ought to 
have been able to give the exact, correct answer.

My example C++ source file, compiled to bitcode using clang from the 
current llvm trunk, is as follows:

	struct Base
	{
	  virtual void virt();
	};

	void Base::virt()
	{
	}

	void red();
	void blue();

	extern volatile int unknown;
	extern Base *base;

	void test()
	{
	  base->virt();
	  (unknown ? red : blue)();
	}

Observe that we have a class with a virtual method, and two indirect 
calls: one through a vtable to that virtual method, and another which is 
a simple non-deterministic choice between two possible function 
pointers.  I can understand an inexact (over-approximating) set of 
callees for the vtable call, as that is rather complex at the bitcode 
level.  However, I am very surprised to see an over-approximation at the 
second indirect call, which is merely picking between two possible values:

	%11 = phi void ()* [ @red(), %8 ], [ @blue(), %9 ]   # demangled
	call void %11()

Yet my DSCallGraph tester code reports that this instruction might call 
either red(), blue(), or Base::virt().  I am at a loss to explain why.

Equally strange: if I comment out the "base->virt();" call, then 
DSCallGraph *does* give the expected answer that "(unknown ? red : 
blue)()" could call either red() or blue() but not Base::virt(). 
Somehow having that vtable-based call present forces the other call to 
be unexpectedly conservative in its over-approximation.

Source code for my DSCallGraph tester is attached below.  I'd be most 
grateful for any clues you good people can provide.

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