llvm dev - Apr 2008 - [LLVMdev] Virtual methods (was: LLVMBuilder vs LLVMFoldingBuilder)

Am Freitag, den 04.04.2008, 11:19 -0700 schrieb Chris
Lattner:
> On Fri, 4 Apr 2008, Joachim Durchholz wrote:
> >> No, please don't do this.  The idea of llvmbuilder is that it
is a
> >> "free" wrapper around the other existing API calls. 
Making the
> >> methods virtual would make them much more expensive.
> >
> > Wouldn't the class of the objects be known at compile time in most
> > cases? This is essentially just a case of precomputing constants, so I
> > think this should be possible.
> >
> > If yes, the compiler can predetermine the type, hence the virtual
method
> > table that will be used, and can replace the virtual call with a
static
> > one.
> 
> Please verify that this actually happens in practice with llvm-gcc and 
> gcc.
If that's already the case (which I'll gladly believe), where does the
performance overhead for virtual functions come from?
(Just curious.)

Regards,
Jo

In general, the C++ compiler does NOT know the type of the leaf class
when performing a virtual method invocation. In particular, a parameter
(including "this") alleging to be a Foo* (Foo being some class) may
actually be any subclass of Foo, so unless the compiler can trace the
value flow all the way from the instantiation, it can't tell.

The necessary tracing is (a) hard, (b) whole-program, and (c) therefore
not supportable without a lot of linker support that isn't available in
practice.


On Fri, 2008-04-04 at 21:09 +0200, Joachim Durchholz
wrote:
> Am Freitag, den 04.04.2008, 11:19 -0700 schrieb Chris Lattner:
> > On Fri, 4 Apr 2008, Joachim Durchholz wrote:
> > >> No, please don't do this.  The idea of llvmbuilder is
that it is a
> > >> "free" wrapper around the other existing API calls.
Making the
> > >> methods virtual would make them much more expensive.
> > >
> > > Wouldn't the class of the objects be known at compile time in
most
> > > cases? This is essentially just a case of precomputing constants,
so I
> > > think this should be possible.
> > >
> > > If yes, the compiler can predetermine the type, hence the virtual
method
> > > table that will be used, and can replace the virtual call with a
static
> > > one.
> > 
> > Please verify that this actually happens in practice with llvm-gcc and
> > gcc.
> 
> If that's already the case (which I'll gladly believe), where does
the
> performance overhead for virtual functions come from?
> (Just curious.)
> 
> Regards,
> Jo
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Fri, 4 Apr 2008, Joachim Durchholz wrote:
>> Please verify that this actually happens in practice with llvm-gcc and
>> gcc.
>
> If that's already the case (which I'll gladly believe), where does
the
> performance overhead for virtual functions come from?
> (Just curious.)
I don't understand what you're asking.  Please rephrase.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

Am Freitag, den 04.04.2008, 13:06 -0700 schrieb Chris
Lattner:
> On Fri, 4 Apr 2008, Joachim Durchholz wrote:
> >> Please verify that this actually happens in practice with llvm-gcc
and
> >> gcc.
> >
> > If that's already the case (which I'll gladly believe), where
does the
> > performance overhead for virtual functions come from?
> > (Just curious.)
> 
> I don't understand what you're asking.  Please rephrase.
Rephrased answer going to Jonathan's post.

Regards,
Jo

Am Freitag, den 04.04.2008, 15:19 -0400 schrieb Jonathan S.
Shapiro:
> In general, the C++ compiler does NOT know the type of the leaf class
> when performing a virtual method invocation. In particular, a parameter
> (including "this") alleging to be a Foo* (Foo being some class)
may
> actually be any subclass of Foo, so unless the compiler can trace the
> value flow all the way from the instantiation, it can't tell.
Right.
> The necessary tracing is (a) hard, (b) whole-program, and (c) therefore
> not supportable without a lot of linker support that isn't available in
> practice.
I'm not sure how hard (a) really is. It's being done in other imperative
OO languages, and quite successful there (the SmartEiffel folks have
reported they can eliminate the vtable lookup in about 90% of call
sites, reaping all the rewards of inlining etc. for these; you can
assume that practically all functions in Eiffel are declared virtual, in
fact you have to declare them nonvirtual if you want that and people
almost never do it).
In C++, integer-to-pointer tricks and array indexing via pointers could
make alias analysis more difficult. Is it that much harder that the
percentage of call sites to replace with static calls drops
significantly?

I agree with (b).

I agree with the "lot of linker support" bit in (c), but not quite
with
the "isn't available in practice" part - isn't link-time
optimization
one of LLVM's particular highlights?


I agree with Chris' reservations about virtual functions if a
gcc-compiled llvm-gcc is the norm.
If a bootstrapped llvm-gcc, compiled with itself, is the norm, *and*
alias analysis is good enough to deal with C++ as it is used in
llvm-gcc, then using virtual functions should not be a serious problem.


This all, of course, assuming I didn't overlook anything relevant.
Which is exactly my question: did I overlook something?

Oh, and this one, of course: are there ramifications for compilers that
use LLVM as a backend?
In particular: If a language makes any and all functions virtual, is
LLVM able to unvirtualize them (at the link stage, if necessary)?

Regards,
Jo