[LLVMdev] Implementing devirtualization
David Blaikie
dblaikie at gmail.com
Thu Dec 8 16:50:32 PST 2011
On Thu, Dec 8, 2011 at 4:26 PM, Eli Friedman <eli.friedman at gmail.com> wrote:
> On Thu, Dec 8, 2011 at 2:11 PM, Vitor Luis Menezes <vitor at utexas.edu> wrote:
>> We've got the following test case:
>>
>>
>> class A {
>> public:
>> int x;
>> A(int x) : x(x) {}
>> int hoo() {return 4;}
>> virtual int foo() {return x;}
>> virtual int goo() {return foo()+10;}
>> virtual int operator+(A &a) {
>> return x + a.x;
>> }
>> };
>>
>> class B : public A {
>> public:
>> B(int x) : A(x) {}
>> int hoo() {return 2;}
>> virtual int foo() {return A::foo()*2;}
>> };
>>
>> int main() {
>> A* a = new A(1);
>> B* b = new B(2);
>> int y = a->foo() + b->goo() + a->hoo() + b->hoo() + (*a + *b);
>> delete a; delete b;
>> return y;
>> }
>>
>>
>> Clang with -O4 -S -emit-llvm emits the following for main():
>>
>>
>> define i32 @main() {
>> %1 = tail call noalias i8* @_Znwm(i64 16), !dbg !70
>> %2 = bitcast i8* %1 to %class.A*, !dbg !70
>> tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata
>> !68)
>> tail call void @llvm.dbg.value(metadata !71, i64 0, metadata !69)
>> tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata
>> !66)
>> tail call void @llvm.dbg.value(metadata !71, i64 0, metadata !67)
>> %3 = bitcast i8* %1 to i32 (...)***
>> store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*]*
>> @_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %3, align 8
>> %4 = getelementptr inbounds i8* %1, i64 8
>> %5 = bitcast i8* %4 to i32*
>> store i32 1, i32* %5, align 4, !tbaa !72
>> tail call void @llvm.dbg.value(metadata !{%class.A* %2}, i64 0, metadata
>> !49), !dbg !70
>> %6 = tail call noalias i8* @_Znwm(i64 16), !dbg !75
>> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !57)
>> tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !58)
>> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !59)
>> tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !60)
>> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !66)
>> tail call void @llvm.dbg.value(metadata !76, i64 0, metadata !67)
>> %7 = getelementptr inbounds i8* %6, i64 8
>> %8 = bitcast i8* %7 to i32*
>> store i32 2, i32* %8, align 4, !tbaa !72
>> %9 = bitcast i8* %6 to i8***
>> store i8** getelementptr inbounds ([5 x i8*]* @_ZTV1B, i64 0, i64 2),
>> i8*** %9, align 8
>> tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !52),
>> !dbg !75
>> %10 = bitcast i8* %1 to i32 (%class.A*)***, !dbg !77
>> %11 = load i32 (%class.A*)*** %10, align 8, !dbg !77
>> %12 = load i32 (%class.A*)** %11, align 8, !dbg !77
>> %13 = tail call i32 %12(%class.A* %2), !dbg !77
>> %14 = bitcast i8* %6 to %class.A*, !dbg !77
>> %15 = bitcast i8* %6 to i32 (%class.A*)***, !dbg !77
>> %16 = load i32 (%class.A*)*** %15, align 8, !dbg !77
>> %17 = getelementptr inbounds i32 (%class.A*)** %16, i64 1, !dbg !77
>> %18 = load i32 (%class.A*)** %17, align 8, !dbg !77
>> %19 = tail call i32 %18(%class.A* %14), !dbg !77
>> %20 = bitcast i8* %1 to i32 (%class.A*, %class.A*)***, !dbg !77
>> %21 = load i32 (%class.A*, %class.A*)*** %20, align 8, !dbg !77
>> %22 = getelementptr inbounds i32 (%class.A*, %class.A*)** %21, i64 2, !dbg
>> !77
>> %23 = load i32 (%class.A*, %class.A*)** %22, align 8, !dbg !77
>> %24 = tail call i32 %23(%class.A* %2, %class.A* %14), !dbg !77
>> %25 = add i32 %13, 6, !dbg !77
>> %26 = add i32 %25, %19, !dbg !77
>> %27 = add i32 %26, %24, !dbg !77
>> tail call void @llvm.dbg.value(metadata !{i32 %27}, i64 0, metadata !54),
>> !dbg !77
>> %28 = icmp eq i8* %1, null, !dbg !78
>> br i1 %28, label %30, label %29, !dbg !78
>>
>> ; <label>:29 ; preds = %0
>> tail call void @_ZdlPv(i8* %1) nounwind, !dbg !78
>> br label %30, !dbg !78
>>
>> ; <label>:30 ; preds = %29, %0
>> %31 = icmp eq i8* %6, null, !dbg !78
>> br i1 %31, label %33, label %32, !dbg !78
>>
>> ; <label>:32 ; preds = %30
>> tail call void @_ZdlPv(i8* %6) nounwind, !dbg !78
>> br label %33, !dbg !78
>>
>> ; <label>:33 ; preds = %32, %30
>> ret i32 %27, !dbg !79
>> }
>>
>>
>> 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.
>
> Try with LLVM trunk; with some recent changes, LLVM's GVN is now a bit
> more powerful in situations like this.
Yep, looks better now (still lots of work done to call new/delete - I
guess I'd have to LTO that with the standard library to get them to go
away), it boils down to "ret i32 24"
Here's the full details:
; ModuleID = 'devirt.cpp'
target datalayout =
"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
%class.B = type { %class.A }
%class.A = type { i32 (...)**, i32 }
@_ZTV1B = linkonce_odr unnamed_addr constant [5 x i8*] [i8* null, i8*
bitcast ({ i8*, i8*, i8* }* @_ZTI1B to i8*), i8* bitcast (i32
(%class.B*)* @_ZN1B3fooEv to i8*), i8* bitcast (i32 (%class.A*)*
@_ZN1A3gooEv to i8*), i8* bitcast (i32 (%class.A*, %class.A*)*
@_ZN1AplERS_ to i8*)]
@_ZTVN10__cxxabiv120__si_class_type_infoE = external global i8*
@_ZTS1B = linkonce_odr constant [3 x i8] c"1B\00"
@_ZTVN10__cxxabiv117__class_type_infoE = external global i8*
@_ZTS1A = linkonce_odr constant [3 x i8] c"1A\00"
@_ZTI1A = linkonce_odr unnamed_addr constant { i8*, i8* } { i8*
bitcast (i8** getelementptr inbounds (i8**
@_ZTVN10__cxxabiv117__class_type_infoE, i64 2) to i8*), i8*
getelementptr inbounds ([3 x i8]* @_ZTS1A, i32 0, i32 0) }
@_ZTI1B = linkonce_odr unnamed_addr constant { i8*, i8*, i8* } { i8*
bitcast (i8** getelementptr inbounds (i8**
@_ZTVN10__cxxabiv120__si_class_type_infoE, i64 2) to i8*), i8*
getelementptr inbounds ([3 x i8]* @_ZTS1B, i32 0, i32 0), i8* bitcast
({ i8*, i8* }* @_ZTI1A to i8*) }
@_ZTV1A = linkonce_odr unnamed_addr constant [5 x i8*] [i8* null, i8*
bitcast ({ i8*, i8* }* @_ZTI1A to i8*), i8* bitcast (i32 (%class.A*)*
@_ZN1A3fooEv to i8*), i8* bitcast (i32 (%class.A*)* @_ZN1A3gooEv to
i8*), i8* bitcast (i32 (%class.A*, %class.A*)* @_ZN1AplERS_ to i8*)]
define i32 @main() uwtable {
invoke.cont3:
%call = tail call noalias i8* @_Znwm(i64 16)
%0 = bitcast i8* %call to i32 (...)***
store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*]*
@_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %0, align 8
%x2.i.i = getelementptr inbounds i8* %call, i64 8
%1 = bitcast i8* %x2.i.i to i32*
store i32 1, i32* %1, align 4, !tbaa !0
%call1 = tail call noalias i8* @_Znwm(i64 16)
%2 = bitcast i8* %call1 to i32 (...)***
%x2.i.i.i = getelementptr inbounds i8* %call1, i64 8
%3 = bitcast i8* %x2.i.i.i to i32*
store i32 2, i32* %3, align 4, !tbaa !0
store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*]*
@_ZTV1B, i64 0, i64 2) to i32 (...)**), i32 (...)*** %2, align 8
%isnull = icmp eq i8* %call, null
br i1 %isnull, label %delete.end, label %delete.notnull
delete.notnull: ; preds = %invoke.cont3
tail call void @_ZdlPv(i8* %call) nounwind
br label %delete.end
delete.end: ; preds =
%delete.notnull, %invoke.cont3
%isnull16 = icmp eq i8* %call1, null
br i1 %isnull16, label %delete.end18, label %delete.notnull17
delete.notnull17: ; preds = %delete.end
tail call void @_ZdlPv(i8* %call1) nounwind
br label %delete.end18
delete.end18: ; preds =
%delete.notnull17, %delete.end
ret i32 24
}
declare noalias i8* @_Znwm(i64)
declare void @_ZdlPv(i8*) nounwind
define linkonce_odr i32 @_ZN1B3fooEv(%class.B* nocapture %this)
nounwind uwtable readonly align 2 {
entry:
%x.i = getelementptr inbounds %class.B* %this, i64 0, i32 0, i32 1
%0 = load i32* %x.i, align 4, !tbaa !0
%mul = shl nsw i32 %0, 1
ret i32 %mul
}
define linkonce_odr i32 @_ZN1A3gooEv(%class.A* %this) uwtable align 2 {
entry:
%0 = bitcast %class.A* %this to i32 (%class.A*)***
%vtable = load i32 (%class.A*)*** %0, align 8
%1 = load i32 (%class.A*)** %vtable, align 8
%call = tail call i32 %1(%class.A* %this)
%add = add nsw i32 %call, 10
ret i32 %add
}
define linkonce_odr i32 @_ZN1AplERS_(%class.A* nocapture %this,
%class.A* nocapture %a) nounwind uwtable readonly align 2 {
entry:
%x = getelementptr inbounds %class.A* %this, i64 0, i32 1
%0 = load i32* %x, align 4, !tbaa !0
%x2 = getelementptr inbounds %class.A* %a, i64 0, i32 1
%1 = load i32* %x2, align 4, !tbaa !0
%add = add nsw i32 %1, %0
ret i32 %add
}
define linkonce_odr i32 @_ZN1A3fooEv(%class.A* nocapture %this)
nounwind uwtable readonly align 2 {
entry:
%x = getelementptr inbounds %class.A* %this, i64 0, i32 1
%0 = load i32* %x, align 4, !tbaa !0
ret i32 %0
}
!0 = metadata !{metadata !"int", metadata !1}
!1 = metadata !{metadata !"omnipotent char", metadata !2}
!2 = metadata !{metadata !"Simple C/C++ TBAA", null}
More information about the llvm-dev
mailing list