llvm dev - Aug 2011 - [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby

Will Dietz wrote:
> This is actually the expected behavior for EQTD :).
Expected by you, maybe.  :-D
> If you switch to TD you'll get better alias-analysis information, and
> in this example the correct result.
OK, I have switched to TDDataStructures as well, and I am also seeing 
much better (for my purposes) results in simple tests.  I'll keep poking 
at this some more and let you folks know if I hit any other surprises.

There is no mention of TDDataStructures in 
"poolalloc/dsa-manual/manual.tex", which is why I did not consider
using
it earlier.  Can you give me a high-level idea of how TDDataStructures 
and EQTDDataStructures differ?  Clearly they differ in the "gives the 
answers Ben expected" dimension, but that's not a very useful 
description more generally.  What should I know about the key 
differences between these two?
> FWIW at the moment DSA doesn't give good results for vtable-heavy
> code, marking all such callsites as incomplete and cannot resolve
> them.
Understood.  My plan for vtable-based calls is to pattern-match on the 
specific code sequences emitted by clang or whatever front end we are 
using.  Likewise I'll be exploiting C++ domain knowledge to recognize 
global variables that are vtables.  Once the clang type-system-rewrite 
work is released, that will also help me a lot as I'll have better 
information about the static types at each vtable call site.  So I think 
I'm in reasonable shape for vtables.  [I was prepared to be pleasantly 
surprised if DSA figured these out for me, but I certainly was not 
expecting or assuming that.]

Thanks again, Will, John, and Andrew.  You've been most helpful.  It's 
great to see that the high quality of LLVM's code is matched by the high 
quality of support found on this mailing list.

Regards,
Ben

I wrote:
> I'll keep poking at this some more and let you folks know if I hit any
other surprises.
Well, that didn't take long.  :-)  I have found two new surprises in 
DSCallGraph as built by TDDataStructures.  Consider the following 
program, which is complete and self-contained and which has one simple 
indirect call site:

	volatile int unknown;

	static void red() { }
	static void blue() { }

	int main()
	{
	  (unknown ? red : blue)();
	  return 0;
	}

If I save this as "test.c", compile it with clang, and run my 
ShowCallGraph testing pass, DSCallGraph lists *zero* callees and claims 
that its results for the indirect call site are incomplete.  Why is it 
unable to identify the two (seemingly-obvious) callees in this case? 
The bitcode generated for this call looks like:

     %7 = phi void (...)* [ bitcast (void ()* @red to void (...)*), %4 ],
                          [ bitcast (void ()* @blue to void (...)*), %5 ]
     call void (...)* %7()

If I save this same program as "test.cpp", compile it with clang, and 
run my ShowCallGraph testing pass, DSCallGraph correctly lists both 
red() and blue() as possible callees.  However, it still claims that its 
results are incomplete.  Why doesn't it know that its callee set is 
complete here?  The bitcode generated for this call is slightly 
different than for "test.c".  Here it looks like:

     %7 = phi void ()* [ @_Z3redv, %4 ], [ @_Z4bluev, %5 ]
     call void %7()

I would have expected any analysis to give the same results for either 
version of the bitcode: callee set is {red, blue} and this answer is 
complete.  What's going wrong here?

Attached below is an updated copy of my "ShowCallGraph.cpp" pass.  It 
now uses TDDataStructures (instead of EQTDDataStructures) and prints an 
additional line of output identifying incomplete callee sets.

Thanks for any hints,
Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ShowCallGraph.cpp
Type: text/x-c++src
Size: 1536 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110811/66060862/attachment.cpp>

On Thu, Aug 11, 2011 at 11:10 AM, Ben Liblit <liblit at cs.wisc.edu>
wrote:
>        volatile int unknown;
>
>        static void red() { }
>        static void blue() { }
>
>        int main()
>        {
>          (unknown ? red : blue)();
>          return 0;
>        }
>
> If I save this as "test.c", compile it with clang, and run my
ShowCallGraph
> testing pass, DSCallGraph lists *zero* callees and claims that its results
> for the indirect call site are incomplete.
Reproduced.
> If I save this same program as "test.cpp", compile it with clang,
and run my
> ShowCallGraph testing pass, DSCallGraph correctly lists both red() and
> blue() as possible callees.  However, it still claims that its results are
> incomplete.  Why doesn't it know that its callee set is complete here?
 The
> bitcode generated for this call is slightly different than for
"test.c".
>  Here it looks like:
>
>    %7 = phi void ()* [ @_Z3redv, %4 ], [ @_Z4bluev, %5 ]
>    call void %7()
>
> I would have expected any analysis to give the same results for either
> version of the bitcode: callee set is {red, blue} and this answer is
> complete.  What's going wrong here?
>
In C the red() and blue() declarations are var-args functions, in C++
they're void.  This difference is behind the IR you posted, and the
function pointer cast required in the C version.

Since DSA often has conservative results, one way to keep down
explosion of the size of the analysis information (while doing
interprocedural inlining) is to drop "illlegal" callgraph edges.  This
can be very useful in many cases, particularly at helping DSA scale on
large codes that are hard to analyze.  Anyway, one such arguably
illegal pairing is a varargs/nonvarargs mismatch between callsite and
callee, and filtering on this is what's causing the results you're
seeing.

To be maximally clear, DSA sees you calling a var-args method from a
non-varargs callsite and says "nope, that's illegal, that can't be
right" ("and if you really are doing so, your code is illegal, so oh
well"), and drops those as valid callees.

Luckily(-ish), the types of filtering used are controlled by flags,
and the flag for this option is "-dsa-no-filter-vararg".  Adding that
to the opt invocation (after -show-call-graph) causes DSA to give the
expected results on your example.

Interestingly we actually have a test case for this exact behavior,
that is presently failing (and is fixed by changing this option to not
filter in this way).  I admin I'm personally a little unclear on if
this is supposed to actually be illegal or not (and if it is, we might
want to special-case the no-argument ambiguity demonstrated in your
example _anyway_, since that's fairly common in C...).  Regardless of
what our defaults are, setting that option should get things going for
you, and I apologize for the trouble.

Thanks for your detailed reports, and happy callgraph building :)

~Will