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

John Criswell wrote:
> 1) I'll try out your example C++ code below and see if I can get the
> same results that you do. However, I'm at a conference right now
(Usenix
> Security), so I don't know exactly when I'll get to it.
Excellent.  Thanks, John!
> 2) DSA can get pessimistic results when dealing with external code (as
> Andrew described). It is designed for whole program analysis, meaning
> that the entire program should be available (e.g., no variables defined
> in other compilation units). Can you: [...]
I have made the recommended changes.  My test input is now a complete, 
self-contained program with a proper main.  I use "-internalize" on
the
"opt" command line to run llvm::InternalizePass before my
ShowCallGraph
pass.  (Sadly, llvm::InternalizePass::ID is not exposed through any 
headers, making it impossible to compile this pass-ordering requirement 
directly into my ShowCallGraph sources.)

The modified test input is attached below.  I'm happy to provide 
compiled bitcode, LLVM assembly source, or whatever else you need to 
reproduce the problem.  The ShowCallGraph pass is the same as in my 
earlier message at 
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042312.html>. 
When run on the bitcode for my updated test input, ShowCallGraph reports:

   call void %6(%struct.Base* %2)
	red()
	blue()
	Base::virt() const
	Derived::virt() const
   call void %12()
	red()
	blue()
	Base::virt() const
	Derived::virt() const

The first of those two calls is a vtable dispatch; the ideal answer 
would be Base::virt() const and Derived::virt() const, without red() and 
blue().  Still, vtable lookups are complex, so I could imagine an 
over-approximation here.

The second of those two calls is just a non-deterministic choice between 
two functions.  I'd really hoped that DSA would give the ideal answer 
here: red() or blue(), but not Base::virt() const or Derived::virt() const.

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

On Wed, Aug 10, 2011 at 1:39 PM, Ben Liblit <liblit at cs.wisc.edu>
wrote:
> The first of those two calls is a vtable dispatch; the ideal answer would
be
> Base::virt() const and Derived::virt() const, without red() and blue().
>  Still, vtable lookups are complex, so I could imagine an
over-approximation
> here.
>
> The second of those two calls is just a non-deterministic choice between
two
> functions.  I'd really hoped that DSA would give the ideal answer here:
> red() or blue(), but not Base::virt() const or Derived::virt() const.
>
Hi Ben!

This is actually the expected behavior for EQTD :).

In short, EQTD (and CBU) are useful for program-transforming passes
like pool allocation, but are _not_ good for alias analysis queries.
If you switch to TD you'll get better alias-analysis information, and
in this example the correct result. I changed both instances of
EQTDDataStructures to TDDataStructures in your example code, and got
the desired result (and confirmed that I get the results you report
when using EQTD).

Give that change a shot and let us know if you have any further
questions/issues.

FWIW at the moment DSA doesn't give good results for vtable-heavy
code, marking all such callsites as incomplete and cannot resolve
them.  Offhand, I don't remember if DSCallGraph will correctly report
a pessimistic callee set or if we expect you to look at the Incomplete
flag yourself.  Anyway, this is a fundamental limitation of DSA that
probably won't be fixed anytime soon, just a heads-up.

Hope this helps! :)

~Will

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