Re: C++ virtual function calls

David L Moore (dlmoore@ix.netcom.com) wrote:
: > for (...) {
: > foo->virtual_method(...);
: > }
: > Are compilers smart enough to lift the virtual lookup out of the loop?
: > Is this commonly done?


Because of the low level semantics of C++ code, this optimization
is not possible in general. Nothing prevents the programmer from
overwriting the object at the end of foo to be any (compatible) type.
For instance:


struct A {
    int a;
    virtual void foo();
    A() { a = 1; }
};
struct B : A {
    virtual void foo();
    B() { a = 2; }
};


void A::foo() { printf("A::foo %d\n",a); memcpy(this,new B,sizeof(B)); }
void B::foo() { printf("B::foo %d\n",a); memcpy(this,new A,sizeof(A)); }


main() {
    A * foo = new A;
    for (int i=0;i<10;i++) foo->foo();
}


: Given a loop with several virtual function calls:
: while (1) {
: x->Func1();
: x->Func2();
: y->SomeOtherFuncMaybe();
: etc...
: }
: When is it worthwhile hoisting the dispatching out of the loop and inlining
: the loop? That is, you turn the loop into a virtual function so that the
: virtual calls inside the loop can be statically bound and then pulled inline.


This sort of optimization most closely resembles "splitting" by
Chambers (1990). The idea is to insert conditionals which speculated
on the types of "x" and "y" and inline the methods under the
conditionals. The type information is then preserved by "splitting"
the following control flow path to preserve the type information:


@INPROCEEDINGS{Chambers90,
                AUTHOR = {C. Chambers and D. Ungar},
                TITLE = {Iterative Type Analysis and Extended Message Splitting},
                BOOKTITLE = {Proceedings of the SIGPLAN Conference on Programming Langua
ge Design and Implementation},
                YEAR = {1990},
                PAGES = {150-60}
}


The same result can be achieved as you said by combining speculatively
inlining with merging and lifting of conditionals:


Speculative Inline:


while (1){
      if (typeof(x)==FOO) {
            // code for FOO::Func1
      } else x->Func1();
      if (typeof(x)==FOO) {
            // code for FOO::Func2
      } else x->Func2();
}


Merge Conditionals:


while (1){
      if (typeof(x)==FOO) {
            // code for FOO::Func1
            // code for FOO::Func2
      } else { x->Func1(); x->Func2(); }
}


Lift Conditionals:


if (typeof(x)==FOO)
    while (1) {
            // code for FOO::Func1
            // code for FOO::Func2
    } else while(1) { x->Func1(); x->Func2(); }


You are correct about the speedups. For two examples of speedups
over C++ code of ~2x check out:


            http://www-csag.cs.uiuc.edu/papers/comp-oop.ps


--
    John Plevyak (plevyak@uiuc.edu) (217) 244-7116 PGP KeyID: 0x051130BD
                          Concurrent Systems Architecture Group
                    University of Illinois at Urbana-Champaign
      2233 Digital Computer Lab, 1304 West Springfield, Urbana, IL 61801
<A HREF="http://www-csag.cs.uiuc.edu/individual/jplevyak">My Home Page</A>
[It appears from other discussion that C++ forbids changing the type of an
object anywhere except in its contructor. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.