Ben Liblit
2011-Aug-11 15:40 UTC
[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
Ben Liblit
2011-Aug-11 16:10 UTC
[LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
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>
Will Dietz
2011-Aug-11 23:22 UTC
[LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
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
Seemingly Similar Threads
- [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
- [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
- [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
- [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby
- [LLVMdev] incorrect DSCallGraph for simple indirect call with vtable nearby