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

[Will Dietz]

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