We've got the following test case:<br><br><br>class A {<br>public:<br> int x;<br> A(int x) : x(x) {}<br> int hoo() {return 4;}<br> virtual int foo() {return x;}<br> virtual int goo() {return foo()+10;}<br> virtual int operator+(A &a) {<br>
return x + a.x;<br> }<br>};<br><br>class B : public A {<br>public:<br> B(int x) : A(x) {}<br> int hoo() {return 2;}<br> virtual int foo() {return A::foo()*2;}<br>};<br><br>int main() {<br> A* a = new A(1);<br> B* b = new B(2);<br>
int y = a->foo() + b->goo() + a->hoo() + b->hoo() + (*a + *b);<br> delete a; delete b;<br> return y;<br>}<br><br><br>Clang with -O4 -S -emit-llvm emits the following for main():<br><br><br>define i32 @main() {<br>
%1 = tail call noalias i8* @_Znwm(i64 16), !dbg !70<br> %2 = bitcast i8* %1 to %class.A*, !dbg !70<br> tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata !68)<br> tail call void @llvm.dbg.value(metadata !71, i64 0, metadata !69)<br>
tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata !66)<br> tail call void @llvm.dbg.value(metadata !71, i64 0, metadata !67)<br> %3 = bitcast i8* %1 to i32 (...)***<br> store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*]* @_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %3, align 8<br>
%4 = getelementptr inbounds i8* %1, i64 8<br> %5 = bitcast i8* %4 to i32*<br> store i32 1, i32* %5, align 4, !tbaa !72<br> tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata !49), !dbg !70<br> %6 = tail call noalias i8* @_Znwm(i64 16), !dbg !75<br>
tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !57)<br> tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !58)<br> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !59)<br>
tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !60)<br> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !66)<br> tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !67)<br> %7 = getelementptr inbounds i8* %6, i64 8<br>
%8 = bitcast i8* %7 to i32*<br> store i32 2, i32* %8, align 4, !tbaa !72<br> %9 = bitcast i8* %6 to i8***<br> store i8** getelementptr inbounds ([5 x i8*]* @_ZTV1B, i64 0, i64 2), i8*** %9, align 8<br> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !52), !dbg !75<br>
%10 = bitcast i8* %1 to i32 (%class.A*)***, !dbg !77<br> %11 = load i32 (%class.A*)*** %10, align 8, !dbg !77<br> %12 = load i32 (%class.A*)** %11, align 8, !dbg !77<br> %13 = tail call i32 %12(%class.A* %2), !dbg !77<br>
%14 = bitcast i8* %6 to %class.A*, !dbg !77<br> %15 = bitcast i8* %6 to i32 (%class.A*)***, !dbg !77<br> %16 = load i32 (%class.A*)*** %15, align 8, !dbg !77<br> %17 = getelementptr inbounds i32 (%class.A*)** %16, i64 1, !dbg !77<br>
%18 = load i32 (%class.A*)** %17, align 8, !dbg !77<br> %19 = tail call i32 %18(%class.A* %14), !dbg !77<br> %20 = bitcast i8* %1 to i32 (%class.A*, %class.A*)***, !dbg !77<br> %21 = load i32 (%class.A*, %class.A*)*** %20, align 8, !dbg !77<br>
%22 = getelementptr inbounds i32 (%class.A*, %class.A*)** %21, i64 2, !dbg !77<br> %23 = load i32 (%class.A*, %class.A*)** %22, align 8, !dbg !77<br> %24 = tail call i32 %23(%class.A* %2, %class.A* %14), !dbg !77<br> %25 = add i32 %13, 6, !dbg !77<br>
%26 = add i32 %25, %19, !dbg !77<br> %27 = add i32 %26, %24, !dbg !77<br> tail call void @llvm.dbg.value(metadata !{i32 %27}, i64 0, metadata !54), !dbg !77<br> %28 = icmp eq i8* %1, null, !dbg !78<br> br i1 %28, label %30, label %29, !dbg !78<br>
<br>; <label>:29 ; preds = %0<br> tail call void @_ZdlPv(i8* %1) nounwind, !dbg !78<br> br label %30, !dbg !78<br><br>; <label>:30 ; preds = %29, %0<br>
%31 = icmp eq i8* %6, null, !dbg !78<br> br i1 %31, label %33, label %32, !dbg !78<br><br>; <label>:32 ; preds = %30<br> tail call void @_ZdlPv(i8* %6) nounwind, !dbg !78<br>
br label %33, !dbg !78<br><br>; <label>:33 ; preds = %32, %30<br> ret i32 %27, !dbg !79<br>}<br><br><br>It's a bit long-winded, but from looking at the code it's clear that no virtual calls are actually necessary, yet Clang and LLVM generated both of them.<br>
<br>In particular, we seek to implement the sort of analysis for devirtualization by Sonajalg et al in <a href="http://www.cs.ut.ee/%7Evarmo/seminar/sem09S/final/s6najalg.pdf">http://www.cs.ut.ee/~varmo/seminar/sem09S/final/s6najalg.pdf</a> but in C++, even if all we can get is a more conservative approximation in most cases. It's basically a lot of type analysis, and involves querying properties about types -lower- in the hierarchy than the declared or instantiated type, which doesn't seem to be an operation supported by Clang or debug metadata directly, so the only option (as we see it) is to build a custom representation of the class hierarchy from data we -do- have access to which allows it. Well, or generate even more metadata.<br>
<br>It's unclear to me how much assert/assume features would help. I can see it as useful for simplifying the process of determining how much precision is needed (e.g. in a file-scoped function, we know that its arguments can't come from somewhere external and hence could actually determine what the "lowest" type arguments can be), but it's unclear how this per se helps with obtaining type information, since the -g flag seems to generate sufficient data, but with no clear way to access it. It could just be myopia and ignorance on my part, though.<br>
<br><br>Thanks for your help,<br>-Vitor<br><br><div class="gmail_quote">On Thu, Dec 8, 2011 at 2:04 PM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com">dblaikie@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="HOEnZb"><div class="h5">On Thu, Dec 8, 2011 at 9:56 AM, Vitor Luis Menezes <<a href="mailto:vitor@utexas.edu">vitor@utexas.edu</a>> wrote:<br>
> Hello all,<br>
><br>
> Our compilers class has been using LLVM, and a partner and I decided to<br>
> implement devirtualization of virtual C++ calls in LLVM as a class project.<br>
> We quickly realized that existing debug metadata generated by Clang didn't<br>
> give us enough info to (precisely) implement this, and as such have already<br>
> begun modifying Clang to insert such metadata. However, for devirtualization<br>
> we also need to reconstruct the class hierarchy, which we also seek to do<br>
> through metadata. There appears to be sufficient metadata to do this, but we<br>
> can't seem to figure out how to actually access this metadata and<br>
> successfully reconstruct the class hierarchy. Can anyone help with this?<br>
><br>
> We're also open to alternative approaches, but we'd like to stay in LLVM IR<br>
> as much as possible.<br>
<br>
</div></div>Some of this is already done by LLVM/Clang - do you have particular<br>
cases that aren't being devirtualized that you want to focus on?<br>
<br>
For some brief background reading you might want to take a look at these bugs:<br>
<a href="http://llvm.org/bugs/show_bug.cgi?id=3100" target="_blank">http://llvm.org/bugs/show_bug.cgi?id=3100</a><br>
<a href="http://llvm.org/bugs/show_bug.cgi?id=810" target="_blank">http://llvm.org/bugs/show_bug.cgi?id=810</a><br>
<br>
Which are things I (& others more experienced than myself) have posted<br>
some thoughts on. If you're interested in pursuing PR810 then I have<br>
some code that Nick Lewycky passed on to me involving his experiments<br>
in this domain. & I'm also going to CC Eric Christopher because he<br>
mentioned he'd had some thoughts on how to achieve this (the general<br>
problem described in 810 about how to pass assumptions/facts from the<br>
frontend to the backend) & I never got around to asking him about the<br>
details.<br>
<br>
This approach should stay even more in LLVM IR than your proposed<br>
solution of metadata or debug info, but it may have<br>
limitations/problems that your proposed approach does not - so I<br>
certainly wouldn't rule anything out just yet.<br>
<span class="HOEnZb"><font color="#888888"><br>
- David<br>
</font></span></blockquote></div><br>